bluuebunny/crossref_metadata_2025 huggingface dataset:
Debugging in a side effect free programming environment
Authors: Hall Cordelia V. , O'Donnell John T.
Published: November 2005

Lisp and its successors provide the programmer with a powerful single tool [2] in which he can write, modify, debug and execute programs. Side effects play a crucial role in these programming environments. We propose an alternative approach to debugging that doesn't rely on side effects. Then we describe an implementation of our approach in a purely functional language.
A new notion of encapsulation
Authors: Gries David , Prins Jan
Published: November 2005

Generally speaking, a “module” is used as an “encapsulation mechanism” to tie together a set of declarations of variables and operations upon them. Although there is no standard way to instantiate or use a module, the general idea is that a module describes the implementation of all the values of a given type. We believe that this is too inflexible to provide enough control:

one should be able to use different implementations (given by different modules) for variables (and values) of the same type.

When incorporated properly into the notation, this finer grain of control allows one to program at a high level of abstraction and then to indicate how various pieces of the program should be implemented. It provides simple, effective access to earlier-written modules, so that they are useable in a more flexible manner than is possible in current notations. It generalizes to provide the ability to indicate structural transformations, in a disciplined fashion, in order to achieve efficiency with respect to time or space. However, the program will still be understood at the abstract level and the transformations or implementations will be looked at only to deal with efficiency concerns. Finally, some so-called “data types” (e.g.
stack
and subranges of the integers) can more properly be looked upon simply as restricted implementations of more general types (e.g.
sequence
and
integer
). Thus, the notion of subtype becomes less important.
PegaSys
Authors: Moriconi Mark , Hare Dwight F.
Published: November 2005

This paper is an initial report on a system, called PegaSys, that supports a new visual paradigm for describing and manipulating programs and their designs. A program design is described by a hierarchically structured collection of graphical pictures. These pictures are intended to be easy to understand, yet still serve as formal program documentation. Pictures in PegaSys capture a variety of concepts, including (but not limited to) what we believe to be the important design concepts represented in flowcharts, structure charts, dataflow diagrams, and module interconnection languages. PegaSys treats pictures as computationally meaningful structures, checking whether they make sense syntactically, whether hierarchical picture refinements adhere to certain methodological principles, and whether a picture is logically consistent with a program. This paper describes the key ideas that enable PegaSys to provide these capabilities, as well as important properties of the PegaSys design and underlying logical framework. PegaSys has been implemented on Xerox personal computers and takes advantage of a high-resolution bitmap display.
Efficient abstractions for the implementation of structured editors
Authors: Hood Robert
Published: November 2005

This paper investigates the use of abstract recursive data structures and operations in the implementation of a structured program editor. The value-oriented semantics of the proposed constructs simplify the implementation of important features such as version control and an unbounded
undo
operation. Since the constructs can be implemented efficiently, their use in the structured program editor does not significantly affect its performance.
An environment for logic programming
Authors: Francez Nissim , Goldenberg Shalom , Pinter Ron Y. , Tiomkin Michael , Tsur Shalom
Published: November 2005

We describe a programming environment for Prolog, a common logic programming language. The services offered by our system assist a Prolog user in the tasks of composing, editing, and storing logic (rule-based) programs, as well as in the control of their execution for debugging purposes.

In order to facilitate effective debugging of Prolog programs, we propose a new
model of computation
that can handle both pure Prolog and impure (side-effect causing) Prolog operations quite gracefully. This model employs two stacks representing the state of a computation with respect to the two major activities of Prolog execution: recursion and backtracking. This representation, in addition to being quite clear and intuitive, is easy to display on a terminal's screen and can be further processed.

We also describe a
Prolog oriented editor
with which the user may easily create and update Prolog source programs and, further, inspect states of computation as generated by the debugger.
Design issues in a Rule-Based System
Authors: Fickas Stephen
Published: November 2005

This paper discusses a language and associated environment for building rule-based programs. The language and environment are encapsulated in a system we call ORBS (Oregon Rule Based System). In tune with this conference, our focus will be on the interplay between language and environment design. However, we will broaden this somewhat to include design constraints placed by our program development model
1
as well. Instead of attempting a complete design rationalization of ORBS, we will concentrate on design decisions that highlight the coupling between language, environment, and development model.

ORBS falls in the class of rule-based systems that often is categorized as forward-chaining or data-driven. Other systems in this category include OPS5 [9], YAPS [2], and all of the Hearsay family [5, 11, 15]. What is often taken as the inverse of this set are the backward-chaining or goal-directed languages such as EMYCIN [17]. Arguments for and against the forward and backward approaches have been made many times elsewhere (see [12] for examples of each), and we will not address the issue further in this paper.
2
While we believe that many of the arguments we make for the design of ORBS are applicable to rule-based systems in general, any reference to the term
rule-based
should be taken in light of the classification above.
Extending PowerEpsilon with algebraic rewriting
Authors: Zeng Li-Xin , Zhu Ming-Yuan
Published: November 2005

PowerEpsilon ([ZhuW9l]) is a strongly-typed polymorphic functional programming language based on Martin-Löf's type theory and the Calculus of Constructions. In PowerEpsilon there are no constant time definitions of the predecessor functions which will lead to non-efficient programs. In this paper, we give a solution to this problem by introducing an algebraic rewriting mechanism into the system.
Program profiling problems, and a solution via machine language rewriting
Authors: Reiser John F. , Skudlarek Joseph P.
Published: November 2005

The executable binary image of a program can be mechanically rewritten to produce a second program that collects execution statistics as a side effect, while executing the same routines and producing the same primary outputs as the original program. We describe a general technique and present our experiences with several alternate profiling mechanisms. The challenges of presenting the profile information in easily-used. understandable ways are also discussed.
Uniprep—preparing a C/C++ compiler for Unicode
Authors: Dürst Martin J.
Published: November 2005

A new way to ease the transition of programs and programmers to multilingual 16-bit character sets is presented. A filter, called uniprep, is inserted between the C/C++ macro preprocessor and the compiler itself. It substitutes wide-character constants and strings by appropriately converted and casted traditional constants.
Parallel multiplication
Authors: Yuen C. K. , Feng M. D.
Published: November 2005

Six versions of a parallel program for multiplication are presented, and compared in terms of their efficiencies. They illustrate the bottom up and top down methods of program structure design, and the use of tuplespace and speculative processing in parallel programming. The ideas are also applicable to general AND/OR parallel problems.
A general, fine-grained, machine independent, object-oriented language
Authors: Andersen Birger
Published: November 2005

This paper introduces the general-purpose object-oriented programming language Ellie which supports machine independent fine-grained objects and parallelism. As something particular, classes, types, blocks, and methods are abstracted by first class objects/citizens called Ellie objects. Ellie demonstrates new approaches for abstraction and code reuse in parallel programming.The goals of Ellie have been to obtain an extremely flexible, machine independent, parallel language. Ellie tries to meet these goals by extensive usage of selected language concepts combined with compile-time analysis to adapt programs for efficient execution on the available hardware. Ellie runs on a parallel mesh transputer network.
A “linear logic” Quicksort
Authors: Baker Henry G.
Published: November 2005

The
linear
style of programming inspired by
linear logic
has been proposed to reduce garbage collection and synchronization costs in serial and parallel systems. We programmed Quicksort for both lists and arrays in a "linear" fragment of Lisp to estimate the performance impact of linearity on a serial machine. Even though Quicksort is well-tuned for current non-linear architectures, we find that linearity extracts no real penalty. Our "linear" list Quicksort is as fast as any non-linear list Quicksort, and our "linear" vector Quicksort is only 3.5% slower than a non-linear vector Quicksort. The linear style is moderately pleasant, and the redundancy of linearity checking can aid in finding bugs.
Does Scheme enhance an introductory programming course?
Authors: Berman A. Michael
Published: November 2005

There is no consensus within the Computer Science community as to which programming language or languages ought to be used in introductory courses. In recent years a substantial contingent has proposed the use of Scheme, a dialect of Lisp, as a candidate for "Best First Language"; however, despite the articles touting success with this approach, there have been no empirical studies comparing the results of using Scheme versus other languages. This paper is a first step towards collecting data that might answer this question. We compare two pre-major courses at a four-year college, one taught using a structured version of Basic, the other taught using Scheme. A survey was used to compare student attitudes towards computer science and programming at the end of the course. While the survey was too small to provide statistically significant answers, there were indications that Scheme may in fact do a better job of capturing and holding students' interest in Computer Science.
Bug analysis of Pascal programs
Authors: Anjaneyulu K. S. R.
Published: November 2005

The paper first looks at issues related to the teaching of programming. Solutions to two programming problems written by participants new to the Pascal programming language are analyzed. The types of bugs which were detected in these programs are then described. Results of such analyses could perhaps help in improving the way programming is taught.
Thermodynamics and garbage collection
Authors: Baker Henry G.
Published: November 2005

We discuss the principles of statistical thermodynamics and their application to storage management problems. We point out problems which result from impercise usage of the terms
information, state, reversible, conservative
, etc.
Polymorphism and subtyping in interface
Authors: Katiyar Dinesh , Luckham David , Mitchell John
Published: November 2005

RAPIDE is a programming language framework designed for the development of large, concurrent, real-time systems by prototyping. The framework consists of a type language and default executable, specification and architecture languages, along with associated programming tools.
Interfaces
are the central construct of the type system. This document describes RAPIDE interfaces, their expressiveness and their use as a typing construct.
Interface language for supporting programming styles
Authors: Tan Yang Meng
Published: November 2005

We suggest a novel application of a formal specification language: we use it to support some programming conventions and encourage certain styles of programming. The Larch/C Interface Language (LCL) is a language for documenting the interfaces of ANSI C programs. It is designed to support a style of c programming where a program is organized around a set of software modules. Even though C does not support abstract data types, LCL supports the specifications of abstract data types, and provides guidelines on how abstract types can be implemented in C. A
lint
-like program checks for some conformance of C code to its LCL specification.
Interfaces and extended ML
Authors: Kahrs Stefan , Sannella Donald , Tarlecki Andrzej
Published: November 2005

This is a position paper giving our views on the uses and makeup of module interfaces. The position espoused is inspired by our work on the Extended ML (EML) formal software development framework and by ideas in the algebraic foundations of specification and formal development. The present state of interfaces in EML is outlined and set in the context of plans for a more general EML-like framework with axioms in interfaces taken from an arbitrary logical system formulated as an
institution
. Some more speculative plans are sketched concerning the simultaneous use of multiple institutions in specification and development.
Genericity versus inheritance reconsidered
Authors: Seidewitz Ed
Published: November 2005

As shown by the work of Bertrand Meyer, it is possible to simulate genericity using inheritance, but not vice-versa. This is because genericity is a parameterization mechanism with no way to deal with the polymorphic typing introduced using inheritance. Nevertheless, if we focus on the use of inheritance as an implementation technique, its key feature is the dynamic binding of self-referential operation calls. This turns out to be basically a parameterization mechanism that can in fact be simulated using generics and static binding. And for some applications this approach may actually be of more than academic interest.
Proposal for a monotonic multiple inheritance linearization
Authors: Ducournau R. , Habib M. , Huchard M. , Mugnier M. L.
Published: November 2005

Previous studies concerning multiple inheritance convinced us that a better analysis of conflict resolution mechanisms was necessary. In [DHHM92], we stated properties that a sound mechanism has to respect. Among them, a monotonicity principle plays a critical role, ensuring that the inheritance mechanism behaves “naturally” relative to the incremental design of the inheritance hierarchy. We focus here on linearizations and present an intrinsically monotonic linearization, whereas currently used linearizations are not. This paper describes the algorithm in detail, explains the design choices, and compares it to other linearizations, with LOOPS and CLOS taken as references. In particular, this new linearization extends CLOS and LOOPS linearizations, producing the same results when these linearizations are sound.
MI—an object oriented environment for integration of scientific applications
Authors: Spinelli Andrea , Salvaneschi Paolo , Cadei Mauro , Rocca Marino
Published: November 2005

Scientific and engineering software is often produced by integration of existing software components of the size of a whole program. However, on the average, scientific software was not developed for reusability and is quite distant from the user model of the application problem; integration and retrofitting is as such a costly process. An architecture, methodology and several C++ class libraries for supporting integration are introduced. The architecture separates a software component layer, and an integration layer. The latter in based on the concept of software model, that is an abstraction of components and a representation of the system differing from its actual physical structure. The methodology is based on matching needs with existing models. The C++ class libraries are explained in some detail. The application to two major systems is analysed and the ideas behind seven other systems are briefly outlined. Some lessons learned are summarised in the conclusions.
Optimizing multi-method dispatch using compressed dispatch tables
Authors: Amiel Eric , Gruber Olivier , Simon Eric
Published: November 2005

Optimizing method dispatch is a central issue in object-oriented language implementation. The
dispatch table
scheme, used for example by C++, is the only implementation of method dispatch that offers
constant time
performance. This property is the main asset of dispatch tables and a major requirement for some languages. However, the major drawback of dispatch tables is the space they require. Reducing the size of dispatch tables has been studied in the case of mono-methods with techniques such as
coloring
. In the case of multi-methods, dispatch tables are practically unusable as they grow as a power of the number of arguments. In this paper, we propose an algorithm to compress the dispatch tables of multi-methods by analyzing their signatures.
Implementing constraint imperative programming languages
Authors: Lopez Gus , Freeman-Benson Bjorn , Borning Alan
Published: November 2005

Constraint Imperative Programming (CIP) languages integrate declarative constraints with imperative state and destructive assignment, yielding a powerful new programming paradigm. However, CIP languages are difficult to implement efficiently due to complex interactions between the two donor paradigms. Neither the virtual machines for classical object-oriented languages, nor those for existing constraint languages, are suitable for implementing CIP languages, as each assumes a purely imperative or a purely declarative computation model. We have developed a new virtual machine for CIP languages, the K-machine, an imperative machine with an incremental constraint solver and a constraint-based, rather than value-based, data store. This virtual machine allows user-defined constraints to be defined using constraint constructor definitions which are the CIP analog to method definitions. Similar to methods, these constructors are able to reference variables indirectly through many levels of pointers. The K-machine maintains relations between objects in the presence of state change to these indirectly referenced objects. The K-machine is capable of supporting a wide variety of CIP languages, including our most recent: Kaleidoscope'93.
Development of distributed and client/server object-oriented applications
Authors: Heuser Lutz , Dilley John , Madduri Hari , Rabin Steven , Woods Shawn
Published: November 2005

The panel will discuss emerging “industrial” solutions that help programmers to develop distributed and client/server applications based on objects supporting so-called openness and heterogeneity.

The goal of the panel is to help answer the question whether there can be one single solution or whether various (integrated) approaches are needed. The panel will also compare industrial solutions such as COM, DSOM, CORBA and OODCE with results that came out of academia. Finally, a set of questions will be answered by each panelist according to the approach he will propose.
Precise concrete type inference for object-oriented languages
Authors: Plevyak John , Chien Andrew A.
Published: November 2005

Concrete type information is invaluable for program optimization. The determination of concrete types in object-oriented languages is a flow sensitive global data flow problem. It is made difficult by dynamic dispatch (virtual function invocation) and first class functions (and selectors)—the very program structures for whose optimization its results are most critical. Previous work has shown that constraint-based type inference systems can be used to safely approximate concrete types [15], but their use can be expensive and their results imprecise.

We present an incremental constraint-based type inference which produces precise concrete type information for a much larger class of programs at lower cost. Our algorithm extends the analysis in response to discovered imprecisions, guiding the analysis' effort to where it is most productive. This produces precise information at a cost proportional to the type complexity of the program. Many programs untypable by previous approaches or practically untypable due to computational expense, can be precisely analyzed by our new algorithm. Performance results, precision, and running time, are reported for a number of concurrent object-oriented programs. These results confirm the algorithm's precision and efficiency.
Composition of before/after metaclasses in SOM
Authors: Forman Ira R. , Danforth Scott , Madduri Hari
Published: November 2005

In SOM, the IBM System Object Model, a class is a run-time object that defines the behavior of its instances by creating an instance method table. Because classes are objects, their behavior is defined by other classes (called metaclasses). For example, a “Before/After Metaclass” can be used to define the implementation of classes that, by suitable construction of their instance method tables, arrange for each invocation of a method to be preceded by execution of a “before method” and followed by execution of an “after method”. This paper introduces and solves the problem of composing different Before/After Metaclasses in the context of SOM. An enabling element in the solution is SOM's concept of
derived metaclasses
, i.e., at run-time a SOM system derives the appropriate metaclass of a class based on the classes of its parents and an optional metaclass constraint.
Reflections on metaclass programming in SOM
Authors: Danforth Scott , Forman Ira R.
Published: November 2005

This paper reports on the evolution of metaclass programming in SOM (the IBM System Object Model). Initially, SOM's use of explicit metaclasses introduced metaclass incompatibilities. This was cured by having SOM dynamically derive an appropriate metaclass by interpreting the “metaclass declaration” as a constraint. In effect, inheritance is given a new dimension, because the constraint is also inherited. The derived metaclass is the least solution to all these constraints. Subsequently, this cure led to the possibility of metaclasses conflicting over the need to assign meaning to a method. The cure for this problem is a framework that facilitates the programming of metaclasses that cooperate on the assignment of meaning to methods.
Reactive synchronization algorithms for multiprocessors
Authors: Lim Beng-Hong , Agarwal Anant
Published: November 2005

Synchronization algorithms that are efficient across a wide range of applications and operating conditions are hard to design because their performance depends on unpredictable run-time factors. The designer of a synchronization algorithm has a choice of
protocols
to use for implementing the synchronization operation. For example, candidate protocols for locks include test-and-set protocols and queueing protocols. Frequently, the best choice of protocols depends on the level of contention: previous research has shown that test-and-set protocols for locks outperform queueing protocols at low contention, while the opposite is true at high contention.

This paper investigates reactive synchronization algorithms that dynamically choose protocols in response to the level of contention. We describe reactive algorithms for spin locks and fetch-and-op that choose among several shared-memory and message-passing protocols. Dynamically choosing protocols presents a challenge: a reactive algorithm needs to select and change protocols efficiently, and has to allow for the possibility that multiple processes may be executing different protocols at the same time. We describe the notion of
consensus objects
that the reactive algorithms use to preserve correctness in the face of dynamic protocol changes.

Experimental measurements demonstrate that reactive algorithms perform close to the
best
static choice of protocols at all levels of contention. Furthermore, with mixed levels of contention, reactive algorithms outperform passive algorithms with fixed protocols, provided that contention levels do not change too frequently. Measurements of several parallel applications show that reactive algorithms result in modest performance gains for spin locks and significant gains for fetch-and-op.
Resource allocation in a high clock rate microprocessor
Authors: Upton Michael , Huff Thomas , Mudge Trevor , Brown Richard
Published: November 2005

This paper discusses the design of a high clock rate (300MHz) processor. The architecture is described, and the goals for the design are explained. The performance of three processor models is evaluated using trace-driven simulation. A cost model is used to estimate the resources required to build processors with varying sizes of on-chip memories, in both single and dual issue models. Recommendations are then made to increase the effectiveness of each of the models.
Contrasting characteristics and cache performance of technical and multi-user commercial workloads
Authors: Maynard Ann Marie Grizzaffi , Donnelly Colette M. , Olszewski Bret R.
Published: November 2005

Experience has shown that many widely used benchmarks are poor predictors of the performance of systems running commercial applications. Research into this anomaly has long been hampered by a lack of address traces from representative multi-user commercial workloads. This paper presents research, using traces of industry-standard commercial benchmarks, which examines the characteristic differences between technical and commercial workloads and illustrates how those differences affect cache performance.

Commercial and technical environments differ in their respective branch behavior, operating system activity, I/O, and dispatching characteristics. A wide range of uniprocessor instruction and data cache geometries were studied. The instruction cache results for commercial workloads demonstrate that instruction cache performance can no longer be neglected because these workloads have much larger code working sets than technical applications. For database workloads, a breakdown of kernel and user behavior reveals that the application component can exhibit behavior similar to the operating system and therefore, can experience miss rates equally high. This paper also indicates that “dispatching” or process switching characteristics must be considered when designing level-two caches. The data presented shows that increasing the associativity of second-level caches can reduce miss rates significantly. Overall, the results of this research should help system designers choose a cache configuration that will perform well in commercial markets.
The performance advantages of integrating block data transfer in cache-coherent multiprocessors
Authors: Woo Steven Cameron , Singh Jaswinder Pal , Hennessy John L.
Published: November 2005

Integrating support for block data transfer has become an important emphasis in recent cache-coherent shared address space multiprocessors. This paper examines the potential performance benefits of adding this support. A set of ambitious hardware mechanisms is used to study performance gains in five important scientific computations that appear to be good candidates for using block transfer. Our conclusion is that the benefits of block transfer are not substantial for hardware cache-coherent multiprocessors. The main reasons for this are (i) the relatively modest fraction of time applications spend in communication amenable to block transfer, (ii) the difficulty of finding enough independent computation to overlap with the communication latency that remains after block transfer, and (iii) long cache lines often capture many of the benefits of block transfer in efficient cache-coherent machines. In the cases where block transfer improves performance, prefetching can often provide comparable, if not superior, performance benefits. We also examine the impact of varying important communication parameters and processor speed on the effectiveness of block transfer, and comment on useful features that a block transfer facility should support for real applications.
Reducing branch costs via branch alignment
Authors: Calder Brad , Grunwald Dirk
Published: November 2005

Several researchers have proposed algorithms for basic block reordering. We call these
branch alignment
algorithms. The primary emphasis of these algorithms has been on improving instruction cache locality, and the few studies concerned with branch prediction reported small or minimal improvements. As wide-issue architectures become increasingly popular the importance of reducing branch costs will increase, and branch alignment is one mechanism which can effectively reduce these costs.

In this paper, we propose an improved branch alignment algorithm that takes into consideration the architectural cost model and the branch prediction architecture when performing the basic block reordering. We show that branch alignment algorithms can improve a broad range of static and dynamic branch prediction architectures. We also show that a program performance can be improved by approximately 5% even when using recently proposed, highly accurate branch prediction architectures. The programs are compiled by any existing compiler and then transformed via binary transformations. When implementing these algorithms on a Alpha AXP 21604 up to a 16% reduction in total execution time is achieved.
Compiler optimizations for improving data locality
Authors: Carr Steve , McKinley Kathryn S. , Tseng Chau-Wen
Published: November 2005

In the past decade, processor speed has become significantly faster than memory speed. Small, fast cache memories are designed to overcome this discrepancy, but they are only effective when programs exhibit
data locality
. In this paper, we present compiler optimizations to improve data locality based on a simple yet accurate cost model. The model computes both
temporal
and
spatial
reuse of cache lines to find desirable loop organizations. The cost model drives the application of compound transformations consisting of loop permutation, loop fusion, loop distribution, and loop reversal. We demonstrate that these program transformations are useful for optimizing many programs.

To validate our optimization strategy, we implemented our algorithms and ran experiments on a large collection of scientific programs and kernels. Experiments with kernels illustrate that our model and algorithm can select and achieve the best performance. For over thirty complete applications, we executed the original and transformed versions and simulated cache hit rates. We collected statistics about the inherent characteristics of these programs and our ability to improve their data locality. To our knowledge, these studies are the first of such breadth and depth. We found performance improvements were difficult to achieve because benchmark programs typically have high hit rates even for small data caches; however, our optimizations significantly improved several programs.
DCG
Authors: Engler Dawson R. , Proebsting Todd A.
Published: November 2005

Dynamic code generation allows aggressive optimization through the use of runtime information. Previous systems typically relied on ad hoc code generators that were not designed for retargetability, and did not shield the client from machine-specific details. We present a system,
dcg
, that allows clients to specify dynamically generated code in a machine-independent manner. Our one-pass code generator is easily retargeted and extremely efficient (code generation costs approximately 350 instructions per generated instruction). Experiments show that dynamic code generation increases some application speeds by over an order of magnitude.
The performance impact of flexibility in the Stanford FLASH multiprocessor
Authors: Heinrich Mark , Kuskin Jeffrey , Ofelt David , Heinlein John , Baxter Joel , Singh Jaswinder Pal , Simoni Richard , Gharachorloo Kourosh , Nakahira David , Horowitz Mark , Gupta Anoop , Rosenblum Mendel , Hennessy John
Published: November 2005

A flexible communication mechanism is a desirable feature in multiprocessors because it allows support for multiple communication protocols, expands performance monitoring capabilities, and leads to a simpler design and debug process. In the Stanford FLASH multiprocessor, flexibility is obtained by requiring all transactions in a node to pass through a programmable node controller, called MAGIC. In this paper, we evaluate the performance costs of flexibility by comparing the performance of FLASH to that of an idealized hardwired machine on representative parallel applications and a multiprogramming workload. To measure the performance of FLASH, we use a detailed simulator of the FLASH and MAGIC designs, together with the code sequences that implement the cache-coherence protocol. We find that for a range of optimized parallel applications the performance differences between the idealized machine and FLASH are small. For these programs, either the miss rates are small or the latency of the programmable protocol can be hidden behind the memory access time. For applications that incur a large number of remote misses or exhibit substantial hot-spotting, performance is poor for both machines, though the increased remote access latencies or the occupancy of MAGIC lead to lower performance for the flexible design. In most cases, however, FLASH is only 2%–12% slower than the idealized machine.
Simple compiler algorithms to reduce ownership overhead in cache coherence protocols
Authors: Skeppstedt Jonas , Stenström Per
Published: November 2005

We study in this paper the design and efficiency of compiler algorithms that remove ownership overhead in shared-memory multiprocessors with write-invalidate protocols. These algorithms detect loads followed by stores to the same address. Such loads are marked and constitute a hint to the cache to obtain an exclusive copy of the block. We consider three algorithms where the first one focuses on load-store sequences within each basic block of code and the other two analyse the existence of load-store sequences across basic blocks at the intra-procedural level. Since the dataflow analysis we adopt is a trivial variation of live-variable analysis, the algorithms are easily incorporated into a compiler.

Through detailed simulations of a cache-coherent NUMA architecture using five scientific parallel benchmark programs, we find that the algorithms are capable of removing over 95% of the separate ownership acquisitions. Moreover, we also find that even the simplest algorithm is comparable in efficiency with previously proposed hardware-based adaptive cache coherence protocols to attack the same problem.
A new iteration mechanism for the C++ programming language
Authors: Kim Myung Ho
Published: November 2005

A new mechanism for writing iterators in the C++ programming language is proposed in this paper. It provides a handy notation for writing general iterators easily, and a simple semantics based-on semicoroutines. A set of useful programming idioms for use with the proposed mechanism is also presented.
A brief look at extension programming before and now
Authors: Räihä Liisa
Published: November 2005

We try to bind together some old and some new: what is an extension. In addition, we give a short analysis of extension facilities in three language systems with slightly different theoretical basis. We compare Ada 9x, Oberon and Macro Language, with additional comments to e.g., C++.
The specification of a generic multicomputer using Lotos
Authors: Gallud J. A. , García J. M.
Published: November 2005

Formal Methods of specification can play an important role in exploring the behaviour of complex systems, as distributed systems or communication protocols. Lotos, based on algebra of processes, has been chosen as an international standard for specifying many systems. We show in this paper the model for a popular class of parallel machines: multicomputers. This paper establishes a guide to employ the Lotos technique in specifying problems on multicomputer architecture. We focus our attention in a new feature of these machines: the dynamic reconfiguration of the network.
Bottom in the imperative world
Authors: Syropoulos Apostolos , Karakos Alexandros
Published: November 2005

Bottom is used in functional programming languages to denote abnormal situations. We propose the incorporation of this value in any existing imperative language. We show how this can be done and finally what are the benefits of the bottom incorporation in any imperative language.Covariant deep subtyping has always been viewed as a way to narrow the range of a component in subtypes. In this paper, however, we will see covariant deep subtyping in a new light---a way to clarify a vague but fixed range of a component in subclasses. We will also examine such concepts as class substitution, generic calss by BETA/Cluster, and a number of theoretic approaches in relation to covariant deep subtyping.
Multithreading in C++
Authors: English John
Published: November 2005

This paper describes the design and implementation of a C++ class library which provides timesliced multithreading capabilities for C++ programs. The implementation described here runs under MS-DOS on an IBM PC, but the library could easily be reimplemented for other systems. The library and its source code are freely available by anonymous FTP from a number of sites.
A comparison of three strategies for computing letter oriented, minimal perfect hashing functions
Authors: Trono John A.
Published: November 2005

This paper will discuss improvements to Cichelli's method for computing the set of weights used for minimal perfect hashing functions[1]. The major modifications investigated here pertain to adding a "MOD number_of_keys" operation to the hashing function, and to the removal of unnecessary backtracking due to "guaranteed collisions".
Optimizing sparse representations for dataflow analysis
Authors: Ruf Erik
Published: November 2005

Sparse program representations allow inter-statement dependences to be represented explicitly, enabling dataflow analyzers to restrict the propagation of information to paths where it could potentially affect the dataflow solution. This paper describes the use of a single sparse program representation, the value dependence graph, in both general and analysis-specific contexts, and demonstrates its utility in reducing the cost of dataflow analysis. We find that several semantics-preserving transformations are beneficial in both contexts.
Sparse functional stores for imperative programs
Authors: Steensgaard Bjarne
Published: November 2005

In recent years, the trend in program representations for imperative programs has been to make them more functional, or to make them more sparse. However, new sparse representations have been non-functional, and new functional representations have not been sparse in the presence of pointer operations. In this paper, we present a functional representation that is sparse even in the presence of pointer operations.

Conventionally, a store is represented in a functional program representation by a single object—typically a mapping from locations to values. We show how such a store object may be fragmented into several objects, each representing part of the store. The result is a sparser representation, which has not only the usual benefit of directly linking producers to consumers, but which also for static program analysis often leads to smaller domains of abstract values for store objects. Store fragmentation corresponds to assignment factored SSA form (a factorization of SSA form introduced in this paper). We report on experiments with a thorough fragmentation based on a data flow points-to analysis and an intermediate level fragmentation based on an almost linear time complexity points-to analysis by type inference.
Rationalized three instruction machine
Authors: Chitnis Sachin V. , Satpathy Manoranjan , Oberoi Sundeep
Published: November 2005

The declarative nature of functional programming languages causes many difficulties in their efficient implementation on conventional machines. The problem is much harder when the language has non-strict (lazy) semantics. Abstract machines serve as an intellectual aid in bridging the semantic gap between such languages and the conventional von Neumann architecture. However they become more and more complex with time as efficiency considerations force the instruction set of the machine to grow in size. In this paper we explain the phenomenon in context of the Three Instruction Machine (TIM). We then define a rationalized instruction set for TIM that allows us to view all enhancements to TIM in a uniform way. This instruction set is quite close to RISC instructions and clearly identifies the key operations on closures. Translation of functional programs to our rationalized instruction set opens up scope for various local and global optimizations. We illustrate this by showing how to build control flow graphs and perform optimizations on it. Lazy arguments in functional programs make it hard to predict evaluation order statistically. We define the notion of
pseudo-lazy
arguments to statically expose the control flow information, wherever possible, for doing better flow analysis.
Java intermediate bytecodes
Authors: Gosling James
Published: November 2005

Java is a programming language loosely related to C++. Java originated in a project to produce a software development environment for small distributed embedded systems. Programs needed to be small, fast, “safe” and portable. These needs led to a design that is rather different from standard practice. In particular, the form of compiled programs is machine independent bytecodes. But we needed to manipulate programs in ways usually associated with higher level, more abstract intermediate representations. This lets us build systems that are safer, less fragile, more portable, and yet show little performance penalty while still being simple.
A project-based approach to programming language evaluation
Authors: Howatt James
Published: November 2005

Most programming language evaluation criteria are based solely on characteristics inherent in a language. Software developers could better use evaluations that help them determine how well-suited a language is for their particular task. This paper proposes such an evaluation method.
Formulating update messages
Authors: Hallett Jon
Published: November 2005

This paper presents a method with which we can generate update messages for use with Smalltalk's dependency mechanism. The basic idea is that any messages which cause an object to change are forwarded to the object's dependants. The method is perfectly general and future-proofs objects against changes in their dependants.
Representing calendrical algorithms and data in Prolog and Prolog III languages
Authors: Návrat Pavol , Bieliková Maria
Published: November 2005

The paper reports on a study to develop solutions for a chosen problem in two related, but different languages. Moreover, the languages reflect two related, but different programming paradigms: logic programming, and constraint, logic programming, respectively. We use Prolog to describe calendars and their mutual conversions. Next, we use Prolog III to describe the same. We discuss suitability of both languages for this kind of task. Prolog III as a logic programming language with constraints allows writing a program which is both more general (i.e., covering a broader range of cases) and more abstract (i.e., expressed on a higher level of abstraction due to the use of constraints).
Introducing virtual instance variables in classes to provide sufficient support for encapsulation
Authors: XueDong Li , Guoliang Zheng
Published: November 2005

Encapsulation is a technique for minimizing interdependecies among separately-writen modules by defining strict external interfaces. Many popular object-oriented languages (e.g, Smalltalk, Flavors, Objective-C and Eiffel) allow free access to inherited instances variables by descendant classes, thus denying the designer the freedom to compatibly change the represnntation of a class without affecting clients and severly compromising encapsulation. In this paper, by introducing virtual instance variables and providing two interfaces (client-interface and subclass-interface) for a class, we give a class mechanism which provides sufficent support for encapsulation and is implemented in NDOOM, a object-oriented dialect of Modula-2 which we are developing.
A model and compilation strategy for out-of-core data parallel programs
Authors: Bordawekar Rajesh , Choudhary Alok , Kennedy Ken , Koelbel Charles , Paleczny Michael
Published: November 2005

It is widely acknowledged in high-performance computing circles that parallel input/output needs substantial improvement in order to make scalable computers truly usable. We present a data storage model that allows processors independent access to their own data and a corresponding compilation strategy that integrates data-parallel computation with data distribution for out-of-core problems. Our results compare several communication methods and I/O optimizations using two out-of-core problems, Jacobi iteration and LU factorization.
pC++/streams
Authors: Gotwals Jacob , Srinivas Suresh , Gannon Dennis
Published: November 2005

The design and implementation of portable, efficient, and expressive mechanisms for I/O on complex distributed data structures—such as found in adaptive parallel applications—is a challenging problem that we address in this paper.

We describe the design, programmer interface, implementation, and performance of
pC++/streams
, a library that provides an expressive mechanism for I/O on distributed arrays of variable-sized objects in pC++, an object-parallel language. pC++/streams is intended for developers of parallel programs requiring efficient high-level I/O abstractions for checkpointing, scientific visualization, and debugging.

pC++/streams is an implementation of
d/streams
, a language-independent abstraction for buffered I/O on distributed data structures. We describe the d/streams abstraction and present performance results on the Intel Paragon and SGI Challenge showing that d/streams can be implemented efficiently and portably.
Distributed data access in AC
Authors: Carlson William W. , Draper Jesse M.
Published: November 2005

We have modified the C language to support a programming model based on a shared address space with physically distributed memory. With this model users can write programs in which the nodes of a massively parallel processor can access remote memory without message passing. AC provides support for distributed arrays as well as pointers to distributed data. Simple array references and pointer dereferencing are sufficient to generate low-overhead remote reads and writes. We have implemented these ideas in a compiler based on the GNU C compiler and targeted at Cray Research's T3D. Initial performance measurements show that AC generates code for remote accesses which is considerably faster than that of the native compiler for structures up to about 16 words in size and virtually equivalent for larger transfers.