一种面向数据密集型及依赖关系的并行计算方法

摘要

本发明属于并行系统的技术领域，涉及针对数据划分及并行调度策略定量化研究，特别提出一种面向数据密集型及依赖关系的并行计算方法。该方法包括：对于具有数据密集型特征的数据确定划分方法；对于具有数据密集型特征的并行计算建模及其相应并行化策略；基于并行化数据建模及并行化策略的调度策略与方法。本发明完全可应用于大规模海量数据的并行数字地形分析的高性能计算场合，例如，规则格网并行插值、坡度坡向并行计算、洼地填平并行计算，可视域地形分析等地形因子提取；可以应用于地理信息处理的高性能计算；也可以应用于基于地理信息的空间决策分析和数据挖掘等应用场合，提高处理效率。

说明书

技术领域

本发明属于并行系统的技术领域，涉及针对数据划分及并行调度策略定量化研究，特别提出运用数据依赖图建立数据关系模型和量化方法及基于数据模型并行计算方法。

背景技术

并行数字地形分析是并行计算与地理学科的有机结合。并行计算是计算机学科中重要的研究内容之一，最初用来解决数值或非数值的计算问题，主要面向的是大数据量的科学计算。数字地形分析(Digital Terrain Analysis，DTA）是在数字高程模型(Digital Elevation Model，DEM）的基础上进行地形属性计算和特征提取的数字信息处理技术。

随着各种传感器以及测量技术的更新，DEM数据规模增大，使单机环境下对海量数据的处理成为一件十分困难的事情。因此需要使用并行计算技术来解决单处理器的计算瓶颈问题。

目前，并行数字地形分析的研究主要集中在数据并行策略上。通过对现有的研究工作分析研究发现，尽管并行数字地形分析取得了一定的发展，并得到了不同程度的性能提升，但是数据并行的理论亟需系统化整理以及数据粒度的定量考核。众多学者将研究的热点集中在数据划分策略以及存储策略来更方便地管理海量空间数据，缺少量化的理论依据指导数据在并行化算法设计中的拆分和管理。数字地形分析主要通过对数据以及任务的拆分来实现并行化设计，存在复杂的数据依赖关系。并行数字地形分析具有其特有的数据特性，如果忽略数据之间的内在关系，就不能从内涵和本质上对并行计算中任务与数据之间的关系进行很好的厘定。如何进行数据的分解、数据的分发以及任务的调度都是影响并行化效率的关键因素。

发明内容

本发明针对上述技术问题，提出了对于具有数据依赖型特征的并行计算建模及其并行化策略及其相应的调度方法。

本发明所述的并行计算建模及其相应并行化策略与调度方法包括：

一种面向数据密集型及依赖关系的并行计算方法，包括如下步骤：

（1）对于具有数据密集型特征的数据确定划分方法；

（2）对于具有数据密集型特征的数据进行并行化数据建模及其相应并行化策略；

（3）基于步骤（2）的并行化数据建模及并行化策略进行调度。

步骤（1）划分方法的确定过程为：

步骤101：导入数据；对于具有数据密集型特征的并行计算建模，先将数据进行有效划分，然后针对每个块进行分别计算，最后进行结果融合；

步骤102：根据处理数据特征选择数据划分方法：包括条划分方法和块划分方法，其中条划分分为行划分和列划分，块划分分为方形数据划分和矩形数据划分；通过公式与计算节点数P的关系来确定划分块数n，若，则，否则n=P；其中，Msize为须处理数据大小，men为提供节点内存，k为提供节点的处理器数，P为计算节点数；

步骤103：根据数据划分方法进行相应的并行化方法处理数据。

当步骤（1）采用条划分方法时，步骤（2）的过程具体包括：

步骤201：对于具体数据密集型特征数据进行条划分，即按照行或列对数据进行划分；

步骤202：并行化策略:考虑处理算法对所划分数据块间是否存在依赖关系，若处理算法对于数据块之间无依赖关系，则执行步骤203，若处理算法对于数据块之间有依赖关系，则执行步骤204；

步骤203：若每个数据块的任务相互独立，则直接并行执行；

步骤204：若数据块的任务有相互依赖关系，则可从数据块1和数据块n开始逐次向中间顺序进行计算任务；每次有两个任务并行执行，故需要两个计算节点即可；

步骤205：执行后续任务。

当步骤（1）采用条划分方法时，步骤（2）的过程具体包括：

步骤301：对区域数据按照方块进行划分，若区域数据为方形，则执行步骤302；若区域数据为非正方形，则执行步骤305；

步骤302：并行化策略：对于建立n×n数据块划分方法，若数据块之间不存在依赖，则执行步骤303；若数据块之间存在依赖，则执行步骤304；

步骤303：若数据块对应的任务相互独立，在共享内存计算模式下则可用n²个节点进行并行计算获得最好的效率；在分布式式内存计算模式下，计算效率提升取决于粒度和数据分发度其中，T_cp为每个数据块的计算时间，T_cc为数据块之间的通信时间，T_dis每个数据块的分发时间；其需要的计算的最佳处理器数目p=[p+d]，其中[]为取整运算符；

步骤304：若数据块对应的任务之间存在依赖关系，则可将划分的数据块划为2n-1层，每层的数据块逐步增加，且每层最多有n个数据块，下层计算依赖上层结果，因此仅同一层中数据块可以并行计算，并行计算最多需要n个节点；

步骤305：并行化策略：对于建立n×m数据块划分方法，若数据块之间不存在依赖，则同步骤303处理方法；若数据块之间存在依赖，则执行步骤306；

步骤306：对于数据块存在依赖关系，则n×m的数据分块共有m+n-1层，每层最多有n个数据块，并行方法同步骤304；因此，其最多需要n个节点进行并行计算才能达到最高的加速比。

步骤（3）的调度方法包括：

步骤401：主节点选择有效的数据划分方法对数据进行划分，然后根据处理算法判断数据块是否具有依赖关系，主节点分发数据；

步骤402：根据处理算法判断数据块是否具有依赖关系，若数据块之间不存在依赖关系，则执行步骤403；若数据块之间存在依赖关系，则执行步骤404；

步骤403：主节点根据计算资源分发全部数据块，各个节点发起计算，并将计算结果发给主节点；

步骤404：若数据划分采用条划分方法，则执行步骤405；否则执行步骤408；

步骤405：主节点分发头与尾两个不存在依赖关系的数据块到两个节点，即数据块1和数据块n，节点发起计算，直到计算完毕；

步骤406：主节点继续分发数据块2和数据块n-1到上述两个节点，节点根据上层计算结果发起计算，直到计算完毕；

步骤407：依次处理到数据块n/2和数据块n/2-1，整个节点计算完毕，并将计算结果发给节点，执行步骤417；

步骤408：若数据划分为块状n×n划分，则执行步骤409；否则执行步骤416；

步骤409：根据数据依赖关系图，下层计算依赖上层结果，主节点分发第1层数据，即数据块1，节点发起计算，并将计算结果发回主节点；

步骤410：主节点分发第2层数据：主节点首先将依赖于数据块1的数据块2分发到原计算节点，节点进行计算，并将计算结果发回主节点；

步骤411：主节点同时启动一个新的节点，将依赖于数据块1的数据块3和上一层计算结果分发到新节点；节点进行计算，并将计算结果发回主节点；

步骤412：主节点分发第3层数据：主节点继续启动一个新的节点，并将依赖于上层数据的数据块和上层数据的计算结果分发到三个节点中，节点进行计算，并将计算结果发回主节点；

步骤413：依次处理后几层数据，每层启动一个新节点，直到n层数据处理结束，此时分节点总数为n；

步骤414：主节点分发第n+1层数据：根据数据依赖关系图，从n层数据之后，每层数据块开始逐一减少，主节点将不再启动新节点，分发n+1层数据块和n层计算结果到n-1个节点，n-1个节点进行计算，并将计算结果发回主节点；

步骤415：主节点依次分发后续几层数据块和依赖的计算结果，直到所有数据块计算结束，返回计算结果，执行步骤417；

步骤416：若数据划分为块状n×m划分，数据处理同块状n×n划分，但在处理完n层数据块之后，由于此时分块为n×m划分，则在此后|m-n+1|层，节点数均为n，处理时，主节点不须启动新的节点，执行步骤417；

步骤417：主节点收集整理处理结果。

本发明的技术特点及有益效果：

1、本发明是基于数据密集型数据，提出一种理论依据指导数据在并行化算法设计中的拆分和管理；考虑了复杂的数据依赖、任务依赖关系、如何进行数据和任务的分解、数据的分发以及任务的调度等重要因素。

2、本发明基于数据划分方法，分别考虑了数据块是否存在依赖关系，进行不同的数据处理并行化；同时提出相应的并行化计算过程调度算法。

3、本发明完全可应用于大规模海量数据的并行数字地形分析的高性能计算场合，例如，规则格网并行插值、坡度坡向并行计算、洼地填平并行计算，可视域地形分析等地形因子提取；可以应用于地理信息处理的高性能计算；也可以应用于基于地理信息的空间决策分析和数据挖掘等应用场合，提高处理效率。

附图说明

图1是本发明的实施例中对条形划分数据并行化处理案例，(a)为按条形划分数据情况，(b)为相应数据划分并行建模情况；

图2是本发明的实施例中对3×3划分数据并行化处理案例，(a)为按3×3块状划分数据情况，(b)为相应数据划分并行建模情况；

图3是本发明的实施例中对4×4划分数据并行化处理案例，(a)为按4×4块状划分数据情况，(b)为相应数据划分并行建模情况；

图4是本发明的实施例中对n×n划分数据并行化处理案例，(a)为按n×n块状划分数据情况，(b)为相应数据划分并行建模情况；

图5是本发明的实施例中对2×3划分数据并行化处理案例；(a)为按2×3块状划分数据情况，(b)为相应数据划分并行建模情况；

图6是本发明的实施例中对3×4划分数据并行化处理案例；(a)为按3×4块状划分数据情况，(b)为相应数据划分并行建模情况；

图7是本发明的实施例中对划分后数据进行并行计算调度算法流程图；

具体实施方式

以下结合附图对本发明具体说明。需要指出，所描述的实施例仅仅视为说明的目的，而不是对发明的限制。

本发明的实施例提供了一种面向数据密集型及依赖关系的并行计算方法，包括以下步骤：

1.并行计算建模的数据划分确定方法

步骤101：导入数据；对于具有数据密集型特征的并行计算建模，通常是将数据进行有效划分，然后针对每个块进行分别计算，最后进行结果融合；

步骤102：根据处理数据特征选择数据划分方法：常见的数据划分方法有条划分和块划分，其中条划分分为行划分和列划分，块划分分为方形数据划分和矩形数据划分。通过公式与计算节点数P的关系来确定划分块数n，若，则，否则n=P；其中，Msize为须处理数据大小，men为提供节点内存，k为提供节点的核数，P为计算节点数；

步骤103：执行后续任务。

如果处理算法对数据块间没有依赖关系，则对应每个数据块的任务就是独立，可以直接并行执行。如果数据块存在依赖的情况（见图1），因为数据块1和数据块n都是从边界开始，每次只有两个数据块可以进行并行计算，因此只需要两个节点就可以。

2.对于具有数据密集型特征数据进行条状划分并行计算建模方法包括：

步骤201：按照行或列对数据进行划分；

步骤202：并行化策略:考虑处理算法对所划分数据块间是否存在依赖关系，若处理算法对于数据块之间无依赖关系，则执行步骤203，若处理算法对于数据块之间有依赖关系，则执行步骤204；

步骤203：若每个数据块的任务相互独立，则直接并行执行。其效率取决于计算的节点数m；当n与m整除时，计算时间为nt/m；否则为([n/m]+1)t；其中t为单个数据块计算时间。

步骤204：若数据块的任务有相互依赖关系，则可从数据块1和数据块n开始逐次向中间顺序进行计算任务；每次有两个任务并行执行，故需要两个计算节点即可；当n为偶数时，计算时间为nt/2；否则为([n/2]+1)t；其中t为单个数据块计算时间。

3.对于具有数据密集型特征数据进行块状划分并行计算建模方法包括：

步骤301：对区域数据按照方块进行划分，若区域数据为方形，则执行步骤302；若区域数据为非方形，则执行步骤305；

步骤302：并行化策略：对于建立n×n数据块划分方法，若数据块之间不存在依赖，则执行步骤303；若数据块之间存在依赖，则执行步骤304；

步骤303：若数据块对应的任务相互独立，则可用n²个节点进行并行计算获得最好的效率，若受到计算资源的限制，其计算效率与计算节点数m相关，故其计算时间为[n²/m]t；

步骤304：若数据块对应的任务之间存在依赖关系，如图4所示，则可将划分的数据块划为2n-1层，每层的数据块逐步增加，且每层最多有n个数据块。因此，n×n数据块划分的并行计算最多需要n个节点，计算时间为T=(2n-1)t；每一层的数据块可并行计算，上一次执行完成之后才能执行下一层的数据块；

步骤305：并行化策略：对于建立n×m数据块划分方法，若数据块之间不存在依赖，则同步骤303处理方法；若数据块之间存在依赖，则执行步骤306；

步骤306：对于数据块存在依赖关系，则n×m的数据分块共有m+n-1层，每层最多有n个数据块。因此，其最多需要n个节点进行并行计算才能达到最高的加速比，并行计算的总时间为T=(m+n-1)t。

各种划分方法及并行策略比较：当划分的数据块之间不存在依赖关系时，依行或列为单位的条状数据块划分处理起来比较简单，并行计算效率高。当数据块之间存在依赖关系时，数据块只能按照先后关系进行计算，显然块状数据块划分优势明显，并行计算的效率要优于条状划分。方数据块要比矩形数据块更具有优势。因为当数据块的周长一定时，方数据块的面积最大，即数据块大，效率最高。

4.基于上述并行化数据建模及并行化策略的调度方法包括：

步骤401：主节点选择有效的数据划分方法对数据进行划分，然后根据处理算法判断数据块是否具有依赖关系，主节点分发数据。

步骤402：根据处理算法判断数据块是否具有依赖关系，若数据块之间不存在依赖关系，则执行步骤403；若数据块之间存在依赖关系，则执行步骤404。

步骤403：主节点根据计算资源分发全部数据块，各个节点发起计算，并将计算结果发给主节点；

步骤404：若数据划分为条状划分，则执行步骤405；否则执行步骤408；

步骤405：主节点分发头与尾两个不存在依赖关系的数据块到两个节点，即数据块1和数据块n，节点发起计算，直到计算完毕；

步骤406：主节点继续分发数据块2和数据块n-1到上述两个节点，节点根据上层计算结果发起计算，直到计算完毕；

步骤407：依次处理到数据块n/2和数据块n/2-1，整个节点计算完毕，并将计算结果发给节点，执行步骤417。

步骤408：若数据划分为块状n×n划分，则执行步骤409；否则执行步骤416；

步骤409：根据数据依赖关系图，下层计算依赖上层结果，主节点分发第1层数据，即数据块1，节点发起计算，并将计算结果发回主节点；

步骤410：主节点分发第2层数据：主节点首先将依赖于数据块1的数据块2分发到原计算节点，节点进行计算，并将计算结果发回主节点；

步骤411：主节点同时启动一个新的节点，将依赖于数据块1的数据块3和上一层计算结果分发到新节点；节点进行计算，并将计算结果发回主节点；

步骤412：主节点分发第3层数据：主节点继续启动一个新的节点，并将依赖于上层数据的数据块和上层数据的计算结果分发到三个节点中，节点进行计算，并将计算结果发回主节点；

步骤413：依次处理后几层数据，每层启动一个新节点，直到n层数据处理结束，此时分节点总数为n；

步骤414：主节点分发第n+1层数据：根据数据依赖关系图，从n层数据之后，每层数据块开始逐一减少，主节点将不再启动新节点，分发n+1层数据块和n层计算结果到n-1个节点，n-1个节点进行计算，并将计算结果发回主节点。

步骤415：主节点依次分发后续几层数据块和依赖的计算结果，直到所有数据块计算结束，返回计算结果，执行步骤417。

步骤416：若数据划分为块状n×m划分，数据处理同块状n×n划分，但在处理完n层数据块之后，由于此时分块为n×m划分，则在此后|m-n+1|层，节点数均为n，处理时，主节点不须启动新的节点，执行步骤417；

步骤417：主节点收集整理处理结果。