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.