Architecture decomposition in system synthesis of heterogeneous many-core systems

ABSTRACT

Determining feasible application mappings for Design Space Exploration (DSE) and run-time embedding is a challenge for modern many-core systems. The underlying NP-complete system-synthesis problem faces tremendously complex problem instances due to the hundreds of heterogeneous processing elements, their communication infrastructure, and the resulting number of mapping possibilities. Thus, we propose to employ a search-space splitting (SSS) technique using architecture decomposition to increase the performance of existing design-time and run-time synthesis approaches. The technique first restricts the search for application embeddings to selected sub-architectures at substantially reduced complexity; therefore, the complete architecture needs to be searched only in case no embedding is found on any sub-system. Furthermore, we introduce a basic learning mechanism to detect promising sub-architectures and subsequently restrict the search to those. We exemplify the SSS for a SAT-based and a problem-specific backtracking-based system synthesis as part of DSE for NoC-based many-core systems. Experimental results show drastically reduced execution times (≈ 15--50 x on a 24×24 architecture) and an enhanced quality of the embedding, since less mappings (≈20--40 x, compared to the non-decomposing procedures) need to be discarded due to a timeout.

References

1. A. K. Singh, M. Shafique, A. Kumar and J. Henkel. 2013. Mapping on Multi/Many-core Systems: Survey of Current and Emerging Trends. In 2013 50th ACM/EDAC/IEEE Design Automation Conference (DAC). 1--10.
2. M. K. Benhaoua and A. K. Singh. 2014. Heuristic for Accelerating Run-time Task Mapping in NoC-based Heterogeneous MPSoCs. Journal of Digital Information Management 12, 5 (2014), 293.
3. R. Dick. 2018. Embedded System Synthesis Benchmarks Suite (E3S). (2018). http://ziyang.eecs.umich.edu/~dickrp/e3s/.
4. A. Emeretlis, G. Theodoridis, P. Alefragis, and N. Voros. 2016. A Logic-Based Benders Decomposition Approach for Mapping Applications on Heterogeneous Multicore Platforms. ACM Trans. Embed. Comput. Syst. 15, 1, Article 19 (2016).
5. M. A. Al Faruque, R. Krist, and J. Henkel. 2008. ADAM: Run-time Agent-based Distributed Application Mapping for On-Chip Communication. In 2008 45th ACM/IEEE Design Automation Conference. 760--765.
6. A. Goens, S. Siccha, and J. Castrillon. 2017. Symmetry in Software Synthesis. ACM Transactions on Architecture and Code Opt. 14, 2, Article 20 (2017).
7. L. Benini, M. Lombardi, M. Milano and M. Ruggiero. 2011. Optimal Resource Allocation and Scheduling for the CELL BE Platform. Annals of Operations Research 184, 1 (2011), 51--77.
8. M. Lukasiewycz, M. Glaß, F. Reimann, and J. Teich. 2011. Opt4J: A Modular Framework for Meta-heuristic Optimization. In Proc. of the 13th Annual Conf. on Genetic and Evol. Comp. (GECCO '11). ACM, New York, NY, USA, 1723--1730.
9. M. Laumanns, L. Thiele, K. Deb and E. Zitzler. 2002. Combining Convergence and Diversity in Evolutionary Multiobjective Optimization. Evolutionary Computing 10, 3 (2002), 263--282.
10. M. Ruggiero, A. Guerri, D. Bertozzi, M. Milano and L. Benini. 2008. A Fast and Accurate Technique for Mapping Parallel Applications on Stream-Oriented MPSoC Platforms with Communication Awareness. International Journal of Parallel Programming 36, 1 (2008), 3--36.
11. P. K. Sahu and S. Chattopadhyay. 2013. Survey on Application Mapping Strategies for Network-on-Chip Design. Journal of Systems Arch. 59, 1 (2013), 60 -- 76.
12. T. Schwarzer, A. Weichslgartner, M. Glaß, S. Wildermann, P. Brand, and J. Teich. 2018. Symmetry-Eliminating Design Space Exploration for Hybrid Application Mapping on Many-Core Architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 37, 2 (Feb 2018), 297--310.
13. A. K. Singh, P. Dziurzanski, H. R. Mendis, and L. S. Indrusiak. 2017. A Survey and Comp. Study of Hard and Soft Real-Time Dynamic Resource Allocation Strategies for Multi-/Many-Core Systems. ACM Comput. Surv. 50, 2, Article 24 (2017).
14. T. Blickle, J. Teich and L. Thiele. 1998. System-Level Synthesis Using Evolutionary Algorithms. Design Automation for Embedded Systems 3, 1 (1998), 23--58.
15. J. Teich. 2012. Hardware/Software Codesign: The Past, the Present, and Predicting the Future. Proc. IEEE 100, Special Centennial Issue (2012), 1411--1430.
16. A. Weichslgartner, D. Gangadharan, S. Wildermann, M. Glaß, and J. Teich. 2014. DAARM: Design-Time Application Analysis and Run-Time Mapping for Predictable Execution in Many-Core Systems. In Proc. of CODES+ISSS 2014.
17. E. Zitzler and L. Thiele. 1998. Multiobjective Optimization Using Evolutionary Algorithms --- A Comparative Case Study. In In Proceedings of PPSN. 292--301.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Multicore architectures

  • Embedded and cyber-physical systems

    • Embedded systems