Computer Science ›› 2015, Vol. 42 ›› Issue (7): 78-84.doi: 10.11896/j.issn.1002-137X.2015.07.017

Previous Articles     Next Articles

Efficient Reduction Algorithms for Directed Acyclic Graph

HOU Rui WU Ji-gang   

  • Online:2018-11-14 Published:2018-11-14

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

[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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!