About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
Matrix transpose on meshes with wormhole and XY routing
Abstract
We give nearly optimal algorithms for matrix transpose on meshes with wormhole and XY routing and with a 1-port or 2-port communication model. For an N x N mesh, where N = 3 · 2n and each mesh node has a submatrix of size m to be transposed, our best algorithm takes about Nm/3.27 time steps. The lower bound is Nm/3.414. While there is no previously known algorithm for matrix transpose on meshes with wormhole and XY routing, a naive algorithm, which is naturally adapted from the well-known Recursive Exchange Algorithm, has a complexity of about Nm. That is our best algorithm improves over the naive algorithm by about a factor of 3.27, and is about a factor of 3.414/3.27 of the lower bound. © 1998 Elsevier Science B.V. All rights reserved.