Datapath synthesis using a problem-space genetic algorithm

This paper presents a new approach to datapath synthesis based on a problem-space genetic algorithm (PSGA). The proposed technique performs concurrent scheduling and allocation of functional units, registers, and multiplexers with the objective of finding both a schedule and an allocation which minimizes the cost function of the hardware resources and the total time of execution. The problem-space genetic algorithm based datapath synthesis system (PSGA-Synth) combines a standard genetic algorithm with a known heuristic to search the large design space in an intelligent manner. PSGA-Synth handles multicycle functional units, structural pipelining, conditional code and loops, and provides a mechanism to specify lower and upper bounds on the number of control steps. The PSGA-Synth was tested on a set of problems selected from the literature, as well as larger problems created by us, with promising results. PSGA-Synth not only finds the best known results for all the test problems examined in a relatively small amount of CPU time, but also has the ability to efficiently handle large problems