Architecture Synthesis and Partitioning of Real-Time Systems: A Comparison of Three Heuristic Search Strategies

ABSTRACT

This paper studies the problem of automatically selecting a suitable system architecture for implementing a real-time application. Given a library of hardware components, it is shown how an architecture can be synthesized with the goal of fulfilling the real-time constraints stated in the system's specification. In case the selected architecture contains several processing units, the specification is partitioned by assigning tasks to these. The use of three heuristic search techniques is investigated: genetic algorithms, simulated annealing, and tabu search; and it is described how these can be adapted to the architecture synthesis problem. It is concluded that tabu search is the most promising technique, but that simulated annealing is also applicable.

REFERENCES

• 1: [1] J. Axelsson. Schedulability-driven partitioning of heterogeneous real-time systems. Licentiate Thesis No. 517, Linköping University, 1995.
• 2: Jakob Axelsson, Hardware/software partitioning aiming at fulfillment of real-time constraints, Journal of Systems Architecture: the EUROMICRO Journal, v.42 n.6-7, p.449-464, Dec. 1, 1996 [doi>10.1016/S1383-7621(96)00033-1]
• 3: [3] J. Axelsson. Three search strategies for architecture synthesis and partitioning of real-time systems. Technical Report LiTH-IDA-R-96-32, Dept. of Computer and Information Science, Linköping University, 1996. (Available from http://www.ida.liu.se/publications/techrep/)
• 4: [4] K. Buchenrieder and A. Pyttel. System zur wissensbasierten Konfigurierung von Leiterplatten. CADS, 92(1): 52-59, 1992.
• 5: [5] P. Eles, Z. Peng, K. Kuchcinski, and A. Doboli. System level hardware/software partitioning based on simulated annealing and tabu search. To appear in Design Automation for Embedded Systems, 1997.
• 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: Fred Glover , Eric Taillard , Dominique de Werra, A user's guide to tabu search, Annals of Operations Research, v.41 n.1-4, p.3-28, 1993
• 8: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 9: [9] S. Kirkpatrick, C. D. Gelatt, Jr., and M. P Vecchi. Optimization by simulated annealing. Science, 220(4598): 671-680, May 1983.
• 10: Chunho Lee , Miodrag Potkonjak , Wayne Wolf, System-Level Synthesis of Application Specific Systems using A* Search and Generalized Force-Directed Heuristics, Proceedings of the 9th international symposium on System synthesis, p.2, November 06-08, 1996
• 11: [11] S. Narayan and D. D. Gajski. Area and performance estimation from system-level specification. Technical Report ICS-92-16, University of California, Irvine, 1992.
• 12: [12] S. Prakash and A. C. Parker. SOS: Synthesis of application-specific heterogeneous multiprocessor systems. Journal of Parallel and Distributed Computing, 16: 338-351, 1992.
• 13: K. W. Tindell , A. Burns , A. J. Wellings, Allocating hard real-time tasks: an NP-hard problem made easy, Real-Time Systems, v.4 n.2, p.145-165, May 1992 [doi>10.1007/BF00365407]

INDEX TERMS

Keywords:
Architecture Synthesis, Real-Time Systems, Heuristic Search