基于PRAM并行模型最大值查找的方法与改进①

贺 成,施华君

(中国电子科技集团公司第三十二研究所,上海 201808)

当今许多尖端技术的解决都离不开并行处理,许多国家都将其列入关键技术.并行机的发展和智能计算等实际应用的需要共同促进了并行算法的研究[1,2].算法是求解问题的步骤和方法[3].简单的讲,并行算法是用多台处理器联合求解问题的方法和步骤[4,5].并行算法不能仅通过时间复杂度[6]来进行评价,因为人们在对计算速度的渴求的同时,对于并行处理所需要的处理器数量急剧增长的问题也开始关心.所以,评判并行算法综合性能的指标“成本”显得格外的重要.并行算法的成本是指并行算法在并行机各处理器上运行时间总和Cost=Tp∗P[7],Tp代表每个处理器处理问题的运行时间,P代表处理器数量.并行算法相比串行算法而言,可以在更短的时间内给出问题的答案,满足了应用对于实时性的要求.但是并行算法所带来的额外开销也是不容忽视的,其中并行算法对于处理器数量的要求导致并行算法的实现是昂贵的.这无疑给有些并行算法的实现带来一定的限制.其中并行算法中最大值查找就存在成本过高的问题.

本文以最大值查找算法为基础,探讨了3种并行化查找最大值的方法(平衡树方法、双对数深度树方法、快速查找法),进而提出提出了一种比平衡树算法,快速查找法,双对数深度树方法并行成本(Cost)更优的基于数据划分方法的最大值查找并行算法.该方法通过减少处理器使用的数量,维持处理问题时间与平衡树方法一致,以此取得相比平衡树方法,双对数深度树方法,快速查找法在并行成本上表现更优的算法.为之后的相关并行算法的优化提供一个改进的方向,为大数据处理中查找最大值提供了一个可行的办法.

本文并行算法研究是在PRAM[8,9]模型下进行的,但微型计算机CPU架构中的SIMD并行机制,由于实现指令的复杂性,几乎没有编译程序将高级语言设计的程序优化到SIMD指令级别[10].因此本文通过模拟仿真实验对几种并行查找算法的实际运行时间进行对比.

1 并行查找最大值的算法

1.1 平衡树查找方法

1.1.1 算法原理

利用平衡二叉树[11-13](Balanced Binary Tree)抽象出并行求解最大值的方法,树的叶节点是输入元素集合,树的非叶节点用于比较操作,树的高度为H.在树的同一深度上内节点并行计算.树中的节点都包含两个子节点,所以每个节点只需要一个处理器就可以在常数时间内做出比较操作,同一深度并行计算需要的处理器数目与内节点数相同,这样仅需要O(H)的时间就可以完成最大值查找.需要处理器数目为2H-1.如图1.

下面是平衡树方法的伪代码[14]:

输入:n = 2m个数存于数组A(n:2n-1)中.输出:最大值,位于A(1).Balance(Element A[]){for k=m-1 to 0 do for j=2k to 2k+1-1 par-do A[j]=max{A[2j],A[2j+1]}}

图1 平衡树查找最大值

1.1.2 算法分析

平衡二叉树算法的运行时间为Tp=O(logN),处理器数目P(n)=O(N/2),并行成本Cost=Tp∗P=O(NlogN).从时间复杂度上来看,平衡树算法运行速度较快.该方法能快速缩减待比较的数据量,因此速度得到了极大的提升.但是由于每次操作之后待比较数据都减少一半,所以每轮操作之后都有一半当前参与工作的处理器无事可做.直到树根时,仅仅有一个处理器在工作.平衡树方法的优点是可以快速缩减待比较数据量,从而提高查找速度.但是由于其自身结构的原因,导致了处理器负载不均衡[15,16],处理器利用率不高.

1.2 快速查找方法

1.2.1 算法原理

通过比较手段快速获取集合中的最大值[17],每次操作就需要确定更多元素之间的大小关系,也就是每次操作需要更多元素进行比较.快速并行算法利用一个n*n的逻辑二维表来存储某一个元素与集合中其余元素的大小关系(0表示小于,1表示不小于),如表1.当某一行或者某一列元素关系都为“大于”时,该行(列)代表的元素为最大值.

表1 逻辑关系表

下面是快速并行算法的伪代码[14]:

输入:存有n个不同元素的数组A.输出:布尔数组M,当且仅当A(i)=max{A}时,M(i)=1.Quick(Element A[]){(1)for 1＜=i,j＜=n par-do

if A[i] ＞= A[j]B[i][j] = 1 else B[i][j] = 0(2)for 1＜=i＜=n par-do M[i]=B[i][1]∩B[i][2]∩… ∩B[i][n]}

该算法要求步骤(1)同时读,步骤(2)要求同时写.

1.2.2 算法分析

算法执行时间为Tp(n)=O(1),使用了P(n)=O(N2)个处理器,成本为Cost=Tp∗P=O(N2).从时间复杂度上看,该算法是目前已知运行速度最快的最大值查找并行算法.与平衡树方法和双对数方法每轮操作只能确定部分元素之间大小关系,该算法每轮操作都可以确定一个元素与其余所有元素的大小关系.利用这一并行思想可以快速确定所有元素之间的关系,但是该方法缺点就是所需要的处理器数目过多,处理器数目将会以元素个数的指数增长,并且对于处理器之间的通信速度要求极高,算法实现要求条件苛刻.

1.3 双对数深度树查找方法

1.3.1 算法原理

所有输入数据作为叶节点,节点u的子节点数为其中Nu是节点u所包含的叶节点的数目.规定节点u的层为u到根路径的边数,显然根节点的层为0[14].假定共有元素则第i层有 个节点,每个节点有个子节点.由此可以计算出树的高度为k+1=loglogN.图2为当N=16时的双对数深度树[18].

图2 双对数深度树

下面是双对数深度树方法的伪代码:

22k输入: n = 个数存于数组A(1:n)中.输出:布尔数组M,当且仅当A(i)=max{A}时,M(i)=1.

DoubleTree(Element A[]){(1)for j=1 to n/2 do A[j]=max{A[2j-1],A[2j]}(2)for i=k-1 to 0 do 22k−2k−i for m=0 to m= par-do 22k−i−122k−i−1 Quick(A[m* :(m+1)* ])}

1.3.2 算法分析

算法执行时间Tp(n)=O(loglogN),使用了P(n)=O(N)个处理器,成本为Cost=Tp∗P=O(NloglogN).双对数深度树每次比较操作之后,待比较数据量减少的速度比平衡树方法更快,每个处理器的工作量相比平衡树方法都有更好的提升,所以双对数深度树的查找时间比平衡树更快.但是双对数深度树的每个节点的最大值都是通过调用快速查找算法而实现的,所以双对数深度树的方法的实现的难度仍然很大.

2 基于数据划分的最大值查找算法

基于数据划分的最大值查找算法(以下简称为“数据划分方法”)针对平衡树算法处理器工作分配不均导致工作效率低下,快速查找算法对于处理器数量需求过大,以及双对数深度树方法难以实现的问题进行了改进.汲取了双对数深度树中处理器工作饱满,查找时间快,快速查找算法逻辑表比较数据法的优点.提出了一种比平衡树算法,快速查找法,双对数深度树方法并行成本Cost更优的基于数据划分方法的最大值查找并行算法,通过降低处理器(P)数量,保证处理时间(Tp)达到O(logn)量级,来达到降低并行成本的目的.

数据划分方法使用比第一节中3种并行方法更少的处理器,保证处理速度达到O(logn)级,就必须充分利用每个处理器的工作效率,从而保证数据划分方法不会因为处理器数目的减少,而使得问题处理速度远远慢于平衡树方法.研究过程中发现利用逻辑表将数据进行合理的划分为多个组,可以提升每个处理器的效率,且能快速降低待查找数据集.

最终实现了一种比平衡树算法,快速查找法,双对数深度树方法并行成本额Cost更优的高度可行的基于数据划分查找最大值的并行算法.

2.1 算法原理

从逻辑上将集合中的数据进行分组,假设共N个元素,分为logN组,每组N/logN个元素,共N/logN个处理器.

Step1.每组都采取两两元素比较的方式,使每组元素个数都减少为N/(2logN)个元素.由于每组需要N/(2logN)个处理器,所以每两组可以并行计算,共需要(logN)/2步完成所有操作.

Step2.此时每组所剩元素为N/(2logN)个,继续采用两两比较的方式,使每组元素个数都减少为N/(4logN).由于每组需要N/(4logN)个处理器,所以每四组可以并行计算,共需要(logN)/4步完成所有操作.

Step3.此时每组所剩元素为N/(4logN)个,继续采用两两比较的方式,使每组元素个数都减少为N/(8logN).由于每组需要N/(8logN)个处理器,所以每八组可以并行计算,共需要(logN)/8步完成所有操作.

依次类推,最终的目的是使得每组剩余元素个数为1.而此时需要log(N/2logN)步完成.当每组只剩1个元素的时候,就可以采用平衡树或双对数深度树进行求解最终的最大值.

下面是基于数据划分算法的伪代码:

输入: n个数存放于A[logn][logn]数组中输出:最大值A[1][1]Data_Partition(Element A[][]){for i = 1 to log(n/(2logn))for m=1 to logn par-do blance(A[m][1:(logn)/i])Blance(A[1:logn][1])}

2.2 算法分析

3 实验方式

Pan[19]和Pavel[20]提出了并行计算模型具备可重配置流水线总线的线性阵列模型(Linear Arrays with a Reconfigurable Pipelined Bus System,LARPBS),并且在该模型上实现了平衡树与双对数深度树查找的并行算法[21].由于实验条件所限,无法实现真正搭建并行机和LARPBS.鉴于此种情况,本文采用多核并行计算进行仿真模拟实验.深度学习[22]中神经网络利用Tensor flow学习库来构建计算图,通过GPU进行计算图中部分节点并行计算,从而实现并行加速效果.因此本文也使用基于TensorFlow的GPU[23,24]处理框架来进行仿真模拟实验.

3.1 实验原理

利用TensorFlow构建各个并行查找算法的计算图,如图3-图6(为了显示方便,图中只显示一定数据量下的计算图),将计算图中的每个节点视为并行机中的一个处理器,计算图中每个节点的连线(数据传递)代表处理器之间的通信.通过TensorFlow自带的GPU加速来实现同计算层次中节点的并行计算,以此来仿真并行机运行查找算法的过程.实验测试数据共分为5组,每组数据通过随机数生成,每组数据个数依次为512,1024,2048,4096,8192.(为了简化程序将数据量都设置为2n).每组数据测试1000次取运行时间的平均值,作为最后实验分析数据.

图3 数据量为8的平衡二叉树方法tensorflow计算图

3.2 实验环境

操作系统:Windows7

编程语言:Python3.6

机器学习库:Tensorflow-GPU 1.12.0

处理器:CPU i7-4790 3.6 GHz

加速器:GPU GTX1070

编辑器:Pycharm Community Edition 2017.1.2

图4 数据量为16的双对数深度树tensorflow计算图

图5 数据量为4的快速查找算法计算图

图6 数据量为16的数据划分方法计算图

3.3 实验结果与分析

从数据划分方法运行时间(见表2,图7)来看,数据划分方法随着测试数据量的增加其实际运行时间的增长符合理论时间复杂度的增长规律,说明仿真模拟实验从运行时间结果上来看是满足实验需要的,实验数据具有一定的可参考性.表2中有一个现象,快速查找算法理论时间复杂度是 O (1),但是实际运行时间却跟双对数深度树方法几乎一样,甚者运行时间表现的更糟糕.这是由于快速查找算法的理想模型机是MIMD (Multiple Instruction stream Multiple Data stream),tensorflow搭建的计算图并不能模拟MIMD所具有的性质,因此运行时间表现糟糕.而改进算法的实际运行时间与平衡树算法运行时间几乎一致,较其他算法略慢,但是达到了改进算法最初对其运行时间的要求.

从运行所需的处理器数量来看(见表3,图8),随着数据量的增长,快速查找方法所需要的处理器数量爆炸增长,因而在当前坐标轴下已经无法看到快速查找方法的曲线,而数据划分方法所需要的处理器数量远低于平衡树查找法和双对数深度树查找法,并且随着数据量的增多,数据划分方法对处理器数量的需求相较其他查找算法优势越大.达到了数据划分方法最初对其所需处理器数量的要求.

表2 实验结果时间对比表

从运行成本来看(见表4,图9),由于快速查找方法并行成本过高,因而在当前坐标轴下已经无法看到快速查找方法的曲线.数据划分方法的综合成本相比于其他最大值查找的并行算法是更优的,说明数据划分方法是有效的,达到了研究目的.

图7 算法运行时间对比图

表3 模拟处理器数量对比表

图8 算法使用处理器数目对比图

4 结论与展望

通过对比实验,数据划分方法的并行成本(Cost)相较平衡树方法,双对数深度树方法,快速查找法是更优的,说明数据划分方法到达了最初的研究目的.数据划分方法使用更少处理器,有效降低了所需处理器数量,保证了问题处理时间达到并行处理的目的,使其执行时间与平衡树方法一致的改进算法,略低于双对数深度树方法.最终减少并行算法的成本,节约了资源.

表4 运行成本对比表

图9 算法成本对比图

随着并行技术越来越多的应用到学术研究,生产生活等方面,人们对于算法运行产生的并行成本的要求会更高.希望可以保证处理速度的同时,降低并行算法的成本.本文最大值查找算法的改进,就是在此背景下进行的.并行算法众多,文章通过比较具有代表性的最大值查找算法进行改进.为此后类似并行算法降低并行成本提供一个方向.随着更多学者和专家的投入,相信会有更多具有高额成本的并行算法在快速解决问题的同时,有效减低并行技术产生巨额的成本.