DATAPATH SYNTHESIS USING A PROBLEM-SPACE GENETIC ALGORITHM

This paper presents a new approach to datapath synthesis based on a pr oblem-space genetic algorithm (PSGA). The proposed technique performs concurrent scheduling and allocation of functional units, registers, a nd multiplexers with the objective of finding both a schedule and an a llocation which minimizes the cost function of the hardware resources and the total time of execution, The problem-space genetic algorithm b ased datapath synthesis system (PSGA_Synth) combines a standard geneti c 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 me chanism to specify lower and upper bounds on the number of control ste ps, The PSGA_Synth was tested on a set of problems selected from the l iterature, as well as larger problems created by us, with promising re sults, PSGA_Synth not only finds the best known results for all the te st problems examined in a relatively small amount of CPU time, but als o has the ability to efficiently handle large problems.