Using Genetic Algorithms for Scheduling Data Flow Graphs

摘要

A scheduling problem in High Level Synthesis, a section in a silicon compiler forthe automatic design of integrated circuits, is addressed. In the High Level Synthesis section, the functional specification is transformed into a description for a network of modules (like adders or multipliers) and a controller for that network. A scheduler that uses a 'genetic algorithm' to perform the optimization is described. Internally it uses a (resource constrained) 'list scheduler' in the process of representing schedules. The genetic scheduler is fast and produces good results. Several features that would be nice for a scheduler (chaining, pipelining, taking into account register costs, etc.) are not yet implemented. The genetic part of the scheduler could not be tested very well because for many problems the initialization of the algorithm already gave the optimal solution. Larger benchmarks are necessary to test the genetic part more thoroughly.