The standard binary reflected Gray code produces a permutation of the sequence of integers (0, 1,..., n - 1), where n is a power of 2, such that the binary representation of each integer in the permuted sequence differs from the binary representation of the preceding integer in exactly one bit. In an earlier paper, we presented two methods to compute binary dense Gray codes, which extend the possible values of n to the set of all positive integers while preserving both the Gray-code property - only one bit changes between each pair of consecutive integers - and the denseness property - the sequence contains exactly the n integers 0 to n - 1. This paper generalizes our method for binary dense Gray codes to arbitrary radices that may be either a single fixed radix for all digits or mixed radices, so that each digit may have a different radix. That is, we show how to produce a permutation of (0, 1, ..., n-1) represented in any set of radices, such that the representation of each number differs from the representation of the preceding number in exactly one digit, and the values of these digits differ by exactly 1. We provide a simple formula for this permuation, which we can use to quickly compute a Hamiltonian path for a dynamic array of n nodes, where the nodes are added and deleted in order along the k dimensions of a grid network.

Previous implementations of out-of-core columnsort limit the problem size to N ≤(M/P)3/2, where N is the number of records to sort, P is the number of processors, and M is the total number of records that the entire system can hold in its memory. We implemented two variations to out-of-core columnsort that relax this restriction. Subblock columnsort is based on an algorithmic modification of the underlying columnsort algorithm, and it improves the problem-size bound to N ≤(M/P)5/3 / 42/3 but at the cost of additional disk I/O. M-columnsort changes the notion of the column size in columnsort, improving the maximum problem size to N ≤M3 / 2 but at the cost of additional computation and communication. Experimental results on a Beowulf cluster show that both subblock columnsort and M-columnsort run well but that M-columnsort is faster. A further advantage of M-columnsort is that it handles a wider range of problem sizes than subblock columnsort.

We present the design and implementation of a parallel out-of-core sorting algorithm, which is based on Leighton's columnsort algorithm. We show how to relax some of the steps of the original columnsort algorithm to permit a faster out-of-core implementation. Our algorithm requires only 4 passes over the data, and a 3-pass implementation is possible. Although there is a limit on the number of records that can be sorted---as a function of the memory used per processor---this upper limit need not be a severe restriction, and it increases superlinearly with the per-processor memory. To the best of our knowledge, our implementation is the first out-of-core multiprocessor sorting algorithm whose output is in the order assumed by the Parallel Disk Model. We define several measures of sorting efficiency and demonstrate that our implementation's sorting efficiency is competitive with that of NOW-Sort, a sorting algorithm developed to sort large amounts of data quickly on a cluster of workstations.

We show how to compute multidimensional Fast Fourier Transforms (FITS) on a multiprocessor system with distributed memory when problem sizes are so large that the data do not fit in the memory of the entire system.Instead, data reside on a parallel disk system and are brought into memory in sections.We use the Parallel Disk Model for implementation and analysis.Our method is a straightforward out-of-core variant of a wellknown method for in-core, multidimensional FFTs.It performs l-dimensional FIT computations on each dimension in turn.This method is easy to generalize to any number of dimensions, and it also readily permits the individual dimensions to be of any sizes that are integer powers of 2. The key step is an out-of-core transpose operation that places the data along each dimension into contiguous positions on the parallel disk system so that the data for the l-dimensional FFTs are contiguous.We present an I/O complexity analysis for 'this method as well as empirical results for a DEC 2100 server, an SGI Origin 2000, and a Beowulf cluster, each of which has a parallel disk system.

The paper describes the functionality of ViC*, a compiler for a variant of the data parallel language C* with support for out-of-core data. The compiler translates C* programs with shapes declared out of core, which describe parallel data stored on disk. The compiler output is a SPMD style program in standard C with I/O and library calls added to efficiently access out-of-core parallel data. The ViC* compiler also applies several program transformations to improve out-of-core data access.

The Fast Fourier Transform (FFT) plays a key role in many areas of computational science and engineering. Although most one-dimensional FFT problems can be solved entirely in main memory, some important classes of applications require out-of-core techniques. For these, use of parallel I/O systems can improve performance considerably. This paper shows how to perform one-dimensional FFTs using a parallel disk system with independent disk accesses. We present both analytical and experimental results for performing out-of-core FFTs in two ways: using traditional virtual memory with demand paging, and using a provably asymptotically optimal algorithm for the Parallel Disk Model (PDM) of Vitter and Shriver. When run on a DEC 2100 server with a large memory and eight parallel disks, the optimal algorithm for the PDM runs up to 144.7 times faster than in-core methods under demand paging. Moreover, even including I/O costs, the normalized times for the optimal PDM algorithm are competitive, or better than, those for in-core methods even when they run entirely in memory.

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 bound in the previous best known BMMC algorithm and upon the constant factor in the previous best known bit-permute/complement (BPC) permutation algorithm. The algorithm achieving the upper bound uses basic linear-algebra techniques to factor the characteristic matrix for the BMMC permutation into a product of factors, each of which characterizes a permutation that can be performed in one pass over the data. The factoring uses new subclasses of BMMC permutations: memoryload-dispersal (MLD) permutations and their inverses. These subclasses extend the catalog of one-pass permutations. Although many BMMC permutations of practical interest fall into subclasses that might be explicitly invoked within the source code, this paper shows how to quickly detect 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 the BMMC permutation algorithm herein.

Although several algorithms have been developed for the Parallel Disk Model (PDM), few have been implemented. Consequently, little has been known about the accuracy of the PDM in measuring I/O time and total running time to perform an out-of-core computation. This paper analyzes timing results on multiple-disk platforms for two PDM algorithms, out-of-core radix sort and BMMC permutations, to determine the strengths and weaknesses of the PDM. The results indicate the following. First, good PDM algorithms are usually not I/O bound. Second, of the four PDM parameters, one (problem size) is a good indicator of I/O time and running time, one (memory size) is a good indicator of I/O time but not necessarily running time, and the other two (block size and number of disks) do not necessarily indicate either I/O or running time. Third, because PDM algorithms tend not to be I/O bound, using asynchronous I/O can reduce I/O wait times significantly. The software interface to the PDM is part of the ViC ∗ run-time library. The interface is a set of wrappers that are designed to be both efficient and portable across several underlying file systems and target machines.

We implemented and measured several BMMC permutations on the MasPar methods to perform MP-2.Our results indicate that, except for certain types of permutations or very high virtual processor ratios, the best method overall is the naive method but with virtual-processor numbers computed in Gray-code order.For some permutations, however, the naive method performs very poorly; the best method in these cases is an adaptation of the block BMMC algorithm for parallel disk systems in which the processor elements are treated as independent devices. 1

Article Free Access Share on Asymptotically tight bounds for performing BMMC permutations on parallel disk systems Authors: Thomas H. Cormen View Profile , Leonard F. Wisniewski View Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 130–139https://doi.org/10.1145/165231.165248Published:01 August 1993Publication History 6citation177DownloadsMetricsTotal Citations6Total Downloads177Last 12 Months14Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present fast algorithms to accomplish common classes of permutations on parallel disk systems. Vitter and Shriver introduced a parallel I/O model and proved an asymptotically tight bound on the number of parallel I/Os needed to perform a general permutation. They demonstrated, however, that at least one type of permutation-matrix transpose-can be performed with fewer parallel I/Os than the lower bound for general permutations. This paper generalizes the Vitter-Shriver matrix-transpose result, showing that other classes of permutations can be performed with fewer parallel I/Os than the general permutation bound in many cases. We show how to perform bit-permute/complement (BPC) permutations, a class including matrix transpose and many other common permutations, with fewer parallel I/Os than general permutations. We also present a fast algorithm to perform bit-matrix-multiply/complement (BMMC) permutations. The algorithms for these permutations are built from restricted classes of permutations that we define, each requiring only one pass over the data. All the permutation algorithms presented in this paper are deterministic and are easily performed on-line.