Signal processing algorithms on parallel architectures: A performance update

The Burg algorithm is a widely applied and extensively studied signal processing procedure having a structure typical of a class of important batch signal processing algorithms. Its implementation and performance on four different parallel machines were reported in the 1990 Journal of Parallel and Distributed Computing Special Issue on Massively Parallel Computation. The machines were: the Intel iPSC/2, the Denelcor HEP, the NASA/Goodyear MPP, and the Cray X-MP/48. The objective of the work reported here was to extend that study to two new parallel machines: the nCUBE 2 and the MasPar MP-1. These computers are related to the distributed memory systems above (i.e., the iPSC and the MPP, respectively), but use newer technology. In addition to achieving significant performance gains on the new machines compared to machines in the same architectural class, we found that the original study underestimated the scaleability of the algorithm. That is, the algorithm maps efficiently to small-scale as well as large-scale computers, including both SIMD and MIMD distributed memory systems. Improvements in the parallel algorithm are highlighted. Of special import is the use of appropriate performance metrics and performance visualization to characterize the parallelism of the algorithm and lend insight toward understanding and evaluating its performance. 14 refs., 9 figs