Title: A dynamic synchronization mechanism and its implementation on Cell Broadband Engine.

题目：一种并行动态调度方法及其在Cell/BE上的实现

Background: Nowadays, multicore on a chip is a common trend for microprocessor architecture. The successful example is a Cell Broadband Engine which is designed as a main engine for the game machine. As for the calculation of computer graphics on the multicore processors, the whole tasks can be divided and allocated statically to each core and the synchronization of each task is done statically, since the execution time are estimated beforehand. The cost performance of the multicore like Cell Broadband Engine is very high; so many researchers are working on how to apply multicore processors to more general application fields. In general, if a big task is divided into many subtasks, the execution time of each subtask cannot be estimated beforehand, so the dynamic task allocation and dynamic synchronization are needed for the efficient execution of parallel tasks. The data-driven principle and scheme is very simple and formal method for this dynamic synchronization mechanism. So, this research aims to find and evaluate the effectiveness of dynamic synchronization mechanism on the Cell Broadband Engine.

背景：现在，单芯片多核处理器已经成为了一种多核结构的趋势。一个成功的案例就是IBM公司的Cell/BE处理器，它是为游戏专用的引擎。因为在多核处理中，计算机图形的计算可以被划分为工作块，并且执行时间可以预知，所以可以静态地分配到不同的计算核中，进行并行计算和同步。因此，人们希望将这种Cell/BE多核处理器的强大的计算功能应用到其他的通用计算领域。但是一般情况下，如果一个任务被分成不同的子任务块，他们各自执行的时间和结果是不能够被预知的，所以需要一种动态的任务调度和同步方案，来解决这个问题。我们的研究目标是为Cell/BE找到一种有效的动态调度和同步方案，并且对他进行评价。

Basic: Cell/BE has 1 ppe which controls 8 spes. Work steps as follows:

动态调度基本思想：

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

PPE工作基本流程见图2：

图2 PPE工作流程图

When ppe receive the init data, calculate the dependency of each task, and divided the whole task into task blocks; create task list and result list. The task list contains task reliance.

Dynamic choose task which can be execute and allocate into a free spe. After the spe finish and send back the result. ppe update task list and save result into list. More detail later.

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

SPE工作方案见图3

图3 SPE工作方案图

Spe receive data block pointer from ppe, make clear the task type and dma data block from LS or main memory. Run algorithm to calculate and tell the neighbor spe when it finish. Send back result and choose to continue the neighbor task or start over a new task.

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

Why we dynamic:

我们动态调度的目的：

1. Make every spe work efficient, avoid some spe busy but some other free.让每个SPE都能充分被利用，防止一些SPE很忙，而一些SPE空闲的情况。

2. Each task block execute time and dependency is different, ppe choose itself without static setting.因为每个工作的完成时间都不一样，依赖关系也不一样，我们让PPE根据工作进展情况自动选择下一个要执行的任务，自动分配到空闲的SPE或SPE队列。

3. Considerate the localization and task dependency, we let the spe continue its neighbor task with same dependency to reduce the dma cost. 考虑到工作之间的连续相关依赖性，让同一个SPE，尽量处理更多的与自己刚才完成的任务相关的任务。减少DMA数据的传输开销。

4. Optimistic ppe scheduling, reduce the waiting time of ppe; make it use more time on scheduling and updating list.优化PPE调度，减少PPE空闲循环等待的时间，让更多的时间用在工作依赖关系的检测和任务的分配上。

More details

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

Preparation:

准备工作：

1. Implementation of the Smith Waterman algorithm. Set up different length of sequence and generate the similar matrix. It will be used by spe. 在单核上实现了Smith Waterman算法，即可以通过设置不同的序列长度，来生成相应的矩阵。并且通过相似性矩阵，回溯得到序列的相似性关系。为后面SPE的工作所利用。我们记这两个函数为

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

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

2. Thread pool and queue function. It will be used by ppe. Create multi thread and waiting in queue.实现了线程池以及队列功能。为PPE利用，可以创建多个线程，并且根据工作情况将工作加入队列等待或者直接启动，等待队列唤醒等功能。Threadpool

3. Z routing with arrays for ppe check the task status. 二维数组的对角遍历，为PPE检测工作完成度使用。从数组左上元素，按对角线方式遍历，并且可以设置遍历的初始位置开始遍历。举例：10*10数组，从（1，1）开始遍历，下一个元素为（0，2）。

4. Public data structs definition公用数据结构定义：

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

（2）PPE中定义每个SPE执行的基本信息：SPEid，SPEcontext，线程信息，传递参数，参数大小。Spu_data_information

In single spe

单个SPE实现：

（1） Get task number and calculate the start x and y.经过PPE的调度，获取当前工作序号，计算相似性矩阵开始元素；

（2） Get sequence A and B with the start x and y. 根据开始序号，从文件中获得序列A和序列B的对应区间。

（3） Get the init data with the start data pointer, dma from main memory or get directly from its own register. 根据相似性矩阵的首地址及当前开始序号，工作方式，通过DMA方式取得该矩阵区块的上，左，左上数据块，如果是有连续工作的形式，直接从SPE结果缓存中获得数据，初始化矩阵。

（4） Calculate similar matrix with Smith Waterman algorithm. 调用Smith Waterman函数，填充改相似性矩阵区块。

（5） Choose the next task type, continue it or wait another ppe call. Dma result back to main memory. 选择下次工作方式，将数据信息及相似性矩阵区块DMA方式传回主存。

Ppe scheduling:

PPE调度实现：

（1） Some init work: spe information creation, similar matrix creation, queue and thread pool creation. Set up data block and task list, result list. 一些初始化工作，SPE信息的创建，相似性矩阵置零，队列的创建，线程池的创建，根据设置的区块大小，初始化工作列表和结果列表。

（2） Check task list status: end status or arose thread pool thread or continue as 3. 检测工作列表是否全部完成，跳转到结束状态（8）；若未完成，则检测线程池是否有未完成的工作任务，唤醒之；若无，则进行步骤（3）

（3） Check task dependency and allocate a runable task. Or wait for a unit task working time. 调用对角遍历函数遍历工作列表，检测当前工作依赖关系，如果有满足运行条件的，进行接下来的步骤。如果没有满足条件的，等待一个工作单位时间，继续从上次位置遍历。

（4） Set up task num, prepare the spe data, create a spe thread into thread pool. 设置当前工作序号，组装传递给SPE的信息数据包，创建一个SPE线程，并且将他设置为完成自动销毁。

（5） Create spe_information_package in the spe thread. 在SPE线程中设置相似性矩阵首地址，组装参数数据包，准备交付实际的SPE完成工作。

（6） Check free spe in thread pool, choose spe id to allocate or queue it into waiting line. 通过查询空闲SPE队列，为该工作选择SPEid，并启动真实SPE任务，如果当前没有空闲SPE队列，则将该工作加入等待队列。

（7） At the end of the spe thread, add spe to free spe queue and update thread pool and task list, result list. 一次SPE完成后，收集SPE传回的下次工作方式，将该SPE入队空闲SPE队列，更新工作列表和结果列表。跳转到步骤（2）。

（8） After the whole task finish, delete task list, result list, destroy thread pool and spe information. Exit. 工作全部完成，清空工作列表和结果列表，销毁线程和线程池，销毁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之间并行执行，从而加快这个矩阵生成的速度。这样我们就可以在这种区块的划分下，进行区块的动态调度执行问题。

Other:

1. Which one is the topic? Dynamic synchronization or Cell?

2. Multitask, unknown task num and size. Can deal.

3. Easy to implement, just divided block and allocate. Just like describe as the above.