Method for performing matrix transposition on a mesh multiprocessor architecture having multiple processor with concurrent execution of the multiple processors

摘要

A matrix transpose method for transposing any size matrix on a 2-dimensional mesh multi-node system with circuit-switched-like routing in the iterative and recursive forms. The matrix transpose method involves a two-level decomposition technique of first partitioning each mesh on a diagonal axis into four submeshes and then further partitioning each of the four submeshes on the diagonal axis into four submeshes. The transposition of all off-diagonal submatrices can be performed concurrently and the transposition of all successive on-diagonal submatrices can be performed iteratively or recursively.