Optimal Algorithm for Matrix Transpose on

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, N our algorithm takes communication steps to perform matrix transpose on an N 2+ 2 × 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 N −1 bound is and the best previous bound is about N/3.27. The complexity o