The RAPID-Transit Project (1987-1991)

David Kotz and Carla Ellis, Duke University

RAPID-Transitwas a testbed for experimenting with caching and
prefetching algorithms in parallel file systems (RAPID means
"Read-Ahead for Parallel Independent Disks"), and was part of the
larger NUMAtic project at Duke University.  The testbed ran on Duke's
64-processor Butterfly GP1000.  The model we used had a disk attached
to every processor, and that each file was striped across all disks.
Of course, Duke's GP1000 had only one real disk, so our testbed
simulated its disks.  The implementation and some of the policies were
dependent on the shared-memory nature of the machine; for example,
there was a single shared file cache accessible to all processors.  We
found several policies that were successful at prefetching in a
variety of parallel file-access patterns.

This directory contains source code, configuration scripts, scripts to
run tests, etc.  I supply it AS-IS, and can't offer much support for
anyone trying to use it.  

David Kotz
dfk@cs.dartmouth.edu
December 1994

http://www.cs.dartmouth.edu/research/rapid-transit.html


There are several papers describing this research:

@InProceedings{ellis:prefetch,
  author = {Carla Schlatter Ellis and David Kotz},
  title = {Prefetching in File Systems for {MIMD} Multiprocessors},
  booktitle = {Proceedings of the 1989 International Conference on Parallel
  Processing},
  year = {1989},
  month = {August},
  pages = {I:306--314},
  URL = {http://www.cs.dartmouth.edu/papers/Kotz/ellis_prefetch.html},
  keyword = {dfk, parallel file system, prefetching, disk caching, MIMD,
  parallel I/O, pario bib},
  abstract = {The problem of providing file I/O to parallel programs has been
  largely neglected in the development of multiprocessor systems. There are two
  essential elements of any file system design intended for a highly parallel
  environment: parallel I/O and effective caching schemes. This paper
  concentrates on the second aspect of file system design and specifically, on
  the question of whether prefetching blocks of the file into the block cache
  can effectively reduce overall execution time of a parallel computation, even
  under favorable assumptions. Experiments have been conducted with an
  interleaved file system testbed on the Butterfly Plus multiprocessor. Results
  of these experiments suggest that 1) the hit ratio, the accepted measure in
  traditional caching studies, may not be an adequate measure of performance
  when the workload consists of parallel computations and parallel file access
  patterns, 2) caching with prefetching can significantly improve the hit ratio
  and the average time to perform an I/O operation, and 3) an improvement in
  overall execution time has been observed in most cases. In spite of these
  gains, prefetching sometimes results in increased execution times (a negative
  result, given the optimistic nature of the study). We explore why is it not
  trivial to translate savings on individual I/O requests into consistently
  better overall performance and identify the key problems that need to be
  addressed in order to improve the potential of prefetching techniques in this
  environment.},
  comment = {Superseded by kotz:prefetch.}
}

@TechReport{kotz:fsint,
  author = {David Kotz},
  title = {Multiprocessor File System Interfaces},
  year = {1992},
  month = {March},
  number = {PCS-TR92-179},
  institution = {Dept. of Math and Computer Science, Dartmouth College},
  note = {Revised version appeared in PDIS'93.},
  URL = {file://cs.dartmouth.edu/pub/CS-techreports/TR92-179.ps.Z},
  keyword = {dfk, parallel I/O, multiprocessor file system, file system
  interface, pario bib},
  abstract = {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 {\em multiopen\/} operation, local and
  global file pointers, mapped file pointers, logical records, {\em
  multifiles}, and logical coercion for backward compatibility.},
  comment = {Cite kotz:fsint2. See also lake:pario for implementation of some
  of the ideas.}
}

@InProceedings{kotz:fsint2,
  author = {David Kotz},
  title = {Multiprocessor File System Interfaces},
  booktitle = {Proceedings of the Second International Conference on Parallel
  and Distributed Information Systems},
  year = {1993},
  pages = {194--201},
  URL = {file://cs.dartmouth.edu/pub/CS-papers/Kotz/kotz:fsint2.ps.Z},
  keyword = {dfk, parallel I/O, multiprocessor file system, file system
  interface, pario bib},
  abstract = {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 {\em multiopen\/} operation, local and
  global file pointers, mapped file pointers, logical records, {\em
  multifiles}, and logical coercion for backward compatibility.},
  comment = {See also lake:pario for implementation of some of the ideas.}
}

@InProceedings{kotz:fsint2p,
  author = {David Kotz},
  title = {Multiprocessor File System Interfaces},
  booktitle = {Proceedings of the USENIX File Systems Workshop},
  year = {1992},
  month = {May},
  pages = {149--150},
  keyword = {dfk, parallel I/O, multiprocessor file system, file system
  interface, pario bib},
  comment = {Short paper (2 pages). See kotz:fsint2.}
}

@Article{kotz:jpractical,
  author = {David Kotz and Carla Schlatter Ellis},
  title = {Practical Prefetching Techniques for Multiprocessor File Systems},
  journal = {Journal of Distributed and Parallel Databases},
  year = {1993},
  month = {January},
  volume = {1},
  number = {1},
  pages = {33--51},
  URL = {http://www.cs.dartmouth.edu/papers/Kotz/jpractical.html},
  keyword = {dfk, parallel file system, prefetching, disk caching, parallel
  I/O, MIMD, pario bib},
  abstract = {Improvements in the processing speed of multiprocessors are
  outpacing improvements in the speed of disk hardware. Parallel disk I/O
  subsystems have been proposed as one way to close the gap between processor
  and disk speeds. In a previous paper we showed that prefetching and caching
  have the potential to deliver the performance benefits of parallel file
  systems to parallel applications. In this paper we describe experiments with
  practical prefetching policies that base decisions only on on-line reference
  history, and that can be implemented efficiently. We also test the ability of
  these policies across a range of architectural parameters.},
  comment = {Journal version of kotz:practical. See also kotz:jwriteback,
  kotz:fsint2, cormen:integrate.}
}

@Article{kotz:jwriteback,
  author = {David Kotz and Carla Schlatter Ellis},
  title = {Caching and Writeback Policies in Parallel File Systems},
  journal = {Journal of Parallel and Distributed Computing},
  year = {1993},
  month = {January and February},
  volume = {17},
  number = {1--2},
  pages = {140--145},
  URL = {file://cs.dartmouth.edu/pub/CS-papers/Kotz/kotz:jwriteback.ps.Z},
  keyword = {dfk, parallel file system, disk caching, parallel I/O, MIMD, pario
  bib},
  abstract = {Improvements in the processing speed of multiprocessors are
  outpacing improvements in the speed of disk hardware. Parallel disk I/O
  subsystems have been proposed as one way to close the gap between processor
  and disk speeds. Such parallel disk systems require parallel file system
  software to avoid performance-limiting bottlenecks. We discuss cache
  management techniques that can be used in a parallel file system
  implementation for multiprocessors with scientific workloads. We examine
  several writeback policies, and give results of experiments that test their
  performance.},
  comment = {Journal version of kotz:writeback. See kotz:jpractical,
  kotz:fsint2, cormen:integrate.}
}

@InProceedings{kotz:practical,
  author = {David Kotz and Carla Schlatter Ellis},
  title = {Practical Prefetching Techniques for Parallel File Systems},
  booktitle = {Proceedings of the First International Conference on Parallel
  and Distributed Information Systems},
  year = {1991},
  month = {December},
  pages = {182--189},
  URL = {file://cs.dartmouth.edu/pub/CS-papers/Kotz/kotz:practical.ps.Z},
  keyword = {dfk, parallel file system, prefetching, disk caching, parallel
  I/O, MIMD, OS93W extra, OS92W, pario bib},
  abstract = {Parallel disk subsystems have been proposed as one way to close
  the gap between processor and disk speeds. In a previous paper we showed that
  prefetching and caching have the potential to deliver the performance
  benefits of parallel file systems to parallel applications. In this paper we
  describe experiments with practical prefetching policies, and show that
  prefetching can be implemented efficiently even for the more complex parallel
  file access patterns. We test these policies across a range of architectural
  parameters.},
  comment = {Short form of primary thesis results. Cite kotz:jpractical. See
  kotz:jwriteback, kotz:fsint2, cormen:integrate.}
}

@Article{kotz:prefetch,
  author = {David Kotz and Carla Schlatter Ellis},
  title = {Prefetching in File Systems for {MIMD} Multiprocessors},
  journal = {IEEE Transactions on Parallel and Distributed Systems},
  year = {1990},
  month = {April},
  volume = {1},
  number = {2},
  pages = {218--230},
  URL = {http://www.cs.dartmouth.edu/papers/Kotz/prefetch.html},
  keyword = {dfk, parallel file system, prefetching, MIMD, disk caching,
  parallel I/O, pario bib},
  abstract = {The problem of providing file I/O to parallel programs has been
  largely neglected in the development of multiprocessor systems. There are two
  essential elements of any file system design intended for a highly parallel
  environment: parallel I/O and effective caching schemes. This paper
  concentrates on the second aspect of file system design and specifically, on
  the question of whether prefetching blocks of the file into the block cache
  can effectively reduce overall execution time of a parallel computation, even
  under favorable assumptions. Experiments have been conducted with an
  interleaved file system testbed on the Butterfly Plus multiprocessor. Results
  of these experiments suggest that 1) the hit ratio, the accepted measure in
  traditional caching studies, may not be an adequate measure of performance
  when the workload consists of parallel computations and parallel file access
  patterns, 2) caching with prefetching can significantly improve the hit ratio
  and the average time to perform an I/O operation, and 3) an improvement in
  overall execution time has been observed in most cases. In spite of these
  gains, prefetching sometimes results in increased execution times (a negative
  result, given the optimistic nature of the study). We explore why is it not
  trivial to translate savings on individual I/O requests into consistently
  better overall performance and identify the key problems that need to be
  addressed in order to improve the potential of prefetching techniques in this
  environment.}
}

@PhdThesis{kotz:thesis,
  author = {David Kotz},
  title = {Prefetching and Caching Techniques in File Systems for {MIMD}
  Multiprocessors},
  year = {1991},
  month = {April},
  school = {Duke University},
  note = {Available as technical report CS-1991-016.},
  URL = {file://cs.duke.edu/dist/theses/kotz/kotz.ps.Z},
  keyword = {dfk, parallel file system, prefetching, MIMD, disk caching,
  parallel I/O, pario bib},
  abstract = {The increasing speed of the most powerful computers, especially
  multiprocessors, makes it difficult to provide sufficient I/O bandwidth to
  keep them running at full speed for the largest problems. Trends show that
  the difference in the speed of disk hardware and the speed of processors is
  increasing, with I/O severely limiting the performance of otherwise fast
  machines. This widening access-time gap is known as the ``I/O bottleneck
  crisis.'' One solution to the crisis, suggested by many researchers, is to
  use many disks in parallel to increase the overall bandwidth. This
  dissertation studies some of the file system issues needed to get high
  performance from parallel disk systems, since parallel hardware alone cannot
  guarantee good performance. The target systems are large MIMD multiprocessors
  used for scientific applications, with large files spread over multiple disks
  attached in parallel. The focus is on automatic caching and prefetching
  techniques. We show that caching and prefetching can transparently provide
  the power of parallel disk hardware to both sequential and parallel
  applications using a conventional file system interface. We also propose a
  new file system interface (compatible with the conventional interface) that
  could make it easier to use parallel disks effectively. Our methodology is a
  mixture of implementation and simulation, using a software testbed that we
  built to run on a BBN GP1000 multiprocessor. The testbed simulates the disks
  and fully implements the caching and prefetching policies. Using a synthetic
  workload as input, we use the testbed in an extensive set of experiments. The
  results show that prefetching and caching improved the performance of
  parallel file systems, often dramatically.},
  comment = {Published as kotz:prefetch, kotz:jwriteback, kotz:jpractical,
  kotz:fsint2.}
}

@InProceedings{kotz:writeback,
  author = {David Kotz and Carla Schlatter Ellis},
  title = {Caching and Writeback Policies in Parallel File Systems},
  booktitle = {1991 IEEE Symposium on Parallel and Distributed Processing},
  year = {1991},
  month = {December},
  pages = {60--67},
  URL = {file://cs.dartmouth.edu/pub/CS-papers/Kotz/kotz:writeback.ps.Z},
  keyword = {dfk, parallel file system, disk caching, parallel I/O, MIMD, pario
  bib},
  abstract = {Improvements in the processing speed of multiprocessors are
  outpacing improvements in the speed of disk hardware. Parallel disk I/O
  subsystems have been proposed as one way to close the gap between processor
  and disk speeds. Such parallel disk systems require parallel file system
  software to avoid performance-limiting bottlenecks. We discuss cache
  management techniques that can be used in a parallel file system
  implementation. We examine several writeback policies, and give results of
  experiments that test their performance.},
  comment = {Cite kotz:jwriteback. See also kotz:jpractical, kotz:fsint2,
  cormen:integrate.}
}