Newsgroups: comp.parallel From: gvg@engr.orst.edu (Gritton Gregory Vance) Subject: Re: Garbage Collection Keywords: parallel garbage collection Organization: College of Engineering, Oregon State University Date: Thu, 23 Sep 1993 12:39:46 GMT A week or two ago I posted a query for information on Garbage Collection in general and parallel Garbage Collection in particular. I got a number of reply. They are posed below. Thank you to all the people who responded. One particularly useful piece of information was a pointer to look at cs.utexas for more information. You can anonymous ftp to cs.utexas.edu and get information in /pub/garbage. Here is a summery of the responses: >From kram@cc.gatech.edu Mon Sep 13 09:14:33 1993 Date: Mon, 13 Sep 1993 12:14:26 -0400 From: Ram M Kordale To: gvg@ENGR.ORST.EDU Subject: Re: Parallel Garbage Collection Newsgroups: comp.parallel Organization: College of Computing Cc: Content-Length: 5058 Status: RO X-Lines: 90 The following bibliography is more relevant to distributed garbage collection but there are quite a few which are applicable even to parallel garbage collection. Hope it helps, Ram ------------------------------------------------------------------------ \begin{thebibliography}{ZZZ99} \bibitem[App88]{App88} A. W. Appel, J. R. Ellis and Kai Li. Real--time Concurrent Collection on Stock Multiprocessors. {\it SIGPLAN'88 Conf. on Prog. Lang. Design and Implementation}, June 1988, pp 11-20. \bibitem[Bis77]{Bis77} P. B. Bishop. Computer systems with a very large address space and garbage collection. {\it Tech. Rep. MIT/LCS/TR-178, M.I.T. Laboratory of Computer Science}, Cambridge, MA, May, 1977. \bibitem[Cha92]{Cha92} J. S. Chase, H. M. Levy, M. Baker-Harvey, and E. D. Lazowska. How to Use a 64-bit Virtual Address Space. {\it Dept. of Comp. Science and Engg., Univ. of Washington. Tech. Report 92-03-02}, Mar 1992. \bibitem[Coh81]{Coh81} J. Cohen. Garbage Collection of linked data structures. {\it Computing Surveys}, Sep 1988. {Dic92} P. Dickman. Optimising weighted reference counts for scalable fault-tolerant distributed object-support systems. \bibitem[Dji78]{Dji78} E. W. Djikstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On--the--fly garbage collection: an exercise in cooperation. {\it Communications of the ACM}, Nov 1978. %\bibitem[Dob92]{Dob92} D. Dobberpuhl et. al. A 200mhz 64 bit dual issue %cmos microprocessor. In {\it International Solid-State Circuits %Conference 1992}, Feb 1992. \bibitem[Hug85]{Hug85} J. Hughes. A distributed garbage collection Algorithm. In {\it Functional Languages and Computer Architechtures}. In Lecture Notes in Computer Science, Sep 1985. \bibitem[JJ92]{JJ92} N. C. Juul and E. Jul. Comprehensive and Robust Garbage Collection in a Distributed System. IWMM'92. \bibitem[Knu69]{Knu69} D. E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms. {\it Addison--Wesley, Reading, Massachusetts}, 1969. \bibitem[Kor92]{Kor92} R. Kordale, M. Ahamad and J. Shilling. Distributed/Concurrent Garbage Collection in Distributed Shared Memory systems. {\it Georgia Inst. ofTechnology, Tech. Report}, TR \# GIT-CC-92/45. \bibitem[Kor93a]{Kor93a} R. Kordale, M. Ahamad and J. Shilling. Distributed/Concurrent Garbage Collection in Distributed Shared Memory systems. To appear in {\it International Workshop on Object-Orientation in Operating Systems}, Ashville, Dec 1993. \bibitem[Kor93b]{Kor93b} R. Kordale, and M. Ahamad. A Scalable Cyclic Garbage Detection Algorithm for Distributed Systems. To appear in the Proceedings of the {\it OOPSLA'93 Workshop on Garbage Collection}. \bibitem[Lad92]{Lad92} R. Ladin and B. Liskov. Garbage Collection of a Distributed Heap. {\it In proceedings of 12th International Conference on DCS, 1992.} \bibitem[LQP92]{LQP92} B. Lang, C. Queinnec and J. Piquer. Garbage collecting the world. In Proc. of the 19th Symp. on Principles of Programming Lang., 1992. \bibitem[Lie83]{Lie83} H. Lieberman and C. Hewitt. A Real--Time Garbage Collector Based on the Lifetimes of Objects. {\it Communications of the ACM}, June 1983. \bibitem[Lis88]{Lis88} Distributed Programming in Argus. {Comm. of the ACM}, Vol 31, March, 1988. \bibitem[MS91]{MS91} L. Mancini and S.K. Shrivastava. Fault-tolerant reference counting for garbage collection in distributed systems. The Computer Journal 34,6. Dec 1991. \bibitem[Net92]{Net92} S. Nettles, J. O'Toole, D. Pierce, N. Haines. Replication-Based Incremental Copying Collection. {\it Proceedings of the 1992 International Workshop on Memory Management}. \bibitem[Piq91]{Piq91} J. M. Piquer. Indirect reference counting, a distributed garbage colection algorithm. In {\it PARLE'91}, vol. I of {\it Lecture Notes in Computer Science}, Springer-Verlag. \bibitem[Ser92]{Ser92} T. Le Sergent, B. Berthomieu. Incremental Multi-Threaded Garbage Collection on Virtually Shared Memory Architectures. {\it Proceedings of the 1992 International Workshop on Memory Management}. \bibitem[Sha90]{Sha90} M. Shapiro, O. Gruber and D. Plainfosse. A Garbage Detection Protocol for a Realistic Distributed Object Support System. {\it Rapport de Recherche 1320}, INRIA, France, November 1990 \bibitem[Sha92]{Sha92} M. Shapiro, P. Dickman, and D. Plainfosse. Robust, Distributed References and Acyclic Garbage Collection. {\it Symp. on Princ. of Dist. Computing.} August 1992. \bibitem[Ung84]{Ung84} D. Ungar. Generational Scavenging: A Non--Disruptive High Performance Storage Reclamation Algorithm. {\it ACM Software Eng. Notes/SIGPLAN Notices Software Engineering Symposium on Practical Software Development Environments.} April 1984. \bibitem[Ves87]{Ves87} S. C. Vestal. Garbage Collection: An Exercise in Distributed, Fault--tolerant Programming. {\it PhD thesis, Dept. of Comp. Sc., U. of Washington, Seattle}. Tech. Report 87--01--03. \bibitem[Wil92]{Wil92} P. R. Wilson. Uniprocessor Garbage Collection Techniques. {\it Proceedings of the 1992 International Workshop on Memory Management}. \end{thebibliography} >From tuecke@mcs.anl.gov Mon Sep 13 11:23:10 1993 To: gvg@ENGR.ORST.EDU Cc: tuecke@mcs.anl.gov Subject: Re: Parallel Garbage Collection Date: Mon, 13 Sep 1993 13:23:02 -0500 From: Steve Tuecke Content-Length: 10353 Status: RO X-Lines: 307 In comp.parallel article <26r644INN6e0@flop.ENGR.ORST.EDU> you wrote: > I am implementing a simulated Parallel Smalltalk system, and one of the > things I am going to have to implement is Garbage Collection. > Unfortunately, our library seems to lack good information on the topic. > Is there anybody out there in net-land who has a good bibliography > on parallel garbage collection (or just plain garbage collection), > or knows of FTP sites or other places to get papers on the subject. PCN, a parallel programming language developed over the last few years at Argonne and Caltech, uses a parallel garbage collector. You can anonymous ftp the following technical memo which describes how garbage collection (among other things) was implemented in the version 1.x system: info.mcs.anl.gov /pub/pcn_other/internal/runtime.ps.Z In PCN version 2.0 we rewrote the garbage collector to employ a variation of the "Morris algorithm" (single space, compacting), instead of the stop-and-copy (two spaces, copy between them) collector which was used in v1.x. However, the two versions use the same weighting scheme to handle "reference counting" between nodes, as described in the above mentioned technical memo. The "Morris algorithm" is described in: "A Time- and Space- Efficient Garbage Compaction Algorithm" F. Lockwood Morris Communications of the ACM August 1978, Volume 21, Number 8 If you wish to see how we modified it to work in parallel in PCN, I refer you to the (fairly well documented) source. The PCN source can be anonymous ftp'd from: info.mcs.anl.gov /pub/pcn/pcn_v2.0.tar.Z The file src/runtime/gc.c is the source for the garbage collector. In addition, while working on the second collector I ran across the following bibliographies, mostly from the comp.compilers news group during the Winter of '92. A. Appel, "Garbage Collection can be Faster than Stack Allocation", Information Processing Letters, 1987. Paul R. Wilson, "Caching Considerations for Generational Garbage Collection", Proc. 1992 ACM Conference on Lisp and Functional Programming, San Francisco, CA, June 27-29. - Check out the bibliography of this paper... The following bibliography was posted to comp.compilers by Paul Wilson (wilson@cs.utexas.edu) in February '92: > @inproceedings{Whit80, > author = "White, Jon L.", > title = "Address/Memory Management For a Gigantic {L}isp Environment, or, {GC} > Considered Harmful", > booktitle = "Conference Record of the 1980 {L}isp Conference", > note = {Redwood Estates, California}, > pages = "119--127", > month = aug, > year = 1980 } > > @article{LiHe83, > author = "Lieberman, Henry and Carl Hewitt", > title = "A Real-Time Garbage Collector Based on the Lifetimes of Objects", > journal = CACM, > volume = 26, > number = 6, > month = "June", > year = 1983 > pages = "419--429"} > > @inproceedings{Moon84, > author = "Moon, David", > title = "Garbage Collection in a Large {L}isp System", > booktitle = "Conference Record of the 1984 {ACM} Symposium on {L}isp and > Functional Programming", > year = 1984, > month = aug, > pages = "235--246", > note = {Austin, Texas} } > > @inproceedings{Mo:AS3600, > AUTHOR = "David A. Moon", > TITLE = "Architecture of the {S}ymbolics 3600", > @inproceedings{Unga84, > author = "Ungar, David M.", > title = "Generation Scavenging: A Non-disruptive High-Performance Storage > Reclamation Algorithm", > booktitle = "Proceedings of the {ACM SIGSOFT/SIGPLAN} Software > Engineering Symposium on Practical Software Development Environments", > month = apr, > year = 1984, > pages = "157--167", > note = "Also distributed as {\em ACM SIGPLAN Notices 19}(5):157--167, > May, 1987" } > > @article{Cour88, > author = "Courts, Robert", > title = "Improving Locality of Reference in a Garbage-Collecting Memory > Management System", > journal = CACM, > volume = 31, > number = 9, > month = Sep, > year = 1988, > pages = "1128--1138" } > > @techreport{Deb:EGCGM, > @inproceedings{WM:OGC, > author = "Wilson, Paul R. and Thomas G. Moher", > title = "Design of the Opportunistic Garbage Collector", > booktitle = OOPSLA89, > note = "New Orleans, Louisiana", > month = Oct, > year = 1989, > pages = "23--35" > } > > @inproceedings{GCandMH, > author = "Wilson, Paul R.", > title = "Some Issues and Strategies in Heap Management and Memory > Hierarchies", > booktitle = "{OOPSLA/ECOOP} '90 Workshop on Garbage Collection in > Object-Oriented Systems", > note = "Also in {\em SIGPLAN Notices 23}(1):45--52, January 1991.", > month = oct, > year = 1990 } > > @inproceedings{DJoh91, > title = "The Case For a Read Barrier", > author = "Douglas Johnson", > booktitle = "Proceedings of the Fourth International Conference on > Architectural Support for Programming Languages and Operating Systems > (ASPLOS IV)", > note = {Santa Clara, CA}, > month = "April", > year = 1991, > pages = "96--107" } > > @inproceedings{Wi:DM, > @inproceedings{StaticGrouping, > author = "Wilson, Paul R. and Michael S. Lam and Thomas G. Moher", > title = "Effective Static-Graph Reorganization to Improve Locality in > Garbage-Collected Systems", > booktitle = "Proceedings of the {ACM} {SIGPLAN} '91 Conference on > Programming Language Design and Implementation", > month = Jun, > year = 1991, > note = {Toronto, Canada}, > pages = "177--191" } > > > @inproceedings{BDS:MPGC, > AUTHOR = "Hans-J. Boehm and Alan J. Demers and Scott Shenker", > TITLE = "Mostly Parallel Garbage Collection", > BOOKTITLE = PLDI, > YEAR = 1991, > PAGES= {157--164} > } > > @techreport{SwizzCAN, > title = "Pointer Swizzling at Page Fault Time: Efficiently Supporting > Huge Address Spaces on Standard Hardware", > author = "Paul R. Wilson", > type = "Technical Report", > number = "UIC-EECS-90-6", > institution = "University of Illinois at Chicago, Electrical Engineering and > Computer Science Department", > address = "Chicago, Illinois", > month = Dec, > year = 1990, > note = "Also in {\em Computer Architecture News}, 19(4):6-13, June 1991"} > > @techreport{WiLM90b, > title = "Caching Consideration For Generational Garbage Collection", > author = "Paul R. Wilson and Michael S. Lam and Thomas G. Moher", > institution = "University of Illinois at Chicago EECS Dept.", > type = "Technical Report", > number = "UIC-EECS-90-5", > address = "Chicago, Illinois", > month = Dec, > year = 1990, > note = "A much improved version will appear in ACM 1992 Conf on Lisp and > Functional Programming. > Technical summary available from wilson@cs.utexas.edu"} |>@inproceedings{Zorn, |>author = "Benjamin Zorn", |>title = "Comparing Mark-and-sweep and Stop-and-copy Garbage Collection", |>booktitle = "Proceedings of the 1990 ACM Conference on Lisp and functional programming", |>abstract = "Stop-and-copy garbage collection has been preferred to |>mark-and-sweep collection in the last decade because its collection time |>is proportional to the size of reachable data and not the memory size. |>This paper compares the CPU overhead and the memory requirements of the |>two collection algorithms extended with generations, and finds that |>mark-and-sweep collection requires at most a small amount of additional |>CPU overhead (3-6%) but requires an average of 20% (and up to 40%) less |>memory to achieve the same page fault rate. The comparison is based on |>results obtained using trace-driven simulation with large Common Lisp |>programs", |>month = june, |>year = 1990 } Kirk Hays (hays@ssd.intel.com) contributed the following on comp.compilers around February 92: > Stamos, J. W. "Static grouping of small objects to enhance performance of > a paged virtual memory" _ACM Trans. Comput. Syst. 2,3 (May 1984), 155-180 > > Stamos, J.W. ""A large object-oriented virtual memory: Grouping, > measurements, and performance." Tech. Rep. SCG-82-2, Xerox, PARC, Palo > Alto, CA, May 1982 > > Zorn, B.G. "Comparative performance evaluation of garbage collection > algorithms." Ph.D. dissertation, Tech. Rep. UCB/CSD 89/544, Univ. of > Calif. at Berkeley, Mar. 1989 And from hosking@cs.umass.edu: @InProceedings{WLM91, author = "Paul R. Wilson and Michael S. Lam and Thomas G. Moher", title = "Effective ``Static-graph'' Reorganization to Improve Locality in Garbage-Collected Systems", crossref = "sigplan91", pages = "177--191" } @INPROCEEDINGS{WM89, crossref = "oopsla89", AUTHOR = "Paul R. Wilson and Thomas G. Moher", TITLE = "Design of the {Opportunistic Garbage Collector}", PAGES = "23--35" } @TechReport{Shaw87, author = "Robert A. Shaw", title = "Improving Garbage Collector Performance in Virtual Memory", institution = "Stanford University", year = 1987, number = "CSL-TR-87-323", month = mar } @PHDTHESIS{Shaw88, AUTHOR = "Robert A. Shaw", TITLE = "Empirical Analysis of a {LISP} System", SCHOOL = "Stanford University", MONTH = feb, YEAR = 1988, NOTE = "Available as Technical Report CSL-TR-88-351" } @INPROCEEDINGS{Ungar84, crossref = "sigsoft84", AUTHOR = "David Ungar", TITLE = "Generation Scavenging: A Non-Disruptive High Performance Storage Reclamation Algorithm", PAGES = "157--167" } @INPROCEEDINGS{UJ88, crossref = "oopsla88", AUTHOR = "David Ungar and Frank Jackson", TITLE = "Tenuring Policies for Generation-Based Storage Reclamation", PAGES = "1--17" } @Book{Ungar87, author = "David Michael Ungar", title = "The Design and Evaluation of a High Performance Smalltalk System", publisher = "The MIT Press", year = 1987, series = "ACM Distinguished Dissertations", address = "Cambridge, MA", note = "Ph.D. Dissertation, University of California at Berkeley, February 1986" } And from Eliot Miranda (eliot@dcs.qmw.ac.uk): > Deutsch, L.P., Bobrow, D.G. 1976, An efficient, incremental, automatic > garbage collector, Comm. ACM, 19(9) pp522-526 > > Baden SB 1983, Low-overhead storage reclamation in the Smalltalk-80 virtual > machine, in Smalltalk-80: Bits of History, Words of Advice, Addison-Wesley, > pp 331-342 > > Miranda, E.E. 1987 BrouHaHa - a portable Smalltalk interpreter, OOPSLA '87, > SIGPLAN Notices 22(12), ACM, pp 354-365 -------------------------------------------------------------------- Steve Tuecke MCS - Bldg 221, Office D-220 Technical Staff Argonne National Laboratory tuecke@mcs.anl.gov (708) 252-8711 Argonne, IL 60439 >From Xli@top.cis.syr.edu Mon Sep 13 13:25:25 1993 Date: Mon, 13 Sep 93 16:24:53 EDT From: Xli@top.cis.syr.edu To: gvg@caleb.ECE.ORST.EDU Subject: garbage collection Content-Length: 165 Status: RO X-Lines: 5 Hi, I did some research on garbage collection a few years ago, and I also implemented my algorithm on Multimax. I will send you a copy of my work. Good luck! Xue Li >From jhummel@esp.ics.uci.edu Mon Sep 13 23:41:20 1993 To: gvg@ENGR.ORST.EDU Subject: Re: Parallel Garbage Collection X-Newsgroups: comp.parallel X-References: <26r644INN6e0@flop.ENGR.ORST.EDU> Reply-To: Joseph Edward Hummel X-Organization: UC Irvine, Department of ICS X-Original-Path: paris.ics.uci.edu!news.service.uci.edu!usc!elroy.jpl.nasa.gov!swrinde!gatech!hubcap!bounce-back Date: Mon, 13 Sep 1993 23:39:14 -0700 From: Joe Hummel Content-Length: 978 X-Lines: 28 Status: RO In article <26r644INN6e0@flop.ENGR.ORST.EDU> you write: >I am implementing a simulated Parallel Smalltalk system, and one of the >things I am going to have to implement is Garbage Collection. >Unfortunately, our library seems to lack good information on the topic. >Is there anybody out there in net-land who has a good bibliography >on parallel garbage collection (or just plain garbage collection), >or knows of FTP sites or other places to get papers on the subject. > >I will post a summary of responses. > >Thanks. > >-------------------------------------------------------------------------- >Greg Gritton >gvg@caleb.ece.orst.edu > >...Microfala Ganara... > Don't have a complete bib, but I do know there was a paper in this year's Ppopp (principles and practice of parallel programming, an ACM conf) on parallel garbase collection. The people are from U of Wisconsin, paper might even be available via TR form. Paper should refer to previous work. Cheers, - joe >From @vm.urz.Uni-Heidelberg.de:dentzer@polyhymnia.iwr.uni-heidelberg.de Tue Sep 14 00:17:44 1993 Date: Tue, 14 Sep 93 09:23:40 +0200 From: dentzer@polyhymnia.iwr.uni-heidelberg.de (Ralf Dentzer) To: gvg@caleb.ECE.ORST.EDU Subject: parallel garbage collection Content-Length: 591 X-Lines: 22 Status: RO Dear Greg! There was an article in the ACM Trans. on Prog. Lang. and Systems, Vol. 15, No. 1, Jan. 1993 by G. Tel and F. Mattern with a slightly different subject that contains a good overview of distributed GC techniques: "The derivation of distributed termination detection algorithms from garbage collection schemes." I would be interested in other answers to your question, could you please let me know in case you don't post a summary? Bye Ralf Ralf Dentzer IWR, University of Heidelberg Im Neuenheimer Feld 368 D-6900 Heidelberg, Germany dentzer@kalliope.iwr.uni-heidelberg.de >From tls@dcs.ed.ac.uk Tue Sep 14 03:44:03 1993 From: tls@dcs.ed.ac.uk Date: Tue, 14 Sep 93 11:40:30 BST To: Gritton Gregory Vance Subject: Re: Parallel Garbage Collection Cc: bernard@laas.fr Content-Length: 1278 X-Lines: 39 Status: RO A very good recent workshop on this subject is: @book{IWMM92, title = "Memory Management", series = "{LNCS}", publisher = "Springer-{Verlag}", year = 1992, month = "September", editor = "Y. Bekkers and J. Cohen", volume = 637, note = "Proceedings of International Workshop IWMM 92, St. Malo, France"} You can get a copy of our paper by anonymous ftp at laas.laas.fr in pub/lcs/reports/iwmm92.ps.Z @inproceedings{Les92aGC, author = "Thierry {Le Sergent} and Bernard Berthomieu", title = "Incremental Multi-threaded Garbage Collection on Virtually Shared Memory Architectures", booktitle = "Memory Management", series = "{LNCS}", volume = 637, month = "September", pages = "179--199", year = 1992, publisher = "Springer-{V}erlag", note = "Rapport de Recherche LAAS-CNRS 92077"} Cheers, -- =========================================================================== Thierry LE SERGENT LFCS - Dept. of Computer Science - University of Edinburgh King's Buildings - Mayfield road Edinburgh - EH9 3JZ - United Kingdom e-mail:tls@dcs.ed.ac.uk - Ph: +44-31-650-5140 - Fax: +44-31-667-7209 =========================================================================== >From kseah@cs.utexas.edu Tue Sep 14 06:50:17 1993 From: kseah@cs.utexas.edu (Kenneth Cheng-Lim Seah) Date: Tue, 14 Sep 1993 08:49:16 -0500 Organization: ESCware Associates X-Mailer: Mail User's Shell (7.2.3 5/22/91) To: gvg@caleb.ECE.ORST.EDU Subject: Parallel/Distributed GC Content-Length: 152 X-Lines: 3 Status: RO Hi Greg, Try the University of Texas ftp site. We're at anon-ftp on ftp.cs.utexas.edu and look in the pub/garbage directory. Hope this helps -- Ken >From nat@sybase.com Wed Sep 15 10:51:28 1993 Date: Wed, 15 Sep 93 10:51:18 PDT From: nat@sybase.com (Nat Wyatt) To: gvg@ENGR.ORST.EDU (Gritton Gregory Vance) Subject: Re: Parallel Garbage Collection Content-Length: 470 X-Lines: 17 Status: RO at cs.utexas.edu there's a couple of papers in pub/garbage: gcsurvey.ps, and dgcsurvey.ps. they don't cover parallel garbage collection but they do cover garbage collection in general. i am interested in this topic myself so if you manage to scare up any information i'd appreciate it if you could pass it along to me. thanks, nat -- Nat Wyatt nat@sybase.com Sybase, Inc., 6475 Christie Ave., Emeryville CA 94608, (510) 596-3500 >From herlihy@crl.dec.com Thu Sep 16 13:52:43 1993 Date: Thu, 16 Sep 93 16:52:34 -0400 From: herlihy@crl.dec.com To: gvg@ENGR.ORST.EDU (Gritton Gregory Vance) Subject: Re: Parallel Garbage Collection Content-Length: 187 X-Lines: 6 Status: RO A parallel GC algorithm is described in CRL Tech Report 90/9. To get a postscript copy, send the word ``help'' to techreports@crl.dec.com and follow the instructions. Maurice Herlihy