14,15th meeting

动态调度基本思想:

一般的并行处理机,都有一个控制单元和若干个执行单元,以我们要做的Cell/BE为例,由一个控制PPE和8个数据处理SPE组成,我们设计的他们之间的工作关系。

PPE工作基本流程见图2:

clip_image001

图2 PPE工作流程图

当PPE接收初始数据之后,通过工作之间的相互关系,和设定的工作块的大小,划分为n个工作块,并且将工作块之间的依赖关系存入Work List,之后启动动态调度模式,将工作数据块分配给空闲的SPE。SPE计算完之后,PPE将SPE传回的结果存入Result List后备使用,并且更新Work List信息,如工作的完成度,依赖关系等。详细过程后面继续讨论。

SPE工作方案见图3

clip_image002

图3 SPE工作方案图

SPE接收PPE传来的数据块之后,判断工作方式,选择从主存传回需要的初始数据并利用Result List中缓存的结果,共同进行运算和处理,完毕之后将结果缓存到自己的Result List中并更新,通知相邻节点依赖关系的更新。同时将结果使用DMA方式传回PPE主存中,完成一次工作。

我们动态调度的目的:

1. 让每个SPE都能充分被利用,防止一些SPE很忙,而一些SPE空闲的情况。

2. 因为每个工作的完成时间都不一样,依赖关系也不一样,我们让PPE根据工作进展情况自动选择下一个要执行的任务,自动分配到空闲的SPE或SPE队列。

3. 考虑到工作之间的连续相关依赖性,让同一个SPE,尽量处理更多的与自己刚才完成的任务相关的任务。减少DMA数据的传输开销。

4. 优化PPE调度,减少PPE空闲循环等待的时间,让更多的时间用在工作依赖关系的检测和任务的分配上。

下面结合Cell/BE详细说明动态调度的工作结构和过程:

准备工作:

1.在单核上实现了SmithWaterman算法,即可以通过设置不同的序列长度,来生成相应的矩阵。并且通过相似性矩阵,回溯得到序列的相似性关系。为后面SPE的工作所利用。我们记这两个函数为

int smithWaterman(int score[m][n], char sequenceA[], char sequenceB[])

int getSimilar(int score[m][n],char sequenceA[], char sequenceB[])

2.实现了线程池以及队列功能。为PPE利用,可以创建多个线程,并且根据工作情况将工作加入队列等待或者直接启动,等待队列唤醒等功能。Threadpool

3.二维数组的对角遍历,为PPE检测工作完成度使用。从数组左上元素,按对角线方式遍历,并且可以设置遍历的初始位置开始遍历。举例:10*10数组,从(1,1)开始遍历,下一个元素为(0,2)。

4.公用数据结构定义:

(1)SPE,PPE之间数据传递结构包括相似性矩阵首地址,工作序号,工作方式,SPEid。

(2)PPE中定义每个SPE执行的基本信息:SPEid,SPEcontext,线程信息,传递参数,参数大小。

单个SPE实现:

(1) 经过PPE的调度,获取当前工作序号,计算相似性矩阵开始元素;

(2) 根据开始序号,从文件中获得序列A和序列B的对应区间。

(3) 根据相似性矩阵的首地址及当前开始序号,工作方式,通过DMA方式取得该矩阵区块的上,左,左上数据块,如果是有连续工作的形式,直接从SPE结果缓存中获得数据,初始化矩阵。

(4) 调用SmithWaterman函数,填充改相似性矩阵区块。

(5) 选择下次工作方式,将数据信息及相似性矩阵区块DMA方式传回主存。

PPE调度实现:

(1) 一些初始化工作,SPE信息的创建,相似性矩阵置零,队列的创建,线程池的创建,根据设置的区块大小,初始化工作列表和结果列表。

(2) 检测工作列表是否全部完成,跳转到结束状态(8);若未完成,则检测线程池是否有未完成的工作任务,唤醒之;若无,则进行步骤(3)

(3) 调用对角遍历函数遍历工作列表,检测当前工作依赖关系,如果有满足运行条件的,进行接下来的步骤。如果没有满足条件的,等待一个工作单位时间,继续从上次位置遍历。

(4) 设置当前工作序号,组装传递给SPE的信息数据包,创建一个SPE线程,并且将他设置为完成自动销毁。

(5) 在SPE线程中设置相似性矩阵首地址,组装参数数据包,准备交付实际的SPE完成工作。

(6) 通过查询空闲SPE队列,为该工作选择SPEid,并启动真实SPE任务,如果当前没有空闲SPE队列,则将该工作加入等待队列。

(7) 一次SPE完成后,收集SPE传回的下次工作方式,将该SPE入队空闲SPE队列,更新工作列表和结果列表。跳转到步骤(2)。

(8) 工作全部完成,清空工作列表和结果列表,销毁线程和线程池,销毁SPE信息,退出。

Smith Waterman算法简介

Smith Waterman算法的具体描述如下:

对于两个序列clip_image003clip_image004clip_image005clip_image006,其中clip_image007,都属于某个字符集clip_image008,对clip_image008[1]中的任何元素和空符号,他们两两之间都有一个记分值,用记分函数clip_image009表示,clip_image010表示序列clip_image003[1]的前缀clip_image011和序列clip_image004[1]的前缀clip_image012之间的最优相似性比较的得分。那么有如下公式:

clip_image013

其中计分函数clip_image009[1]取值:

clip_image005[1]clip_image006[1]相同,clip_image009[2]= +2

clip_image005[2]clip_image006[2]不相同,或者是删除行,插入行,clip_image009[3]= -1

由此可以得到一个相似性矩阵。通过相似性的可计算性分析,在某个特定的时候,矩阵中出现多个可以同时计算的元素,实际上就是在计算得分矩阵的过程中包含着可并行性。Smith Waterman算法就可以利用这种并行性进行并行优化。

SmithWaterman算法的并行实现:

经过分析,该算法的主要花费时间在相似性矩阵的生成上,所以我们根据矩阵的特性,将整个要生成的矩阵划分成若干区块,我们假设:

序列A长度为a,序列B长度为b,那么矩阵总大小为a*b;结合实际情况,有95%的基因序列长度在5KB左右,所以a和b的长度在5120左右数量级;同时结合我们要做的并行处理的数据传输情况和处理单元LS大小,我们可以将区块大小划分为8 ~ 128, 我们设区块大小为m*n,其中mn都属于8~128。那么有整个矩阵被分成(a/m)*(b/n)块。

clip_image015

因为矩阵中的每一个元素的计算,都只跟左,上及左上元素有关,那么可以得到同理,不同的区块之间,也只跟左,上及左上区块有关,在区块进行完初始化之后,区块内部可以并行执行,如下图:

clip_image017

那么我们可以使t2,t3之间并行执行,从而加快这个矩阵生成的速度。这样我们就可以在这种区块的划分下,进行区块的动态调度执行问题。

发表评论

电子邮件地址不会被公开。 必填项已用*标注