LL Logo



Data Remapping
Techniques for
Embedded Signal
Processing Applications

Viktor K. Prasanna
University of Southern California
Department of Electrical Engineering
3740 McClintock Avenue, EEB 200
Los Angeles, CA 90089-2562

Embedded signal processing applications such as STAP, SAR, ATR, Sonar among others consist of a number of stages in which data is accessed along different axes as the computation proceeds. For these applications, we first develop a unified methodology using run time data remapping between stages to realize scalable performance in using HPC technology. We then present new techniques to solve the classic run time data redistribution problem. For the Cyclic(X) to Cyclic(KX) distribution, problem we show new indirect techniques that perform the mapping using ceiling log K + 2 steps. Previous approaches take as much as K steps. All the data transfers are performed in a conflict-free manner and the index computation at the nodes can be performed in a distributed fashion with simple modulo computations. The corner turn operation and the data cube access between Doppler processing and beamforming in STAP are special cases of the above data redistribution problem. Using our approach we show efficient algorithms for several related redistribution problems arising in throughput oriented implementations of signal processing applications. Interstage data movement operations that arise in using HPC platforms for STAP, SAR, ATR, and Sonar applications can be modelled by the above data redistribution problem. Using our techniques for redistribution, we show scalable parallel algorithms and implementations for STAP, SAR, ATR, and universal beamforming in Sonar applications on IBM SP-2 and Cray T3D. Experimental results are shown using MITRE and MIT LL STAP benchmarks and Sonar benchmarks from NUWC. For corner turn and SAR image formation, we show implementations that reduce the number of compute nodes by 40% compared with earlier implementations. These implementations have been performed using the Message Passing Interface (MPI) and C and are portable.


LL Logo Disclaimer

Direct comments and questions to: webmaster@ll.mit.edu

Last modified: October 11, 2012

© MIT Lincoln Laboratory. All rights reserved.