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

¡@

Optimal Algorithm for Matrix Transpose on

Wormhole-Switched Meshes

**Jyh-Jong Tsay, Kuo-Shun Ding ^{+} and Wen-Tsong Wang**

National Chung Cheng University

Chiayi, 621 Taiwan

E-mail: tsay@cs.ccu.edu.tw

Wu-Feng Institute of Technology

Chiayi, 621 Taiwan

E-mail: dks@mail.wfc.edu.tw

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-

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.