SCALABLE PARALLEL ALGORITHMS FOR MULTIDIMENSIONAL DIGITAL SIGNAL PROCESSING

IN THIS PROGRAM, A STUDY OF THE MAPPING OF A NEW CLASS OF MULTIDIMENSIONAL DISCRETE FOURIER TRANSFORM (MD DFT) ALGORITHMS TO BROADCAST MODE MULTIPROCESSORS IS PROPOSED. THESE ALGORITHMS ARE DESIGNED TO SCALE FROM LIMITED TO MASSIVE DEGREES OF PARALLELISM. CONVENTIONAL APPROACHES MAP VARIATIONS OF ROW-COLUMN OF VECTOR-RADIX ALGORITHMS TO PARLLEL ARCHITECTURES. THESE ALGORITHMS REQUIRE INTENSIVE INTERPROCESSOR ARCHITECTURES. TO OVERCOME THIS DIFFICULTY REDUCED TRANSFORM ALGORITHMS ARE MAPPED TO MULTIPROCESSORS. THIS NEW METHOD APPLIED TO $D-$DIMENSIONAL DFT OF SIZE $P^[N]$ IN EACH DIMENSION, WHERE $P$ IS ANY PRIME INCLUDING 2. THE MAIN FEATURES OF THIS ALGORITHM ARE THAT IT REQUIRES NO INTERPROCESSOR COMMUNICATIONS, AND SCALES TO MATCH THE DEGREE OF PARALLELISM OF ANY MULTIPROCESSOR. THIS STUDY WILL INCLUDE THE DETAILED DEFINITION OF THE MODULES REQUIRED TO REALIZE 2D, 3D, AND 4D IMPLEMENTATIONS OF THE ALGORITHMS. THE MODULES ARE TO BE REALIZABLE IN A HIGH LEVEL LANGUAGE, AND CAN BE RETARGETED TO SPECIFIC IMPLEMENTATION OF MULTIPROCESSORS THAT SUPPORT THE REQUIRED PRIMITIVES.