Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems (Extended Abstract)

We give asymptotically equal lower and upper bounds for the number of parallel I/O operations required to perform BMMC permutations (defined by a characteristic matrix that is nonsingular over GF (2)) on parallel disk systems. Under the Vitter-Shriver parallel-disk model with N records, D disks, block size B, and M records of RAM, we show a universal lower bound of\Omega \Gamma N BD \Gamma 1 + rank(fl) lg(M=B) \Delta \Delta parallel I/Os for performing a BMMC permutation, where fl is the lower left lg(N=B) \Theta lg B submatrix of the characteristic matrix. We adapt this lower bound to show that the algorithm for BPC permutations in [Cor93] is asymptotically optimal. We also present an algorithm that uses at most 2N BD \Gamma 6 \Sigma rank(fl) lg(M=B) \Upsilon + 5 \Delta parallel I/Os, which asymptotically matches the lower bound and improves upon the BMMC..