bluuebunny/crossref_metadata_2025 huggingface dataset:
Generating parallel code from object oriented mathematical models
Authors: Andersson Niclas , Fritzson Peter
Published: November 2005

For a long time efficient use of parallel computers has been hindered by dependencies introduced in software through low-level implementation practice. In this paper we present a programming environment and language called Object-Math (Object oriented Mathematical language for scientific computing), which aims at eliminating this problem by allowing the user to represent mathematical equation-based models directly in the system. The system performs analysis of mathematical models to extract parallelism and automatically generates parallel code for numerical solution.

In the context of industrial applications in mechanical analysis, we have so far primarily explored generation of parallel code for solving systems of ordinary differential equations (ODEs), in addition to preliminary work on generating code for solving partial differential equations. Two approaches to extracting parallelism have been implemented and evaluated: extracting parallelism at the equation system level and at the single equation level, respectively. We found that for several applications the corresponding systems of equations do not partition well into subsystems. This means that the equation system level approach is of restricted general applicability. Thus, we focused on the equation-level approach which yielded significant parallelism for ODE systems solution. For the bearing simulation applications we present here, the achieved speedup is however critically dependent on low communication latency of the parallel computer.
Flattening and parallelizing irregular, recurrent loop nests
Authors: Ghuloum Anwar M. , Fisher Allan L.
Published: November 2005

Irregular loop nests in which the loop bounds are determined dynamically by indexed arrays are difficult to compile into expressive parallel constructs, such as segmented scans and reductions. In this paper, we describe a suite of transformations to automatically parallelize such irregular loop nests, even in the presence of recurrences. We describe a simple, general loop flattening transformation, along with new optimizations which make it a viable compiler transformation. A robust recurrence parallelization technique is coupled to the loop flattening transformation, allowing parallelization of segmented reductions, scans, and combining-sends over arbitrary associative operators. We discuss the implementation and performance results of the transformations in a parallelizing Fortran 77 compiler for the Cray C90 supercomputer. In particular, we focus on important sparse matrix-vector multiplication kernels, for one of which we are able to automatically derive an algorithm used by one of the fastest library routines available.
High-level optimization via automated statistical modeling
Authors: Brewer Eric A.
Published: November 2005

We develop the use of statistical modeling for portable high-level optimizations such as data layout and algorithm selection. We build the models automatically from profiling information, which ensures robust and accurate models that reflect all aspects of the target platform.

We use the models to select among several data layouts for an iterative PDE solver and to select among several sorting algorithms. The selection is correct more than 99% of the time on each of four platforms. In the few cases it selects suboptimally, the selected implementation performs nearly as well; that is, it always makes at least a very good choice. Correct selection is platform and workload dependent and can improve performance by nearly a factor of three.

We also use the models to optimize parameters of these applications automatically. In all cases, the models predicted the optimal parameter setting, resulting in improvements ranging up to a factor of three.

Finally, we use the models to construct portable
high-level libraries
, which contain multiple implementations and support for automatic selection and parameter optimization of the fastest implementation for the target platform and workload.
Compiler optimizations for eliminating barrier synchronization
Authors: Tseng Chau-Wen
Published: November 2005

This paper presents novel compiler optimizations for reducing synchronization overhead in compiler-parallelized scientific codes. A hybrid programming model is employed to combine the flexibility of the fork-join model with the precision and power of the single-program, multiple data (SPMD) model. By exploiting compile-time computation partitions, communication analysis can eliminate barrier synchronization or replace it with less expensive forms of synchronization. We show computation partitions and data communication can be represented as systems of symbolic linear inequalities for high flexibility and precision. These optimizations has been implemented in the Stanford SUIF compiler. We extensively evaluate their performance using standard benchmark suites. Experimental results show barrier synchronization is reduced 29% on average and by several orders of magnitude for certain programs.
Data and computation transformations for multiprocessors
Authors: Anderson Jennifer M. , Amarasinghe Saman P. , Lam Monica S.
Published: November 2005

Effective memory hierarchy utilization is critical to the performance of modern multiprocessor architectures. We have developed the first compiler system that fully automatically parallelizes sequential programs and changes the original array layouts to improve memory system performance. Our optimization algorithm consists of two steps. The first step chooses the parallelization and computation assignment such that synchronization and data sharing are minimized. The second step then restructures the layout of the data in the shared address space with an algorithm that is based on a new data transformation framework. We ran our compiler on a set of application programs and measured their performance on the Stanford DASH multiprocessor. Our results show that the compiler can effectively optimize parallelism in conjunction with memory subsystem performance.
Evaluating the locality benefits of active messages
Authors: Spertus Ellen , Dally William J.
Published: November 2005

A major challenge in fine-grained computing is achieving locality without excessive scheduling overhead. We built two J-Machine implementations of a fine-grained programming model, the Berkeley Threaded Abstract Machine. One implementation takes an Active Messages approach, maintaining a scheduling hierarchy in software in order to improve data cache performance. Another approach relies on the J-Machine's message queues and fast task switch, lowering the control costs at the expense of data locality. Our analysis measures the costs and benefits of each approach, for a variety of programs and cache configurations. The Active Messages implementation is strongest when miss penalties are high and for the finest-grained programs. The hardware-buffered implementation is strongest in direct-mapped caches, where it achieves substantially better instruction cache performance.
Optimistic active messages
Authors: Wallach Deborah A. , Hsieh Wilson C. , Johnson Kirk L. , Kaashoek M. Frans , Weihl William E.
Published: November 2005

Low-overhead message passing is critical to the performance of many applications. Active Messages reduce the software overhead for message handling: messages are run as handlers instead of as threads, which avoids the overhead of thread management and the unnecessary data copying of other communication models. Scheduling the execution of Active Messages is typically done by disabling and enabling interrupts, or by polling the network. This primitive scheduling control, combined with the fact that handlers are not schedulable entities, puts severe restrictions on the code that can be run in a message handler. This paper describes a new software mechanism,
Optimistic Active Messages
(OAM), that eliminates these restrictions; OAMs allow arbitrary user code to execute in handlers, and also allow handlers to block. Despite this gain in expressiveness, OAMs perform as well as Active Messages.

We used OAM as the base for an RPC system,
Optimistic RPC
(ORPC), for the Thinking Machines CM-5 multiprocessor; it consists of an optimized thread package and a stub compiler that hides communication details from the programmer. ORPC is 1.5 to 5 times faster than traditional RPC (TRPC) for small messages and performs as well as Active Messages (AM). Applications that primarily communicate using large data transfers or are fairly coarse-grained perform equally well, independent of whether AMs, ORPCs, or TRPCs are used. For applications that send many short messages, however, the ORPC and AM implementations are up to three times faster than the TRPC implementations. Using ORPC, programmers obtain the benefits of well-proven programming abstractions such as threads, mutexes, and condition variables, do not have to be concerned with communication details, and yet obtain nearly the performance of hand-coded Active Message programs.
Scheduling of hard aperiodic tasks
Authors: Lee Jongwon , Lee Sungyoung , Kim Hyungill
Published: November 2005

In this paper, we present a preemptive joint scheduling of hard deadline periodic and hard deadline aperiodic tasks on a uniprocessor real-time system. The scheduling has extended the Critical Task Indicating (CTI) algorithm [4] of which simulation study shows a considerable performance improvement over the other soft aperiodic task schedulings, especially under a heavy transient overload. Since a hard deadline aperiodic task has its own deadline, the proposed algorithm has a decision making mechanism that performs the on-line acceptance/rejection test upon its arrival. For simplicity and good performance, the algorithm reuses the original CTI table being used in the CTI algorithm as a slack search domain. Moreover, by searching the CTI table similarly to a circular list, it has removed the problem of search space limitation caused by the hyperperiod bound.
Re-usable software design for programmable logic controllers
Authors: Bonfatti Flavio , Gadda Gianni , Monari Paola Daniela
Published: November 2005

It is the aim of this paper to present a model conceived for supporting the initial, critical phases of PLC software life cycle, namely requirement specification, requirement analysis and software design, to obtain reusable code. The model, named EASIER, is based on an object-oriented paradigm where the message-method mechanism is replaced by the law and action primitives, since they are more suitable to cope with the real-time, cyclic nature of PLC software. Software re-usability is pursued by identifying independent control modules through a proper bedded encapsulation mechanism, representing system dynamics by means of synchronized state diagrams, expressing context-free behaviour of system components by introducing virtual objects. The EASIER approach is presently validated with respect to relevant reverse and forward engineering applications; from one of these cases we derive the examples used in the paper.
Verus
Authors: Campos S. , Clarke E. , Marrero W. , Minea M.
Published: November 2005

Symbolic model checking is a technique for verifying finite-state concurrent systems. Models with up to 10
30
states can often be verified in minutes. In this paper, we present a new tool to analyze real-time systems, based on this technique. We have designed a language, called
Verus
, for the description of real-time systems. Such a description is compiled into a state-transition graph and represented symbolically using binary decision diagrams. We have developed new algorithms for exploring the state space and computing
quantitative
information about the system. In addition to determining the exact bounds on the length of the time interval between two specified events, we compute the number of occurrences of an event in such an interval. This technique allows us to determine performance measures such as schedulability, response time, and system load. Our algorithms produce more detailed information than traditional methods. This information leads to a better understanding of the behavior of the system, in addition to verifying if its timing requirements are satisfied. We integrate these ideas into the Verus tool, currently under development. To demonstrate how our technique works, we have verified a robotics control system. The results obtained demonstrate that our method can be successfully applied in the analysis of real-time system designs.
Static timing analysis of real-time systems
Authors: Jourdan M. , Maraninchi F.
Published: November 2005

The approach we propose consists in describing a real-time system with a timed extension of a synchronous language. The formal semantics of the language describes how programs can be translated into a wide class of models, usually labeled transition systems, but whose labels can range from pure boolean information to complex assignements to real-valued variables. In particular, Timed Graphs [ACD90] may be obtained. We then use a tool which implements a symbolic modelchecking algorithm for TCTL [ACD90] properties of Timed Graphs. We illustrate the approach with an example taken from robotics. Several real-time tasks are involved in a synchronization scheme, sending and receiving messages, according to various protocols. They are periodically re-activated by an external controller, and should not be re-activated if they are still communicating with each other. We show how to statically determine whether a particular choice of the re-activation delays would allow a deadlock.
The cluster compiler—a tool for the design of time-triggered real-time systems
Authors: Kopetz Hermann , Nossal Roman
Published: November 2005

An off-line planning tool that supports the programmer in developing his real-time application is mandatory in the design of time-triggered real-time systems. This paper describes the architecture and the functions of such a tool, the Cluster Compiler, that is in development at our institute. We emphasize on the principle of a strict separation of the local from the global parts of a distributed system and on the consequences for the structure of the design tool arising from this principle.
SIG3C first anniversary
Authors: Klee Karl J.
Published: November 2005

Congratulations on a great first year for SIG3C, the Special Interest Group for Computing at Community Colleges. This group was chartered on July 1, 1994 as the first
Newsletter
SIG of ACM. The quarterly publication of SIG3C, titled

3C ONLINE

, is the primary vehicle for achieving the goals of SIG3C. The current membership of SIG3C is approximately 300. SIG3C has representation in 38 of the 50 states as well as Austria, Belgium, Canada, Germany, Japan, the Netherlands, Portugal, and South Korea. New York State leads with 45 SIG3C members, followed by California with 25, Canada with 19, New Jersey with 16, and Texas with 14. At least 10 members are affiliated with four-year colleges or universities, and at least 10 members are affiliated with non-collegiate companies or organizations.
The Self-4.0 user interface
Authors: Smith Randall B. , Maloney John , Ungar David
Published: November 2005

Manipulating programs is hard, while manipulating objects in the physical world is often easy. Several attributes of the physical world help make it comprehensible and manipulable: concreteness, uniformity, and flexibility. The Self programming system attempts to apply these attributes to the world within the computer. The semantics of the language, the efficiency and fidelity of its implementation, and the architecture of its user interface conspire to make the experience of constructing programs in Self immediate and tangible. We describe the mechanisms used to achieve this goal, and illustrate those mechanisms within the context of an extended programming task.
Minimizing row displacement dispatch tables
Authors: Driesen Karel , Hölzle Urs
Published: November 2005

Row displacement dispatch tables implement message dispatching for dynamically-typed languages with a run time overhead of one memory indirection plus an equality test. The technique is similar to virtual function table lookup, which is, however, restricted to statically typed languages like C++. We show how to reduce the space requirements of dispatch tables to approximately the same size as virtual function tables. The scheme is then generalized for multiple inheritance. Experiments on a number of class libraries from five different languages demonstrate that the technique is effective for a broad range of programs. Finally, we discuss optimizations of the row displacement algorithm that allow dispatch table construction of these large samples to take place in a few seconds.
Subtypes vs. where clauses
Authors: Day Mark , Gruber Robert , Liskov Barbara , Myers Andrew C.
Published: November 2005

All object-oriented languages provide support for subtype polymorphism, which allows the writing of generic code that works for families of related types. There is also a need, however, to write code that is generic across types that have no real family relationship. To satisfy this need a programming language must provide a mechanism for parametric polymorphism, allowing for types as parameters to routines and types. We show that to support modular programming and separate compilation there must be a mechanism for constraining the actual parameters of the routine or type. We describe a simple and powerful constraint mechanism and compare it with constraint mechanisms in other languages in terms of both ease of use and semantic expressiveness. We also discuss the interaction between subtype and parametric polymorphism: we discuss the subtype relations that can exist between instantiations of parameterized types, and which of those relations are useful and can be implemented efficiently. We illustrate our points using examples in Theta, a new object-oriented language, and we describe the time- and space-efficient implementation of parametric polymorphism used in Theta.
An algebraic semantics of subobjects
Authors: Rossie Jonathan G. , Friedman Daniel P.
Published: November 2005

Existing formalisms of inheritance are not sufficient to model the complexities of the kind of multiple inheritance exemplified in C++. Any satisfactory formalism must model the complicating effects of virtual and non-virtual base classes as well as virtual and non-virtual methods. By abstracting the implementational notion of a subobject and formalizing subobject selection, we develop a formalism to model this combination of features. Not intended as a formal semantics of C++, the resulting model should nevertheless provide an essential level of understanding for language theorists and implementors in their dealings with C++ and related languages.
A reflective model for first class dependencies
Authors: Ducasse S. , Blay-Fornarino M. , Pinna-Dery A. M.
Published: November 2005

We propose a reflective model to express and to automatically manage dependencies between objects. This model describes reflective facilities which enable the changing of language semantics. Although the importance of inter-object dependencies is well accepted, there is only limited object-oriented language support for their specification and implementation. In response to this lack of expressiveness of object models, the FLO language integrates dependency management into the object oriented paradigm. Dependencies are described as first class objects and FLO automatically maintains the consistency of the dependency graph.In this paper, we first show how a user can declare dependencies and how the system maintains the consistency of the graph of expressed dependencies. In a second part, we focus on the implementation of this management by controlling the messages sent to linked objects. In order to make dependency management orthogonal to other application concerns, we propose an abstraction of message handling, implemented with meta-objects. We illustrate the extensibility of our language with different control behavior implementations, in particular we study different implementations of the global control of message propagation flow.
A metaobject protocol for C++
Authors: Chiba Shigeru
Published: November 2005

This paper presents a metaobject protocol (
MOP
) for C++. This MOP was designed to bring the power of meta-programming to C++ programmers. It avoids penalties on runtime performance by adopting a new meta-architecture in which the metaobjects control the compilation of programs instead of being active during program execution. This allows the MOP to be used to implement libraries of efficient, transparent language extensions.
Patterns in practice
Authors: Helm Richard
Published: November 2005

Object-oriented systems often exhibit idiomatic and recurring structures of objects and classes that solve particular design problems and make systems more flexible, elegant, and ultimately reusable. Design patterns have been proposed as one way to represent, record and reuse these recurring design structures and associated design experience. Here we report on experiences in using design patterns during the design of object-oriented systems.
Interactive visualization of design patterns can help in framework understanding
Authors: Lange Danny B. , Nakamura Yuichi
Published: November 2005

Framework programming is regarded as one the main advantages of object-oriented software engineering, and is expected to increase software reuse. In exploiting frameworks, however, programmers often face difficulties caused by the complexity of the hidden architecture and the multiplicity of the design decisions that are embedded in a framework. Interactive visualization of design patterns occurring in a framework shows how the framework is operating, in a flexible yet structured way that contributes to the programmer's understanding of the underlying software architecture. In this way, programmers can explore and use frameworks efficiently even when they are distributed without vast amounts of documentation and source code.
SCONE
Authors: Itoh Jun-ichiro , Yokote Yasuhiko , Tokoro Mario
Published: November 2005

This paper proposes a methodology for making low-level system code of operating systems be replaceable at runtime. Our approach is to use concurrent objects as a basic programming unit for low-level system programs. To realize the different need for each type of system code and to execute these concurrent objects sufficiently efficient, we use a combination of dedicated system service layers and other implementation techniques. System service layers provide the most suitable primitive operations for each concurrent object. Under our programming model for low-level system code, which we call

SCONE

, it is possible to program low-level system code without hazardous operations such as explicit synchronization, direct scheduler manipulation, etc. We present the implementation of our methodology on the

Apertos

operating system and demonstrate its efficiency with performance evaluation.
Lessons from the battlefield
Authors: Vayda Thomas P.
Published: November 2005

The pragmatic aspects of deploying large scale Object Oriented (OO) applications are examined. The focus is on identifying some of the main obstacles that arise in typical large scale OO projects, and offering hints about effective solutions. This The topics are based on a number of actual large scale projects in which the author participated in a It significant capacity and solutions that he adopted or developed to deal with the problems encountered.
Doubly-linked opportunities
Authors: Carraway Jim
Published: November 2005

Does the expression, Opportunity always knocks at the least opportune moment, mean anything to you? Well, it seems to control my life. Recently, while teaching a C++ class, the topic of sorting doublylinked lists came up. I thought this was a subject worth pursuing. so I told my class to consider the problem and that we would cover the matter during the next meeting. Now, it was time for me to do my homework. My usual approach to a situation like this is to review all the textbooks that fill my book shelves and cover my floor. No success. This left me with an opportunity (remember the expression) at a time when I had at least a hundred other things on my
To Do
list. The result of my efforts are presented below.
Efficient parallel recursion
Authors: Hansen Per Brinch
Published: November 2005

A simple mechanism is proposed for dynamic memory allocation of a parallel recursive program with Algol-like scope rules. The method is about as fast as the traditional stack discipline for sequential languages. It has been used to implement the parallel programming language SuperPascal.
Disciplined C
Authors: Noyelle Yves L.
Published: November 2005

Some proposals to render the C language a truly high level language are presented, as well as a program verifying that a given C program conforms to those proposals.
Context-insensitive alias analysis reconsidered
Authors: Ruf Erik
Published: November 2005

Recent work on alias analysis in the presence of pointers has concentrated on
context-sensitive
interprocedural analyses, which treat multiple calls to a single procedure independently rather than constructing a single approximation to a procedure's effect on all of its callers. While context-sensitive modeling offers the potential for greater precision by considering only realizable call-return paths, its empirical benefits have yet to be measured.

This paper compares the precision of a simple, efficient,
context-insensitive
points-to analysis for the C programming language with that of a maximally context-sensitive version of the same analysis. We demonstrate that, for a number of pointer-intensive benchmark programs, context-insensitivity exerts little to no precision penalty. We also describe techniques for using the output of context-insensitive analysis to improve the efficiency of context-sensitive analysis without affecting precision.
Accurate static branch prediction by value range propagation
Authors: Patterson Jason R. C.
Published: November 2005

The ability to predict at compile time the likelihood of a particular branch being taken provides valuable information for several optimizations, including global instruction scheduling, code layout, function inlining, interprocedural register allocation and many high level optimizations. Previous attempts at static branch prediction have either used simple heuristics, which can be quite inaccurate, or put the burden onto the programmer by using execution profiling data or source code hints.

This paper presents a new approach to static branch prediction called
value range propagation
. This method tracks the weighted value ranges of variables through a program, much like constant propagation. These value ranges may be either numeric of symbolic in nature. Branch prediction is then performed by simply consulting the value range of the appropriate variable. Heuristics are used as a fallback for cases where the value range of the variable cannot be determined statically. In the process,
value range propagation
subsumes both constant propagation and copy propagation.

Experimental results indicate that this approach produces significantly more accurate predictions than the best existing heuristic techniques. The
value range propagation
method can be implemented over any “factored” dataflow representation with a static single assignment property (such as SSA form or a dependence flow graph where the variables have been renamed to achieve single assignment). Experimental results indicate that the technique maintains the linear runtime behavior of constant propagation experienced in practice.
Selective specialization for object-oriented languages
Authors: Dean Jeffrey , Chambers Craig , Grove David
Published: November 2005

Dynamic dispatching is a major source of run-time overhead in object-oriented languages, due both to the direct cost of method lookup and to the indirect effect of preventing other optimizations. To reduce this overhead, optimizing compilers for object-oriented languages analyze the classes of objects stored in program variables, with the goal of bounding the possible classes of message receivers enough so that the compiler can uniquely determine the target of a message send at compile time and replace the message send with a direct procedure call.
Specialization
is one important technique for improving the precision of this static class information: by compiling multiple versions of a method, each applicable to a subset of the possible argument classes of the method, more precise static information about the classes of the method's arguments is obtained. Previous specialization strategies have not been selective about where this technique is applied, and therefore tended to significantly increase compile time and code space usage, particularly for large applications. In this paper, we present a more general framework for specialization in object-oriented languages and describe a goal directed specialization algorithm that makes selective decisions to apply specialization to those cases where it provides the highest benefit. Our results show that our algorithm improves the performance of a group of sizeable programs by 65% to 275% while increasing compiled code space requirements by only 4% to 10%. Moreover, when compared to the previous state-of-the-art specialization scheme, our algorithm improves performance by 11% to 67% while simultaneously reducing code space requirements by 65% to 73%.
A type-based compiler for standard ML
Authors: Shao Zhong , Appel Andrew W.
Published: November 2005

Compile-time type information should be valuable in efficient compilation of statically typed functional languages such as Standard ML. But how should type-directed compilation work in real compilers, and how much performance gain will type-based optimizations yield? In order to support more efficient data representations and gain more experience about type-directed compilation, we have implemented a new type-based middle end and back end for the Standard ML of New Jersey compiler. We describe the basic design of the new compiler, identify a number of practical issues, and then compare the performance of our new compiler with the old non-type-based compiler. Our measurement shows that a combination of several simple type-based optimizations reduces heap allocation by 36%; and improves the already-efficient code generated by the old non-type-based compiler by about 19% on a DECstation 500.
Implementation of the data-flow synchronous language SIGNAL
Authors: Amagbégnon Pascalin , Besnard Loïc , Le Guernic Paul
Published: November 2005

This paper presents the techniques used for the compilation of the data-flow, synchronous language SIGNAL. The key feature of the compiler is that it performs formal calculus on systems of boolean equations. The originality of the implementation of the compiler lies in the use of a tree structure to solve the equations.
Unifying data and control transformations for distributed shared-memory machines
Authors: Cierniak Michał , Li Wei
Published: November 2005

We present a unified approach to locality optimization that employs both data and control transformations. Data transformations include changing the array layout in memory. Control transformations involve changing the execution order of programs. We have developed new techniques for compiler optimizations for distributed shared-memory machines, although the same techniques can be used for sequential machines with a memory hierarchy.

Our compiler optimizations are based on an algebraic representation of data mappings and a new data locality model. We present a pure data transformation algorithm and an algorithm unifying data and control transformations. While there has been much work on control transformations, the opportunities for data transformations have been largely neglected. In fact, data transformations have the advantage of being applicable to programs that cannot be optimized with control transformations. The unified algorithm, which performs data and control transformations
simultaneously
, offers improvement over optimizations obtained by applying data and control transformations separately.

The experimental results using a set of applications on a parallel machine show that the new optimizations improve performance significantly. These results are further analyzed using locality metrics with instrumentation and simulation.
The power of assignment motion
Authors: Knoop Jens , Rüthing Oliver , Steffen Bernhard
Published: November 2005

Assignment motion (AM)
and
expression motion (EM)
are the basis of powerful and at the first sight incomparable techniques for removing partially redundant code from a program. Whereas AM aims at the elimination of complete assignments, a transformation which is always desirable, the more flexible EM requires temporaries to remove partial redundancies. Based on the observation that a simple program transformation enhances AM to subsume EM, we develop an algorithm that for the first time captures all second order effects between AM and EM transformations. Under usual structural restrictions, the worst case time complexity of our algorithm is essentially quadratic, a fact which explains the promising experience with our implementation.
Elimination of redundant array subscript range checks
Authors: Kolte Priyadarshan , Wolfe Michael
Published: November 2005

This paper presents a compiler optimization algorithm to reduce the run time overhead of array subscript range checks in programs without compromising safety. The algorithm is based on partial redundancy elimination and it incorporates previously developed algorithms for range check optimization. We implemented the algorithm in our research compiler, Nascent, and conducted experiments on a suite of 10 benchmark programs to obtain four results: (1) the execution overhead of naive range checking is high enough to merit optimization, (2) there are substantial differences between various optimizations, (3) loop-based optimizations that hoist checks out of loops are effective in eliminating about 98% of the range checks, and (4) more sophisticated analysis and optimization algorithms produce very marginal benefits.
EEL
Authors: Larus James R. , Schnarr Eric
Published: November 2005

EEL (Executable Editing Library) is a library for building tools to analyze and modify an executable (compiled) program. The systems and languages communities have built many tools for error detection, fault isolation, architecture translation, performance measurement, simulation, and optimization using this approach of modifying executables. Currently, however, tools of this sort are difficult and time-consuming to write and are usually closely tied to a particular machine and operating system. EEL supports a machine- and system-independent editing model that enables tool builders to modify an executable without being aware of the details of the underlying architecture or operating system or being concerned with the consequences of deleting instructions or adding foreign code.
Stack caching for interpreters
Authors: Ertl M. Anton
Published: November 2005

An interpreter can spend a significant part of its execution time on accessing arguments of virtual machine instructions. This paper explores two methods to reduce this overhead for virtual stack machines by caching top-of-stack values in (real machine) registers. The
dynamic method
is based on having, for every possible state of the cache, one specialized version of the whole interpreter; the execution of an instruction usually changes the state of the cache and the next instruction is executed in the version corresponding to the new state. In the
static method
a state machine that keeps track of the cache state is added to the compiler. Common instructions exist in specialized versions for several states, but it is not necessary to have a version of every instruction for every cache state. Stack manipulation instructions are optimized away.
Teaching on the other side
Authors: Christiaanse Vance
Published: November 2005

When your computer science students leave college and enter the work force, instructors at the work site will take over where you left off. What is the key difference between their classrooms and yours?
LL
and
LR
translators need
k
>1 lookahead
Authors: Parr Terence J. , Quong Russell W.
Published: November 2005

Language translation is a harder and more important problem than language recognition. In particular, programmers implement translators not recognizers. Yet too often, translation is equated with the simpler task of syntactic parsing. This misconception coupled with computing limitations of past computers has led to the almost exclusive use of
LR
(1) and
LL
(1) in parser generators. We claim that use of
k
< 1 lookahead can and should be available in practice, as it simplifies the translator development. We give several examples justifying our arguments.
Let-floating
Authors: Peyton Jones Simon , Partain Will , Santos André
Published: November 2005

Virtually every compiler performs transformations on the program it is compiling in an attempt to improve efficiency. Despite their importance, however, there have been few systematic attempts to categorise such transformations and measure their impact.In this paper we describe a particular group of transformations --- the "let-floating" transformations --- and give detailed measurements of their effect in an optimizing compiler for the non-strict functional language Haskell. Let-floating has not received much explicit attention in the past, but our measurements show that it is an important group of transformations (at least for lazy languages), offering a reduction of more than 30% in heap allocation and 15% in execution time.
Lag, drag, void and use—heap profiling and space-efficient compilation revisited
Authors: Röjemo Niklas , Runciman Colin
Published: November 2005

The context for this paper is functional computation by graph reduction. Our overall aim is more efficient use of memory. The specific topic is the detection of dormant cells in the live graph --- those retained in heap memory though not actually playing a useful role in computation. We describe a profiler that can identify heap consumption by such 'useless' cells. Unlike heap profilers based on traversals of the live heap, this profiler works by examining cells
postmortem
. The new profiler has revealed a surprisingly large proportion of 'useless' cells, even in some programs that previously seemed space-efficient such as the boot-strapping Haskell compiler nhc.
A new look at pattern matching in abstract data types
Authors: Palao Gostanza Pedro , Peña Ricardo , Núñez Manuel
Published: November 2005

In this paper we present a construction smoothly integrating pattern matching with abstract data types. We review some previous proposals [19, 23, 20, 6, 1] and their drawbacks, and show how our proposal can solve them. In particular we pay attention to equational reasoning about programs containing this new facility. We also give its formal syntax and semantics, as well as some guidelines in order to compile the construction efficiently.
pHluid
Authors: Flanagan Cormac , Nikhil Rishiyur S.
Published: November 2005

This paper describes the distributed memory implementation of a shared memory parallel functional language. The language is Id, an implicitly parallel, mostly functional language that is currently evolving into a dialect of Haskell. The target is a distributed memory machine, because we expect these to be the most widely available parallel platforms in the future. The difficult problem is to bridge the gap between the shared memory language model and the distributed memory machine model. The language model assumes that all data is uniformly accessible, whereas the machine has a severe memory hierarchy: a processor's access to remote memory (using explicit communication) is orders of magnitude slower than its access to local memory. Thus, avoiding communication is crucial for good performance. The Id language, and its general dataflow-inspierd compilation to multithreaded code are described elsewhere. In this paper, we focus on our new parallel runtime system and its features for avoiding communication and for tolerating its latency when necessary: multithreading, scheduling and load balancing; the distributed heap model and distributed coherent cacheing, and parallel garbage collection. We have completed the first implementation, and we present some preliminary performance mearsurements.
Comparison of student success in Pascal and C-language curriculums
Authors: Gilberg Richard F. , Forouzan Behrouz A.
Published: November 2005

In September 1994, De Anza College in Cupertino, California added a CS1 C programming class to parallel its traditional Pascal offering. This paper reports on the history leading up to this decision, the success of the program, and our impressions after the first year.
An equational object-oriented data model and its data-parallel query language
Authors: Nishimura Susumu , Ohori Atsushi , Tajima Keishi
Published: November 2005

This paper presents an equational formulation of an object-oriented data model. In this model, a database is represented as a
system of equations
over a set of oid's, and a database query is a transformation of a system of equations into another system of equations. During the query processing, our model maintains an
equivalence relation
over oid's that relates oid's corresponding to the same "real-world entity." By this mechanism, the model achieves a declarative set-based query language and views for objects with identity. Moreover, the query primitives are designed so that queries including object traversal can be evaluated in a data-parallel fashion.
A monotonic superclass linearization for Dylan
Authors: Barrett Kim , Cassels Bob , Haahr Paul , Moon David A. , Playford Keith , Withington P. Tucker
Published: November 2005

Object-oriented languages with multiple inheritance and automatic conflict resolution typically use a linearization of superclasses to determine which version of a property to inherit when several superclasses provide definitions. Recent work has defined several desirable characteristics for linearizations, the most important being monotonicity, which prohibits inherited properties from skipping over direct superclasses. Combined with Dylan's sealing mechanism, a monotonic linearization enables some compile-time method selection that would otherwise be impossible in the absence of a closed-world assumption.The Dylan linearization is monotonic, easily described, strictly observes local precedence order, and produces the same ordering as CLOS when that is monotonic. We present an implementation based on merging and a survey of class heterarchies from several large programs, analyzing where commonly used linearizations differ.
Vortex
Authors: Dean Jeffrey , DeFouw Greg , Grove David , Litvinov Vassily , Chambers Craig
Published: November 2005

Previously, techniques such as class hierarchy analysis and profile-guided receiver class prediction have been demonstrated to greatly improve the performance of applications written in pure object-oriented languages, but the degree to which these results are transferable to applications written in hybrid languages has been unclear. In part to answer this question, we have developed the Vortex compiler infrastructure, a language-independent optimizing compiler for object-oriented languages, with front-ends for Cecil, C++, Java, and Modula-3. In this paper, we describe the Vortex compiler's intermediate language, internal structure, and optimization suite, and then we report the results of experiments assessing the effectiveness of different combinations of optimizations on sizable applications across these four languages. We characterize the benchmark programs in terms of a collection of static and dynamic metrics, intended to quantify aspects of the "object-orientedness" of a program.
Reorganizing split objects
Authors: Astudillo R. Hernán
Published: November 2005

Object-based (i.e. classless) models are very effective for elucidating requirements from users, and they support exploratory programming and rapid prototyping, providing a direct manipulation approach. On the other hand, class-based models have powerful mechanisms to control redundancy, exploit sharing, express extension, and propagate changes to instances.The price object-based approaches pay is loss of control over change propagation, and potential redundancy. Two mechanisms to overcome this are sharing among objects and definition of objects as extension of others. We examine these mechanisms, and consider the effect that interacting policies for objects sharing and definition-by-extension have on change propagation and replication control. An implication is that, in absence of meta-objects or extra-language support, monolithic shared parts cannot coexist with prototypes represented as split objects.
A situated evaluation of the Object Management Group's (OMG) Object Management Architecture (OMA)
Authors: Wallace Evan , Wallnau Kurt C.
Published: November 2005

It has been difficult to objectively assess the real value or maturity of the Object Management Group's Object Management Architecture (OMA). While experience reports have appeared in the literature, these have focused more on the functionality of the end-system than on systematically exploring the strengths and weaknesses of the OMA, and providing practical guidelines on the effective use of the OMA for specific software-engineering problems. In this paper we describe a case study in the use of the OMA to integrate legacy software components into a distributed object system. We assess the OMA in this problem context, and indicate strengths and weaknesses of the specification and current implementations. We extrapolate our experience to a broader class of component-based software systems, and recommend an architectural strategy for the effective use of the OMA to this class of systems.
A functional layer for description logics
Authors: Möller Ralf
Published: November 2005

The paper motivates the facilities provided by Description Logics in an object-oriented programming scenario. It presents a unification approach of Description Logics and object-oriented programming that allows both views to be conveniently used for different subproblems in a modern software-engineering environment. The main thesis of this paper is that in order to use Description Logics in practical applications, a seamless integration with object-oriented system development methodologies must be realized.
OO anthropology (panel)
Authors: Fraser Steven D. , Cockburn Alistair , Coplien Jim , Constantine Larry , West Dave , Brajkovich Leo
Published: November 2005

Anthropology is the study of civilization, particularly its societies, customs, structure, and evolution. Our premise is that there are cultureal "chasms" to be crossed to ensure the success of the technological beachhead established by innovators and early adopters of the OO paradigm. Our panelists will address the following questions:•What anthropological cultural factors have to be "matured" (and how?) to foster the success of the OO paradigm?•What mechanisms are required to facilitate communications between cultures of differing maturity?•What cultural chasms must be crossed to develop a successful organization/culture within the framework supported by the object-oriented paradigm (or more perrversely, is there anything "special" about the OO paradigm)?This panel will interest pracitioners as a forum to share and debate experiences related to our current-day software culture metamorphosis.