@Article{barve:mergesort,
  author = {Rakesh D. Barve and Edward F. Grove and Jeffrey S. Vitter},
  title = {Simple Randomized Mergesort on Parallel Disks},
  journal = {Parallel Computing},
  year = {1997},
  volume = {23},
  number = {4},
  publisher = {North-Holland (Elsevier Scientific)},
  note = {To appear},
  keyword = {verify, parallel I/O algorithm, sorting, pario-bib},
  abstract = {We consider the problem of sorting a file of N records on the
  D-disk model of parallel I/O in which there are two sources of parallelism.
  Records are transferred to and from disk concurrently in blocks of B
  contiguous records. In each I/O operation, up to one block can be transferred
  to or from each of the D disks in parallel. We propose a simple, efficient,
  randomized mergesort algorithm called SRM that uses a forecast-and-flush
  approach to overcome the inherent difficulties of simple merging on parallel
  disks. SRM exhibits a limited use of randomization and also has a useful
  deterministic version. Generalizing the technique of forecasting, our
  algorithm is able to read in, at any time, the ``right'' block from any disk,
  and using the technique of flushing, our algorithm evicts, without any I/O
  overhead, just the ``right'' blocks from memory to make space for new ones to
  be read in. The disk layout of SRM is such that it enjoys perfect write
  parallelism, avoiding fundamental inefficiencies of previous mergesort
  algorithms. By analysis of generalized maximum occupancy problems we are able
  to derive an analytical upper bound on SRM's expected overhead valid for
  arbitrary inputs. \par The upper bound derived on expected I/O performance of
  SRM indicates that SRM is provably better than disk-striped mergesort (DSM)
  for realistic parameter values D, M, and B. Average-case simulations show
  further improvement on the analytical upper bound. Unlike previously proposed
  optimal sorting algorithms, SRM outperforms DSM even when the number D of
  parallel disks is small.}
}

@InProceedings{chang:titan,
  author = {Chialin Chang and Bongki Moon and Anurag Acharya and Carter Shock
  and Alan Sussman and Joel Saltz},
  title = {{Titan}: a High-Performance Remote-sensing Database},
  booktitle = {Proceedings of the Thirteenth International Conference on Data
  Engineering},
  year = {1997},
  month = {April},
  address = {College Park, MD},
  URL = {ftp://hpsl.cs.umd.edu/pub/papers/icde97.ps.Z},
  abstract = {There are two major challenges for a high-performance
  remote-sensing database. First, it must provide low-latency retrieval of very
  large volumes of spatio-temporal data. This requires effective declustering
  and placement of a multi-dimensional dataset onto a large disk farm. Second,
  the order of magnitude reduction in data-size due to post-processing makes it
  imperative, from a performance perspective, that the postprocessing be done
  on the machine that holds the data. This requires careful coordination of
  computation and data retrieval. This paper describes the design,
  implementation and evaluation of {\em Titan}, a parallel shared-nothing
  database designed for handling remote-sensing data. The computational
  platform for Titan is a 16-processor IBM SP-2 with four fast disks attached
  to each processor. Titan is currently operational and contains about 24~GB of
  AVHRR data from the NOAA-7 satellite. The experimental results show that
  Titan provides good performance for global queries and interactive response
  times for local queries.}
}

@TechReport{cormen:early-vic-tr,
  author = {Thomas H. Cormen and Melissa Hirschl},
  title = {Early Experiences in Evaluating the Parallel Disk Model with the
  {ViC*} Implementation},
  year = {1996},
  month = {August},
  number = {PCS-TR96-293},
  institution = {Dept. of Computer Science, Dartmouth College},
  later = {cormen:early-vic},
  URL = {http://www.cs.dartmouth.edu/reports/abstracts/TR96-293/},
  keyword = {parallel I/O, parallel I/O algorithm, compiler, pario-bib},
  abstract = {Although several algorithms have been developed for the Parallel
  Disk Model (PDM), few have been implemented. Consequently, little has been
  known about the accuracy of the PDM in measuring I/O time and total time to
  perform an out-of-core computation. This paper analyzes timing results on a
  uniprocessor with several disks for two PDM algorithms, out-of-core radix
  sort and BMMC permutations, to determine the strengths and weaknesses of the
  PDM. \par The results indicate the following. First, good PDM algorithms are
  usually not I/O bound. Second, of the four PDM parameters, two (problem size
  and memory size) are good indicators of I/O time and running time, but the
  other two (block size and number of disks) are not. Third, because PDM
  algorithms tend not to be I/O bound, asynchronous I/O effectively hides I/O
  times. \par The software interface to the PDM is part of the ViC* run-time
  library. The interface is a set of wrappers that are designed to be both
  efficient and portable across several parallel file systems and target
  machines.},
  comment = {This used to be called cormen:early-vic but I renamed it because
  the paper will appear in parcomp.}
}

@Article{moon:declustering,
  author = {Bongki Moon and Joel H. Saltz},
  title = {Scalability Analysis of Declustering Methods for for
  Multidimensional Range Queries},
  year = {1997},
  note = {To appear},
  URL = {ftp://hpsl.cs.umd.edu/pub/papers/ieee_tkde.ps.Z},
  abstract = {Efficient storage and retrieval of multi-attribute datasets have
  become one of the essential requirements for many data-intensive
  applications. The Cartesian product file has been known as an effective
  multi-attribute file structure for partial-match and best-match queries.
  Several heuristic methods have been developed to decluster Cartesian product
  files across multiple disks to obtain high performance for disk accesses.
  Though the scalability of the declustering methods becomes increasingly
  important for systems equipped with a large number of disks, no analytic
  studies have been done so far. In this paper we derive formulas describing
  the scalability of two popular declustering methods Disk Modulo and Fieldwise
  Xor for range queries, which are the most common type of queries. These
  formulas disclose the limited scalability of the declustering methods and are
  corroborated by extensive simulation experiments. From the practical point of
  view, the formulas given in this paper provide a simple measure which can be
  used to predict the response time of a given range query and to guide the
  selection of a declustering method under various conditions.}
}

@Article{parsons:templates,
  author = {Ian Parsons and Ron Unrau and Jonathan Schaeffer and Duane
  Szafron},
  title = {{PI/OT}: Parallel {I/O} Templates},
  journal = {Parallel Computing},
  year = {1997},
  volume = {23},
  number = {4},
  publisher = {North-Holland (Elsevier Scientific)},
  note = {To appear},
  keyword = {verify, parallel I/O, pario-bib},
  abstract = {This paper presents a novel, top-down, high-level approach to
  parallelizing file I/O. Each parallel file descriptor is annotated with a
  high-level specification, or template, of the expected parallel behaviour.
  The annotations are external to and independent of the source code. At
  run-time, all I/O using a parallel file descriptor adheres to the semantics
  of the selected template. By separating the parallel I/O specifications from
  the code, a user can quickly change the I/O behaviour without rewriting code.
  Templates can be composed hierarchically to construct complex access
  patterns.}
}

@Article{schwabe:jlayouts,
  author = {Eric J. Schwabe and Ian M. Sutherland},
  title = {Evaluating Approximately Balanced Parity-Declustered Data Layouts
  for Disk Arrays},
  journal = {Parallel Computing},
  year = {1997},
  volume = {23},
  number = {4},
  publisher = {North-Holland (Elsevier Scientific)},
  note = {To appear},
  earlier = {schwabe:layouts},
  keyword = {verify, disk array, parity, RAID, parallel I/O, pario-bib},
  abstract = {Parity-declustered data layouts were developed to reduce the time
  for on-line failure recovery in disk arrays. They generally require perfect
  balancing of reconstruction workload among the disks; this restrictive
  balance condition makes such data layouts difficult to construct. In this
  paper, we consider approximately balanced data layouts, where some variation
  in the reconstruction workload over the disks is permitted. Such layouts are
  considerably easier to construct than perfectly balanced layouts. We consider
  three methods for constructing approximately balanced data layouts, and
  analyze their performance both theoretically and experimentally. We conclude
  that on uniform workloads, approximately balanced layouts have performance
  nearly identical to that of perfectly balanced layouts.}
}