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

doi:10.11896/j.issn.1002-137X.2015.07.017

摘要/Abstract

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

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

Abstract: 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.

Key words: Network-on-chip (NoC),Directed acyclic graph,Graph reduction,Reducible subgraph

侯睿武继刚. 有向无环图的高效归约算法[J]. 计算机科学, 2015, 42(7): 78-84. https://doi.org/10.11896/j.issn.1002-137X.2015.07.017

HOU Rui WU Ji-gang. Efficient Reduction Algorithms for Directed Acyclic Graph[J]. Computer Science, 2015, 42(7): 78-84. https://doi.org/10.11896/j.issn.1002-137X.2015.07.017

参考文献

[1] Pasricha S,Dutt N.On-chip communication architectures:system on chip interconnect[M].Morgan Kaufmann,2010:544
[2] Borkar S.Thousand core chips:a technology perspective[C]∥Proceedings of the 44th annual Design Automation Conference.USA:ACM,2007:746-749
[3] Sylvester D,Keutzer K.A global wiring paradigm for deep submicron design[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2000,19(2):242-252
[4] Dally W J,Towles B.Route packets,not wires:On-chip interconnection networks[C]∥Proceedings of 2001 Design Automation Conference.USA:IEEE,2001:684-689
[5] Flich J,Bertozzi D.Designing network on-chip architectures inthe nanoscale era[M].Chapman & Hall/CRC,2010:528
[6] Lei T,Kumar S.A two-step genetic algorithm for mapping task graphs to a network on chip architecture[C]∥Proceedings of Euromicro Symposium on Digital System Design (DSD 2003).USA:IEEE,2003:180-187
[7] Addo-Quaye C.Thermal-aware mapping and placement for 3-D NoC designs[C]∥Proceedings of 2005 IEEE International SOC Conference.USA:IEEE,2005:25-28
[8] Hu J,Marculescu R.Energy-aware mapping for tile-based NoC architectures under performance constraints[C]∥Proceedings of the 2003 Asia and South Pacific Design Automation Conference.USA:ACM,2003:233-239
[9] Hu J,Marculescu R.Energy-and performance-aware mappingfor regular NoC architectures[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2005,24(4):551-562
[10] Hamedani P K,Hessabi S,Sarbazi-Azad H,et al.Exploration of temperature constraints for thermal aware mapping of 3D Networks on Chip[C]∥Proceedings of the 20th Euromicro International Conference on Parallel,Distributed and Network-Based Processing (PDP).USA:IEEE,2012:499-506
[11] Murali S,De Micheli G.Bandwidth-constrained mapping of cores onto NoC architectures[C]∥Proceedings of the conference on Design,automation and test in Europe-Volume 2.USA:IEEE,2004:20896
[12] Zhao K,Bian J.Instruction-level hardware/software partitionthrough DFG exploration[C]∥Proceedings of the 15th International Conference on Computer Supported Cooperative Work in Design (CSCWD).USA:IEEE,2011:55-60
[13] Bouchhima A,Gerin P,Pétrot F.Automatic instrumentation of embedded software for high level hardware/software co-simulation[C]∥Proceedings of the Design Automation Conference Asia and South Pacific (ASP-DAC).USA:IEEE,2009:546-551
[14] Wang D,Li S,Dou Y.Collaborative hardware/software partition of coarse-grained reconfigurable system using evolutionary ant colony optimization[C]∥Proceedings of the Design Automation Conference Asia and South Pacific (ASP-DAC).USA:IEEE,2008:679-684
[15] Srinivasan V,Govindarajan S,Vemuri R.Fine-grained andcoarse-grained behavioral partitioning with effective utilization of memory and design space exploration for multi-FPGA architectures[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2001,9(1):140-158
[16] Wolf W.Object-oriented cosynthesis of distributed embeddedsystems[J].ACM Transactions on Design Automation of Electronic Systems (TODAES),1996,1(3):301-314
[17] Henkel J,Ernst R.An approach to automated hardware/soft-ware partitioning using a flexible granularity that is driven by high-level estimation techniques[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2001,9(2):273-289
[18] Chai S,Li Y,Wang J,et al.A List Simulated Annealing Algorithm for Task Scheduling on Network-on-Chip[J].Journal of Computers,2014,9(1):176-182
[19] Liu W,Gu Z,Xu J,et al.Satisfiability modulo graph theory for task mapping and scheduling on multiprocessor systems[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(8):1382-1389
[20] Tahaee S A,Jahangir A H,Habibi-Masouleh H.Improving the performance of heuristic searches with judicious initial point selection[C]∥Proceedings of the Fifth IEEE International Symposium on Embedded Computing.USA:IEEE,2008:14-19
[21] Hu J,Marculescu R.Energy-aware communication and taskscheduling for network-on-chip architectures under real-time constraints[C]∥Proceedings of the Design,Automation and Test in Europe Conference and Exhibition.USA:IEEE,2004:234-239
[22] Vahid F.Partitioning sequential programs for CAD using athree-step approach[J].ACM Transactions on Design Automation of Electronic Systems (TODAES),2002,7(3):413-429
[23] Wiangtong T,Cheung P Y K,Luk W.Comparing three heuristic search methods for functional partitioning in hardware-software codesign[J].Design Automation for Embedded Systems,2002,6(4):425-449

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed