bluuebunny/crossref_metadata_2025_split huggingface dataset:
A database model of debugging
Authors: Powell Michael L. , Linton Mark A. 
Published: November 2005

Debugging a program can be viewed as performing queries and updates on a database that contains both program source and execution state information. This model of debugging simplifies a "debugger" to a database interface for runtime information and allows the debugger to be easily integrated into a programming environment.
We are currently designing a programming environment in which all program information is stored in a relational database system. This system will include debugging capabilities to provide the programmer a simple yet powerful mechanism for describing debugging requests
DYMOS
Authors: Cook Robert P. , Lee Insup 
Published: November 2005

Programs are frequently modified during their lifetime. Furthermore, modifications to some systems have to be made on the fly; that is, without stopping their execution. For example, changes to airline reservation systems, telephone switching systems, and on-line banking systems have to performed dynamically. Other continuously running systems, such as operating systems, may be modified on the fly to increase their availability.
DYMOS is a programming system that supports a programmer modifying a StarMod program dynamically. StarMod [2] is an extension of Modula [3]. To modify procedures dynamically, the programmer modifies and recompiles the source code of the procedures to be replaced and then requests the system to change the current core image to incorporate new code and data.
An overview of Fortran 2003
Authors: Reid John 
Published: November 2005

There is plenty happening just now with respect to Fortran. Two sets of features (for exception handling and for enhancements to allocatable arrays) were defined in Technical Reports as extensions to Fortran 95 and have become widely available in compilers.The features of Fortran 2003 have been chosen and the standard is essentially complete. As well as the contents of the two Technical Reports, this adds interoperability with C, parameterized derived types, procedure pointers, type extension and polymorphism, access to the computing environment, support of international character sets, and many other enhancements.A new Technical Report is essentially complete. This enhances the module features and avoids the 'compilation cascade' that can mar the development of very large programs. It is written as an extension of Fortran 2003, but is expected to be widely implemented as an extension to Fortran 95 compilers.We will summarize all these developments, which will make Fortran even more suitable for large numerically-demanding applications.
Converting Java classes to use generics
Authors: von Dincklage Daniel , Diwan Amer 
Published: November 2005

Generics offer significant software engineering benefits since they provide code reuse without compromising type safety. Thus generics will be added to the Java language in the next release. While this extension to Java will help programmers when they are writing new code, it will not help legacy code unless it is rewritten to use generics. In our experience, manually modifying existing programs to use generics is complex and can be error prone and labor intensive.
We describe a system, Ilwith, that (i) converts non-generic classes to generic classes and (ii) rewrites their clients to use the newly generified classes. Our experiments with a number of Java container classes show that our system is effective in modifying legacy code to use generics.
A unified theory of garbage collection
Authors: Bacon David F. , Cheng Perry , Rajan V. T. 
Published: November 2005

Tracing and reference counting are uniformly viewed as being fundamentally different approaches to garbage collection that possess very distinct performance properties. We have implemented high-performance collectors of both types, and in the process observed that the more we optimized them, the more similarly they behaved - that they seem to share some deep structure.
We present a formulation of the two algorithms that shows that they are in fact duals of each other. Intuitively, the difference is that tracing operates on live objects, or "matter", while reference counting operates on dead objects, or "anti-matter". For every operation performed by the tracing collector, there is a precisely corresponding anti-operation performed by the reference counting collector.
Using this framework, we show that all high-performance collectors (for example, deferred reference counting and generational collection) are in fact hybrids of tracing and reference counting. We develop a uniform cost-model for the collectors to quantify the trade-offs that result from choosing different hybridizations of tracing and reference counting. This allows the correct scheme to be selected based on system performance requirements and the expected properties of the target application.
Vertical profiling
Authors: Hauswirth Matthias , Sweeney Peter F. , Diwan Amer , Hind Michael 
Published: November 2005

Object-oriented programming languages provide a rich set of features that provide significant software engineering benefits. The increased productivity provided by these features comes at a justifiable cost in a more sophisticated runtime system whose responsibility is to implement these features efficiently. However, the virtualization introduced by this sophistication provides a significant challenge to understanding complete system performance, not found in traditionally compiled languages, such as C or C++. Thus, understanding system performance of such a system requires profiling that spans all levels of the execution stack, such as the hardware, operating system, virtual machine, and application.
In this work, we suggest an approach, called <i>vertical profiling</i>, that enables this level of understanding. We illustrate the efficacy of this approach by providing deep understandings of performance problems of Java applications run on a VM with vertical profiling support. By incorporating vertical profiling into a programming environment, the programmer will be able to understand how their program interacts with the underlying abstraction levels, such as application server, VM, operating system, and hardware.
Refactoring class hierarchies with KABA
Authors: Streckenbach Mirko , Snelting Gregor 
Published: November 2005

KABA is an innovative system for refactoring Java class hierar-chies. It uses the Snelting/Tip algorithm [13] in order to determine a behavior-preserving refactoring which is optimal with respect to a given set of client programs. KABA can be based on dynamic as well as static program analysis. The static variant will preserve program behavior for all possible input values; the dynamic version guarantees preservation of behavior for all runs in a given test suite. KABA offers automatic refactoring as well as manual refactoring using a dedicated editor.
In this contribution, we recapitulate the Snelting/Tip algorithm, present the new dynamic version, and explain new extensions which allow to handle full Java. We then present five case studies which discuss the KABA refactoring proposals for programs such as javac and antlr. KABA proved that javac does not need refactoring, but generated semantics-based refactoring proposals for antlr.
Compilation for a high-performance systolic array
Authors: Gross Thomas , Lam Monica S. 
Published: November 2005

We report on a compiler for Warp, a high-performance systolic array developed at Carnegie Mellon. This compiler enhances the usefulness of Warp significantly and allows application programmers to code substantial algorithms.
The compiler combines a novel programming model, which is based on a model of skewed computation for the array, with powerful optimization techniques. Programming in W2 (the language accepted by the compiler) is orders of magnitude easier than coding in microcode, the only alternative available previously.
A dynamic scheduling method for irregular parallel programs
Authors: Lucco Steven 
Published: November 2005

This paper develops a methodology for compiling and executing
irregular
parallel programs. Such programs implement parallel operations whose size and work distribution depend on input data. We show a fundamental relationship between three quantities that characterize an irregular parallel computation: the total available parallelism, the optimal grain size, and the statistical variance of execution times for individual tasks. This relationship yields a dynamic scheduling algorithm that substantially reduces the overhead of executing irregular parallel operations.

We incorporated this algorithm into an extended Fortran compiler. The compiler accepts as input a subset of Fortran D which includes blocked and cyclic decompositions and perfect alignment; it outputs Fortran 77 augmented with calls to library routines written in C. For irregular parallel operations, the compiled code gathers information about available parallelism and task execution time variance and uses this information to schedule the operation. On distributed memory architectures, the compiler encodes information about data access patterns for the runtime scheduling system so that it can preserve communication locality.
We evaluated these compilation techniques using a set of application programs including climate modeling, circuit simulation, and x-ray tomography, that contain irregular parallel operations. The results demonstrate that, for these applications, the dynamic techniques described here achieve near-optimal efficiency on large numbers of processors. In addition, they perform significantly better, on these problems, than any previously proposed static or dynamic scheduling algorithm.
The early history of Smalltalk
Authors: Kay Alan C. 
Published: November 2005

Most ideas come from previous ideas. The sixties, particularly in the ARPA community, gave rise to a host of notions about “human-computer symbiosis” through interactive time-shared computers, graphics screens and pointing devices. Advanced computer languages were invented to simulate complex systems such as oil refineries and semi-intelligent behavior. The soon to follow paradigm shift of modern personal computing, overlapping window interfaces, and object-oriented design came from seeing the work of the sixties as something more than a “better old thing”. That is, more than a better way: to do mainframe computing; for end-users to invoke functionality; to make data structures more abstract. Instead the promise of exponential growth in computing/$/volume demanded that the sixties be regarded as “almosta new thing” and to find out what the actual “new things” might be. For example, one would compute with a handheld “Dynabook” in a way that would not be possible on a shared mainframe; millions of potential users meant that the user interface would have to become a learning environment along the lines of Montessori and Bruner; and needs for large scope, reduction in complexity, and end-user literacy would require that data and control structures be done away with in favor of a more biological scheme of protected universal cells interacting only through messages that could mimic any desired behavior.Early Smalltalk was the first complete realization of these new points of view as parented by its many predecessors in hardware, language and user interface design. It became the exemplar of the new computing, in part, because we were actually trying for a qualitative shift in belief structures—a new Kuhnian paradigm in the same spirit as the invention of the printing press—and thus took highly extreme positions which almost forced these new styles to be invented.
Orchestrating interactions among parallel computations
Authors: Graham Susan L. , Lucco Steven , Sharp Oliver 
Published: November 2005

Many parallel programs contain multiple sub-computations, each with distinct communication and load balancing requirements. The traditional approach to compiling such programs is to impose a processor synchronization barrier between sub-computations, optimizing each as a separate entity. This paper develops a methodology for managing the interactions among sub-computations, avoiding strict synchronization where concurrent or pipelined relationships are possible.
Our approach to compiling parallel programs has two components: symbolic data access analysis and adaptive runtime support. We summarize the data access behavior of sub-computations (such as loop nests) and split them to expose concurrency and pipelining opportunities. The split transformation has been incorporated into an extended FORTRAN compiler, which outputs a FORTRAN 77 program augmented with calls to library routines written in C and a coarse-grained dataflow graph summarizing the exposed parallelism.
The compiler encodes symbolic information, including loop bounds and communication requirements, for an adaptive runtime system, which uses runtime information to improve the scheduling efficiency of irregular sub-computations. The runtime system incorporates algorithms that allocate processing resources to concurrently executing sub-computations and choose communication granularity. We have demonstrated that these dynamic techniques substantially improve performance on a range of production applications including climate modeling and x-ray tomography, expecially when large numbers of processors are available.
A model and an implementation of a logic programming environment
Authors: Komorowski Henryk Jan , Omori Shigeo 
Published: November 2005

It has been claimed that logic programming offers outstanding possibilities for new concepts in programming environments. But with the exceptions of the pioneering work of Shapiro on algorithmic debugging, Pereira's rational debugging and early work on expert systems from Imperial College, there has been little progress reported in the field of logic programming environments. This summary describes our current work on a generic software engineering shell for logic programming. We use reflection and the amalgamation of meta-level language with the object level to express and support the
incremental
character of specifying/programming. An important facet of the shell is that we formalize some aspects of programming methodology and provide heuristics for avoiding errors. These heuristics formalize what experienced programmers may already know.

The shell bears similarities to an expert system since it has explanation mechanisms and provides programming-knowledge acquisition. Currently, it supports single user Prolog programming and runs in C-Prolog. The shell is generic in that it provides support for activities ranging from artificial intelligence programming to formal specification development.
This research has been supported in part by the IBM Young Faculty Development Award and in part by the NSF grant # MCS-84-05079.
Integration mechanisms in Cedar
Authors: Donahue James 
Published: November 2005

The importance of integration in programming environments is well known. Perhaps the easiest way to build an integrated system is to build a closed system; the designers of the system can use whatever ad hoc techniques are available to make the pieces they provide hang together nicely. Many of the integrated editor/compiler/execution environments (like the Cornell Program Synthesizer) fall into this category [Teitelbaum81].
When building an open system, the problem for the designers of the system is not to integrate a fixed collection of tools, but to provide general mechanisms for tool integration. For instance, Unix “pipes” provide an elegant means of integrating new tools by making it easy to make the output of one tool the input of another; also, the simplicity of the Unix file system makes it easy to integrate new devices into the system - the file system conceals the physical peculiarities of the devices instead of making them visible [Kernighan81].
A third-generation SELF implementation
Authors: Hölzle Urs , Ungar David 
Published: November 2005

Programming systems should be both responsive (to support rapid development) and efficient (to complete computations quickly). Pure object-oriented languages are harder to implement efficiently since they need optimization to achieve good performance. Unfortunately, optimization conflicts with interactive responsiveness because it tends to produce long compilation pauses, leading to unresponsive programming environments. Therefore, to achieve good responsiveness, existing exploratory programming environments such as the Smalltalk-80 environment rely on interpretation or non-optimizing dynamic compilation. But such systems pay a price for their interactiveness, since they may execute programs several times slower than an optimizing system.
SELF-93 reconciles high performance with responsiveness by combining a fast, non-optimizing compiler with a slower, optimizing compiler. The resulting system achieves both excellent performance (two or three times faster than existing Smalltalk systems) and good responsiveness. Except for situations requiring large applications to be (re)compiled from scratch, the system allows for pleasant interactive use with few perceptible compilation pauses. To our knowledge, SELF-93 is the first implementation of a pure object-oriented language achieving both good performance and good responsiveness.

When measuring interactive pauses, it is imperative to treat multiple short pauses as one longer pause if the pauses occur in short succession, since they are perceived as one pause by the user. We propose a definition of
pause clustering
and show that clustering can make an order-of-magnitude difference in the pause time distribution.
Reducing false sharing on shared memory multiprocessors through compile time data transformations
Authors: Jeremiassen Tor E. , Eggers Susan J. 
Published: November 2005

We have developed compiler algorithms that analyze explicitly parallel programs and restructure their shared data to reduce the number of false sharing misses. The algorithms analyze per-process shared data accesses, pinpoint the data structures that are susceptible to false sharing and choose an appropriate transformation to reduce it. The transformations either group data that is accessed by the same processor or separate individual data items that are shared.
This paper evaluates that technique. We show through simulation that our analysis successfully identifies the data structures that are responsible for most false sharing misses, and then transforms them without unduly decreasing spatial locality. The reduction in false sharing positively impacts both execution time and program scalability when executed on a KSR2. Both factors combine to increase the maximum achievable speedup for all programs, more than doubling it for several. Despite being able to only approximate actual inter-processor memory accesses, the compiler-directed transformations always outperform programmer efforts to eliminate false sharing.
Improving balanced scheduling with compiler optimizations that increase instruction-level parallelism
Authors: Lo Jack L. , Eggers Susan J. 
Published: November 2005

Traditional list schedulers order instructions based on an optimistic estimate of the load latency imposed by the hardware and therefore cannot respond to variations in memory latency caused by cache hits and misses on non-blocking architectures. In contrast, balanced scheduling schedules instructions based on an estimate of the amount of instruction-level parallelism in the program. By scheduling independent instructions behind loads based on what the program can provide, rather than what the implementation stipulates in the best case (i.e., a cache hit), balanced scheduling can hide variations in memory latencies more effectively.
Since its success depends on the amount of instruction-level parallelism in the code, balanced scheduling should perform even better when more parallelism is available. In this study, we combine balanced scheduling with three compiler optimizations that increase instruction-level parallelism: loop unrolling, trace scheduling and cache locality analysis. Using code generated for the DEC Alpha by the Multiflow compiler, we simulated a non-blocking processor architecture that closely models the Alpha 21164. Our results show that balanced scheduling benefits from all three optimizations, producing average speedups that range from 1.15 to 1.40, across the optimizations. More importantly, because of its ability to tolerate variations in load interlocks, it improves its advantage over traditional scheduling. Without the optimizations, balanced scheduled code is, on average, 1.05 times faster than that generated by a traditional scheduler; with them, its lead increases to 1.18.
Compositional pointer and escape analysis for Java programs
Authors: Whaley John , Rinard Martin 
Published: November 2005

This paper presents a combined pointer and escape analysis algorithm for Java programs. The algorithm is based on the abstraction of points-to escape graphs, which characterize how local variables and fields in objects refer to other objects. Each points-to escape graph also contains escape information, which characterizes how objects allocated in one region of the program can escape to be accessed by another region. The algorithm is designed to analyze arbitrary regions of complete or incomplete programs, obtaining complete information for objects that do not escape the analyzed regions.
We have developed an implementation that uses the escape information to eliminate synchronization for objects that are accessed by only one thread and to allocate objects on the stack instead of in the heap. Our experimental results are encouraging. We were able to analyze programs tens of thousands of lines long. For our benchmark programs, our algorithms enable the elimination of between 24% and 67% of the synchronization operations. They also enable the stack allocation of between 22% and 95% of the objects.
Implementing jalapeño in Java
Authors: Alpern Bowen , Attanasio C. R. , Cocchi Anthony , Lieber Derek , Smith Stephen , Ngo Ton , Barton John J. , Hummel Susan Flynn , Sheperd Janice C. , Mergen Mark 
Published: November 2005

Jalapeño is a virtual machine for Java™ servers written in Java.
A running Java program involves four layers of functionality: the user code, the virtual-machine, the operating system, and the hardware. By drawing the Java / non-Java boundary below the virtual machine rather than above it, Jalapeño reduces the boundary-crossing overhead and opens up more opportunities for optimization.

To get Jalapeño started, a
boot image
of a working Jalapeño virtual machine is concocted and written to a file. Later, this file can be loaded into memory and executed. Because the boot image consists entirely of Java objects, it can be concocted by a Java program that runs in
any
JVM. This program uses reflection to convert the boot image into Jalapeño's object format.

A special MAGIC class allows unsafe casts and direct access to the hardware. Methods of this class are recognized by Jalapeño's three compilers, which ignore their bytecodes and emit special-purpose machine code. User code will not be allowed to call MAGIC methods so Java's integrity is preserved.
A small non-Java program is used to start up a boot image and as an interface to the operating system.
Java's programming features — object orientation, type safety, automatic memory management — greatly facilitated development of Jalapeño. However, we also discovered some of the language's limitations.