Abstract
The speed of CPUs is accelerating rapidly, outstripping that of peripheral storage devices and making it increasingly difficult to keep CPUs busy. Consequently multi-level memory hierarchies, scaled to simulate single-level memories, are increasing in importance. In this paper we introduce the Memory Hierarchy Game, a multi-level pebble game that simulates data movement in memory hierarchies in terms of which we study space-time tradeoffs.
We provide a) a common generalization of the Hong-Kung and Paterson-Hewitt pebble models to the Memory Hierarchy Game, b) a greatly simplified proof of the Hong-Kung lower bound on I/O complexity that makes their result readily accessible, c) straight-line algorithms for a representative set of problems that are simultaneously optimal at each level in the memory hierarchy in their use of space and I/O and computation time, and d) an extension the game to block transfers of data between memories.
This work was supported in part by the Office of Naval Research under contract N00014-91-J-4052, ARPA Order 8225 and by NSF under Grant MIP-902570.
Preview
Unable to display preview. Download preview PDF.
References
A. Aggarwal, B. Alpern, A. Chandra, and M. Snir, “A Model for Hierarchical Memory,” Procs. 21st Annual ACM Symposium on Theory of Computing (May 15–17, 1989), 305–314.
A. Aggarwal, A. Chandra, and M. Snir, “Hierarchical Memory with Block Transfer,” Proc. 28th Annl. Symp. on Foundations of Computer Science (October 1987), 204–216.
A. Aggarwal and J. S. Vitter, “The Input/Output Complexity of Sorting and Related Problems,” Communications of the ACM 31 (September 1988), 1116–1127.
B. Alpern, L. Carter, and E. Feig, “Uniform Memory Hierarchies,” Proc. 31st Annual Symposium on Foundations of Computer Science (October 22–24, 1990), 600–608.
D. A. Carlson, “Time-Space Tradeoffs for Back-to-Back FFT Algorithms,” IEEE Trans. Computing C-32 (1983), 585–589.
S. Even and A. Litman, “Layered Cross Product–A Technique to Construct Interconnection Networks,” Proc. 4th Ann. ACM Symp. on Parallel Algorithms and Architectures (June 29–July 1, 1992), 60–69.
D. Y. Grigoryev, “An Application of Separability and Independence Notions for Proving Lower Bounds of Circuit Complexity,” Notes of Scientific Seminars, Steklov Math. Inst. 60 (1976), 35–48.
J.-W. Hong and H. T. Kung, “I/O Complexity: The Red-Blue Pebble Game,” Proc. 13th Ann. ACM Symp. on Theory of Computing (May 11–13, 1981), 326–333.
F. T. Leighton, in Introduction to Parallel Algorithms and Architectures, Morgan Kaufmann Publishers, Inc., San Mateo, CA, 1992.
M. H. Nodine and J. S. Vitter, “Large-Scale Sorting in Parallel Memories (Extended Abstract),” Procs. 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (July 21–24, 1991), 29–39.
M. S. Paterson and C. E. Hewitt, “Comparative Schematology,” Proc. Proj. MAC Conf. on Concurrent Systems and Parallel Computation (June 1970), 119–127.
J. E. Savage and J. S. Vitter, “Parallelism in Space-Time Tradeoffs,” in Advances in Computing Research, F. P. Preparata, ed., 1987, 117–146.
J. E. Savage, A Generalization of Grigoryev's Space-Time Tradeoff Method, Unpublished manuscript, March 1995.
M. Tompa, “Time-Space Tradeoffs for Computing Functions, Using Connectivity Properties of Their Circuits,” JCSS 20 (1980), 118–132.
M. Tompa, “Corrigendum: Time-Space Tradeoffs for Computing Functions, Using Connectivity Properties of Their Circuits,” JCSS 23 (1981), 106.
J. S. Vitter and E. A. M. Shriver, “Optimal Disk I/O with Parallel Block Transfer,” Procs. 22nd Annual ACM Symposium on Theory of Computing (May 1990), 159–169.
C. L. Wu and T. Y. Feng, “The Universality of the Shuffle-Exchange Network,” IEEE Trans. Computing C-30 (May 1981), 324–332.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Savage, J.E. (1995). Extending the Hong-Kung model to memory hierarchies. In: Du, DZ., Li, M. (eds) Computing and Combinatorics. COCOON 1995. Lecture Notes in Computer Science, vol 959. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0030842
Download citation
DOI: https://doi.org/10.1007/BFb0030842
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60216-3
Online ISBN: 978-3-540-44733-7
eBook Packages: Springer Book Archive