23 February 1988 Synchronous And Asynchronous Algorithms For Matrix Transposition On MCAP
Author Affiliations +
Matrix transposition is one of the major tasks in image and signal processing and matrix decompositions. This paper presents algorithms for transposing a matrix on a mesh-connected array processor (MCAP). These algorithms make a very efficient use of the processing elements (PE's) in parallel. We discuss both synchronous and asynchronous algorithms. In the synchronized approach algorithms use a global clock to synchronize the communications between PE's. The number of time units required by synchronous algorithms for transposing an m x n matrix (n ≥ m) on an n x n MCAP is 2(n - 1). The synchronous algorithms eliminate simultaneous requests for using channels between PE's. Clock skews and delays are inevitable problems when we have a large array size (large n). An asynchronous (self-time) approach is proposed to circumvent this problem. The feasibility of the asynchronous algorithm have been demonstrated by the simulation of the algorithm for different sizes of matrices.
© (1988) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Nasser G. Azari, Adam W. Bojanczyk, Soo-Young Lee, "Synchronous And Asynchronous Algorithms For Matrix Transposition On MCAP", Proc. SPIE 0975, Advanced Algorithms and Architectures for Signal Processing III, (23 February 1988); doi: 10.1117/12.948511; https://doi.org/10.1117/12.948511


Numerical Linear Algebra On The CEDAR Multiprocessor
Proceedings of SPIE (January 21 1988)
Super-fast Fourier transform
Proceedings of SPIE (February 16 2006)
A Linear Array For Covariance Differencing Via Hyperbolic SVD
Proceedings of SPIE (November 14 1989)

Back to Top