An evolutionary approach to system-level synthesis

ABSTRACT

Considers system-level synthesis as the problem of optimally mapping a task-level specification onto a heterogeneous hardware/software architecture. This problem requires: (1) the selection of the architecture (allocation), including general-purpose and dedicated processors, ASICs, buses and memories; (2) the mapping of the algorithm onto the selected architecture in space (binding) and time (scheduling); and (3) the design space exploration, with the goal of finding a set of implementations that satisfy a number of constraints on cost and performance. In this paper, a new graph-based mapping model is introduced to specify the task of system-level synthesis as an optimization problem. An evolutionary algorithm is adapted to solve this problem and is applied to explore the design space of video-codec implementations.

REFERENCES

• 1: [1] E. Barros and W. Rosenstiel. A method for hardware software partitioning. In Proc. 1992 COMPEURO: Computer Systems and Software Engineering, pages 580-586, The Hague, Netherlands, May 1992.
• 2: [2] T. Blickle, J. Teich, and L. Thiele. System-level synthesis using evolutionary algorithms. Technical Report 16, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, April 1996. http://www.tik.ee.eths.ch/ Publications/ TIK-Reports/ TIK-Report16.pa.gz.
• 3: [3] R. Camposano and R. K. Brayton. Partitioning before logic synthesis. In Proc. ICCAD, 1987.
• 4: Joseph G. D'Ambrosio , Xiaobo (Sharon) Hu, Configuration-level hardware/software partitioning for real-time embedded systems, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• 5: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 6: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964]
• 7: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 8: [8] R. Gupta and G. De Micheli. System-level synthesis using reprogrammable components. In Proc. of the European Conference on Design Automation (EDAC), pages 2-7, 1992.
• 9: [9] W. Hardt and R. Camposano. Specification analysis for hw/sw-partitioning. In Proc. GI/ITG Workshop Application of formal Methods during the Design of Hardware Systems, pages 1-10, Passau, Germany, March 1995.
• 10: [10] T. B. Ismail, K. O'Brien, and A. A. Jerraya. Interactive system-level partitioning with PARTIF. In Proc. of the European Conference on Design Automation (EDAC), pages 464-473, 1994.
• 11: Kayhan Küçükçakar , Alice C. Parker, A methodology and design tools to support system-level VLSI design, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.3, p.355-369, Sept. 1995 [doi>10.1109/92.406994]
• 12: [12] E. D. Lagnese and D. E. Thomas. Architectural partitioning for system level synthesis of integrated circuits, IEEE Trans. on CAD, 10(7):847-860, July 1991.
• 13: Michael C. McFarland, Using bottom-up design techniques in the synthesis of digital hardware from abstract behavioral descriptions, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.474-480, July 1986, Las Vegas, Nevada, United States
• 14: F. Vahid , D. D. Gajski, Specification partitioning for system design, Proceedings of the 29th ACM/IEEE conference on Design automation, p.219-224, June 08-12, 1992, Anaheim, California, United States

INDEX TERMS

Keywords:
ASICs, algorithm mapping, allocation, architecture selection, binding, buses, cost constraints, dedicated processors, design space exploration, evolutionary approach, general-purpose processors, genetic algorithms, graph-based mapping model, heterogeneous hardware/software architecture, memories, optimal mapping, optimization problem, performance constraints, scheduling, system-level synthesis, task-level specification mapping, video-codec implementations