动态调度基本思想：

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

PPE工作基本流程见图2：

图2 PPE工作流程图

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

SPE工作方案见图3

图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算法的具体描述如下：

对于两个序列和，和，其中，都属于某个字符集，对中的任何元素和空符号，他们两两之间都有一个记分值，用记分函数表示，表示序列的前缀和序列的前缀之间的最优相似性比较的得分。那么有如下公式：

其中计分函数取值：

和相同，= +2

和不相同，或者是删除行，插入行，= -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)块。

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

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