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

Efficient Reduction Algorithms for Directed Acyclic Graph

作　　者：侯睿[1] 武继刚[2] 

机构地区：[1]天津工业大学计算机科学与软件学院,天津300387 [2]中国科学院计算技术研究所计算机体系结构国家重点实验室,北京100190

出　　处：《计算机科学》2015年第7期78-84,共7页Computer Science

基　　金：国家自然科学基金(61173032);国家自然科学基金天元青年基金(11326211;11326198);计算机体系结构国家重点实验室开放课题(CARCH201303)资助

摘　　要：将一个应用程序部署到给定的片上网络上执行时,需要将应用程序中的每一个子任务都指派给片上网络中的一个节点执行。该问题一般被建模成一组子任务作为顶点的有向无环图,任务在片上网络上的部署过程就等同于一个有向无环图的顶点向一个片上网络拓扑映射的过程。而随着应用程序和片上网络规模的增大,计算一个最优的映射方案是典型的难解问题。为了加速有向无环图到片上网络拓扑的映射过程,提出了有向无环图的归约算法,使归约后的图中的顶点数量尽可能地与给定片上网络中的节点数量相同。提出的图归约算法可以有效地识别出所有可归约子图,这些可归约子图可被归约为单一顶点。新算法的适用范围从嵌套图扩展到了任意图,并且拥有与原算法相同的复杂度量级。还提出了一种并行化的算法思想来加速可归约子图的搜索过程。When deploying an application to a given network-on-chip（NoC）to execute,each task of the application should be assigned to a tile in the NoC seperately first.The application is generally modeled as a directed acyclic graph（DAG）in which tasks are repersented as vertices,and the deployment process is equivalent to mapping a DAG to the topology of a NoC.With the increasing scale of applications and NoCs,finding out an optimal mapping scheme is a typical intractable problem.To accelerate the process of mapping DAGs to a given NoC system,this paper proposed an efficient reduction algorithm for DAG,so that the number of vertices in the DAG after reduction is close to the number of tiles in the NoC system.The proposed algorithm can effectively identify all reducible subgraph,which can be reduced to a single vertex.The new algorithm extends the applicable scope from nested graphs to arbitrary DAGs,with the same level of computational complexity compared to the original algorithm.This paper also presented a parallelized algorithm which can shorten the process of seraching reducible subgraph.

关 键 词：片上网络 有向无环图 图归约 可归约子图 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]