Abstract: This paper proposed a hardware task partitioning algorithm according to the problems of communication cost minimum in reconfigurable computing, called DFGSP (Depth First Greedy Search Partitioning). At first, the front task was taken from the ready queue, a Directed Acyclic Graph (DAG), which was transformed from a computing-intensive task, was scanned and partitioned by Depth First Search (DFS). Then, the number of outputting-edges (quantized to communication cost) of current partitioning module was computed when the task node did not meet the area constraints. Finally, the ready task node, which considered sufficiently partitioning module outputting-edges which were not increasing and made good use of reconfigurable resources hardware fragment as soon as possible, was scanned and partitioned, after skipping the task node which did not meet the area constraints. In comparison with the Cluster-Based Partitioning (CBP) algorithm and Level Sensitive Cluster-Based Partitioning (LSCBP) algorithm, the experimental results show that the proposed algorithm can obtain the least number of partitioning modules and the least average number of input-output edges crossing modules, and the practical resultson reconfigurable task compiler，作者电话回复要求改过。 indicate the proposed algorithm gets a prominent improvement in hardware task partitioning performance over previous algorithms, while the run-time efficiency is preserved.
Key words: reconfigurable computing; temporal partitioning; depth first greedy search; communication cost; resource restraint; hardware fragment
0 引言
可重构计算结构可以看成是由时间和空间构成的二维结构［1］，其具有时间域上的可编程性和空间域上可配置性。目前，可重构计算技术在音、视频的压缩［2］，嵌入式与可重构计算机系统［3-5］，图像处理［6］等方面得以广泛的应用。可重构计算可以定义为对结构固定的硬件计算平台，根据应用的不同需要对可重构硬件进行动态配置，根据配置信息来改变内部可重构单元的功能和相互之间的连接关系，并在辅助设备(包括外围控制硬件和软件)的协同下完成相应的计算任务［7］。
在可重构计算的任务编译器设计过程中，由关键循环转换来的数据流图(Data Flow Graph, DFG)如何被映射到可重构处理单元(Reconfigurable Processing Unit, RPU)是实现可重构计算机系统高性能的关键所在，其中任务图的划分又是其中的重要一环，划分是映射的前提，划分子图的提取对映射结果好坏产生很大的影响，因此可重构计算的硬件任务划分问题是可重构计算中的难点问题，而且图的时域划分问题已经被证明是一个NP完全问题［8］，故该类问题常常得到的是较优解。
在这样的背景下，本文对可重构相关的划分算法和划分块间的通信成本的较小化等方面进行了深入的研究，提出了一种深度优先贪婪搜索的硬件任务划分算法。实验证明该方法有效减少了划分块的块间边数和划分块数。
1 相关研究
传统的DFG时域划分算法根据电路的抽象层次进行划分，可大致分为两种：网表级时域划分和行为级时域划分［7］。行为级时域划分方法是本文的研究重点，相关算法很多，通信成本是影响可重构计算机系统性能的主要因素之一，主要以通信代价作为优化目标的典型时域划分算法有以下几种，分述如下。
文献［9］用概率构造与遗传算法(Probabilistic Constructive Genetic Algorithm， PCGA）相融合来对相关的硬件任务进行划分，旨在获得较小的任务簇集合和较低的通信代价，效果较好，但是PCGA运行的时间较长。文献［10］提出划分合并簇算法(Partitioning Merging Clusters, PMC),该方法首先对待划分DFG按扇出和扇入两种类型簇分别做初始划分；然后，分析簇之间的关系，在满足硬件资源限制的前提下，按概率将簇进行合并，目标是减少通信量。但是因为存在硬件资源约束问题，所以初始扇出和扇入两种类型簇很难划定，而且即使划定，初始产生的划分簇在很多情况下也不能合并。
簇划分（Cluster-Based Partitioning，CBP）算法是一个典型的列表调度算法［11］，执行时能获得较小的通信代价，划分效果良好。簇的层次敏感划分(Level Sensitive Cluster-Based Partitioning， LSCBP)算法对CBP算法进行了改进［12］，克服了该算法机械选取节点划分的缺陷，提高了硬件资源的利用率，取得了较好的效果。
2 问题定义
为了凸显本文研究的侧重点，下面给出一些前提条件：1)待划分的任务由DFG表示，一个计算密集型任务已经转换为一个DFG；2)一个划分可以直接映射到一块可重构单元阵列(Reconfigurable Cell Array, RCA)，RCA的面积为一个定值，并且可以被重复使用。
针对具体的研究内容，本文对相关概念定义如下。
定义1 一个计算任务或程序的DFG可以表示为一个三元组G=(V,E,W)。其中：顶点集V={vi|vi是有序运算符，1≤i≤n}，|V|=n表示运算符的个数；边集E={eij|eij=〈vi, vj〉，1≤i, j≤n}，eij表示从vi到vj的有向边，vi是vj的直接前驱节点，vj是vi的直接后继节点，表示了vi和vj两个运算符的先后依赖关系，vj的执行依赖于vi，|E|=m为边的数量；权集W={wi|表示vi所占的硬件资源面积，1≤i≤n}。
一般而言，可重构计算系统的可重构处理单元（Reconfigurable Processing Unit， RPU）的面积为一个定值，表示为ARPU。对于任意一个大任务的DFG很难被全部被映射上去，这就需要对该DFG进行分割。不同的分割方法由不同的划分算法实现，对于任一个计算任务或程序的DFG，在满足相关约束条件下，采用某种分割方法可以获得一个具有M个划分块的划分，表示为P={P1,P2,…,PM}，|P|=M，其中，第i个划分块Pi由DFG的若干个节点组成，1≤i≤M。Pi和Pj要求具有严格的执行顺序，若Pi先执行，Pj紧跟Pi后执行，表示为Pi→Pj，则称Pi为Pj前驱模块，Pj为Pi的后继模块。 (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）
- 毕业论文定制
南粤论文中心提供本科/研究生/博士毕业论文，从提纲，开题到后期免费修改,免费指导答辩等 ，联系人：魏老师，电话：13450375436。 - 代写代发职称论文
南粤论文中心提供职称论文代写，报告总结，演讲致辞,心得体会,党团辅导等代写服务并推荐发表省级,国家级,核心杂志包发。联系QQ:631069747。
基于深度优先贪婪搜索的可重构硬件任务划分算法
来源：网络(转载) 作者：陈乃金 发表于：2012-01-26 13:49 点击：次
【关健词】可重构计算；时域划分；深度优先贪婪搜索；通信成本；资源约束；
针对可重构计算硬件任务划分通信成本较小化的问题，提出了一种基于深度优先贪婪搜索划分(DFGSP)算法。首先，从待调度的就绪队列中取出队首任务，在某一硬件面积约束下，按深度优先搜索(DFS)方式扫描一个计算密集型任务转换来的有向无环图(DAG)，逐个划入满足要求的节点
顶一下
(0)
0%
踩一下
(0)
0%
版权声明：因本文均来自于网络，如果有版权方面侵犯,请及时联系本站删除.
