I/O Complexity: The Red-Blue Pebble Game.

Abstract

In this paper, the red-blue pebble game is proposed to model the input-output complexity of algorithms. Using the pebble game formulation, a number of lower bound results for the I/O (Input/Output) requirement are proven. For example, it is shown that to perform the n-point FFT (or the ordinary nxn matrix multiplication algorithm) with a device of O(S) memory at least Omega(n log n/log S) (or Omega(n-cubed/square root of S), respectively) time is needed for the I/O. Similar results are obtained for algorithms for several other problems. All of the lower bounds presented are the best possible in the sense that they are achievable by certain decomposition schemes. The results in this paper provide insight into the difficult task of balancing I/O and computation in special-purpose system design. For example, for the n-point FFT, the I/O lower bound implies that an S-point device achieving a speed-up ratio O(log S) over the conventional O(n log n) implementation is all that one can hope for.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1981
Accession Number
ADA104739

Entities

People

  • H. T. Kung
  • Jai-wei Hong

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Algorithms
  • Blood Coagulation Factors
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Contracts
  • Decomposition
  • Image Processing
  • Numbers
  • Signal Processing
  • Test And Evaluation
  • Theorems
  • Transitions
  • Universities

Fields of Study

  • Computer science

Readers

  • Game Theory.
  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.