Scheduling and allocation in high-level synthesis using genetic algorithm

Abstract

High-level Synthesis (HLS) is the process of automatically translating abstract behavioral models of digital systems to implementable hardware. Operation scheduling and hardware allocation are the two most important phases in the synthesis of circuits from behavioral specification. Scheduling and allocation can be formulated as an optimization problem. In this work a unique approach to scheduling and allocation problem using the genetic paradigm is described. The main contributions include: (1) a new chromosomal representation for scheduling and for two subproblems of allocation, and (2) two novel crossover operators to generate legal schedules. In addition the application of tabu search to scheduling and allocation is also implemented and studied. Both techniques have been tested on various benchmarks and results obtained for data-oriented control-data flow graphs (CDFGs) are compared with other implementations. A novel interconnect optimization technique using genetic algorithm is also realized.