Comparing a genetic algorithm penalty function and repair heuristic in the DSP application domain
Gary Gréwal, Stelian Coros, D.K. Banerji, Alec Morton · International conference on Artificial intelligence and applications · 2006
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 specialized register capabilities of most DSPs. In this paper, we present a new methodology based on a genetic algorithm (GA) for assigning data to dual-bank memories. Our approach is global, and integrates several important issues in memory assignment within a single model. Special effort is made to identify those data objects that could potentially benefit from an assignment 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 feasible ones, with a penalty functions that seeks to degrade the fitness of infeasible individuals based on their degree 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 memory cycles and a reduction in the range of 7% to 42% in the total number of cycles.