Integrated Scheduling, Allocation and Binding in High Level Synthesis using Multi Structure Genetic Algorithm based Design Space Exploration System

Anirban Sengupta and Reza Sedaghat
Ryerson University


This paper presents a novel multi structure genetic algorithm based design space exploration system which concurrently solves the problem of integrated scheduling, allocation and binding in High Level Synthesis based on the user specified power consumption and execution time constraints (not just latency constraint). The proposed novel cost function based on power consumption and execution time considers functional units, registers, multiplexers, demultiplexers and clock frequency oscillator during the exploration process. The presented approach incorporates a new seeding process for the two special parent chromosomes as well as employs a novel ‘load factor heuristic’ which guarantees that the final solution found will always be optimal/near-optimal in terms of the user specified execution time and power constraints. The results of the final solution reflect the number of adders/subtractors, multipliers, clock frequency, multiplexers, demultiplexers and registers. Further, the final result also indicates the latency, execution time, power consumption and the optimal/near-optimal resource combination found. The proposed approach when verified for number of standard DSP benchmarks yielded superior results compared to a recent GA based heuristic approach.