We present the sticky trie, a new variant of the standard trie data structure that achieves high-performing atomic insertions and lookups for large key universes by precluding deletions. It has applications in several areas, including address tracking, logging, and garbage collection. By leveraging features of a modern operating system, we show how a runtime can exploit the absence of deletions to realize an efficient sticky-trie implementation.

A large body of data-flow analyses exists for analyzing and optimizing sequential code. Unfortunately, much of it cannot be directly applied on parallel code, for reasons of correctness. This article presents a technique to automatically, aggressively, yet safely apply sequentially-sound data-flow transformations, without change , on shared-memory programs. The technique is founded on the notion of program references being “siloed” on certain control-flow paths. Intuitively, siloed references are free of interference from other threads within the confines of such paths. Data-flow transformations can, in general, be unblocked on siloed references. The solution has been implemented in a widely used compiler. Results on benchmarks from SPLASH-2 show that performance improvements of up to 41% are possible, with an average improvement of 6% across all the tested programs over all thread counts.

Programming with atomic sections is a promising alternative to locks since it raises the abstraction and removes deadlocks at the programmer level. However, implementations of atomic sections using software transactional memory (STM) support have significant bookkeeping overheads. Additionally, because of the speculative nature of transactions, aborts can be frequent greatly lowering application performance. Thus regardless of the STM implementation, tools need to be available to programmers that provide insights into the runtime characteristics of an application as well as provide means to improve performance. This paper attempts to identify the source of an abort at the granularity of a transactional memory reference. The resulting abort patterns are captured in the form of a runtime abort graph (RAG). We show how to build this graph efficiently using compiler instrumentation. We then describe a technique that works on the RAG and automatically recommends STM policy changes to improve performance. Detailed experimental results are presented showing the tradeoffs in building the RAG and its use in reducing aborts and improving performance.

A large body of data-flow analyses exists for analyzing and optimizing sequential code. Unfortunately, much of it cannot be directly applied on parallel code, for reasons of correctness. This paper presents a technique to automatically, aggressively, yet safely apply sequentially-sound data-flow transformations, without change, on shared-memory programs. The technique is founded on the notion of program references being "siloed" on certain control-flow paths. Intuitively, siloed references are free of interference from other threads within the confines of such paths. Data-flow transformations can, in general, be unblocked on siloed references.

Nondeferred reference-counting (RC) garbage collection is among the oldest memory-management methods. Despite offering unique advantages, little attention has been paid on how to correctly implement it for modern programming languages. This paper revisits this collection method and describes how to implement it for a modern object-oriented language in an optimizing compiler.

Numerous optimizations exist for improving the performance of nondeferred reference-counting (RC) garbage collection. Their designs are ad hoc, intended to exploit different count removal opportunities. This paper shows that many of these optimizations can be unified using a notion called overlooking roots. The paper also shows how the notionenables more powerful versions of past optimizations and makes new optimizations possible. While recent static analyses have dramatically improved nondeferred RC performance, margins relative to the deferred variant were still significant in the worst case. With the optimizations made possible by overlooking roots, we show that these margins can be reduced to within 4% on nearly all programs in a test suite, at even large heap sizes, and to within 23% in the worst case.

Abstract A whole‐program MATLAB to C translation system is presented. The paper outlines the motivation for the problem, discusses the system's architecture, its features and limitations. The translator's operation is explained using an example input program. Details are given on how the system implements and specializes some of the language's built‐in primitives. Finally, the paper reports measurements evaluating the execution time and memory usage of the translated sources, and the compilation time required for the translations. Copyright © 2006 John Wiley & Sons, Ltd.

Reference counting is a well-known technique for automatic memory management, offering unique advantages over other forms of garbage collection. However, on account of the high costs associated with the maintenance of up-to-date tallies of references from the stack, deferred variants are typically used in modern implementations. This partially sacrifices some of the benefits of non-deferred reference-counting (RC) garbage collection, like the immediate reclamation of garbage and short collector pause times.This paper presents a series of optimizations that target the stack and substantially enhance the throughput of nondeferred RC collection. A key enabler is a new static analysis and optimization called RC subsumption that significantly reduces the overhead of maintaining the stack contribution to reference counts. We report execution time improvements on a benchmark suite of ten C# programs, and show how RC subsumption, aided with other optimizations, improves the performance of nondeferred RC collection by as much as a factor of 10, making possible running times that are within 32% of that with an advanced traversal-based collector on seven programs, and 19% of that with a deferred RC collector on eight programs. This is in the context of a baseline RC implementation that is typically at least a factor of 6 slower than the tracing collector and a factor of 5 slower than the deferred RC collector.

The problem of inferring array shapes ahead of time in languages that exhibit both implicit and dynamic typing is a critical one because the ramifications of its solution are the better organization of array storage through compaction and reuse, and the generation of high-performance code through specialization by shape. This article addresses the problem in a prototypical implicitly and dynamically typed array language called MATLAB. The approach involves modeling the language's shape semantics using an algebraic system, and applying term rewriting techniques to evaluate expressions under this algebra. Unlike prior efforts at array shape determination, this enables the deduction of valuable shape information even when array extents are compile-time unknowns. Furthermore, unlike some previous methods, our approach doesn't impose monotonicity requirements on an operator's shape semantics. The work also describes an inference methodology and reports measurements from a type inference engine called MAGICA. In a benchmark suite of 17 programs, the shape inference subsystem in MAGICA detected the equivalence of over 61% of the symbolic shapes in six programs, and over 57% and 37% of the symbolic shapes in two others. In the remaining nine programs, all array shapes were inferred to be compile-time constants.

Static array storage optimization in MATLAB.

This paper presents a compilation framework that enables efficient sharing of executable code across distinct Java Virtual Machine (JVM) instances. High-performance JVMs rely on run-time compilation, since static compilation cannot handle many dynamic features of Java. These JVMs suffer from large memory footprints and high startup costs, which are serious problems for embedded devices (such as hand held personal digital assistants and cellular phones) and scalable servers. A recently proposed approach called quasi-static compilation overcomes these difficulties by reusing precompiled binary images after performing validation checks and stitching on them (i.e., adapting them to a new execution context), falling back to interpretation or dynamic compilation whenever necessary. However, the requirement in our previous design to duplicate and modify the executable binary image for stitching is a major drawback when targeting embedded systems and scalable servers. In this paper, we describe a new approach that allows stitching to be done on an indirection table, leaving the executable code unmodified and therefore writable to readonly memory. On embedded devices, this saves precious space in writable memory. On scalable servers, this allows a single image of the executable to be shared among multiple JVMs, thus improving scalability. Furthermore, we describe a novel technique for dynamically linking classes that uses traps to detect when a class should be linked and initialized. Like back-patching, the technique allows all accesses after the first to proceed at full speed, but unlike back-patching, it avoids the modification of running code. We have implemented this approach in the Quicksilver quasi-static com-

Ownership sets are fundamental to the partitioning of program computations across processors by the owner-computes rule. These sets arise due to the mapping of arrays onto processors. In this paper, we focus on how ownership sets can be efficiently determined in the context of the HPF language and show how the structure of these sets can be symbolically characterized in the presence of arbitrary array alignment and array distribution directives. Our starting point is a system of equalities and inequalities due to Ancourt et al. (1995) that captures the array mapping problem in HPF. We arrive at a refined system that enables us to efficiently solve for the ownership set using the Fourier-Motzkin Elimination technique and that requires the course vector as the only auxiliary vector. The formulation makes it possible to enumerate the elements of the ownership set exactly once, a feature that is very beneficial when such sets are applied to handle DO loops qualified by HPF's INDEPENDENT directive. We develop important and general properties pertaining to HPF alignments and distributions and show how they can be used to eliminate redundant communication due to array replication. Polynomial-time schemes that determine whether the ownership set of a particular processor, with respect to some array, is the empty set or whether the ownership set of every processor, with respect to some array, is the empty set, are presented. We show how distribution directives with unspecified processor meshes can be efficiently handled at compile time. We also show how to avoid the generation of communication code when pairs of array references are ultimately mapped onto the same processors. Experimental data demonstrating the improved code performance that the latter optimization enables is presented and discussed.

Recently, high-level languages such as MATLAB have become popular in prototyping algorithms in domains such as signal and image processing. Many of these applications whose subtasks have diverse execution requirements, often employ distributed, heterogeneous, reconfigurable systems. These systems consist of an interconnected set of heterogeneous processing resources that provide a variety of architectural capabilities. The objective of the MATCH (MATLAB Compiler for Heterogeneous Computing Systems) compiler project at Northwestern University is to make it easier for the users to develop efficient code for distributed heterogeneous, reconfigurable computing systems. Towards this end we are implementing and evaluating an experimental prototype of a software system that will take MATLAB descriptions of various applications, and automatically map them on to a distributed computing environment consisting of embedded processors, digital signal processors and field-programmable gale arrays built from commercial off-the-shelf components. We provide an overview of the MATCH compiler and discuss the testbed which is being used to demonstrate our ideas. We present preliminary experimental results on some benchmark MATLAB programs with the use of the MATCH compiler.

MATLAB is one of the most popular languages for desktop numerical computations as well as for signal and image processing applications. Applying parallel processing techniques to improve performance of MATLAB codes has been the goal of many recent works. Most current frameworks require the user to specify parallelism and/or information regarding type/shape of the variables, thereby sacrificing the user friendliness which is one of the most popular MATLAB features. Other systems work on a restricted subset of MATLAB, thereby limiting the class of applications MATLAB can support. We present a runtime system capable of executing MATLAB code in parallel without any user intervention. The runtime system performs automatic parallelization and type/shape inference of the code at runtime. A unique feature of the runtime system is its capability to automatically adapt to changes in the underlying architecture, making it particularly useful for systems where predicting performance statically is difficult. We present experimental results obtained for the runtime system running on SGI Origin2000 shared memory multiprocessor.

We present a novel framework of a Web-based automated parallel CAD environment. The goal of this project is to make available to the CAD community a growing number of design and test applications that support standard interfaces and execute efficiently in a parallel environment. The design files of a user working on a remote machine are transparently shipped to the local Compute Center, the relevant computation is performed in a parallel environment and then the results are returned back to the user. A job submission and scheduling tool ensures proper load balance and maximal usage of the various parallel machines. The whole process is done efficiently and transparently without the user having to bother about any low-level details. At present, a number of parallel CAD tools including a placement tool, a fault simulator and a VHDL simulator are supported. Results from a preliminary implementation are impressive and show the feasibility of the approach.