language: en

Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems

Thomas H. Cormen Thomas Sundquist Leonard F. Wisniewski
Department of Mathematics and Computer Science Dartmouth College

Abstract We give asymptotically equal lower and upper bounds for the number of parallel I/O operations required to perform bit-matrix-multiply/complement (BMMC) permutations on parallel disk systems. In a BMMC permutation on N records, where N is a power of 2, each (lg N )-bit source address x maps to a corresponding (lg N)-bit target address by the matrix equation = A x c, where matrix multiplication is performed over GF (2). The characteristic matrix A is (lg N )fi(lg N ) and nonsingular over GF (2). Under the Vitter-Shriver parallel-disk model with N records, D disks, B records per block, and M records of memory, we show a universal lower bound of BD 1 + rank lg(M=B) parallel I/Os for performing a BMMC permutation, where is the lower left lg(N=B) fi lg B submatrix of the characteristic matrix. We also present an algo rithm that uses at most 2N BD rank lg(M=B) + 2 parallel I/Os, which asymptotically matches the lower bound and improves upon the BMMC and bit-permute/complement (BPC) algorithms in [4]. When rank is low, this method is an improvement over the general-permutation bound of fi N lg(N=B) We introduce a new subclass of BMMC permutations, called memoryload-dispersal (MLD) permutations, which can be performed in one pass. This subclass, which is used in the BMMC algorithm, extends the catalog of one-pass permutations appearing in [4]. Although many BMMC permutations of practical interest fall into subclasses that might be explicitly invoked within the source code, we show how to detect in at most N=BD+ l D parallel I/Os whether a given vector of target addresses specifies a BMMC permutation. Thus, one can determine efficiently at run time whether a permutation to be performed is BMMC and then avoid the general-permutation algorithm and save parallel I/Os by using our algorithm.

1 Introduction