Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Applied Mathematics
Asymptotically Tight Bounds For Performing Bmmc Permutations On Parallel Disk Systems, Thomas H. Cormen, Thomas Sundquist, Leonard F. Wisniewski
Asymptotically Tight Bounds For Performing Bmmc Permutations On Parallel Disk Systems, Thomas H. Cormen, Thomas Sundquist, Leonard F. Wisniewski
Dartmouth Scholarship
This paper presents asymptotically equal lower and upper bounds for the number of parallel I/O operations required to perform bit-matrix-multiply/complement (BMMC) permutations on the Parallel Disk Model proposed by Vitter and Shriver. A BMMC permutation maps a source index to a target index by an affine transformation over GF(2), where the source and target indices are treated as bit vectors. The class of BMMC permutations includes many common permutations, such as matrix transposition (when dimensions are powers of 2), bit-reversal permutations, vector-reversal permutations, hypercube permutations, matrix reblocking, Gray-code permutations, and inverse Gray-code permutations. The upper bound improves upon the asymptotic …