有向无环图的高效归约算法

摘要

将一个应用程序部署到给定的片上网络上执行时,需要将应用程序中的每一个子任务都指派给片上网络中的一个节点执行.该问题一般被建模成一组子任务作为顶点的有向无环图,任务在片上网络上的部署过程就等同于一个有向无环图的顶点向一个片上网络拓扑映射的过程.而随着应用程序和片上网络规模的增大,计算一个最优的映射方案是典型的难解问题.为了加速有向无环图到片上网络拓扑的映射过程,提出了有向无环图的归约算法,使归约后的图中的顶点数量尽可能地与给定片上网络中的节点数量相同.提出的图归约算法可以有效地识别出所有可归约子图,这些可归约子图可被归约为单一顶点.新算法的适用范围从嵌套图扩展到了任意图,并且拥有与原算法相同的复杂度量级.还提出了一种并行化的算法思想来加速可归约子图的搜索过程.