Algorithms for Matrix Multiplication and the FFT on a Processor Array with Separable Buses

Takashi MAEBA  Mitsuyoshi SUGAYA  Shoji TATSUMI  Ken'ichi ABE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.1   pp.136-140
Publication Date: 2003/01/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithms
Keyword: 
processor array with separable buses,  matrix multiplication,  fast Fourier transform,  parallel algorithm,  area-time complexity,  

Full Text: PDF(273.4KB)>>
Buy this Article




Summary: 
This letter presents parallel algorithms for matrix multiplication and the fast Fourier transform (FFT) that are significant problems arising in engineering and scientific applications. The proposed algorithms are designed on a 3-dimensional processor array with separable buses (PASb). We show that a PASb consisting of N N h processors can compute matrix multiplication of size N N and the FFT of size N in O(N/h+log N) time, respectively. In order to examine ease of hardware implementation, we also evaluate the VLSI complexity of the algorithms. A result obtained achieves an optimal bound on area-time complexity when h=O(N/log N).