SCHEDULING AND ALLOCATION IN HIGH-LEVEL SYNTHESIS USING STOCHASTIC TECHNIQUES

High-level synthesis is the process of automatically translating abstr act behavioral models of digtal systems to implementable hardware. Ope ration scheduling and hardware allocation are the two most important p hases in the synthesis of circuits from behavioral specification. Sche duling and allocation can be formulated as an optimization problem. In this work, a unique approach to scheduling and allocation problem usi ng the genetic algorithm (GA) is described. This approach is different from a previous attempt using GA (Wehn et al., IFIP Working Conferenc e on Logic and Architecture Synthesis, Paris, 1990, pp. 47-56) in many respects. The main contributions include: (1) a new chromosomal repre sentation for scheduling and for two subproblems of allocation; and (2 ) two novel crossover operators to generate legal schedules. In additi on the application of tabu search (TS) to scheduling and allocation is also implemented and studied. Two implementations of TS are reported and compared. Both genetic scheduling and allocation (GSA) and tabu sc heduling and allocation (TSA) have been tested on various benchmarks a nd results obtained for data-oriented control-data flow graphs are com pared with other implementations in the literature. (A discussion on G SA was presented at the European Design Automation Conference Euro-DAC '94 in Grenoble, France, and TSA at the International Conference on El ectronics, Circuits and Systems - ICECS'94 in Cairo, Egypt.) A novel i nterconnect optimization technique using the GA is also realized. Copy right (C) 1996 Elsevier Science Ltd.