An evolutionary algorithm for concurrent scheduling and allocation in the process of integrated-circuit design

Authors

G. Papa,
J. Šilc,
F. Bratkovič

Publication

Electrotechnical Review , 2003, 70(4): 202-207

Abstract

This work presents a method enabling an evolutionary approach to some of the tasks of integrated-circuit design. It is focused on application-specific integrated circuits that need rather sophisticated design (in terms of size and speed) because of their specific use. <br />
The evolutionary approach considers scheduling and allocation constraints and ensures a globally optimal solution in a reasonable time. According to the description of the circuit, all operations are scheduled twice, i.e. as soon as possible and as late as possible. The two schedules are the boundaries between which we have to find an optimal solution. Each solution has to be properly encoded into the chromosomes, i.e. start times and unit for each operation. The chromosomes are multiplied to make a large enough population. In the iterations of the genetic algorithm the genetic operators transform the chromosomes. The starting times of the operations or their execution units are changed by crossover, mutation and variation. At the end we get an optimal solution. <br />
To evaluate our method, we built an algorithm and implemented it with a computer. We used it over a group of test-bench integrated circuits chosen according to their appearance in a similar study. The circuits differed in size and the number of operation types. It turned out that the evolutionary method is able to find a solution that is more appropriate in terms of all the considered and important parameters than is the case when working with classical deterministic methods.

BIBTEX copied to Clipboard