定义2 一个DFG的划分问题可以描述如下。 输入 G=(V,E,W)；ARPU。 输出 G的一个划分P={P1,P2,,PM}。 约束条件 1)Mi=1Pi=；2)Mi=1Pi=V；3)PiP，1iM，wjARPU，wj为
定义2 一个DFG的划分问题可以描述如下。
输入 G=(V,E,W)；ARPU。
输出 G的一个划分P={P1,P2,…,PM}。
约束条件 1)∩Mi=1Pi=；2)∪Mi=1Pi=V；3)Pi∈P，1≤i≤M，∑wj≤ARPU，wj为Pi中所有包含的第j个节点的权值；4)P中所有的前驱和后继划分块之间不存在非法依赖关系；5)RPU支持流水线处理。在计算资源成功映射的前提下，划分内所有的边都能在硬件中实现连接。
目标 1)划分块数较少； 2)块间边数较少。
定义3 设V是一个计算任务或程序的DFG的有序运算符中的任一个运算节点，则V被划入一个划分块的前提是V的所有的前驱节点均已经被分配到相应的划分块中。一个合理的划分要求划分块之间不产生非法依赖关系。由于DFG是一个有向无环图，如果一个节点的前驱节点被分配到其后继模块中，就会引发非法依赖关系现象。图1给出了这种情况的图示，为了简化问题描述，假设一个任务或程序的DFG中各个节点的权值相同，这样，本文可以将面积的单位等价于节点的个数。设ARPU=4，获得P1和P2两个划分，如果划分块的执行次序是从P1→P2,因P1划分中运算节点V6前驱V3位于P2划分，反之亦然，所以划分块P1和P2之间产生了非法依赖关系，如图1所示。
3 深度优先贪婪搜索划分
3.1 深度优先贪婪搜索划分算法设计
为了保证某个DFG在划分时能获得较小划分块间边数，同时充分利用可重构计算阵列的资源，深度优先贪婪搜索划分(Depth First Greedy Search Partitioning, DFGSP)算法在满足可重构资源面积约束的条件下，按深度遍历的方式，同时考虑了存储边数和硬件资源两个因素，而且DFGSP算法在初始化过程中，将原始输入作为文件直接读取。综上，DFGSP算法采用以下两个策略来进行算法设计。
策略1 追求块间通信成本的较小化。
DFGSP算法按深度优先搜索的思想进行划分，一遇到不满足要求的点时跳过，继续搜索该点之后处于就绪状态的节点，当搜索到满足要求的点时，加入当前块设置限制条件如下：首先计算当前块的块间边数，在保证当前块的块间边数不变的情况下，尽可能地把满足要求的节点放入当前的划分块，如果新的运算节点加入后的块间边数小于等于当前块边数则加入；否则不加入。这样做的主要目的是使更多的紧密型运算节点放在一起，从而获得整个DFG划分块间的通信成本的较小化。
策略2 在保证当前划分块通信成本的较小化的情况下，使可重构运算阵列面积利用最大化。
按深度优先搜索的思想进行划分，算法在划分完当前就绪节点后面积仍有剩余时就停止，但是该剩余面积还有可能满足剩下的队首节点后面节点的面积要求，因此在保证当前划分块执行通信成本的最小化的情况下，可以在队首节点之后按同时满足加入某节点后不增加当前划分块间的边数和尽可能填满可重构运算阵列的原则进行贪婪搜索满足要求的就绪运算节点，从而提高系统资源的利用率。
定理1 DFGSP是一种综合考虑可重构硬件资源和划分块间边数深度优先贪婪搜索算法。
证明 本证明分为两个部分：第1)部分证明DFGSP是一个综合考虑任务硬件资源和划分块间边数的贪婪搜索算法；第2)部分证明DFGSP算法是一个深度优先搜索算法。
1)令S(n)是谓词“给定一个DFG，并且该图顶点集合V满足|V|=n≥1，则DFGSP是一种综合考虑可重构硬件资源和划分块间边数的贪婪搜索算法”。
用数学归纳法证明，基本步骤如下。
步骤1 当n=1，即V只有一个元素，块间边集E={}，块间边数计数变量为j，初值为0，即有V={v1}，则有P={P1}，P1={v1}， j=0，S(1)为真。
步骤2 当n=2，设ARPU=1(ARPU为一个约定的划分面积)，基于DFGSP算法进行任务划分存在两种情况：一种情况是任务节点v1和v2存在依赖关系，若v1为v2的直接前驱，v2为v1的直接后继，则这两个具有固定次序的客体可组成一个序偶表示为〈v1,v2〉,假设划分的执行顺序为P1→P2则P={P1,P2}，P1={v1}，P2={v2}，块间边数j=1；另一种情况是任务节点v1和v2不存在依赖关系，且两个节点同时就绪，DFGSPDFGS按先来先服务(First In First Out, FIFO)的原则优先选择就绪队列的首节点进行分配，若队列的排列顺序为{v2,v1},则P={P1,P2}，P1={v2}，P2={v1}，块间边数j=0；则S(2)为真。归纳步骤如下。
假设当n=k-1时命题成立，S(k-1)为真。
当n=k时，在ARPU约束下，不妨设采用DFGSP分割具有n个顶点DFG可以获得一个具有M个划分块的划分，可表示为P={P1,P2,…,Pi-1,Pi,…,PM}，前k-1个节点(即v1，v2，…vk-1)已经按DFGSPDFGS算法划分完毕，当前划分的块间边数j=δ，因为每个划分块包含的节点数有可能多于一个，所以设获得的相应划分块为P={P1,P2,…,Pi-1}，现考查从余下顶点序列V={vk,vk+1,…,vn}选取第k个节点vα的处理过程，DFGSP算法搜索当前就绪列表中所有满足要求节点(即indegree(vi)=0，k≤i≤n的点)，当前就绪列表队首的节点的面积不满足要求，但是当前队首后面的运算任务节点面积满足要求。具体可以分为以下两种情况。
①若队首后面的运算任务面积满足要求的节点与当前划分块内的节点无联系时，算法就依据FIFO的调度策略分配相应的任务，若当前划分|Pi-1| ②若队首后面的运算任务面积满足要求的节点存在两种类型：a)与当前划分块内的节点无联系；b)与当前划分块内的节点有联系。则优先划入第b)种类型的运算节点，若当前划分|Pi-1|
由①、②可知，S(k)为真，即对k个元素而言，DFGSP是一个综合考虑可重构硬件资源和划分块间边数的算法。综上，S(n)为真，即给定一个具有n个节点的DFG，DFGSP是一个综合考虑可重构硬件资源和划分块间边数的算法。 (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）
顶一下
(0)
0%
踩一下
(0)
0%
版权声明：因本文均来自于网络，如果有版权方面侵犯,请及时联系本站删除.
