Efficient implementation of digital signal processing algorithms on high performance multiprocessor systems

Digital signal processing (DSP) applications are highly computation intensive. In order to realize a given systems objective which may be the fastest task completion time or the highest throughput rate or any other suitable metric, multiprocessing is usually carried out. The target architecture would typically comprise of complex processors connected in a suitable topology by a high bandwidth communications network. To fully exploit the advantage of using increasingly sophisticated processors and interconnect medium, a systematic approach to system design and implementation must be adopted. In this research we address some of the main issues in the efficient implementation of DSP applications on high performance multiprocessor systems and propose techniques to enhance overall system performance.;We first propose our model for the organization of a DSP system. This model is hierarchical and comprises of processors or processor clusters connected by a suitable interconnection scheme. The given DSP application is partitioned on these processor clusters. Given the high level description of a DSP application by a signal flow graph, we use the Ratio-Cut Partitioning technique and allocate tasks to processing elements. Since maximization of the throughput rate is a common goal when processing a continuous stream of data, we propose a macropipelining based scheduling scheme to achieve our objective. Through various example graphs, we compare and contrast our approach with that of other approaches in literature and show how our technique is best suited for our application domain. We show how an exact network cost model can affect our scheduling results by scheduling a task graph on a 4 node SCI ring using an exact network cost model developed by Picker et al. We then also show how our partitioning and scheduling methodology realizes the goals of rapid prototyping DSP systems.;After the system level partitioning and scheduling, we then target individual DSP algorithms and partition and schedule these algorithms on a single cluster of processors. Specifically we have chosen the Adaptive Beamforming algorithm and ESPRIT. By judiciously allocating rows and columns of these matrix based algorithms, we show how our approach is a more viable alternative to that of traditional array processor solutions that have been proposed in the past.