research-article

Parallel real-time garbage collection of multiple heaps in reconfigurable hardware

Authors:

David F. Bacon,

Sunil ShuklaAuthors Info & Claims

ACM SIGPLAN Notices, Volume 49, Issue 11

Pages 117 - 127

https://doi.org/10.1145/2775049.2602996

Published: 12 June 2014 Publication History

Abstract

Despite rapid increases in memory capacity, reconfigurable hardware is still programmed in a very low-level manner, generally without any dynamic allocation at all. This limits productivity especially as the larger chips encourage more and more complex designs to be attempted.

Prior work has shown that it is possible to implement a real-time collector in hardware and achieve stall-free operation --- but at the price of severe restrictions on object layouts. We present the first hardware garbage collector capable of collecting multiple inter-connected heaps, thereby allowing a rich set of object types.

We show that for a modest additional cost in logic and memory, we can support multiple heaps at a clock frequency competitive with monolithic, fixed-layout heaps. We evaluate the hardware design by synthesizing it for a Xilinx FPGA and using co-simulation to measure the run-time behavior over a set of four benchmarks. Even at high allocation and mutation rates the collector is able to sustain stall-free (100% minimum mutator utilization) operation with up to 4 inter-connected heaps, while only requiring between 1.1 and 1.7 times the maximum live memory of the application.

References

[1]

S. E. Abdullahi and G. A. Ringwood. Garbage collecting the internet: A survey of distributed garbage collection. ACM Comput. Surv., 30(3):330--373, Sept. 1998.

Digital Library

[2]

D. F. Bacon, P. Cheng, and S. Shukla. And then there were none: A stall-free real-time garbage collector for reconfigurable hardware. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 23--34, 2012.

Digital Library

[3]

D. F. Bacon, P. Cheng, and S. Shukla. A generalized high-performance garbage collector for FPGA data structures. Technical report, IBM Research, Jan. 2014.

[4]

H. G. Baker. List processing in real-time on a serial computer. Commun. ACM, 21(4):280--294, Apr. 1978.

Digital Library

[5]

A. Canis et al. LegUp: An open-source high-level synthesis tool for FPGA-based processor/accelerator systems. TECS, 13(2):1:1--1:25, Sept. 2013.

Digital Library

[6]

P. Cheng and G. Blelloch. A parallel, real-time garbage collector. In Proc. SIGPLAN Conference on Programming Language Design and Implementation, pp. 125--136, Snowbird, Utah, June 2001.

Digital Library

[7]

C. Click, G. Tene, and M. Wolf. The pauseless GC algorithm. In Proceedings of the First ACM/USENIX International Conference on Virtual Execution Environments, pp. 46--56, 2005.

Digital Library

[8]

R. P. Colwell, R. P. Nix, J. J. O'Donnell, D. B. Papworth, and P. K. Rodman. A VLIW architecture for a trace scheduling compiler. IEEE Trans. Computers, 37(8):967--979, 1988.

Digital Library

[9]

B. Cook et al. Finding heap-bounds for hardware synthesis. In Formal Methods in Computer-Aided Design, pp. 205--212, Nov. 2009.

[10]

P. Faes, M. Christiaens, D. Buytaert, and D. Stroobandt. FPGA-aware garbage collection in Java. In T. Rissa, S. J. E. Wilton, and P. H. W. Leong, editors, FPL, pp. 675--680, 2005.

[11]

M. Meyer. An on-chip garbage collection coprocessor for embedded real-time systems. In Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pp. 517--524, 2005.

Digital Library

[12]

D. A. Moon. Garbage collection in a large LISP system. In Conference Record of the 1984 ACM Symposium on LISP and Functional Programming, Austin, Texas, Aug. 1984.

Digital Library

[13]

W. J. Schmidt and K. D. Nilsen. Performance of a hardware-assisted real-time garbage collector. In Proceedings of the Sixth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 76--85, 1994.

Digital Library

[14]

M. Schoeberl and W. Puffitsch. Nonblocking real-time garbage collection. ACM Trans. Embedded Comput. Sys., 10:1--28, 2010.

Digital Library

[15]

J. Simsa and S. Singh. Designing hardware with dynamic memory abstraction. In Proceedings of the 18th Annual International Symposium on Field Programmable Gate Arrays, pp. 69--72, 2010.

Digital Library

[16]

G. L. Steele, Jr. Data representation in PDP-10 MACLISP. Technical report, MIT, 1977. AI Memo 420.

[17]

D. Ungar et al. Architecture of SOAR: Smalltalk on a RISC. In Proceedings of the 11th Annual International Symposium on Computer Architecture, pp. 188--197, 1984.

Digital Library

[18]

Xilinx. Virtex-5 family overview. Technical Report DS100, Feb. 2009.

[19]

T. Yuasa. Real-time garbage collection on general-purpose machines. J. Systems and Software, 11(3):181--198, Mar. 1990.

Digital Library

[20]

J. Zhou and B. Demsky. Locality-aware many-core garbage collectionTechnical Report CECS 10-08, Center for Embedded Computer Systems University of California, Irvine, Aug. 2010.

Cited By

Barker MEdwards SKim M(2022)Synthesized In-BramGarbage Collection for Accelerators with Immutable Memory2022 32nd International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL57034.2022.00019(47-53)Online publication date: Aug-2022
https://doi.org/10.1109/FPL57034.2022.00019
Ugawa TRitson CJones R(2018)Transactional SapphireACM Transactions on Programming Languages and Systems10.1145/322622540:4(1-56)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1145/3226225
Hussein AHosking APayer MVick C(2015)Don't race the memory bus: taming the GC leadfootACM SIGPLAN Notices10.1145/2887746.275418250:11(15-27)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2887746.2754182
Show More Cited By

Index Terms

Parallel real-time garbage collection of multiple heaps in reconfigurable hardware
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features

Recommendations

Parallel real-time garbage collection of multiple heaps in reconfigurable hardware
ISMM '14: Proceedings of the 2014 international symposium on Memory management

Despite rapid increases in memory capacity, reconfigurable hardware is still programmed in a very low-level manner, generally without any dynamic allocation at all. This limits productivity especially as the larger chips encourage more and more complex ...
And then there were none: a stall-free real-time garbage collector for reconfigurable hardware
PLDI '12: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation

Programmers are turning to radical architectures such as reconfigurable hardware (FPGAs) to achieve performance. But such systems, programmed at a very low level in languages with impoverished abstractions, are orders of magnitude more complex to use ...
And then there were none: a stall-free real-time garbage collector for reconfigurable hardware
PLDI '12

Programmers are turning to radical architectures such as reconfigurable hardware (FPGAs) to achieve performance. But such systems, programmed at a very low level in languages with impoverished abstractions, are orders of magnitude more complex to use ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 49, Issue 11

ISMM '14

November 2014

121 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2775049

Editor:
Andy Gill
University of Kansas, Lawrence, KS

Issue’s Table of Contents

ISMM '14: Proceedings of the 2014 international symposium on Memory management
June 2014
136 pages
ISBN:9781450329217
DOI:10.1145/2602988
General Chair:
David Grove
IBM Research, USA
,
Program Chair:
Samuel Z. Guyer
Tufts University, USA

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2014

Published in SIGPLAN Volume 49, Issue 11

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
356
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Barker MEdwards SKim M(2022)Synthesized In-BramGarbage Collection for Accelerators with Immutable Memory2022 32nd International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL57034.2022.00019(47-53)Online publication date: Aug-2022
https://doi.org/10.1109/FPL57034.2022.00019
Ugawa TRitson CJones R(2018)Transactional SapphireACM Transactions on Programming Languages and Systems10.1145/322622540:4(1-56)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1145/3226225
Hussein AHosking APayer MVick C(2015)Don't race the memory bus: taming the GC leadfootACM SIGPLAN Notices10.1145/2887746.275418250:11(15-27)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2887746.2754182
Hussein AHosking APayer MVick CHosking ABond M(2015)Don't race the memory bus: taming the GC leadfootProceedings of the 2015 International Symposium on Memory Management10.1145/2754169.2754182(15-27)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2754169.2754182
Ugawa TRitson CJones R(2018)Transactional SapphireACM Transactions on Programming Languages and Systems10.1145/322622540:4(1-56)Online publication date: 10-Dec-2018
https://dl.acm.org/doi/10.1145/3226225
Townsend RKim MEdwards SWu PHack S(2017)From functional programs to pipelined dataflow circuitsProceedings of the 26th International Conference on Compiler Construction10.1145/3033019.3033027(76-86)Online publication date: 5-Feb-2017
https://dl.acm.org/doi/10.1145/3033019.3033027
Hussein AHosking APayer MVick C(2015)Don't race the memory bus: taming the GC leadfootACM SIGPLAN Notices10.1145/2887746.275418250:11(15-27)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2887746.2754182
Hussein AHosking APayer MVick CHosking ABond M(2015)Don't race the memory bus: taming the GC leadfootProceedings of the 2015 International Symposium on Memory Management10.1145/2754169.2754182(15-27)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2754169.2754182

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents