BibTeX for papers by David Kotz; for complete/updated list see https://www.cs.dartmouth.edu/~kotz/research/papers.html @InCollection{kotz:bpractical, author = {David Kotz and Carla Schlatter Ellis}, title = {{Practical Prefetching Techniques for Multiprocessor File Systems}}, booktitle = {{High Performance Mass Storage and Parallel I/O: Technologies and Applications}}, editor = {Hai Jin and Toni Cortes and Rajkumar Buyya}, year = 2001, month = {September}, chapter = 17, pages = {245--258}, publisher = {Wiley-IEEE Press}, copyright = {Wiley-IEEE Press}, ISBN13 = {978-0-471-20809-9}, address = {New York, NY}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-bpractical/index.html}, 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.}, } @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}, publisher = {Kluwer Academic Publishers}, copyright = {Kluwer Academic Publishers}, DOI = {10.1007/BF01277519}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-jpractical/index.html}, 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.}, } @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}, volume = 17, number = {1--2}, pages = {140--145}, publisher = {Academic Press}, copyright = {Academic Press}, DOI = {10.1006/jpdc.1993.1012}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-jwriteback/index.html}, 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.}, } @InProceedings{kotz:practical, author = {David Kotz and Carla Schlatter Ellis}, title = {{Practical Prefetching Techniques for Parallel File Systems}}, booktitle = {{Proceedings of the International Conference on Parallel and Distributed Information Systems (PDIS)}}, year = 1991, month = {December}, pages = {182--189}, publisher = {IEEE}, copyright = {IEEE}, DOI = {10.1109/PDIS.1991.183101}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-practical/index.html}, 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.}, } @PhdThesis{kotz:thesis, author = {David Kotz}, title = {{Prefetching and Caching Techniques in File Systems for MIMD Multiprocessors}}, school = {Duke University}, year = 1991, month = {April}, copyright = {David Kotz}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-thesis/index.html}, note = {Available as technical report CS-1991-016}, 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. \par 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. \par 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.}, } @InProceedings{kotz:writeback, author = {David Kotz and Carla Schlatter Ellis}, title = {{Caching and Writeback Policies in Parallel File Systems}}, booktitle = {{Proceedings of the IEEE Symposium on Parallel and Distributed Processing (SPDP)}}, year = 1991, month = {December}, pages = {60--67}, publisher = {IEEE}, copyright = {IEEE}, DOI = {10.1109/SPDP.1991.218296}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-writeback/index.html}, 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.}, } @Misc{kotz:rapid-transit-sw, author = {David Kotz}, title = {{RAPID-Transit parallel file-system simulator}}, howpublished = {The software basis for my Ph.D dissertation}, year = 1991, copyright = {David Kotz}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-rapid-transit-sw/index.html}, abstract = {RAPID-Transit was 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.}, } @Article{kotz:prefetch, author = {David F. 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}, publisher = {IEEE}, copyright = {IEEE}, DOI = {10.1109/71.80133}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-prefetch/index.html}, 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. \par 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). \par 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.}, } @InProceedings{ellis:prefetch, author = {Carla Schlatter Ellis and David Kotz}, title = {{Prefetching in File Systems for MIMD Multiprocessors}}, booktitle = {{Proceedings of the International Conference on Parallel Processing (ICPP)}}, year = 1989, month = {August}, volume = 1, pages = {306--314}, publisher = {Pennsylvania State University Press}, copyright = {Pennsylvania State University Press}, ISBN = {0-271-00686-2}, address = {St. Charles, IL}, URL = {https://www.cs.dartmouth.edu/~kotz/research/ellis-prefetch/index.html}, 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. \par 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). \par 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.}, } @Misc{kotz:umiacs, author = {David Kotz}, title = {{High-performance File System Design for MIMD Parallel Processors}}, howpublished = {A talk presented at the DARPA Workshop on Parallel Processing at UMIACS}, year = 1989, month = {August}, copyright = {the author}, URL = {https://www.cs.dartmouth.edu/~kotz/research/kotz-umiacs/index.html}, note = {Audiovisual presentation}, } @TechReport{ellis:prefetchTR, author = {Carla Schlatter Ellis and David Kotz}, title = {{Prefetching in File Systems for MIMD Multiprocessors}}, institution = {Dept. of Computer Science, Duke University}, year = 1988, month = {November}, number = {CS-1988-23}, copyright = {the authors}, URL = {https://www.cs.dartmouth.edu/~kotz/research/ellis-prefetchTR/index.html}, 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. MIMD multiprocessor architectures have a profound impact on the nature of the workloads they support. In particular, it is the collective behavior of the processes in a parallel computation that often determines the performance. The assumptions about file access patterns that underlie much of the work in uniprocessor file management are called into question. Results from experiments performed on the Butterfly Plus multiprocessor are presented showing the benefits that can be derived from prefetching (e.g. significant improvements in the cache miss ratio and the average time to perform an I/O operation). We explore why it is not trivial to translate these gains into much better overall performance. }, }