Incremental run-time application mapping for homogeneous NoCs with multiple voltage levels

ABSTRACT

In this paper, we propose an efficient technique for run-time application mapping onto Network-on-Chip (NoC) platforms with multiple voltage levels. Our technique consists of a region selection algorithm and a heuristic for run-time application mapping which minimizes the communication energy consumption, while still providing the required performance guarantees. The proposed technique allows for new applications to be easily added to the system platform with minimal inter-processor communication overhead. Moreover, our approach scales very well for large designs. Finally, the experimental results show as much as 50% communication energy savings compared to arbitrary mapping solutions.

REFERENCES

• 1: William J. Dally , Brian Towles, Route packets, not wires: on-chip inteconnection networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 2: J. Hu, R. Marculescu," Energy- and performance-aware mapping for regular NoC architectures," IEEE Trans. on CAD, 24(4), Apr. 2005.
• 3: Srinivasan Murali , Giovanni De Micheli, Bandwidth-Constrained Mapping of Cores onto NoC Architectures, Proceedings of the conference on Design, automation and test in Europe, p.20896, February 16-20, 2004
• 4: L. T. Smit, et. al, "Run-time assignment of tasks to multiple heterogeneous processors," Progress 2004 Embedded Systems Symp., the Netherlands, Oct. 2004.
• 5: H. J. Broersma, et. al, "The computational complexity of the minimum weight processor assignment problem," Proc. Intl. Workshop on Graph-theoretic Concepts in Computer Science, Bonn, Germany, June 2004.
• 6: Huaizhi Wu , Martin D. F. Wong , I-Min Liu, Timing-constrained and voltage-island-aware voltage assignment, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147023]
• 7: Terry Tao Ye , Giovanni De Micheli , Luca Benini, Analysis of power consumption on switch fabrics in network routers, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514051]
• 8: Task graphs for free (TGFF v3.0) Keith Vallerio, 2003. http://ziyang.ece.northwestern.edu/tgff/.
• 9: R. Dick, "Embedded system synthesis benchmarks suites (E3S)," http://www.ece.northwestern.edu/~dickrp/e3s.
• 10: Hang-Sheng Wang , Xinping Zhu , Li-Shiuan Peh , Sharad Malik, Orion: a power-performance simulator for interconnection networks, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 11: A. M. Pastrnak, P. H. N. de With, S. Stuijk, J. van Meerbergen, "Parallel implementation of arbitrary-shaped MPEG-4 decoder for multiprocessor Systems," in Proc. Visual Comm. and Image Processing, San Jose, CA, Jan. 2006.
• 12: J.-M. Chang, M. Pedram, "Codex-dp: co-design of communicating systems using dynamic programming," IEEE Trans. on CAD, 19(7), July 2000.
• 13: Vincent Nollet , Théodore Marescaux , Diederik Verkest , Jean-Yves Mignolet , Serge Vernalde, Operating-system controlled network on chip, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996637]
• 14: Paul Pop , Petru Eles , Traian Pop , Zebo Peng, An approach to incremental design of distributed embedded systems, Proceedings of the 38th conference on Design automation, p.450-455, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378557]
• 15: J. Kao, F. B. Prinz, "Optimal motion planning for deposition in layered manufacturing," Proc. Design Engineering Technical Conf., Atlanta, GA, Sept. 1998.
• 16: Umit Y. Ogras , Radu Marculescu , Puru Choudhary , Diana Marculescu, Voltage-frequency island partitioning for GALS-based networks-on-chip, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278509]
• 17: M. A. Bender, et. al, "Communication-aware processor allocation for supercomputers," Proc. Workshop on Algorithm and Data Structure, Waterloo, Canada, Aug. 2005.
• 18: Stefano Bertozzi , Andrea Acquaviva , Davide Bertozzi , Antonio Poggiali, Supporting task migration in multi-processor systems-on-chip: a feasibility study, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 19: C. Y. Lee, "An algorithm for path connection and its applications," IRE Trans. Electron Comput., vol. EC-10, pp. 346--365, Sept. 1961.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance

Keywords:
dynamic application mapping, low-power, networks-on-chip