Abstract
We provide the first optimal algorithms in terms of the number of input/outputs (I/Os) required between internal memory and multiple secondary storage devices for the problems of sorting, FFT, matrix transposition, standard matrix multiplication, and related problems. Our two-level memory model is new and gives a realistic treatmentof parallel block transfer, in which during a single I/O each of theP secondary storage devices can simultaneously transfer a contiguous block ofB records. The model pertains to a large-scale uniprocessor system or parallel multiprocessor system withP disks. In addition, the sorting, FFT, permutation network, and standard matrix multiplication algorithms are typically optimal in terms of the amount of internal processing time. The difficulty in developing optimal algorithms is to cope with the partitioning of memory intoP separate physical devices. Our algorithms' performances can be significantly better than those obtained by the wellknown but nonoptimal technique of disk striping. Our optimal sorting algorithm is randomized, but practical; the probability of using more than ι times the optimal number of I/Os is exponentially small inl(logl) log(M/B), whereM is the internal memory size.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Aggarwal and J. S. Vitter, The Input/Output Complexity of Sorting and Related Problems,Communications of the ACM 31(9) (September 1988), 1116–1127.
M, Blum, R. W. Floyd, V. Pratt, R. Rivest, and R. E. Tarjan, Time Bounds for Selection,Journal of Computer and System Sciences 7(4) (1973), 448–461.
J. L. Carter and M. N. Wegman, Universal Classes of Hash Functions,Journal of Computer and System Sciences 18 (April 1979), 143–154.
R. W. Floyd, Permuting Information in Idealized Two-Level Storage, inComplexity of Computer Calculations, R. Miller and J. Thatcher, eds., Plenum, New York, 1972, pp. 105–109.
L. Hellerstein, G. A. Gibson, R. M. Karp, R. H. Katz, and D. A. Patterson, Coding Techniques for Handling Failures in Large Disk Arrays,Algorithmica, this issue, pp. 182–208.
W. Jilke, Disk Array Mass Storage Systems: The New Opportunity, Amperif Corporation, September 1986.
L. Kleinrock,Queueing Systems, Vol. I, Wiley, New York, 1979.
D. Knuth,The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.
F. T. Leighton, Tight Bounds on the Complexity of Parallel Sorting,IEEE Transactions on Computers 34 (April 1985), 344–354.
E. E. Lindstrom and J. S. Vitter, The Design and Analysis of BucketSort for Bubble Memory Secondary Storage,IEEE Transactions on Computers 34 (March 1985), 218–233.
N. B. Maginnis, Store More, Spend Less: Mid-Range Options Around,Computerworld, November 16, 1986, p. 71.
M. H. Nodine and J. S. Vitter, Large-Scale Sorting in Parallel Memories,Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, July 1991, pp. 29–39.
M. H. Nodine and J. S. Vitter, Deterministic Distribution Sort in Shared and Distributed Memory Multiprocessors,Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, July 1993, pp. 120–129.
D. A. Patterson, G. Gibson, and R. H. Katz, A Case for Redundant Arrays of Inexpensive Disks (RAID),Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, June 1988, pp. 109–116.
J. Savage and J. S. Vitter, Parallelism in Space-Time Tradeoffs, inAdvances in Computing Research, Vol. 4, F. P. Preparata, ed., JAI Press, Greenwich, CT, 1987, pp. 117–146.
H. S. Stone, Parallel Processing with the Perfect Shuffle,IEEE Transactions on Computers 20 (February 1971), 153–161.
University of California, Massive Information Storage, Management, and Use (NSF Institutional Infrastructure Proposal), Technical Report No. UCB/CSD 89/493, University of California at Berkeley, January 1989.
J. S. Vitter and Ph. Flajolet, Average-Case Analysis of Algorithms and Data Structures, inHandbook of Theoretical Computer Science, Jan van Leeuwen, ed., North-Holland, Amsterdam, 1990, pp. 431–524.
J. S. Vitter and E. A. M. Shriver, Algorithms for Parallel Memory, II: Hierarchical Multilevel Memories,Algorithmica, this issue, pp. 148–169.
C. Wu and T. Feng, The Universality of the Shuffle-Exchange Network,IEEE Transactions on Computers 30 (May 1981), 324–332.
Author information
Authors and Affiliations
Additional information
Communicated by C. K. Wong.
Rights and permissions
About this article
Cite this article
Vitter, J.S., Shriver, E.A.M. Algorithms for parallel memory, I: Two-level memories. Algorithmica 12, 110–147 (1994). https://doi.org/10.1007/BF01185207
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01185207