Datapath synthesis using concurrent scheduling and allocation based on problem-space genetic algorithms
F.H. Hielscher, M.K. Dhodhi · 1992
A high-level synthesis system, which includes a datapath synthesizer and a control table generator, is presented. The datapath synthesizer performs concurrent scheduling and allocation of functional units, registers and multiplexers. The core of the datapath synthesizer is a concurrent scheduling and allocation approach based on a problem-space genetic algorithm (PSGA). The objective of this approach is to find a schedule and allocation which minimizes a given cost function of hardware resources and the total time of execution. The proposed datapath synthesizer allows multi-cycle functional units as well as structural pipelining. The datapath synthesizer combines the power of genetic algorithms, a global search method, with a known heuristic to search a large design space in an intelligent manner. The datapath synthesizer was tested on a set of problems selected from the literature and the results were compared with results obtained by several state-of-the-art existing datapath synthesis systems. Also some large tree data flow graphs (more than 200 nodes) were synthesized using this datapath synthesizer. The datapath synthesizer described here not only finds the known optimal designs for all the test problems examined, but also has the ability to handle large problems more efficiently than the other existing datapath synthesis systems which use a concurrent scheduling and allocation approach. The proposed high-level synthesis system also generates control specifications in the form of a control table.