Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]


Journal of Information Science and Engineering, Vol.19 No.1, pp.167-177 (January 2003)

Optimal Algorithm for Matrix Transpose on
Wormhole-Switched Meshes*

Jyh-Jong Tsay, Kuo-Shun Ding+ and Wen-Tsong Wang
Department of Computer Science and Information Engineering
National Chung Cheng University
Chiayi, 621 Taiwan
+Department of Information Management
Wu-Feng Institute of Technology
Chiayi, 621 Taiwan

The mesh is an architecture that has many scientific applications, and matrix transpose is an important permutation frequently performed in various techniques involving systems of linear equations. In this paper, we present an optimal algorithm for performing matrix transpose on meshes that support wormhole switching. If N is even, our algorithm takes communication steps to perform matrix transpose on an N ? N mesh and requires only 3 more steps when the routing is restricted to XY routing, which is supported by most commercial mesh-connected parallel computers. The lower bound is and the best previous bound is about N/3.27. The complexity of our algorithm almost matches the lower bound. Furthermore, our algorithm is simple and can be implemented on current mesh-connected parallel computers.

Keywords: consecutive-k-n matrix transpose, collective communication, mesh-connected computers, wormhole routing, parallel computing

Full Text () Retrieve PDF document (200301_10.pdf)

Received March 15, 2001; revised September 5 & October 23, 2001; accepted December 25, 2001.
Communicated by Gen-Huey Chen.
* Reserach partially supported by the ROC National Science Council under Contract NSC85-2213-E-194-021.