[发明专利]基于数据流分析的单线程程序并行化的实现方法

摘要

本发明公开了一种基于数据流分析的单线程程序并行化的实现方法。本发明通过分析单线程程序中指令之间的数据依赖性，把单线程程序分解成多线程程序，单线程程序指令之间的依赖性有数据依赖和控制依赖两种，控制依赖是对控制条件值的依赖，是一种特殊的数据依赖。本发明在线程分解的过程中，同时考虑分解后线程通信代价和线程之间的平衡性。本发明的优势在于能够使单线程程序的不同部分并行执行，进而减短程序执行时间提高程序执行效率。单线程程序的并行化方法尤其适合当今的多核结构。

主权项

1.一种基于数据流分析的单线程程序并行化的实现方法，其特征在于：1)分解算法的实现：分解算法是把单线程程序分解成多个线程的算法实现，这个算法根据联合依赖关系图当中的指令依赖性，把单个线程分解成两个或多个线程，分解算法是一个递归的过程，它首先作出非嵌套循环或者无循环部分的联合依赖关系图，根据原程序中指令执行的时间以及数据依赖关系，向图中的节点和边的添加属性，之后是图的分解过程，分解算法考虑的是分解后线程的通信代价和线程之间的平衡性，把图中的节点分配到不同的组中，组成不同的线程，然后向线程中插入生产者消费者指令，分解后，被分解的部分被当作一个节点插入原来代码当中，分解算法继续分解新组成的代码中的非嵌套循环部分，如此递归进行，直到分解完整个需要分解的代码；2)根据指令依赖关系作出联合依赖关系图：单线程程序指令之间存在两种依赖关系，分别是指令之间的数据依赖和控制依赖。当单线程程序别分解成多个线程而并行执行的时候，还存在反向的数据依赖关系。联合依赖关系图是混合这三种依赖关系的图，它的作法是这样的：首先以程序中的指令作为图的节点，然后根据指令之间的依赖关系添加上述的三种依赖关系。在添加完依赖关系以后，以图中不存在依赖的节点为起始节点，消除与这些节点连接的所有边，查找图中新的不存在依赖的节点，取出这些节点加入到起始节点的集合中，在起始节点的集合中添加新节点与旧节点在程序执行中的先后关系，消除新节点在原来依赖图中所有与之相连的边。这样循环进行直到所有节点被添加到起始节点集合为止；3)函数、过程内联和程序中三种基本元素的分解：函数和过程会使指令流跳出到被分解部分的代码，这使得分解过程难以继续进行，因此需要把被分解代码部分内的函数和过程被内联进来。基本块、条件分支和循环是程序的三种基本元素，循环被分解算法作为基本分解单元，分支和循环需要控制条件值的传递，基本块可以被直接分解，但会存在数据依赖和反向数据依赖；4)生产者消费者通信模式及硬件实现：分解后线程之间的通信通过生产者消费者方式解决，生产者消费者需要在仓库中存储和消费所通信的值，如果以内存为仓库，由于内存的速度慢，对内存的读写影响分解后线程的性能，为了能够更快的完成生产者消费者，减少通信代价，一种硬件的实现可以有效的改进效率；5)分解后线程间通信的一个特殊例子考虑：对于生产者消费者的实现，有一个特殊的例子需要被考虑，当消费者消费的值有可能来自分支或循环内部，也有可能来之分支或循环前面时生产者需要在一个特定的点生产或者向仓库中的同一个单元进行生产，不然消费者得到的值可能是错误的或者过时的。