© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Programming Languages and Systems: Grants
A High-Level Paradigm for Reliable Large-Scale Server Software
Principal Investigator: Professor Simon Thompson. Value: £2,000,000. Funded by: EU-FP7 grant 287510.
MirrorGC: Garbage Collection for Multicore Systems
Principal Investigator: Professor Richard Jones, Co-Investigator: Dr. Fred Barnes. Value: £367,637. Funded by: EPSRC grant EP/H026975/1.
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.
Visiting Researcher: Dr. Tony Hosking
Principal Investigator: Professor Richard Jones. Value: £26,456. Funded by: EPSRC grant EP/F06523X/1.
The growing use of object-oriented languages like Java and C# in substantial applications of commercial import has made automatic dynamic memory management, or 'garbage collection' (GC), more important economically than ever before. GC allows programs to recycle unused memory automatically, without error-prone programmer intervention. Significant research challenges remain in this area as new software developments push state-of-the-art collectors to their limits in terms of scalability and responsiveness. Meanwhile, commodity multi-threaded, multi-core, and multi-processor hardware make scalability and responsiveness even more critical, as applications look to exploit increasingly available thread-level parallelism. Desktop platforms and applications make different demands on garbage collection than server class applications, so further research is needed to reconcile existing concurrent collector techniques to these demands. Moreover, new approaches to concurrency control based on non-blocking synchronization, and transactional memory (TM) hardware, are enabling finer-grained synchronization of GC activities along with improved locality for shared state. In particular, concurrent collectors have until recently focused on "non-moving" collection techniques that avoid relocating live objects, so as to minimize the need for synchronization between the collector and mutators. Unfortunately, non-moving collectors are unable to compact the heap to avoid fragmentation and increase heap utilization. It is this problem that will be addressed by this work, reconciling compaction with concurrency.
This project brings together Jones (University of Kent) and Hosking (Purdue University), two internationally leading researchers in the field of memory management. Dr Hosking has a unique combination of expertise in GC, transactional memory, concurrency, and mutator-collector synchronization. He is PI or co-PI on grants, supported by IBM, Sun Microsystems, Microsoft, Intel, and the USA's National Science Foundation, totalling several million dollars cumulatively, including the successful DaCapo project, www.dacapo-group.org, rated as the "best GC research group in the USA, if not the world" by the NSF. This work will build on his expertise and that of his UK-based colleagues both to understand better how to construct concurrent collectors for multi-core platforms and to disseminate widely this expertise and experience. We plan to improve understanding of concurrent garbage collection for multi-core platforms by (a) developing a uniform platform for comparing different concurrent GC approaches on multi-core platforms; (b) adding transactional memory mechanisms and support; and (c) exploiting TM mechanisms in support of concurrent garbage collection and heap compaction. As well as dissemination through the usual vehicles of journals and conferences, we shall also contribute the software developed back to the open source Jikes RVM project so that they are freely available. In addition, we shall take advantage of Dr Hosking's visit to disseminate his expertise in transactional memory to UK researchers through a seminar series at the University of Kent, open to all, and short visits to other institutions. We plan to make these seminars available to all through multimedia recordings available from the University of Kent web site. Finally, we shall write a new book on advanced GC. Jones's 1996 book has long remained the definitive book on the subject, but there have been many developments over the last eleven years. We anticipate that the new book will be an essential resource for researchers, developers and students. Concurrent GC will be a particular focus of the book.
Visiting Researcher: Dr. Tony Hosking
Principal Investigator: Professor Richard Jones. Value: £26,456. Funded by: EPSRC grant EP/F06523X/1.
The growing use of object-oriented languages like Java and C# in substantial applications of commercial import has made automatic dynamic memory management, or 'garbage collection' (GC), more important economically than ever before. GC allows programs to recycle unused memory automatically, without error-prone programmer intervention. Significant research challenges remain in this area as new software developments push state-of-the-art collectors to their limits in terms of scalability and responsiveness. Meanwhile, commodity multi-threaded, multi-core, and multi-processor hardware make scalability and responsiveness even more critical, as applications look to exploit increasingly available thread-level parallelism. Desktop platforms and applications make different demands on garbage collection than server class applications, so further research is needed to reconcile existing concurrent collector techniques to these demands. Moreover, new approaches to concurrency control based on non-blocking synchronization, and transactional memory (TM) hardware, are enabling finer-grained synchronization of GC activities along with improved locality for shared state. In particular, concurrent collectors have until recently focused on "non-moving" collection techniques that avoid relocating live objects, so as to minimize the need for synchronization between the collector and mutators. Unfortunately, non-moving collectors are unable to compact the heap to avoid fragmentation and increase heap utilization. It is this problem that will be addressed by this work, reconciling compaction with concurrency.
This project brings together Jones (University of Kent) and Hosking (Purdue University), two internationally leading researchers in the field of memory management. Dr Hosking has a unique combination of expertise in GC, transactional memory, concurrency, and mutator-collector synchronization. He is PI or co-PI on grants, supported by IBM, Sun Microsystems, Microsoft, Intel, and the USA's National Science Foundation, totalling several million dollars cumulatively, including the successful DaCapo project, www.dacapo-group.org, rated as the "best GC research group in the USA, if not the world" by the NSF. This work will build on his expertise and that of his UK-based colleagues both to understand better how to construct concurrent collectors for multi-core platforms and to disseminate widely this expertise and experience. We plan to improve understanding of concurrent garbage collection for multi-core platforms by (a) developing a uniform platform for comparing different concurrent GC approaches on multi-core platforms; (b) adding transactional memory mechanisms and support; and (c) exploiting TM mechanisms in support of concurrent garbage collection and heap compaction. As well as dissemination through the usual vehicles of journals and conferences, we shall also contribute the software developed back to the open source Jikes RVM project so that they are freely available. In addition, we shall take advantage of Dr Hosking's visit to disseminate his expertise in transactional memory to UK researchers through a seminar series at the University of Kent, open to all, and short visits to other institutions. We plan to make these seminars available to all through multimedia recordings available from the University of Kent web site. Finally, we shall write a new book on advanced GC. Jones's 1996 book has long remained the definitive book on the subject, but there have been many developments over the last eleven years. We anticipate that the new book will be an essential resource for researchers, developers and students. Concurrent GC will be a particular focus of the book.
CoSMoS: Complex Systems Modelling and Simulation
Principal Investigator: Professor Peter Welch, Co-Investigator: Dr. Fred Barnes. Value: £398,058. Funded by: EPSRC grant EP/E049419/1.
Our project will build capacity in generic modelling tools and simulation techniques for complex systems, to support the modelling, analysis and prediction of complex systems, and to help design and validate complex systems. Drawing on our state-of-the-art expertise in many aspects of computer systems engineering, we will develop CoSMoS, a modelling and simulation process and infrastructure specifically designed to allow complex systems to be explored, analysed, and designed within a uniform framework.
CoSMoS will comprise: a modelling and analysis process, based on computational concepts such as class, state, behaviour, and communication, and on complex system emergent properties, expressed in part as rich argumentation, modelling, analysis, and refactoring Pattern Languages; a massively parallel and distributed simulation environment, based on CSP and system modelling technologies that encompass a wide range of process granularities, targeted to the specific properties of complex systems: vast numbers of (relatively) simple agents interacting and communicating in parallel, in an (often stigmergic) environment. The development of CoSMoS will be case study driven, to ensure that it contains the necessary generic components, and so that several iterations of the method and toolset, of increasing functionality and applicability, can be produced and validated.
A Framework for Lightweight, Flexible and Concurrent Operating Systems
Principal Investigator: Dr. Fred Barnes. Value: £210,405. Funded by: EPSRC grant EP/D061822/1.
The operating-system (OS) is a core software component of many computer platforms, responsible for managing the hardware and software involved. These come in a wide assortment of shapes and sizes, from small operating-systems for embedded devices (e.g. engine management systems, mobile-phones, PDAs), through general-purpose OSs for desktop computing, and on to large operating-systems that run massively parallel or distributed supercomputers. Despite the critical nature of an operating-system, many of those currently available today suffer from various problems. From the user's perspective, the most notable of these problems is one of incorrect implementation -- bugs in the operating-system leading to strange/undefined behaviour, or even complete failure.
This project sets out to solve many of the existing problems associated with operating-systems by taking a different approach to their design and implementation. Instead of being mostly sequential code, concurrency will be utilised at the lowest level yielding operating-systems built from of thousands of individual, communicating processes. To guarantee that such systems will work correctly, we turn to formal methods. In particular Hoare's CSP and Milner's pi-calculus process algebras, as engineered into the occam-pi programming language and design tools (which will be further developed as part of this research). This provides a sound model of concurrency, capable of scaling to millions of processes whilst avoiding race-hazards, aliasing errors and deadlock. The overall goal of the project is to produce a "tool-kit" of operating-system software components, together with the necessary design tools, to develop systems for the PC/104 range of embedded hardware. Given that the PC/104 architecture is based on that of the IBM PC, much of the research will be reusable in the future for developing operating-systems for commodity desktop PCs.
LACE: Lifetime-Aware Collection
Principal Investigator: Professor Richard Jones, Co-Investigator: Dr. Andy King. Value: £278,032. Funded by: EPSRC grant EP/D078342/1.
The growing use of object-oriented languages like Java and C# in substantial applications of commercial import has made automatic dynamic memory management, or 'garbage collection' (GC), more important economically than ever before. GC allows programs to recycle unused memory automatically, without error-prone programmer intervention. Significant research challenges remain in this area as new environments - from multi-processor servers to hand-held devices - push state-of-the-art collectors to their limits in terms of scalability and responsiveness. Although today's state of the art collectors can meet users' throughput and pause time requirements in heaps of up to many hundred megabytes, current techniques will not scale to the tens of gigabytes heaps that Java virtual machine vendors expect their customers to demand in the near future.
Much GC effort is, in a sense, wasted. Rather than reclaiming memory directly (which is what the programmer wants), GC expends effort on preventing the premature and unsafe reclamation of space used by live objects. It has long been known that programs' 'object demographics' are not random. Rather objects are allocated, interact and die in particular patterns. We believe that understanding and exploiting this regularity is the key to the next generation of program-directed memory management. In order to reduce the cost of discovering live objects ('tracing'), GC must concentrate effort on those regions of the heap in which few objects are live.
Our vision is for a Lifetime-Aware GC framework (LACE) that takes advantage of predictable program behaviour in order to collect only regions of the heap in which we expect the vast majority of objects to be dead. Our preliminary research shows that the number of distinct behaviour patterns are small enough to be mapped onto a region-based memory manager such as Beltway. LA is a new paradigm for allocation and collection. First, it never attempts to reclaim an object before its estimated death-time, whereas conventional 'generational' collectors process even the very newest objects although they are almost certain to be live. Second, long-lived objects must be examined (copied) at least once by a generational collector, but LA collection avoids touching them until they are expected to be dead. Third, to reclaim long-lived objects, a generational GC must collect not only the region of memory holding the object but all younger objects as well; LA collection processes objects of any age independently.
We plan to build a novel LA heap structure over our Beltway GC framework. We shall explore the object demographics of realistic Java programs through a combination of off-line analysis of program traces, static analysis of program code and run-time sampling in order to identify suitable policies for LA collection. We shall construct new LA collectors that use these policies to the ends described above; we expect significant improvements over existing systems in both throughput - how fast the program executes - and pause-times - brief intervals during which the progam is interrupted to allow the GC to reclaim unused memory. We shall make our analysis tools and the LA collector framework freely available, e.g. through our website and the UK Memory Management Network (MM-NET). As well as dissemination through the usual vehicles of journals and conferences, a mid-project workshop on analytic support for memory management will be held through the auspices of MM-NET.