Pointer swizzling at page fault time: efficiently supporting huge address spaces on standard hardware

ABSTRACT

We describe a scheme for supporting huge address spaces without the need for long addresses implemented in hardware. Pointers are translated ("swizzled") from a long format to a shorter format (directly supported by normal hardware) at page fault time. No extra hardware is required beyond that normally used by virtual memory systems, and no continual software cost is incurred by presence checks or indirection of pointers.This scheme could be used to fault pages into a normal memory from a persistent store, or simply to avoid extra hardware requirements when supporting large address spaces. It exploits temporal and spatial locality in much the same way as a normal virtual memory, so its performance should be quite good.

REFERENCES

• 1: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
• 2: ABCC83 Atkinson, M.P., P.J. Bailey, K.J. Chisholm, P. W. Cockshott, and R. Morrison, "An approach to persistent programming," The Computer Journal, vol. 26, no. 4, December 1983, pp. 360-365.
• 3: Bart88 Bartlett, Joel F. "Compacting garbage collection with ambiguous roots," Technical Report 88/2, Digital Equipment Corp., Western Research Laboratory, February 88.
• 4: BaSa76 Baer, J.-L., and Sager, G.R. "Dynamic improvement of Locality in virtual memory systems," IEEE TSWE, vol. SE-2, no. 1 (March 1976).
• 5: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 6: CACB84 Cockshott, W., M. Atkinson, K. Chisholm, P. Bailey, and R. Morrison, "Persistent Object Management System," Software Practice and Experience, vol. 14, 1984, pp. 49-71.
• 7: Alan Demmers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States [doi>10.1145/96709.96735]
• 8: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 9: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 10: Jan Heering , Paul Klint, Towards monolingual programming environments, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.183-213, April 1985 [doi>10.1145/3318.3321]
• 11: Kaeh81 Kaehler, T. "Virtual memory for an object-oriented language," Byte 6, 8 (August 1981), pp. 378-387.
• 12: J. Eliot B. Moss, Addressing large distributed collections of persistent objects: the Mneme project's approach, Proceedings of the second international workshop on Database programming languages, p.358-374, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
• 13: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 14: Moss90 Moss, Eliot "Working with objects: to swizzle or not to swizzle?," Unpublished technical report, University of Massachusetts 1990.
• 15: Stam82 Stamos, James William, "A large object-oriented virtual memory: grouping strategies, measurements, and performance," Xerox Palo Alto Research Centers Technical Report SCG-82-2, May 1982.
• 16: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 17: Wils89 Wilson, Paul R. "Heap management and hierarchical memories," Unpublished working paper, May 1989.
• 18: Paul R. Wilson, Some issues and strategies in heap management and memory hierarchies, ACM SIGPLAN Notices, v.26 n.3, p.45-52, March 1991 [doi>10.1145/122167.122173]
• 19: Paul R. Wilson , Michael S. Lam , Thomas G. Moher, Effective “static-graph” reorganization to improve locality in garbage-collected systems, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.177-191, June 24-28, 1991, Toronto, Ontario, Canada
• 20: P. R. Wilson , T. G. Moher, Design of the opportunistic garbage collector, Conference proceedings on Object-oriented programming systems, languages and applications, p.23-35, October 02-06, 1989, New Orleans, Louisiana, United States
• 21: Ifor Williams , Mario Wolczko , Trevor Hopkins, Dynamic Grouping in an Object-Oriented Virtual Memory Hierarchy, Proceedings of the European Conference on Object-Oriented Programming, p.79-88, June 15-17, 1987
• 22: WiWH90 Williams, Ifor, Mario Wolkzko, and Trevor Hopkins, "Realization of a dynamically grouped object-oriented memory hierarchy," technical report, University of Manchester Dept. of Computer Science, 1990.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

Additional Classification:
  C. Computer Systems Organization

General Terms:
Design