MULTIPROCESSOR IMPLEMENTATION MODELS FOR ADAPTIVE ALGORITHMS

This paper addresses the problem of implementing adaptive algorithms o n parallel MIMD message-passing computers using a small number of digi tal signal processors, First, we evaluate the maximal speedup obtained by an ideal machine without resources restriction but taking into acc ount interprocessor communications, This estimation is based on the si gnal flow graph of the algorithm and a description of the parameters o f the target architecture, Explicit expressions are obtained and criti cal tasks are detected, thus allowing a fast and easy evaluation of th e influence of implementation parameters, Next, we propose some techni ques to enhance the intrinsic parallelism of iterative algorithms usin g our models. An algorithm is given to find an implementation achievin g maximal speedup and using a small number of processors, Then, an opt imal intercommunication network is obtained and some techniques are gi ven to reduce the number of point-to-point links between processors wi thout affecting the speedup, Finally, if the optimal network cannot be constructed because of an excessive number of links, we propose an al location method to minimize the performance degradation introduced by the use of a fixed arbitrary communication network.