bluuebunny/crossref_metadata_2025 huggingface dataset:
The interaction of parallel programming constructs and coherence protocols
Authors: Bianchini Ricardo , Carrera Enrique V. , Kontothanassis Leonidas
Published: November 2005

Some of the most common parallel programming idioms include locks, barriers, and reduction operations. The interaction of these programming idioms with the multiprocessor's coherence protocol has a significant impact on performance. In addition, the advent of machines that support multiple coherence protocols prompts the question of how to best implement such parallel constructs, i.e. what combination of implementation and coherence protocol yields the best performance. In this paper we study the running time and communication behavior of (1) centralized (ticket) and MCS spin locks, (2) centralized, dissemination, and tree-based barriers, and (3) parallel and sequential reductions, under pure and competitive update coherence protocols; results for write-invalidate protocol are presented mostly for comparison purposes. Our experiments indicate that parallel programming techniques that are well-established for write invalidate protocols, such as MCS locks and parallel reductions, are often inappropriate for update-based protocols. In contrast, techniques such as dissemination and tree barriers achieve superior performance under update-based protocols. Our results also show that the implementation of parallel programming idioms must take the coherence protocol into account, since update-based protocols often lead to different design decisions than write invalidate protocols. Our main conclusion is that protocol-conscious implementation of parallel programming structures can significantly improve application performance; for multiprocessors that can support more than one coherence protocol both the protocol and implementation should betaken into account when exploiting parallel constructs.
Compiling dynamic mappings with array copies
Authors: Coelho Fabien
Published: November 2005

Array remapping are useful to many applications on distributed memory parallel machines. They are available in High Performance Fortran, a Fortran-based data-parallel language. This paper describes techniques to handle dynamic mappings through simple array copies: array remapping are translated into copies between statically mapped distinct versions of the array. It discusses the language restrictions required to do so. The remapping graph which captures all remapping and liveness information is presented, as well as additional data-flow optimizations that can be performed on this graph, so as to avoid useless remapping at run time. Such useless remapping appear for arrays that are not used after a remapping. Live array copies are also kept to avoid other flow-dependent useless remappings. Finally the code generation and runtime required by our scheme are discussed. These techniques are implemented in our prototype HPF compiler.
Compilation of parallel multimedia computations—extending retiming theory and Amdahl's law
Authors: Prasanna G. Srinivasa N.
Published: November 2005

Multimedia applications (also called multimedia systems) operate on datastreams, which are periodic sequences of data elements, called
datasets
. A large class of multimedia applications is described by the macro-dataflow graph model, with nodes representing parallelizable tasks, and arcs representing communication. This paper examines how such multimedia applications can be compiled to run efficiently on parallel machines, by optimizing both throughput (
T
) and latency (
L
), using two techniques, based on task speedup functions. The first step chooses an
appropriate pipeline structure for the system (task clustering)
. The second step exploits the dataset parallelism intrinsic in the periodic datastream, and
runs multiple datasets in parallel (task/cluster multiplicity)
for each clustering. The key find-of this research areA The best task clustering depends on system throughput. In general
skewed
parallelism profiles are desirable i.e. tasks with good speedup and tasks with poor speedup are in separate clusters. Indeed
the maximal throughput and minimal latency can be simultaneously attained
in the limiting case of a maximally skewed distribution. This result can be viewed as a generalization of Amdahl's law for real-time applications.B Optimal dataset multiplicity for a specific clustering can be determined by
extending retiming theory
[1] to include parallel resource allocation. In this process, counter-intuitive relaxation regions often appear, wherein by increasing dataset multiplicity, throughput is increased and latency simultaneously reduced (a free lunch).The techniques have been used for compiling real-time image-processing problems on an NCUBE-2 multiprocessor, and show substantial performance gains.
An effective garbage collection strategy for parallel programming languages on large scale distributed-memory machines
Authors: Taura Kenjiro , Yonezawa Akinori
Published: November 2005

This paper describes the design and implementation of a garbage collection scheme on large-scale distributed-memory computers and reports various experimental results. The collector is based on the conservative GC library by Boehm & Weiser. Each processor traces local pointers using the GC library while traversing remote pointers by exchanging "mark messages" between processors. It exhibits a promising performance---in the most space-intensive settings we tested, the total collection overhead ranges from 5% up to 15% of the application running time (excluding idle time). We not only examine basic performance figures such as the total overhead or latency of a global collection, but also demonstrate how local collection
scheduling
strategies affect application performance. In our collector, a local collection is scheduled either
independently
or
synchronously
. Experimental results show that the benefit of independent local collections has been overstated in the literature. Independent local collections slowed down application performance to 40%, by increasing the average communication latency. Synchronized local collections exhibit much more robust performance characteristics than independent local collections and the overhead for global synchronization is not significant. Furthermore, we show that an adaptive collection scheduler can select the appropriate local collection strategy based on the application's behavior. The collector has been used in a concurrent object-oriented language ABCL/
f
and the performance is measured on a large-scale parallel computer (256 processors) using four non-trivial applications written in ABCL/
f
.
Standardized extensions to Modula-2
Authors: Pronk C. , Sutcliffe R. J. , Schönhacker M. , Wiedemann A.
Published: November 2005

This article will describe a number of extensions to the programming language Modula-2 that are in the process of being standardized by ISO. Modula-2 has been extended by facilities for generic and object oriented programming and by a set of rules to facilitate calling APIs defined in the C language. The first two extensions will be defined in part 2 and 3 of the multi-part Modula-2 standard (of which part 1 describes the base standard). The latter extension will be described in a Technical Report.
Design and static semantics of algorithm language
L
Authors: Jiazhong Zhang , Yanbing Wang , Mingchun Zheng
Published: November 2005

In this paper, an algorithm language L is suggested both as a tool to express algorithm and as a model language for semantic study. The concrete syntax, abstract syntax and static semantics of L are presented at length. The design principle of L is also described, and the comparison with PASCAL is demonstrated by a couple of examples.
64 bit Oberon
Authors: Dotzel Günter , Goebel Hartmut
Published: November 2005

To exploit the 64 bit address space, we migrated ModulaWare's 32 bit Oberon System [DG 96] to OpenVMS Alpha V7.1 [AXP] using very large memory [VLM]. We describe the required language extensions of the Oberon-2 programming language in order to support 64 bit pointers and 64 bit integers. The goal was to keep the number of languages extensions minimal and to disallow any language changes which would break existing code developed for the 32 bit Oberon System. We also summarize the modifications required to get the Oberon System running in the 64 bit address space.
When are two classes equivalent?
Authors: Rangarajan K. , Balasubramaniam A.
Published: November 2005

Software written using an object-oriented programming language is made up of classes, which are compile-time entities and objects, that represent the run-tlme instances of these classes. When the software evolves from one version to another, some of these classes might undergo changes. An important question concerning this evolution is whether the changed class needs to be retested. Research in the area of regression testing has focussed on techniques for optimizing the regression testing effort. We have proposed elsewhere a language-based approach to regression testing that exploits features specific to an object-oriented language to reason about the need to retest an evolved class. The basis for our research is the intuition that when a class can be shown to be equivalent to its original tested version, regression testing may not always be required. We have identified four types of equivalence between a class and its evolved counterpart. In this article, we discuss these equivalence categories and point out their impact on retest effort.
An evaluation of the message-passing interface
Authors: Hansen Per Brinch
Published: November 2005

The Message-Passing Interface (MPI) is evaluated by rewriting message parallel programs for Householder reduction, matrix multiplication, and successive overrelaxation. The author concludes that MPI is a practical programming tool. It does, however, lack the elegance and security that can only be achieved by a parallel programming language.
Concept analysis—a new framework for program understanding
Authors: Snelting Gregor
Published: November 2005

Concept analysis transforms any relation between "objects" and "attributes" into a complete lattice. This concept lattice can be studied by algebraic means and offers remarkable insight into properties and structure of the original relation. As relations between "objects" and "attributes" occur all the time in software technology, concept analysis is an attractive foundation for a new class of program analysis tools. The article presents a short overview of the underlying theory, as well as applications for software component retrieval, analysis of configuration spaces, and modularization of legacy code.
Experiments with combined analysis for pointer aliasing
Authors: Zhang Sean , Ryder Barbara G. , Landi William A.
Published: November 2005

We present initial empirical experiments with
combined analysis
, a scalabk analysis technique that uses a program decomposition to apply different aliasing algorithms to independent program segments. The effectiveness of the solution strategy is validated through application to side-effect and reference analysis of C programs.
OPTVIEW
Authors: Tice Caroline , Graham Susan L.
Published: November 2005

The task of mapping between source programs and machine code, once the code has been optimized and transformed by a compiler is often difficult. Yet there are many instances, such as debugging optimized code or attributing performance analysis data to source lines, whrn it is useful or necessary to understand at the source level what is occurring in the binary. The standard approach has been for tools to attempt to map directly from the optimized binary to the original source. Such mappings are often fragile, and sometimes inaccurate or misleading. We suggest an alternative approach. Rather than mapping directly between the original source and the binary, we create a modified version of the source program, still recognizable, but updated to reflect some of the effects of optimizations, thus facilitating mapping from the binary. We have implemented a tool, Optview, to demonstrate and test these ideas.
Static slicing of threaded programs
Authors: Krinke Jens
Published: November 2005

Static program slicing is an established method for analyzing sequential programs, especially for program understanding, debugging and testing. Until now, there was no slicing method for threaded programs which handles interference correctly. We present such a method which also calculates more precise static slices. This paper extends the well known structures of the control flow graph and the program dependencc graph for threaded programs with interference. This new technique does not require serialization of threaded programs.
Software visualization in the desert environment
Authors: Reiss Steven P.
Published: November 2005

While software visualization has been widely used for navigation, its use for understanding has been much more limited. Software visualizations are expensive to develop, require large amounts of information that is often difficult to collect, and even then, are good only at addressing the specific task for which they were developed. Our work on software visualization in the Desert environment is aimed at making software visualization a viable approach to understanding. We do this by providing ready access to a variety of information about the system at hand, a range of high-quality, high-density visualizations, and a simple interface that lets the programmer rapidly create new software visualizations for understanding problems as they arise. In this paper we describe the approach we have taken.
A lightweight architecture for program execution monitoring
Authors: Jeffery Clinton , Zhou Wenyi , Templer Kevin , Brazell Michael
Published: November 2005

The Alamo monitor architecture reduces the difficulty of writing dynamic analysis tools such as special-purpose profilers, bug-detectors, and visualizations.
Visualizing the performance of higher-order programs
Authors: Waddell Oscar , Ashley J. Michael
Published: November 2005

Profiling can provide the information needed to identify performance bottlenecks in a program, but the programmer must understand its relation to the program source in order to use this information. This is difficult due to the tremendous volume of data collected. Moreover, program transformations such as macro expansion and procedure inlining can obscure the relationship between the source and object code. Higher-order programs present additional challenges due to complex control flow and because they often consist of many small, often anonytnous, procedures whose individual performance properties may be less interesting than their characteristics as a group.To address these challenges we have implemented a profiler and interactive profile visualizer and integrated them into an optimizing Scheme compiler. The profiler instruments target code and maintains correlations with the original source despite compiler optimizations that can eliminate, duplicate, or move code. The visualizer operates as a source-code browser with features to examine execution counts and execution times from several perspectives. It supports the programmer in identifying program hot spots as well as code regions responsible for or affected by those hotspots. It also supports profile differencing which permits the programmer to study program behavior in different execution contexts.Our experience suggests that visualization tools can help to present raw profile data in a meaningful way. The tool can synthesize a high-level picture of program performance while still giving the programmer the ability to explore the details in interesting regions of code.
The implementation and evaluation of fusion and contraction in array languages
Authors: Lewis E. Christopher , Lin Calvin , Snyder Lawrence
Published: November 2005

Array languages such as Fortran 90, HPF and ZPL have many benefits in simplifying array-based computations and expressing data parallelism. However, they can suffer large performance penalties because they introduce intermediate arrays---both at the source level and during the compilation process---which increase memory usage and pollute the cache. Most compilers address this problem by simply scalarizing the array language and relying on a scalar language compiler to perform loop fusion and array contraction. We instead show that there are advantages to performing a form of loop fusion and array contraction
at the array level
. This paper describes this approach and explains its advantages. Experimental results show that our scheme typically yields runtime improvements of greater than 20% and sometimes up to 400%. In addition, it yields superior memory use when compared against commercial compilers and exhibits comparable memory use when compared with scalar languages. We also explore the interaction between these transformations and communication optimizations.
Improving data-flow analysis with path profiles
Authors: Ammons Glenn , Larus James R.
Published: November 2005

Data-flow analysis computes its solutions over the paths in a control-flow graph. These paths---whether feasible or infeasible, heavily or rarely executed---contribute equally to a solution. However, programs execute only a small fraction of their potential paths and, moreover, programs' execution time and cost is concentrated in a far smaller subset of
hot paths
.This paper describes a new approach to analyzing and optimizing programs, which improves the precision of data flow analysis along hot paths. Our technique identifies and duplicates hot paths, creating a
hot path graph
in which these paths are isolated. After flow analysis, the graph is reduced to eliminate unnecessary duplicates of unprofitable paths. In experiments on SPEC95 benchmarks, path qualification identified 2--112 times more non-local constants (weighted dynamically) than the Wegman-Zadek conditional constant algorithm, which translated into 1--7% more dynamic instructions with constant results.
Using static single assignment form to improve flow-insensitive pointer analysis
Authors: Hasti Rebecca , Horwitz Susan
Published: November 2005

A pointer-analysis algorithm can be either flow-sensitive or flow-insensitive. While flow-sensitive analysis usually provides more precise information, it is also usually considerably more costly in terms of time and space. The main contribution of this paper is the presentation of another option in the form of an algorithm that can be 'tuned' to provide a range of results that fall between the results of flow-insensitive and flow-sensitive analysis. The algorithm combines a flow-insensitive pointer analysis with static single assignment (SSA) form and uses an iterative process to obtain progressively better results.
Type-based alias analysis
Authors: Diwan Amer , McKinley Kathryn S. , Moss J. Eliot B.
Published: November 2005

This paper evaluates three alias analyses based on programming language types. The first analysis uses type compatibility to determine aliases. The second extends the first by using additional high-level information such as field names. The third extends the second with a flow-insensitive analysis. Although other researchers suggests using types to disambiguate memory references, none evaluates its effectiveness. We perform both static and dynamic evaluations of type-based alias analyses for Modula-3, a statically-typed type-safe language. The static analysis reveals that type compatibility alone yields a very imprecise alias analysis, but the other two analyses significantly improve alias precision. We use redundant load elimination (RLE) to demonstrate the effectiveness of the three alias algorithms in terms of the opportunities for optimization, the impact on simulated execution times, and to compute an upper bound on what a perfect alias analysis would yield. We show modest dynamic improvements for (RLE), and more surprisingly, that on average our alias analysis is within 2.5% of a perfect alias analysis with respect to RLE on 8 Modula-3 programs. These results illustrate that to explore thoroughly the effectiveness of alias analyses, researchers need static, dynamic, and upper-bound analysis. In addition, we show that for type-safe languages like Modula-3 and Java, a fast and simple alias analysis may be sufficient for many applications.
Quality and speed in linear-scan register allocation
Authors: Traub Omri , Holloway Glenn , Smith Michael D.
Published: November 2005

A
linear-scan
algorithm directs the global allocation of register candidates to registers based on a simple linear sweep over the program being compiled. This approach to register allocation makes sense for systems, such as those for dynamic compilation, where compilation speed is important. In contrast, most commercial and research optimizing compilers rely on a graph-coloring approach to global register allocation. In this paper, we compare the performance of a linear-scan method against a modern graph-coloring method. We implement both register allocators within the Machine SUIF extension of the Stanford SUIF compiler system. Experimental results show that linear scan is much faster than coloring on benchmarks with large numbers of register candidates. We also describe improvements to the linear-scan approach that do not change its linear character, but allow it to produce code of a quality near to that produced by graph coloring.
The implementation of the Cilk-5 multithreaded language
Authors: Frigo Matteo , Leiserson Charles E. , Randall Keith H.
Published: November 2005

The fifth release of the multithreaded language Cilk uses a provably good "work-stealing" scheduling algorithm similar to the first system, but the language has been completely redesigned and the runtime system completely reengineered. The efficiency of the new implementation was aided by a clear strategy that arose from a theoretical analysis of the scheduling algorithm: concentrate on minimizing overheads that contribute to the work, even at the expense of overheads that contribute to the critical path. Although it may seem counterintuitive to move overheads onto the critical path, this "work-first" principle has led to a portable Cilk-5 implementation in which the typical cost of spawning a parallel thread is only between 2 and 6 times the cost of a C function call on a variety of contemporary machines. Many Cilk programs run on one processor with virtually no degradation compared to equivalent C programs. This paper describes how the work-first principle was exploited in the design of Cilk-5's compiler and its runtime system. In particular, we present Cilk-5's novel "two-clone" compilation strategy and its Dijkstra-like mutual-exclusion protocol for implementing the ready deque in the work-stealing scheduler.
Units
Authors: Flatt Matthew , Felleisen Matthias
Published: November 2005

A module system ought to enable
assembly-line programming
using separate compilation and an expressive linking language. Separate compilation allows programmers to develop parts of a program independently. A linking language gives programmers precise control over the assembly of parts into a whole. This paper presents models of
program units
, MzScheme's module language for assembly-line programming. Units support separate compilation, independent module reuse, cyclic dependencies, hierarchical structuring, and dynamic linking. The models explain how to integrate units with untyped and typed languages such as Scheme and ML.
Garbage collection and local variable type-precision and liveness in Java virtual machines
Authors: Agesen Ole , Detlefs David , Moss J. Eliot
Published: November 2005

Full precision in garbage collection implies retaining only those heap allocated objects that will actually be used in the future. Since full precision is not computable in general, garbage collectors use safe (i.e., conservative) approximations such as reachability from a set of root references. Ambiguous roots collectors (commonly called "conservative") can be overly conservative because they overestimate the root set, and thereby retain unexpectedly large amounts of garbage. We consider two more precise collection schemes for Java virtual machines (JVMs). One uses a type analysis to obtain a
type-precise
root set (only those variables that contain references); the other adds a live variable analysis to reduce the root set to only the live reference variables. Even with the Java programming language's strong typing, it turns out that the JVM specification has a feature that makes type-precise root sets difficult to compute. We explain the problem and ways in which it can be solved.Our experimental results include measurements of the costs of the type and liveness analyses at load time, of the incremental benefits at run time of the liveness analysis over the type analysis alone, and of various map sizes and counts. We find that the liveness analysis often produces little or no improvement in heap size, sometimes modest improvements, and occasionally the improvement is dramatic. While further study is in order, we conclude that the main benefit of the liveness analysis is preventing bad surprises.
Scalable cross-module optimization
Authors: Ayers Andrew , de Jong Stuart , Peyton John , Schooler Richard
Published: November 2005

Large applications are typically partitioned into separately compiled modules. Large performance gains in these applications are available by optimizing across module boundaries. One barrier to applying crossmodule optimization (CMO) to large applications is the potentially enormous amount of time and space consumed by the optimization process.We describe a framework for scalable CMO that provides large gains in performance on applications that contain millions of lines of code. Two major techniques are described. First, careful management of in-memory data structures results in sub-linear memory occupancy when compared to the number of lines of code being optimized. Second, profile data is used to focus optimization effort on the performance-critical portions of applications. We also present practical issues that arise in deploying this framework in a production environment. These issues include debuggability and compatibility with existing development tools, such as
make
. Our framework is deployed in Hewlett-Packard's (HP) UNIX compiler products and speeds up shipped independent software vendors' applications by as much as 71%.
Automatically closing open reactive programs
Authors: Colby Christopher , Godefroid Patrice , Jagadeesan Lalita Jategaonkar
Published: November 2005

We study in this paper the problem of analyzing implementations of open systems --- systems in which only some of the components are present. We present an algorithm for automatically closing an open concurrent reactive system with its most general environment, i.e., the environment that can provide any input at any time to the system. The result is a nondeterministic closed (i.e., self-executable) system which can exhibit all the possible reactive behaviors of the original open system. These behaviors can then be analyzed using VeriSoft, an existing tool for systematically exploring the state spaces of closed systems composed of multiple (possibly nondeterministic) processes executing arbitrary code. We have implemented the techniques introduced in this paper in a prototype tool for automatically closing open programs written in the C programming language. We discuss preliminary experimental results obtained with a large telephone-switching software application developed at Lucent Technologies.
Java, the good, the bad and the ugly
Authors: Martin Peter
Published: November 2005

This paper describes some of the experience gained over the last two years in teaching Java to both second level undergraduates in an Object-Oriented Specialism and to first year Computing undergraduates as a first programming language, and also in the use of Java both in student project work and in the development of an industrial strength graphics application involving in excess of 100 K lines of code.These experiences have brought to light a number of good as well as bad features of the language and in addition a number of language features which whilst not bad or dangerous, form an unnecessary barrier to understanding.Finally, the paper draws some conclusions from the lessons learnt regarding the appropriateness of the choice of Java in preference to other candidates such as Smalltalk and C++ in these two domains of application.
Kinds of language, kinds of learning
Authors: Burton Peter
Published: November 2005

The starting- (and finishing-) point for this discussion is a reflection, in general terms, on the question of what
kinds
of learning can take place in a programming course. More specifically, I shall consider the nature of the overall intellectual structure with which learners of Java are confronted. What does it mean for learners to fully "internalise" such a structure in their minds? I shall draw attention to the "anatomy" of this structure, to some of the ways in which it can be dissected, and how such dissections translate into orders of business in a first Java course. My central concern is to argue the merits of making some of the anatomical features explicit to learners, even at an early stage, and even if this entails a detour through extensive sub-Java or non-Java terrains in order to arrive at the promised land.
APL Extended Compared With Other Languages According to Halstead's Theory
Authors: van Batenburg F. H. D. , de Kerf Joseph
Published: November 2005

In a previous paper, Halstead's theory was applied to first generation APL. Those implementations only support simple arrays (APL/SA). In this paper we extend the application of Halstead's theory to second generation APL; the main difference being that those implementations support arrays of arrays or nested arrays (APL/NA). In both investigations, Halstead's theory had to be adjusted in order to account for the fact that in APL operations may be functions or operators. It is shown that the language level increases from 3.07 for APL/SA to 3.62 for APL/NA This means that language efficiency of APL versus assembler raises from about 12 for APL/SA to nearly 17 for APL/NA.
JSpace
Authors: Ledru Parcal
Published: November 2005

This paper describes an implementation of Linda for Java. Several capabilities of Java such as rich typing and object oriented programming are used to provide a powerful model. The implementation provides the functionality of Linda as well as some extensions taking advantages of Java. A short presentation of the Linda model and some examples are also provided.
Object-oriented practice in 1998 (panel)
Authors: Artim John , Bridgeford Charlie , Christman Lillian , Coplien James , Rosson Mary Beth , Taylor Stanley , Wirfs-Brock Rebecca
Published: November 2005

Groups of people working in concert perform most commercial, industrial or in-house software development. These groups are often quite diverse. This panel brings together object-oriented consultants and developers as well as practitioners and researchers interested in human factors and user-centered design, project management and technical writing. The panel will address the question, "To successfully complete today's projects, does object-oriented development as practiced today do an adequate job of supporting ALL of the participants who must collaborate?"
Role model based framework design and integration
Authors: Riehle Dirk , Gross Thomas
Published: November 2005

Today, any large object-oriented software system is built using frameworks. Yet, designing frameworks and defining their interaction with clients remains a difficult task. A primary reason is that today's dominant modeling concept, the class, is not well suited to describe the complexity of object collaborations as it emerges in framework design and integration. We use role modeling to overcome the problems and limitations of class-based modeling. Using role models, the design of a framework and its use by clients can be described succinctly and with much better separation of concerns than with classes. Using role objects, frameworks can be integrated into use-contexts that have not been foreseen by their original designers.
How to preserve the benefits of design patterns
Authors: Agerbo Ellen , Cornils Aino
Published: November 2005

The rapid evolution of Design Patterns has hampered the benefits gained from using Design Patterns. The increase in the number of Design Patterns makes a common vocabulary unmanageable, and the tracing problem obscures the documentation that should be enhanced by using Design Patterns. We present an analysis of Design Patterns that will strongly reduce the number of Fundamental Design Patterns and show how strong language abstractions can solve the tracing problem and thereby enhance the documentation.
A lambda calculus of objects with self-inflicted extension
Authors: Di Gianantonio Pietro , Honsell Furio , Liquori Luigi
Published: November 2005

In this paper we investigate, in the context of
functional prototype-based languages
, objects which might extend themselves upon receiving a message. The possibility for an object of extending its own "self", referred to by Cardelli, as a
self-inflicted
operation, is novel in the context of typed object-based languages. We present a sound type system for this calculus which guarantees that evaluating a well-typed expression will never yield a message-not-found run-time error. We give several examples which illustrate the increased expressive power of our system with respect to existing calculi of objects. The new type system allows also for a flexible
width-subtyping
, still permitting sound method override, and a limited form of object extension. The resulting calculus appears to be a good starting point for a rigorous mathematical analysis of class-based languages.
Parametric polymorphism for Java
Authors: Solorzano Jose H. , Alagić Suad
Published: November 2005

A number of inadequacies of existing implementation techniques for extending Java™ with parametric polymorphism are revealed. Homogeneous translations are the most space-efficient but they are not compatible with reflection, some models of persistence, and multiple dispatch. Heterogeneous translations, on the other hand, can potentially produce large amounts of redundant information. Implementation techniques that address these concerns are developed. In languages that support run-time reflection, an adequate implementation of parametric, bounded and F-bounded polymorphism is shown to require (reflective) run-time support. In Java, extensions to the core classes are needed. This is in spite of the fact that parametric polymorphism is intended to be managed
statically
.
System support for object groups
Authors: Guerraoui Rachid , Felber Pascal , Garbinato Benoît , Mazouni Karim
Published: November 2005

This paper draws several observations from our experiences in building support for object groups. These observations actually go beyond our experiences and may apply to many other developments of object based distributed systems.Our first experience aimed at building support for Smalltalk object replication using the Isis process group toolkit. It was quite easy to achieve group transparency but we were confronted with a strong mismatch between the rigidity of the process group model and the flexible nature of object interactions. Consequently, we decided to build our own object oriented protocol framework, specifically dedicated to support object groups (instead of using a process group toolkit). We built our framework in such a way that basic distributed protocols, such as failure detection and multicasts, are considered as first class entities, directly accessible to the programmers. To achieve flexible and dynamic protocol composition, we had to go beyond inheritance and objectify distributed algorithms.Our second experience consisted in building a CORBA service aimed at managing group of objects written on different languages and running on different platforms. This experience revealed a mismatch between the asynchrony of group protocols and the synchrony of standard CORBA interaction mechanisms, which limited the portability of our CORBA object group service. We restricted the impact of this mismatch by encapsulating asynchrony issues inside a specific messaging sub-service.We dissect the cost of object group transparency in our various implementations, and we point out the recurrent sources of overheads, namely message indirection, marshaling/unmarshaling and strong consistency.
Extending the ODMG object model with composite objects
Authors: Bertino Elisa , Guerrini Giovanna
Published: November 2005

In this paper we extend the ODMG object data model with composite objects. A composite object is an object built by aggregating other component objects. Exclusiveness and dependency constraints, as well as referential integrity, can be associated with composition relationships among objects. Our composite object model is developed in the framework of the ODMG object database standard data model, but can be used in both object-oriented and object-relational database systems. In the paper, we propose a language for defining composite objects and we define the semantics of update operations on composite objects.
Lightweight object-oriented shared variables for distributed applications on the Internet
Authors: Harris Jacob , Sarkar Vivek
Published: November 2005

This paper describes a lightweight yet powerful approach for writing distributed applications using shared variables. Our approach, called S
HARE
H
OLDER
, is inspired by the flexible and intuitive model of information access common to the World Wide Web. The distributed applications targeted by our approach all share a weak consistency model and loose transaction semantics, similar to a user's model of accessing email, bulletin boards, chat rooms, etc. on the Internet. The S
HARE
H
OLDER
infrastructure has several advantages. Its highly object-oriented view of shared variables simplifies their initialization and configuration. A shared variable's distribution mechanism is specified through an associated configuration object, and the programmer does not need to write any extra code to implement the sharing mechanism. These configuration objects can be initialized at run-time, allowing tremendous flexibility in dynamic control of distribution of shared variables. Finally, the programmer can treat shared variables and local variables interchangeably, thus simplifying conversion of a serial application into a distributed application.
A type system for object initialization in the Java bytecode language
Authors: Freund Stephen N. , Mitchell John C.
Published: November 2005

In the standard Java implementation, a Java language program is compiled to Java bytecode. This bytecode may be sent across the network to another site, where it is then interpreted by the Java Virtual Machine. Since bytecode may be written by hand, or corrupted during network transmission, the Java Virtual Machine contains a
bytecode verifier
that performs a number of consistency checks before code is interpreted. As illustrated by previous attacks on the Java Virtual Machine, these tests, which include type correctness, are critical for system security. In order to analyze existing bytecode verifiers and to understand the properties that should be verified, we develop a precise specification of
statically-correct
Java bytecode, in the form of a type system. Our focus in this paper is a subset of the bytecode language dealing with object creation and initialization. For this subset, we prove that for every Java bytecode program that satisfies our typing constraints, every object is initialized before it is used. The type system is easily combined with a previous system developed by Stata and Abadi for bytecode subroutines. Our analysis of subroutines and object initialization reveals a previously unpublished bug in the Sun JDK bytecode verifier.
Reasoning about Java classes
Authors: Jacobs Bart , van den Berg Joachim , Huisman Marieke , van Berkum Martijn , Hensel U. , Tews H.
Published: November 2005

We present the first results of a project called LOOP, on formal methods for the object-oriented language Java. It aims at verification of program properties, with support of modern tools. We use our own front-end tool (which is still partly under construction) for translating Java classes into higher order logic, and a back-end theorem prover (namely PVS, developed at SRI) for reasoning. In several examples we demonstrate how non-trivial properties of Java programs and classes can be proven following this two-step approach.
What is Java binary compatibility?
Authors: Drossopoulou Sophia , Wragg David , Eisenbach Susan
Published: November 2005

Separate compilation allows the decomposition of programs into units that may be compiled separately, and linked into an executable. Traditionally, separate compilation was equivalent to the compilation of all units together, and modification and re-compilation of one unit required re-compilation of all importing units.Java suggests a more flexible framework, in which the linker checks the integrity of the binaries to be combined. Certain source code modifications, such as addition of methods to classes, are defined as
binary compatible
. The language description guarantees that binaries of types (
i.e
. classes or interfaces) modified in binary compatible ways may be re-compiled and linked with the binaries of types that imported and were compiled using the earlier versions of the modified types.However, this is not always the case: some of the changes considered by Java as binary compatible do
not
guarantee successful linking and execution. In this paper we study the concepts around binary compatibility. We suggest a formalization of the requirement of safe linking and execution without re-compilation, investigate alternatives, demonstrate several of its properties, and propose a more restricted definition of binary compatible changes. Finally, we prove for a substantial subset of Java, that this restricted definition guarantees error-free linking and execution.
Deleting the rightmost bottommost leaf of a heap
Authors: Lewit Alan F.
Published: November 2005

I am presently teaching a sophomore level course in Data Structures and I am using an excellent text by Thomas A. Standish. In a section entitled
An Application - Heaps and Priority Queues
, a strategy is offered for fetching the value of the highest priority item at the root of a tree and replacing the roots value with the value of the
rightmost leaf on the bottom row
. After the value of this rightmost leaf is obtained and placed in the root, that node is deleted.
Internet-based learning
Authors: Storck Byron
Published: November 2005

My involvement in the development of Internet-based learning activities began in April of 1996 when I was asked to prepare a document briefly listing the types of Internet applications I would use in LaGuardia Community College's
Topics in Astronomy
course. Our College was fortunate to participate in a five-year NASA-MUSPIN (National Aeronautics and Space Administration [

NASA

]

M

inority

U

niversity-

S

pace

I

nterdisciplinary

N

etwork) grant that provided LaGuardia with a 100 Mbps fiber optic backbone connection to the Internet. As a result, we were required to provide examples of how we planned to involve students and faculty in the development and use of Internet applications.
Experiences in building C++ front end
Authors: Yang Fuqing , Mei Hong , Yuan Wanghong , Wu Qiong , Guo Yao
Published: November 2005

It is difficult, if not impossible, for the code analyzers to employ front end from compilers, because these front ends extract different program information using different strategy. This paper describes our experiences in building C++ front end as a part of code analysis toolset. The front end customizes the lexical analyzer incorporating a special preprocessing technique to accurately associate program entities with physical source code location. To support analysis of different C++ languages, the front end employs YACC to generate the parser, and uses token lookahead technique to disambiguate C++ grammar for YACC.
The design and implementation of the GILENA natural language interfaces specification system
Authors: Atkinson-Abutridy John A. , Ferreira-Cabrera Anita A.
Published: November 2005

This paper considers a finite-state parsing algorithm for implementing natural language interfaces. The algorithm has some practical improvements compared to other recognizing algorithms. Resolution of syntax ambiguity, programming facilities and post execution of semantic actions are discussed too.Our approach was implemented in order to design the GILENA software tool which automatically allows to generate natural language interfaces. In addition, our designed algorithm, its implementation and its results are discussed.
Compiler-controlled memory
Authors: Cooper Keith D. , Harvey Timothy J.
Published: November 2005

Optimizations aimed at reducing the impact of memory operations on execution speed have long concentrated on improving cache performance. These efforts achieve a. reasonable level of success. The primary limit on the compiler's ability to improve memory behavior is its imperfect knowledge about the run-time behavior of the program. The compiler cannot completely predict runtime access patterns.There is an exception to this rule. During the register allocation phase, the compiler often must insert substantial amounts of
spill code
; that is, instructions that move values from registers to memory and back again. Because the compiler itself inserts these memory instructions, it has more knowledge about them than other memory operations in the program.Spill-code operations are disjoint from the memory manipulations required by the semantics of the program being compiled, and, indeed, the two can interfere in the cache. This paper proposes a hardware solution to the problem of increased spill costs---a small
compiler-controlled memory
(CCM) to hold spilled values. This small random-access memory can (and should) be placed in a distinct address space from the main memory hierarchy. The compiler can target spill instructions to use the CCM, moving most compiler-inserted memory traffic out of the pathway to main memory and eliminating any impact that those spill instructions would have on the state of the main memory hierarchy. Such memories already exist on some DSP microprocessors. Our techniques can be applied directly on those chips.This paper presents two compiler-based methods to exploit such a memory, along with experimental results showing that speedups from using CCM may be sizable. It shows that using the register allocation's coloring paradigm to assign spilled values to memory can greatly reduce the amount of memory required by a program.
Space-time scheduling of instruction-level parallelism on a raw machine
Authors: Lee Walter , Barua Rajeev , Frank Matthew , Srikrishna Devabhaktuni , Babb Jonathan , Sarkar Vivek , Amarasinghe Saman
Published: November 2005

Increasing demand for both greater parallelism and faster clocks dictate that future generation architectures will need to decentralize their resources and eliminate primitives that require single cycle global communication. A Raw microprocessor distributes all of its resources, including instruction streams, register files, memory ports, and ALUs, over a pipelined two-dimensional mesh interconnect, and exposes them fully to the compiler. Because communication in Raw machines is distributed, compiling for instruction-level parallelism (ILP) requires both spatial instruction partitioning as well as traditional temporal instruction scheduling. In addition, the compiler must explicitly manage all communication through the interconnect, including the global synchronization required at branch points. This paper describes RAWCC, the compiler we have developed for compiling general-purpose sequential programs to the distributed Raw architecture. We present performance results that demonstrate that although Raw machines provide no mechanisms for global communication the Raw compiler can schedule to achieve speedups that scale with the number of available functional units.