bluuebunny/crossref_metadata_2025 huggingface dataset:
Enriching the lambda calculus with contexts
Authors: Lee Shinn-Der , Friedman Daniel P.
Published: November 2005

A context in the λ-calculus is a term with some holes. Hole filling differs from β-substitution in that name capture is intended. This seemingly simple feature transcends static scope and lies at the heart of modular and object-oriented programming. Still, the name capture feature of hole filling is at odds with hygienic β-substitution. In this paper we conservatively extend the λ-calculus to incorporate the notion of contexts without jeopardizing the β-rule. We perceive contexts as source code and λ-terms as target code. Context filling is encoded as compilation operations and the enriched calculus is a theory of separate compilation and incremental program construction. Linking of separately-developed programs is done by coherent renaming of free variables.We apply our context-enriching schema to the λ-calculus extended with definitions and devise a calculus of first-class modules. We show that module linking can be modeled solely by the renaming of import and export variables. We add relinkable variable references to model virtual method references essential to object systems.The inclusion of contexts introduces parameters whose linking is based on names (symbols, identifiers, or keywords). We simulate in the context-enriched calculus other extensions of the λ-calculus with name-based programming notions such as Dami's λ-calculus with names, Aït-Kaci and Garrigue's label-selective λ-calculus, Lamping's transparent data parameters, and our quasi-static procedures.
Sharing code through first-class environments
Authors: Queinnec Christian , de Roure David
Published: November 2005

Nowadays the Net is one of the most obvious driving forces. Yet, to consider it as one global store through which values and code may be shared is still immature. This paper suggests first-class environments as a means to achieve that goal in a multi-user Scheme framework. We propose two new special forms with a simple semantics. Our model allows precise control over environments (including extensible environments) and does not require (but does not prevent) reflective operations.
Mixin modules
Authors: Duggan Dominic , Sourelis Constantinos
Published: November 2005

Mixin modules are proposed as a new construct for module languages, allowing recursive definitions to span module boundaries. Mixin modules are proposed specifically for the Standard ML language. Several applications are described, including the resolution of cycles in module import dependency graphs, as well as functionality related to Haskell type classes and CLOS generic functions, though without any complications to the core language semantics. Mixin modules require no changes to the core ML type system, and only a very minor change to its run-time semantics. A type system and reduction semantics are provided, and the former is verified to be sound relative to the latter.
Creating host compliance in a portable framework
Authors: Yelland Phillip M.
Published: November 2005

This report describes an experiment carried out at ParcPlace-Digitalk which sought to increase the look-and-feel compliance of portable applications built using the company's Smalltalk-based VisualWorks product. We outline the structure of the current VisualWorks user interface framework, and the precise requirements which the experimental system sought to fulfill. We go on to show how we were able to reuse design patterns from the literature in a
generative
fashion, to direct the evolution of the new framework. This contrasts with most pattern-related work to date, which has concentrated on discerning design patterns in existing systems. Finally, we draw generalizations from our experience concerning the evolution of software architecture using patterns.
A flexible operation execution model for shared distributed objects
Authors: Ben Hassen Saniya , Athanasiu Irina , Bal Henri E.
Published: November 2005

Many parallel and distributed programming models are based on some form of shared objects, which may be represented in various ways (e.g., single-copy, replicated, and partitioned objects). Also, many different operationexecution strategieshave been designed for each representation. In programming systems that use multiple representations integrated in a single object model, one way to provide multiple execution strategies is to implement each strategy independently from the others. However, this leads to rigid systems and provides little opportunity for code reuse. Instead, we propose a flexible operation execution model that allows the implementation of many different strategies, which can even be changed at runtime. We present the model and a distributed implementation of it. Also, we describe how various execution strategies can be expressed using the model, and we look at applications that benefit from its flexibility.
Code reuse in an optimizing compiler
Authors: Adl-Tabatabai Ali-Reza , Gross Thomas , Lueh Guei-Yuan
Published: November 2005

This paper describes how the cmcc compiler reuses code---both internally (reuse between different modules) and externally (reuse between versions for different target machines). The key to reuse are the application frameworks developed for global data-flow analysis, code generation, instruction scheduling, and register allocation.The code produced by cmcc is as good as the code produced by the native compilers for the MIPS and SPARC, although significantly less resources have been spent on cmcc (overall, about 6 man years by 2.5 persons). cmcc is implemented in C++, which allowed for a compact expression of the frameworks as class hierarchies. The results support the claim that suitable frameworks facilitate reuse and thereby significantly improve developer effectiveness.
Slicing class hierarchies in C++
Authors: Tip Frank , Choi Jong-Deok , Field John , Ramalingam G.
Published: November 2005

This paper describes an algorithm for
slicing
class hierarchies in C++ programs. Given a C++ class hierarchy (a collection of C++ classes and inheritance relations among them) and a program
P
that uses the hierarchy, the algorithm eliminates from the hierarchy those data members, member functions, classes, and inheritance relations that are unnecessary for ensuring that the semantics of
P
is maintained.Class slicing is especially useful when the program
P
is generated from a larger program
P'
by a
statement slicing
algorithm. Such an algorithm eliminates statements that are irrelevant to a set of slicing
criteria
---program points of particular interest. There has been considerable previous work on statement slicing, and it will not be the concern of this paper. However, the combination of statement slicing and class slicing for C++ has two principal applications: First, class slicing can enhance statement slicing's utility in program debugging and understanding applications, by eliminating both executable
and
declarative program components irrelevant to the slicing criteria. Second, the combination of the two slicing algorithms can be used to decrease the space requirements of programs that do not use all the components of a class hierarchy. Such a situation is particularly common in programs that use class libraries.
Environmental acquisition
Authors: Gil Joseph , Lorenz David H.
Published: November 2005

The class of an object is not necessarily the only determiner of its runtime behaviour. Often it is necessary to have an object behave differently depending upon the other objects to which it is connected. However, as it currently stands, object-oriented programming provides no support for this concept, and little recognition of its role in common, practical programming situations. This paper investigates a new programming paradigm,
environmental acquisition
in the context of
object aggregation
, in which objects acquire behaviour from their current containers at runtime. The key idea is that the behaviour of a component may depend upon its enclosing composite(s). In particular, we propose a form of feature sharing in which an object "
inherits
" features from the classes of objects in its environment. By examining the declaration of classes, it is possible to determine which kinds of classes
may
contain a component, and which components
must
be contained in a given kind of composite. These relationships are the basis for language constructs that supports acquisition. We develop the theory of acquisition that includes topics such as the kinds of links along which acquisition may occur, and the behaviour of routine (methods) and attribute features under acquisition. The proposed model for acquisition as a hierarchical abstraction mechanism is a strongly typed model that allows static type checking of programs exploiting this mechanism. We compare it to several other mechanisms including inheritance and delegation, and show that it is significantly different than these.
Soft issues and hard problems in software development (panel)
Authors: Chisholm Paul S. R. , Constantine Larry , Cunningham Ward , Hohmann Luke , Kerth Norman
Published: November 2005

The key to making object technology work isn't technology. So what is it? This panel will cover a lot of the "soft" issues about dealing with people and teams. It's partly about managing software development, and mostly about doing it.
Reuse contracts
Authors: Steyaert Patrick , Lucas Carine , Mens Kim , D'Hondt Theo
Published: November 2005

A critical concern in the reuse of software is the propagation of changes made to reusable artifacts. Without techniques to manage these changes, multiple versions of these artifacts will propagate through different systems and reusers will not be able to benefit from improvements to the original artifact. We propose to codify the management of change in a software system by means of reuse contracts that record the protocol between managers and users of a reusable asset. Just as real world contracts can be extended, amended and customised, reuse contracts are subject to parallel changes encoded by formal reuse operators: extension, refinement and concretisation. Reuse contracts and their operators serve as structured documentation and facilitate the propagation of changes to reusable assets by indicating how much work is needed to update previously built applications, where and how to test and how to adjust these applications.
Simple and effective analysis of statically-typed object-oriented programs
Authors: Diwan Amer , Moss J. Eliot B. , McKinley Kathryn S.
Published: November 2005

To use modern hardware effectively, compilers need extensive control-flow information. Unfortunately, the frequent method invocations in object-oriented languages obscure control flow. In this paper, we describe and evaluate a range of analysis techniques to convert method invocations into direct calls for statically-typed object-oriented languages and thus improve control-flow information in object-oriented languages. We present simple algorithms for
type hierarchy analysis, aggregate analysis, and interprocedural and intraprocedural type propagation
. These algorithms are also fast,
O
(|procedures| * ∑
p
procedure
n

p

*
v

p

) worst case time (linear in practice) for our slowest analysis, where
n

p

is the size of procedure
p
and
v

p

is the number of variables in procedure
p
, and are thus practical for use in a compiler. When they fail, we introduce
cause analysis
to reveal the source of imprecision and suggest where more powerful algorithms may be warranted. We show that our simple analyses perform almost as well as an oracle that resolves all method invocations that invoke only a single procedure.
Fast static analysis of C++ virtual function calls
Authors: Bacon David F. , Sweeney Peter F.
Published: November 2005

Virtual functions make code easier for programmers to reuse but also make it harder for compilers to analyze. We investigate the ability of three static analysis algorithms to improve C++ programs by resolving virtual function calls, thereby reducing compiled code size and reducing program complexity so as to improve both human and automated program understanding and analysis. In measurements of seven programs of significant size (5000 to 20000 lines of code each) we found that on average the most precise of the three algorithms resolved 71% of the virtual function calls and reduced compiled code size by 25%. This algorithm is very fast: it analyzes 3300 source lines per second on an 80 MHz PowerPC 601. Because of its accuracy and speed, this algorithm is an excellent candidate for inclusion in production C++ compilers.
Architecture-oriented visualization
Authors: Sefika Mohlalefi , Sane Aamod , Campbell Roy H.
Published: November 2005

Tracking the changing dynamics of object-oriented frameworks[5], design patterns[7], architectural styles[8], and subsystems during the development and reuse cycle can aid producing complex systems. Unfortunately, current object-oriented programming tools are relatively oblivious to the rich architectural abstractions in a system.This paper shows that architecture-oriented visualization, the graphical presentation of system statics and dynamics in terms of its architectural abstractions, is highly beneficial in designing complex systems. In addition, the paper presents architecture-aware instrumentation, a new technique for building efficient on-line instrumentation to support architectural queries. We demonstrate the effectiveness and performance of the scheme with case studies in the design of the
Choices
object-oriented operating system.
Components on the Internet (panel)
Authors: Bonar Jeffrey , Lehrer Nancy , Looney Kelly , Schnier Randy , Russel James , Selker Ted , Nickolas Stewart
Published: November 2005

The explosive emergence of the Internet forces us to rethink the traditional roles for client, server, and objects. Component technology has emerged as the way objects and frameworks are packaged for flexible object integration. In particular, components allow users who are not programmers to do their own integration. Up until now, components have mainly focused on object integration on end-users desktops and on a client: compound documents, application assembly, etc.Existing component models like OpenDoc and Microsoft's OLE/OCX/COM provide function for compound documents, persistence, scripting, inking, and code management (registration). A series of Internet scenarios are emerging that demand new kinds of components. These scenarios are thin clients (Internet terminals), virtual reality/rich multimedia clients, collaboration, and business data access. Each panelist will explore one of these scenarios for it's requirements on an Internet component model.
Starting a community college ACM student chapter
Authors: Applin Anne G.
Published: November 2005

I was a Student Chapter Chair for two years during my undergraduate years at Southeastern Louisiana University as well as being Chair of Upsilon Pi Epsilon (the Computer Science Honor Society). When I began to teach at Pearl River Community College (PRCC), I discovered that there had been a "computer club" at one time. Two questions came to my mind. Why wasn't it an ACM student chapter? And why had it fizzled out?
Musical equational programs
Authors: van den Broek P. M. , van den Berg K. G.
Published: November 2005

In this paper we solve musical equational programs by means of higher order functions. The initial solution is written in a functional programming language (Miranda
1
). It is shown how a solution in an imperative language (Pascal) can be obtained by elimination of the higher order functions.
A knowledge-based problem-specific program generator
Authors: Hrycej T
Published: November 2005

A commercially relevant paradigm for a knowledge-based problem-specific program generator is described. It is applicable to repeatedly implemented software, particularly in the intermediate area between the exclusive and standard software. Not the first implementation, but the repeated ones are supported using the "problem-specific programming knowledge" collected during the past implementations. The technical details, as knowledge representation and functional component, are explained and illustrated on an example. Finally, conditions for an efficient application of the program generator are defined. The system can be developed at a relatively low expense of several months.
Limitations of Graham-Glanville style code generation
Authors: Spector D , Turner P K
Published: November 2005

In recent years, the Graham-Glanville approach to code generation has become an increasingly important influence on new compiler writing projects. Initial enthusiasm prompted by the early research results has now fueled projects with more practical goals and requirements. This paper reports on the early results of a long-term project that is applying the Graham-Glanville method to the creation of an industrial-quality multi-language, multi-target compiler system. Much of the resulting code generation system deals with matters that are not fully handled by the Graham-Glanville method. We present a derailed list of the limitations encountered and, for each, the extension or modification that was invented to deal with it.Our conclusion is that the Graham-Glanville method does not always fulfill its early promise of generating locally-optimal code. Production-quality retargetable compiler generation still requires clever organization and many sophisticated algorithms to achieve this goal in the presence of register allocation and cost analysis.
Combinatory code and a parallel packet-based computational model
Authors: Cheese A
Published: November 2005

Up until now the widespread use of functional languages has been hindered by the lack of any sort of efficient implementation. The main reason for this has been the need to support an environment, a mapping of variables in scope to their current values. By using combinatory logic it is possible to translate a functional program into a form in which all bound variables have been removed. The transformed program will be string of constants which selectively ship to each expression that part of the environment it references. As a result of this the hardware needed to produce a physical realization of the model should be very much simpler than that of normal Von Neumann computing engines. In order to exploit the implicit parallelism present in a functional program a computational model based upon a parallel packet based graph reduction scheme is proposed which allows code to be treated in exactly the same manner as data. In particular the code graph can be regarded as a lazily constructed data structure.
Puzzles, PROLOG and logic
Authors: Jerardi T W
Published: November 2005

Puzzles have been and continue to be very effective agents for the presentation of logic. Recently, PROLOG has been suggested as the tool of choice for approaching "virtually all" logic problems. One of Smullyan's puzzles is used to demonstrate this thesis. We question this rush to PROLOG and its associated procedural interpretation of logic. We give a simple puzzle (definitely not of the Lewis Carroll or Smullyan caliber) and our PROLOG solutions. Our problems in applying PROLOG to this puzzle in turn lead us to try to discover the logic roots of PROLOG.
Iteration and abstract data types
Authors: Eckart J D
Published: November 2005

Numerous languages have been developed which support the creation of abstract data types. Introductions to such languages typically provide the standard stack and complex number examples to demonstrate their respective expressive power. While such examples fit neatly into the framework of these languages, only a few have attempted to deal with the problems of iterating through an abstraction, such as the elements of a list. Two approaches to this problem are examined: action importation and data exportation. It is shown that data exportation is the more flexible of the two and a language construct supporting it is presented.
The case for a single-chip multiprocessor
Authors: Olukotun Kunle , Nayfeh Basem A. , Hammond Lance , Wilson Ken , Chang Kunyung
Published: November 2005

Advances in IC processing allow for more microprocessor design options. The increasing gate density and cost of wires in advanced integrated circuit technologies require that we look for new ways to use their capabilities effectively. This paper shows that in advanced technologies it is possible to implement a single-chip multiprocessor in the same area as a wide issue superscalar processor. We find that for applications with little parallelism the performance of the two microarchitectures is comparable. For applications with large amounts of parallelism at both the fine and coarse grained levels, the multiprocessor microarchitecture outperforms the superscalar architecture by a significant margin. Single-chip multiprocessor architectures have the advantage in that they offer localized implementation of a high-clock rate processor for inherently sequential applications and low latency interprocessor communication for parallel applications.
An evaluation of memory consistency models for shared-memory systems with ILP processors
Authors: Pai Vijay S. , Ranganathan Parthasarathy , Adve Sarita V. , Harton Tracy
Published: November 2005

Relaxed consistency models have been shown to significantly outperform sequential consistency for single-issue, statically scheduled processors with blocking reads. However, current microprocessors aggressively exploit instruction-level parallelism (ILP) using methods such as multiple issue, dynamic scheduling, and non-blocking reads. Researchers have conjectured that two techniques, hardware-controlled non-binding prefetching and speculative loads, have the potential to equalize the hardware performance of memory consistency models on such processors.This paper performs the first detailed quantitative comparison of several implementations of sequential consistency and release consistency optimized for aggressive ILP processors. Our results indicate that hardware prefetching and speculative loads dramatically improve the performance of sequential consistency. However, the gap between sequential consistency and release consistency depends on the cache write policy and the complexity of the cache-coherence protocol implementation. In most cases, release consistency significantly outperforms sequential consistency, but for two applications, the use of a write-back primary cache and a more complex cache-coherence protocol nearly equalizes the performance of the two models.We also observe that the existing techniques, which require on-chip hardware modifications, enhance the performance of release consistency only to a small extent. We propose two new software techniques ---
fuzzy acquires
and
selective acquires
--- to achieve more overlap than allowed by the previous implementations of release consistency. To enhance methods for overlapping acquires, we also propose a technique to eliminate control dependences caused by an acquire loop, using a small amount of off-chip hardware called the
synchronization buffer.
A quantitative analysis of loop nest locality
Authors: McKinley Kathryn S. , Temam Olivier
Published: November 2005

This paper analyzes and quantifies the locality characteristics of numerical loop nests in order to suggest future directions for architecture and software cache optimizations. Since most programs spend the majority of their time in nests, the vast majority of cache optimization techniques target loop nests. In contrast, the locality characteristics that drive these optimizations are usually collected across the entire application rather than the nest level. Indeed, researchers have studied numerical codes for so long that a number of commonly held assertions have emerged on their locality characteristics. In light of these assertions, we use the Perfect Benchmarks to take a new look at measuring locality on numerical codes based on references, loop nests, and program locality properties. Our results show that several popular assertions are at best overstatements. For example, we find that temporal and spatial reuse have balanced roles within a loop nest and most reuse across nests and the entire program is temporal. These results are consistent with high hit rates, but go against the commonly held assumption that spatial reuse dominates. Another result contrary to popular assumption is that misses within a nest are overwhelmingly conflict misses rather than capacity misses. Capacity misses are a significant source of misses for the entire program, but mostly correspond to potential reuse between different loop nests. Our locality measurements reveal important differences between loop nests and programs; refute some popular assertions; and provide new insights for the compiler writer and the architect.
Adapting to network and client variability via on-demand dynamic distillation
Authors: Fox Armando , Gribble Steven D. , Brewer Eric A. , Amir Elan
Published: November 2005

The explosive growth of the Internet and the proliferation of smart cellular phones and handheld wireless devices is widening an already large gap between Internet clients. Clients vary in their hardware resources, software sophistication, and quality of connectivity, yet server support for client variation ranges from relatively poor to none at all. In this paper we introduce some design principles that we believe are fundamental to providing "meaningful" Internet access for the entire range of clients. In particular, we show how to perform on-demand datatype-specific lossy compression on semantically typed data, tailoring content to the specific constraints of the client. We instantiate our design principles in a proxy architecture that further exploits typed data to enable application-level management of scarce network resources. Our proxy architecture generalizes previous work addressing all three aspects of client variation by applying well-understood techniques in a novel way, resulting in quantitatively better end-to-end performance, higher quality display output, and new capabilities for low-end clients.
Shasta
Authors: Scales Daniel J. , Gharachorloo Kourosh , Thekkath Chandramohan A.
Published: November 2005

This paper describes Shasta, a system that supports a shared address space in software on clusters of computers with physically distributed memory. A unique aspect of Shasta compared to most other software distributed shared memory systems is that shared data can be kept coherent at a fine granularity. In addition, the system allows the coherence granularity to vary across different shared data structures in a single application. Shasta implements the shared address space by transparently rewriting the application executable to intercept loads and stores. For each shared load or store, the inserted code checks to see if the data is available locally and communicates with other processors if necessary. The system uses numerous techniques to reduce the run-time overhead of these checks. Since Shasta is implemented entirely in software, it also provides tremendous flexibility in supporting different types of cache coherence protocols. We have implemented an efficient cache coherence protocol that incorporates a number of optimizations, including support for multiple communication granularities and use of relaxed memory models. This system is fully functional and runs on a cluster of Alpha workstations.The primary focus of this paper is to describe the techniques used in Shasta to reduce the checking overhead for supporting fine granularity sharing in software. These techniques include careful layout of the shared address space, scheduling the checking code for efficient execution on modern processors, using a simple method that checks loads using only the value loaded, reducing the extra cache misses caused by the checking code, and combining the checks for multiple loads and stores. To characterize the effect of these techniques, we present detailed performance results for the SPLASH-2 applications running on an Alpha processor. Without our optimizations, the checking overheads are excessively high, exceeding 100% for several applications. However, our techniques are effective in reducing these overheads to a range of 5% to 35% for almost all of the applications. We also describe our coherence protocol and present some preliminary results on the parallel performance of several applications running on our workstation cluster. Our experience so far indicates that once the cost of checking memory accesses is reduced using our techniques, the Shasta approach is an attractive software solution for supporting a shared address space with fine-grain access to data.
SoftFLASH
Authors: Erlichson Andrew , Nuckolls Neal , Chesson Greg , Hennessy John
Published: November 2005

One potentially attractive way to build large-scale shared-memory machines is to use small-scale to medium-scale shared-memory machines as clusters that are interconnected with an off-the-shelf network. To create a shared-memory programming environment across the clusters, it is possible to use a virtual shared-memory software layer. Because of the low latency and high bandwidth of the interconnect available within each cluster, there are clear advantages in making the clusters as large as possible. The critical question then becomes whether the latency and bandwidth of the top-level network and the software system are sufficient to support the communication demands generated by the clusters.To explore these questions, we have built an aggressive kernel implementation of a virtual shared-memory system using SGI multiprocessors and 100Mbyte/sec HIPPI interconnects. The system obtains speedups on 32 processors (four nodes, eight processors per node plus additional reserved protocol processors) that range from 6.9 on the communication-intensive FFT program to 21.6 on Ocean (both from the SPLASH 2 suite). In general, clustering is effective in reducing internode miss rates, but as the cluster size increases, increases in the remote latency, mostly due to increased TLB synchronization cost, offset the advantages. For communication-intensive applications, such as FFT, the overhead of sending out network requests, the limited network bandwidth, and the long network latency prevent the achievement of good performance. Overall, this approach still appears promising, but our results indicate that large low latency networks may be needed to make cluster-based virtual shared-memory machines broadly useful as large-scale shared-memory multiprocessors.
Reducing network latency using subpages in a global memory environment
Authors: Jamrozik Hervé A. , Feeley Michael J. , Voelker Geoffrey M. , Evans James , Karlin Anna R. , Levy Henry M. , Vernon Mary K.
Published: November 2005

New high-speed networks greatly encourage the use of network memory as a cache for virtual memory and file pages, thereby reducing the need for disk access. Because pages are the fundamental transfer and access units in remote memory systems, page size is a key performance factor. Recently, page sizes of modern processors have been increasing in order to provide more TLB coverage and amortize disk access costs. Unfortunately, for high-speed networks,
small
transfers are needed to provide low latency. This trend in page size is thus at odds with the use of network memory on high-speed networks.This paper studies the use of
subpages
as a means of reducing transfer size and latency in a remote-memory environment. Using trace-driven simulation, we show how and why subpages reduce latency and improve performance of programs using network memory. Our results show that memory-intensive applications execute up to 1.8 times faster when executing with 1K-byte subpages, when compared to the same applications using full 8K-byte pages in the global memory system. Those same applications using 1K-byte subpages execute up to 4 times faster than they would using the disk for backing store. Using a prototype implementation on the DEC Alpha and AN2 network, we demonstrate how subpages can reduce remote-memory fault time; e.g., our prototype is able to satisfy a fault on a 1K subpage stored in remote memory in 0.5 milliseconds, one third the time of a full page.
Operating system support for improving data locality on CC-NUMA compute servers
Authors: Verghese Ben , Devine Scott , Gupta Anoop , Rosenblum Mendel
Published: November 2005

The dominant architecture for the next generation of shared-memory multiprocessors is CC-NUMA (cache-coherent non-uniform memory architecture). These machines are attractive as compute servers because they provide transparent access to local and remote memory. However, the access latency to remote memory is 3 to 5 times the latency to local memory. CC-NOW machines provide the benefits of cache coherence to networks of workstations, at the cost of even higher remote access latency. Given the large remote access latencies of these architectures, data locality is potentially the most important performance issue. Using realistic workloads, we study the performance improvements provided by OS supported dynamic page migration and replication. Analyzing our kernel-based implementation, we provide a detailed breakdown of the costs. We show that sampling of cache misses can be used to reduce cost without compromising performance, and that TLB misses may not be a consistent approximation for cache misses. Finally, our experiments show that dynamic page migration and replication can substantially increase application performance, as much as 30%, and reduce contention for resources in the NUMA memory system.
A Modula-2 implementation of CSP
Authors: Collado M , Morales R , Moreno J J
Published: November 2005

Recently, a series of process communication schemes based on message exchanges have been developed. Hoare's CSP is perhaps the most interesting one and is the base for concurrent features of modern languages (e.g. ADA, Occam, etc.).Several concurrency mechanisms have already been implemented in Modula-2 (signals, COBEGIN..COEND structure, message exchanges, etc.) but they have not completely fulfilled the Hoare's CSP scheme.In this paper a general implementation of CSP in Modula-2 is presented. Low level and modularity facilities of this language have been used to develop a kernel thus allowing the use of comunication primitives and nondeterministic selection.The original CSP scheme has been slightly modified by using port names instead of process names to specify communication.
Implications of automated restructuring of COBOL
Authors: Miller J C , Strauss B M
Published: November 2005

This paper examines whether mechanical transformations of unstructured program code to a structured equivalent can provide any improvement in understandability. We specifically examine, although are not limited to, a COBOL environment. The paper reviews the basic postulates of structured programming as applied to COBOL, and discusses the transformations caused by an automated restructuring tool.Jerry Sitner has asked the basic question of whether mechanical code transformations (performed by either an automated tool or a human following a set of rigorous rules) can improve the readability of COBOL programs. Assuming equivalence (which is
not
the case), he asks which of the two expressions is more understandable?
IF A = B GO TO C
. "Unstructured"
IF A = B PERFORM C
. "Structured"In COBOL, a GO TO is a non-returning transfer of control and a PERFORM is a returning one. Each computer language has at least one and usually both of these constructs. BASIC has GOTO and GOSUB, PL/I (and PASCAL) has the procedure/function and the GOTO, FORTRAN has the DO and GOTO, etc. The question raises two basic issues, 1) is the structured expression equivalent to the unstructured in meaning and 2) how can understandability of program code be improved. To answer these, we need to examine what structured programming is and why it is better, then address the questions of mechanical transformations of code and of names within programs and systems.
A reduced multipipeline machine description that preserves scheduling constraints
Authors: Eichenberger Alexandre E. , Davidson Edward S.
Published: November 2005

High performance compilers increasingly rely on accurate modeling of the machine resources to efficiently exploit the instruction level parallelism of an application. In this paper, we propose a reduced machine description that results in faster detection of resource contentions while preserving the scheduling constraints present in the original machine description. The proposed approach reduces a machine description in an automated, error-free, and efficient fashion, Moreover, it fully supports schedulers that backtrack and process operations in arbitrary order. Reduced descriptions for the DEC Alpha 21064, MIPS R3000/R3010, and Cydra 5 result in 4 to 7 times faster detection of resource contentions and require 22 to 90% of the memory storage used by the original machine descriptions. Precise measurement for the Cydra 5 indicates that reducing the machine description results in a 2.9 times faster contention query module.
Source-level debugging of scalar optimized code
Authors: Adl-Tabatabai Ali-Reza , Gross Thomas
Published: November 2005

Although compiler optimizations play a crucial role in the performance of modern computer systems, debugger technology has lagged behind in its support of optimization. Yet debugging the unoptimized translation is often impossible or futile, so handling of code optimizations in the debugger is necessary. But compiler optimizations make it difficult to provide source-level debugger functionality: Global optimizations can cause the runtime value of a variable to be inconsistent with the source-level value expected at a breakpoint; such variables are called
endangered
variables. A debugger must detect and warn the user of endangered variables otherwise the user may draw incorrect conclusions about the program. This paper presents a new algorithm for detecting variables that are endangered due to global scalar optimization. Our approach provides more precise classifications of variables and is still simpler than past approaches. We have implemented and evaluated our techniques in the context of the cmcc optimizing C compiler. We describe the compiler extensions necessary to perform the required bookkeeping of compiler optimization. We present measurements of the effect of optimizations on a debugger's ability to present the expected values of variables to the user.
Representing control in the presence of one-shot continuations
Authors: Bruggeman Carl , Waddell Oscar , Dybvig R. Kent
Published: November 2005

Traditional first-class continuation mechanisms allow a captured continuation to be invoked multiple times. Many continuations, however, are invoked only once. This paper introduces
one-shot
continuations, shows how they interact with traditional multi-shot continuations, and describes a stack-based implementation of control that handles both one-shot and multi-shot continuations. The implementation eliminates the copying overhead for one-shot continuations that is inherent in multi-shot continuations.
Practical program analysis using general purpose logic programming systems—a case study
Authors: Dawson Steven , Ramakrishnan C. R. , Warren David S.
Published: November 2005

Many analysis problems can be cast in the form of evaluating minimal models of a logic program. Although such formulations are appealing due to their simplicity and declarativeness, they have not been widely used in practice because, either existing logic programming systems do not guarantee completeness, or those that do have been viewed as too inefficient for integration into a compiler. The objective of this paper is to re-examine this issue in the context of recent advances in implementation technologies of logic programming systems.We find that such declarative formulations can indeed be used in practical systems, when combined with the appropriate tool for evaluation. We useexistingformulations of analysis problems --- groundness analysis of logic programs, and strictness analysis of functional programs --- in this case study, and the XSB system, a table-based logic programming system, as the evaluation tool of choice. We give experimental evidence that the resultant groundness and strictness analysis systems are practical in terms of both time and space. In terms of implementation effort, the analyzers took less than 2 man-weeks (in total), to develop, optimize and evaluate. The analyzer itself consists of about 100 lines of tabled Prolog code and the entire system, including the components to read and preprocess input programs and to collect the analysis results, consists of about 500 lines of code.
Fast, effective dynamic compilation
Authors: Auslander Joel , Philipose Matthai , Chambers Craig , Eggers Susan J. , Bershad Brian N.
Published: November 2005

Dynamic compilation enables optimization based on the values of invariant data computed at run-time. Using the values of these run-time constants, a dynamic compiler can eliminate their memory loads, perform constant propagation and folding, remove branches they determine, and fully unroll loops they bound. However, the performance benefits of the more efficient, dynamically-compiled code are offset by the run-time cost of the dynamic compile. Our approach to dynamic compilation strives for both fast dynamic compilation
and
high-quality dynamically-compiled code: the programmer annotates regions of the programs that should be compiled dynamically; a static, optimizing compiler automatically produces pre-optimized machine-code templates, using a pair of dataflow analyses that identify which variables will be constant at run-time; and a simple, dynamic compiler copies the templates, patching in the computed values of the run-time constants, to produce optimized, executable code. Our work targets general- purpose, imperative programming languages, initially C. Initial experiments applying dynamic compilation to C programs have produced speedups ranging from 1.2 to 1.8.
Data specialization
Authors: Knoblock Todd B. , Ruf Erik
Published: November 2005

Given a repeated computation, part of whose input context remains invariant across all repetitions, program staging improves performance by separating the computation into two phases. An early phase executes only once, performing computations depending only on invariant inputs, while a late phase repeatedly performs the remainder of the work given the varying inputs and the results of the early computations.Common staging techniques based on dynamic compilation statically construct an early phase that dynamically generates object code customized for a particular input context. In effect, the results of the invariant computations are encoded as the compiled code for the late phase.This paper describes an alternative approach in which the results of early computations are encoded as a data structure, allowing both the early and late phases to be generated statically. By avoiding dynamic code manipulation, we give up some optimization opportunities in exchange for significantly lower dynamic space/time overhead and reduced implementation complexity.
Teapot
Authors: Chandra Satish , Richards Brad , Larus James R.
Published: November 2005

Recent shared-memory parallel computer systems offer the exciting possibility of customizing memory coherence protocols to fit an application's semantics and sharing patterns. Custom protocols have been used to achieve message-passing performance---while retaining the convenient programming model of a global address space---and to implement high-level language constructs. Unfortunately, coherence protocols written in a conventional language such as C are difficult to write, debug, understand, or modify. This paper describes Teapot, a small, domain-specific language for writing coherence protocols. Teapot uses continuations to help reduce the complexity of writing protocols. Simple static analysis in the Teapot compiler eliminates much of the overhead of continuations and results in protocols that run nearly as fast as hand-written C code. A Teapot specification can be compiled both to an executable coherence protocol and to input for a model checking system, which permits the specification to be verified. We report our experiences coding and verifying several protocols written in Teapot, along with measurements of the overhead incurred by writing a protocol in a higher-level language.
Target-sensitive construction of diagnostic programs for procedure calling sequence generators
Authors: Bailey Mark W. , Davidson Jack W.
Published: November 2005

Building compilers that generate correct code is difficult. In this paper we present a compiler testing technique that closes the gap between actual compiler implementations and correct compilers. Using formal specifications of procedure calling conventions, we have built a target-sensitive test suite generator that builds test cases for a specific aspect of compiler code generators the procedure calling sequence generator. By exercising compilers with these target-specific test suites, our automated testing tool has exposed bugs in every compiler tested. These compilers include ones that have been in heavy use for many years. The detected bugs cause more than 14,000 test cases to fail.
Data flow frequency analysis
Authors: Ramalingam G.
Published: November 2005

Conventional dataflow analysis computes information about what facts may or will not hold during the execution of a program. Sometimes it is useful, for program optimization, to know
how often
or with
what probability
a fact holds true during program execution. In this paper, we provide a precise formulation of this problem for a large class of dataflow problems --- the class of finite bi-distributive subset problems. We show how it can be reduced to a generalization of the standard dataflow analysis problem, one that requires a sum-over-all-paths quantity instead of the usual meet-overall-paths quantity. We show that Kildall's result expressing the meet-over-all-paths value as a maximal-fixed-point carries over to the generalized setting. We then outline ways to adapt the standard dataflow analysis algorithms to solve this generalized problem, both in the intraprocedural and the interprocedural case.
Bottom-up tree rewriting tool MBURG
Authors: Gough K. John
Published: November 2005

mburg
is a tool for producing bottom up tree rewriters. It has been used for code selection in compilers. It produces hard coded tree pattern matchers from tree grammars, with dynamic programming at runtime. It is comparable in its capabilities with
iburg
[1], but has a rather different implementation, and produces its output in
ISO Modula-2
. The source code for the tool is available by ftp.
Toward an objected-oriented Forth
Authors: Zettel Leonard
Published: November 2005

(This article reports the results of a workshop held at EuroFORTH 95, the European Forth Conference at Schloss Dagstuhl, Saarland, Germany: October 27--29, 1995).
Integration of declarative paradigms
Authors: Hanus Michael
Published: November 2005

We discuss the benefits of integrating the most important declarative programming paradigms namely functional and logic programming. Although many problems need to be solved to provide a true amalgamation of these paradigms, such an integration seems to be possible and has positive effects on teaching, research and application of declarative languages.
Future directions in program transformation
Authors: Pettorossi Alberto , Proietti Maurizio
Published: November 2005

The program transformation methodology can provide valuable techniques and tools for the development of programs from specifications and the reuse and customization of software products. Also various approaches to program optimization and program verification can be based on transformation techniques.
Beyond ML
Authors: Reynolds John C.
Published: November 2005

We believe that the most pressing problem in programming-language design is to control the interference that arises when functional and imperative programming are combined, and to give the user more control of storage allocation, without sacrificing the virtues of higher-order procedures, rigorous typing, and modularity that characterize ML. Towards this end, we intend to pursue research on Algol-like languages, linear typing, and the use of regions for storage allocation.