Publication: A Parallel Scatter Search for Performing Data Partitioning

All || By Area || By Year

Title	A Parallel Scatter Search for Performing Data Partitioning
Authors/Editors*	M. Walton, G. Grewal, W. Dobosiewicz
Where published*	2nd International Multi-Conference on Engineering and Technological Innovation, Orlando, USA
How published*	Journal
Year*	2009
Volume
Number
Pages	77-83
Publisher
Keywords	DSP, partitioning, multicore, scatter search
Link
Abstract	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 parallel scatter search 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. Our computational results show that the scatter search 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 when tested with well-known DSP kernels and applications.