bluuebunny/crossref_metadata_2025_split huggingface dataset:
Implementation issues II
Authors: Kenniston Michael S. , Atkinson Russ 
Published: November 2005

The panelists were asked to address three questions. The three sections below are summaries of the ideas discussed in response to each of these questions.
1. When debugging a program, what information about that program is important for presentation to the user? What techniques can the debugger use to determine such information?
While helping to develop a debugger, John Johnson had observed many programmers using it, and had noticed two distinct styles of information gathering:
• Many programmers began by getting fairly small amounts of information. They simply wanted an overview of the "flow" of the program, in order to get a general understanding of its behavior.
• After suspicion had been narrowed down to- a particular area within the program, the users wanted as much information as possible, formatted nicely.
Hardware assisted high level debugging
Authors: Gentleman W. Morven , Hoeksma Henry 
Published: November 2005

Hardware assistance has long been used for logic level and functional unit level hardware debugging, as well as for machine language level software debugging. Such hardware assistance includes probes to detect signals, comparators to identify matches with expected patterns, buffers to record selected events, and independent logic and software to analyze and interpret the observed events. It can also include the ability to generate selected signals to stimulate the object being debugged and the ability to isolate it from normal changes so its state can be examined.
Through knowledge of the data structures and algorithms used by the operating systems, and the runtime representation, register usage, and code bursts produced by compilers, it is possible to take advantage of such hardware assistance in high-level debugging. High level debugging here refers to debugging in terms of abstractions supported by the operating system and programming languages, as well as user defined abstractions built on top of these.
High-level debugging assistance via optimizing compiler technology
Authors: Ottenstein Karl J. , Ottenstein Linda M. 
Published: November 2005

A primary benefit of most software tools is either the prevention or the detection of human error in the development process. Languages, such as Pascal and Ada, have been designed with features such as strong typing to increase the amount of error detection that can be done by the compiler. Syntax directed editors [11] also decrease the opportunity for the introduction of human error.
Our paper describes some of the debugging assistance which can be provided to a user during the transformation of a program by an optimizing compiler. Our premise is that the additional information obtained during optimization could warrant the sole use of optimizing compilers during software development.
Multilingual debugging with the SWAT high-level debugger
Authors: Cardell James R. 
Published: November 2005

The SWAT (TM) debugger, Data General Corporation's Source Language Debugger, is an interactive, high-level, symbolic debugging tool. It offers its users a full complement of standard high-level debugging features with a simple command format modeled after that of Data General's AOS and AOS/VS operating system Command Line Interpreter. Multilingual capability was a primary design goal and this has resulted in the benefits of both wide user acceptance and product extensibility.
This paper presents a summary of SWAT functionality and relates some of the experience of adding support for Data General Information Systems Division's recently announced AOS/VS Pascal and AOS/VS C languages.
The blit debugger
Authors: Cargill Thomas A. 
Published: November 2005

This paper describes the evolution to date of a flexible debugger for C programs on the Blit, a multi-processing bitmap terminal. The debugger is of interest for the following reasons:
-- it is assisted by the terminal software's elegant separation of the debugger process from its subject process.
-- it resides autonomously in the terminal and is bound dynamically to arbitrary subject processes.
-- it executes asynchronously with its subject.
-- its implementation is distributed as a small process in the terminal and a large process in the host timesharing system.
-- its user interface uses graphics and a mouse.
An opinion about the most fruitful direction for further application of graphics is offered.
A practical adoption of partial redundancy elimination
Authors: Bronnikov Dmitri 
Published: November 2005

Partial redundancy elimination is a powerful optimization technique which needs little introduction. The original formulation was introduced in 1979 by Morel and Renvoise. More efficient formulations have since been offered.
We introduce an ever more simple and efficient formulation. We also show how PRE can be used to deal with partially redundant register loads and stores introduced by spilling.
Measuring the dynamic behaviour of AspectJ programs
Authors: Dufour Bruno , Goard Christopher , Hendren Laurie , de Moor Oege , Sittampalam Ganesh , Verbrugge Clark 
Published: November 2005

This paper proposes and implements a rigorous method for studying the dynamic behaviour of AspectJ programs. As part of this methodology several new metrics specific to AspectJ programs are proposed and tools for collecting the relevant metrics are presented. The major tools consist of: (1) a modified version of the AspectJ compiler that tags bytecode instructions with an indication of the cause of their generation, such as a particular feature of AspectJ; and (2) a modified version of the *J dynamic metrics collection tool which is composed of a JVMPI-based trace generator and an analyzer which propagates tags and computes the proposed metrics. This dynamic propagation is essential, and thus this paper contributes not only new metrics, but also non-trivial ways of computing them.
We furthermore present a set of benchmarks that exercise a wide range of AspectJ's features, and the metrics that we measured on these benchmarks. The results provide guidance to AspectJ users on how to avoid efficiency pitfalls, to AspectJ implementors on promising areas for future optimization, and to tool builders on ways to understand the runtime behaviour of AspectJ.
Decentralizing execution of composite web services
Authors: Nanda Mangala Gowri , Chandra Satish , Sarkar Vivek 
Published: November 2005

Distributed enterprise applications today are increasingly being built from services available over the web. A unit of functionality in this framework is a web service, a software application that exposes a set of "typed'' connections that can be accessed over the web using standard protocols. These units can then be composed into a <i>composite</i> web service. BPEL (Business Process Execution Language) is a high-level distributed programming language for creating composite web services.
Although a BPEL program invokes services distributed over several servers, the <i>orchestration</i> of these services is typically under centralized control. Because performance and throughput are major concerns in enterprise applications, it is important to remove the inefficiencies introduced by the centralized control. In a distributed, or decentralized orchestration, the BPEL program is partitioned into independent sub-programs that interact with each other without any centralized control. Decentralization can increase parallelism and reduce the amount of network traffic required for an application.
This paper presents a technique to partition a composite web service written as a single BPEL program into an equivalent set of decentralized processes. It gives a new code partitioning algorithm to partition a BPEL program represented as a program dependence graph, with the goal of minimizing communication costs and maximizing the <i>throughput</i> of multiple concurrent instances of the input program. In contrast, much of the past work on dependence-based partitioning and scheduling seeks to minimize the <i>completion time</i> of a single instance of a program running in isolation. The paper also gives a cost model to estimate the throughput of a given code partition.
Transparent proxies for java futures
Authors: Pratikakis Polyvios , Spacco Jaime , Hicks Michael 
Published: November 2005

A <i>proxy</i> object is a surrogate or placeholder that controls access to another target object. Proxies can be used to support distributed programming, lazy or parallel evaluation, access control, and other simple forms of behavioral reflection. However, <i>wrapper proxies</i> (like <i>futures</i> or <i>suspensions</i> for yet-to-be-computed results) can require significant code changes to be used in statically-typed languages, while proxies more generally can inadvertently violate assumptions of transparency, resulting in subtle bugs.
To solve these problems, we have designed and implemented a simple framework for proxy programming that employs a static analysis based on qualifier inference, but with additional novelties. Code for using wrapper proxies is automatically introduced via a classfile-to-classfile transformation, and potential violations of transparency are signaled to the programmer. We have formalized our analysis and proven it sound. Our framework has a variety of applications, including support for asynchronous method calls returning futures. Experimental results demonstrate the benefits of our framework: programmers are relieved of managing and/or checking proxy usage, analysis times are reasonably fast, overheads introduced by added dynamic checks are negligible, and performance improvements can be significant. For example, changing two lines in a simple RMI-based peer-to-peer application and then using our framework resulted in a large performance gain.
An efficient parallel heap compaction algorithm
Authors: Abuaiadh Diab , Ossia Yoav , Petrank Erez , Silbershtein Uri 
Published: November 2005

We propose a heap compaction algorithm appropriate for modern computing environments. Our algorithm is targeted at SMP platforms. It demonstrates high scalability when running in parallel but is also extremely efficient when running single-threaded on a uniprocessor. Instead of using the standard forwarding pointer mechanism for updating pointers to moved objects, the algorithm saves information for a pack of objects. It then does a small computation to process this information and determine each object's new location. In addition, using a smart parallel moving strategy, the algorithm achieves (almost) perfect compaction in the lower addresses of the heap, whereas previous algorithms achieved parallelism by compacting within several predetermined segments.
Next, we investigate a method that trades compaction quality for a further reduction in time and space overhead. Finally, we propose a modern version of the two-finger compaction algorithm. This algorithm fails, thus, re-validating traditional wisdom asserting that retaining the order of live objects significantly improves the quality of the compaction.
The parallel compaction algorithm was implemented on the IBM production Java Virtual Machine. We provide measurements demonstrating high efficiency and scalability. Subsequently, this algorithm has been incorporated into the IBM production JVM.
Effectiveness of a machine-level, global optimizer
Authors: Johnson Mark S. , Miller Terrence C. 
Published: November 2005

We present an overview of the design of a machine-code-level, global (intraprocedural) optimizer that supports several front-ends producing code for the Hewlett-Packard Precision Architecture family of machines. The basic optimization strategy is described, including information about the division of responsibilities between various components of the compiler. Optimization algorithms are described, including a discussion of the dataflow information they require. Measurements showing the collective and individual effects of various optimizer components are presented.
The performance data presented here was collected using a preliminary version of the optimizer. Development is continuing and further improvements are expected.
Data flow analysis for `intractable' system software
Authors: Johnson Harold 
Published: November 2005

We describe, and give experience with, a new method of intraprocedural data flow analysis on reducible flow-graphs[9]. The method is advantageous in imbedded applications where the added value of improved performance justifies substantial optimization effort, but extremely powerful data flow analysis is required due to the code profile.
The method is unusual in that (1) various kinds of forward data flow analysis are done simultaneously, so that benefit is derived from informative interactions (e.g. between constant propagation[7] and alias analysis[8]) and (2) we abandon insistence on reaching a least fixed point, allowing us to handle extremely broad classes of information (e.g., inequality of array indices, which implies non-aliasing in array references).
We argue that the gain from using a very rich framework more than offsets the loss due to non-minimal fixed points, and justify this with a 'thought experiment' and practical results.
Implementing RUSSELL
Authors: Boehm Hans-Juergen , Demers Alan 
Published: November 2005

We have completed an implementation of the Russell programming language [Don 85]. This effort has been very helpful in the evaluation of the original language design. It has also served to pinpoint the difficulties in implementing languages with type systems as general as that of Russell.
Russell treats both functions and types as data objects which can be freely manipulated by the program. Most operators present in conventional programming languages are viewed as function calls. In spite of this, our compiler produces surprisingly efficient machine code, even with minimal effort invested in the code generator.
The generality of the language served to simplify some aspects of the compiler. We focus on the separate compilation mechanism.
The most difficult implementation problem is that of inferring typing information omitted by the programmer. We argue that this is an essential part of type checking a language such as Russell. Our current solution is only partially satisfactory.
A retargetable debugger
Authors: Ramsey Norman , Hanson David R. 
Published: November 2005

We are developing techniques for building retargetable debuggers. Our prototype, 1db, debugs C programs compiled for the MIPS R3000, Motorola 68020, SPARC, and VAX architectures. It can use a network to connect to faulty processes and can do cross-architecture debugging. 1db's total code size is about 16,000 lines, but it needs only 250–550 lines of machine-dependent code for each target.
1db owes its retargetability to three techniques: getting help from the compiler, using a machine-independent embedded interpreter, and choosing abstractions that minimize and isolate machine-dependent code. 1db reuses existing compiler function by having the compiler emit PostScript code that 1db later interprets; PostScript works well in this unusual context.
Sharlit—a tool for building optimizers
Authors: Tjiang Steven W. K. , Hennessy John L. 
Published: November 2005

A complex and time-consuming function of a modern compiler is global optimization. Unlike other functions of a compiler such as parsing and code generation which examine only one statement or one basic block at a time, optimizers are much larger in scope, examining and changing large portions of a program all at once. The larger scope means optimizers must perform many program transformations. Each of these transformations makes its own particular demands on the internal representation of programs; each can interact with and depend on the others in different ways. This makes optimizers large and complex.
Despite their complexity, few tools exist to help in building optimizers. This is in stark contrast with other parts of the compiler where years of experience have culminated in tools with which these other parts can be constructed easily. For example, parser generators are used to build front-ends, and peephole optimizers and tree matchers are used to build code generators.
This paper presents Sharlit, a tool to support the construction of modular and extensible global optimizers. We will show how Sharlit helps in constructing data-flow analyzers and the transformations that use data-flow analysis information, both are major components of any optimizer.
Sharlit is implemented in C++ and uses C++ in the same way that YACC uses C. Thus we assume the reader has some familiarity with C++[9].
Escape analysis on lists
Authors: Park Young Gil , Goldberg Benjamin 
Published: November 2005

Higher order functional programs constantly allocate objects dynamically. These objects are typically cons cells, closures, and records and are generally allocated in the heap and reclaimed later by some garbage collection process. This paper describes a compile time analysis, called escape analysis, for determining the lifetime of dynamically created objects in higher order functional programs, and describes optimizations that can be performed, based on the analysis, to improve storage allocation and reclamation of such objects. In particular, our analysis can be applied to programs manipulating lists, in which case optimizations can be performed to allow cons cells in spines of lists to be either reclaimed immediately or reused without incurring any garbage collection overhead. In a previous paper on escape analysis [10], we had left open the problem of performing escape analysis on lists.
Escape analysis simply determines when the argument (or some part of the argument) to a function call is returned by that call. This simple piece of information turns out to be sufficiently powerful to allow stack allocation of objects, compile-time garbage collection, reduction of run-time storage reclamation overhead, and other optimizations that are possible when the lifetimes of objects can be computed statically.
Our approach is to define a high-level non-standard semantics that, in many ways, is similar to the standard semantics and captures the escape behavior caused by the constructs in a functional language. The advantage of our analysis lies in its conceptual simplicity and portability (i.e. no assumption is made about an underlying abstract machine).
Communication optimization and code generation for distributed memory machines
Authors: Amarasinghe Saman P. , Lam Monica S. 
Published: November 2005

This paper presents several algorithms to solve code generation and optimization problems specific to machines with distributed address spaces. Given a description of how the computation is to be partitioned across the processors in a machine, our algorithms produce an SPMD (single program multiple data) program to be run on each processor. Our compiler generated the necessary receive and send instructions, optimizes the communication by eliminating redundant communication and aggregating small messages into large messages, allocates space locally on each processor, and translates global data addresses to local addresses.
Our techniques are based on an exact data-flow analysis on individual array element accesses. Unlike data dependence analysis, this analysis determines if two dynamic instances refer to the same value, and not just to the same location. Using this information, our compiler can handle more flexible data decompositions and find more opportunities for communication optimization than systems based on data dependence analysis.
Our technique is based on a uniform framework, where data decompositions, computation decompositions and the data flow information are all represented as systems of linear inequalities. We show that the problems of communication code generation, local memory management, message aggregation and redundant data communication elimination can all be solved by projecting polyhedra represented by sets of inequalities onto lower dimensional spaces.
Compiling real-time programs into schedulable code
Authors: Hong Seongsoo , Gerber Richard 
Published: November 2005

We present a programming language with first-class timing constructs, whose semantics is based on time-constrained relationships between observable events. Since a system specification postulates timing relationships between events, realizing the specification in a program becomes a more straightforward process.
Using these constraints, as well as those imposed by data and control flow properties, our objective is to transform the code so that its worst-case execution time is consistent with its real-time requirements. To accomplish this goal we first translate an event-based source program into intermediate code, in which the timing constraints are imposed on the code itself, and then use a compilation technique which synthesizes feasible code from the original source program.
Experience with fine-grain synchronization in MIMD machines for preconditioned conjugate gradient
Authors: Yeung Donald , Agarwal Anant 
Published: November 2005

This paper discusses our experience with fine-grain synchronization for a variant of the preconditioned conjugate gradient method. This algorithm represents a large class of algorithms that have been widely used but traditionally difficult to implement efficiently on vector and parallel machines. Through a series of experiments conducted using a simulator of a distributed shared-memory multiprocessor, this paper addresses two major questions related to fine-grain synchronization in the context of this application. First, what is the overall impact of fine-grain synchronization on performance? Second, what are the individual contributions of the following three mechanisms typically provided to support fine-grain synchronization: language-level support, full-empty bits for compact storage and communication of synchronization state, and efficient processor operations on the state bits?
Our expereiments indicate that fine-grain synchronization improves overall performancey by a factor of 3.7 on 16 processors using the largest problem size we could simulate; we project that significant performance advantage will be sustained for larger problem sizes. We also show that the bulk of the performance advantage for this application can be attributed to exposing increased parallelism through language-level expression of fine-grain synchronization. A smaller fraction relies on a compact implementation of synchronization state, while an even smaller fraction results from efficient full-empty bit operations.
A new notion of encapsulation
Authors: Gries David , Prins Jan 
Published: November 2005

Generally speaking, a “module” is used as an “encapsulation mechanism” to tie together a set of declarations of variables and operations upon them. Although there is no standard way to instantiate or use a module, the general idea is that a module describes the implementation of all the values of a given type. We believe that this is too inflexible to provide enough control:
one should be able to use different implementations (given by different modules) for variables (and values) of the same type.

When incorporated properly into the notation, this finer grain of control allows one to program at a high level of abstraction and then to indicate how various pieces of the program should be implemented. It provides simple, effective access to earlier-written modules, so that they are useable in a more flexible manner than is possible in current notations. It generalizes to provide the ability to indicate structural transformations, in a disciplined fashion, in order to achieve efficiency with respect to time or space. However, the program will still be understood at the abstract level and the transformations or implementations will be looked at only to deal with efficiency concerns. Finally, some so-called “data types” (e.g.
stack
and subranges of the integers) can more properly be looked upon simply as restricted implementations of more general types (e.g.
sequence
and
integer
). Thus, the notion of subtype becomes less important.