Comparing a Genetic Algorithm Penalty Function and Repair Heuristic in the DSP Application Domain

G. Gréwal, S. Coros, D. Banerji, and A. Morton (Canada)


genetic algorithm, digital signal processing, dual mem ory assignment


To increase memory bandwidth, many programmable Digital Signal Processors (DSPs) employ two on-chip data memories. This architectural feature supports higher memory bandwidth by allowing multiple data memory accesses to occur in parallel. Exploiting dual memory banks, however, is a challenging problem for compilers. This, in part, is due to the instruction-level parallelism, small numbers of registers, and highly spe cialized register capabilities of most DSPs. In this pa per, we present a new methodology based on a genetic algorithm (GA) for assigning data to dual-bank mem ories. Our approach is global, and integrates several important issues in memory assignment within a sin gle model. Special effort is made to identify those data objects that could potentially benefit from an assign ment to a specific memory, or perhaps duplication in both memories. As part of our experimentation, we compare the effectiveness of a repair heuristic which consist in transforming infeasible solutions into feasi ble ones, with a penalty functions that seeks to degrade the fitness of infeasible individuals based on their de gree of constraint violation. Our results show that the repair operator out-performs the penalty function. Tests on DSPstone benchmarks show that the GA is able to achieve a 54% reduction in the number of mem ory cycles and a reduction in the range of 7% to 42% in the total number of cycles.

Important Links:

Go Back