一种基于动态搜索的运行时GPU显存级数据复用优化方法

摘要

本发明公开了一种基于动态搜索的GPU显存级数据复用优化方法，首先，将已经执行的GPU计算任务的数据访问抽象为动态搜索树的叶子节点，将循环等抽象为搜索树的内部节点；其次，对GPU和CPU计算任务对数据的访问，在运行时逆向回溯检索搜索树发现数据复用，基于数据复用实现对数据的就近访问，有效减少了CPU-GPU数据传输次数。本发明放宽了已有技术对CPU访问GPU显存复用数据的限制，在不需要编译优化的情况下，更有效的利用GPU显存级数据复用消除冗余的CPU-GPU数据传输，进而更大程度地缩短整个应用问题的处理时间。

说明书

技术领域

本发明属于计算机图形处理技术领域，涉及一种数据复用方法，尤其是一种基于动态搜索的运行时GPU显存级数据复用优化方法。

背景技术

高性能计算发展水平是衡量一个国家综合国力与国际竞争力的重要指标，是一个国家科技实力的综合体现。在航空航天、核武研制、石油勘探、气象预报、生命科学、海啸与地震自然灾害预测等关键领域有着巨大应用需求。因此，世界各国都竞相将高性能计算作为技术与经济争夺的战略制高点。目前，异构并行系统架构为解决高性能计算提供了契机，它采用“主处理器+协处理器”的分工机制，主处理器负责逻辑性较强的事务处理，而协处理器则负责数据密集型计算任务。但随着主、协处理器架构的使用，两者之间的跨架构通信不可避免，使得高性能计算问题再次遇到了瓶颈。

在CPU-GPU异构并行系统中，CPU是主处理器，GPU是协处理器。在使用CPU-GPU系统处理一个涉及高性能计算的应用问题时，CPU负责把该问题的数据密集型计算任务加载到GPU上，利用GPU对数据的大规模并行处理加速计算任务的执行，进而缩短整个应用问题处理所需要的时间。但是，这个过程需要CPU将初始化数据传输到GPU，而GPU处理的结果也要传输给CPU，这就是前面所提到的架构之间的通信。由于CPU和GPU通过PCI-E总线互连，其通信延迟高开销大，严重影响了CPU-GPU解决高性能计算应用问题的性能提升。一种有效的解决方法是不同GPU计算任务之间复用GPU显存数据，即显存级数据复用，这样后执行的GPU计算任务访问复用数据时不需要再次取数据到GPU显存。

在当前技术中，可以使用源到源编译器Cetus提供的CPU-GPU通信优化技术或CGCM(CPU-GPU Communication Management)的Map Promotion对CPU-GPU数据传输进行优化。Cetus在包含GPU计算任务的循环中将复用数据的CPU-GPU数据传输移动到循环外，这样在循环执行时最多执行一次，不需要随循环迭代频繁执行。而CGCM使用源到源编译器，对于优化区域内GPU计算任务复用的数据，在GPU计算任务执行前后分别添加map和release外，并在优化区域开始之前添加map，在其后添加unmap和release，map等的介绍如下所示，其效果相当于将优化区域内对复用数据的CPU-GPU数据传输移动到优化区域外。

然而由于编译时识别和优化数据复用的限制，该类计算存在以下不足：

（1）优化条件过于严格限制了适用范围

在优化区域内，CGCM的Map Promotion要求优化区域(循环或子函数)内被优化的数据不被CPU写或被GPU写但不被CPU读，以确保数据访问的一致性；Cetus要求CPU不能对GPU使用数据进行访问。而事实上，CPU读GPU写后的数据时，只需要将其传输到内存即可，并不影响优化区域内GPU计算任务之间复用数据；该优化条件限制了Cetus和CGCM优化技术的适用范围。

（2）未考虑不同计算区域(如循环)之间的数据复用

Cetus和CGCM分别针对循环和循环与子函数等单一优化区域内的数据复用进行优化，没有考虑不同优化区域之间，如相邻循环之间的数据复用导致的CPU-GPU数据传输优化机会。由于程序员通常将整个循环作为单个GPU计算任务移植到GPU，因此，循环之间的数据复用对消除CPU-GPU数据传输更重要。

由于这些问题的存在，依靠编译时优化数据复用，不能充分消除所有可以消除的CPU-GPU跨架构数据传输。

发明内容

本发明的目的在于针对编译时优化GPU显存级数据复用存在的问题，提供一种基于动态搜索的运行时GPU显存级数据复用优化方法，该方法使用搜索树记录已经执行的GPU计算任务的数据访问，将GPU计算任务的数据访问抽象为搜索树的叶子节点并记录GPU对数据的修改情况，而将GPU计算任务和所在的循环等抽象为搜索树的内部节点。该方法能够解决已有的编译时显存级数据复用优化技术存在的缺陷。

本发明的目的是通过以下技术方案来解决的：

这种基于动态搜索的运行时GPU显存级数据复用优化方法，包括以下步骤：

1）使用搜索树表示程序执行：将已经执行的GPU计算任务的数据访问抽象为搜索树的access节点；而将程序中循环、循环迭代和GPU计算任务对应为搜索树的loop、iteration和funExec内部节点；并使用回溯搜索的方法，从与当前数据访问最近的funExec节点出发，逆向回溯检索搜索树；假设访问数据为d，对于所有已经执行的访问数据d的GPU数据访问，在搜索树最多保留一个access节点；

2）对于GPU计算任务访问数据d，当在搜索树中检索到访问数据d的access节点时，则说明数据d在GPU显存有效，GPU复用显存数据，此时若access节点记录的访问方式为读数据d且当前访问方式为写数据d，则将access节点的访问方式更新为写；当未检索到访存数据d的access节点时，说明数据d在GPU显存无效，使用新的access节点表示当前GPU计算任务的数据访问，并从内存中传输数据d到GPU显存；

3）对于CPU计算任务访问数据d，如果为CPU读数据d，此时若在搜索树检索到访问数据d的access节点且该节点表示GPU已经修改数据d，则说明数据d在GPU显存有效，在内存无效，执行显存到内存的数据更新；否则数据d在内存有效，CPU可复用内存数据。如果为CPU写数据d，则将搜索树中表示GPU访问数据d的access节点删除；

4）在数据d的生存期结束时，将表示数据d的access节点从搜索树删除。

进一步的，上述步骤1）中，回溯搜索的方法为：如果上次执行的funExec节点为t_c，则首先搜索t_c表示的子树，如果找到则返回。否则，令nt_c=t_c,t_c=t_c.parent,在t_c下搜索除nt_c外的所有其他子树，如此反复，直到找到或检索完整棵树；对于所有已经执行的GPU数据访问数据d，在搜索树最多保留一个access节点，具体实现方法为将存在数据复用的access节点移动到当前funExec节点下，表示当前GPU数据访问。

本发明具有以下有益效果：

本发明针对GPU显存级数据复用，提出一种基于动态搜索的运行时GPU显存级数据复用优化方法。该方法使用搜索树记录已经执行的GPU计算任务的数据访问，将GPU计算任务的数据访问抽象为搜索树的叶子节点并记录GPU对数据的修改情况，而将GPU计算任务和所在的循环等抽象为搜索树的内部节点。在运行时针对GPU和CPU计算任务的数据访问，通过对搜索树的搜索识别数据复用,复用GPU显存已有的数据，动态消除CPU和GPU之间的冗余数据传输。该方法不受编译时优化条件的限制，一方面尽可能利用数据复用减少了CPU-GPU数据传输量，另一方面减轻了编译器和程序员优化GPU显存级数据复用的负担。

附图说明

图1为本发明的搜索树节点数据结构图；

图2为本发明搜索树和程序执行示例图。

具体实施方式

下面结合附图对本发明做进一步详细描述：

本发明的基于动态搜索的运行时GPU显存级数据复用优化方法，具体包括下述步骤：

（1）使用搜索树表示程序执行：将已经执行的GPU计算任务的数据访问（读/写访问）抽象为搜索树的access节点；而将程序中循环、循环迭代和GPU计算任务对应为搜索树的loop、iteration和funExec内部节点；通过根节点链接程序中所有loop节点。如图1所示，loop的子节点为iteration节点，但iteration的子节点可以为funExec节点或loop节点。funExec的子节点只能是表示GPU计算任务数据访问的access节点。

该方法使用回溯搜索的方法，从上次执行的funExec节点出发，逆向回溯检索搜索树。例如，对图2所示程序，当执行到dystr.gpu_access e时，首先，检索与其最近的funExec3，未没找访问e的access节点；则将搜索范围扩大到funExec3的复节点Iteation所在的子树，继续检索；最后在Iteration k1下的funExec1找到与当前数据访问存在复用的access节点。

对于所有已经执行的GPU数据访问d，在搜索树最多保留一个access节点。如果当前GPU数据访问与搜索树已有的access节点访问同一数据，则将已有的access节点从原funExec子树移动到表示当前GPU计算任务执行的funExec子树，其过程如图2的虚线所示。

（2）GPU计算任务访问数据d时，当在搜索树中检索到访问数据d的access节点时，则说明数据d在GPU显存有效，GPU可复用显存数据，此时若access节点记录的访问方式为读数据d且当前访问方式为写数据d，则将access节点的访问方式更新为写；当未检索到访存数据d的access节点时，说明数据d在GPU显存无效，使用新的access节点表示当前GPU计算任务的数据访问，并从内存中传输数据d到GPU显存。

其次，需要通过依据数据访问在程序的位置创建搜索树的内部节点，例如funExec节点、iteration节点和loop节点。具体实现方法为在循环前后、循环的每次节点执行前后以及GPU计算任务执行前后，插入标识其执行区域的运行时系统调用；运行时依据这些调用标识的位置信息，插入相应的内存节点。另外，当移动transfer节点导致funExec等源节点变为空节点时，需要将这些节点从搜索树删除。本发明将这些功能集成到gpu_access调用中。

（3）对于CPU计算任务访问数据d，如果为CPU读数据d，此时若在搜索树检索到访问数据d的access节点且该节点标示GPU已经修改数据d，则说明数据d在GPU显存有效，在内存无效，执行显存到内存的数据更新；否则数据d在内存有效，CPU可复用内存数据。如果为CPU写数据d，则将搜索树中表示GPU访问d的access节点删除。当删除节点导致出现空的内部节点时，需要将这些节点从搜索树移除。本发明将这些功能集成到cpu_access调用中。

(4)在d生存期结束时，在搜索树中找到表示访问d的access节点，将其从搜索树移除。本发明将这部分功能集成到del调用中。

本发明DySTR简洁易用，程序员或源到源编译器使用本发明优化CPU-GPU数据传输时，只需要在CPU和GPU计算任务执行前，对所访读数据分别调用cpu_access和gpu_access；在执行后对所写数据调用cpu_access和gpu_access;并在数据生存期结束时，调用del。

使用已有优化方法对本发明提出的基于动态搜索的数据复用优化方法进行验证。首先，对于已有方法能进行优化的数据复用实例，本发明可以达到和已有方法相同的优化效果；其次，本发明可优化已有方法不能优化的数据复用。

（1）本发明可优化已有方法能优化的数据复用

由背景技术内容可知，Cetus和CGCM将复用数据d的CPU-GPU传输从优化区域(循环或子函数)内提取到优化区域外，使得该类数据传输在整个优化区域最多执行单次输入和单次输出。由于在优化区域内，CPU计算任务没有访问d。因此，在GPU计算任务首次访问数据d后，指向数据d的access节点一直保留在搜索树；之后GPU计算任务对数据d的任意GPU访问，都不会导致CPU-GPU数据传输。同Cetus和CGCM相比本发明不会引发多余的数据传输。

（2）对于已有方法不能有效优化的数据复用

对于Cetus和CGCM不能有效优化的数据复用，如在优化区域内循环或子函数中CPU访问了GPU计算任务访问的数据d（Example1），相邻外层循环之间的数据复用（Example2）。如Example1，Cetus和CGCM未考虑循环内CPU和GPU计算任务访问同一数据的情况。例如Example2，Cetus未考虑不同循环之间的数据复用机会；CGCM虽然考虑了不同循环之间的数据复用机会，但要求循环之间不能有CPU计算任务或将该CPU计算任务移植到GPU。这种约束限制了其适用范围。

本发明的一个应用实例如下所示：

对于上述例子，本发明只需将load和store替换为对gpu_access和cpu_access的调用，并插入表示循环、循环迭代和GPU计算任务的开始和结束的标识，即可在运行时有效利用数据复用优化消除冗余数据传输。分析结果表明，对于Example1程序，Cetus和CGCM的方法使得d₁被执行1次load，但不能优化d₂相关联的数据传输，d₂必须被执行10stores and10loads；而本发明使得数据d₁仅被执行1次load，数据d₂仅被执行10次store，减少了d₂相关的数据传输执行次数。对于Example2，在cpu_r不能被移植到GPU时，本发明比Cetus和CGCM少执行了一次数据d₁的load；在cpu_r可以被移植到GPU时，本发明比Cetus少执行一次数据d₁的load，和CGCM执行的数据传输次数相同。