A Hierarchical Genetic Algorithm for Hardware Software Co-Synthesis with a Stochastic Approach

Abstract

One of the most challenging problems that occurs in the design of real-time embedded systems is to take into account the stochastic nature of different timing parameters which affect the system performance. In this paper we propose a stochastic framework for hardware-software co-synthesis whereby the task execution times, the data communication times and the input arrival times are all assumed to be random variables. Based on this framework, a hierarchical genetic algorithm has been developed which explores the state space of possible architectures and produces a set of evolved ones which are optimized with respect to cost and performance. This is coupled with a stochastic scheduling algorithm which generates high performance stochastic schedules for the tasks and estimates the overall deadline meeting probability of the system.

Indexing terms:

• Real time embedded systems
• Hardware-software co-synthesis
• Task precedence graph
• Stochastic scheduling
• hierarchical genetic algorithm

Additional information

Notes on contributors

S Chakraverty

Sampa Chakraverty is is an Asstt Professor in the Division of Computer Engineering at Netaji Subhash Institute of Technology. She received her BE degree in Electronics and Communication from Delhi University and MTech in Integrated Electronics and Circuits from IIT, Delhi. Her research interests are CAD of VLSI, Hard/Softwate co-design, Embeded systems and computer architecture.

C P Ravikumar

C P Ravikumar is with the ASIC Product Development Center at Texas Instruments India. Prior to joining TI India, he was with the Department of Electrical Engineering at the Indian Institute of Technology, Delhi as a Professor (1991–2001). He was a visiting faculty at the University of Sourthern California (1995–1996) and spent an year with Controlnet India Pvt Ltd, Goa as Vice President, Training (2000–2001). He obtained his BE degree (Electronics) from Bangalore University (1983), ME (Computer Science) from the Indian Institute of Science (1987) and PhD from the University of Southern California (1991). He has supervised 4 PhD theses and a large number of M Tech and B Tech theses at IIT Delhi. He has authored over 150 technical papers in International journals and conferences. He is the author of the book “Parallel Methods for VLSI Layout” (Ablex Publishers, USA, 1995) and the editor of the books “VLSI Design and Test—Milestones and Challenges,” (Phoenix Publishers, New Delhi, 2000) and “Frontiers of VLSI Design and Test” (Phoenix Publishers, 2001). He founded the VLSI Design and Test Workshops in 1998 and the VLSI Education Day in 2000 and has served as the General Chair of these events since inception. He is the Indian Editor of the International Journal of VLSI Design (Gordon and Breach Publishers) since 1991 and the member of the Editorial Staff of Journal of Electronic Testing (Kluwer) since 2001. He has served as the Technical Program Chair of the International Conference on VLSI Design (2001, 2002). He has served on the program committees of several conferences such as the International Conference on High Performance Computing and the International Conference on VLSI Design. Ravikumar is a recipient of the ACM/SIGDA Student Award at the IEEE/ACM Design Automation Conference (1990), the Best Student Paper award at the IEEE International Conference on VLSI Design (1998), and the Best Paper Award at the IEEE International Conference on VLSI Design (2001).

D Roy Choudhuri

D Roy Choudhury was born in Calcutta, India in 1946. He received MTech degree from the Institute of Radio-physics and Electronics, Calcutta in 1966 and PhD in control systems from the same institute, Calcutta University in 1971.

From 1971 to 1973 he was working as Research Assistant in the institute de Reglage Automatique, Ecole Polytecnic Federal de Laussanne, Switzerland. Since 1974 he has been in the faculty of Delhi College of Engineering, Delhi where is is presently professor in the Computer Engineering Department. He is also a professor in the Department of Electronics and Communication Engineering. Faculty of Technology, University of Delhi where presently he is chairing the department. His research interest includes control system, Fuzzy and Neural network, Petri net.

He is author of the book ‘Networks and Systems’ and coauthor of the book ‘Linear Integrated Circuits’ both from Wiley Eastern India Ltd, New Delhi in 1988 and 1991 respectively.