Big Wins with Small Application-Aware Caches

ABSTRACT

Large datasets, on the order of GB and TB, are increasingly common as abundant computational resources allow practitioners to collect, produce and store data at higher rates. As dataset sizes grow, it becomes more challenging to interactively manipulate and analyze these datasets due to the large amounts of data that need to be moved and processed. Application-independent caches, such as operating system page caches and database buffer caches, are present throughout the memory hierarchy to reduce data access times and alleviate transfer overheads. We claim that an application-aware cache with relatively modest memory requirements can effectively exploit dataset structure and application information to speed access to large datasets. We demonstrate this idea in the context of a system named the tree cache, to reduce query latency to large octree datasets by an order of magnitude.

REFERENCES

• 1: Vokan Akcelik , Jacobo Bielak , George Biros , Ioannis Epanomeritakis , Antonio Fernandez , Omar Ghattas , Eui Joong Kim , Julio Lopez , David O'Hallaron , Tiankai Tu , John Urbanic, High Resolution Forward And Inverse Earthquake Modeling on Terascale Computers, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.52, November 15-21, 2003
• 2: C. L. Bajaj , V. Pascucci , D. Thompson , X. Y. Zhang, Parallel accelerated isocontouring for out-of-core visualization, Proceedings of the 1999 IEEE symposium on Parallel visualization and graphics, p.97-104, October 25-26, 1999, San Francisco, California, United States [doi>10.1145/328712.319342]
• 3: [3] M. Beynon, R. Ferreira, T. M. Kurc, A. Sussman, and J. H. Saltz. Datacutter: Middleware for filtering very large scientific datasets on archival storage systems. In Symp. on Mass Storage Systems, pages 119-134. IEEE, 2000.
• 4: [4] R. E. Bryant and D. O'Hallaron. Computer Systems: A Programmer's Perspective. Prentice Hall, 2003.
• 5: Michael J. Carey , Michael J. Franklin , Markos Zaharioudakis, Fine-grained sharing in a page server OODBMS, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.359-370, May 24-27, 1994, Minneapolis, Minnesota, United States
• 6: Yi-Jen Chiang , Ricardo Farias , Cláudio T. Silva , Bin Wei, A unified infrastructure for parallel out-of-core isosurface extraction and volume rendering of unstructured grids, Proceedings of the IEEE 2001 symposium on parallel and large-data visualization and graphics, October 22-23, 2001, San Diego, California
• 7: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 8: Alper K. Demir , Marcus Thiébaux, Practical Resource Management for Grid-Based Visual Exploration, Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing, p.416, August 07-09, 2001
• 9: Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan, Semantic Data Caching and Replacement, Proceedings of the 22th International Conference on Very Large Data Bases, p.330-341, September 03-06, 1996
• 10: Mark Day , Barbara Liskov , Umesh Maheshwari , Andrew C. Myers, References to remote mobile objects in Thor, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.115-126, March–Dec. 1993 [doi>10.1145/176454.176500]
• 11: David J. DeWitt , Philippe Futtersack , David Maier , Fernando Vélez, A Study of Three Alternative Workstation-Server Architectures for Object Oriented Database Systems, Proceedings of the 16th International Conference on Very Large Data Bases, p.107-121, August 13-16, 1990
• 12: [12] I. Gargantini. Linear octree for fast processing of three-dimensional objects. Computer Graphics and Image Processing, 20(4):365-374, 1982.
• 13: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 14: Anca-Andreea Ivan , Vijay Karamcheti, Using Views for Customizing Reusable Components in Component-Based Frameworks, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing, p.194, June 22-24, 2003
• 15: [15] G. Lai, M. Liu, F.-Y. Wang, and D. Zeng. Web caching: architectures and performance evaluation survey. In Conf. on Systems, Man, and Cybernetics, pages V5: 3039-3044. IEEE, Oct 2001.
• 16: [16] J. Lopez, T. Tu, and D. O'Hallaron. CVMs: Community Velocity Model service. http://cvm.cs.cmu.edu, 2002.
• 17: [17] H. Magistrale, R. Graves, and R. Clayton. A standard three-dimensional seismic velocity model for southern California: version 1. EOS Transactions AGU, 79:F605, 1998. www.scecdc.scec.org/3Dvelocity/ 3Dvelocity.html.
• 18: James H. Morris , Mahadev Satyanarayanan , Michael H. Conner , John H. Howard , David S. Rosenthal , F. Donelson Smith, Andrew: a distributed personal computing environment, Communications of the ACM, v.29 n.3, p.184-201, March 1986 [doi>10.1145/5666.5671]
• 19: [19] G. M. Morton. A computer oriented geodetic database and a new technique in file sequencing. Technical report, IBM, Ottawa, Canada, 1966.
• 20: [20] H. Sagan. Space Filling Curves. Springer, 1994.
• 21: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 22: Mahadev Satyanarayanan , James J. Kistler , Puneet Kumar , Maria E. Okasaki , Ellen H. Siegel , David C. Steere, Coda: A Highly Available File System for a Distributed Workstation Environment, IEEE Transactions on Computers, v.39 n.4, p.447-459, April 1990 [doi>10.1109/12.54838]
• 23: Abraham Silberschatz , James L. Peterson , Peter B. Galvin, Operating system concepts (3rd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 24: Abraham Silberschatz , Henry F. Korth , S. Sudarshan, Database Systems Concepts, McGraw-Hill Higher Education, 2001
• 25: [25] Southern California Earthquake Center. Community velocity model (SCEC/CME). www.scec.org/cme.
• 26: Michael Stonebraker, Operating system support for database management, Communications of the ACM, v.24 n.7, p.412-418, July 1981 [doi>10.1145/358699.358703]
• 27: Philip M. Sutton , Charles D. Hansen, Accelerated Isosurface Extraction in Time-Varying Fields, IEEE Transactions on Visualization and Computer Graphics, v.6 n.2, p.98-107, April 2000 [doi>10.1109/2945.856992]
• 28: [28] T. Tu, J. Lopez, and D. O'Hallaron. The Etree library: A system for manipulating large octrees on disk. Technical Report CMU-CS-03-174, Carnegie Mellon School of Computer Science, Pittsburgh, PA, July 2003.
• 29: [29] T. Tu, D. O'Hallaron, and J. Lopez. Etree - a database-oriented method for generating large octree meshes. In Proceedings of the Eleventh International Meshing Roundtable, pages 127-138, Ithaca, NY, Sep 2002.
• 30: Marc van Kreveld , René van Oostrum , Chandrajit Bajaj , Valerio Pascucci , Dan Schikore, Contour trees and small seed sets for isosurface traversal, Proceedings of the thirteenth annual symposium on Computational geometry, p.212-220, June 04-06, 1997, Nice, France [doi>10.1145/262839.269238]
• 31: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]