Problems with this page?
Contact the mm-net webmaster
Last modified Mon Aug 8 13:00:45 BST 2005
The UK Memory Management Network (mm-net) is an EPSRC-funded network of researchers, interested in memory management for programming languages. The project's mission is to establish collaborations between UK industrialists and academics to further research and development of advanced memory management systems.
The Memory Management Network held two workshops in 2003, both focussed on specific topics.
The Workshop on Memory Management for Handheld Devices, organised by Kevin Hammond, Richard Jones and Peter O'Hearn, was held at the Computing Laboratory in the University of Kent on 15 May 2003. As the memory management field matures, interest has grown in how analytical techniques can be applied, either to improve the efficiency of memory managers or to guarantee the correctness of operations on dynamically allocated memory. 18 members of the Network attended the workshop, with representatives from both academia and industry (and visitors from Denmark and Israel!).
The keynote speaker was Greg Morrissett of Cornell University. Greg introduced the Cyclone project - a type-safe dialect of C which features an advanced type system, an intra-procedural flow analysis, new language featuresand run-time checks. In particular, Greg described Cyclone's approach to Region-based Memory Management and how Cyclone integrates unique pointers. Other speakers gave presentations on how to proving the correctness of a garbage collector by using local reasoning, on modular pointer checking, on space cost analysis using sized types, on synchronisation analysis for Java, and on post-mortem memory profiling.
The Workshop on Analytical Techniques for Memory Management, organised by Chris Clack, was held at the University College London on 2 December 2003. The Network is grateful to Symbian for sponsoring the workshop.
There is increasing market pressure to provide sophisticated applications on handheld devices such as smartphones and PDAs. Typically these applications are programmed in C++ or Java, with increasing reliance on dynamic and automatic memory management. The constrained heaps of these devices and requirements for (soft and hard) real-time performance, coupled with constrained hardware and power resources, provides a challenging environment for memory management.
20 participants heard Andrew Thoelke (Chief Technology Architect of Symbian) give the keynote address on "Memory Management for Smartphones -- Old hat or New challenge?". He showed how smartphones are the place where handheld computers and mobile handsets come together. This combination is rather more complex than one first imagines -- one device inhabited a world of add-on software for the technically literate, the other was an out and out consumer device aimed at the mass market. Something more is demanded than a subtle blend of their existing memory management techniques.
Other speakers discussed the Hume strongly typed, mostly-functional language, intended to explore language design for resource-limited systems, including real-time embedded and safety-critical systems; smart memory for smart phones; memory management in language support for lightweight transactions; and the GCspy heap visualisation framework. The workshop concluded with a discussion led by John Pagonis of Symbian on memory management for wearable and mobile computing.
Mm-net supported visits by academic members of the Network to the following international conferences: ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA'03) in Anaheim, California, IFIP Working Group 2.8 in Coff's Harbour, Australia. It also supported members' attendance at mm-net's own workshops in Canterbury and London.
In addition, it supported a three-day study group at the University of Southampton working on distributed garbace collection algorithms for Richard Jones , Peter Dickman and Luc Moreau, and .
Mm-net members published further memory management related papers.
Norcross, S., Morrison, R., Munro, D S., Detmold, H. & Falkner, K., Implementing a Family of Distributed Garbage Collectors, In 26th Australasian Computer Science Conference (ACSC 2003), Adelaide, Australia (2003), pp 161-170.
Nicholas Nethercote and Julian Seward. Valgrind: A Program Supervision Framework, Third Workshop on Runtime Verification (RV'03), Boulder, Colorado, USA, July 2003.
Nicholas Nethercote and Alan Mycroft. Redux: A Dynamic Dataflow Tracer. Third Workshop on Runtime Verification (RV'03), Boulder, Colorado, USA, July 2003.
Peter D. Petrov and Martin T. Vechev Embedded JVM Concurrent Garbage Collector Internals. In IASTED Networks, Parallel and Distributed Processing, and Applications (NPDPA'02)
Nicholas Nethercote and Alan Mycroft. The Cache Behaviour of Large Lazy Functional Programs on Stock Hardware. Workshop on Memory System Performance (MSP 2002), pp44-55, Berlin, Germany, July 2002.
Patricia M. Hill and Fausto Spoto. A Foundation of Escape Analysis. 9th International Conference on Algebraic Methodology and Software Technology, AMAST 2002, St. Gilles les Bains, Reunion Island, France, September 9-13, 2002, vol. 2422 of Lecture Notes in Computer Science, H. Kirchner, C. Ringeissen, Eds., pp. 380--395.
Hans-Wolfgang Loidl. The Virtual Shared Memory Performance of a Parallel Graph Reducer. In CCGrid 2002 - International Symposium on Cluster Computing and the Grid (DSM 2002: International Workshop on Distributed Shared Memory on Clusters), Berlin, pp. 311-318, May 2002. IEEE Press.
Patricia M. Hill and Fausto Spoto. A Refinement of the Escape Property. In Verification, Model Checking and Abstract Interpretation, Third International Workshop, VMCAI 2002, Venice, Italy, January 2002, Revised Papers. vol. 2294 of Lecture Notes in Computer Science, Agostino Cortesi, Ed., pp 154-166.
and Fermin Reig successfully defended his PhD thesis:
Fermin Reig. Compiler Architecture using a Portable Intermediate Language PhD dissertation. Glasgow 2003.
Mm-net members worked on a number of new projects in 2003.
Distributed garbage collection for both Modula-3's Network Objects and Java's RMI is based on Birrell et al's well-known algorithm. Peter Dickman, Richard Jones, and Luc Moreau continued working on reformulating the algorithm into a form which both elucidates key subtleties of the algorithm and its implementation and, simultaneously, supports a proof of crucial properties. The project also provided an intuitive yet precise graphical notation for such algorithms.
Pat Hill completed a project on Escape Analysis for Object-Oriented Languages (supported by EPSRC grant GR/R35401/01). The aim of the project was to approximate the control flow of an object-oriented program so as to determine the static scopes of selected variables. The main objective was to design a new compositional and focussed escape analysis that has a precision greater than achieved using current techniques. A prototype escape analyser will be built and the precision of its results will be experimentally evaluated. Although the prototype will not have been built for performance, it will provide a check that the techniques are indeed practical and whether they are worth developing further. The final report and our recent publications for research done in this project are on-line.
Memory management subsystems tend to be either fast (able to hit hard or soft
real time deadlines) or small (making the optimum use of available memory) but
are rarely both. This is a problem for the manufacturers of smartphones, which
couple small physical size with complex consumer applications (web browsers,
organisers, image editors) that use dynamic memory management. At UCL, Chris
Clack's new memory manager provides the memory parsimony of best-fit allocation
and coalescing with impressive performance. Initial analytic results indicated
that best-case response times should be equivalent to dlmalloc and worst-case
response times could be an order of magnitude better than existing algorithms.
Further experimental results indicated a consistent 50% improvement on memory
requirements when compared with a popular gmalloc allocator. Following a patent
application and a market study of the mobile phone sector, UCL has received
enthusiastic support from many key players. In particular, UCL is currently
collaborating with Symbian to run comprehensive
tests of the new allocator on the Symbian OS, and ARM are donating a development
kit for similar low-level tests to be run on the ARM architecture. Our research
directions include modifications to move towards hard real-time applications
(currently, the new allocator is only suitable for soft real-time applications),
improving the intelligence of the allocator so that memory allocation patterns
may be predicted and used to further improve memory utilisation, and proving
useful properties of the algorithm.
UCL (Chris Clack) and St.Andrews
(Kevin Hammond) are collaborating on the applicability of UCL's new memory
allocator to St.Andrew's Hume
language. Hume is a functional language aimed at small embedded systems,
where predictability of heap size and response times are critical. The UCL allocator
is aimed at size-constrained soft real-time embedded systems. In terms of smartphones
(the current target of the UCL allocator) this moves the focus of attention
from the applications processor to the base-band processor, where programs are
smaller and have much stricter real-time constraints; the aim is to move the
programmer of base-band code away from hand-crafted assembler so that time-to-market
is reduced and fast-moving standards and protocols can be supported.
In lazy functional languages such as Haskell, reasoning about static properties
of programs such as their meaning and correctness is comparatively simple. In
contrast, it is notoriously difficult to reason about dynamic properties of
lazy programs such as their space and time complexity. Graham
Hutton and Catherine Hope
(Nottingham) are developing a simple but practically useful theory of space
and time for lazy functional programs, based upon the use of structured forms
of recursion in preference to unrestricted recursion.
Richard Jones and Chris Ryder (Kent) are explore in depth the lifetimes of objects allocated by Java programs. They seek to understand whether object lifetime patterns exist, whether there are predictors for these patterns and how such patterns can be exploited to improve garbage collection performance. This project is generously supported by IBM through a Faculty Partnership Award.
Two further organisations joined mm-net in 2003 : Queen Mary, University of London (Josh Berdine, Cristiano Calcagno and Peter O'Hearn) and the University of Nottingham (Graham Hutton and Catherine Hope). Other members of the Network are the Universities of Glasgow, Kent, Southampton, St. Andrews, Cambridge, Heriot-Watt and Leeds, and Imperial College and University College, London and IBM UK Ltd., Insignia Solutions, Microsoft Research, Ravenbrook.
Richard Jones
Problems with this page?
Contact the mm-net webmaster
Last modified Mon Aug 8 13:00:45 BST 2005