Matrix transpose on meshes with buses

• We analyze the matrix transpose problem for 2- and 3-dimensional mesh architectures with row- and column-buses.
• We give a lower bound of approximately 0.45n for the number of steps required by any matrix transpose algorithm on an n x n mesh with buses.
• We present an algorithm which solves this problem in less than 0.5n+90.5n+9 steps.

In this paper we analyze the matrix transpose problem for 2- and 3-dimensional mesh architectures with row and column buses. First we consider the 2-dimensional problem, and we give a lower bound of approximately 0.45n0.45n for the number of steps required by any matrix transpose algorithm on an n×nn×n mesh with buses. Next we present an algorithm which solves this problem in less than 0.5n+90.5n+9 steps. Finally, we prove that the given lower bound remains valid for the 3-dimensional case as well.