bluuebunny/crossref_metadata_2025 huggingface dataset:
A practical arbitrary look-ahead LR parsing technique
Authors: Bermudez Manuel E. , Schimpf Karl M.
Published: November 2005

We present a practical technique that provides an
LR
(0) parser with either fixed or arbitrary look-ahead. The construction algorithm is based on certain paths in the
LR
(0) state diagram, which must be restricted to a maximum length
m
. The technique determines the amount of look-ahead required, and the user is spared the task of guessing it. Instead, the user provides
m
. In situations where single symbol look-ahead is sufficient, the corresponding grammar class (called
LAR
(
m
)) is identical to the
NQLALR
(1) class. For practical grammars that require arbitrary look-ahead, the storage requirements typically do not exceed an amount linear in the size of the corresponding
LR
(0) parser. The technique is shown to work for a practical programming language grammar, and has been used to solve particular cases of the PL/1 keyword problem.
Interprocedural constant propagation
Authors: Callahan David , Cooper Keith D. , Kennedy Ken , Torczon Linda
Published: November 2005

In a compiling system that attempts to improve code for a whole program by optimizing across procedures, the compiler can generate better code for a specific procedure if it knows which variables will have constant values, and what those values will be, when the procedure is invoked. This paper presents a general algorithm for determining for each procedure in a given program the set of inputs that will have known constant values at run time. The precision of the answers provided by this method are dependent on the precision of the local analysis of individual procedures in the program. Since the algorithm is intended for use in a sophisticated software development environment in which local analysis would be provided by the source editor, the quality of the answers will depend on the amount of work the editor performs. Several reasonable strategies for local analysis with different levels of complexity and precision are suggested and the results of a prototype implementation in a vectorizing Fortran compiler are presented.
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.
Static evaluation of functional programs
Authors: Lindstrom Gary
Published: November 2005

Static evaluation underlies essentially all techniques for
a priori
semantic program manipulation, i.e. those that stop short of fully general execution. Included are such activities as type checking, partial evaluation, and, ultimately, optimized compilation.

This paper describes a novel approach to static evaluation of programs in functional languages involving infinite data objects, i.e. those using normal order or “lazy” evaluation. Its principal features are abstract interpretation on a domain of demand patterns, and a notion of function “reversal”. The latter associates with each function f a derived function f' mapping demand patterns on f to demand patterns on its formal parameter. This is used for a comprehensive form of strictness analysis, aiding in efficient compilation.

This analysis leads to a revised notion of
basic block
, appropriate as an intermediate representation for a normal order functional language. An implementation of the analysis technique in Prolog is sketched, as well as an effort currently underway to apply the technique to the generation of optimized G-machine code.
Register allocation in the SPUR Lisp compiler
Authors: Larus James R. , Hilfinger Paul N.
Published: November 2005

Register allocation is an important component of most compilers, particularly those for RISC machines. The SPUR Lisp compiler uses a sophisticated, graph-coloring algorithm developed by Fredrick Chow [Chow84]. This paper describes the algorithm and the techniques used to implement it efficiently and evaluates its performance on several large programs. The allocator successfully assigned most temporaries and local variables to registers in a wide variety of functions. Its execution cost is moderate.
ConstraintLisp
Authors: Liu Bing , Ku Yuen-Wah
Published: November 2005

ConstraintLisp is an object-oriented constraint programming language. It is based on the constraint satisfaction problem (CSP) model in Artificial Intelligence and the object-oriented technology. This integration provides both the declarative representation and efficiency of constraint solving of constraint programming, and the powerful problem modelling capability, maintainability, reusability and extensibility of the object-oriented technology. ConstraintLisp is aimed at providing practical solutions to real life constrained search problems such as scheduling, resource allocation, etc. It is also designed and implemented in an object-oriented approach.
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).
Eliminating false data dependences using the Omega test
Authors: Pugh William , Wonnacott David
Published: November 2005

Array data dependence analysis methods currently in use generate false dependences that can prevent useful program transformations. These false dependences arise because the questions asked are conservative approximations to the questions we really should be asking. Unfortunately, the questions we really should be asking go beyond integer programming and require decision procedures for a sublcass of Presburger formulas. In this paper, we describe how to extend the Omega test so that it can answer these queries and allow us to eliminate these false data dependences. We have implemented the techniques described here and believe they are suitable for use in production compilers.
Delinearization
Authors: Maslov Vadim
Published: November 2005

Exact and efficient data dependence testing is a key to success of loop-parallelizing compiler for computationally intensive programs. A number of algorithms has been created to test array references contained in parameter loops for dependence but most of them are unable to answer the following question correctly: Are references
C
(
i
1
+ 10
j
1
) and
C
(
i
2
+ 5), 0 ≤
i
1
,
i
2
≤ 4, 0 ≤
j
1
,
j
2
≤ 9 independent? The technique introduced in this paper recognizes that
i
1
,
i
2
and
j
1
,
j
2
make different order contributions to the subscript index, and breaks dependence equation
i
1
+ 10
j
1
=
i
2
+ 10
j
2
+ 5 into two equations
i
1
=
i
2
and 10
j
1
= 10
j
2
which then can be solved independently. Since resulting equations contain less variables it is less expensive to solve them. We call this technique
delinearization
because it is reverse of the
linearization
much discussed in the literature.

In the introduction we demonstrate that linearized references are used not infrequently in scientific FORTRAN and C codes. Then we present a theorem on which delinearization algorithm is based and the algorithm itself. The algorithm is fairly simple and inexpensive. As a byproduct it tests equations it produces for independence as exactly as it is done by GCD-test and Banerjee inequalities combined. The algorithm has been implemented at Moscow State University in a vectorizer named VIC.
Beyond induction variables
Authors: Wolfe Michael
Published: November 2005

Induction variable detection is usually closely tied to the strength reduction optimization. This paper studies induction variable analysis from a different perspective, that of finding induction variables for data dependence analysis. While classical induction variable analysis techniques have been used successfully up to now, we have found a simple algorithm based on the Static Single Assignment form of a program that finds all linear induction variables in a loop. Moreover, this algorithm is easily extended to find induction variables in multiple nested loops, to find nonlinear induction variables, and to classify other integer scalar assignments in loops, such as monotonic, periodic and wrap-around variables. Some of these other variables are now classified using ad hoc pattern recognition, while others are not analyzed by current compilers. Giving a unified approach improves the speed of compilers and allows a more general classification scheme. We also show how to use these variables in data dependence testing.
Abstractions for recursive pointer data structures
Authors: Hendren Laurie J. , Hummell Joseph , Nicolau Alexandru
Published: November 2005

Even though impressive progress has been made in the area of optimizing and parallelizing programs with arrays, the application of similar techniques to programs with pointer data structures has remained difficult. In this paper we introduce a new approach that leads to improved analysis and transformation of programs with recursively-defined pointer data structures.

We discuss how an abstract data structure description can improve program analysis by presenting an analysis approach that combines an alias analysis technique,
path matrix
, with information available from an ADDS declaration. Given this improved alias analysis technique, we provide a concrete example of applying a software pipelining transformation to loops involving pointer data structures.
Efficient superscalar performance through boosting
Authors: Smith Michael D. , Horowitz Mark , Lam Monica S.
Published: November 2005

The foremost goal of superscalar processor design is to increase performance through the exploitation of instruction-level parallelism (ILP). Previous studies have shown that speculative execution is required for high instruction per cycle (IPC) rates in non-numerical applications. The general trend has been toward supporting speculative execution in complicated, dynamically-scheduled processors. Performance, though, is more than just a high IPC rate; it also depends upon instruction count and cycle time. Boosting is an architectural technique that supports general speculative execution in simpler, statically-scheduled processors. Boosting labels speculative instructions with their control dependence information. This labelling eliminates control dependence constraints on instruction scheduling while still providng full dependence information to the hardware. We have incorporated boosting into a trace-based, global scheduling algorithm that exploits ILP without adversely affecting the instruction count of a program. We use this algorithm and estimates of the boosting hardware involved to evaluate how much speculative execution support is really necessary to achieve good performance. We find that a statically-scheduled superscalar processor using a minimal implementation of boosting can easily reach the performance of a much more complex dynamically-scheduled superscalar processor.
Cooperative shared memory
Authors: Hill Mark D. , Larus James R. , Reinhardt Steven K. , Wood David A.
Published: November 2005

We believe the absence of massively-parallel, shared-memory machines follows from the lack of a shared-memory programming performance model that can inform programmers of the cost of operations (so they can avoid expensive ones) and can tell hardware designers which cases are common (so they can build simple hardware to optimize them).
Cooperative shared memory
, our approach to shared-memory design, addresses this problem.

Our initial implementation of cooperative shared memory uses a simple programming model, called
Check-In
/
Check-Out (CICO)
, in conjunction with even simpler hardware, called

Dir
1
SW

is a minimal director protocol that adds little complexity to message-passing hardware, but efficiently supports programs written within the CICO model.
YALE: The design of yet another language-based editor
Authors: Zavodnik R J , Middleton M D
Published: November 2005

A simple alternative to language-based editors that employ attribute grammars is proposed in the form of a language independent program editor. This system delegates semantic issues to the back end of the compiler in question, yet resolves all lexical and syntactic questions so that lengthy recompilation after an editing session is bypassed. Finally a prettyprinting-like system is outlined that deals with the text formatting problems in a language independent way.
Alex—A Simple and Efficient Scanner Generator
Authors: Mössenböck H.
Published: November 2005

Alex is a scanner generator which translates the lexical description of a programming language into a scanner for that language. The scanner description language is easy to use, as it is intentionally small and simple. Alex as well as the generated scanners are written in Modula-2 and implemented on several microcomputers. The scanner generator may be used in conjunction with a compiler-compiler. As an example we show how to describe the lexical structure of Modula-2 with our tool. The scanner generated from that description is only about 20 percent slower than a hand-coded scanner.
The efficiency of the equation interpreter compared with the UNH Prolog interpreter
Authors: Heering J , Klint P
Published: November 2005

There are several alternatives for transforming algebraic specifications into executable prototypes. In this note the Equation Interpreter (a rewrite rule interpreter) and the University of New Hampshire Prolog interpreter are viewed as target systems for executing prototypes. The efficiencies of these systems are compared with each other.
Extended pascal - illustrative features
Authors: Joslin D A
Published: November 2005

The Pascal standard (BS6192/ISO7185) is due for revision in about 1987, with BSI as the "sponsoring body". Consideration of the revision began in 1984 within BSI. In addition, the Joint X3J9/IEEE-P77Ø Pascal Standards Committee (JPC) has coordinated a great deal of research into proposed extensions to classic Pascal. An ISO Pascal working group, mainly composed of BSI and JPC members, was set up in 1985 to produce an "Extended Pascal" standard; this group has agreed with JPC the contents of a draft for public comment.
Alex - A simple and efficient scanner generator
Authors: Mossenbock H
Published: November 2005

Alex is a scanner generator which translates the lexical description of a programming language into a scanner for that language. The scanner description language is easy to use, as it is intentionally small and simple. Alex as well as the generated scanners are written in Modula-2 and implemented on several microcomputers. The scanner generator may be used in conjunction with a compiler-compiler. As an example we show how to describe the lexical structure of Modula-2 with our tool. The scanner generated from that description is only about 20 percent slower than a hand-coded scanner.
Pitfalls in PROLOG programming
Authors: Ng K W , Ma W Y
Published: November 2005

A programming language is an intermediate medium between the human user and the machine. Ideally it should reduce the gap between human reasoning and the machine's processing mechanism to the minimum. Accordingly, none of the contemporaryprogramming languages can be said to be ideal. Prolog is no exception. However, it is usually emphasized that programming in Prolog is very easy, even a beginner can handle it within a few hours of learning. The rationale behind this conception is that Prolog clauses are actually some logical statements, and logic is the basis of every rational subject. The problem arises in that Prolog programming is not equivalent to logic programming. Prolog still shares the effect of the influence of the fundamental Von Neumann computer architecture on conventional programming languages. If a user wants to write a Prolog program just according to his logical reasoning, he will probably fall into an unexpected trap of the language.
An integrated Prolog programming environment
Authors: Schreiweis U. , Keune A. , Langendörfer H.
Published: November 2005

For a long time it has been argued that the right kind of representation can provide insight and understanding for a problem. Believing in the general hypothesis that the limitations of our thoughts are all too often identical with the limits of our imagination and visualization capabilities, we have developed a Prolog visualization concept based on a module interconnection graph. This approach provides support for the construction of Prolog systems out of modules (programming-in-the-large). In the approach described below we present an integrated Prolog programming environment based on special features of our hypertext system KnowS. Beyond these features are typed links, node classes, and transfer modules allowing dataflow between several components. But a program is not only a static object. To study the details of a program, we really have to see it in operation. Therefore we also provide animation of program execution. We are convinced that our integrated approach of managing sources of different kinds of information, supporting their structuring and the facility to maintain a Prolog program by hypertext nodes and links is an important step to the integration of software engineering environments and hypertext systems.
Dynamic semantic specification by two-level grammars for a block structured language with subroutine parameters
Authors: Badii M. , Abdollahzadeh F.
Published: November 2005

This paper presents the application of a formal description language -- Van Wijngaarden Two-Level grammar -- to define the dynamic semantics of a block structured language consisting of several types of parameter passing mechanisms. We will show, in a fairly understandable, concise and clear fashion, that the metalinguistic formalism of Two-Level grammar is a fine descriptive device for this purpose.
A history of CLU
Authors: Liskov Barbara
Published: November 2005

The idea of a data abstraction has had a significant impact on the development of programming languages and on programming methodology. CLU was the first implemented programming language to provide direct linguistic support for data abstraction. This paper provides a history of data abstraction and CLU. CLU contains a number of other interesting and influential features, including its exception handling mechanism, its iterators, and its parameterized types.
A history of discrete event simulation programming languages
Authors: Nance Richard E.
Published: November 2005

The history of simulation programming languages is organized as a progression in periods of similar developments. The five periods, spanning 1955-1986, are labeled: The Period Search (1955-1960); The Advent (1961-1965); The Formative Period (1966-1970); The Expansional Period (1971-1978), and The Period of Consolidation and Regeneration (1979-1986). The focus is on recognizing the people and places that have made important contributions in addition to the nature of the contribution. A balance between comprehensive and in-depth treatment has been reached by providing more detailed description of those languages which have or have had major use. Over 30 languages are mentioned, and numerous variations are described in the major contributors. A concluding summary notes the concepts and techniques either originating with simulation programming languages or given significant visibility by them.
The evolution of Forth
Authors: Rather Elizabeth D. , Colburn Donald R. , Moore Charles H.
Published: November 2005

Forth is unique among programming languages in that its development and proliferation has been a grass-roots effort unsupported by any major corporate or academic sponsors. Originally conceived and developed by a single individual, its later development progressed under two significant influences: professional programmers who developed tools to solve application problems and then commercialized them, and the interests of hobbyists concerned with free distribution of Forth. These influences have produced a language markedly different from traditional programming languages.
Recollections about the development of Pascal
Authors: Wirth N.
Published: November 2005

Pascal was defined in 1970 and, after a slow start, became one of the most widely used languages in introductory programming courses. This article first summarises the events leading to Pascal's design and implementation, and then proceeds with a discussion of some of the language's merits and deficiencies. In the last part, developments that followed its release are recounted. Its influence chiefly derived from its being a vehicle for structured programming and a basis for further development of languages and for experiments in program verification.
The development of the C language
Authors: Ritchie Dennis M.
Published: November 2005

The C programming language was devised in the early 1970s as a system implementation language for the nascent Unix operating system. Derived from the typeless language BCPL, it evolved a type structure; created on a tiny machine as a tool to improve a meager programming environment, it has become one of the dominant languages of today. This paper studies its evolution.
Concurrent Object Oriented 'C' (cooC)
Authors: Trehan Rajiv , Sawashima Nobuyuki , Morishita Akira , Tomoda Ichiro , Imai Toru , Maeda Ken-Ichi
Published: November 2005

Concurrent Object Oriented C (cooC) is a language based on the premise that an object not only provides an encapsulation boundary but should also form a process boundary; each object acts concurrently. Upon this basic model various control regimes can be applied to provide different execution and service policies. The cooC language model employs wait-when-necessary communication and affords shared resource protection (via exclusive method invocation). The cooC runtime provides for several execution paradigms for object and method invocation. Varying runtime parameters (number of threads and a mail queue size) allow for: sequential compatible evaluation; fine and coarse grain concurrency; and eager and lazy evaluation, cooC is an extension to C. The underlying syntax of cooC is the same as that of Objective-C; moreover, Objective-C objects are cooC objects which are to be evaluated with a sequential runtime and employ no special synchronisation. The CooC compiler converts cooC into C and also supports C++. Hence cooC is a superset of C, C++ and Objective-C. We present cooC's concurrency object model, runtime and support for various execution and service policies.
A prototype of an interface builder for the Common Lisp Interface Manager—CLIB
Authors: Hesse Jan , König Rainer , Logi Filippo , Herder Jens
Published: November 2005

The Common Lisp Interface Manager (CLIM) is used to develop graphical user interfaces for Lisp-based applications. With the prototype of the CLIM Interface Builder (CLIB) the programmer can generate code for CLIM interactively. The developing process will be fast and less prone to errors. With this new tool, the interactive rapid prototyping reduces costs of a specification phase. Here we present the concept and first results of the prototype of CLIB.
Compiling machine-independent parallel programs
Authors: Philippsen Michael , Heinz Ernst A. , Lukowicz Paul
Published: November 2005

Initial evidence is presented that explicitly parallel, machine-independent programs can automatically be translated into parallel machine code that is competitive in performance with hand-written code.The programming language used is Modula-2*, an extension of Modula-2, which incorporates both data and control parallelism in a portable fashion. An optimizing compiler targeting MIMD, SIMD, and SISD machines translates Modula-2* into machine-dependent C code.The performance of the resulting code is compared to that of equivalent, carefully hand-coded and tuned prograins. On a MasPar MP-1 (SIMD machine with up to 16k processors) the Modula-2* programs typically achieve 80% of the performance of the hand-coded parallel versions. When targeting sequential processors, the Modula-2* programs reach 90% of the performance of hand-coded sequential C. (There are no MIMD results yet.)The effects of two major optimization techniques, synchronization point elimination and data/process alignment are also quantified.
Verification of proofs for the B formal development process
Authors: Dehbonei Babak , Mejia Fernando
Published: November 2005

Formal methods are more frequently used in the realization of industrial safety-critical systems[10]. From the specification to the code, through a refinement process, all the steps are mathematically proved, generally with the help of automatic tools such as provers. This paper addresses the problem of the verification of such tools in the framework of the B formal development technique. The tools are written in a language called
Theory Language
for which the basic proof mechanism is pattern-matching. We propose a technique, based on a unification mechanism, for verifying programs written in this language. Some figures concerning the experimentation of this technique on real-life programs are given.
Complex Gaussian integers for “Gaussian graphics”
Authors: Baker Henry G.
Published: November 2005

Some recent computer languages incorporate rational numbers, complex numbers, and rational complex numbers. We extend these numeric facilities to deal properly with
Gaussian integers
---i.e., complex numbers whose real and imaginary parts are both ordinary (rational) integers. In addition to their intrinsic mathematical interest, such extensions also raise interesting questions regarding polymorphism and multiple inheritance.Since Gaussian integers are the coordinates of discrete square pixels in the complex plane, complex operations can be used to implement 2-D graphics operations. Many 2-D algorithms are more elegant in complex number form---e.g., one can envision a 2-D spreadsheet for scientific applications whose coordinates are Gaussian integers.
Parametrized methods
Authors: de Oliveira Guimarães José
Published: November 2005

This paper presents a new construction that supports creating generic methods, similar to parametrized classes. Generic methods have, in addition to their normal parameters, a set of parameters similar to those of parametrized classes. These parameters are types, constants or procedures. This new construction is important since methods may be redefined to generic in a subclass, making the subclass parametrized, in a way.
Practical data breakpoints
Authors: Wahbe Robert , Lucco Steven , Graham Susan L.
Published: November 2005

A data breakpoint associates debugging actions with programmer-specified conditions on the memory state of an executing program. Data breakpoints provide a means for discovering program bugs that are tedious or impossible to isolate using control breakpoints alone. In practice, programmers rarely use data breakpoints, because they are either unimplemented or prohibitively slow in available debugging software. In this paper, we present the design and implementation of a practical data breakpoint facility.

A data breakpoint facility must monitor all memory updates performed by the program being debugged. We implemented and evaluated two complementary techniques for reducing the overhead of monitoring memory updates. First, we checked write instructions by inserting checking code directly into the program being debugged. The checks use a
segmented bitmap
data structure that minimizes address lookup complexity. Second, we developed data flow algorithms that eliminate checks on some classes of write instructions but may increase the complexity of the remaining checks.

We evaluated these techniques on the SPARC using the SPEC benchmarks. Checking each write instruction using a segmented bitmap achieved an average overhead of 42%. This overhead is
independent
of the number of breakpoints in use. Data flow analysis eliminated an average of 79% of the dynamic write checks. For scientific programs such the NAS kernels, analysis reduced write checks by a factor of ten or more. On the SPARC these optimizations reduced the average overhead to 25%.
Interprocedural modification side effect analysis with pointer aliasing
Authors: Landi William , Ryder Barbara G. , Zhang Sean
Published: November 2005

We present a new interprocedural modification side effects algorithm for C programs, that can discern side effects through general-purpose pointer usage. Ours is the first complete design and implementation of such an algorithm. Preliminary performance findings support the practicality of the technique, which is based on our previous approximation algorithm for pointer aliases [LR92]. Each indirect store through a pointer variable is found, on average, to correspond to a store into 1.2 locations. This indicates that our program-point-specific pointer aliasing information is quite precise when used to determine the effects of these stores.
A practical data flow framework for array reference analysis and its use in optimizations
Authors: Duesterwald Evelyn , Gupta Rajiv , Soffa Mary Lou
Published: November 2005

Data flow analysis techniques have traditionally been restricted to the analysis of scalar variables. This retriction, however, imposes a limitation on the kinds of optimizations that can be performed in loops containing array references. We present a data flow framework for array reference analysis that provides the information needed in various optimizations targeted at sequential or fine-grained parallel architectures. The framework extends the traditional scalar framework by incorporating iteration distance values into the analysis to qualify the computed data flow solution during the fixed point iteration. Analyses phrased in this framework are capable of discovering recurrent access patterns among array references that evolve during the execution of a loop. Applications of our framework are discussed for register allocation, load/store optimizations, and controlled loop unrolling.
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.
Guardians in a generation-based garbage collector
Authors: Dybvig R. Kent , Bruggeman Carl , Eby David
Published: November 2005

This paper describes a new language feature that allows dynamically allocated objects to be saved from deallocation by an automatic storage management system so that clean-up or other actions can be performed using the data stored within the objects. The program has full control over the timing of clean-up actions, which eliminates several potential problems and often eliminates the need for critical sections in code that interacts with clean-up actions. Our implementation is “generation-friendly” in the sense that the additional overhead within a generation-based garbage collector is proportional to the work already done there, and the overhead within the mutator is proportional to the number of clean-up actions actually performed.
Real-time replication garbage collection
Authors: Nettles Scott , O'Toole James
Published: November 2005

We have implemented the first copying garbage collector that permits continuous unimpeded mutator access to the original objects during copying. The garbage collector incrementally replicates all accessible objects and uses a mutation log to bring the replicas up-to-date with changes made by the mutator. An experimental implementation demonstrates that the costs of using our algorithm are small and that bounded pause times of 50 milliseconds can be readily achieved.
LogP: towards a realistic model of parallel computation
Authors: Culler David , Karp Richard , Patterson David , Sahay Abhijit , Schauser Klaus Erik , Santos Eunice , Subramonian Ramesh , von Eicken Thorsten
Published: November 2005

A vast body of theoretical research has focused either on overly simplistic models of parallel computation, notably the PRAM, or overly specific models that have few representatives in the real world. Both kinds of models encourage exploitation of formal loopholes, rather than rewarding development of techniques that yield performance across a range of current and future parallel machines. This paper offers a new parallel machine model, called LogP, that reflects the critical technology trends underlying parallel computers. it is intended to serve as a basis for developing fast, portable parallel algorithms and to offer guidelines to machine designers. Such a model must strike a balance between detail and simplicity in order to reveal important bottlenecks without making analysis of interesting problems intractable. The model is based on four parameters that specify abstractly the computing bandwidth, the communication bandwidth, the communication delay, and the efficiency of coupling communication and computation. Portable parallel algorithms typically adapt to the machine configuration, in terms of these parameters. The utility of the model is demonstrated through examples that are implemented on the CM-5.
Perturbation analysis of high level instrumentation for SPMD programs
Authors: Sarukkai Sekhar R. , Malony Allen D.
Published: November 2005

The process of instrumenting a program to study its behavior can lead to perturbations in the program's execution. These perturbations can become severe for large parallel systems or problem sizes, even when one captures only high level events. In this paper, we address the important issue of eliminating execution perturbations caused by high-level instrumentation of SPMD programs. We will describe perturbation analysis techniques for common computation and communication measurements, and show examples which demonstrate the effectiveness of these techniques in practice.
Explicit data placement (XDP)
Authors: Bala Vasanth , Ferrante Jeanne , Carter Larry
Published: November 2005

The ability to represent, manipulate and optimize data movement between devices such as processors in a distributed memory machine, or between global memory and processors in a shared memory machine, is crucial in generating efficient code for such machines. In this paper we describe a methodology for representing and manipulating data movement explicitly in a compiler. Our methodology, called Explicit Data Placement (XDP), consists of extensions to the compiler's intermediate program language, as well as run-time structures that allow certain operations to be performed efficiently. We also illustrate one of the unique features of the XDP methodology: the ability to manipulate the run-time transfer of data ownership between processors.
Data flow equations for explicitly parallel programs
Authors: Grunwald Dirk , Srinivasan Harini
Published: November 2005

We present a solution to the reaching definitions problem for programs with explicit
lexically specified
parallel constructs, such as cobegin/coend or parallel_sections, both with and without explicit synchronization operations, such as Post, Wait or Advance. The reaching definitions information for sequential programs is used to solve many standard optimization problems. In parallel programs, this information can also be used to explicitly direct communication and data ownership. Although work has been done on analyzing parallel programs to detect data races, little work has been done on optimizing such programs.

We show how the memory consistency model specified by an explicitly parallel programming language can influence the complexity of the reaching definitions problem. By selecting the “weakest” memory consistency semantics, we can efficiently solve the reaching definitions problem for correct programs.
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.
The shared regions approach to software cache coherence on multiprocessors
Authors: Sandhu Harjinder S. , Gamsa Benjamin , Zhou Songnian
Published: November 2005

The effective management of caches is critical to the performance of applications on shared-memory multiprocessors. In this paper, we discuss a technique for software cache coherence tht is based upon the integration of a program-level abstraction for shared data with software cache management
. The program-level abstraction, called
Shared Regions
, explicitly relates synchronization objects with the data they protect. Cache coherence algorithms are presented which use the information provided by shared region primitives, and ensure that shared regions are always cacheable by the processors accessing them. Measurements and experiments of the Shared Region approach on a shared-memory multiprocessors accessing them. Measurements and experiments of the Shared Region approach on a shared-memory multiprocessor are shown. Comparisons with other software based coherence strategies, including a user-controlled strategy and an operating system-based strategy, show that this approach is able to deliver better performance, with relatively low corresponding overhead and only a small increase in the programming effort. Compared to a compiler-based coherence strategy, the Shared Regions approach still performs better than a compiler that can achieve 90% accuracy in allowing cacheing, as long as the regions are a few hundred bytes or larger, or they are re-used a few times in the cache.
Polylith
Authors: Purtilo James
Published: November 2005

Polylith
is the name of a set of enhanced execution time system services along with development tools and an interfacing methodology.
1
As a system, Polylith supports the reliable union of many component tools, addressing the problems of data interchange and synchronization between these tools. It facilitates reuse of code, and promotes the notion that construction of large programs should be viewed instead as orchestration of services. The Polylith is visible as a grammar in which instances of environments
2
are precisely and rapidly specified; it is, through compilation and execution of assertions in that language, a medium through which many programs and tools can be united with impunity.

This paper presents an overview of the Polylith architecture, along with some brief remarks on the requirements analysis leading to Project Polylith at the University of Illinois. Section 2 presents this architecture, summarizing language and data transformation issues. Simple examples are included. Section 3 introduces one particular instance of an environment specified within Polylith called Minion. It is presented as an extended example, showing how the Polylith is utilized to construct an enthusiastic assistant for mathematical problem solving. The closing section contains some evaluation of how Polylith affects the task of environment development.
Maintained and constructor attributes
Authors: Beshers George McArthur , Campbell Roy Harold
Published: November 2005

The potential of the language specific editor as a software engineering tool has attracted much attention in the last few years [Henderson, 84]. This form of an editor offers software engineers the possibility of performing interactive analysis during software production. As a consequence of this possibility, editor generators have become a topic of current research [Reps and Teitelbaum, 84]. In this paper, we describe a general scheme that permits an editor generator to produce a context sensitive, language based editor. The goals of the scheme are to generate editors which can perform interactive type checking, data flow analysis, separate compilation, and update the software project database. The scheme supplements existing attribute grammar techniques with a notion of state provided by maintained and constructor attributes. The method extends the schemes of [Reps et al., 83] and [Fischer and Johnson, 82] by introducing external data structures which support the communication of programming information to the global programming environment.