|
|||
|
Systems Architecture Research Group: Seminars
Upcoming seminars
No seminars currently planned
Past seminars
Dynamic Evolution of Software Architectures using Aspects
Mr. Cristóbal Costa, Dapartment of Information Systems and Computation, Polytechnic University of Valencia (Spain)Tuesday 25th August 2009, 16:00 - 17:00, SW101
Nowadays, software systems are more and more complex. This entails that such systems must frequently undergo subsequent revisions in order to correct errors or to add new unforeseen functionalities. However, the intrinsic nature of some systems makes unfeasible their stopping to integrate changes (i.e. critical or autonomous systems). It is while using (and maintaining) such kind of systems when the need for dynamic evolution emerges.
Software architecture provides a good abstraction level to describe such complex systems, in terms of architectural elements (components and connectors) and their interrelations (attachments). Dynamic evolution can be of two kinds, depending on what is changed: the architecture configuration, or the types that compose this architecture. The first kind of evolution, called dynamic reconfiguration, enables a software architecture to change its configuration (i.e. structure) at runtime. This is frequently used to provide systems with fault-tolerance mechanisms or context-adaptations. The second kind of evolution, called dynamic evolution of architectural types allows either a software architecture or a single architectural element to change completely its type (i.e. its specification) at runtime. This kind of dynamism supports the introduction of new architectural element types and connections, the removal of existing element types, or the modification of the way that the different types interact. That is, it supports changing both the composition and behaviour of the software architecture while it is running.
In addition to support the dynamic evolution of software architectures, the maintainability and reuse of both the evolution specifications and mechanisms must be taken into account. The former are dependent on each concrete architecture, whereas the latter are dependent on the underlying technological platform. For this reason, we have isolated these concerns by using aspects, in a way to improve the modularity of the evolvable systems and make easy its design and building.
R, CXXR and Provenance Tracking
Mr. Chris Silles, Computing Laboratory (homepage) and Dr. Andrew Runnalls, Computing Laboratory (homepage)Thursday 25th June 2009, 16:00 - 16:30, S110B
This seminar is mainly an opportunity for Chris Silles to have a dry-run of a talk 'Provenance Tracking in CXXR' that he is presenting at the useR! 2009 conference in July, in which he will describe his work on adapting the R/CXXR interpreter to track the provenance of data objects, and relate this to the increasing interest in data provenance in other fields of computing.
Before this, Andrew Runnalls will give a brief introduction to the R language for statistical computing, and describe his work on CXXR, an experimental version of the R interpreter in which the current C code is being progressively refactored into C++. This will include material he will be presenting at the upcoming conference on Directions in Statistical Computing, DSC2009.
Homicidal Code: Static Detection and GC Exploitation
Mr. Robert Bunyan, Computing Laboratory (homepage)Thursday 11th June 2009, 14:00 - 14:30, S110B
Generational Garbage Collection handles short-lived objects very successfully, but does less well with longer lived objects, which may either be processed many times or are left in older generations long after they are dead, thereby wasting space. Ideally, a generational collector should process an object only once. We propose to improve generational garbage collection by guiding the collector to areas of the mature space that contain a high proportion of dead objects which can be collected without a full heap collection. We use a static analysis to find groups of allocations sites that create objects that may die together and identify program statements ('kill points') that overwrite reference to these objects. By grouping objects that share kill points, and monitoring kills executed, we can detect the phase change behaviour of a group of objects and guide the collector's attention to regions of the mature space expected to yield the most free space.
A Framework for Debugging Barriers in Concurrent Systems
Mr. Laurence Hellyer, Computing Laboratory (homepage)Thursday 11th June 2009, 14:30 - 15:00, S110B
Read and write barriers are used within managed language runtimes to achieve a number of desirable effects. These runtimes can be complex and it is difficult to ensure that all memory operations are correct. A direct memory operation bypassing a barrier may cause an error that is not detectable until much later. This talk demonstrates a novel framework that (i) Ensures all desired memory operations go via a barrier, (ii) If a non-conforming operation occurs the error is immediate allowing for timely debugging, (iii) The overhead of this framework is only incurred when required and still allows good developer productivity.
Optimising Disk Performance for Virtualised Systems: CO620 project presentation
Mr. Andrew Cassidy, CO620 project studentThursday 7th May 2009, 16:00 - 16:30, S110B
Virtualisation is increasingly used to leverage available computing power, sharing the resources of a single physical system between multiple virtualised computing environments, primarily for reasons of cost. However, this increased sharing leads to increased contention. In a virtualised environment, this can result in a situation where many or all virtualised systems are stalled, waiting for requests on the underlying physical disk to complete.
This presentation will cover the ideas and underlying technologies used in the development of a simple disk reorganisation framework, with an aim to reduce these problems.
Towards the use of Dynamic Workflows for Coordinating Self-adaptation of Software Systems
Mr. Carlos da Silva, Computing Laboratory (homepage)Thursday 30th April 2009, 16:00 - 16:20, S110B
The self-adaptation of software system is a complex process that depends on several factors that may change during the system operational lifetime. Hence, the process for coordinating the self-adaptation should also be adaptable to changes that may occur during run-time. As the means for coordinating the self-adaptation process of software systems, we are applying workflows that are dynamically generated for dealing with the variability associated with the self-adaptation process. In this context, this research aims to define and develop techniques for automatically generate workflows for coordinating the self-adaptation of software systems. For demonstrating the feasibility of the proposed approach, architectural reconfiguration of software systems is used as an example, whereby the reconfiguration is managed by workflows that are dynamically generated depending on the availability of resources.
This is a 10 minutes talk, followed by questions and suggestions, as a rehearsal for a talk at the ICSE 2009 Doctoral Symposium on the end of May.
A Review of Current Compile Time Garbage Techniques
Mr. Robert Bunyan, Computing Laboratory (homepage)Thursday 2nd April 2009, 16:00 - 17:00, S110B
One of the main arguments against using garbage collection (GC), as opposed to explicit memory management, is the runtime costs garbage collection incurs, both in memory overhead and execution time. However, explicit memory management has its own set of problems, including memory leaks and an increased load on the programmer. Compile-time GC aims to remove the overheads of GC while retaining its advantages over explicit memory management.
This talk will cover three types of current compile-time GC: region based memory management, compile-time stack allocation and the automatic insertion of free statements.
Large Scale Ad-Hoc Networks
Dr. Gareth Owen, Computing Laboratory (homepage)Thursday 19th March 2009, 16:00 - 17:00, S110B
Ad hoc wireless networks are formed of many nodes and require no preexisting configuration to take advantage of any possible routes for packets. Routing in such networks can be challenging and fraught with problems, ranging from capacity limitations to route discovery difficulties. This talk will examine some of the challenges in this field, existing approaches to solving them and future directions. Particularly I will talk about very large networks which may in future facilitate ubiquitously computing, vehicular traffic information systems, etc.
Using workflows for coordinating self-adaptation of software systems
Mr. Carlos da Silva, Computing Laboratory (homepage)Thursday 11th December 2008, 16:00 - 17:00, S110B
Self-adaptive software systems can configure and reconfigure themselves to deal with faults, changing of requirements or/and operational environment and resource variability. Workflow management technology coordinates and controls the flow of work and information associated to a process. In the context of self-adaptive software systems, workflow management technology can be used to coordinate the process of self-adaptation. Since this process depends on the system requirements, the system operational state and its environment, which may change during its operation, the process for coordinating the self-adaptation should also adapt depending on the changes that may occur. Thus, to deal with this variability, the workflows that coordinate this process need to be dynamically generated.
In this context, our aim is to design and develop mechanisms for automatic workflow generation for coordinating self-adaptation of software systems. As a case study, we have developed a web service application that relies on the dynamic reconfiguration of its architecture for the provision of dependable services.
Modelling dimensions for self-adaptive software systems
Dr. Rogerio de Lemos, Computing Laboratory (homepage)Thursday 20th November 2008, 16:00 - 17:00, S110B
Software's ability to adapt at run-time to changing user needs, system intrusions or faults, changing operational environment, and resource variability has been proposed as a means to cope with the complexity of today's software-intensive systems. Such self-adaptive systems can configure and reconfigure themselves, augment their functionality, continually optimize themselves, protect themselves, and recover themselves, while keeping most of their complexity hidden from the user and administrator.
In this talk, we present, from the perspective of software engineering, what are the current challenges in the field, and we discuss a classification of modelling dimensions for self-adaptive software systems. Each modelling dimension describes a particular facet of the system that is relevant to self-adaptation. The modelling dimensions provide the engineers with a common set of vocabulary for specifying the self-adaptive properties under consideration and select suitable solutions.
Generics in Small Doses: Part of TCS's Fun in the Afternoon
Mr. Adam Sampson, Computing Laboratory (homepage)Monday 17th November 2008, 16:30 - 17:00, SW101
Tock is a new compiler for concurrent imperative programming languages, designed using nanopass techniques. Nanopass compilers transform a program from source code to the target form through the application of a series of transformation passes. Because these passes are usually small and self-contained, the resulting compiler is highly modular, and easy to test and extend. We describe the generic programming interface that we have designed for building nanopass compilers in Haskell, and show how it can be implemented efficiently by combining techniques from the "Scrap Your Boilerplate" and Uniplate generic programming systems. The resulting generics system supports operations upon multiple types without recourse to runtime type introspection.
The Manticore project
Professor John Reppy, University of ChicagoTuesday 11th November 2008, 16:00 - 17:00, SW101
The Manticore project is an effort to design and implement a new language for parallel programming. Our primary motivation is to move parallel programming out of its traditional application areas, such as Scientific Computing, and into a broader range of applications running on commodity hardware. To achieve that goal, Manticore is a heterogeneous language that supports parallelism at multiple levels. We start with a strict functional core (essentially a mutation-free subset of SML) and extend it with both fine-grain implicitly-threaded parallel constructs and course-grain explicit concurrency. To support heterogeneous parallelism, we have developed a novel scheduling architecture. This talk will give an overview of the project, describe our scheduling infrastructure, and discuss some of the aspects of the implementation.
John Reppy has been studying issues in language design and implementation for twenty years. His work includes the invention of Concurrent ML, co-inventor of the Moby programming language, major contributions to the Standard ML of New Jersey system, and co-editing of the Standard ML Basis Library specification. He received his PhD from Cornell University in 1992 and worked at Bell Laboratories, Murray Hill for eleven years. He is currently a Professor at the University of Chicago.
Software TM
Dr. Tony Hosking, Computing Laboratory (homepage)Thursday 6th November 2008, 16:00 - 17:00, SW101
Transactional Memory has become a "hot" topic these days, as the now prevalent multi-core chips force revisiting support for parallel programming. I will survey some of the recent advances in TM, looking at both hardware and software solutions, and examining the gulf that still needs to be bridged between what hardware manufacturers plan to provide and what software abstractions will demand. The first of these talks will focus on hardware support, using the well-regarded Wisconsin LogTM architecture as a case study. The second talk will look at the programming abstractions that are being proposed for writing transactional programs, and how these abstractions map to the existing hardware, and where hybrid hardware/software techniques are needed.
This seminar is part of the Tony Hosking Seminar Series.
Language Extensions for Open Nested Transactions
Dr. Tony Hosking, Computing Laboratory (homepage)Tuesday 4th November 2008, 16:00 - 17:00, SW101
We are seeing many proposals supporting atomic transactions in programming languages, software libraries, and hardware, some with and some without support for nested transactions. In the long run, it is important to support nesting, and to go beyond closed nesting to open nesting. I will argue as to the general form open nesting should take and why, namely that it is a property of classes (data types) not code regions, and must include support for programmed concurrency control as well as programmed rollback. I will also touch on the implications for software or hardware transactional memory in order to support open nesting of this kind. I will describe a concrete proposal for open nested transactions in Java. We argue that open nesting is most usefully seen as a way to express concurrency abstractions at different levels or granularities within (layered) data structures. To support this, we specify open nesting as a property of the class in Java, since the class is the principal data abstraction mechanism for Java programmers. Concurrency abstractions based on open nesting relax physical (memory-level) serializability while preserving abstract serializability. Abstract serializability is specified by the programmer in terms of abstract locks, which are associated with each of the operations (i.e., methods) operating at a given abstraction level (i.e., class), to specify the logical conflicts among concurrently executing operations. Abstract locks come with a predefined compatibility matrix used by the run-time system to mediate execution of these operations. We will describe the syntax and semantics of open nested classes for Java, and explore the power of the approach with an example. We will also point out possible pitfalls for programmers using open nesting, and discuss rules of thumb for programmers to use to avoid these problems.
This seminar is part of the Tony Hosking Seminar Series.
Hardware TM
Dr. Tony Hosking, Computing Laboratory (homepage)Thursday 30th October 2008, 16:00 - 17:00, SW101
Transactional Memory has become a "hot" topic these days, as the now prevalent multi-core chips force revisiting support for parallel programming. I will survey some of the recent advances in TM, looking at both hardware and software solutions, and examining the gulf that still needs to be bridged between what hardware manufacturers plan to provide and what software abstractions will demand. The first of these talks will focus on hardware support, using the well-regarded Wisconsin LogTM architecture as a case study. The second talk will look at the programming abstractions that are being proposed for writing transactional programs, and how these abstractions map to the existing hardware, and where hybrid hardware/software techniques are needed.
This seminar is part of the Tony Hosking Seminar Series.
Implementing Choice: Communicating Haskell Processes
Mr. Neil Brown, Computing Laboratory (homepage)Tuesday 14th October 2008, 15:00 - 15:20, S110B
This talk will outline a "process-oriented" concurrency model centred around encapsulated processes communicating over synchronous channels. We will explain how the ability to choose between communicating on different channels can be very useful, including choosing between different conjoined sets of channel communications. We will give an overview of how this choice has been implemented with Software Transactional Memory.
Communicating Haskell Processes: implementing CSP ideas in Haskell
Mr. Neil Brown, Computing Laboratory (homepage)Thursday 19th June 2008, 16:00 - 17:00, SW101
Haskell: all-singing, all-dancing higher-order monadic imperative sequential functional lazy language with class. occam-pi: massively-concurrent sequential choice-filled programming. This talk describes what happened when we mixed the two and implemented occam-pi ideas in Haskell using Software Transactional Memory. The simple interface of the resulting library can provide inspiration for future concurrent language design. Haskell's declarative style and higher-order functions allow concurrent programs to be composed more elegantly than in existing languages. We will also explain how to implement multiway synchronisation that any party may withdraw from using STM. Neither Haskell nor occam-pi knowledge is required, but having both would allow you to arrive a few minutes late.
A Study of Java Object Demographics
Mr. Richard Jones, Computing Laboratory (homepage)Thursday 5th June 2008, 11:00 - 11:40, S110B
Researchers have long strived to exploit program behaviour in order to improve garbage collection efficiency. For example, by using a simple heuristic, generational GC manages short-lived objects well, although longer-lived objects will still be promoted to an older generation and may be processed repeatedly thereafter. In this paper, we provide a detailed study of Java object lifetimes which reveals a richer landscape than the generational view offers. Allocation site has been claimed to be a good predictor for object lifetime, but we show that object lifetime can be categorised more precisely than 'short-lived/ long-lived/immortal'. We show that (i) sites allocate objects with lifetimes in only a small number of narrow ranges, and (ii) sites cluster strongly with respect to the lifetime distributions of the objects they allocate. Furthermore, (iii) these clusterings are robust against the size of the input given to the program and (iv) are likely to allocate objects that are live only in particular phases of the program's execution. Finally, we show that, in contrast to previous studies, (v) allocation site alone is not always sufficient as a predictor of object lifetime distribution but one further level of stack context suffices.
Investigating Memory Access and Energy Consumption on the x86 Platform
Mr. Laurence Hellyer, Computing Laboratory (homepage)Thursday 5th June 2008, 11:40 - 12:00, S110B
Power consumption is becoming more and more important, yet suitable tools to research power consumption on popular platforms such as x86 are limited or simply not available.
Memory power and the cost of CPU stalls can account for more than 50% of total power consumption. As memory latency continues to increase relative to CPU performance this problem will grow.
I am particularly interested in the opportunities and difficulties managed run-times present. The fastest algorithm is not always the most energy efficient.
I describe the design of a research tool that will consider the complete system energy consumption and allow exploration of energy consumption due to memory accesses on multiple platforms.
Using the SARG web-page management system
Dr. Fred Barnes, Computing Laboratory (homepage)Thursday 24th April 2008, 16:00 - 17:00, CC02
The Systems Architecture Research Group's new web-pages (which can be found here), are centred around projects and themes, whose information is stored in a database. Unlike the database (CS-web) that feeds the standard CS web-pages, users are able to edit the information associated with themselves, their projects, and suchlike from a basic web-interface. Information kept and managed by this new system includes research-groups, users, projects, postgraduate research project suggestions, publications, supporters (project funding), themes, news items and group seminars. Users can be assigned different levels of access-control, reflecting their roles within the group (e.g. web-master, seminar-organiser) or department as a whole (e.g. head-of-group, head-of-research). As well as generating the group's main web-pages, the system generates small sections of HTML that can be included on a user's home-page (business-card page), showing the projects with which they are involved.
Currently, only the systems architecture group are using this style of pages, but the database behind it is aware of other research groups, permitting users, projects and suchlike to be shared between groups.
This seminar will take place in a terminal-room. In the first part, I will give a brief overview of what the system does and how it works. In the second part, users (principally laboratory staff), will have the opportunity to play around with the administrative interface, setting some of their own details (e.g. research-interests) or creating projects with which they are involved.
Re-engineering Legacy Numerical Software
Mr. James Nicolson, CO620 project studentThursday 27th March 2008, 16:00 - 16:30, S110B
We describe the process used to transform a piece of legacy numerical software, written in Fortran 66, into a Fortran 95 module. The final version is more maintainable, has more user facilities and has fewer errors. We also report on the effect this transformation had on the run-time efficiency of the code.
Active, Provenance-Aware File System
Mr. Chris Silles, CO620 project studentThursday 20th March 2008, 16:00 - 16:30, SW101
The Active, Provenance-Aware File System aims to present users with only the most up-to-date versions of derived files; by considering files as not only having content, but also a recipe by which that content can be derived. During execution of a file recipe, APAFS monitors exactly which files are requested to accurately determine dependencies of the target file. When an APAFS file is opened, this provenance information is used to establish whether or not the target files and its dependencies are up-to-date with respect to their dependencies, and out-of-date files are rebuilt as necessary according to their recipes.
No Entry Without the Permission of the Surveyor
Mr. Jon Simpson, Computing Laboratory (homepage) and Mr. Carl Ritson, Computing Laboratory (homepage)Thursday 21st February 2008, 16:00 - 17:00, SW101
The Surveyor Corporation SRV-1 robot, is a small inexpensive robotics platform making in-roads into the enthusiast and education communities. Equiped with a fast micro-processor, camera, motors and wireless networking it provides an excellent platform for explorations into robotic control. In this casual talk, we will detail the SRV-1 robot\'s architecture and recent innovations in the Transterpreter Transputer Virtual Machine to support running the occam-pi concurrent programming language on it. We will also demonstrate a software development environment we have produced to aid teaching using the SRV-1 and occam-pi at Olin Technical College, Boston, MA.
Tock: Beginning with Omega
Mr. Neil Brown, Computing Laboratory (homepage)Thursday 31st January 2008, 16:00 - 17:00, SW101
The Omega Test is an automated equation solver that discovers whether there is an integer solution to a set of linear equalities and linear inequalities. We can use it in Tock, our occam compiler, to check whether parallel array indexes can ever overlap (and are thus unsafe). This presentation gives an explanation of how the Omega Test works, and of its limitations. Modulo arithmetic, a potential sticking point, is examined and solutions for dealing with it are detailed. Basic knowledge of algebra and mathematical notation is required.
Tock: a nanopass presentation
Mr. Adam Sampson, Computing Laboratory (homepage) and Mr. Neil Brown, Computing Laboratory (homepage)Thursday 6th December 2007, 16:00 - 17:00, SW101
In the second Tock talk, we will examine the various stages of compilation in more detail. We will discuss parser combinators, C/C++ code generation, usage checking, and look at why occam is an interesting language to compile. We will also look at another use of generics, and finally reflect on our experiences with Haskell. Attendance at last week's talk is not required. Knowledge of Haskell and monads will help in parts, but is not essential for all of the talk.
Tock: every compilation begins with a single pass
Mr. Neil Brown, Computing Laboratory (homepage) and Mr. Adam Sampson, Computing Laboratory (homepage)Thursday 29th November 2007, 16:00 - 17:00, SW101
Nanopass compilation is a way of structuring a compiler as many small passes, each performing only one simple action. In the first of two talks, we will introduce Tock, our nanopass compiler for concurrent languages. The compiler itself is written in Haskell. We will explain nanopass compilation, and how we have implemented it with the help of Haskell generics. We will then go on to demonstrate a novel use for Haskell generics for pattern-matching in our testing framework. Basic familiarity with Haskell is assumed, but no more.
Will Virtual Machines Ever Take Off?: A High Integrity VM for Safety-Critical Applications
Mr. Steve Wright, University of Bristol (homepage)Thursday 22nd November 2007, 16:00 - 17:00, S110B
A Virtual Machine (VM) is a program running on a conventional microprocessor that emulates the binary instruction set, registers, and memory space of an idealized computing machine. At the cost of run-time performance, VMs provide a route for planned hardware obsolescence and early application development and test. Therefore, VMs have been suggested as an evolution of current Integrated Modular Avionics architectures.
MIDAS (Microprocessor Instruction & Data Abstraction System) is a VM capable of running binary executables compiled from languages such as C and ADA, whilst providing run-time executable verification, and being suitable for implementation using Formal Methods.
This presentation covers the features of the MIDAS VM, its place in IMA architectures, and its implementation using Formal Methods.
Decrypting the Java Gene Pool: Object lifetime discovery using Micro-Patterns
Mr. Sebastien Marion, Computing Laboratory (homepage)Thursday 11th October 2007, 16:00 - 16:30, S110B
Over the years, Garbage Collection (GC) has been a topic of much interest. Some attempts to improve GC throughput have resulted in making use of heuristics, essentially trying to predict how long an object is likely to live. The main drawback of these approaches however is that they require some prior trace recordings of the program's behavior. We present a novel method allowing the prediction of such lifetime by determining the set of micro-patterns associated with each Java class of the program.
Intelligent Selection of Application-Specific Garbage Collectors
Jeremy Singer, University of Manchester (homepage)Thursday 27th September 2007, 16:00 - 17:00, S110B
Java program execution times vary greatly with different garbage collection algorithms. Until now, it has not been possible to determine the best GC algorithm for a particular program without exhaustively profiling that program for all available GC algorithms. Our new approach uses machine learning techniques to build a prediction model that, given a single profile run of a previously unseen Java program, can predict an optimal GC algorithm for that program.
CPA-2007 Conference Presentations
Mr. Carl Ritson, Computing Laboratory (homepage), Dr. Fred Barnes, Computing Laboratory (homepage), Professor Peter Welch, Computing Laboratory (homepage), Mr. Neil Brown, Computing Laboratory (homepage), Mr. Jon Simpson, Computing Laboratory (homepage), Mr. Christian Jacobsen, Computing Laboratory (homepage) and Dr. Matthew Jadud, Computing LaboratoryWednesday 4th July 2007, 14:00 - 17:00, S110B
Approximately 7 research staff and students from the systems research group will be heading off to CPA-2007 next week, armed with a variety of paper presentations. This session will be a "test drive" for these -- all welcome to observe, comment and question. The talks will be:
Carl Ritson and Fred Barnes A Process Oriented Approach to USB Driver Development Peter Welch and Neil Brown Integrating and Extending JCSP Carl Ritson and Peter Welch A Process-Oriented Architecture for Complex System Modelling Neil Brown C++CSP2: A Many-to-Many Threading Model for Multicore Architectures Jon Simpson, Christian Jacobsen and Matthew Jadud A Native Transterpreter for the LEGO Mindstorms RCX Abstracts for these talks can be found on the CPA-2007 programme page.
C++CSP2 -- Atomic Adventures in a Multi-Core Universe
Mr. Neil Brown, Computing Laboratory (homepage)Thursday 10th May 2007, 16:00 - 17:00, S110B
The original C++CSP library — an implementation of occam/CSP ideas in C++, was written as an undergraduate project, built on top of co-operatively scheduled user-threads. Faced with the mass-market advent of multi-core processors, I have rewritten the C++CSP library to take advantage of the available parallelism; transforming the library to use many-to-many threading, combining kernel-threads and user-threads. The algorithms are intended to be scalable, ready for a future increase in the number of cores. This talk on my work will involve a mix of algorithms, practical benchmarks, the C++CSP2 API and discussion of issues arising from implementing concurrency in a sequential language.
Dynamic memory management: challenges for today and tomorrow
Mr. Richard Jones, Computing Laboratory (homepage)Thursday 29th March 2007, 16:00 - 17:00, S110B
Garbage collection (GC) is a key component of almost all modern programming languages. The advent of conventional object-oriented languages supported by managed run-times (e.g. Java, C# and even Managed C++) has brought GC into the mainstream and, as memory manager performance is critical for many large applications, brought GC to the attention of programmers outside its traditional functional programming language community.
In this talk, I shall start by reviewing how GC got to where it is today, why it is desirable, what performance you might reasonably expect and I shall outline the directions in which GC research is moving. In particular, I'll look at some of the challenges facing modern GC, in contexts ranging from GC for high-performance, multiprocessor systems to GC for real-time systems and limited devices, from better integrating with its operating environment to supporting specific applications. I shall speculate wildly on future directions for research.
System Monitoring and Control
Mr. Richard Bonner, CO620 project studentThursday 22nd March 2007, 16:00 - 17:00, S110B
Every network administrator's worst fear is for a server to enter a state where it stops responding to the network (or console), thereby requiring a hard reset before normal operations can resume. Due to the physical location of most servers, this can be a costly and time-consuming task. This seminar presents an inexpensive method for controlling servers remotely, utilising a two-tier software/hardware approach.
A Process-Oriented Approach to Blood Clotting Simulation and Visualisation
Mr. Carl Ritson, Computing Laboratory (homepage)Wednesday 21st March 2007, 14:00 - 15:00, S110B
Although presented in a generic re-usable form, at this work's core is a fine-grained massively-parallel process-oriented model of platelets within a blood vessel using a CSP inspired design, expressed and implemented using the occam-pi language. The aim being to engineer emergent behaviour from platelet processes. The described case study runs to millions of processes engaged in ever-changing communication topologies. It is free from deadlock, livelock, race hazards and starvation by design, employing a small set of synchronisation patterns for which we have proven safety theorems.
Distributed Information Storage in a Pervasive Peer-to-Peer Network (part 1)
Mr. James Grant, CO620 project studentThursday 15th March 2007, 16:00 - 16:30, SW101
This talk is the first part of two complementary talks that introduce the problem of dynamically maintaining a population of file replicas in a distributed, ad-hoc peer-to-peer file storage system. The focus of this talk are two very simple algorithms that allow fragments to autonomously respond to changing levels of replica fragments in their local network. The two algorithms were simulated and evaluated using NetLogo, and the overall fragmentation-redundancy-scattering file system was implemented and evaluated in a cluster of computers for evaluating the scalability of the overall approach.
Distributed Information Storage in a Pervasive Peer-to-Peer Network (part 2)
Mr. Jonathan So, CO620 project studentThursday 15th March 2007, 16:30 - 17:00, SW101
Fragmentation-redundancy-scattering is a fault-tolerance technique for ensuring the availability of information in distributed systems. This talk presents different algorithms that can be combined with FRS to lessen the risk of information loss in a pervasive peer-to-peer storage system. I shall also describe a prototype implementation, written in Java, which was used for simulation of the algorithms. This talk continues from the previous talk by my colleague, James Grant.
Garbage Collection for Data Structure Reorganisation
Mr. George Kurian, CO620 project studentThursday 8th March 2007, 16:30 - 17:00, SW101
Complex programs typically have complex data structures. When used in a language with automatic garbage-collection (Java), a significant portion of collection time can be spent handling such complex structures. This talk discusses the optimisation of such structures, using knowledge gained about these structures from the collector itself, in order to improve garabage-collection (GC) performance.
A Native Transterpreter for the LEGO MindStorms RCX
Mr. Jon Simpson, CO620 project student (homepage)Thursday 22nd February 2007, 16:00 - 16:30, S110B
This talk will present a small and maximally concurrent occam-pi operating environment for the LEGO MindStorms RCX robotics platform, implemented using the Transterpreter virtual machine.
After an overview of the platform and virtual machine, I will discuss the difference between this implementation and a previous related one, some of the problems of using the Transterpreter with the Mindstorms RCX and present an advantage to working in a concurrent runtime from the hardware up.
An IDE Driver for RMoX
Mr. Christian Föecker, CO620 project studentThursday 22nd February 2007, 16:30 - 17:00, S110B
I will describe my work on a IDE (harddisk) driver for RMoX. This will include an introduction on how to access the hardware as well as concrete code examples showing how this is realised. The talk will finish with a brief outlook of what could be done in the future, building upon this project.
Making Music with occam-pi
Mr. Adam Sampson, Computing Laboratory (homepage)Thursday 1st February 2007, 16:00 - 17:00, S110B
In the last twenty years of electronic music, the boundaries between programming and composition have become increasingly blurred. This talk will show how musicians can make use of process-oriented techniques during live performance.
Region Based Memory Management
Guillaume Salagnac, Laboratoire Verimag, Grenoble (homepage)Wednesday 17th January 2007, 14:00 - 15:00, S110B
Dynamic memory management is a serious challenge for real-time embedded systems based on Java technology. Contrary to the standard Java paradigm, garbage collection is rarely used in such real-time environments, since the temporal behavior of dynamic memory collection (e.g. pause times) is usually difficult to predict and thus significantly complicates the implementation of real-time scheduling policies. On resource-limited platforms, such as smart cards, the implementation of efficient garbage collectors (GC) is furthermore hindered by hardware limitations, and embedded systems manufacturers frequently omit them completely (see the JavaCard2 platform for instance). Similarly, several GC algorithms have been proposed for real-time applications, but they typically require the programmer to provide a model of the dynamic memory management behaviour of his application, such as the maximum allocation and mortality rates of objects for instance, a difficult task at best (i.e. determine the maximum allocation is undecidable).
This talk will present an efficient static analysis algorithm, combined with a region allocation policy for real-time embedded Java applications. The goal of this work is to provide a static analysis mechanism efficient enough to be integrated in an assisted-development environment, and to implement region-based memory management primitives suited for resource-limited platforms.
occam-pi Masterclass
Mr. Adam Sampson, Computing Laboratory (homepage)Thursday 16th November 2006, 12:00 - 17:00, SW110A
This short course will introduce participants to the new features of occam-pi.
Improvements to the GCSpy Heap Visualisation Framework
Andy Cheadle, Imperial College, London (homepage)Thursday 16th November 2006, 16:00 - 17:00, SW101
We will present generic extensions to the GCspy visualisation framework that make it suitable for tracking the way continuous dynamic memory allocators such as malloc or incremental and concurrent garbage collectors make use of heap memory. These extensions include sample-driven client-server communication, incremental stream updates and client-controlled stream update frequency. Additional enhanements to the current GCspy client will also described. These include the grouping of drivers to form hierarchies and the subsequent visualisation of those hierarchies. Additional features such as zooming and tile linking between spaces, will also be demonstrated.
We also introduce some new features that add primitive performance debugging capabilities to GCspy. In particular we will report our experiences with a simple heuristics engine can flip GCspy from its decoupled 'observation' mode to a synchronous 'single-step' mode, and a backtrace facility that can trace the server-side call sequence that led to the triggering of a specified event, such as the allocation or freeing of a block of memory.
We will provide a demonstration of the new framework and will show how the various new features can be combined to provide a visualisation of Doug Lea's 'malloc' (dlmalloc). We will present performance figures for the new framework and will demonstrate how it can be used to explore contrived modifications to dlmalloc's coalescing policy. We will also comment on our plan to extend further CGspy's performance debugging capabilities.
Objects' Lifetime Discovery with Micro-Patterns
Mr. Sebastien Marion, Computing Laboratory (homepage)Thursday 9th November 2006, 16:00 - 17:00, SW101
Over the years, Garbage Collection (GC) has been a topic of much interest. Some attempts to improve GC throughput have resulted in making use of heuristics, essentially trying to predict how long an object is likely to live. The main drawback of these approaches however is that they require some prior trace recordings of the program's behavior. We present a novel method allowing the prediction of such lifetime by determining the set of micro-patterns associated with each Java class of the program.
An Introduction to Pointer Analysis
Mr. Robert Bunyan, Computing Laboratory (homepage)Tuesday 17th October 2006, 16:00 - 17:00, S110B
I will introduce the concept of pointer analysis beginning with a brief look at the concept of aliasing and concluding with a step by step example analysis of some code using both the Steensgaard and Andersen pointer analyses. The presentation will also cover some of issues that have to be considered when choosing or designing a pointer analysis, such as the issue of flow sensitivity.
The Doomsday Protocol
David Munro, University of Adelaide (homepage)Wednesday 30th August 2006, 10:00 - 11:00, SW101
Distributed termination detection (DTD) algorithms are important since they detect globally stable states in distributed computations. Here we introduce a new distributed termination detection protocol, the Doomsday protocol, together with its proof of correctness. We use the term protocol since it is generic, forming the basis for a number of new and existing DTD algorithms for which the correctness proof may be reused. This talk describes the Doomsday protocol, outlines its formal proof, and shows how a new DTD algorithm and how other hitherto unrelated algorithms can be derived from the protocol.
Using a Policy Language to Control Tuple-space Synchronization in a Mobile Environment
Mr. Vorapol Jittamas, Computing LaboratoryThursday 25th May 2006, 11:00 - 12:00, S110B
Any sharing of information using a distributed platform carries the risk of disconnection because of loss of network access. This is particularly the case when considering mobile communication, either using base stations or by forming ad-hoc networks. Replication of shared data is one way to increase data availability in such an environment, but leads to the problem of inconsistency between copies of data, and so requires some means of data synchronization.
This paper investigates how policies can be used to resolve data conflict in a way that can be tailored to meet the needs of different types of application in different situations. It discusses a range of application requirements, and describes a policy-based pervasive middleware to support the sharing of data using a tuple-space paradigm. Policies maintained within the middleware are used to trigger a wide range of synchronization options to restore the consistency of the data after periods of disconnected operation.
Portable, Mostly-Concurrent, Mostly-Copying Garbage Collection for Multi-Processors
Antony Hosking, Purdue University (homepage)Friday 19th May 2006, 14:00 - 15:00, S110B
Modern commodity platforms increasingly support thread-level parallelism, which must be exploited by garbage collected applications. We describe the design and implementation of a portable *mostly-concurrent* mostly-copying garbage collector that exhibits scalable performance on multi-processors. We characterize its performance for heap-intensive workloads on two different multi-processor platforms, showing maximum pause times two orders of magnitude shorter than for fully stop-the-world collection at the cost of some total mutator throughput.
Game Algorithms in occam-pi
Mr. Kevin Morgan, CO620 project studentFriday 3rd March 2006, 12:00 - 13:00, S110B
The occGame project is a research project to explore how zero-sum perfect-information game algorithms can be realised in occam-pi. With simpler games, like tic-tac-toe, the game tree is relatively small and can be completely searched, whereas in larger games such as chess this is not possible (at least not in a reasonable time). Using parallel hardware and algorithms would allow for more of the tree to be searched and better results obtained. As such occam-pi seems a highly suitable language to implement these kinds of algorithms. My presentation will give a brief overview of the algorithms that are generally used, what new occam-pi features have been, and may be used for these types of algorithms, the pros and cons of using occam-pi, as well as some of the results obtained so far.
Graphics Library Support for occam-pi
Ms. Samantha Davis, CO620 project studentTuesday 28th February 2006, 10:00 - 10:30, S110B
In this talk I will be discussing my research involving the occam-pi graphics library. The talk will cover programming Brownian-motion in occam-pi and some performance results. Further developments that could build on this work will also be discussed.
Intrusion Tolerance in Distributed Systems
Ms. Vicki Spurrett, CO620 project studentTuesday 28th February 2006, 10:30 - 11:00, S110B
In this talk I will discuss how the intrusion tolerance technique of fragmentation-replication-scattering (FRS) can be used to create a dependable and secure way to store files within a distributed system. I will also talk about how a simulation of the FRS system was designed and implemented and the issues raised during implementation. The talk will finish with details on possible future work.
An Eclipse Framework for occam-pi
Mr. Alex Mather, CO620 project studentMonday 27th February 2006, 15:00 - 15:30, S110B
In this talk I will discuss an Eclipse framework for occam-pi. The talk will cover the motivations for creating the framework, the Eclipse platform, features included in the framework to improve occam-pi development, its uses as a teaching tool and its implementation. I will also look at possible future work on the project.
A Video Processing Framework in occam-pi
Mr. Carl Ritson, CO620 project student (homepage)Tuesday 21st February 2006, 10:00 - 10:30, S110B
In this talk I will describe a video processing framework for the occam-pi language. The talk will cover the motivation for using occam-pi as a multi-media handler, an overview of the protocols involved and a look into developing video players and other tools, exploiting occam-pi's features to provide dynamism and efficiency.
Tolerating Fault in a Distributed Storage System
Mr. Rudi Ball, CO620 project studentTuesday 21st February 2006, 10:30 - 11:00, S110B
The talk will describe an approach for tolerating faults in a distributed storage system using the mechanisms of fragmentation, replication and scattering (FRS), keyed digests and encryption. I hope to describe the aims of the system, its structure, prototype implementation (using agents), performance issues and anticipated future work.
Programming the CELL
Mr. Damian Dimmich, Computing Laboratory (homepage)Tuesday 7th February 2006, 10:00 - 11:00, S110B
The CELL processor developed by IBM, Sony and Toshiba, is a radically new CPU design. The talk will start with a quick overview of the architecture and primary features of the CELL. Following that details of how to program the CELL will be given along with code examples. I hope to cover at least some of the following: concurrency mechanisms; CELL's internal communication mechanisms (mailboxes); how to make use of the vector units, attaining maximum performance; and possibly going over some of the SPU's (dedicated vector units) assembly language.
A New Compiler for Parallel Programming
Dr. Fred Barnes, Computing Laboratory (homepage)Tuesday 31st January 2006, 10:00 - 11:00, S110B
This talk introduces the new occam-pi compiler, a highly dynamic and extensible compiler for parallel programming. Although primarily designed to compile occam-pi, the compiler supports a CSP-like language that also targets the KRoC run-time system. In this talk I will discuss the motivation for writing a new compiler along with its structure and some key features. Amongst the more interesting features are the ability to modify the language grammar at run-time, namespaces and digital-signatures for generated code.
One size doesn't fit all: exploiting program behaviour
Mr. Richard Jones, Computing Laboratory (homepage)Tuesday 24th January 2006, 10:00 - 11:00, S110B
Modern state of the art garbage collectors are designed to combine high throughput with low pause-times. And they are very successful for typical programmes. However, much GC effort is, in a sense, wasted. Rather than reclaiming memorydirectly (which is what the programmer wants), tracing 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. Furthermore, there is no 'one size fits all' strategy: different collectors perform better or worse on different programs. We believe that GC should and can exploit understanding of the program in order to improve performance.
In this talk, I shall review work that has sought to exploit program behaviour. I shall describe three recent aspects of our work in this area. First, we introduce a novel static analysis and heap organisation in order to reduce GC synchronisation. Second, we show that program behaviour is sufficiently predicable to allow us to collect only those regions of the heap in which we expect the vast majority of objects to be dead. Finally, I shall outline a new collection framework that can take advantage of this behaviour.
Exploiting Phases in Execution and Resource Availability for Efficient Program Sampling and VEE Specialization
Dr. Chandra Krintz, University of California, Santa Barbara (homepage)Monday 19th December 2005, 14:00 - 15:00, SW101
Key to extracting high-performance from programs executed using virtual execution environments (VEEs), is effective dynamic adaptation of the program and runtime to the changing characteristics of program execution and resource availability. To enable aggressive adaptive optimization, VEEs require efficient techniques that track these changes accurately and that exploit them to extract higher-levels of performance.
Our work focuses on two techniques that enable dynamic adaptation in VEEs: efficient performance profiling and dynamic VEE specialization. The unifying factor of our research is our capture, characterization, and exploitation of repeating patterns, i.e., phases, in program behavior and resource availability. Our profiling techniques use phases to guide transparent execution sampling. Our specializations consider not only optimization and specialization of executing programs, but that of the execution environment, as resource consumption and availability changes. In this talk, we overview our research on efficient program sampling and specialization. As examples of the latter, we present two VEE specializations for garbage collection (GC) that improve startup time for generational systems and that improve overall execution time via dynamic switching between GC systems.
A Fast Analysis for Thread-Local Garbage Collection
Mr. Richard Jones, Computing Laboratory (homepage) and Dr. Andy King, Computing LaboratoryTuesday 6th December 2005, 10:00 - 11:00, SW101
Long-running, heavily multi-threaded, Java server applications make stringent demands of garbage collector (GC) performance. Synchronisation of all application threads before garbage collection is a significant bottleneck for JVMs that use native threads. We present a new static analysis and a novel GC framework designed to address this issue by allowing independent collection of thread-local heaps. In contrast to previous work, our solution safely classifies objects even in the presence of dynamic class loading, requires neither write-barriers that may do unbounded work, nor synchronisation, nor locks during thread-local collections; our analysis is sufficiently fast to permit its integration into a high-performance, production-quality virtual machine.
Death Order Garbage Collection and the Beltway Collector
Dr. Chris Ryder, Computing Laboratory (homepage)Tuesday 22nd November 2005, 10:00 - 11:00, S110B
In this talk (previously given to the TCS group, updated for the systems group) I will introduce the Beltway garbage collector. Beltway is a very flexible collector which offers many opportunities for tuning the collection strategy. Death order garbage collection is a strategy that takes advantage of predictable behaviour in programs to collect only the regions of the heap in which we expect all objects to be dead. I will discuss work currently being carried out by Richard Jones and myself, funded by IBM, to implement a death order strategy using the Beltway collector and IBM's Jikes RVM Java virtual machine.
Lazy Simulation of Cellular Automaton with Communicating Processes
Mr. Adam Sampson, Computing Laboratory (homepage)Tuesday 15th November 2005, 10:00 - 11:00, SW101
Cellular automata (CAs) are good examples of systems in which large numbers of autonomous entities exhibit emergent behaviour. Using the occam-pi and JCSP communicating process systems, we show how to construct lazy and just-in-time models of cellular automata, which permit very efficient parallel simulation of sparse CA populations on shared-memory and distributed systems.
pony - The occam-pi Network Environment
Dr. Mario Schweigler, Computing LaboratoryTuesday 8th November 2005, 10:00 - 11:00, S122A
Although concurrency is generally perceived to be a `hard' subject, it can in fact be very simple - provided that the underlying model is simple. The occam-pi language provides such a simple yet powerful concurrency model that is based on CSP and the pi calculus. This talk presents pony, the network environment for occam-pi. occam-pi and pony provide a new, unified, concurrency model that bridges inter- and intra-processor concurrency. This enables the development of distributed applications in a transparent, dynamic and highly scalable way.
Interfacing C and occam-pi
Dr. Fred Barnes, Computing Laboratory (homepage)Tuesday 25th October 2005, 14:00 - 15:00, S122A
The occam-pi programming language provides various facilities for interacting with the external environment, e.g. to call external library functions. Although these mechanisms are useful (and sufficient for our needs so far), the handling of foreign data-types in occam-pi is not particularly pleasant. In the majority of cases, such data are pointers to C structures, often containing external state and passed to many different external calls. Although the overheads of these external calls are small, the resulting occam-pi program becomes hard to understand without constant reference to the external functions.
This talk, first presented at CPA-2005, examines a new C interface for occam-pi that allows whole processes to be written in C; complete with channel communication, barrier synchronisation and all the occam-pi features. This provides a way of having processes that can easily make external calls (more or less as any C application would), manipulate their own state in an obvious way, and interact with concurrent processes (through channel communication and other synchronisations).
The applications of this new mechanism are wide-ranging, from providing cleaner handling of external code in occam-pi systems, through to the programming of whole CSP-based concurrent systems in C (with all the features of occam-pi).
Low-level device drivers for RMoX
Mr. Alex Foreman, CO620 project studentTuesday 19th April 2005, 14:00 - 14:30, SW101
This short talk will discuss the development of a legacy device-driver in occam-pi for the RMoX operating-system. The driver developed is for a standard PC floppy-drive (SA-450 FDC), including basic support for interrupts and DMA (which the driver uses).
Garbage Collection for Servers via Sliding Views
Dr. Erez Petrank, Technion - Israel Institute of Technology (homepage)Friday 1st April 2005, 11:00 - 12:00, S110B
With concurrent and garbage collected languages like Java and C# becoming popular, the need for a suitable non-intrusive, efficient, and concurrent multiprocessor garbage collector has become acute. Reference counting has traditionally been considered unsuitable for multi-processor systems. According to conventional wisdom, the update of pointers and reference counts required atomic or synchronized operations. In this work we show that this is not the case by presenting a novel reference-counting algorithm suitable for a multi-processor system that does not require any synchronized operation on a pointer modification (not even a compare-and-swap type of synchronization). Furthermore, the new collector eliminates a large fraction of the reference-count updates, thus, drastically reducing the reference-counting traditional overhead.
This garbage collector was implemented on the Jikes research JVM and comparisons against Jikes collectors will be presented. Measurements show extremely low pause times (around 1ms) and excellent throughput.
If time allows, we will discuss several directions of subsequent work building on the techniques developed in this basic work.
This is a joint work with Yossi Levanoni, and Harel Paz.