ADAM: run-time agent-based distributed application mapping for on-chip communication

ABSTRACT

Design-time decisions can often only cover certain scenarios and fail in efficiency when hard-to-predict system scenarios occur. This drives the development of run-time adaptive systems. To the best of our knowledge, we are presenting the first scheme for a run-time application mapping in a distributed manner using agents targeting for adaptive NoC-based heterogeneous multi-processor systems. Our approach reduces the overall traffic produced to collect the current state of the system (monitoring-traffic), needed for runtime mapping, compared to a centralized mapping scheme. In our experiment, we obtain 10.7 times lower monitoring traffic compared to the centralized mapping scheme proposed in [8] for a 64 x 64 NoC. Our proposed scheme also requires less execution cycles compared to a non-clustered centralized approach. We achieve on an average 7.1 times lower computational effort for the mapping algorithm compared to the simple nearest-neighbor (NN) heuristics proposed in [6] in a 64 x 32 NoC. We demonstrate the advantage of our scheme by means of a robot application and a set of multimedia applications and compare it to the state-of-the-art run-time mapping schemes proposed in [6, 8, 19].

References

1. L. Benini and G. De Micheli. "Networks on Chips: A new SoC paradigm". IEEE Computer, 35(1):70--78, 2002.
2. S. Bertozzi, A. Acquaviva, D. Bertozzi, and A. Poggiali. "Supporting task migration in multi-processor systems-on- chip: a feasibility study". DATE '06: Proc. of the Conf. on Design, Automation and Test in Europe, pages 15--20, 2006.
3. A. Bieszczad, B. Pagurek, and T. White. "Mobile agents for network management". IEEE Comm. surveys and tutorials, 1(1):2--9, 1998.
4. S. Borkar. "Thousand core chips - A technology perspective". DAC '07: Proc. of the 44th annual Conf. on Design Automation, pages 746--749, 2007.
5. H. Broersma, D. Paulusma, G. J. M. Smit, F. Vlaardinger-broek, and G. J. Woeginger. "The computational complexity of the minimum weight processor assignment problem". WG '04: Proc. of the 30th int. Workshop on Graph-theoretic concepts in computer science, pages 189--200, 2004.
6. E. Carvalho, N. Calazans, and F. Moraes. "Heuristics for dynamic task mapping in NoC-based heterogeneous MPSoCs". RSP '07: Proc. of the 18th IEEE int. workshop on Rapid System Prototyping, pages 34--40, May 2007.
7. J. Chan and S. Parameswaran. "NoCGEN: A template based reuse methodology for networks on chip architecture". VLSID '04: Proc. of the 17th int. Conf. on VLSI Design, pages 717--720, 2004.
8. C.-L. Chou and R. Marculescu. "Incremental run-time application mapping for homogeneous NoCs with multiple voltage levels". CODES+ISSS '07: Proc. of the 5th IEEE/ACM int. Conf. on Hardware/software Codesign and system synthesis, pages 161--166, 2007.
9. W. J. Dally and B. Towles. "Route packets, not wires: Onchip interconnection networks". DAC '01: Proc. of the 38th Conf. on Design Automation, pages 684--689, 2001.
10. R. P. Dick. D. L. Rhodes, and W. Wolf. "TGFF: Task graphs for free". CODES/CASHE '98: Proc. of the 6th int. workshop on Hardware/software Codesign, pages 97--101, 1998.
11. M. A. A. Faruque, T. Ebi, and J. Henkel. "Run-time adaptive on-chip communication scheme". ICCAD '07: Proc. of the 2007 IEEE/ACM int. Conf. on Computer-aided design, pages 26--31, 2007.
12. A. Hansson, K. Goossens, and A. Rǎdulescu. "A unified approach to constrained mapping and routing on network-on-chip architectures". CODES+ISSS '05: Proc. of the 3rd IEEE/ACM int. Conf. on Hardware/software Codesign and system synthesis, pages 75--80, 2005.
13. J. Henkel, W. Wolf, and S. Chakradhar. "On-chip networks: A scalable, communication-centric embedded system design paradigm". VLSID '04: Proc. of the 17th int. Conf. on VLSI Design, pages 845--851, 2004.
14. P. Horn. "Autonomic computing: IBM's perspective on the state of information technology". IBM Corporation, 2001.
15. J. Hu and R. Marculescu. "Exploiting the routing flexibility for energy/performance aware mapping of regular NoC architectures". DATE '03: Proc. of the Conf. on Design, Automation and Test in Europe, pages 10688--10693, 2003.
16. T. Lei and S. Kumar. "A two-step genetic algorithm for mapping task graphs to a network on chip architecture". DSD '03: Proc. of the Euromicro symposium on Digital Systems Design, pages 180--189, 2003.
17. V. Nollet, T. Marescaux, P. Avasare, D. Verkest, and J.-Y. Mignolet. "Centralized run-time resource management in a network-on-chip containing reconfigurable hardware tiles". DATE '05: Proc. of the Conf. on Design. Automation and Test in Europe, pages 234--239, March 2005.
18. P. Azad, A. Ude, T. Asfour, G. Cheng, and R. Dillmann. "Image-based markerless 3D human motion capture using multiple cues". Proc. of the int. workshop on Vision Based Human-Robot Interaction, 2006.
19. L. Smit, G. Smit. J. Hurink, H. Broersma, D. Paulusma, and P. Wolkotte. "Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture". FPL '04: Proc. of the IEEE int. Conf. on Field-Programmable Technology, pages 421--424, 2004.
20. P. Smith and N. C. Hutchinson. "Heterogeneous process migration: The Tui system". Software - Practice and Experience, 28(6):611--639, 1998.
21. Xilinx. "Virtex2 datasheets". http://www.xilinx.com/.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

  • Real-time systems