On design strategies for parallel algorithms in signal processing using graph models

To reduce computation time in a multiprocessor environment the efficient configuration and utilization of hardware components is necessary. It requires both a restructuring of the considered algorithms and a reconfiguration of the corresponding machine architectures. A transformation system is presented, which uses computation graphs as a representation of both the algorithmic structure and the processor configuration. The system is able to rewrite the computation graph automatically, dependent on the available hardware resources. In this paper the design strategy for algorithms and machine models is illustrated by the DFT. Several models for the algorithm are discussed. Finally the results of time and hardware complexity with regard to the different graph structures and machine architectures are presented.