A true hardware read barrier

ABSTRACT

Read barriers synchronize compacting garbage collection and application processing in a simple yet elegant way. Unfortunately, read barrier checks are expensive to implement in software, and even with hardware support, the clustering of read barrier faults irregularly impairs application progress to an unacceptable extent. For this reason, read barriers are often considered unsuitable for hard real-time systems.In this paper, we introduce a novel hardware read barrier design for an object-based RISC architecture. The design integrates read barrier checking and, for the first time, read barrier fault handling directly into a processor pipeline.Our system handles read barrier faults within 20 clock cycles on average. Despite fault clustering, all application programs we have run on our prototype show minimum mutator utilizations of more that 55% within arbitrary time intervals of only 1ms. Thanks to this property, our system facilitates worst case estimates for tasks with very short response times, thereby paving the way for garbage collection in embedded systems with extremely fine-grained real-time requirements.

REFERENCES

• 1: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 2: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-298, January 15-17, 2003, New Orleans, Louisiana, USA
• 3: Rodney A. Brooks, Trading data space for reduced time and code space in real-time garbage collection on stock hardware, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.256-262, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802042]
• 4: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 5: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.125-136, June 2001, Snowbird, Utah, United States
• 6: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 7: Mark Hill , Susan Eggers , Jim Larus , George Taylor , Glenn Adams , B. K. Bose , Garth Gibson , Paul Hansen , Jon Keller , Shing Kong , Corinna Lee , Daebum Lee , Joan Pendleton , Scott Ritchie , David Wood , Ben Zorn , Paul Hilfinger , Dave Hodges , Randy Katz , John Ousterhout , Dave Patterson, Design decisions in SPUR, Computer, v.19 n.11, p.8-22, Nov. 1986 [doi>10.1109/MC.1986.1663096]
• 8: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 9: Matthias Meyer, A Novel Processor Architecture with Exact Tag-Free Pointers, IEEE Micro, v.24 n.3, p.46-55, March 2004 [doi>10.1109/MM.2004.2]
• 10: Matthias Meyer, An On-Chip Garbage Collection Coprocessor for Embedded Real-Time Systems, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05), p.517-524, August 17-19, 2005 [doi>10.1109/RTCSA.2005.25]
• 11: 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]
• 12: Nilsen, K. D.: Memory Cycle Accountings for Hardware-Assisted Real-Time Garbage Collection, Tech. Report 91-21, Dep. of Computer Science, Iowa State University, Nov. 1992.
• 13: William J. Schmidt , Kelvin D. Nilsen, Performance of a hardware-assisted real-time garbage collector, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.76-85, October 05-07, 1994, San Jose, California, United States
• 14: Siebert, F.: Hard Realtime Garbage Collection in Modern Object Oriented Programming Languages, Dissertation, University of Karlsruhe, Germany, 2002.
• 15: David Ungar , Ricki Blau , Peter Foley , Dain Samples , David Patterson, Architecture of SOAR: Smalltalk on a RISC, Proceedings of the 11th annual international symposium on Computer architecture, p.188-197, January 1984
• 16: Zorn, B.: Barrier Methods for Garbage Collection, Tech. Report CU-CS-494-90, University of Colorado, Nov. 1990.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance

Keywords:
hardware support, object-based processor architecture, read barrier, real-time garbage collection