Group: People Projects Publications Seminars Events Wiki Grants PhD studentships Themes: Concurrency Dependability and testing Distributed systems Memory management Mobile systems Projects: AQuest BlueJ C++CSP CHP Collaborative Testing CoSMoS CSProjects EPOCH GCspy Greenfoot GROK ImmuneFT ImmuneSensors JCSP jctld Juniper KRoC LACE LAHN MM-Net MobiComp NOCC Occam-pi on LEGO occlipse RMoX The Transterpreter Tock TUNA UK Mirror Service

Systems Architecture Research Group: Grants

Visiting Researcher: Dr. Tony Hosking

Principal Investigator: Mr. 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: Mr. 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.

TUNA: Theory Underpinning Nanotech Assemblers

Principal Investigator: Prof. Susan Stepney (York), Co-Investigators: Prof. Peter Welch (Kent), Dr. Fiona Polack (York), Prof. Jim Woodcock (York), Prof. Steve Schneider (Surrey), Dr. Helen Treharne (Surrey), Dr. Ana Cavalcanti (York). Value: £60,867. Funded by: EPSRC grant EP/C516966/1.

Nanites are tiny robots, with components that can be one billionth of a metre in size, and which cooperate to cause macroscopic effects; nanotech assemblers are nanites that build things atom by atom. We will study the feasibility of developing huge collections of nanites that behave safely. We face the following challenges. (1) To look at ways of building computer models of nanites, how they communicate with each other, and how they may be controlled. (2) To find ways of knowing when our models of nanites do what they are supposed to do. (3) To work out what resources are needed to run these models on a computer. (4) To suggest ways that lawyers and experts can be certain that that these nanites work safely. In carrying out these investigations, we plan to use models of nanites that work like artificial blood cells, and we will study how they stop cuts bleeding. The really interesting thing about these artificial blood cells is that they are very simple, and yet they work together to do something that is very complicated. It is impossible to see from one nanite what hundreds of thousands of them will do when they work together. So, we will simulate their behaviour on a network of computers to see if we have got the ideas right and to make sure that they work safely. There has been a lot of work on the construction of advanced devices based on collections of nanites, but no effort has been made into assuring their safety. We propose to make a contribution on this area.

Internal users: additional information on the grants currently held by the systems architecture group can be found here.