一种基于开销计算的可重构体系结构的映射决策方法

摘要

本发明公开了一种基于开销计算的可重构体系结构的映射决策方法，首先根据表示应用算法核心循环的数据依赖图DDG以及可重构体系结构，建立4个开销模型，分别为延时开销、互连开销、PE占用率开销和相近度开销；然后对某一操作节点存在的多个可行映射方案，计算各可行映射方案在4个开销模型中对应的开销值；接着按照4个开销模型对映射结果的影响程度由主到次依次遍历各可行的映射方案，逐渐缩小可行映射方案集，最终得出最佳映射方案。这种决策方法保证了对映射影响越大的因素在映射决策中越占主导地位。使用本发明的开销模型和映射决策方法，能够得到执行效率较高的配置信息，从而充分发挥可重构系统的并行性。

主权项

一种基于开销计算的可重构体系结构的映射决策方法，其特征在于：首先建立表示应用程序核心循环的数据依赖图DDG，得到当前待映射操作节点u、当前待映射操作节点u的直接前驱结点Pred(u)、当前待映射操作节点u的直接后续节点Succ(u)，以及在可重构体系结构中软件流水的启动间隔II，然后顺序执行以下步骤：(1)、建立以下4个开销模型，分别为：延时开销：表示操作数传输到候选可重构处理单元PE的输入端口的延时；互连开销：表示用于传递数据到候选可重构处理单元PE的互连资源数目；PE占用率开销：用以衡量可重构阵列中各个可重构处理单元PE的使用程度；相近度开销：衡量当前待映射的操作节点与已经映射到可重构处理单元PE上、且没有直接的数据依赖却有相同的直接后继操作节点的操作节点之间的相近程度；(2)、对某一操作节点存在的多个可行映射方案，计算各可行映射方案在4个开销模型中对应的开销值；所述延时开销的计算公式为：$Delay\cos t\left({\mathrm{PE}}_u\right)={\mathrm{MAX}}_{v_{s^{\prime }}\in V_{s^{\prime }}}\left\{\begin{array}{c}{C}_w({\mathrm{PE}}_{v_{s^{\prime }}},{\mathrm{PE}}_u)+\\ C_r({\mathrm{PE}}_{v_{s^{\prime }}},{\mathrm{PE}}_u)+\\ C_d({\mathrm{PE}}_{v_{s^{\prime }}},{\mathrm{PE}}_u)\end{array}\right\}$其中，可重构处理单元PE_u表示当前待映射操作节点u的可映射候选处理单元；V_S'表示当前待映射的操作节点u的直接前驱操作节点中已经映射到可重构阵列上的所有操作节点的集合；表示映射当前待映射操作节点u所需的操作数从其已被映射的直接前驱节点v_s'所对应的可重构处理单元到当前候选可重构处理单元PE_u的数据传输路径中，由互连线引入的延时；和分别表示映射当前待映射操作节点u所需的操作数从可重构处理单元到当前候选可重构处理单元PE_u的数据传输路径中由路由PE和分布式寄存器DRF引入的延时；所述互连开销的计算公式为：其中，V_s表示已经映射到可重构阵列上的所有操作节点的集合；V_s”表示当前待映射操作节点u的直接前驱操作节点和直接后继操作节点中，已经映射到可重构阵列上的操作节点的集合；Pred(u)表示当前待映射操作节点u的所有直接前驱操作节点的集合；Succ(u)表示当前待映射操作节点u的所有直接后继操作节点的集合；表示可重构处理单元PE_u和间需要插入的最少路由PE数；所述PE占用率开销的计算公式为：$U\cos t\left({\mathrm{PE}}_u\right)=\frac{PEOccupationCycles\left({\mathrm{PE}}_u\right)}{II}$其中，PEOccupationCycles(PE_u)表示当前可重构处理单元PE执行映射到其上的操作集合的总时间；II为可重构体系结构软件流水的启动间隔；所述相近度开销的计算公式为：$\mathrm{Re}l\cos t\left({\mathrm{PE}}_u\right)=\underset{v\in V_{\min }}{\Sigma }|Vexdist(u,v)-PEdist({\mathrm{PE}}_u-{\mathrm{PE}}_v)|$其中，V_min表示已经映射的操作节点v中与当前待映射操作节点u距离最短的所有操作节点的集合；Vexdist(u,v)表示V_min中已经映射的操作节点v与当前待映射操作节点u的距离；PEdist(PE_u‑PE_v)表示V_min中已经映射的操作节点v所映射的可重构处理单元PE_v与当前待映射操作节点u的候选可重构处理单元PE_u之间的距离；(3)、对当前待映射操作节点u的多个可行映射方案，按照延时开销、互连开销、PE占用率开销和相近度开销的顺序依次遍历各可行的映射方案，逐渐缩小可行映射方案集，最终得出最佳映射方案。