ACM Computing Surveys 28A(4), December 1996, http://www.cs.duke.edu/~jsv/SDCR96-IO/VengroffVitterIO/. Copyright © 1996 by the Association for Computing Machinery, Inc. See the permissions statement below.

Darren Erik Vengroff
Department of Electrical Engineering, University of Delaware
Evans Hall, Newark, DE 19716, USA
vengroff@ee.udel.edu, http://www.ee.udel.edu/~vengroff/

Jeffrey Scott Vitter

---

Abstract: There has recently been much productive work in the algorithms community on techniques for efficient use of external memory in large-scale applications. In order for I/O-optimal algorithms to be implemented efficiently, the machines that they run on must support fundamental external-memory operations. Unfortunately, existing file systems generally do not support the necessary semantics or provide useful tools. There are three basic approaches to supporting development of I/O-efficient code, which we call array-oriented systems (such as PASSION and ViC*), access-oriented systems (such as the UNIX file system and Panda), and framework-oriented systems (such as TPIE, a Transparent Parallel I/O Programming Environment). In the full position statement, we discuss the advantages and potential of the TPIE approach in enabling I/O-efficient computation.

Categories and Subject Descriptors: D.4.2 [Operating Systems]: Storage Management - Secondary Storage; D.4.4 [Operating Systems]: Communications Management - Input/Output; E.2 [Data Storage Representations]: Contiguous representations; E.5 [Files]: Sorting/searching; F.2.1 [Analysis of Algorithms and Problem Complexity: Numerical Algorithms and Problems - Computations on matrices; F.2.2 [Analysis of Algorithms and Problem Complexity: Nonnumerical Algorithms and Problems - Computations on discrete structures, geometrical problems and computations, sorting and searching; B.4.4 [Input/Output and Data Communications: Performance Analysis and Design Aids] - Formal models, Worst-case analysis;

General Terms: Algorithms, Design, Languages, Performance, Theory.

Additional Key Words and Phrases: I/O, external memory, secondary memory, communication, disk drive, parallel disks, sorting.

---

Publication Information

Citation

Vengroff, D. E., and Vitter, J. S., 1996. I/O-Efficient Algorithms and Environments, Strategic Directions in Computing Research: Working Group on Storage I/O for Large-Scale Computing, ACM Computing Surveys, 28A(4), December 1996, http://www.cs.duke.edu/~jsv/SDCR96-IO/VengroffVitterIO/.

Submission date

June 14, 1996

Revision date (if any)

October 31, 1996

Acceptance date

October 31, 1996

Publication Sources

• HTML (of full position statement).

Auxiliary Information

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.