bluuebunny/crossref_metadata_2025 huggingface dataset:
Architectural support for fast symmetric-key cryptography
Authors: Burke Jerome , McDonald John , Austin Todd
Published: November 2005

The emergence of the Internet as a trusted medium for commerce and communication has made cryptography an essential component of modern information systems. Cryptography provides the mechanisms necessary to implement accountability, accuracy, and confidentiality in communication. As demands for secure communication bandwidth grow, efficient cryptographic processing will become increasingly vital to good system performance.In this paper, we explore techinques to improve the performance of symmetric key cipher algorithms. Eight popular strong encryption algorithms are examined in detail. Analysis reveals the algorithms are computaionally complex and contain little parallelism. Overall throughput on high-end microprocessor is quite poor, a 600 Mhz processor is incapable of saturation a T3 communication line with 3DES (triple DES) encrypted data.We introduce new instructions taht improve the efficiency of the analyzed algorithms. Our approach adds instruction set support for fast substitutions, general permutations, rotates, and modular arithmetic. Performance analysis of the optimized ciphers shows an overall speedup of 59% over a baseline machine with rotate instructions and 74% speedup over a baseline without rotates. Even higher speedups are demonstrated with optimized subtitutions (SBOXes) and additional functional unit resources. our analyses of the original and optimized algorithms suggest future directions for the design of high-performance programmable cryptographic processors.
OceanStore
Authors: Kubiatowicz John , Bindel David , Chen Yan , Czerwinski Steven , Eaton Patrick , Geels Dennis , Gummadi Ramakrishan , Rhea Sean , Weatherspoon Hakim , Weimer Westley , Wells Chris , Zhao Ben
Published: November 2005

OceanStore is a utility infrastructure designed to span the globe and provide continuous access to persistent information. Since this infrastructure is comprised of untrusted servers, data is protected through redundancy and cryptographic techniques. To improve performance, data is allowed to be cached anywhere, anytime. Additionally, monitoring of usage patterns allows adaptation to regional outages and denial of service attacks; monitoring also enhances performance through pro-active movement of data. A prototype implementation is currently under development.
Software profiling for hot path prediction
Authors: Duesterwald Evelyn , Bala Vasanth
Published: November 2005

Recently, there has been a growing interest in exploiting profile information in adaptive systems such as just-in-time compilers, dynamic optimizers and, binary translators. In this paper, we show that sophisticated software profiling schemes that provide highly accurate information in an offline setting are ill-suited for these dynamic code generation systems. We experimentally demonstrate that hot path predictions must be made early in order to control the rising cost of missed opportunity that result from the prediction delay. We also show that existing sophisticated path profiling schemes, if used in an online setting, offer no prediction advantages over simpler schemes that exhibit much lower runtime overheads.Based on these observation we developed a new low-overhead software profiling scheme for hot path prediction. Using an abstract metric we compare our scheme to path profile based prediction and show that our scheme achieves comparable prediction quality. In our second set of experiments we include runtime overhead and evaluate the performance of our scheme in a realistic application: Dynamo, a dynamic optimization system. The results show that our prediction scheme clearly outperforms path profile based prediction and thus confirm that
less
profiling as exhibited in our scheme will actually lead to
more
effective hot path prediction.
OS and compiler considerations in the design of the IA-64 architecture
Authors: Zahir Rumi , Ross Jonathan , Morris Dale , Hess Drew
Published: November 2005

Increasing demands for processor performance have outstripped the pace of process and frequency improvements, pushing designers to find ways of increasing the amount of work that can be processed in parallel. Traditional RISC architectures use hardware approaches to obtain more instruction-level parallelism, with the compiler and the operating system (OS) having only indirect visibility into the mechanisms used.The IA-64 architecture [14] was specifically designed to enable systems which create and exploit high levels of instruction-level parallelism by explicitly encoding a program's parallelism in the instruction set [25]. This paper provides a qualitative summary of the IA-64 architecture features that support control and data speculation, and register stacking. The paper focusses on the functional synergy between these architectural elements (rather than their individual performance merits), and emphasizes how they were designed for cooperation between processor hardware, compilers and the OS.
Slipstream processors
Authors: Sundaramoorthy Karthik , Purser Zach , Rotenberg Eric
Published: November 2005

Processors execute the full dynamic instruction stream to arrive at the final output of a program, yet there exist shorter instruction streams that produce the same overall effect. We propose creating a shorter but otherwise equivalent version of the original program by removing ineffectual computation and computation related to highly-predictable control flow. The shortened program is run concurrently with the full program on a chip multiprocessor or simultaneous multithreaded processor, with two key advantages:1)
Improved single-program performance
. The shorter program speculatively runs ahead of the full program and supplies the full program with control and data flow outcomes. The full program executes efficiently due to the communicated outcomes, at the same time validating the speculative, shorter program. The two programs combined run faster than the original program alone. Detailed simulations of an example implementation show an average improvement of 7% for the SPEC95 integer benchmarks.2)
Fault tolerance
. The shorter program is a subset of the full program and this partial-redundancy is transparently leveraged for detecting and recovering from transient hardware faults.
Regular expression types for XML
Authors: Hosoya Haruo , Vouillon Jérôme , Pierce Benjamin C.
Published: November 2005

We propose
regular expression types
as a foundation for XML processing languages. Regular expression types are a natural generalization of Document Type Definitions (DTDs), describing structures in XML documents using regular expression operators (i.e., *, ?, |, etc.) and supporting a simple but powerful notion of
subtyping
.The decision problem for the subtype relation is EXPTIME-hard, but it can be checked quite efficiently in many cases of practical interest. The subtyping algorithm developed here is a variant of Aiken and Murphy's set-inclusion constraint solver, to which are added several optimizations and two new properties: (1) our algorithm is provably complete, and (2) it allows a useful "subtagging" relation between nodes with different labels in XML trees.
Information flow inference for free
Authors: Pottier François , Conchon Sylvain
Published: November 2005

This paper shows how to systematically extend an arbitrary type system with dependency information, and how soundness and non-interference proofs for the new system may rely upon, rather than duplicate, the soundness proof of the original system. This allows enriching virtually any of the type systems known today with information flow analysis, while requiring only a minimal proof effort.Our approach is based on an untyped operational semantics for a labelled calculus akin to core ML. Thus, it is simple, and should be applicable to other computing paradigms, such as object or process calculi.The paper also discusses access control, and shows it may be viewed as entirely independent of information flow control. Letting the two mechanisms coexist, without interacting, yields a simple and expressive type system, which allows, in particular, "selective" declassification.
FranTk - a declarative GUI language for Haskell
Authors: Sage Meurig
Published: November 2005

FranTk is a new high level library for programming Graphical User Interfaces (GUIs) in Haskell. It is based on Fran (Functional Reactive Animation), and uses the notions of
Behaviors
and
Events
to structure code. Behaviors are time-varying, reactive values. They can be used to represent the state of an application. Events are streams of values that occur at discrete points in time. They can be used, for instance, to represent user input. FranTk allows user interfaces to be structured in a more declarative manner than has been possible with previous functional GUI libraries. We demonstrate, through a series of examples, how this is achieved, and why it is important. These examples are elements of a prototype, Air Traffic Control simulator. FranTk uses a binding to the popular Tcl/Tk toolkit to provide a powerful set of platform independent set of widgets. It has been released as a Haskell library that runs under Hugs and GHC.
Dynamo
Authors: Bala Vasanth , Duesterwald Evelyn , Banerjia Sanjeev
Published: November 2005

We describe the design and implementation of Dynamo, a software dynamic optimization system that is capable of transparently improving the performance of a native instruction stream as it executes on the processor. The input native instruction stream to Dynamo can be dynamically generated (by a JIT for example), or it can come from the execution of a statically compiled native binary. This paper evaluates the Dynamo system in the latter, more challenging situation, in order to emphasize the limits, rather than the potential, of the system. Our experiments demonstrate that even statically optimized native binaries can be accelerated Dynamo, and often by a significant degree. For example, the average performance of -O optimized SpecInt95 benchmark binaries created by the HP product C compiler is improved to a level comparable to their -O4 optimized version running without Dynamo. Dynamo achieves this by focusing its efforts on optimization opportunities that tend to manifest only at runtime, and hence opportunities that might be difficult for a static compiler to exploit. Dynamo's operation is transparent in the sense that it does not depend on any user annotations or binary instrumentation, and does not require multiple runs, or any special compiler, operating system or hardware support. The Dynamo prototype presented here is a realistic implementation running on an HP PA-8000 workstation under the HPUX 10.20 operating system.
A certifying compiler for Java
Authors: Colby Christopher , Lee Peter , Necula George C. , Blau Fred , Plesko Mark , Cline Kenneth
Published: November 2005

This paper presents the initial results of a project to determine if
the techniques of
proof-carrying code
and
certifying compilers
can be applied to programming languages of realistic size and complexity. The experiment shows that: (1) it is possible to implement a certifying native-code compiler for a large subset of the Java programming language; (2) the compiler is freely able to apply many standard local and global optimizations; and (3) the PCC binaries it produces are of reasonable size and can be rapidly checked for type safety by a small proof-checker. This paper also presents further evidence that PCC provides several advantages for compiler development. In particular, generating proofs of the target code helps to identify compiler bugs, many of which would have been difficult to discover by testing.
Transforming loops to recursion for multi-level memory hierarchies
Authors: Yi Qing , Adve Vikram , Kennedy Ken
Published: November 2005

Recently, there have been several experimental and theoretical results
showing significant performance benefits of recursive algorithms on both
multi-level memory hierarchies and on shared-memory systems. In particular, such algorithms have the data reuse characteristics of a blocked algorithm that is simultaneously blocked at many different levels. Most existing applications, however, are written using ordinary loops. We present a new compiler transformation that can be used to convert loop nests into recursive form automatically. We show that the algorithm is fast and effective, handling loop nests with arbitrary nesting and control flow. The transformation achieves substantial performance improvements for several linear algebra codes even on a current system with a two level cache hierarchy. As a side-effect of this work, we also develop an improved algorithm for transitive dependence analysis (a powerful technique used in the recursion transformation and other loop transformations)that is much faster than the best previously known algorithm in practice.
Symbolic bounds analysis of pointers, array indices, and accessed memory regions
Authors: Rugina Radu , Rinard Martin
Published: November 2005

This paper presents a novel framework for the symbolic bounds analysis of pointers, array indices, and accessed memory regions. Our
framework formulates each analysis problem as a system of inequality constraints between symbolic bound polynomials. It then reduces the constraint system to a linear program. The solution to the linear program provides symbolic lower and upper bounds for the values of pointer and array index variables and for the regions of memory that each statement and procedure accesses. This approach eliminates fundamental problems associated with applying standard fixed-point approaches to symbolic
analysis problems. Experimental results from our implemented compiler show that the analysis can solve several important problems, including static
race detection, automatic parallelization, static detection of array
bounds violations, elimination of array bounds checks, and
reduction of the number of bits used to store computed values.
Effective synchronization removal for Java
Authors: Ruf Erik
Published: November 2005

We present a new technique for removing unnecessary synchronization operations from statically compiled Java programs. Our approach improves upon current efforts based on escape analysis, as it can eliminate synchronization operations even on objects that escape their allocating threads. It makes use of a compact, equivalence-class-based representation that eliminates the need for fixed point operations during the analysis.

We describe and evaluate the performance of an implementation in the
Marmot native Java compiler. For the benchmark programs examined, the optimization removes 100% of the dynamic synchronization operations in single-threaded programs, and 0-99% in multi-threaded programs, at a low cost in additional compilation time and code growth.
ABCD
Authors: Bodík Rastislav , Gupta Rajiv , Sarkar Vivek
Published: November 2005

To guarantee typesafe execution, Java and other strongly typed languages require bounds checking of array accesses. Because array-bounds checks may raise exceptions, they block code motion of instructions with side effects, thus preventing many useful code optimizations, such as partial redundancy elimination or instruction scheduling of memory operations. Furthermore, because it is not expressible at bytecode level, the elimination of bounds checks can only be performed at
run time
, after the bytecode program is loaded. Using existing powerful bounds-check optimizers at run time is not feasible, however, because they are too heavyweight for the dynamic compilation setting.

ABCD is a light-weight algorithm for elimination of Array Bounds Checks on Demand. Its design emphasizes simplicity and efficiency. In essence, ABCD works by adding a few edges to the SSA value graph and performing a simple traversal of the graph. Despite its simplicity, ABCD is surprisingly powerful. On our benchmarks, ABCD removes on average 45% of dynamic bound check instructions, sometimes achieving near-ideal optimization.

The efficiency of ABCD stems from two factors. First, ABCD works on
a
sparse
representation. As a result, it requires on average fewer than 10 simple analysis steps per bounds check. Second, ABCD is
demand-driven
. It can be applied to a set of frequently executed (hot) bounds checks, which makes it suitable for the dynamic-compilation setting, in which compile-time cost is constrained but hot statements are known.
uu
for programming languages
Authors: Ferreira Ulisses
Published: November 2005

The Internet has motivated new programming language features and, in this article, we consider that programming for such a global environment requires the ability to deal with what is unknown because connections often fail or delay and programs should be robust. Thus, we concentrate on this particular issue.In this article we present
uu
, a value that can represent lack of information in programming languages. A thesis is that this value is a good feature towards the unification of some programming paradigms. Thus, in this article, we explore constructs as consequences of
uu
in such languages together with examples where this value helps in programming, and we explain the relationship between
uu
and another programming paradigm. The implementation of
uu
is also briefly discussed.
Java 2 distributed object middleware performance analysis and optimization
Authors: Juric Matjaz B. , Rozman Ivan , Nash Simon
Published: November 2005

This paper is focused on the performance analysis, comparison and optimization of distributed object middleware for Java 2: RMI (Remote Method Invocation), CORBA IDL (Interface Definition Language) and RMI-IIOP (Remote Method Invocation on Internet Inter-ORB Protocol). The paper presents the following contributions to the research on distributed object performance. First, a detailed performance analysis is provided with the comparison. These results help to understand how the models perform. Second, an overhead analysis has been done, which explains why there are differences in peRformance. Third, optimizations and improved performance for RMI-IIOP and CORBA IDL are presented. These show considerably better performance in all areas compared to the original versions.
VLSI assist for a multiprocessor
Authors: Beck Bob , Kasten Bob , Thakkar Shreekant
Published: November 2005

Multiprocessors have long been of interest to computer community. They provide the potential for accelerating applications through parallelism and increased throughput for large multi-user system. Three factors have limited the commercial success of multiprocessor systems; entry cost, range of performance, and ease of application. Advances in very large scale integration (VLSI) and in computer aided design (CAD) have removed these limitations, making possible a new class of multiprocessor systems based on VLSI components. A set of requirements for building an efficient shared multiprocessor system are discussed, including: low-level mutual exclusion, interrupt distribution, inter-processor signaling, process dispatching, caching, and system configuration. A system that meets these requirements is described and evaluated.
The dragon processor
Authors: Atkinson Russell R. , McCreight Edward M.
Published: November 2005

The Xerox PARC Dragon is a VLSI research computer that uses several techniques to achieve dense code and fast procedure calls in a system that can support multiple processors on a central high bandwidth memory bus.
Cheap hardware support for software debugging and profiling
Authors: Cargill T. A. , Locanthi B. N.
Published: November 2005

We wish to determine the effectiveness of some simple hardware for debugging and profiling compiled programs on a conventional processor. The hardware cost is small -- a counter decremented on each instruction that raises an exception when its value becomes zero. With the counter a debugger can provide data watchpoints and reverse execution: a profiler can measure the total instruction cost of a code segment and sample the program counter accurately. Such a counter has been included on a single-board MC68020 workstation, for which system software is currently being written. We will report our progress at the symposium.
Compiling Smalltalk-80 to a RISC
Authors: Bush William R. , Samples A. Dain , Ungar David , Hilfinger Paul N.
Published: November 2005

The Smalltalk On A RISC project at U. C. Berkeley proves that a high-level object-oriented language can attain high performance on a modified reduced instruction set architecture. The single most important optimization is the removal of a layer of interpretation, compiling the bytecoded virtual machine instructions into low-level, register-based, hardware instructions. This paper describes the compiler and how it was affected by SOAR architectural features. The compiler generates code of reasonable density and speed. Because of Smalltalk-80's semantics, relatively few optimizations are possible, but hardware and software mechanisms at runtime offset these limitations. Register allocation for an architecture with register windows comprises the major task of the compiler. Performance analysis suggests that SOAR is not simple enough; several hardware features could be efficiently replaced by instruction sequences constructed by the compiler.
Superoptimizer: a look at the smallest program
Authors: Massalin Henry
Published: November 2005

Given an instruction set, the superoptimizer finds the shortest program to compute a function. Startling programs have been generated, many of them engaging in convoluted bit-fiddling bearing little resemblance to the source programs which defined the functions. The key idea in the superoptimizer is a probabilistic test that makes exhaustive searches practical for programs of useful size. The search space is defined by the processor's instruction set, which may include the whole set, but it is typically restricted to a subset. By constraining the instructions and observing the effect on the output program, one can gain insight into the design of instruction sets. In addition, superoptimized programs may be used by peephole optimizers to improve the quality of generated code, or by assembly language programmers to improve manually written code.
Performance and architectural evaluation of the PSI machine
Authors: Taki Kazuo , Nakajima Katzuto , Nakashima Hiroshi , Ikeda Morihiro
Published: November 2005

We evaluated a Prolog machine PSI (Personal Sequential Inference machine) for the purpose of improving and redesigning it. In this evaluation, we measured the execution speed and the dynamic characteristics of cache memory, register file, and branching hardware introduced for high-speed execution of Prolog programs.Execution speed of the PSI firmware interpreter was found to be comparable to that of the DEC-10 Prolog compiled code on the DEC-2060. It was also found that PSI was faster than DEC for executing programs containing much unification and backtracking that require runtime processing.With the cache memory, the hit ratio for application programs was found higher than 96%; this demonstrates that the Prolog execution has much memory access locality. The memory access frequency and the appearance ratio between Read and Write command were also investigated.Concerning the register file, use rate of each dedicated access mode was measured and effect of each mode was discussed. In the branching function we confirmed a high appearance rate of conditional branches and multi-way branches based on tag values.
On effectiveness of GC in Java
Authors: Shaham Ran , Kolodner Elliot K. , Sagiv Mooly
Published: November 2005

We study the effectiveness of garbage collection (GC) algorithms by measuring the time difference between the actual collection time of an object and the potential earliest collection time for that object. Our ultimate goal is to use this study in order to develop static analysis techniques that can be used together with GC to allow earlier reclamation of objects. The results may also be used to pinpoint application source code that could be rewritten in a way that would allow more timely GC.

Specifically, we compare the objects reachable from the root set to the ones that are actually used again. The idea is that GC could reclaim unused objects even if they are reachable from the root set. Thus, our experiments indicate a kind of upper bound on storage savings that could be achieved. We also try to characterize these objects in order to understand the potential benefits of various static analysis algorithms.

The Java Virtual Machine (JVM) was instrumented to measure objects that are reachable, but not used again, and to characterize these objects. Experimental results are shown for the SPECjvm98 benchmark suite. The potential memory savings for these benchmarks range from 23% to 74%.
Thread-specific heaps for multi-threaded programs
Authors: Steensgaard Bjarne
Published: November 2005

Garbage collection for a multi-threaded program typically involves either stopping all threads while doing the collection or involves copious amounts of synchronization between threads. However, a lot of data is only ever visible to a single thread, and such data should ideally be collected without involving other threads.

Given an escape analysis, a memory management system may allocate thread-specific data in thread-specific heaps and allocate shared data in a shared heap. Garbage collection of data in a thread-specific heaps can be done independent of other threads and of data in their thread-specific heaps. For multi-threaded programs, thread-specific heaps allow reduced garbage collection latency for active threads. On multi-processor computers, thread-specific heaps allow concurrent garbage collection of different thread-specific heaps with minimal synchronization overhead.

We present an escape analysis and a sample memory management system using thread-specific heaps.
Designing a trace format for heap allocation events
Authors: Chilimbi Trishul , Jones Richard , Zorn Benjamin
Published: November 2005

Dynamic storage allocation continues to play an important role in the performance and correctness of systems ranging from user productivity software to high-performance servers. While algorithms for dynamic storage allocation have been studied for decades, much of the literature is based on measuring the performance of benchmark programs unrepresentative of many important allocation-intensive workloads. Furthermore, to date no standard has emerged or been proposed for publishing and exchanging representative allocation workloads. In this paper, we describe a preliminary design of a trace format for such workloads and investigate its effectiveness at representing large allocation traces. Our proposal allows for a flexible encoding of information in the trace to achieve greater compression. We evaluate our preliminary design in two dimensions. First, we measure how effective these encodings are at reducing trace size. Second we consider how a meta-level specification language could be used to describe such formats and to generate trace readers and writers automatically.
Concurrent garbage collection using program slices on multithreaded processors
Authors: Plakal Manoj , Fischer Charles N.
Published: November 2005

We investigate reference counting in the context of a multi-threaded architecture by exploiting two observations: (1) reference-counting can be performed by a transformed program slice of the mutator that isolates heap references, and (2) hardware trends indicate that microprocessors in the near future will be able to execute multiple concurrent threads on a single chip. We generate a reference-counting collector as a transformed program slice of an application and then execute this slice in parallel with the application as a “run-behind” thread. Preliminary measurements of collector overheads are quite encouraging, showing a 25% to 53% space overhead to transfer garbage collection to a separate thread.
Efficient object sampling via weak references
Authors: Agesen Ole , Garthwaite Alex
Published: November 2005

The performance of automatic memory management may be improved if the policies used in allocating and collecting objects had knowledge of the lifetimes of objects. To date, approaches to the pretenuring of objects in older generations have relied on profile-driven feedback gathered from trace runs. This feedback has been used to specialize allocation sites in a program. These approaches suffer from a number of limitations. We propose an alternative that through efficient sampling of objects allows for on-line adaption of allocation sites to improve the efficiency of the memory system. In doing so, we make use of a facility already present in many collectors such as those found in Java™ virtual machines: weak references. By judiciously tracking a subset of allocated objects with weak references, we are able to gather the necessary statistics to make better object-placement decisions.
A generational mostly-concurrent garbage collector
Authors: Printezis Tony , Detlefs David
Published: November 2005

This paper reports our experiences with a mostly-concurrent incremental garbage collector, implemented in the context of a high performance virtual machine for the Java™ programming language. The garbage collector is based on the “mostly parallel” collection algorithm of Boehm
et al.
and can be used as the old generation of a generational memory system. It overloads efficient write-barrier code already generated to support generational garbage collection to also identify objects that were modified during concurrent marking. These objects must be rescanned to ensure that the concurrent marking phase marks all live objects. This algorithm minimises maximum garbage collection pause times, while having only a small impact on the average garbage collection pause time and overall execution time. We support our claims with experimental results, for both a synthetic benchmark and real programs.
A multiparty coordination aspect language
Authors: Corchuelo Rafael , Pérez José A. , Toro Miguel
Published: November 2005

Coordination languages were motivated by an ever-increasing need for producing highly-reusable components, which can be partially achieved by implementing them in a way that is independent of the way they interact. Isolating interaction from computation, persistence and other concerns enhances modularity, thus promoting reusability and understandability. In this paper, we concentrate on a language aimed at describing the simultaneous coordination of a number of entities, which is a problem we are usually faced with when we have to programme bank transfers, purchases with debit cards, auctions, and so on. This language relies on the novel multiparty interaction model.
An object-oriented LL(1) parser generator
Authors: Kühl Bernd , Schreiner Axel-Toblas
Published: November 2005

This paper describes
oops
, an object-oriented parser generator implemented in Java [1].
Oops
takes a grammar written in EBNF, checks that it is indeed LL(1), i.e., suitable for recursive descent parsing, and produces a parser as a set of serialized objects. A scanner must be provided and classes satisfying certain interfaces can be implemented which the parser uses to build parse trees.The paper discusses the ideas behind
oops
---which are not specific to an implementation in Java---and shows the advantages of an object-oriented approach to grammar verification and parsing.
Regular expression pattern matching for XML
Authors: Hosoya Haruo , Pierce Benjamin
Published: November 2005

We propose
regular expression pattern matching
as a core feature for programming languages for manipulating XML (and similar tree-structured data formats). We extend conventional pattern-matching facilities with regular expression operators such as repetition (*), alternation (I), etc., that can match arbitrarily long
sequences
of subtrees, allowing a compact pattern to extract data from the middle of a complex sequence. We show how to check standard notions of exhaustiveness and redundancy for these patterns.Regular expression patterns are intended to be used in languages whose type systems are also based on the
regular expression types
. To avoid excessive type annotations, we develop a type inference scheme that propagates type constraints to pattern variables from the surrounding context. The type inference algorithm translates types and patterns into regular tree automata and then works in terms of standard closure operations (union, intersection, and difference) on tree automata. The main technical challenge is dealing with the interaction of repetition and alternation patterns with the
first-match
policy, which gives rise to subtleties concerning both the termination and the precision of the analysis. We address these issues by introducing a data structure representing closure operations lazily.
Mobile values, new names, and secure communication
Authors: Abadi Martín , Fournet Cédric
Published: November 2005

We study the interaction of the "new" construct with a rich but common form of (first-order) communication. This interaction is crucial in security protocols, which are the main motivating examples for our work; it also appears in other programming-language contexts. Specifically, we introduce a simple, general extension of the pi calculus with value passing, primitive functions, and equations among terms. We develop semantics and proof techniques for this extended language and apply them in reasoning about some security protocols.
A compiler technique for improving whole-program locality
Authors: Kandemir Mahmut Taylan
Published: November 2005

Exploiting spatial and temporal locality is essential for obtaining high performance on modern computers. Writing programs that exhibit high locality of reference is difficult and error-prone. Compiler researchers have developed loop transformations that allow the conversion of programs to exploit locality. Recently, transformations that change the memory layouts of multi-dimensional arrays---called data transformations---have been proposed. Unfortunately, both data and loop transformations have some important draw-backs. In this work, we present an integrated framework that uses loop and data transformations in concert to exploit the benefits of both approaches while minimizing the impact of their disadvantages. Our approach works inter-procedurally on acyclic call graphs, uses profile data to eliminate layout conflicts, and is unique in its capability of resolving conflicting layout requirements of different references to the same array in the same nest and in different nests for regular array-based applications.The optimization technique presented in this paper has been implemented in a source-to-source translator. We evaluate its performance using standard benchmark suites and several math libraries (complete programs) with large input sizes. Experimental results show that our approach reduces the overall execution times of original codes by 17.5% on the average. This reduction comes from three important characteristics of the technique, namely, resolving layout conflicts between references to the same array in a loop nest, determining a suitable order to propagate layout modifications across loop nests, and propagating layouts between different procedures in the program --- all in a unified framework.
Slicing concurrent java programs
Authors: Chen Zhenqiang , Xu Baowen
Published: November 2005

Program slicing is an important approach to testing, understanding and maintaining programs. The paper presents a slicing algorithm for concurrent Java programs. Because the execution process of concurrent programs is unpredictable, there are many problems to be solved when slicing. To slice concurrent Java programs, we present concurrent control flow graphs and concurrent program dependence graphs to representconcurrent Java programs. Based on these models, we design an efficient static slicing algorithm for concurrent Java programs. The algorithm may get more precise slices than previous approaches we know.
Some issues on the translator of smalltalk to C++
Authors: Shaofeng Wang , Fuquing Yang , Jiaguang Sun
Published: November 2005

This paper mainly discusses s2cpp that is a translator of Smalltalk to C++. Generally, the translators of programming languages can be classified into two types. The first type is the translation between two specific programming languages. The second type is the translation between any two programming languages. Although s2cpp belongs to the first type, the use of intermediate pseudocodes allows it to be easily modified to be a translator of Smalltalk to other programming languages. We describe the architecture of s2cpp as well as some issues in designing and implementing the translator. Some results concerning the translation were given in the end.
Java without the coffee breaks
Authors: Bacon David F. , Attanasio Clement R. , Lee Han B. , Rajan V. T. , Smith Stephen
Published: November 2005

The deployment of Java as a concurrent programming language has created a critical need for high-performance, concurrent, and incremental multiprocessor garbage collection. We present the
Recycler
, a fully concurrent pure reference counting garbage collector that we have implemented in the Jalapeño Java virtual machine running on shared memory multiprocessors.

While a variety of multiprocessor collectors have been proposed and some have been implemented, experimental data is limited and there is little quantitative basis for comparison between different algorithms. We present measurements of the Recycler and compare it against a non-concurrent but parallel load-balancing mark-and-sweep collector (that we also implemented in Jalapeño), and evaluate the classical tradeoff between response time and throughput.

When processor or memory resources are limited, the Recycler runs at about 90% of the speed of the mark-and-sweep collector. However, with an extra processor to run collection and with a moderate amount of memory headroom, the Recycler is able to operate without ever blocking the mutators and achieves a maximum measured mutator delay of only 2.6 milliseconds for our benchmarks. End-to-end execution time is usually within 5%.
Bytecode compression via profiled grammar rewriting
Authors: Evans William S. , Fraser Christopher W.
Published: November 2005

This paper describes the design and implementation of a method for producing compact, bytecoded instruction sets and interpreters for them. It accepts a grammar for programs written using a simple bytecoded stack-based instruction set, as well as a training set of sample programs. The system transforms the grammar, creating an expanded grammar that represents the same language as the original grammar, but permits a shorter derivation of the sample programs and others like them. A program's derivation under the expanded grammar forms the compressed bytecode representation of the program. The interpreter for this bytecode is automatically generated from the original bytecode interpreter and the expanded grammar. Programs expressed using compressed bytecode can be substantially smaller than their original bytecode representation and even their machine code representation. For example, compression cuts the bytecode for lcc from 199KB to 58KB but increases the size of the interpreter by just over 11KB.
A framework for reducing the cost of instrumented code
Authors: Arnold Matthew , Ryder Barbara G.
Published: November 2005

Instrumenting code to collect profiling information can cause substantial execution overhead. This overhead makes instrumentation difficult to perform at runtime, often preventing many known
offline
feedback-directed optimizations from being used in online systems. This paper presents a general framework for performing
instrumentation sampling
to reduce the overhead of previously expensive instrumentation. The framework is simple and effective, using code-duplication and
counter-based sampling
to allow switching between instrumented and non-instrumented code.

Our framework does not rely on any hardware or operating system support, yet provides a high frequency sample rate that is tunable, allowing the tradeoff between overhead and accuracy to be adjusted easily at runtime. Experimental results are presented to validate that our technique can collect accurate profiles (93-98% overlap with a perfect profile) with low overhead (averaging 6% total overhead with a naive implementation). A Jalape~ no-specific optimization is also presented that reduces overhead further, resulting in an average total overhead of 3%.
Automatic predicate abstraction of C programs
Authors: Ball Thomas , Majumdar Rupak , Millstein Todd , Rajamani Sriram K.
Published: November 2005

Model checking has been widely successful in validating and debugging designs in the hardware and protocol domains. However, state-space explosion limits the applicability of model checking tools, so model checkers typically operate on abstractions of systems.

Recently, there has been significant interest in applying model checking to software. For infinite-state systems like software, abstraction is even more critical. Techniques for abstracting software are a prerequisite to making software model checking a reality.

We present the first algorithm to automatically construct a
predicate abstraction
of programs written in an industrial programming language such as C, and its implementation in a tool — C2BP. The C2BP tool is part of the SLAM toolkit, which uses a combination of predicate abstraction, model checking, symbolic reasoning, and iterative refinement to statically check temporal safety properties of programs.

Predicate abstraction of software has many applications, including detecting program errors, synthesizing program invariants, and improving the precision of program analyses through predicate sensitivity. We discuss our experience applying the C2BP predicate abstraction tool to a variety of problems, ranging from checking that list-manipulating code preserves heap invariants to finding errors in Windows NT device drivers.
Optimal spilling for CISC machines with few registers
Authors: Appel Andrew W. , George Lal
Published: November 2005

Many graph-coloring register-allocation algorithms don't work well for machines with few registers. Heuristics for live-range splitting are complex or suboptimal; heuristics for register assignment rarely factor the presence of fancy addressing modes; these problems are more severe the fewer registers there are to work with. We show how to optimally split live ranges and optimally use addressing modes, where the optimality condition measures dynamically weighted loads and stores but not register-register moves. Our algorithm uses integer linear programming but is much more efficient than previous ILP-based approaches to register allocation. We then show a variant of Park and Moon's optimistic coalescing algorithm that does a very good (though not provably optimal) job of removing the register-register moves. The result is Pentium code that is 9.5% faster than code generated by SSA-based splitting with iterated register coalescing.
Dynamic variables
Authors: Hanson David R. , Proebsting Todd A.
Published: November 2005

Most programming languages use static scope rules for associating uses of identifiers with their declarations. Static scope helps catch errors at compile time, and it can be implemented efficiently. Some popular languages—Perl, Tel, TeX, and Postscript—offer dynamic scope, because dynamic scope works well for variables that “customize” the execution environment, for example. Programmers must simulate dynamic scope to implement this kind of usage in statically scoped languages. This paper describes the design and implementation of imperative language constructs for introducing and referencing dynamically scoped variables—dynamic variables for short. The design is a minimalist one, because dynamic variables are best used sparingly, much like exceptions. The facility does, however, cater to the typical uses for dynamic scope, and it provides a cleaner mechanism for so-called thread-local variables. A particularly simple implementation suffices for languages without exception handling. For languages with exception handling, a more efficient implementation builds on existing compiler infrastructure. Exception handling can be viewed as a control construct with dynamic scope. Likewise, dynamic variables are a data construct with dynamic scope.
Asynchronous exceptions in Haskell
Authors: Marlow Simon , Jones Simon Peyton , Moran Andrew , Reppy John
Published: November 2005

Asynchronous exceptions, such as timeouts are important for robust, modular programs, but are extremely difficult to program with — so much so that most programming languages either heavily restrict them or ban them altogether. We extend our earlier work, in which we added synchronous exceptions to Haskell, to support asynchronous exceptions too. Our design introduces scoped combinators for blocking and unblocking asynchronous interrupts, along with a somewhat surprising semantics for operations that can suspend. Uniquely, we also give a formal semantics for our system.
Cool
Authors: Aiken Alexander
Published: November 2005

The compiler course is a fixture of undergraduate computer science education. Most CS programs offer a course on compilers that includes a substantial project where students write a compiler for a small programming language. The project often serves two distinct purposes: it teaches something about language design and compiler implementation, and it gives students the experience of building a substantial software system. A compiler project is the most complex software engineering task many students complete in an undergraduate program.
Process to process communication in prolog
Authors: Panti M. , Cucchiarelli A. , Mattiucci M. , Valenti S.
Published: November 2005

Purpose of this paper is to present an extension to LPA-MacProlog that allows the programmer to build communication-based applications. A simple set of primitives to open and close communication, and to send and to receive messages to other processes running in Prolog on different machines connected over an AppleTalk network, have been provided. A great design effort has been made in order to grant full independence of the communication layer from the domain: therefore, the proposed paradigm may be easily ported under different interpreters providing a powerful and inexpensive tool to implement process to process communication.
Utilizing students as resources
Authors: Brooks Kent
Published: November 2005

How often in the course of teaching does one encounter a situation where there is no budget and little time to prepare? Teaching a new course often requires a significant amount of preparation. When the course is technology related, the resources required to do the job well are also significant. What happens when you are asked to teach a technology-related course on short notice with few resources? It pays in this situation and most classroom situations to take inventory of the human resources available within the classroom to see what they can offer to make the course a worthwhile experience for everyone involved.
Textbooks for teaching C++
Authors: Janik Carol
Published: November 2005

Until recently, there were very few materials available for teaching C++ and object-oriented programming. I taught a new course in that subject this spring, and we are considering changing from Pascal to C++ in our first year computer science sequence; thus, I have been collecting books from publisher's reps and the ACM conference. Lab manuals are scarce, but some texts come with disks of the programs in the text that could be used in a lab situation. A short review of texts that I've recently obtained follows.