Parallel I/O

Large parallel computing systems, especially those used for scientific computation, consume and produce huge amounts of data. To provide the necessary semantics for parallel processes accessing a file, and to provide the necessary throughput for an application working with terabytes of data, requires a multiprocessor file system.

We created an on-line bibliography of parallel I/O papers. This annotated bibliography helped many new researchers learn about and begin research in the area of parallel I/O.

We also created a detailed simulation model of the HP 97560 disk drive; see the [technical report] and the [software].

Archive

We created the 'Parallel I/O Archive', gathering material related to parallel I/O, including the above-mentioned bibliography of parallel I/O papers. That archive has not been updated in over a decade, but is reproduced here for reference.

Funding and acknowledgements

The papers reported here were created as part of one or more other projects, each of which had its own source(s) of funding. For more information, see those project pages: Armada, CHARISMA, Galley, RAPID-Transit, and STARFISH.

People

The following people are co-author on one or more of the papers listed below (see the related projects for others involved in my parallel-I/O research): Charles Catlett, Alok Choudhary, C. Connelly, Thomas H. Cormen, C. Ellis, M. Holliday, Ravi Jain, V. Khera, David Kotz, R. LaRowe, Ron Oldfield, S. Owen, Sriram Radhakrishnan, Daniel A. Reed, Marc Snir, Song Bac Toh, and Darren Erik Vengroff.

Papers (tagged 'pario')

The papers here are those that did not clearly fit with one of the named projects listed above. This list is also available in BibTeX.

Papers are listed in reverse-chronological order; click an entry to pop up the abstract. For full information and pdf, please click Details link. Follow updates with RSS.

2004:

Darren Erik Vengroff and David Kotz. A Holesome File System. Technical Report, May 2004. Originally written in July 1995; released May 2004. [Details]

We present a novel approach to fully dynamic management of physical disk blocks in Unix file systems. By adding a single system call, zero(), to an existing file system, we permit applications to create holes, that is, regions of files to which no physical disk blocks are allocated, far more flexibly than previously possible. zero can create holes in the middle of existing files.

Using zero(), it is possible to efficiently implement applications including a variety of databases and I/O-efficient computation systems on top of the Unix file system. zero() can also be used to implement an efficient file-system-based paging mechanism. In some I/O-efficient computations, the availability of zero() effectively doubles disk capacity by allowing blocks of temporary files to be reallocated to new files as they are read.

Experiments on a Linux ext2 file system augmented by zero() demonstrate that where their functionality overlaps, zero() is more efficient than ftruncate(). Additional experiments reveal that in exchange for added effective disk capacity, I/O-efficient code pays only a small performance penalty.

2001:

Ron Oldfield and David Kotz. Scientific Applications using Parallel I/O. High Performance Mass Storage and Parallel I/O: Technologies and Applications. September 2001. [Details]

Scientific applications are increasingly being implemented on massively parallel supercomputers. Many of these applications have intense I/O demands, as well as massive computational requirements. This paper is essentially an annotated bibliography of papers and other sources of information about scientific applications using parallel I/O.

2000:

David Kotz. Bibliography about Parallel I/O. BibTeX bibliography, 2000. Original version published 1994. [Details]

A bibliography of many references on parallel I/O and multiprocessor file-systems issues. As of the fifth edition, it is available in HTML format.

1999:

David Kotz and Ravi Jain. I/O in Parallel and Distributed Systems. Encyclopedia of Computer Science and Technology. 1999. Supplement 25. [Details]

We sketch the reasons for the I/O bottleneck in parallel and distributed systems, pointing out that it can be viewed as a special case of a general bottleneck that arises at all levels of the memory hierarchy. We argue that because of its severity, the I/O bottleneck deserves systematic attention at all levels of system design. We then present a survey of the issues raised by the I/O bottleneck in six key areas of parallel and distributed systems: applications, algorithms, languages and compilers, run-time libraries, operating systems, and architecture.

1996:

David Kotz. Introduction to Multiprocessor I/O Architecture. Input/Output in Parallel and Distributed Computer Systems. 1996. [Details]

The computational performance of multiprocessors continues to improve by leaps and bounds, fueled in part by rapid improvements in processor and interconnection technology. I/O performance thus becomes ever more critical, to avoid becoming the bottleneck of system performance. In this paper we provide an introduction to I/O architectural issues in multiprocessors, with a focus on disk subsystems. While we discuss examples from actual architectures and provide pointers to interesting research in the literature, we do not attempt to provide a comprehensive survey. We concentrate on a study of the architectural design issues, and the effects of different design alternatives.

Alok Choudhary and David Kotz. Large-Scale File Systems with the Flexibility of Databases. ACM Computing Surveys. December 1996. Position paper for the Working Group on Storage I/O for Large-Scale Computing, ACM Workshop on Strategic Directions in Computing Research. Available on-line only. [Details]

We note that large-scale computing includes many applications with intensive I/O demands. A data-storage system for such applications must address two issues: locating the appropriate data set, and accessing the contents of the data set. Today, there are two extreme models of data location and management: 1) file systems, which can be fast but which require a user to manage the structure of the file-name space and, often, of the file contents; and 2) object-oriented-database systems, in which even the smallest granule of data is stored as an object with associated access methods, which is very flexible but often slow. We propose a solution that may provide the performance of file systems with the flexibility of object databases.

David Kotz. Applications of Parallel I/O. Technical Report, October 1996. Release 1. [Details]

Joel T. Thomas. The Panda Array I/O Library on the Galley Parallel File System. Technical Report, June 1996. Available as Dartmouth Computer Science Technical Report PCS-TR96-288. [Details]

The Panda Array I/O library, created at the University of Illinois, Urbana-Champaign, was built especially to address the needs of high-performance scientific applications. I/O has been one of the most frustrating bottlenecks to high performance for quite some time, and the Panda project is an attempt to ameliorate this problem while still providing the user with a simple, high-level interface. The Galley File System, with its hierarchical structure of files and strided requests, is another attempt at addressing the performance problem. My project was to redesign the Panda Array library for use on the Galley file system. This project involved porting Panda's three main functions: a checkpoint function for writing a large array periodically for 'safekeeping,' a restart function that would allow a checkpointed file to be read back in, and finally a timestep function that would allow the user to write a group of large arrays several times in a sequence. Panda supports several different distributions in both the compute-node memories and I/O-node disks.

We have found that the Galley File System provides a good environment on which to build high-performance libraries, and that the mesh of Panda and Galley was a successful combination.

David Kotz. Parallel File Systems. A multimedia lecture included in the CD-ROM “Introductory Lectures on Data-Parallel Computing”, published by AK Peters, Ltd., March 1996. [Details]

1995:

Daniel A. Reed, Charles Catlett, Alok Choudhary, David Kotz, and Marc Snir. Parallel I/O: Getting Ready for Prime Time. IEEE Parallel and Distributed Technology. Summer 1995. Edited transcript of panel discussion at the 1994 International Conference on Parallel Processing. [Details]

During the International Conference on Parallel Processing, held August 15-19, 1994, we convened a panel to discuss the state of the art in parallel I/O, tools and techniques to address current problems, and challenges for the future. The following is an edited transcript of that panel.

1994:

David Kotz. HP 97560 disk simulation module. Used in STARFISH and several other research projects, 1994. [Details]

We implemented a detailed model of the HP 97560 disk drive, to replicate a model devised by Ruemmler and Wilkes (both of Hewlett-Packard).

David Kotz, Song Bac Toh, and Sriram Radhakrishnan. A Detailed Simulation Model of the HP 97560 Disk Drive. Technical Report, July 1994. [Details]

We implemented a detailed model of the HP 97560 disk drive, to replicate a model devised by Ruemmler and Wilkes (both of Hewlett-Packard, HP). Our model simulates one or more disk drives attached to one or more SCSI buses, using a small discrete-event simulation module included in our implementation. The design is broken into three components: a test driver, the disk model itself, and the discrete-event simulation support. Thus, the disk model can be easily extracted and used in other simulation environments. We validated our model using traces obtained from HP, using the same “demerit” measure as Ruemmler and Wilkes. We obtained a demerit figure of 3.9%, indicating that our model was extremely accurate. This paper describes our implementation, and is meant for those wishing to understand our model or to implement their own.

1993:

Thomas H. Cormen and David Kotz. Integrating Theory and Practice in Parallel File Systems. Proceedings of the Dartmouth Institute for Advanced Graduate Studies (DAGS). June 1993. Revised as Dartmouth PCS-TR93-188 on 9/20/94. [Details]

Several algorithms for parallel disk systems have appeared in the literature recently, and they are asymptotically optimal in terms of the number of disk accesses. Scalable systems with parallel disks must be able to run these algorithms. We present for the first time a list of capabilities that must be provided by the system to support these optimal algorithms: control over declustering, querying about the configuration, independent I/O, and turning off parity, file caching, and prefetching. We summarize recent theoretical and empirical work that justifies the need for these capabilities. In addition, we sketch an organization for a parallel file interface with low-level primitives and higher-level operations.

David Kotz. Throughput of Existing Multiprocessor File Systems. Technical Report, May 1993. [Details]

Fast file systems are critical for high-performance scientific computing, since many scientific applications have tremendous I/O requirements. Many parallel supercomputers have only recently obtained fully parallel I/O architectures and file systems, which are necessary for scalable I/O performance. Scalability aside, I show here that many systems lack sufficient absolute performance. I do this by surveying the performance reported in the literature, summarized in an informal table.

Thomas H. Cormen and David Kotz. Integrating Theory and Practice in Parallel File Systems. Technical Report, March 1993. Revised 9/20/94. [Details]

Several algorithms for parallel disk systems have appeared in the literature recently, and they are asymptotically optimal in terms of the number of disk accesses. Scalable systems with parallel disks must be able to run these algorithms. We present a list of capabilities that must be provided by the system to support these optimal algorithms: control over declustering, querying about the configuration, independent I/O, turning off file caching and prefetching, and bypassing parity. We summarize recent theoretical and empirical work that justifies the need for these capabilities.

David Kotz. Multiprocessor File System Interfaces. Proceedings of the International Conference on Parallel and Distributed Information Systems (PDIS). January 1993. [Details]

Increasingly, file systems for multiprocessors are designed with parallel access to multiple disks, to keep I/O from becoming a serious bottleneck for parallel applications. Although file system software can transparently provide high-performance access to parallel disks, a new file system interface is needed to facilitate parallel access to a file from a parallel application. We describe the difficulties faced when using the conventional (Unix-like) interface in parallel applications, and then outline ways to extend the conventional interface to provide convenient access to the file for parallel programs, while retaining the traditional interface for programs that have no need for explicitly parallel file access. Our interface includes a single naming scheme, a multiopen operation, local and global file pointers, mapped file pointers, logical records, multifiles, and logical coercion for backward compatibility.

1992:

David Kotz. Multiprocessor File System Interfaces. Proceedings of the USENIX File Systems Workshop (WOFS). May 1992. [Details]

David Kotz. Multiprocessor File System Interfaces. Technical Report, March 1992. [Details]

1991:

C. Ellis, M. Holliday, R. LaRowe, D. Kotz, V. Khera, S. Owen, and C. Connelly. NUMAtic Project and the DUnX OS. IEEE Technical Committee on Operating Systems and Application Environments (Newsletter). Winter 1991. [Details]

Parallel I/O projects (1987-2006)

Summary

Archive

Funding and acknowledgements

People

Papers (tagged 'pario')