bluuebunny/crossref_metadata_2025 huggingface dataset:
Automatic inheritance hierarchy restructuring and method refactoring
Authors: Moore Ivan
Published: November 2005

Most, object-oriented programs have imperfectly designed inheritance hierarchies and imperfectly factored methods, and these imperfections tend to increase with maintenance. Hence, even object-oriented programs are more expensive to maintain, harder to understand and larger than necessary. Automatic restructuring of inheritance hierarchies and refactoring of methods can improve the design of inheritance hierarchies, and the factoring of methods. This results in programs being smaller, having better code re-use and being more consistent. This paper describes Guru, a prototype tool for automatic inheritance hierarchy restructuring and method refactoring of Self programs. Results from realistic applications of the tool are presented.
On automatic class insertion with overloading
Authors: Dicky H. , Dony C. , Huchard M. , Libourel T.
Published: November 2005

Several algorithms [Cas92, MS89, Run92, DDHL94a, DDHL95, GMM95] have been proposed to automatically insert a class into an inheritance hierarchy. But actual hierarchies all include overriden and overloaded properties that these algorithms handle either very partially or not at all. Partially handled means handled provided there is a separate given function
f
able to compare overloaded properties [DDHL95, GMM95].In this paper, we describe a new version of our algorithm (named
Ares
) which handles automatic class insertion more efficiently using such a function
f
. Although impossible to fully define, this function can be computed for a number of well defined cases of overloading and overriding. We give a classification of such cases and describe the computation process for a well-defined set of nontrivial cases.The algorithm preserves these important properties:- preservation of the maximal factorization of properties- preservation of the underlying structure (Galois lattice) of the input hierarchy- conservation of relevant classes of the input hierarchy with their properties.
Object on the server
Authors: Shan Yen-Ping , Morgan Tom , Proudfoot Phil , Thompson Jim , Tibetts John , Woolfrey Allen
Published: November 2005

Object-oriented concepts such as reuse and encapsulation offer many benefits to application development, particularly in managing complexity and change. All the benefits of OO that apply to the client can apply equally well to the server. However, until recently, these concepts have proven to benefit only the client side. Could there be any intrinsic or conceptual reason for this? Or could it be a result of timing, the availability of the tools, and the conservative restraints that result from the mission-critical nature of server computing?This panel will explore the roles of objects on the server by examining the experiences of the panelists from a technology consumer's perspective. By doing so, we would like to provide insights for corporations that are making decisions on OO technology, point out pitfalls along the way, and identify potential opportunities for technology providers.All panelists have developed production level object servers. The panel will answer the question of whether we are ready for object servers by discussing the following issues:• Different server types: transactional server, data server, application server, web server, etc. Are they really that much different? Which one is the most important kind?• Experience in implementing and maintaining object systems on the server: the configurations of the systems and how they were arrived at; the tools and programming languages used.• Benefits and drawbacks of server object systems.• What's hard? What's easy?• What are the prerequisites for pervasive deployments of objects on the server? (e.g., standards, application types, customer situations, tools, and languages.)• What would be desirable for technology providers (researchers and vendors) to provide? (Tools, languages, execution environments that represents vendor opportunities.)• Practical advice to organizations interested in introducing objects to the server.
Accreditation in Canada
Authors: Gill Suzanne
Published: November 2005

Accreditation of university and college programs has been in place in Canada since 1985 and is an integral part of the professional certification process that was introduced in 1989. CIPS (Canadian Information Processing Society - the professional society with the largest membership) is in the process of registering the I.S.P. (Information Systems Professional) as the professional designation in several provinces. Since 1985, a number of academic programs have been accredited, and several have been reaccredited after their initial period of 5 years had expired.
Manual and compiler for the terse and modular language DEM
Authors: Houser Chris
Published: November 2005

This paper describes the DEM language and presents a small DEM to C++ translator written in Perl 5. DEM is a terse language for writing modular programs. DEM programs compile to C++ programs, typically swelling three times. Many modifications changing only a few lines of a DEM program change many more lines in the resulting C++ program. DEM is a simplified and streamlined version of the Demeter System (Lieberherr91).
Recursion versus non-recursion in Pascal: recursion can be faster
Authors: Louden K
Published: November 2005

A timing study of two Pascal programs on three machines provides some evidence that, for modern machines and compilers, the cost of removing recursion in non-trivial situations can sometimes be greater than the cost of the recursive procedure calls.
Value locality and load value prediction
Authors: Lipasti Mikko H. , Wilkerson Christopher B. , Shen John Paul
Published: November 2005

Since the introduction of virtual memory demand-paging and cache memories, computer systems have been exploiting spatial and temporal locality to reduce the average latency of a memory reference. In this paper, we introduce the notion of
value locality,
a third facet of locality that is frequently present in real-world programs, and describe how to effectively capture and exploit it in order to perform
load value prediction.
Temporal and spatial locality are attributes of storage locations, and describe the future likelihood of references to those locations or their close neighbors. In a similar vein,
value locality
describes the likelihood of the recurrence of a previously-seen value within a storage location. Modern processors already exploit
value locality
in a very restricted sense through the use of control speculation (i.e. branch prediction), which seeks to predict the future value of a single condition bit based on previously-seen values. Our work extends this to predict entire 32- and 64-bit register values based on previously-seen values. We find that, just as condition bits are fairly predictable on a per-static-branch basis, full register values being loaded from memory are frequently predictable as well. Furthermore, we show that simple microarchitectural enhancements to two modern microprocessor implementations (based on the PowerPC 620 and Alpha 21164) that enable
load value prediction
can effectively exploit
value locality
to collapse true dependencies, reduce average memory latency and bandwidth requirements, and provide measurable performance gains.
An integrated compile-time/run-time software distributed shared memory system
Authors: Dwarkadas Sandhya , Cox Alan L. , Zwaenepoel Willy
Published: November 2005

On a distributed memory machine, hand-coded message passing leads to the most efficient execution, but it is difficult to use. Parallelizing compilers can approach the performance of hand-coded message passing by translating data-parallel programs into message passing programs, but efficient execution is limited to those programs for which precise analysis can be carried out. Shared memory is easier to program than message passing and its domain is not constrained by the limitations of parallelizing compilers, but it lags in performance. Our goal is to close that performance gap while retaining the benefits of shared memory. In other words, our goal is (1) to make shared memory as efficient as message passing, whether hand-coded or compiler-generated, (2) to retain its ease of programming, and (3) to retain the broader class of applications it supports.To this end we have designed and implemented an integrated compile-time and run-time software DSM system. The programming model remains identical to the original pure run-time DSM system. No user intervention is required to obtain the benefits of our system. The compiler computes data access patterns for the individual processors. It then performs a source-to-source transformation, inserting in the program calls to inform the run-time system of the computed data access patterns. The run-time system uses this information to aggregate communication, to aggregate data and synchronization into a single message, to eliminate consistency overhead, and to replace global synchronization with point-to-point synchronization wherever possible.We extended the Parascope programming environment to perform the required analysis, and we augmented the TreadMarks run-time DSM library to take advantage of the analysis. We used six Fortran programs to assess the performance benefits: Jacobi, 3D-FFT, Integer Sort, Shallow, Gauss, and Modified Gramm-Schmidt, each with two different data set sizes. The experiments were run on an 8-node IBM SP/2 using user-space communication. Compiler optimization in conjunction with the augmented run-time system achieves substantial execution time improvements in comparison to the base TreadMarks, ranging from 4% to 59% on 8 processors. Relative to message passing implementations of the same applications, the compile-time run-time system is 0-29% slower than message passing, while the base run-time system is 5-212% slower. For the five programs that XHPF could parallelize (all except IS), the execution times achieved by the compiler optimized shared memory programs are within 9% of XHPF.
Hiding communication latency and coherence overhead in software DSMs
Authors: Bianchini R. , Kontothanassis L. I. , Pinto R. , De Maria M. , Abud M. , Amorim C. L.
Published: November 2005

In this paper we propose the use of a PCI-based programmable
protocol controller
for hiding communication and coherence overheads in software DSMs. Our protocol controller provides three different types of overhead tolerance: a) moving basic communication and coherence tasks away from computation processors; b) prefetching of diffs; and c) generating and applying diffs with hardware assistance. We evaluate the isolated and combined impact of these features on the performance of TreadMarks. We also compare performance against two versions of the Shrimp-based AURC protocol. Using detailed execution-driven simulations of a 16-node network of workstations, we show that the greatest performance benefits provided by our protocol controller come from our hardware-supported diffs. Reducing the burden of communication and coherence transactions on the computation processor is also beneficial but to a smaller extent. Prefetching is not always profitable. Our results show that our protocol controller can improve running time performance by up to 50% for TreadMarks, which means that it can double the TreadMarks speedups. The overlapping implementation of TreadMarks performs as well or better than AURC for 5 of our 6 applications. We conclude that the simple hardware support we propose allows for the implementation of high-performance software DSMs at low cost. Based on this conclusion, we are building the NCP
2
parallel system at COPPE/UFRJ.
Compiler-directed page coloring for multiprocessors
Authors: Bugnion Edouard , Anderson Jennifer M. , Mowry Todd C. , Rosenblum Mendel , Lam Monica S.
Published: November 2005

This paper presents a new technique,
compiler-directed page coloring,
that eliminates conflict misses in multiprocessor applications. It enables applications to make better use of the increased aggregate cache size available in a multiprocessor. This technique uses the compiler's knowledge of the access patterns of the parallelized applications to direct the operating system's virtual memory page mapping strategy. We demonstrate that this technique can lead to significant performance improvements over two commonly used page mapping strategies for machines with either direct-mapped or two-way set-associative caches. We also show that it is complementary to latency-hiding techniques such as prefetching.We implemented compiler-directed page coloring in the SUIF parallelizing compiler and on two commercial operating systems. We applied the technique to the SPEC95fp benchmark suite, a representative set of numeric programs. We used the SimOS machine simulator to analyze the applications and isolate their performance bottlenecks. We also validated these results on a real machine, an eight-processor 350MHz Digital AlphaServer. Compiler-directed page coloring leads to significant performance improvements for several applications. Overall, our technique improves the SPEC95fp rating for eight processors by 8% over Digital UNIX's page mapping policy and by 20% over a page coloring, a standard page mapping policy. The SUIF compiler achieves a SPEC95fp ratio of 57.4, the highest ratio to date.
Support for dynamic binding in strongly typed languages
Authors: Gantenbein R E
Published: November 2005

Dynamic binding is a facility usually found only in weakly typed languages. A strongly typed, block-structured language can, however, also support dynamic binding if its implementation is modified according to a set of widely applicable principles. The result of applying these principles to a strongly typed base language is a language that has much of the flexibility of weakly typed languages without requiring extensive run-time type checking.The primary principles in this general approach to adding dynamic binding to a language are providing separate compilation for the units of dynamic binding, establishing a link between a name in one unit and its implementation in another, and assuring that programs using dynamic binding remain consistent during their execution. There are different methods for implementing each of these principles; two languages to which dynamic binding has been added serve to illustrate some of the alternatives.
Commutativity analysis
Authors: Rinard Martin C. , Diniz Pedro C.
Published: November 2005

This paper presents a new analysis technique, commutativity analysis, for automatically parallelizing computations that manipulate dynamic, pointer-based data structures. Commutativity analysis views the computation as composed of operations on objects. It then analyzes the program at this granularity to discover when operations commute (i.e. generate the same final result regardless of the order in which they execute). If all of the operations required to perform a given computation commute, the compiler can automatically generate parallel code.We have implemented a prototype compilation system that uses commutativity analysis as its primary analysis framework. We have used this system to automatically parallelize two complete scientific computations: the Barnes-Hut N-body solver and the Water code. This paper presents performance results for the generated parallel code running on the Stanford DASH machine. These results provide encouraging evidence that commutativity analysis can serve as the basis for a successful parallelizing compiler.
Global communication analysis and optimization
Authors: Chakrabarti Soumen , Gupta Manish , Choi Jong-Deok
Published: November 2005

Reducing communication cost is crucial to achieving good performance on scalable parallel machines. This paper presents a new compiler algorithm for global analysis and optimization of communication in data-parallel programs. Our algorithm is distinct from existing approaches in that rather than handling loop-nests and array references one by one, it considers all communication in a procedure and their interactions under different placements before making a final decision on the placement of any communication. It exploits the flexibility resulting from this advanced analysis to eliminate redundancy, reduce the number of messages, and reduce contention for cache and communication buffers, all in a unified framework. In contrast, single loop-nest analysis often retains redundant communication, and more aggressive dataflow analysis on array sections can generate too many messages or cache and buffer contention. The algorithm has been implemented in the IBM pHPF compiler for High Performance Fortran. During compilation, the number of messages per processor goes down by as much as a factor of nine for some HPF programs. We present performance results for the IBM SP2 and a network of Sparc workstations (NOW) connected by a Myrinet switch. In many cases, the communication cost is reduced by a factor of two.
Efficient and language-independent mobile programs
Authors: Adl-Tabatabai Ali-Reza , Langdale Geoff , Lucco Steven , Wahbe Robert
Published: November 2005

This paper evaluates the design and implementation of Omniware: a safe, efficient, and language-independent system for executing mobile program modules. Previous approaches to implementing mobile code rely on either language semantics or abstract machine interpretation to enforce safety. In the former case, the mobile code system sacrifices universality to gain safety by dictating a particular source language or type system. In the latter case, the mobile code system sacrifices performance to gain safety through abstract machine interpretation.Omniware uses software fault isolation, a technology developed to provide safe extension code for databases and operating systems, to achieve a unique combination of language-independence and excellent performance. Software fault isolation uses only the semantics of the underlying processor to determine whether a mobile code module can corrupt its execution environment. This separation of programming language implementation from program module safety enables our mobile code system to use a radically simplified virtual machine as its basis for portability. We measured the performance of Omniware using a suite of four SPEC92 programs on the Pentium, PowerPC, Mips, and Sparc processor architectures. Including the overhead for enforcing safety on all four processors, OmniVM executed the benchmark programs within 21% as fast as the optimized, unsafe code produced by the vendor-supplied compiler.
Simple objects for Standard ML
Authors: Reppy John , Riecke Jon
Published: November 2005

We propose a new approach to adding objects to Standard ML (SML) based on explicit declarations of object types, object constructors, and subtyping relationships, with a generalization of the SML case statement to a "typecase" on object types. The language, called Object ML (OML), has a type system that conservatively extends the SML type system, preserves sound static typing, and permits type inference. The type system sacrifices some of the expressiveness found in recently proposed schemes, but has the virtue of simplicity. We give examples of how features found in other object-oriented languages can be emulated in OML, discuss the formal properties of OML, and describe some implementation issues.
Flow-directed inlining
Authors: Jagannathan Suresh , Wright Andrew
Published: November 2005

A
flow-directed inlining
strategy uses information derived from control-flow analysis to specialize and inline procedures for functional and object-oriented languages. Since it uses control-flow analysis to identify candidate call sites, flow-directed inlining can inline procedures whose relationships to their call sites are not apparent. For instance, procedures defined in other modules, passed as arguments, returned as values, or extracted from data structures can all be inlined. Flow-directed inlining specializes procedures for particular call sites, and can selectively inline a particular procedure at some call sites but not at others. Finally, flow-directed inlining encourages modular implementations: control-flow analysis, inlining, and post-inlining optimizations are all orthogonal components. Results from a prototype implementation indicate that this strategy effectively reduces procedure call overhead and leads to significant reduction in execution time.
Tail-recursive parallel summing of a multi-list
Authors: Yuen C. K. , Feng M. D.
Published: November 2005

An apparently simple program for summing a list of numbers, with parallel tasks spawned to sum sublists, causes some problem with tail recursion and side effects. It can be solved by combining functional result return with task synchronization.
Future directions in program transformations
Authors: Paige R.
Published: November 2005

As the emphasis of Programming Languages has evolved from computing on numbers to computing on programs, the area of program transformations has naturally gained in importance. This paper briefly surveys what transformational programming is about, and how to make progress in the field.
On the need for a popular formal semantics
Authors: Schmidt David A.
Published: November 2005

The technology transfer from semantics research to mainstream computing has been hampered by specialization of techniques at the expense of calculational clarity. A "popular semantics" is proposed as a remedy.
Provably-secure programming languages for remote evaluation
Authors: Volpano Dennis
Published: November 2005

Remote evaluation and dynamically-extensible systems pose serious safety and security risks. Programming language design has a major role in overcoming some of these risks. Important research areas include designing suitable languages for remote evaluation, identifying appropriate security and safety properties for them, and developing provably-sound logics for reasoning about the properties in the context of separate compilation and dynamic linking.
Is Ada an object oriented programming language?
Authors: Touati H
Published: November 2005

This article presents an argument and a counter-argument on Ada being an object oriented programming language, in the style of a famous classic author. This work was done as part of the final examination for an advanced Programming Language Design course taught by Professor Larry Rowe at UC Berkeley in Fall 1986.
A software science counting strategy for the full Ada language
Authors: Miller D M , Maness R S , Howatt J W , Shaw W H
Published: November 2005

A software science counting strategy is defined for the Ada* programming language. Two initial approaches, one based on intuition and the other based on trial-and-error, prove unsatisfactory. The third, based on the BNF description of Ada, leads to a satisfactory counting strategy. In contrast to most software science counting strategies, ones that consider only executable code, this strategy provides rules for classifying tokens in an entire Ada program, including declarations, as operators and operands.
Robot control techniques: Part one
Authors: Frenger Paul
Published: November 2005

This two-part paper describes the author's recent experiences with robot control systems. First, three principal programming techniques are reviewed, including dedicated robotics languages; machine tool languages; and general purpose computer programming languages. Then, unconventional languages for robot control, such as PostScript and Java, are discussed. In the next installment, the use of Forth as an object-oriented language to develop the author's multiprocessor android control system is explored.
A member lookup algorithm for C++
Authors: Ramalingam G. , Srinivasan Harini
Published: November 2005

The member lookup problem in C++ is the problem of resolving a specified member name in the context of a specified class. Member lookup in C++ is complicated by the presence of virtual inheritance and multiple inheritance. In this paper, we present an efficient algorithm for member lookup in C++. We also present a formalism for the multiple inheritance mechanism of C++, which we use as the basis for deriving our algorithm. The formalism may also be of use as a formal basis for deriving other C++ compiler algorithms.
Flick
Authors: Eide Eric , Frei Kevin , Ford Bryan , Lepreau Jay , Lindstrom Gary
Published: November 2005

An interface definition language (
IDL
) is a nontraditional language for describing interfaces between software components.
IDL
compilers generate "stubs" that provide separate communicating processes with the abstraction of local object invocation or procedure call. High-quality stub generation is essential for applications to benefit from component-based designs, whether the components reside on a single computer or on multiple networked hosts. Typical
IDL
compilers, however, do little code optimization, incorrectly assuming that interprocess communication is always the primary bottleneck. More generally, typical
IDL
compilers are "rigid" and limited to supporting only a single
IDL
, a fixed mapping onto a target language, and a narrow range of data encodings and transport mechanisms.
Flick
, our new
IDL
compiler, is based on the insight that
IDL
s are true languages amenable to modern compilation techniques. Flick exploits concepts from traditional programming language compilers to bring both flexibility and optimization to the domain of
IDL
compilation. Through the use of carefully chosen intermediate representations, Flick supports multiple
IDL
s, diverse data encodings, multiple transport mechanisms, and applies numerous optimizations to all of the code it generates. Our experiments show that Flick-generated stubs marshal data between 2 and 17 times faster than stubs produced by traditional
IDL
compilers, and on today's generic operating systems, increase end-to-end throughput by factors between 1.2 and 3.7.
Generational garbage collection and the radioactive decay model
Authors: Clinger William D. , Hansen Lars T.
Published: November 2005

If a fixed exponentially decreasing probability distribution function is used to model every object's lifetime, then the age of an object gives no information about its future life expectancy. This
radioactive decay
model implies there can be no rational basis for deciding which live objects should be promoted to another generation. Yet there remains a rational basis for deciding how many objects to promote, when to collect garbage, and which generations to collect.Analysis of the model leads to a new kind of generational garbage collector whose effectiveness does not depend upon heuristics that predict which objects will live longer than others.This result provides insight into the computational advantages of generational garbage collection, with implications for the management of objects whose life expectancies are difficult to predict.
Partial dead code elimination using slicing transformations
Authors: Bodík Rastislav , Gupta Rajiv
Published: November 2005

We present an approach for optimizing programs that uncovers additional opportunities for optimization of a statement by
predicating
the statement. In this paper predication algorithms for achieving partial dead code elimination (PDE) are presented. The process of predication embeds a statement in a control flow structure such that the statement is executed only if the execution follows a path along which the value computed by the statement is live. The control flow restructuring performed to achieve predication is expressed through
slicing transformations
. This approach achieves PDE that is not realizable by existing algorithms. We prove that our algorithm never increases the operation count along any path, and that for acyclic code all partially dead statements are eliminated. The slicing transformation that achieves predication introduces into the program additional conditional branches. These branches are eliminated in a branch deletion step based upon code duplication. We also show how PDE can be used by acyclic schedulers for VLIW processors to reduce critical path lengths along frequently executed paths.
Efficient formulation for optimal modulo schedulers
Authors: Eichenberger Alexandre E. , Davidson Edward S.
Published: November 2005

Modulo scheduling algorithms based on optimal solvers have been proposed to investigate and tune the performance of modulo scheduling heuristics. While recent advances have broadened the scope for which the optimal approach is applicable, this approach increasingly suffers from large execution times. In this paper, we propose a more efficient formulation of the modulo scheduling space that significantly decreases the execution time of solvers based on integer linear programs. For example, the total execution time is reduced by a factor of 8.6 when 782 loops from the Perfect Club, SPEC, and Livermore Fortran Kernels are scheduled for minimum register requirements using the more efficient formulation instead of the traditional formulation. Experimental evidence further indicates that significantly larger loops can be scheduled under realistic machine constraints.
Componential set-based analysis
Authors: Flanagan Cormac , Felleisen Matthias
Published: November 2005

Set based analysis is a constraint-based whole program analysis that is applicable to functional and object-oriented programming language. Unfortunately, the analysis is useless for large programs, since it generates descriptions of data flow relationships that grow quadratically in the size of the program.This paper presents componential set-based analysis, which is faster and handles larger programs without any loss of accuracy over set-based analysis. The design of the analysis exploits a number of theoretical results concerning constraint systems, including a completeness result and a decision algorithm concerning the observable equivalance of constraint systems. Experimental results validate the practically of the analysis.
Data-centric multi-level blocking
Authors: Kodukula Induprakas , Ahmed Nawaaz , Pingali Keshav
Published: November 2005

We present a simple and novel framework for generating blocked codes for high-performance machines with a memory hierarchy. Unlike traditional compiler techniques like tiling, which are based on reasoning about the control flow of programs, our techniques are based on reasoning directly about the flow of data through the memory hierarchy. Our data-centric transformations permit a more direct solution to the problem of enhancing data locality than current control-centric techniques do, and generalize easily to multiple levels of memory hierarchy. We buttress these claims with performance numbers for standard benchmarks from the problem domain of dense numerical linear algebra. The simplicity and intuitive appeal of our approach should make it attractive to compiler writers as well as to library writers.
A modular, polyvariant and type-based closure analysis
Authors: Banerjee Anindya
Published: November 2005

We observe that the
principal typing property
of a type system is the enabling technology for
modularity
and
separate compilation
[10]. We use this technology to formulate a modular and polyvariant closure analysis, based on the rank 2 intersection types annotated with control-flow information.Modularity manifests itself in a syntax-directed, annotated-type inference algorithm that can analyse
program fragments
containing free variables: a
principal typing
property is used to formalise it. Polyvariance manifests itself in the separation of different behaviours of the same function at its different uses: this is formalised via the rank 2 intersection types. As the rank 2 intersection type discipline types at least all (core) ML programs, our analysis can be used in the separate compilation of such programs.
Type-driven defunctionalization
Authors: Bell Jeffrey M. , Bellegarde Françoise , Hook James
Published: November 2005

In 1972, Reynolds outlined a general method for eliminating functional arguments known as
defunctionalization
. The idea underlying defunctionalization is encoding a functional value as first-order data, and then realizing the applications of the encoded function via an
apply
function. Although this process is simple enough, problems arise when defunctionalization is used in a polymorphic language. In such a language, a functional argument of a higher-order function can take different type instances in different applications. As a consequence, its associated
apply
function can be untypable in the source language. In the paper we present a defunctionalization transformation which preserves typability. Moreover, the transformation imposes no restriction on functional arguments of recursive functions, and it handles functions as results as well as functions encapsulated in constructors. The key to this success is the use of type information in the defunctionalization transformation. Run-time characteristics are preserved by defunctionalization; hence, there is no performance improvement coming from the transformation itself. However closures need not be implemented to compile the transformed program.
The effectiveness of flow analysis for inlining
Authors: Ashley J. Michael
Published: November 2005

An interprocedural flow analysis can justify inlining in higher-order languages. In principle, more inlining can be performed as analysis accuracy improves. This paper compares four flow analyses to determine how effectively they justify inlining in practice. The paper makes two contributions. First, the relative merits of the flow analyses are measured with all other variables held constant. The four analyses include two monovariant and two polyvariant analyses that cover a wide range of the accuracy/cost spectrum. Our measurements show that the effectiveness of the inliner improves slightly as analysis accuracy improves, but the improvement is offset by the compile-time cost of the accurate analyses. The second contribution is an improvement to the previously reported inlining algorithm used in our experiments. The improvement causes flow information provided by a polyvariant analysis to be selectively merged. By merging flow information depending on the inlining context, the algorithm is able to expose additional opportunities for inlining. This merging technique can be used in any program transformer justified by a polyvariant flow analysis. The revised algorithm is fully implemented in a production Scheme compiler.
Monadic state
Authors: Launchbury John , Sabry Amr
Published: November 2005

Type safety of imperative programs is an area fraught with difficulty and requiring great care. The SML solution to the problem, originally involving imperative type variables, has been recently simplified to the syntactic-value restriction. In Haskell, the problem is addressed in a rather different way using explicit monadic state. We present an operational semantics for state in Haskell and the first full proof of type safety. We demonstrate that the
semantic
notion of value provided by the explicit monadic types is able to avoid any problems with generalization.
Implementing bit-addressing with specialization
Authors: Draves Scott
Published: November 2005

General media-processing programs are easily expressed with bit-addressing and variable-sized bit-fields. But the natural implementation of bit-addressing relies on dynamic shift offsets and repeated loads, resulting in slow execution. If the code is specialized to the alignment of the data against word boundaries, the offsets become static and many repeated loads can be removed. We show how introducing modular arithmetic into an automatic compiler generator enables the transformation of a program that uses bit-addressing into a synthesizes of fast specialized programs.In partiai-evaluation jargon we say: modular arithmetic is supported by extending the binding time lattice used by the static analysis in a polyvariant compiler generator. The new binding time Cyclic functions like a partially static integer.A software cache combined with a fast, optimistic sharing analysis built into the compilers eliminates repeated loads and stores. The utility of the transformation is demonstrated with a collection of examples and benchmark data. The examples include vector arithmetic, audio synthesis, image processing, and a base-64 codec.
Interconvertbility of set constraints and context-free language reachability
Authors: Melski David , Reps Thomas
Published: November 2005

We show the interconvertibility of context-free-language reachability problems and a class of set-constraint problems: given a context-free-language reachability problem, we show how to construct a set-constraint problem whose answer gives a solution to the reachability problem; given a set-constraint problem, we show how to construct a context-free-language reachability problem whose answer gives a solution to the set-constraint problem. The interconvertibility of these two formalisms offers an conceptual advantage akin to the advantage gained from the interconvertibility of finite-state automata and regular expressions in formal language theory, namely, a problem can be formulated in whichever formalism is most natural. It also offers some insight into the "

O(n
3
)

bottleneck" for different types of program-analysis problems, and allows results previously obtained for context-free-language reachability problems to be applied to set-constraint problems.
Annotation-directed run-time specialization in C
Authors: Grant Brian , Mock Markus , Philipose Matthai , Chambers Craig , Eggers Susan J.
Published: November 2005

We present the design of a dynamic compilation system for C. Directed by a few declarative user annotations specifying where and on what dynamic compilation is to take place, a binding time analysis computes the set of run-time constants at each program point in each annotated procedure's control flow graph; the analysis supports program-point-specific polyvariant division and specialization. The analysis results guide the construction of a specialized run-time specializer for each dynamically compiled region; the specializer supports various caching strategies for managing dynamically generated code and supports mixes of speculative and demand-driven specialization of dynamic branch successors. Most of the key cost/benefit trade-offs in the binding time analysis and the run-time specialize are open to user control through declarative policy annotations. Our design is being implemented in the context of art existing optimizing compiler.
Multi-stage programming with explicit annotations
Authors: Taha Walid , Sheard Tim
Published: November 2005

We introduce MetaML, a statically-typed multi-stage programming language extending Nielson and Nielson's two stage notation to an arbitrary number of stages. MetaML extends previous work by introducing
four
distinct staging annotations which generalize those published previously [25, 12, 7, 6]We give a static semantics in which type checking is done once and for all before the first stage, and a dynamic semantics which introduces a new concept of
cross-stage persistence
, which requires that variables available in any stage are also available in all future stages.We illustrate that staging is a manual form of binding time analysis. We explain why, even in the presence of automatic binding time analysis, explicit annotations are useful, especially for programs with more than two stages.A thesis of this paper is that multi-stage languages are useful as programming languages in their own right, and should support features that make it possible for programmers to write staged computations without significantly changing their normal programming style. To illustrate this we provide a simple three stage example, and an extended two-stage example elaborating a number of practical issues.
Exploring largeness, complexity and scalability from the OOT perspective (panel)
Authors: Rao Bindu Rama , Edwards Chad , Linden Ted , Moore Regan , Seager Mark
Published: November 2005

This panel will lay the foundation for understanding the needs of Large Systems so that OO practitioners can:• appreciate the problems faced;• understand the issues involved; and• re-orient the approaches to provide a viable solution when participating in similar efforts.Specifically, this panel will establish the foundation for discussions on Large Systems by establishing concepts, exposing terminology, and highlighting the state-of-the art.Large applications are usually complex and display one or more of the following dimensions of largeness:•
Processing power
: requiring tens to hundreds of gigabytes of memory and hundreds of gigaflops performance•
High connectivity
: highly-connected, systems can show aggregate behavior with complex characteristics: they can become chaotic.• Online access: Archival of terabytes of information, with the need to provide online access to information•
Archival and online retrieval
: The two technologies (database and archival storage), however, currently do not interoperate. There is a need to develop interfaces to integrate these two technologies.•
Data-intensive scientific applications
: These involve constructing a data handling infrastructure that simplifies the effort required to maintain petabyte archives, identify relevant data sets within the archive, move, the data to processing platforms, and distribute the data sets across multiple nodes.•
Internet access
: Large applications often require simultaneous access of information by millions of users worldwide;they must provide acceptable response times.•
Scaleable architecture
: The systems must be prepared to support exponential growth of application load.Is OOT up to the task? OO practitioners will be encountering some of these application domains in the near future. Some may have already gained some experience in trying to solve these problems. However, the literature in OO does not provide sufficient evidence to believe that OO is ready for such large systems today. Part of the problem is the cross-disciplinary nature of these problems requires a steep learning curve for OO practitioners to be effective. The modeling of these problems with an OO approach is also a challenge. Current 00 methods do not do a good job of supporting multiple views of a domain, and multiple layers of a complex application domain.
The ODMG object model
Authors: Alagic Suad
Published: November 2005

The ODMG Object Model is shown to have a number of problems. A major confusion is caused by the intended type of polymorphism and the way it is expressed in the Model. Dynamic type checking is required even in situations when static type checking is possible. There are situations in which there is no way that type checking can determine whether a particular construct is type correct or not. The model of persistence in the ODMG Standard is not orthogonal, which has undesirable pragmatic consequences on complex objects. The discrepancies between the ODMG Object Model and the particular language bindings of the ODMG Standard are non-trivial. This paper presents solutions to some of these problems together with the associated formal system. Without such a formal system the recommended ODMG bindings are open to a wide range of different, and sometimes confusing interpretations. The criticism expressed in the paper is intended to be helpful in developing future releases of the ODMG Standard.
High performance Fortran for highly irregular problems
Authors: Hu Y. Charlie , Johnsson S. Lennart , Teng Shang-Hua
Published: November 2005

We present a general data parallel formulation for highly irregular problems in High Performance Fortran (HPF). Our formulation consists of(1) a method for linearizing irregular data structures (2) a data parallel implementation (in HPF) of graph partitioning algorithms applied to the linearized data structure, (3) techniques for expressing irregular communication and nonuniform computations associated with the elements of linearized data structures.We demonstrate and evaluate our formulation on a parallel, hierarchical N--body method for the evaluation of potentials and forces of nonuniform particle distributions. Our experimental results demonstrate that efficient data parallel (HPF) implementations of highly nonuniform problems are feasible with the proper language/compiler/runtime support. Our data parallel N--body code provides a much needed "benchmark" code for evaluating and improving HPF compilers.
Space and time efficient execution of parallel irregular computations
Authors: Fu Cong , Yang Tao
Published: November 2005

Solving problems of large sizes is an important goal for parallel machines with multiple CPU and memory resources. In this paper, issues of efficient execution of overhead-sensitive parallel irregular computation under memory constraints are addressed. The irregular parallelism is modeled by task dependence graphs with mixed granularities. The trade-off in achieving both time and space efficiency is investigated. The main difficulty of designing efficient run-time system support is caused by the use of fast communication primitives available on modern parallel architectures. A run-time active memory management scheme and new scheduling techniques are proposed to improve memory utilization while retaining good time efficiency, and a theoretical analysis on correctness and performance is provided. This work is implemented in the context of RAPID system [5] which provides run-time support for parallelizing irregular code on distributed memory machines and the effectiveness of the proposed techniques is verified on sparse Cholesky and LU factorization with partial pivoting. The experimental results on Cray-T3D show that solvable problem sizes can be increased substantially under limited memory capacities and the loss of execution efficiency caused by the extra memory managing overhead is reasonable.
Tradeoffs between false sharing and aggregation in software distributed shared memory
Authors: Amza Cristiana , Cox Alan , Rajamani Karthick , Zwaenepoel Willy
Published: November 2005

Software Distributed Shared Memory (DSM) systems based on virtual memory techniques traditionally use the hardware page as the consistency unit. The large size of the hardware page is considered to be a performance bottleneck because of the implied false sharing overheads. Instead, we show that in the presence of a relaxed consistency model and a multiple writer protocol, a large consistency unit is generally not detrimental to performance. We study the tradeoffs between false sharing and aggregation effects when using large consistency units. In this context, this paper makes three separate contributions:1. We document the cost of false sharing in terms of extra messages and extra data being communicated. We find that, for the applications considered, when the virtual memory page is used as the consistency unit, the number of extra messages is small, while the amount of extra data can be substantial.2. We evaluate the performance when the consistency unit is increased to a multiple of the virtual memory page size. For most applications and data sets, the performance improves, except when the false sharing effects include extra messages or a large amount of extra data.3. We present a new algorithm for dynamically aggregating pages. In our algorithm, the aggregated pages do not necessarily need to be contiguous. In all cases, the performance of our dynamic aggregation algorithm is similar to that achieved with the best static page size.These results were obtained by measuring the performance of eight applications on the TreadMarks distributed shared memory system. The hardware platform used is a network of 166Mhz Pentiums connected by a switched 100Mbps Ethernet network.
Automatic placement of communications in mesh-partitioning parallelization
Authors: Hascoët Laurent
Published: November 2005

We present a tool for mesh-partitioning parallelization of numerical programs working iteratively on an unstructured mesh. This conventional method splits a mesh into sub-meshes, adding some overlap on the boundaries of the sub-meshes. The program is then run in SPMD mode on a parallel architecture with distributed memory. It is necessary to add calls to communication routines at a few carefully selected locations in the code. The tool presented here uses the data-dependence information to mechanize the placement of these synchronizations. Additionally, we see that there is not a unique solution for placing these synchronizations, and performance depends on this choice.