2)DFGSP算法每次搜索满足划分要求和充分考虑硬件资源的硬件利用碎片的节点时，搜索的节点的次序从一个节点出发，依次逐个划入该节点的满足要求的直接后继节点，这和深度优先搜索特性吻合，故DFGSP算法又是一种深度
2)DFGSP算法每次搜索满足划分要求和充分考虑硬件资源的硬件利用碎片的节点时，搜索的节点的次序从一个节点出发，依次逐个划入该节点的满足要求的直接后继节点，这和深度优先搜索特性吻合，故DFGSP算法又是一种深度优先搜索算法。
由1)、2)可知，DFGSP是一种综合考虑可重构硬件资源和划分块间边数的深度优先贪婪搜索算法。证毕。
基于上述两个策略的算法描述如下：
算法1 DFGSP。(Depth First Greedy Search Partitioning)
程序前
Input A DFG of a given task;
Ouput optimized edges acrossed modules of all the modules & module-numbers
Initialization & input data table; part=1;
For each node vi∈V do
calculate each node indegree numbers;
if(node［i］.indegree=0)
AddQueue(vi);
End if
End For each
while (n while(pQueue!=NULL) do
ui=QueueFront();
Total_Cost=node［ui］.size+RCost;//把队首元素所占的硬件资源大小加入
if(Area_Filled+Total_Cost<=ARPU)//如果当前节点面积小于等于ARPU
加入当前节点;更新填充面积;
更新就绪列表;
通过函数edges1=Acrossed_ modules_Edges()计算当前划分块的块间边数
End if
if(Area_Filled+Total_Cost>ARPU)
跳过该点，搜索该点之后的所有满足当前面积要求&可以划入的运算节点;
更新就绪列表; 更新填充面积;并将它们依次保留在一个存储数组中
End if
End while
For each node vi∈V do
依次从存储数组中取出满足要求的点
并且通过函数edges2=Acrossed_ modules_Edges()计算加入该点的划分块间边数
if(edges2<=edges1)
加入该点
Else
删除该点
End if
End for each
开辟新块;
Area_Filled=Total_Cost=0;
通过排序函数sortlist()找到当前就绪节点层次号最小的点;
并以该点为起点进行新一轮的划分
End while
分别计算DFG的划分块数和块间边数
输出较优解P和E
End DFGSP
程序后
3.2 算法时间复杂度分析
DFGSP算法在执行前，一个DFG总的节点数、每个运算节点运算类型和占用的资源数已知。每个节点前驱与后继的个数及列表在初始化函数Init()通过任务节点的二维关系矩阵求得，该运算的时间复杂度为O(n2)。求每个节点的入度的时间复杂度为O(n)。DFGSP算法进行贪婪硬件划分的平均时间复杂度为O(n2)。综上，DFGSP算法的时间复杂度为O(n2)。
4 实验及其结果分析
由于LSCBP和CBP两个算法是目前典型的减少通信成本效率较高的算法，本章通过软件仿真将本文的算法与LSCBP和CBP两个算法进行对比。为了便于比较，本文统一用重构硬件资源面积作为约束条件。各类运算的占用资源量见表1，各类运算所占的重构硬件资源数(单位用可配置逻辑模块(Configurable Logic Block, CLB)个数表示)是参照XC4000E系列8位FPGA来确定的。
本文采用C语言实现了DFGSP、CBP、LSCBP算法，并用划分基准程序集对其进行了测试验证。基准程序集包含6个程序，它们是快速数据加密算法(Fast data Encipherment ALgorithm, FEAL)、快速傅里叶变换4次展开 (Fast Fourier Transform 4, FFT4)、快速傅里叶变换8次展开(Fast Fourier Transform 8, FFT8)、快速傅里叶变换16次展开(Fast Fourier Transform 16, FFT16)、逆离散余弦变换(Inverse Discrete Cosine Transformation, IDCT)、离散余弦变换32次展开(Discrete Cosine Transform 32, DCT32)，其操作单元的数量和占用的硬件资源总数如表2所列，其中，“—”表示划分用例没有该种运算。程序的开发环境是Visual Studio.Net 2010，运行环境是Windows XP，PC的处理器为Intel Core i3 CPU,主频为2.26GHz,内存为2GB。CBP、LSCBP算法模块数的计数均包括第0层输入的划分。统计块间输出边时，如一个运算节点有两条及以上输出边，只统计一次。ARPU随机选取60CLB、70CLB和80CLB三个值。其中：P表示划分块数，E表示划分块之间的I/O边数。
4.1 DFGSP算法与CBP算法的比较
DFGSP算法和CBP算法对比实验的数据见表3~5，表中的Δ%表示相对改进百分比。相对于CBP而言，DFGSP所获得的P值是最小的。
4.2 DFGSP算法与LSCBP算法的比较
DFGSP算法与LSCBP算法比较的实验数据见表6~8。LSCBP算法是对CBP算法的改进，旨在优化P和E，但相比于DFGSP而言，P值和E均值均大于DFGSP算法。
从上述实验比较结果可以看出，DFGSP相比于CBP、LSCBP两种算法而言，模块数是最小的，块间均值也是最小的。但是DFGSP的局限性是每个划分后的模块内部运算任务之间的并行度没有达到最大，所以本文算法适用于想获得划分模块数和块间存储成本较小的场合。
5 结语
本文提出了一种DFGSP算法，该算法采用深度优先搜索的思想综合考虑了DFG划分块数和块间的边数最小化等因素，动态调整节点的调度次序。采用通过真实的计算密集型任务转换来的DFG，与CBP、LSCBP两种算法进行了比较，结果表明，DFGSP算法具有较小的划分块数和块间的边数，总体效果良好。
参考文献:
[1] (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）
顶一下
(0)
0%
踩一下
(0)
0%
版权声明：因本文均来自于网络，如果有版权方面侵犯,请及时联系本站删除.
