海量计算粗颗粒并行实现及计算任务随机动态分配方法

摘要

本发明公开了海量计算粗颗粒并行实现及计算任务随机动态分配方法，包括：将整个计算程序划分为多个互不重叠的计算颗粒，统计各计算颗粒的加权CPU时间和整个计算过程的总CPU时间；对各计算颗粒加权CPU时间的大小排序，选出并行粗颗粒；基于随机分配策略将并行粗颗粒执行的计算任务的序列随机打乱，形成新的序列；基于文件标记技术和先申请先分配策略，将计算任务分配到所有进程中，完成所有计算任务的并行计算；主进程收集计算结果并进行后处理，完成整个计算过程。本发明最大限度的减少了进程之间的通信，减少了多进程并行计算时所需内存的峰值，同时完美解决计算实例复杂度不对等带来的进程等待问题，进而大大提高并行计算效率。

说明书

技术领域

本发明涉及高性能计算技术领域，尤其涉及海量计算粗颗粒并行实现及计算任务随机动态分配方法。

背景技术

在电磁功能材料优化设计、测井响应及反演、复杂电磁环境与多物理场耦合计算、海洋环境数值模拟、分子动力学及个性化药物设计与筛选等领域，需要海量的同类型大规模数值计算。这类大规模数值计算由于不同计算实例具有不同结构，导致不同计算实例的计算复杂度不对等，对于这类不对等的海量计算，需要高效率并行计算方法设计，充分考虑不同实例计算复杂度的不对等，尽可能提高并行计算效率。

常规并行计算基本针对单个计算实例并行，在大量循环的计算部分实现并行，并行颗粒通常很细，这样导致不同进程之间存在大量的数据交换，降低并行效率；其次，由于不同进程计算进度不同，不可避免在需要数据共享和同步时出现大量等待，从而导致整体并行效率很低；再者，由于单个实例计算过程相当部分的计算过程有先后顺序，数据有依赖性，因此针对单个计算实例并行时，有相当部分的计算无法并行化，这也严重降低整体并行效率。

发明内容

针对上述问题中存在的不足之处，本发明提供海量计算粗颗粒并行实现及计算任务随机动态分配方法。

为实现上述目的，本发明提供一种海量计算粗颗粒并行实现及计算任务随机动态分配方法，包括：

步骤1、根据问题计算特征，将整个计算过程中执行相同类型的所有独立计算的计算程序定义为计算颗粒，并将执行整个计算过程的整个计算程序划分为多个互不重叠的计算颗粒，计算颗粒执行的一个独立计算作为一个计算任务；

步骤2、实现包含所有计算颗粒单次计算的串行计算，并统计各计算颗粒单次计算的CPU时间；

步骤3、计算各计算颗粒的加权CPU时间和整个计算过程的总CPU时间；

步骤4、对各计算颗粒按照加权CPU时间的大小进行排序，从大到小选出加权CPU时间之和大于99％总CPU时间的多个计算颗粒，并将选出的每个计算颗粒作为一个并行粗颗粒；

步骤5、执行并行粗颗粒前，采用主进程执行并行粗颗粒之外的计算颗粒；

步骤6、执行一个并行粗颗粒时，根据并行粗颗粒需要执行的所有计算任务，基于随机分配策略，主进程将并行粗颗粒执行的所有计算任务的序列随机打乱，形成新的计算任务序列；

步骤7、基于文件标记技术和先申请先分配策略，主进程按照新的计算任务序列将并行粗颗粒执行的所有计算任务分配到包含主进程的所有进程中，并完成计算任务的并行计算；

步骤8、重复步骤6～步骤7，依次完成每个并行粗颗粒需要执行的所有计算任务的并行计算；

步骤9、待所有并行粗颗粒需要执行的所有计算任务的并行计算完成后，主进程收集计算结果并进行后处理，完成整个计算过程。

作为本发明的进一步改进，所述计算颗粒的加权CPU时间的计算公式为：

T_weight,i＝N_task,iT_i

式中：T_weight,i为第i个计算颗粒的加权CPU时间，T_i为第i个计算颗粒单次计算的CPU时间，N_task,i为第i个计算颗粒执行的计算任务数。

作为本发明的进一步改进，所述整个计算过程的总CPU时间的计算公式为：

$>T=\underset{i=1}{\overset{m}{\Sigma }}{T}_{weight,i}$>

式中：T为整个计算过程的总CPU时间，m为整个计算程序被划分的计算颗粒数，T_weight,i为第i个计算颗粒的加权CPU时间。

作为本发明的进一步改进，在步骤6中，所述随机分配策略的实现方法为：

步骤6-1、将计算任务的序列List0＝{n}，对应生成随机数序列{R_n}，n＝1,2,3,…,N；

步骤6-2、对序列{R_n}从小到大排序，排序后的序列为{O_n}；

步骤6-3、生成新的不重复的计算任务序列List＝{L_n}。

作为本发明的进一步改进，在步骤7中，所述文件标记技术为：若并行粗颗粒中某计算任务被分配到一进程中，则生成该计算任务的状态文件；另一进程在申请分配某一计算任务时，将尝试生成该计算任务的状态文件，如果该状态文件存在，则表明该计算任务已经被分配，则所述另一进程将自动尝试申请分配下一个计算任务。

作为本发明的进一步改进，所述文件标记技术的实现方法为：

步骤7-1、一进程申请分配第i个计算任务；

步骤7-2、判断第i个计算任务的状态文件F_i是否存在，若存在则跳至步骤7-5，若不存在则跳至步骤7-3；

步骤7-3、生成状态文件F_i；

步骤7-4、完成第i个计算任务的计算；

步骤7-5、判断并行粗颗粒执行的所有计算任务是否全部完成，若未完成则i＝i+1，并返回步骤7-1，若已完成则跳至步骤7-6；

步骤7-6、结束。

作为本发明的进一步改进，所述步骤7-2与步骤7-3之间还包括：

步骤7-7、判断状态文件F_i是否被锁定，若被锁定则跳至步骤7-5，若未被锁定则跳至步骤7-8；

步骤7-8、锁定状态文件F_i；

所述步骤7-3与步骤7-4之间还包括：

步骤7-9、状态文件F_i解锁。

与现有技术相比，本发明的有益效果为：

本发明公开的海量计算粗颗粒并行实现及计算任务随机动态分配方法，该方法只对并行粗颗粒执行的计算任务采用所有进程进行并行计算，其它计算颗粒执行的操作只采用主进程执行，从而最大限度的减少了各进程之间的通信；通过随机分配策略将一并行粗颗粒执行的所有计算任务的序列进行随机打乱，同时基于文件标记技术和先申请先分配策略动态分配计算任务至所有进程，避免了多进程并行计算时因为内存峰值大于可用物理内存而造成的硬盘读写瓶颈，同时完美解决计算实例复杂度不对等带来的进程等待问题，进而大大提高并行计算效率。

附图说明

图1为本发明一种实施例公开的海量计算粗颗粒并行实现及计算任务随机动态分配方法的总体流程图；

图2为本发明一种实施例公开的随机分配策略的实现方法的流程图；

图3为本发明一种实施例公开的采用文件标记技术实现方法的流程图；

图4为本发明一种实施例公开的文件锁定与解锁技术的文件标记技术实现方法的流程图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明的一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明提供的海量计算粗颗粒并行实现及计算任务随机动态分配方法，该方法包括下述步骤：根据计算问题确定并行计算区域(即计算颗粒)；对每个计算颗粒串行实现相关计算并以粗颗粒为基本执行单元对程序并行化；根据各计算颗粒的任务完成情况，随机动态分配计算任务；采用文件标记技术记录计算任务正在实现和已经实现的状态；如果所有计算任务已经完成，主进程完成计算结果收集与后处理。相对于传统并行方法，本发明的方法实现粗颗粒并行，极大程度减少进程之间的通信及因为同步而产生的等待时间，同时，由于采用计算任务随机动态分配方法，保证复杂度不对等的计算模型随机均匀分布在各计算节点，避免由于过高的峰值内存导致虚拟内存访问而造成的硬盘读写瓶颈。

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

如图1-4所示，本发明提供海量计算粗颗粒并行实现及计算任务随机动态分配方法，包括：

在并行计算前，需人为的确定进程数，并将其中一个进程作为主进程。

S1、根据问题计算特征，将整个计算过程中执行相同类型的所有独立计算的计算程序定义为计算颗粒，从而将执行整个计算过程的整个计算程序划分为多个互不重叠的计算颗粒；其中，计算颗粒执行的一个独立计算作为一个计算任务，互不重叠的计算颗粒即互不重叠的涵盖整个计算过程的串行实现代码。

其中：问题计算特征为：对不同行业，问题计算特征各不相同。例如对于电阻率测井的测井响应计算，其问题计算特征是在某个地质条件下(地层结构、井眼大小、仪器结构和位置)仪器工作时的电磁场分布，并由此计算出指定电极的电流、电位大小；对于电磁功能材料的电磁响应计算，其问题计算特征是某种结构(包括几何结构和材料介质构成)的材料对某个频率电磁波的影响，即材料对电磁波的反射、透射和吸收效果；对于大规模集成电路电磁场分布计算，其问题计算特征是某种结构的多层集成电路板，在不同频率、或不同大小的电流驱动情况下各层板的电流、电位分布以及层与层之间电磁场分布情况；对于脑电问题的电磁场计算，其问题计算特征是脑内电偶极子某种分布情况下脑内的电磁场分布，进而计算头皮电位分布；对于药物设计的大规模筛选问题，其问题计算特征可能是某种结构大分子的自由能扰动。

其具体实施例为：若根据上述计算颗粒的定义将整个计算程序划分为a1、a2、a3、a4、a5共5个计算颗粒，5个计算颗粒可执行整个计算过程的计算任务；若a1执行1个计算任务，a2执行100个计算任务，a3执行2个计算任务，a4执行200个计算任务，a5执行2个计算任务；那么共305个计算任务构成整个计算过程，上述整个计算过程只需a1、a2、a3、a4、a5共5个计算颗粒来实现；其中执行整个计算过程依次需要a1、a2、a3、a4、a5这5个计算颗粒执行，且a1、a2、a3、a4、a5中均包含至少1个独立计算(计算任务)。

S2、实现包含所有计算颗粒单次计算的串行计算，并统计各计算颗粒单次计算的CPU时间。

其具体实施例为：根据问题计算特征为每个计算颗粒所需执行的所有计算任务中选取一个经典计算任务，并将a1、a2、a3、a4、a5这5个计算颗粒执行的5个经典计算任务实现a1～a5顺序执行一次的串行计算，根据单次计算的串行计算结果，统计5个计算颗粒完成单次经典计算任务计算所需的CPU时间。

S3、计算各计算颗粒的加权CPU时间和整个计算过程的总CPU时间。

其中：计算颗粒的加权CPU时间的计算公式为：

T_weight,i＝N_task,iT_i

式中：T_weight,i为第i个计算颗粒的加权CPU时间，T_i为第i个计算颗粒单次计算的CPU时间，N_task,i为第i个计算颗粒执行的计算任务数。

整个计算过程的总CPU时间的计算公式为：

$>T=\underset{i=1}{\overset{m}{\Sigma }}{T}_{weight,i}$>

式中：T为整个计算过程的总CPU时间，m为整个计算程序被划分的计算颗粒数，T_weight,i为第i个计算颗粒的加权CPU时间。

S4、对各计算颗粒的计算时间按照加权CPU时间的大小进行排序，从大到小选出加权CPU时间之和大于99％总CPU时间的多个计算颗粒，并将选出的每个计算颗粒作为一个并行粗颗粒。

其具体实施例为：根据各计算颗粒计算所得的加权CPU时间进行大小排序，若a1加权CPU时间为0.1s，a2加权CPU时间为100s，a3加权CPU时间为0.2s，a4加权CPU时间为50s，a5加权CPU时间为0.3s，则最终排序结果为a2>a4>a5>a3>a1；5个计算颗粒的加权CPU时间从大到小依次相加，即T(a2)+T(a4)+…直到时间和大于总CPU时间的99％为止；如果T(a2)+T(a4)>99％，那就是a2、a4分别作为一个并行粗颗粒；如果T(a2)>99％总CPU时间，那么a2为并行粗颗粒。

S5、在串行版本的基础上对程序进行并行化，以并行粗颗粒为基本执行单元进行并行，在执行并行粗颗粒前，采用主进程执行并行粗颗粒之外的计算颗粒。

其具体实施例为：在执行整个计算过程的整个计算程序中并行粗颗粒a2并行计算前需要先执行a1；并行粗颗粒a4并行计算前需要先执行a3，并行计算后需要执行a5；其中a1、a3、a5采用主进程进行执行。

S6、执行S4定义的一个并行粗颗粒(a2)时，根据并行粗颗粒(a2)需要执行的所有计算任务，基于随机分配策略，主进程将并行粗颗粒(a2)执行的所有计算任务的序列随机打乱，形成新的计算任务序列。

所述随机分配策略的实现方法为：

步骤6-1、将计算任务的序列List0＝{n}，对应生成随机数序列{R_n}，n＝1,2,3,…,N；

步骤6-2、对序列{R_n}从小到大排序，排序后的序列为{O_n}；

步骤6-3、生成新的不重复的计算任务序列List＝{L_n}，L_n为O_n在R_n中的位置。

其中，随机分配策略，其关键在于将并行粗颗粒中所有计算任务的序列List0＝{1,2,3,…,N}随机打乱，产生新的不重复的计算任务序列List＝{L₁,L₂,…,L_N}，然后按照该序列顺序分配计算任务，即等效为对原始计算任务进行随机分配，该随机分配策略特征在于随机分配方案能彻底打乱所有计算任务的分配顺序，从而实现各计算节点同时计算的任务占用的峰值内存总和由进程数和所有模型(计算颗粒)占用峰值内存的平均值而非最高值决定。产生新的不重复的计算任务序列的流程图如图2所示。

S7、基于文件标记技术和先申请先分配策略，主进程按照S6形成新的计算任务序列将S6中该并行粗颗粒(a2)所需执行的所有计算任务分配到包含主进程的所有进程中，并完成并行粗颗粒(a2)执行的所有计算任务的并行计算。

其中，先申请先分配策略基于文件标记技术实现；在多进程并行计算过程中，各个进程分配到某个计算任务的机会是均等的，如果不采取任何措施，可能导致多个进程被分配到同一计算任务，造成计算资源的浪费，因此必须采取某种措施，使得所有计算任务被唯一分配到某个进程。达到这一目的最简单也最直观的措施是分配任务及时标记，即任务被分配到某一进程的同时即将该任务进行标记，这样其他进程不再分配该任务。但由于并行计算时各进程的变量一般情况下相互独立，且计算任务不对称，各进程计算状态不同，任何进程通过变量标记任务被分配的信息无法立即被传递到其他进程，因此必须采用一种外在显式的标记方法使得计算任务一旦被标记，所有进程都能获得这个信息。本发明提出采用文件标记技术，若并行粗颗粒中计算任务被分配到进程中，马上生成计算任务的状态文件；某一进程在申请分配某一计算任务时，将试图生成该计算任务的状态文件，如果该状态文件存在，则表明该计算任务已经被分配，该进程将自动尝试申请分配下一个计算任务。

如图3所示，每个并行粗颗粒中均需要采用文件标记技术进行分配其各自所需执行的所有计算任务，其中文件标记技术的实现方法为：

步骤7-1、一进程申请分配第i个计算任务；

步骤7-2、判断第i个计算任务的状态文件F_i是否存在，若存在则跳至步骤7-5，若不存在则跳至步骤7-3；

步骤7-3、生成状态文件F_i；

步骤7-4、完成第i个计算任务的计算；

步骤7-5、判断并行粗颗粒执行的所有计算任务是否全部完成，若未完成则i＝i+1，并返回步骤7-1，若已完成则跳至步骤7-6；

步骤7-6、该并行粗颗粒所需执行的所有计算任务全部分配到所有进程中，该并行粗颗粒的分配结束；其返回执行其他并行粗颗粒分配其各自所需执行的所有计算任务。

文件标记技术采用文件锁定与解锁技术，文件锁定与解锁技术保证一次只能一个进程读/写同一计算任务，防止多个进程同时操作同一文件，导致重复计算同一个计算任务。文件读写锁具有很高的并行性，可以有多个线程同时占用读模式的读写锁，但是只能有一个线程占用写模式的读写锁，读写锁的三种状态：

1、当读写锁是写加锁状态时，在这个锁被解锁之前，所有试图对这个锁加锁的线程都会被阻塞；

2、当读写锁在读加锁状态时，所有试图以读模式对它进行加锁的线程都可以得到访问权，但是以写模式对它进行加锁的线程将会被阻塞；

3、当读写锁在读模式的锁状态时，如果有另外的线程试图以写模式加锁，读写锁通常会阻塞随后的读模式锁的请求，这样可以避免读模式锁长期占用，而等待的写模式锁请求则长期阻塞。

处理读者-写者问题的两种常见策略是强读者同步(strong readersynchronization)和强写者同步(strong writer synchronization)。在强读者同步中，总是给读者更高的优先权，只要写者当前没有进行写操作，读者就可以获得访问权限；而在强写者同步中，则往往将优先权交付给写者，而读者只能等到所有正在等待的或者是正在执行的写者结束以后才能执行。

采用C++实现的文件锁定与解锁技术的典型代码如下所示：

创建标识文件并加锁，其他进程不能读/写该文件：

out.open(filename,_SH_DENYRW)；

读标识文件并加锁，其他进程不能写该文件：

ifstream in(filename,ios::in,_SH_DENYWR)；

写标识文件并加锁，其他进程不能读/写该文件：

out.open(filename,ios::app,_SH_DENYRW)。

如图4所示，采用文件锁定与解锁技术的文件标记技术的实现方法为：

步骤7-1、一进程申请分配第i个计算任务；

步骤7-2、判断第i个计算任务的状态文件F_i是否存在，若存在则跳至步骤7-8，若不存在则跳至步骤7-3；

步骤7-3、判断状态文件F_i是否被锁定，若被锁定则跳至步骤7-8，若未被锁定则跳至步骤7-4；

步骤7-4、锁定状态文件F_i；

步骤7-5、生成状态文件F_i；

步骤7-6、状态文件F_i解锁；

步骤7-7、完成第i个计算任务的计算；

步骤7-8、判断并行粗颗粒中的所有计算任务是否全部完成，若未完成则i＝i+1，并返回步骤7-1，若已完成则跳至步骤7-9；

步骤7-9、该并行粗颗粒所需执行的所有计算任务全部分配到所有进程中，该并行粗颗粒的分配结束；其返回执行其他并行粗颗粒分配其各自所需执行的所有计算任务。

S8、重复S6～S7，依次完成每个有并行粗颗粒需要执行的所有计算任务的并行计算。

其具体实施例为：假设a1、a2、a3、a4、a5中，a1、a3、a5为无需并行计算的计算颗粒，a2、a4为需要并行计算的并行粗颗粒；则主进程执行计算颗粒a1，并基于S7通过所有进程实现并行粗颗粒a2需要执行的所有计算任务的并行计算，主进程执行a3(收集并行粗颗粒a2的计算结果)，并转入下一个并行粗颗粒a4，采用a2类似的方法，并行粗颗粒a4通过所有进程实现a4需要执行的所有计算任务的并行计算，完成所有并行粗颗粒的并行计算。

S9、待所有并行粗颗粒需要执行的所有计算任务的并行计算完成后，主进程收集计算结果(即主进程执行计算颗粒a5)并进行后处理，完成整个计算过程。根据不同问题计算特征，完成相应的后处理过程；如归并、整理等。

复杂地层的电法测井响应计算、复杂结构的电磁功能材料电磁响应计算等计算模型表明，同一类型计算由于模型结构不同，导致网格剖分产生的单元数量有较大差异，从而不同模型计算需要的内存也有较大差异。统计结果表明，如果采用二阶有限元计算，相同网格剖分参数设置情况下，计算不同模型所需的内存峰值最小约为8GB，最大则超过20GB。如果一个集群每个节点内存为48GB，利用该集群采用二阶有限元并行计算，最简单的模型可以同时开启6个进程，最复杂的模型则只能同时开启2个进程，否则系统会将部分硬盘空间作为虚拟内存供程序使用。目前常用的HDD硬盘读写速度在80MB/s左右，而物理内存的读写速度有百倍以上的提高，例如，对于DDR31333MHz的服务器内存，其数据传输速率达到10.6GB/s。这一比较结果说明，如果并行计算开启的进程过多，导致计算过程中部分硬盘存储空间被当作虚拟内存读取，将使得程序运行速度降低百倍以上。为避免计算过程中部分硬盘存储空间被当作虚拟内存读取的现象，在开启进程时，需要考虑每个进程运行时可能需要的最大内存，以此为依据确定每个节点能开启的最大进程数。如果采用普通方法粗颗粒并行计算，则每节点最多能开启2个进程。实验结果表明，采用本发明的随机动态分配计算任务策略，每节点开启4个进程，内存使用率长期在80％以上，且无硬盘空间作为虚拟内存供程序使用的情况，基本做到了内存使用峰值平均化和内存峰值出现时间上的错位。

本发明公开的海量计算粗颗粒并行实现及计算任务随机动态分配方法，该方法只对并行粗颗粒执行的计算任务采用所有进程进行并行计算，其它计算颗粒执行的操作只采用主进程执行，从而最大限度的减少了各进程之间的通信；通过随机分配策略将一并行粗颗粒执行的所有计算任务的序列进行随机打乱，同时基于文件标记技术和先申请先分配策略动态分配计算任务至所有进程，避免了多进程并行计算时因为内存峰值大于可用物理内存而造成的硬盘读写瓶颈，同时完美解决计算实例复杂度不对等问题，进而大大提高并行计算效率。

以上仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。