Garbage Collection for Multicore Platforms

Developers are increasingly turning to languages like Java and C# for their ease of development, deployment and maintenance. Most applications for the foreseeable future will be written in languages supported by managed runtimes, running on multicore hardware. Particular benefits of managed runtimes include support for automatic dynamic memory management, or 'garbage collection' (GC) and threads. GC allows programs to recycle unused memory automatically, without error-prone programmer intervention. Threading allows a program to run different sequences of instructions in parallel; for instance, a web server might employ a separate thread for each incoming request from internet browsers.One of the most significant recent developments for language implementers is the development of multicore processors, with the number of cores deployed in commodity platforms expected to increase significantly over the next 5 years. The complexity of the processor's access to memory has also increased, in terms of levels of memory hierarchy and in the technology interconnecting processors. However, modern runtime technology has not evolved as fast as hardware technology, and how to fully exploit hardware parallelism remains an open question.This research asks, how can we exploit hardware parallelism, in particular by running multiple user program ('mutator') and GC threads? How can we avoid paying penalties for non-local memory access, but still benefit from multiple paths to memory? How can we take proactive advantage of locality properties? How can we minimise synchronisation between mutator and GC threads?Today's concurrent GC techniques avoid relocating live objects, so as to minimise the need for this synchronisation, but this leads to poor use of memory with many small holes but nowhere to accommodate larger objects ('fragmentation'). The standard fragmentation solution - periodic compaction phases - has high overheads, and often lacks portability or leads to throughput slumps before mutator threads can operate at full speed again. Memory management will be a bottleneck for the next generation of increasingly thread parallel software unless the problem of high performance GC for multicore can be solved. This proposal aims to address this key problem, reconciling compaction with concurrency and performance.We believe that the key to exploiting modern multicore architectures is a judicious division of effort between mutator and GC threads, in order not simply to avoid paying the price of accessing non-local memory, but proactively to process data while it is in the cache. It is almost always worth paying the cost of executing a few more instructions in order to avoid accessing non-local data. Thus, if a mutator thread is about to access data (and hence it is or soon will be in the cache), it should perform some GC work on that data immediately. Other data should be left to be handled by separate GC threads. At no time should all mutator threads be halted waiting for the collector. Our aim is therefore to provide high throughput and very low pauses, by utilising parallel copying collector threads, running concurrently and carefully coupled with mutators in order to leverage locality.This research will benefit GC researchers by broadening the design space and devising and evaluating new concurrent GC techniques, and developers in the broad community through enabling them to tune their applications and GCs to modern architectures. A high-performance GC tuned to modern multicore hardware will also lower the barrier to deployment of future software applications that expect to exploit multicore hardware fully. We will make all code developed freely available under an Open Source license. As well as disseminating our results through journals and conferences, we shall organise two workshops in order to build UK research strength in this field.

The ubiquitous platform for the medium term future (say, the next ten years) will almost certainly be multicore, multi-socket, hardware executing a managed runtime for a language like Java or C#. Such hardware is already ubiquitous on modern desktops and laptops, and will soon appear in more mobile markets (netbooks, high-end phones). It is essential that the next generation of runtimes, such as Java virtual machines in general and their memory management subsystems in particular, can fully exploit the hardware parallelism on offer in order to provide a better experience for end users. JikesRVM is the most widely used platform for research into the implementation of Java Virtual Machines. Currently, JikesRVM/MMTk provides no support for concurrent collectors. If successful, the research proposed here will open up the design space of concurrent, copying collectors. It will also provide a platform for further GC research, by embodying the knowledge gathered into a redesigned MMTk toolkit for building GCs. The 2008 CPHC study of the IT labour market in the UK revealed that, while employers need more technical staff (and IT managers), the supply of computer science graduates is falling, putting the UK's position in the IT industry at risk. A supply of highly skilled, human capital to UK technology companies is essential. This project will train a research assistant and a PhD student, thus contributing to the UK's skills base. We plan to disseminate the results of our research in a variety of effective and appropriate ways. The PI has a track record of promoting research and exchange of ideas. He is author of the definitive book on GC, co-founded the International Symposium on Memory Management, co-established ACM SIGPLAN/EAPLS Semantics, Program Analysis and Computing Environments for memory management as a regular workshop series, edited a special issue on memory management of the journal Science of Computer Programming, and maintains the widely used online GC bibliography, www.cs.ukc.ac.uk/~rej/gcbib/gcbib.html. Coordinating the UK Memory Management Network (GR/R57140), he regularly brings together academic and industrial researchers and developers. The intensity of interest in this area was exemplified by the oversubscribed 2008 Workshop on Language and Runtime Support for Concurrent Systems, which attracted attendees from the UK, Europe and the USA. This proposal plans two further workshops on the same theme, which will provide an opportunity not only for researchers to exchange ideas but will also build UK research strength in this field.