Design and analysis of parallel algorithms for distributed in situ array beamforming

Parallel processing algorithms, coupled with advanced networking and distributed computing architectures, improve the overall computational performance, dependability, and versatility of a digital signal processing system. In this dissertation, several novel parallel algorithms are introduced and investigated for beamforming algorithms that include split-aperture conventional beamforming (SA-CBF), subspace projection beamforming (SPB), and conventional matched-field processing (CMFP) algorithms. Each beamforming algorithm has its distinctive complexity and bottlenecks caused by the unique computational pattern of the algorithm. Based on a specific domain, each parallel algorithm decomposes the sequential workload in order to obtain scalable parallel speedup and efficient memory management. Depending on the processing requirement of the beamforming algorithm, the computational performance of the parallel algorithm reveals different characteristics. The least computationally complex algorithm, SA-CBF, is particularly susceptible to the communication overhead. With parallel SA-CBF algorithms, the best combination is shown to yield around 80% scaled efficiency on a cluster of workstations. The two high-complexity algorithms, SPB and CMFP, show scalable parallel performance on the testbed. The impact on parallel performance due to workload balancing, communication scheme, algorithm complexity, processor speed, network performance, and testbed configuration is explored. Finally, results show almost ideal distributed energy characteristics over the multiple processors used by the parallel algorithms in CMFP.