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
