有向无环图的高效归约算法
将一个应用程序部署到给定的片上网络上执行时,需要将应用程序中的每一个子任务都指派给片上网络中的一个节点执行.该问题一般被建模成由一组子任务作为顶点的有向无环图,任务在片上网络上的部署过程就等同于一个有向无环图的顶点向一个片上网络拓扑的映射过程.而随着应用程序和片上网络规模的增大,计算一个最优的映射方案是典型的难解问题.为了加速有向无环图到片上网络拓扑的映射过程,文中提出了有向无环图的归约算法,使归约后的图中的顶点数量尽可能的与给定片上网络中的节点数量相同.文中提出的图归约算法可以有效地识别出所有可归约子图,这些可归约子图可被归约为单一顶点.新算法的适用范围从嵌套图扩展到了任意图,并且拥有与原算法相同的复杂度量级.本文也提出了一个并行化的算法思想加速了可归约子图的搜索过程.
片上网络 有向无环图 归约算法 可归约子图
侯睿 武继刚
天津工业大学计算机科学与软件学院 天津 300387 计算机体系结构国家重点实验室,中国科学院计算技术研究所 北京 100190
国内会议
济南
中文
1-6
2014-10-16（万方平台首次上网日期，不代表论文的发表时间）