Publications and Abstracts

Copyright Notice. The below material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's or organization's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Frampton, D., Blackburn, S. M., Cheng, P., Garner, R. J., Grove, D., Moss, J. E. B., Salishev, S. I. Demystifying magic: high-level low-level programming VEE 2009, International Conference on Virtual Execution Environments, (Washington, DC, USA, March 11-13, 2009)

DOI: 10.1145/1508293.1508305 Download: Paper:

Talk:

FOR Codes: 080308, 080309

Abstract

The power of high-level languages lies in their abstraction over hardware and software complexity, leading to greater security, better reliability, and lower development costs. However, opaque abstractions are often show-stoppers for systems programmers, forcing them to either break the abstraction, or more often, simply give up and use a different language. This paper addresses the challenge of opening up a high-level language to allow practical low-level programming without forsaking integrity or performance.

The contribution of this paper is three-fold: 1) we draw together common threads in a diverse literature, 2) we identify a framework for extending high-level languages for low-level programming, and 3) we show the power of this approach through concrete case studies. Our framework leverages just three core ideas: extending semantics via intrinsic methods, extending types via unboxing and architectural-width primitives, and controlling semantics via scoped semantic regimes. We develop these ideas through the context of a rich literature and substantial practical experience. We show that they provide the power necessary to implement substantial artifacts such as a high-performance virtual machine, while preserving the software engineering benefits of the host language.

The time has come for high-level low-level programming to be taken more seriously: 1) more projects now use high-level languages for systems programming, 2) increasing architectural heterogeneity and parallelism heighten the need for abstraction, and 3) a new generation of high-level languages are under development and ripe to be influenced.

Blackburn, S. M., McKinley, K. S., Garner, R., Hoffman, C., Khan, A. M., Bentzur, R., Diwan, A., Feinberg, D., Frampton, D., Guyer, S. Z., Hirzel, M., Hosking, A., Jump, M., Lee, H., Moss, J. E. B., Phansalkar, A., Stefanovic, D., VanDrunen, T., von Dincklage, D., and Wiedermann, B. Wake Up and Smell the Coffee: Evaluation Methodology for the 21st Century Communications of the ACM, 51(8) pp 83--89, August 2008

DOI: 10.1145/1378704.1378723 Download: Paper: Talk:
FOR Codes: 080308, 080309, 100605

Abstract
Evaluation methodology underpins all innovation in experimental computer science. It requires relevant workloads, appropriate experimental design, and rigorous analysis. Unfortunately, methodology is not keeping pace with the changes in our field. The rise of managed languages such as Java, C#, and Ruby in the past decade and the imminent rise of commodity multicore architectures for the next decade pose new methodological challenges that are not yet widely understood. This paper explores the consequences of our collective inattention to methodology on innovation, makes recommendations for addressing this problem in one domain, and provides guidelines for other domains. We describe benchmark suite design, experimental design, and analysis for evaluating Java applications. For example, we introduce new criteria for measuring and selecting diverse applications for a benchmark suite. We show that the complexity and nondeterminism of the Java runtime system make experimental design a first-order consideration, and we recommend mechanisms for addressing complexity and nondeterminism. Drawing on these results, we suggest how to adapt methodology more broadly. To continue to deliver innovations, our field needs to significantly increase participation in and funding for developing sound methodological foundations.

Blackburn, S. M., and McKinley, K. S. Immix: A Mark-Region Garbage Collector with Space Efficiency, Fast Collection, and Mutator Performance ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2008), (Tucson, AZ, USA, June 7-13, 2008)

DOI: 10.1145/1375581.1375586 Download: Paper: Talk:
FOR Codes: 080308
Patch against Jikes RVM revision 13767: Data (csv): Complete results:
Abstract
Programmers are increasingly choosing managed languages for modern applications, which tend to allocate many short-to-medium lived small objects. The garbage collector therefore directly determines program performance by making a classic space-time tradeoff that seeks to provide space efficiency, fast reclamation, and mutator performance. The three canonical tracing garbage collectors: semi-space, mark-sweep, and mark-compact each sacrifice one objective. This paper describes a collector family, called mark-region, and introduces opportunistic defragmentation, which mixes copying and marking in a single pass. Combining both, we implement immix, a novel high performance garbage collector that achieves all three performance objectives. The key insight is to allocate and reclaim memory in contiguous regions, at a coarse block grain when possible and otherwise in groups of finer grain lines. We show that immix outperforms existing canonical algorithms, improving total application performance by 7 to 25% on average across 20 benchmarks. As the mature space in a generational collector, immix matches or beats a highly tuned generational collector, e.g. it improves SPEC jbb by 5%. These innovations and the identification of a new family of collectors open new opportunities for garbage collector design.

Blackburn, S. M., Salishev, S. I., Danilov, M., Mokhovikov, O. A., Nashatyrev A. A., Novodvorsky, P. A., Bogdanov, V. I., Li, X. F., and Ushakov, D. The Moxie JVM Experience, Australian National University Technical Report TR-CS-08-01, January 2008

Download:
FOR Codes: 080308

Abstract
By January 1998, only two years after the launch of the first Java virtual machine, almost all JVMs in use today had been architected. In the nine years since, technology has advanced enormously, with respect to the underlying hardware, language implementation, and in the application domain. Although JVM technology has moved forward in leaps and bounds, basic design decisions made in the 90's has anchored JVM implementation.
The Moxie project set out to explore the question: "How would we design a JVM from scratch knowing what we know today?' Amid the mass of design questions we faced, the tension between performance and flexibility was pervasive, persistent and problematic. In this experience paper we describe the Moxie project and its lessons, a process which began with consulting experts from industry and academia, and ended with a fully working prototype.

Garner, R., Blackburn, S. M., and Frampton, D. Effective Prefetch for Mark-Sweep Garbage Collection ISMM 2007, International Symposium on Memory Management, (Montreal, Canada, October 21-22, 2007)

DOI: 10.1145/1296907.1296915 Download:
Patches against Jikes RVM revision 10327:
Abstract
Garbage collection is a performance-critical feature of most modern object oriented languages, and is characterized by poor locality since it must traverse the heap. In this paper we show that by combining two very simple ideas we can significantly improve the performance of the canonical mark-sweep collector, resulting in improvements in application performance. We make three main contributions: 1) we develop a methodology and framework for accurately and deterministically analyzing the tracing loop at the heart of the collector, 2) we offer a number of insights and improvements over conventional design choices for mark-sweep collectors, and 3) we find that two simple ideas --- edge order traversal and software prefetch --- combine to greatly improve garbage collection performance although each is unproductive in isolation.
We perform a thorough analysis in the context of MMTk and Jikes RVM on a wide range of benchmarks and four different architectures. Our baseline system (which includes a number of our improvements) is very competitive with highly tuned alternatives. We show a simple marking mechanism which offers modest but consistent improvements over conventional choices. Finally, we show that enqueuing the edges (pointers) of the object graph rather than the nodes (objects) significantly increases opportunities for software prefetch, despite increasing the total number of queue operations. Combining edge ordered enqueuing with software prefetching yields average performance improvements over a large suite of benchmarks of 20-30% in garbage collection time and 4-6% of total application performance in moderate heaps, across four architectures.

Blackburn, S. M., Hertz, M., McKinley, K. S., Moss, J.E.B., and Yang, T. Profile-based pretenuring ACM Transactions on Programming Languages and Systems (TOPLAS), (27), 1, 2007

DOI: 10.1145/1180475.1180477 Download:
Abstract
Pretenuring can reduce copying costs in garbage collectors by allocating long-lived objects into regions that the garbage collector will rarely, if ever, collect. We extend previous work on pretenuring as follows: (1) We produce pretenuring advice that is neutral with respect to the garbage collector algorithm and configuration. We thus can and do combine advice from different applications. We find for our benchmarks that predictions using object lifetimes at each allocation site in Java programs are accurate, which simplifies the pretenuring implementation. (2) We gather and apply advice to both applications and Jikes RVM, a compiler and runtime system for Java written in Java. Our results demonstrate that building combined advice into Jikes RVM from different application executions improves performance, regardless of the application Jikes RVM is compiling and executing. This build-time advice thus gives user applications some benefits of pretenuring, without any application profiling. No previous work uses profile feedback to pretenure in the runtime system. (3) We find that application-only advice also consistently improves performance, but that the combination of build-time and application-specific advice is almost always noticeably better. (4) Our same advice improves the performance of generational, Older First, and Beltway collectors, illustrating that it is collector neutral. (5) We include an immortal allocation space in addition to a nursery and older generation, and show that pretenuring to immortal space has substantial benefit.

Blackburn, S. M., Garner, R., Hoffman, C., Khan, A. M., McKinley, K. S., Bentzur, R., Diwan, A., Feinberg, D., Frampton, D., Guyer, S. Z., Hirzel, M., Hosking, A., Jump, M., Lee, H., Moss, J. E. B., Phansalkar, A., Stefanovic, D., VanDrunen, T., von Dincklage, D., and Wiedermann, B. The DaCapo Benchmarks: Java Benchmarking Development and Analysis OOPSLA 2006, ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, (Portland, OR, USA, October 22-26, 2006)

DOI: 10.1145/1167473.1167488 Download:
Abstract
Since benchmarks drive computer science research and industry product development, which ones we use and how we evaluate them are key questions for the community. Despite complex runtime tradeoffs due to dynamic compilation and garbage collection required for Java programs, many evaluations still use methodologies developed for C, C++, and Fortran. SPEC, the dominant purveyor of benchmarks, compounded this problem by institutionalizing these methodologies for their Java benchmark suite. This paper recommends benchmarking selection and evaluation methodologies, and introduces the DaCapo benchmarks, a set of open source, client-side Java benchmarks. We demonstrate that the complex interactions of (1) architecture, (2) compiler, (3) virtual machine, (4) memory management, and (5) application require more extensive evaluation than C, C++, and Fortran which stress (4) much less, and do not require (3). We use and introduce new value, time-series, and statistical metrics for static and dynamic properties such as code complexity, code size, heap composition, and pointer mutations. No benchmark suite is definitive, but these metrics show that DaCapo improves over SPEC Java in a variety of ways, including more complex code, richer object behaviors, and more demanding memory system requirements. This paper takes a step towards improving methodologies for choosing and evaluating benchmarks to foster innovation in system design and implementation for Java and other managed languages.

Blackburn, S. M., Garner, R., Hoffman, C., Khan, A. M., McKinley, K. S., Bentzur, R., Diwan, A., Feinberg, D., Frampton, D., Guyer, S. Z., Hirzel, M., Hosking, A., Jump, M., Lee, H., Moss, J. E. B., Phansalkar, A., Stefanovic, D., VanDrunen, T., von Dincklage, D., and Wiedermann, B. The DaCapo Benchmarks: Java Benchmarking Development and Analysis (Extended Version) Australian National University Technical Report TR-CS-06-03, September 2006

Download:
Note that this is an extend version of our OOPSLA paper, which includes extensive data for SPECjvm98 in addition to the DaCapo benchmarks.
Abstract
Since benchmarks drive computer science research and industry product development, which ones we use and how we evaluate them are key questions for the community. Despite complex runtime tradeoffs due to dynamic compilation and garbage collection required for Java programs, many evaluations still use methodologies developed for C, C++, and Fortran. SPEC, the dominant purveyor of benchmarks, compounded this problem by institutionalizing these methodologies for their Java benchmark suite. This paper recommends benchmarking selection and evaluation methodologies, and introduces the DaCapo benchmarks, a set of open source, client-side Java benchmarks. We demonstrate that the complex interactions of (1) architecture, (2) compiler, (3) virtual machine, (4) memory management, and (5) application require more extensive evaluation than C, C++, and Fortran which stress (4) much less, and do not require (3). We use and introduce new value, time-series, and statistical metrics for static and dynamic properties such as code complexity, code size, heap composition, and pointer mutations. No benchmark suite is definitive, but these metrics show that DaCapo improves over SPEC Java in a variety of ways, including more complex code, richer object behaviors, and more demanding memory system requirements. This paper takes a step towards improving methodologies for choosing and evaluating benchmarks to foster innovation in system design and implementation for Java and other managed languages.

Blackburn, S. M. and McKinley, K. S. Transient Caches and Object Streams, Australian National University Technical Report TR-CS-06-03, October 2006

Download:
Abstract
Memory latency limits program performance. Object-oriented languages such as C# and Java exacerbate this problem, but their software engineering benefits make them increasingly popular. We show that current memory hierarchies are not particularly well suited to Java in which object streams write and read a window of short-lived objects that pollute the cache. These observations motivate the exploration of transient caches which assist a parent cache. For an L1 parent cache, transient caches are positioned similarly to a classic L0, providing one cycle access time. Their distinguishing features are (1) they are tiny (4 to 8 lines), (2) they are highly associative, and (3) the processor may seek them in parallel with their parent. They can assist any cache level. To address object stream behavior, we explore policies for read and write instantiation, promotion, filtering, and valid bits to implement no-fetch on write.
Good design points include a parallel L0 (PL0) which improves Java programs by 3% on average, and C by 2% in cycle-accurate simulation over a two-cycle 32KB, 128B line, 2-way L1. A transient qualifying cache (TQ) improves further by a) minimizing pollution in the parent by filtering short-lived lines without temporal reuse, and b) using a write no-fetch policy with per-byte valid bits to eliminate wasted fetch bandwidth. TQs at L1 and L2 improve Java programs by 5% on average and up to 15%. The TQ even achieves improvements when the parent has half the capacity or associativity compared to the original larger L1. The one-cycle access time, a write no-fetch policy, and filtering bestow these benefits. Java motivates this approach, but it also improves for C programs.

Hertz, M., Blackburn, S. M., Moss, J.E.B., McKinley, K. S., and Stefanovic, D. Generating object lifetime traces with Merlin ACM Transactions on Programming Languages and Systems (TOPLAS), (26), 3, pp 476-512, 2006

DOI: 10.1145/1133651.1133654 Download:
Abstract
Programmers are writing a rapidly growing number of programs in object-oriented languages, such as Java and C#, that require garbage collection. Garbage collection traces and simulation speed up research by enabling deeper understandings of object lifetime behavior and quick exploration and design of new garbage collection algorithms. When generating perfect traces, the brute-force method of computing object lifetimes requires a whole-heap garbage collection at every potential collection point in the program. Because this process is prohibitively expensive, researchers often use granulated traces by collecting only periodically, for example, every 32 KB of allocation.We extend the state of the art for simulating garbage collection algorithms in two ways. First, we develop a systematic methodology for simulation studies of copying garbage collection and present results showing the effects of trace granularity on these simulations. We show that trace granularity often distorts simulated garbage collection results compared with perfect traces. Second, we present and measure the performance of a new algorithm called Merlin for computing object lifetimes. Merlin timestamps objects and later uses the timestamps of dead objects to reconstruct when they died. The Merlin algorithm piggybacks on garbage collections performed by the base system. Experimental results show that Merlin can generate traces over two orders of magnitude faster than the brute-force method which collects after every object allocation. We also use Merlin to produce visualizations of heap behavior that expose new object lifetime behaviors.

Huang, X., Blackburn, S. M., Grove, D., and McKinley, K.S. Fast and Efficient Partial Code Reordering: Taking Advantage of Dynamic Recompilation ISMM 2006, International Symposium on Memory Management, (Ottawa, Canada, June 10-11, 2006)

DOI: 10.1145/1133956.1133980 Download:

Abstract
Poor instruction cache locality can degrade performance on modern architectures. For example, our simulation results show that eliminating all instruction cache misses improves performance by as much as 16% for a modestly sized instruction cache. In this paper, we show how to take advantage of dynamic code generation in a Java Virtual Machine (VM) to improve instruction locality at run-time. We develop a dynamic code reordering (DCR) system; a low overhead, online approach for improving instruction locality. DCR has three optimizations: (1) Interprocedural method separation; (2) Intraprocedural code splitting; and (3) Code padding. DCR uses the dynamic call graph and an edge profile that most VMs already collect to separate hot/cold methods and hot/cold code within a method. It also puts padding between methods to minimize conflict misses between frequent caller/callee pairs. It incrementally performs these optimizations only when the VM is optimizing a method at a higher level. We implement DCR in Jikes RVM and show its overhead is negligible. Extensive simulation and run-time experiments show that a simple code space improves average performance on a Pentium 4 by around 6% on SPEC and DaCapo Java benchmarks. These programs however have very small instruction cache footprints that limit opportunities for DCR to improve performance. Consequently, DCR optimizations on average show little effect, sometimes degrading performance and occasionally improving performance by up to 5%. Our work shows that the VM has the potential to dynamically improve instruction locality incrementally by simply piggybacking on hotspot recompilation.

Paz, H., Petrank, E., and Blackburn, S. M.. Age-Oriented Concurrent Garbage Collection CC 2005, Compiler Construction, 14th International Conference, (Edinburgh, UK, April 4-8, 2005). Lecture Notes in Computer Science 3443, Springer.

DOI: 10.1007/b107108 Download:

Abstract
Generational collectors are well known as a tool for shortening pause times incurred by garbage collection and for improving garbage collection efficiency. In this paper, we investigate how to best use generations with on-the-fly collectors. On-the-fly collectors run concurrently with the program threads and induce very short program pauses. Thus, the motivation for incorporating generations is focused at improving the throughput; pauses do not matter, since they are already very short. We propose a new collection approach, denoted age-oriented collection, for exploiting the generational hypothesis to obtain better efficiency. This approach is particularly useful when reference counting is used to collect the old generation, yielding a highly efficient and non-obtrusive on-the-fly collector. Finally, an implementation is provided demonstrating how the age-oriented collector outperforms both the non-generational and the generational collectors' efficiency.

Aplern, B., Augart, S., Blackburn, S. M., Butrico, M., Cocchi, A., Cheng, P., Dolby, J., Fink, S., Grove, D., Hind, M., McKinley, K.S., Mergen, M., Moss, J.E.B., Ngo, T., and Sarkar, V.. The Jikes research virtual machine project: building an open-source research community IBM Systems Journal, (44), 2, pp 399-417, 2005.

ACM Digital Library link Download:
Abstract
This paper describes the evolution of the Jikes Research Virtual Machine project from an IBM internal research project, called Jalapeño, into an open-source project. After summarizing the original goals of the project, we discuss the motivation for releasing it as an open-source project and the activities performed to ensure the success of the project. Throughout, we highlight the unique challenges of developing and maintaining an open-source project designed specifically to support a research community.

Huang, X., Blackburn, S. M., McKinley, K. S., Moss, J. E. B., Wang, Z., and Cheng, P. The Garbage Collection Advantage: Improving Program Locality OOPSLA 2004, ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, (Vancouver, Canada, October 24-28, 2004)

DOI: 10.1145/1028976.1028983 Download:
Abstract
As increases in processor speed continue to outpace increases in cache and memory speed, programs are losing more performance to poor locality. Because copying garbage collectors move objects, they have the opportunity to improve locality for languages such as Java. This paper introduces a new dynamic, online class analysis for finding and exploiting locality in a copying collector. The analysis exploits method sampling in a JIT (just-in-time) optimizing compiler. For each hot (frequently accessed) method, object reordering analysis marks the class fields that the method accesses as hot. Then at garbage collection time, the collector copies referents of hot fields together with their parent. Enhancements to this basic technique include heuristics that decay heat to respond to phase changes, group objects of hot classes together in a separate copy space, and static analysis to exclude cold basic blocks from the reordering analysis. In experiments with Jikes RVM using MMTk on a range of Java programs, the overhead of dynamic class reordering is on average negligible and at most 1.9%. We compare class reordering with a number of static class oblivious orderings (e.g., breadth and depth first). The overall time variation between static orderings can be up to 25% and there is no consistent winner. In contrast, dynamic class reordering always matches or improves over the best static ordering since its history-based copying order tunes memory layout to program traversal.

Blackburn, S. M. and Hosking, A. L. Barriers: Friend or Foe? The 2004 International Symposium on Memory Management (ISMM 2004), (Vancouver, Canada, October 24-25, 2004)

DOI: 10.1145/1029873.1029891 Download:
Patches against Jikes RVM 2.3.3:
Abstract
Modern garbage collectors rely on read and write barriers imposed on heap accesses by the mutator, to keep track of references between different regions of the garbage collected heap, and to synchronize actions of the mutator with those of the collector. It has been a long-standing untested assumption that barriers impose significant overhead to garbage-collected applications. As a result, researchers have devoted effort to development of optimization approaches for elimination of unnecessary barriers, or proposed new algorithms for garbage collection that avoid the need for barriers while retaining the capability for independent collection of heap partitions. On the basis of the results presented here, we dispel the assumption that barrier overhead should be a primary motivator for such efforts.
We present a methodology for precise measurement of mutator overheads for barriers associated with mutator heap accesses. We provide a taxonomy of different styles of barrier and measure the cost of a range of popular barriers used for different garbage collectors within Jikes RVM. Our results demonstrate that barriers impose surprisingly low cost to the mutator, though results vary by architecture. We found that the average overhead for a reasonable generational write barrier was less than 2% on average, and less that 6% in the worst case. Furthermore, we found that the average overhear of an unconditional read barrier on the PowerPC was only 0.85%, while on the AMD it was 8.05%. With both read and write barriers, we found that second order locality effects were sometimes more important that the overhead of the barriers themselves, leading to counter-intuitive speedups in a number of situations.

Jump, M., Blackburn, S. M., McKinley, K. S. Dynamic Object Sampling for Pretenuring. The 2004 International Symposium on Memory Management (ISMM 2004), (Vancouver, Canada, October 24-25, 2004)

DOI: 10.1145/1029873.1029892 Download:
Abstract
Generational garbage collectors make a space-time tradeoff by exploiting the gross statistical object lifetime property that young objects tend to die at a higher rate than old ones. They thus collect the young nursery objects more frequently than old objects. Pretenuring decreases nursery collection work by allocating new, but long-lived objects directly into the old space. This paper introduces a new low-cost dynamic object sampling technique to generate pretenuring advice as the program executes. Every 2^k bytes of allocation, object sampling marks the new object with its allocation site. The collector computes allocation site survival rates using the sampled objects, and then starts pretenuring sites that produce mostly long-lived objects. It occasionally back-samples a site to react to phase changes. Evaluations in Jikes RVM on Java programs show the sampling space and time overheads are low, on average 1 to 2% when the compiler inlines the allocation sequence. As with previous dynamic pretenuring approaches, consistent performance improvements are difficult to attain with dynamic pretenuring and many programs degrade slightly (by 1 to 2%), however we demonstrate a consistent 10% improvement over a number of heap sizes for javac, a SPECjvm benchmark.

Blackburn, S. M., Cheng, P., and McKinley, K. S. Myths and Reality: The Performance Impact of Garbage Collection Sigmetrics - Performance 2004, Joint International Conference on Measurement and Modeling of Computer Systems, (New York, New York, USA, June 12-16, 2004)

DOI: 10.1145/1005686.1005693 Download:
Abstract
This paper explores and quantifies garbage collection (GC) behavior for three whole heap collectors and generational counterparts: copying semi-space, mark-sweep, and reference counting, the canonical algorithms from which essentially all other GC algorithms are derived. Efficient implementations in the memory management toolkit (MMTk) in Jikes RVM share all common mechanisms to provide a clean experimental platform. Performance counters and instrumentation measure timing and memory performance, separating GC and program behavior.
Experiments on SPEC JVM Benchmarks reveal key algorithmic features and how they match program characteristics to explain the direct cost of GC as a function of heap size, and the indirect impact of GC on application performance. Results include the finding that the choice of GC algorithms can improve mutator locality, disputing the myth that "no GC is good GC." We show how the trade-offs in space utilization versus allocation and tracing costs in copying and mark-sweep collectors motivates a copying nursery for newly allocated objects, even without high nursery mortality. We find that object locality and pointer mutations demographics in the mature space are much less sensitive to GC algorithm, but that copying and mark-sweep for the mature space occasionally excel in different programs. This study is unique in its breadth of GC algorithms and its depth of analysis.

Blackburn, S. M., Cheng, P., and McKinley, K. S. Oil and Water? High Performance Garbage Collection in Java with MMTk ICSE 2004, 26th International Conference on Software Engineering, (Edinburgh, Scotland, May 23-28, 2004)

DOI: 10.1109/ICSE.2004.1317436 Download:
Abstract
Increasingly popular languages such as Java and C# require efficient garbage collection. This paper presents the design, implementation, and evaluation of MMTk, a Memory Management Toolkit for and in Java. MMTk is an efficient, composable, extensible, and portable framework for building garbage collectors. MMTk uses design patterns and compiler cooperation to combine modularity and efficiency. The resulting system is more robust, easier to maintain, and has fewer defects than monolithic collectors. Experimental comparisons with monolithic Java and C implementations reveal MMTk has significant performance advantages as well. Performance critical system software typically uses monolithic C at the expense of flexibility. Our results refute common wisdom that only this approach attains efficiency, and suggest that performance critical software can embrace modular design and high-level languages.

Blackburn, S. M. and McKinley, K. S. Ulterior Reference Counting: Fast Garbage Collection without a Long Wait OOPSLA 2003, ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, (Anaheim, CA, USA, October 26-30, 2003)

DOI: 10.1145/949305.949336 Download:
Abstract
General purpose garbage collectors have yet to combine short pause times with high throughput. For example, generational collectors can achieve high throughput. They have modest average pause times, but occasionally collect the whole heap and consequently incur long pauses. At the other extreme, concurrent collectors, including reference counting, attain short pause times but with significant performance penalties. This paper introduces a new hybrid collector that combines copying generational collection for the young objects and reference counting the old objects to achieve both goals. It restricts copying and reference counting to the object demographics for which they perform well. Key to our algorithm is a generalization of deferred reference counting we call Ulterior Reference Counting. Ulterior reference counting safely ignores mutations to select heap objects. We compare a generational reference counting hybrid with pure reference counting, pure mark-sweep, and hybrid generational mark-sweep collectors. This new collector combines excellent throughput, matching a high performance generational mark-sweep hybrid, with low maximum pause

Blackburn, S. M., Jones, R., McKinley, K. S., and Moss, J. E. B. Beltway: Getting around Garbage Collection Gridlock Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), (Berlin, Germany, June 17 - 19, 2002)

DOI: 10.1145/512529.512548 Download:
Abstract
We present the design and implementation of a new garbage collection framework that significantly generalizes existing copying collectors. The Beltway framework exploits and separates object age and incrementality. It groups objects in one or more increments on queues called belts, collects belts independently, and collects increments on a belt in first-in-first-out order. We show that Beltway configurations, selected by command line options, act and perform the same as semi-space, generational, and older-first collectors, and encompass all previous copying collectors of which we are aware.
The increasing reliance on garbage collected languages such as Java requires that the collector perform well. We show that the generality of Beltway enables us to design and implement new collectors that are robust to variations in heap size and improve total execution time over the best generational copying collectors of which we are aware by up to 40%, and on average by 5 to 10%, for small to moderate heap sizes. New garbage collection algorithms are rare, and yet we define not just one, but a new family of collectors that subsumes previous work. This generality enables us to explore a larger design space and build better collectors.

Blackburn, S. M. and McKinley, K. S. In or Out? Putting Write Barriers in Their Place International Symposium on Memory Management (ISMM), (Berlin, Germany, June 20 - 21, 2002)

DOI: 10.1145/512429.512452 Download:

Abstract

In many garbage collected systems, the mutator performs a write barrier for every pointer update. Using generational garbage collectors, we study in depth three code placement options for remembered-set write barriers: inlined, out-of-line, and partially inlined (fast path inlined, slow path out-of-line). The fast path determines if the collector needs to remember the pointer update. The slow path records the pointer in a list when necessary. Efficient implementations minimize the instructions on the fast path, and record few pointers (from 0.16 to 3% of pointer stores in our benchmarks). We find the mutator performs best with a partially inlined barrier, by a modest 1.5% on average over full inlining.

We also study the compilation cost of write-barrier code placement. We find that partial inlining reduces the compilation cost by 20 to 25% compared to full inlining. In the context of just-in-time compilation, the application is exposed to compiler activity. Regardless of the level of compiler activity, partial inlining consistently gives a total running time performance advantage over full inlining on the SPEC JVM98 benchmarks. When the compiler optimizes all application methods on demand and compiler load is highest, partial inlining improves total performance on average by 10.2%, and up to 18.5%.

Stefanovic, D., Hertz, M., Blackburn, S. M., McKinley, K. S., and Moss, J.E.B. Older-first Garbage Collection in Practice: Evaluation in a Java Virtual Machine ACM SIGPLAN Workshop on Memory System Performance (MSP), (Berlin, Germany, June 16, 2002).

DOI: 10.1145/773146.773042 Download:

Abstract

Until recently, the best performing copying garbage collectors used a generational policy which repeatedly collects the very youngest objects, copies any survivors to an older space, and then infrequently collects the older space. A previous study that used garbage-collection simulation pointed to potential improvements by using an Older-First copying garbage collection algorithm. The Older-First algorithm sweeps a fixed-sized window through the heap from older to younger objects, and avoids copying the very youngest objects which have not yet had sufficient time to die. We describe and examine here an implementation of the Older-First algorithm in the Jikes RVM for Java. This investigation shows that Older-First can perform as well as the simulation results suggested, and greatly improves total program performance when compared to using a fixed-size nursery generational collector. We further compare Older-First to a flexible-size nursery generational collector in which the nursery occupies all of the heap that does not contain older objects. In these comparisons, the flexible-nursery collector is occasionally the better of the two, but on average the Older-First collector performs the best.

Hertz, M., Blackburn, S. M., Moss, J.E.B., McKinley, K. S., and Stefanovic, D. Error-Free Garbage Collection Traces: How to Cheat and Not Get Caught ACM Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '02), (Marina Del Ray, CA, U.S.A., June 15-19, 2002).

DOI: 10.1145/511334.511352 Download:

Abstract

Programmers are writing a large and rapidly growing number of programs in object-oriented languages such as Java that require garbage collection (GC). To explore the design and evaluation of GC algorithms quickly, researchers are using simulation based on traces of object allocation and lifetime behavior. The brute force method generates perfect traces using a whole-heap GC at every potential GC point in the program. Because this process is prohibitively expensive, researchers often use granulated traces by collecting only periodically, e.g., every 32K bytes of allocation.

We extend the state of the art for simulating GC algorithms in two ways. First, we present a systematic methodology and results on the effects of trace granularity for a variety of copying GC algorithms. We show that trace granularity often distorts GC performance results compared with perfect traces, and that some GC algorithms are more sensitive to this effect than others. Second, we introduce and measure the performance of a new precise algorithm for generating GC traces which is over 800 times faster than the brute force method. Our algorithm, called Merlin, frequently timestamps objects and later uses the timestamps of dead objects to reconstruct precisely when they died. It performs only periodic garbage collections and achieves high accuracy at low cost, eliminating any reason to use granulated traces.

Blackburn, S. M., Singhai, S., Hertz, M, McKinley, K. S., and Moss, J. E. B. Pretenuring for Java OOPSLA 2001: ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, (Tampa, FL, USA, Oct. 14 - 18, 2001)

DOI: 10.1145/504282.504307 Download:

Abstract

Pretenuring can reduce copying costs in garbage collectors by allocating long-lived objects into regions that the garbage collector will rarely, if ever, collect. We extend previous work on pretenuring as follows. (1) We produce pretenuring advice that is neutral with respect to the garbage collector algorithm and configuration. We thus can and do combine advice from different applications. We find that predictions using object lifetimes at each allocation site in Java programs are accurate, which simplifies the pretenuring implementation. (2) We gather and apply advice to applications and the Jalapeño JVM, a compiler and run-time system for Java written in Java. Our results demonstrate that building combined advice into Jalapeño from different application executions improves performance regardless of the application Jalapeño is compiling and executing. This build-time advice thus gives user applications some benefits of pretenuring without any application profiling. No previous work pretenures in the run-time system. (3) We find that application-only advice also improves performance, but that the combination of build-time and application-specific advice is almost always noticeably better. (4) Our same advice improves the performance of generational and Older First collection, illustrating that it is collector neutral.

Marquez, A., Blackburn, S. M., Mercer, G., and Zigman, J. N. Implementing Orthogonally Persistent Java Advances in Persistent Object Systems: Proceedings of the 9th International Workshop on Persistent Object Systems (POS9), (Lillehammer, Norway, Sept. 6 - 8, 2000).

Springer: link Download:

Abstract

Orthogonally persistent Java combines the power of abstraction over persistence with Java's rich programming environment. In this paper we report our experience in designing and implementing orthogonally persistent Java. Our design approach is anchored by the view that any system that brings together Java and orthogonal persistence should as far as possible avoid diluting the strengths of Java or the principles of orthogonal persistence. Our approach is thus distinguished by three features: complete transparency of persistence, support for both intra and inter application concurrency through ACID transactions, and the preservation of Java's property of portability. In addition to discussing design and implementation, we present results that show that our approach performs credibly.

He, Z., Blackburn, S. M., Kirby, L., and Zigman, J. Platypus: The design and implementation of a flexible high performance object store Advances in Persistent Object Systems: Proceedings of the 9th International Workshop on Persistent Object Systems (POS9), (Lillehammer, Norway, Sept. 6 - 8, 2000).

Springer: link Download:

Abstract

This paper reports the design and implementation of Platypus, a transactional object store. The twin goals of flexibility and performance dominate the design of Platypus. The design includes: strong support for SMP concurrency; stand-alone, client-server and client-peer distribution configurations; configureable logging and recovery; and object management which can accommodate garbage collection and clustering mechanisms. The first implementation of Platypus incorporates a number of innovations. (1) A new recovery algorithm derived from ARIES that removes the need for log seqeuence numbers to be present on store pages. (2) A zero-copy memory-mapped buffer manager with controlled write-back behavior. (3) New data structures for highly concurrent locking and map querying. We present performance results comparing Platypus with a stream-lined implemention of the SHORE object store. For both medium and small OO7 workloads Platypus outperforms SHORE across a wide range of benchmark operations in both `hot' and `cold' settings.

Zigman, J. N., Blackburn, S. M., and Moss, J.E.B. TMOS: A Transactional Garbage Collector Advances in Persistent Object Systems: Proceedings of the 9th International Workshop on Persistent Object Systems (POS9), (Lillehammer, Norway, Sept. 6 - 8, 2000).

Springer: link Download:

Abstract

Defining persistence in terms of reachability is fundamental to achieving orthogonality of persistence. It is implicit to the principles of orthogonal persistence and is a part of the ODMG 3.0 data objects standard. Although space reclamation in the context of persistence by reachability can be achieved automatically using garbage collection, relatively few papers address the problem of implementing garbage collection in a transactional storage system. A transactional GC algorithm must operate correctly in the face of failure, and in particular must deal with the problem of transaction abort, which by undoing changes such as the deletion of references, subverts the GC reachability axiom of `once garbage always garbage'.

In this paper we make two key contributions. First, we present a generic approach to the design of transactional collectors that promotes clarity, generality, and understandability, and then using this approach, we present a new transactional garbage collection algorithm, TMOS. Our design approach brings together three independent components---a mutator, a transactional store, and a GC algorithm. TMOS represents the application of the Mature Object Space family of GC algorithms to the transactional context through our approach to transactional GC design.

Blackburn, S. M. Panel discussion: Supporting Persistent Application Development Advances in Persistent Object Systems: Proceedings of the 9th International Workshop on Persistent Object Systems (POS9), (Lillehammer, Norway, Sept. 6 - 8, 2000).

Springer: link Download:

Abstract

The three papers in this session each address different aspects of the provision of rich environments for persistent application development. The first,which was presented by Erik Vogues, looks at the provision of high level tools for spatiotemporal querying. The second, presented by Nicolas Richer, addresses support for distributed persistent applications. The third, presented by Alan Kaplan, looks at heterolingual persistent programming.

He, Z., Marquez, A., and Blackburn, S. M., Opportunistic Prioritised Clustering Framework (OPCF) Objects and Databases, International Symposium (Sophia Antipolis, France, June 13, 2000) Lecture Notes in Computer Science, vol 1944, Springer, 2001.

Springer: link Download:

Abstract

Ever since the `early days' of database management systems, clustering has proven to be one of the most effective performance enhancement techniques for object oriented database management systems. The bulk of the work in the area has been on static clustering algorithms which re-cluster the object base when the database is static. However, this type of re-clustering cannot be used when 24-hour database access is required. In such situations dynamic clustering is required, which allows the object base to be reclustered while the database is in operation. We believe that most existing dynamic clustering algorithms lack three important properties. These include: the use of opportunism to imposes the smallest I/O footprint for re-organisation; the re-use of prior research on static clustering algorithms; and the prioritisation of re-clustering so that the worst clustered pages are re-clustered first. In this paper, we present OPCF, a framework in which any existing static clustering algorithm can be made dynamic and given the desired properties of I/O opportunism and clustering prioritisation. In addition, this paper presents a performance evaluation of the ideas suggested above and in particular shows the importance of I/O opportunism in improving the performance of dynamic clustering algorithms in a variety of situations. The main contribution of this paper is the observation that existing static clustering algorithms, when transformed via a simple transformation framework such as OPCF, can produce dynamic clustering algorithms that out-perform complex existing dynamic algorithms, in a variety of situations. This makes the solution presented in this paper particularly attractive to real OODBMS system implementers who often prefer to opt for simpler solutions.

Blackburn, S. M. , Cavazos, J., Singhai, S., Khan, A., McKinley, K. S., Moss, J. E. B. Extended Abstract: Profile-Driven Pretenuring for Java OOPSLA'00 Companion, OOPSLA 2001, ACM Conference on Object-Oriented Programming, Systems, Languages and Applications, (Minneapolis, MN, USA, Oct. 15 - 19, 2000).

Download:

Abstract

Pretenuring is a technique for reducing copying costs in garbage collectors. We develop a collector-neutral approach to obtaining object lifetime profile information, and our pretenuring advice is neutral with respect to the collector algorithm. Our simulations using Java programs show that pretenuring significantly reduces copying for generational and older-first collectors.

Marquez, A., and Blackburn, S. M., Chapter 10, Addressing Complexity and Scale in a High Performance Object Server Succeeding with Object Databases: a practical look at today's implementations with Java and XML, Chaudhri, A and Zicari, R eds, John Wiley & Sons, 2001.

Download:

Abstract

The so called `information explosion' has lead to an enormous demand for networked information, which has in turn placed enormous pressure on information servers. The design of high performance server technology has thus become a hot topic in computer science. In this paper we describe how our exposure to a large real-world application has shaped our response to two key issues for high performance object server technologies---the management of complexity and the management of scale.

The Australian Bureau of Statistics' Business Register (BR) is an OODB application that forms a register of all businesses in Australia. The register is fundamental to much of the ABS' economic survey activity and is used by many branches of the large organization. The basis of the register is an object model that reflects the business structure of all Australian businesses, from large multinationals through to corner stores. There are over 100,000,000 objects in the register and it is constantly updated, both through operator-driven data entry and the batch processing of data from other government agencies. Specific requirements are acceptable response time for interactive access for more that 100 users, long and short transaction support, efficient storage and online access to historic information, flexible object version views and schema evolution support.

The challenges raised by the BR are dominated by the problems of complexity and scale. Our response to these challenges has been guided by our view that {\em abstraction} has a basic role in addressing complexity and scale, and by our use of Java as an implementation context.

In this paper we report not only our approach, but also novel technological outcomes which stem from our exposure to the challenges highlighted by the ABS-BR. These outcomes include: portable orthogonally persistent Java, a system for object versioning, a proposal for schema versioning, and a system architecture for scalable object servers based on a separation of programming language and storage system concerns. These outcomes are examined in the context of an ABS-BR technology demonstrator---a small-scale version of the ABS-BR built to test and showcase new technologies for high performance object servers.

Marquez, A., Zigman, J. N., and Blackburn, S. M., Fast Portable Orthogonally Persistent Java Software - Practice & Experience , (30), 4, pp 449-479, 2000.

Download:

Abstract

A powerful feature of the Java programming language is its user-definable class loading policy, which when combined with the namespace independence between class loaders, allows portable implementation of semi-dynamic program transformations. Such transformations can be used for a range of purposes, including optimization and semantic extension.

In this paper we present a framework for semantic extensions in Java. This framework consists of a number of simple but powerful transformations that, among other things, allow us to semantically extend Java to provide orthogonal persistence.

The use of semi-dynamic program transformations lends our orthogonally persistent Java a number of important qualities, including simplicity, portability and a clean model of persistence. Significantly, our implementations are efficient and can outperform in some cases PJama, a well-known orthogonally persistent Java, which is based on a modified virtual machine.

In addition to describing the application of these transformations to orthogonally persistent Java, we foreshadow their use in a number of other contexts, including dynamic instance versioning and instrumentation.

Blackburn, S.M., Hudson, R., Morrison, R., Moss, J.E.B., Munro, D., and Zigman, J. Starting with Termination: A Methodology for Building Distributed Garbage Collection AlgorithmsProceedings of the Australian Computer Science Conference (Gold Coast, Australia, Jan 29-31, 2001).

DOI: 10.1109/ACSC.2001.906619 Download:

Abstract

We propose an effective methodology in which a distributed garbage collector may be derived from a distributed termination algorithm and a centralized garbage collector in a manner that preserves interesting properties of the original collector, such as completeness. To illustrate our technique we show how two distributed termination algorithms, credit recovery and task balancing, may be suitably described; and then map four centralized garbage collectors reference counting, mark/scan, a generational scheme, and the Mature Object Space collector (MOS) onto this description. The advantage of our approach is that, by separating the issues of distribution and collection, we alleviate the difficulty of inventing, understanding, and comparing distributed garbage collection techniques.

Blackburn, S. M., and Zigman, J. N. Concurrency - The fly in the ointment?Advances in Persistent Object Systems: Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3), (Tiburon, CA, U.S.A., Aug. 30 - Sept. 1 1998).

Download:

Abstract

Concurrency is a central pillar of the Java programming language, is implicit in the transactional model of computation adopted by most persistent systems, and has been widely studied in the context of orthogonal persistence. We argue that despite the substantial literature on concurrency control and transaction models for orthogonal persistence, a basic question as to the interaction between concurrency and orthogonal persistence has yet to be adequately addressed.

The demands of orthogonality appear to place orthogonal persistence at odds with more general approaches to concurrency control. Given its stated objective of providing a `complete' computational environment, the future of the orthogonal persistence vision in general, and persistent Java in particular, will depend, to some extent, on the release of this tension through the realization of new approaches to the integration of concurrency and persistence.

This paper addresses both strict transactional and more `open' approaches to managing concurrency in face of persistence, and examines difficulties with each approach. A simple transaction model that relieves some of these difficulties is presented and its limitations briefly examined.

Zigman, J. N., and Blackburn, S. M. Java Finalize Method, Orthogonal Persistence and Transactions. Advances in Persistent Object Systems: Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3), (Tiburon, CA, U.S.A., Aug. 30 - Sept. 1 1998).

Download:

Abstract

Java is a popular, object oriented language that is runtime type safe. As such, it has been seen as an attractive basis for the implementation of orthogonally persistent systems by several research groups. Transactions are widely used as a means of enforcing consistency of the stable image in the face of concurrency, and have been adopted by most groups developing persistent Java systems. However, Java has a user definable finalize method which provides an asynchronous cleanup mechanism. The strict temporal semantics of transactions and the asynchrony of the finalize method seem at odds. This paper describes this conflict and provides a strategy for resolving the problem.

Blackburn, S. M., and Stanton, R. B. The Transactional Object Cache: A foundation for high performance persistent system construction. Advances in Persistent Object Systems: Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3), (Tiburon, CA, U.S.A., Aug. 30 - Sept. 1 1998).

Download:

Abstract

This paper argues that caching, atomicity and layering are fundamental to persistent systems, and that the transactional object cache architecture, as an embodiment of these concerns, provides a foundation for high performance persistent system construction. Central to the paper is a description of the semantics of an abstract transactional object cache architecture that supports a wide range of transactional models and is open to a broad spectrum of transactional cache coherency algorithms. The centrality of the abstraction is a consequence of its role in facilitating the definition of a transactional interface, which is the key to the practical application of the transactional object cache architecture. The utility of the architectural framework in general, and the interface in particular, is argued for in the context of existing systems and systems currently under construction within that framework.

Blackburn, S. M. Persistent Store Interface: A foundation for scalable persistent system design. PhD Thesis, Australian National University, Canberra, Australia, August 1998.

Download:

Abstract

The subject of this thesis is scalability and persistence.

A convergence of computing and communications technologies has lead to the `information explosion'. Demand for information has grown at an unprecedented pace, placing pressure on the scalability of information servers. At the same time there has been a revolution in switching technology which has seen the once exotic tightly coupled distributed memory computer become widely available through commodity components. These two developments in computing and communications technologies come together, the former bringing with it the challenge of constructing systems capable of scaling to address the spiraling demand for information, and the latter offering a scalable hardware architecture upon which such systems can be based.

The most elegant approach to persistent data management lies in the use of orthogonal persistence. Orthogonally persistent programming languages bring together the disparate concerns of programming languages and databases by making the persistence of data a property orthogonal to all others. However, while users are presented with a unified view of the concerns, implementers of orthogonally persistent programming languages must confront the disparity head-on.

The quest to design efficient, scalable, orthogonally persistent systems represents a bringing together of the challenge of constructing systems capable of scaling with the challenge of constructing orthogonally persistent systems. This raises the deeper question as to whether there exists a generalized framework for scalable persistent system design. The framework will bring together the fundamental concerns of concurrency, replication, coherency, latency, and stability.

The major result in this thesis is the description of such a framework. The fundamental concerns are met through a reference architecture based on caching, atomicity, and a layered software architecture.

The framework has been realized in the form of the Persistent Store Interface (PSI). The effectiveness of PSI for scalable persistentsystem construction is demonstrated through a number of experiments with PSI prototypes, both stand-alone and distributed. In addition,two supporting experiments are described, one examining the issues ofdesigning scalable stores that present users with a single store imageand the other examining mechanisms for scalable coherency and recovery.

The development of a generalized and practical framework for scalable persistent system design in this thesis gives cause for optimism thatorthogonal persistence will play an important role in the future of scalable information management.

Blackburn, S. M., and Stanton, R. B. Scalable Multicomputer Object Spaces: a Foundation for High Performance Systems. In Proceedings of the Third International Working Conference on Massively Parallel Programming Models (London, Nov. 12-14 1997), IEEE.

Download:

Abstract

The development of scalable architectures at store levels of a layered model has concentrated on processor parallelism balanced against scalable memory bandwidth, primarily through distributed memory structures of one kind or another. A great deal of attention has been paid to hiding the distribution of memory to produce a single store image across the memory structure. It is unlikely that the distribution and concurrency aspects of scalable computing can be completely hidden at that level.

The paper argues for a store layer which respects the need for caching and replication, and to do so at an "object" level granularity of memory use. These facits are interrelated through atomic processes, leading to an interface for the store which is strongly transactional in character. The paper describes the experimental performance of such a layer on a scalable multi-computer architecture. The behaviour of the store supports the view that a scalable cached "transactional" store architecture is a practical objective for high performance based on parallel computation across distributed memories.

Blackburn, S. M., and Stanton, R. B. Scalable Transactional Cache Coherency: Towards Scalable Persistent Systems. In Proceedings of the Sixth International Parallel Computing Workshop (Canberra, Australia, Sept. 25-26 1997), Fujitsu Laboratories Ltd.

Download:

Abstract

This paper reports on the development of a scalable storage layer to be used as a foundation for the development of scalable persistent programming environments and object-oriented databases.

We identify the challenges associated with the construction of such a storage layer and report on progress in each of these areas. Detailed results of recent experiments on scalable transactional cache coherency are presented.

Blackburn, S. M., and Stanton, R. B. The Transactional Object Cache as a Basis for Persistent Java System Construction. In 2nd International Workshop on Persistence and Java (Half Moon Bay, CA, U.S.A., Aug. 13-15 1997).

Download:

Abstract

The promise of Java as the vehicle for widely used, industrial strength orthogonally persistent systems places a renewed emphasis on implementation technologies for orthogonally persistent systems. The implementation of such systems has been held back by a number of factors, including a breadth of technologies spanning database and programming language research domains, and difficulty in capitalizing on the fruits of the mainstream database research community.

In this paper we present PSI---a practical storage abstraction that separates database and programming language concerns and facilitates the adoption of mainstream transactional storage technology within orthogonally persistent systems. We argue for PSI as the basis for persistent Java system construction with particular reference to how it might be applied to PJama₀ [Atkinson96].

Blackburn, S. M. The Transactional Object Cache as a Basis for Persistent System Construction In A. L. Brown, Ed. Proceedings of the Fourth IDEA Workshop (Magnetic Island, Australia, May 1997).

Blackburn, S. M. High performance transactional stores: Scalable servers = scalable stores? In A. L. Brown, Ed. Proceedings of the Fourth IDEA Workshop (Magnetic Island, Australia, May 1997).

Blackburn, S. M., Scheuerl, S. J. G., Stanton, R. B., and Johnson, C. W. Recovery and page coherency for a scalable multicomputer object store. In 30th Hawaii International Conference on System Sciences (Hawaii, U.S.A., Jan. 7-10 1997), pp 523-532.

Download:

Abstract

This paper presents scalable algorithms for recovery and page coherency in multicomputer object stores. Recovery and coherency are central to object store engineering and distributed memory multicomputers are fundamental to scalable computation. Efficient recovery is implemented through a combination of local logging and a localisation of the transactional workspace model. A vector of update counts is used to efficiently represent global time.

The algorithms have been successfully implemented and tested on a 128 node Fujitsu AP1000 distributed memory multicomputer. The paper presents performance results which indicate good performance and scalability for these algorithms under a range of situations. The work is seen as a step in the continuing development of high performance multicomputer object stores.

Blackburn, S. M. Multicomputer Object Stores: The Single Store Image Approach In A. L. Brown and S. M. Blackburn, Eds. Proceedings of the Third IDEA Workshop (Lamington, Australia, July 1996).

Scheuerl, S. J. G. and Blackburn, S. M. A Recoverable Distributed Stable Store for the AP1000. In A. L. Brown, Ed. Proceedings of the Second IDEA Workshop (Melbourne, Australia, Feb. 1996).

Blackburn, S. M., and Stanton, R. B Multicomputer object stores: the Multicomputer Texas experiment. In R. Connor and S. Nettles, Eds. Seventh International Workshop on Persistent Object Systems (Cape May, NJ, U.S.A., May 1996).

Download:

Abstract

The paper is about design of object stores for distributed memory computers. Problems of distribution within such stores are described through the design of Multicomputer Texas, a system derived from the Texas store [Singhal92] and implemented on a scalable multicomputer (a Fujitsu AP1000). Problems discussed include creating a single image of an object space across multicomputer architectures, tradeoffs between page-based and object-based granularity, the distribution of store level services and the management of concurrency and persistance within those distributed services. Problems of building layered software on multicomputers pervade these issues. Preliminary scalability performance figures for Multicomputer Texas are also presented.

Blackburn, S. M.

Encoding of Arbitrary Images by Raster-Chain Coding of Cracks, In K. Ngan, Ed. IEEE Visual Signal Processing and Communications Workshop (Melbourne, Australia, Sep. 1993) pp. 85-88.

Blackburn, S. M. Extraction of Color Region Boundaries, In M. Takagi, Ed. MVA'92, IAPR Workshop on Machine Vision Applications (Tokyo, Japan, Dec. 1992), pp. 63-66.