The Vesta parallel file system is designed to provide parallel file access to application programs running on multicomputers with parallel I/O subsystems. Vesta uses a new abstraction of files: a file is not a sequence of bytes, but rather it can be partitioned into multiple disjoint sequences that are accessed in parallel. The partitioning—which can also be changed dynamically—reduces the need for synchronization and coordination during the access. Some control over the layout of data is also provided, so the layout can be matched with the anticipated access patterns. The system is fully implemented and forms the basis for the AIX Parallel I/O File System on the IBM SP2. The implementation does not compromise scalability or parallelism. In fact, all data accesses are done directly to the I/O node that contains the requested data, without any indirection or access to shared metadata. Disk mapping and caching functions are confined to each I/O node, so there is no need to keep data coherent across nodes. Performance measurements shown good scalability with increased resources. Moreover, different access patterns are show to achieve similar performance.

The Vesta parallel file system is intended to solve the I/O problems of massively parallel multicomputers executing numerically intensive scientific applications. It provides parallel access from the applications to files distributed across multiple storage nodes in the multicomputer, thereby exposing an opportunity for high-bandwidth data transfer across the multicomputer's low-latency network. The Vesta interface provides a user-defined parallel view of file data, which gives users some control over the layout of data. This is useful for tailoring data layout to much common access patterns. The interface also allows user-defined partitioning and repartitioning of files without moving data among storage nodes. Libraries with higher-level interfaces that hide the layout details, while exploiting the power of parallel access, may be implemented above the basic interface. It is shown how collective I/O operations can be implemented, and six parallel access modes to Vesta files are defined. Each mode has unique characteristics in terms of how the processes share the file and how their accesses are interleaved. The combination of user-defined file partitioning and the six access modes gives users very versatile parallel file access.

Rotator graphs, a set of directed permutation graphs, are proposed as an alternative to star and pancake graphs. Rotator graphs are defined in a way similar to the recently proposed Faber-Moore graphs. They have smaller diameter, n-1 in a graph with n factorial vertices, than either the star or pancake graphs or the k-ary n-cubes. A simple optimal routing algorithm is presented for rotator graphs. The n-rotator graphs are defined as a subset of all rotator graphs. The distribution of distances of vertices in the n-rotator graphs is presented, and the average distance between vertices is found. The n-rotator graphs are shown to be optimally fault tolerant and maximally one-step fault diagnosable. The n-rotator graphs are shown to be Hamiltonian, and an algorithm for finding a Hamiltonian circuit in the graphs is given.>

A sorting algorithm, dubbed MeshSort, for multidimensional mesh-connected multiprocessors is introduced. Bitonic Sort and ShearSort are shown to be special cases of MeshSort. MeshSort thus provides some insight into the operation of parallel sorting. It requires operations only along orthogonal vectors of processors, simplifying the control of the multiprocessor. This allows MeshSort to be used on any reduced architecture where a multidimensional memory structure is interconnected with a lower dimensional structure of processors. A modified version of MeshSort, called FastMeshSort, is presented. This algorithm applies the same basic principle as MeshSort, and is almost as simple to implement, but achieves much better performance. The modified algorithm is shown to be very efficient for reasonably sized meshes. FastMeshSort is presented as a practical sorting and routing algorithm for real multidimensional mesh-connected multiprocessors. The algorithms can easily be extended to other multiprocessor structures.>

The shuffle-exchange network can be generalized by the definition of three parameters (n, r', k). In a generalized shuffle-exchange (GSE) network, 2/sup n/ inputs are first permuted by a shuffle such that an n-bit source address label is rotated left r'-bit positions to yield the destination address label. The exchange performs arbitrary permutations on 2/sup k/*2/sup k/ exchange switches. The GSE networks can emulate a variety of other networks, including orthogonally connected multidimensional cubes of all sizes, and they provide the possibility of incorporating alternate paths into networks without the addition of extra processing nodes or interconnections. Generalized shuffle-exchange networks are characterized herein by their connectivity, their diameter, and the number of alternate paths they permit.>