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, Nasser G. Azari, Adam W. Bojanczyk, Adam W. Bojanczyk, Soo-Young Lee, 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


Back to Top