bluuebunny/crossref_metadata_2025 huggingface dataset:
Adding the leads-to operator to Dijkstra's calculus
Authors: Singh Awadhesh Kumar , Bandyopadhyay Anup Kumar
Published: November 2005

A temporal operator, namely leads-to, has been incorporated into the Dijkstra's weakest precondition calculus. It is demonstrated that the augmented calculus provides a basis, not only for the modeling but also, for a straightforward and thorough analysis of large and complex distributed systems. The technique has been illustrated by describing a data link layer protocol. This analysis contributes to the understanding of the system.
Process algebra model of Ada protected objects
Authors: Liu Yuan , Xu Baowen
Published: November 2005

The feasibility and efficiency of analyzing concurrent programs mostly relies on the programs' representations. So modeling concurrent programs in a proper and suitable way is very important. Protected objects, which have been introduced in Ada95, are of significant importance in concurrent programming language. In this paper, process algebra is used to model Ada95 protected objects in a neat and tidy way. Because using process algebra can simplify process composition and conveniently hide internal details, it becomes easy to analyze Ada concurrent programs with protected objects and to combat problems of state explosion. In addition, many mechanisms similar to protected objects can be modeled in this way. With these models, many analyses, such as model checking, can be performed.
LO and behold! Concurrent structured processes
Authors: Andreoli Jean-Marc , Pareschi Remo
Published: November 2005

We introduce a novel concurrent logic programming language, which we call LO, based on an extension of Horn logic. This language enhances the process view of objects implementable in Horn-based concurrent logic programming languages with powerful capabilities for knowledge structuring, leading to a flexible form of variable-structure inheritance. The main novelty about LO is a new kind of OR-concurrency which is dual to the usual AND-concurrency and provides us with the notion of
structured process.
Such OR-concurrency can be nicely characterized with a sociological metaphor as modelling the internal distribution of tasks inside a complex organization; this complements the external cooperation among different entities accounted for by AND-concurrency
.
When objects collide experiences with reusing multiple class hierarchies
Authors: Berlin Lucy M.
Published: November 2005

Well-designed reusable class libraries are often incompatible due to architectural mismatches such as error-handling and composition conventions. We identify five
pragmatic dimensions
along which combinations of subsystems must match, and present detailed examples of conflicts resulting from mismatches. Examples are drawn from our experiences of integrating five subsystem-level class hierarchies into an object-oriented hypertext platform. We submit that effective reuse will require that these pragmatic decisions be explicitly identified in descriptions of reusable software. Such descriptions will enable developers to identify and combine subsystems whose architectures are compatible.
Type consistency of queries in an object-oriented database system
Authors: Straube Dave D. , Özsu M. Tamer
Published: November 2005

Queries in object-oriented databases can return non-homogeneous sets of objects when no type restrictions are placed on the inputs to the query. The tradition has been to force homogeneity on the result by restricting the types of the inputs. This restricts the range of permissible, and possibly useful, queries. We propose a type consistency theory for queries in object-oriented databases which supports the existence of multiple types in the query result. The technique is illustrated by developing type inference rules for an object algebra. The main result is that the loss of type information associated with a query operation is reduced in most cases. We also show how type information is increased when queries are qualified by conjunctive predicates.
A framework for visualizing object-oriented systems
Authors: Haarslev Volker , Möller Ralf
Published: November 2005

This paper describes a new approach to visualizing program systems within the object-oriented paradigm. This approach is based on a TEX-like notation which has been extended and generalized for specifying graphical layout of arbitrary objects. The CLOS meta-level architecture is used to associate visualization and application objects. We propose several useful techniques such as indirect values, slot and method demons, and instance-specific meta-objects. Our techniques require no modifications to the systems which are selected for visualization. We demonstrate the feasibility of our approach using application domains such as CLOS debugging and constraint systems.
Painting multiple views of complex objects
Authors: McDonald John Alan , Stuetzle Werner , Buja Andreas
Published: November 2005

This paper reviews and illustrates a direct manipulation approach to visualization of complex objects called
painting multiple views
. We describe a programming model for direct manipulation in general and for painting in particular, based on simple constraints between entities in an the underlying scientific database and the components of displays used to examine the data. With this model, the original notion of “brushing scatterplots” is easily extended.
MoDE: a UIMS for Smalltalk
Authors: Shan Yen-Ping
Published: November 2005

While the Model-View-Controller (MVC) framework has contributed to many aspects of user interface development in Smalltalk, interfaces produced with MVC often have highly coupled model, view, and controller classes. This coupling and the effort required to use MVC make user interface creation a less effective aspect of Smalltalk.

The Mode Development Environment (MoDE) is a user interface management system (UIMS) which addresses the above issues. MoDE is composed of two major components: the Mode framework and the Mode Composer. The Mode framework accommodates an orthogonal design which decouples the user interface components and increases their reusability. The Mode Composer reduces the effort of using MoDE by providing a direct-manipulation user interface to its users. This paper discusses the importance of orthogonality and illustrates its incorporation into the design of MoDE. A comparison of the Mode framework and the MVC framework is included.
OOP in the real world
Authors: DeNatale Rick , Irby Charles , LaLonde John , Leathers Burton , Phillips Reed
Published: November 2005

Some advocates of OOP have promised that it will make all code reusable, shorten development cycles, remove the applications backlog, cure the common cold and plug the hole in the ozone layer.

How well does actual experience bear this out?

Success stories are published much more often than failures and false starts. This is very unfortunate since the former two are often much more instructive.

This panel will attempt to bring the less successful experiences to light, and hopefully, will provide lessons on how to do better.
The point of view notion for multiple inheritance
Authors: Carré Bernard , Geib Jean-Marc
Published: November 2005

We examine several problems related to the preservation of the Independence Principle inheritance. This principle states that all the characteristics of independent superclasses must be inherited by subclasses, even if there are name conflicts. In this context, a conventional approach is to use explicit class selection. We show that this mechanism suffers from serious limitations, and leads to inhibition of refinement and genericity. Our experimental object-oriented language ROME introduces the “Point of View” notion (using an “as-expressions” mechanism) which solves these problems.
Exception handling and object-oriented programming: towards a synthesis
Authors: Dony Christophe
Published: November 2005

The paper presents a discussion and a specification of an exception handling system dedicated to object-oriented programming. We show how a full object-oriented representation of exceptions and of protocols to handle them, using meta-classes, makes the system powerful as well as extendible and solves many classical exception handling issues. We explain the interest for object-oriented programming of handlers attached to classes and to expressions. We propose an original algorithm for propagating exceptions along the invocation chain which takes into account, at each stack level, both kind of handlers. Any class can control which exceptions will be propagated out of its methods; any method can provide context-dependant answers to exceptional events. The whole specification and some keys of our
Smalltalk
implementation are presented in the paper.
Simple relational correctness proofs for static analyses and program transformations
Authors: Benton Nick
Published: November 2005

We show how some classical static analyses for imperative programs, and the optimizing transformations which they enable, may be expressed and proved correct using elementary logical and denotationaltechniques. The key ingredients are an interpretation of program properties as relations, rather than predicates, and a realization that although many program analyses are traditionally formulated in very intensional terms, the associated transformations are actually enabled by more liberal extensional properties.We illustrate our approach with formal systems for analysing and transforming while-programs. The first is a simple type system which tracks constancy and dependency information and can be used to perform dead-code elimination, constant propagation and program slicing as well as capturing a form of secure information flow. The second is a relational version of Hoare logic, which significantly generalizes our first type system and can also justify optimizations including hoisting loop invariants. Finally we show how a simple available expression analysis and redundancy elimination transformation may be justified by translation into relational Hoare logic.
Parsing expression grammars
Authors: Ford Bryan
Published: November 2005

For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ambiguity is crucial to their original purpose of modelling natural languages, but this very power makes it unnecessarily difficult both to express and to parse machine-oriented languages using CFGs. Parsing Expression Grammars (PEGs) provide an alternative, recognition-based formal foundation for describing machine-oriented syntax, which solves the ambiguity problem by not introducing ambiguity in the first place. Where CFGs express nondeterministic choice between alternatives, PEGs instead use
prioritized choice
. PEGs address frequently felt expressiveness limitations of CFGs and REs, simplifying syntax definitions and making it unnecessary to separate their lexical and hierarchical components. A linear-time parser can be built for any PEG, avoiding both the complexity and fickleness of LR parsers and the inefficiency of generalized CFG parsing. While PEGs provide a rich set of operators for constructing grammars, they are reducible to two minimal recognition schemas developed around 1970, TS/TDPL and gTS/GTDPL, which are here proven equivalent in effective recognition power.
Global value numbering using random interpretation
Authors: Gulwani Sumit , Necula George C.
Published: November 2005

We present a polynomial time randomized algorithm for global value numbering. Our algorithm is complete when conditionals are treated as non-deterministic and all operators are treated as uninterpreted functions. We are not aware of any complete polynomial-time deterministic algorithm for the same problem. The algorithm does not require symbolic manipulations and hence is simpler to implement than the deterministic symbolic algorithms. The price for these benefits is that there is a probability that the algorithm can report a false equality. We prove that this probability can be made arbitrarily small by controlling various parameters of the algorithm.Our algorithm is based on the idea of random interpretation, which relies on executing a program on a number of random inputs and discovering relationships from the computed values. The computations are done by giving random linear interpretations to the operators in the program. Both branches of a conditional are executed. At join points, the program states are combined using a random affine combination. We discuss ways in which this algorithm can be made more precise by using more accurate interpretations for the linear arithmetic operators and other language constructs.
Design and implementation of PL/I preprocessor-based systems
Authors: Schwartz B. M.
Published: November 2005

This paper describes and illustrates the type of simple application-oriented "language" that is easily implemented as a set of PL/I %procedure calls. A tool kit of % procedures designed to simplify the task is described. Finally, a general approach to the design and implementation of this type of system is discussed.
SNOBOL4 as a language for bootstrapping a compiler
Authors: Dunn Richard
Published: November 2005

The programming language SNOBOL4 is evaluated for the task of bootstrapping the compiler for a new language. Based on the results of an actual project, SNOBOL4 was found to have adequate power to write the bootstrap, but could not produce an acceptably efficient translator.
Flow trace of a structured program
Authors: Mathis Robert F.
Published: November 2005

Program traces are historical records of some phase of a program's activity. The program listing of a structured program can be indented to show the structure and flow of control. The printed output lines of the flow trace of a structured program can be indented to the level indicated by the indentation of the program listing. By adding this information to the trace output, considerably more information about the program's flow of control is available after execution. More options should be available because it is a structured program that is being traced. Storage traces and subroutine traces also fit into the indentation pattern of the flow trace. The indentation scheme possible because it is a structured program not only shows the control flow better but also gives a better picture of how variables are used and changed.
Multiple tense computer programming
Authors: Nylin William C. , Harvill John B.
Published: November 2005

A programming language concept which uses natural language operand qualifiers is proposed as an addition to current high level programming languages. This language concept allows the programmer to access both past and future values of operands and operators by using natural language tense qualifiers. Current computer languages require explicit array manipulation by the program to maintain and access previous operand values; not the one-to-one mapping of problem quantities to program operands that is desirable. Instead they represent a one-to-many mapping. The control and use of this forced multiple mapping seriously increases the complexity of our algorithms.A BNF for qualifying phrases which may be used to modify operands is presented. Examples of some permissible qualifiers for an operand A are PREVIOUS A, NEXT A, FIRST A, TENTH A, ANY A, ALL A'S, 1ST THROUGH 7TH A'S. These qualifiers provide the computer programmer with the ability to specify algorithms in a computer language which more closely resembles a natural language.Since the concept implies a distinctly non-Von Neuman computer, several possible implementations using current software and hardware techniques are suggested.
Syntax extension and the IMP72 programming language
Authors: Bilofsky Walter
Published: November 2005

The IMP72 language for the DEC PDP-10 computer is the most recent of the IMP family of extensible software implementation languages. Its facility for extending the syntax of the language, the syntax statement, is simple enough to be useful to relatively unsophisticated users, yet powerful enough that the IMP72 language is defined by an IMP72 source program consisting of syntax statements.
How to build LR parsers which accept incomplete input
Authors: Snelting Gregor
Published: November 2005

In this short note, we describe a modification to LR parsers which allows processing of incomplete input, while at the same time building of correct abstract syntax trees. This feature is very useful for language-based editors.
On "powerloop" constructs in programming languages
Authors: Mandl Robert
Published: November 2005

A recent article in these Notices [1] gives an overview of proposals and implementations of a "power operator" which (in its simplest form), acting on a nonnegative integer N and on a dyadic function ¤, yields a monadic function which maps any nonnegative number B into B¤B¤B¤...¤B with N occurrences of B. The entire discourse is couched in APL terms, thus unfortunately suggesting a somewhat narrow relevance. To dispel this erroneous impression, we give here a simple example of a programming task where the utility of such a construct appears in a most natural manner, and suggest a possible syntax therefor.
Experience with extensible, portable Fortran extensions
Authors: Cook A. James
Published: November 2005

We assess the impact over a three-year period, of the macro-pre-processor MORTRAN, and one of the languages it processes. We confine our assessment to SLAC and Stanford since, although MORTRAN has been widely distributed in the United States and to a lesser extent in Europe, we have no personal knowledge of its impact elsewhere. The impact is attributed to three factors: (1) portability, (2) compatibility (with existing FORTRAN libraries), and (3) extensibility, which is sub-divided into (a) extension of control structures, and (6) extension of data structures. We divide the impact into an "initial" impact which we relate to control structure extensions, and a "secondary" impact which we relate to data structure extensions. MORTRAN is currently being used at SLAC to process large production programs, some of which exceed ten thousand lines of MORTRAN source code.
Recursive definitions for iterative algorithms
Authors: Lassagne Theodore D.
Published: November 2005

Since higher level languages first appeared, computer
practitioners have been seeking a language which will permit them
to define an algorithm to a computer without unnecessary
specification of the sequence in which actions are to be carried
out. Recursive definitions meet this requirement, but a major
obstacle to their wider adoption has been the fact that so many of
our algorithms are iterative in nature, and it typically has not
been easy to convert an iterative atgorithm to one in recursive
definition form.

However, if we look at recursive definitions from a somewhat
broader viewpoint and introduce the technique of "mu-recursion",
then iterative algorithms can be expressed fairly naturally in
recursive form. This capability opens up possibilities for a
practical recurstve definition language useful for a wide range of
computational tasks. Therefore, in addition to demonstrating how to
write practical algorithms with recursive definitions, we will
discuss the prospects for a practical language and its compilation.
Also covered briefly will be proof techniques and suggestions for
further research.
Why the goto is harmful
Authors: Zoethout Th. A. , Stein E. I. N.
Published: November 2005

In this paper, the results of some research on the semantics of the goto-statement are presented. The outcome of this research might give an explanation for the problems encountered when using goto-statements in computer programs.We also discuss why the increased speed of operation of future computers may aggravate the dangers of this statement.
The Intel Fortran-80 compiler for the 8080 and 8085 microprocessors
Authors: Schulz Dean
Published: November 2005

Fortran-80 is the name of Intel's dialect of Fortran as well as the compiler which implements it for the 8080 and 8085 microprocessors.The Fortran-80 language is a superset of the new ANS Fortran 77 Subset language, incorporates many of the features of the full Fortran-77 language, and includes a few features not in Fortran-77 which are convenient for microprocessor applications programming. The latter includes hexadecimal integer constants and format specifiers, simple bit manipulation on integer variables, and INTEGER and LOGICAL variables of three different lengths. This paper comments on the relationship among microprocessors, the new ANS Fortran-77 Subset, and Fortran-80.
Some practical experiences formatting Pascal programs
Authors: Gustafson G. G.
Published: November 2005

Experiences, in the production environment, with two Pascal formatting schemes are discussed and a revised scheme is proposed.
Some Pascal style guidelines
Authors: Marca David
Published: November 2005

The need for developing a style of writing Pascal programs to allow reasonable rehosting success prompted a study on Pascal style. Presented is a subset of guidelines developed from that research, plus some philosophy behind proper interpretation and enforcement of those guidelines. Styling is defined for the programming areas of: description using comments, expression with identifier names and conditionals, and the constructs of block, decision, repetition, and qualification. Enforcement of style and using it in a practical setting are also discussed.
Syntax of comments
Authors: Pentzlin Karl L.
Published: November 2005

The syntaxes of comments in some widespread programming languages are discussed.A comment syntax that avoids the disadvantages of the previously discussed syntaxes is proposed.
Text-oriented structure commands for structure editors
Authors: Cohen Ellis
Published: November 2005

The main problems associated with program structure editors are not inherent and can be solved without reverting to a textual viewpoint. Cursor movements can be made more natural by viewing the screen as a 2-D arrangement of nodes. Expressions can be input from left to right by rebinding operator keys to commands more complex than simple template expansion. Transformations of program fragments can be accomplished by an editor which supports matching and instantiation of subtrees.
Lexing and parsing Modula-2
Authors: Spector David
Published: November 2005

This paper attempts to be a complete description, from the implementor's viewpoint, of the basic lexing and parsing requirements of the Modula-2 language. The lexical structure is described informally, while the syntax is specified formally by an LALR(1) grammar expressed in BNF (Backus-Naur Form).Further information is available in the Modula-2 language definition [1].
Command level software tools
Authors: Gait Jason
Published: November 2005

The
V6 UNIX
command language,
shell
, has weak looping constructs and no apparent interactive capability. We show how to exploit the existing weak loop constructs in
shell
to provide more powerful facilities. Further, we show how to interact with
shell
programs from the terminal.
DO-SELECT reconsidered
Authors: den Hertog E. H. , Gerbscheid H J. C. , Kersten M. L.
Published: November 2005

This article is a further investigation into the usefulness of a DO-SELECT as proposed by Hill [Hill82]. The DO-SELECT construct claims to improve understandability and reduce the complexity of deeply nested IF-THEN-ELSE statements. However, the presentation does not address the limitations of the approach. A better structure is indicated.
Tracing offensive values from exceptions
Authors: Gutfreund Steven
Published: November 2005

In debugging, techniques for tracing back offending values are extremely useful. In [1] Raphael Finkel presents us with an easily implemented and fairly useful technique. As was pointed out in [1] there has been other work in this area. In this note I would like to present a short taxonomy of the various techniques, and attempt to place Finkel's technique in its place in the hierarchy.
Eliminating unwanted loops in Prolog
Authors: Covington Michael A.
Published: November 2005

Modifications to Prolog are proposed that make it possible to express transitive and symmetrical relations and biconditionals. This is done by blocking recursion under circumstances that would lead to infinite loops.
Using BINS for inter-process communication
Authors: Graham Peter C. J.
Published: November 2005

A bin is essentially a message drop, used to implement inter-process communications in the
FRANK
programming language. The use of bins provides three distinct advantages over traditional message passing systems.1) relative anonymity,2) multiple servers,3) enhanced compile time checking. (relative to systems like Thoth[3]).This paper discusses the rationale behind bins and the possible implementation strategies under examination. Finally, it gives two examples using bins which will illustrate the concept.
The NIL distributed systems programming language
Authors: Strom Rob , Yemini Shaula
Published: November 2005

This paper is a summary of ongoing research activities related to the programming language NIL, a high level language for concurrent and distributed systems developed at IBM Yorktown.We first present a short summary of the major features of NIL. These include the NIL system model, which is a dynamically evolving network of loosely coupled processes, communicating by message passing; the abstract NIL computation model; and typestate, which is a refinement of type systems allowing a compiler to assume an important subset of program validation.We then discuss issues related to providing a semantic theory for NIL, and list some general requirements a semantic model should satisfy to be applicable to practical concurrent and distributed systems. We discuss the fit between CCS, which we are studying as a possible candidate for such a semantic theory, and these requirements.Finally we describe some recent work on transformations which map NIL programs to efficient distributed and parallel implementations.
On the organization of Pascal blocks
Authors: Rudnicki Piotr
Published: November 2005

This paper discusses a modest extension to standard Pascal aimed at increasing the readability of long sequences of statements. A new construct, named
action
, for structuring program texts is proposed.
On eliminating loops in Prolog
Authors: Poole David , Goebel Randy
Published: November 2005

Recent papers have explained how infinite loops in a Prolog search tree can be avoided by the use of subgoal deletion. We show here that this works only in limited cases, and argue that these cases can be better avoided by slight modifications of the program, rather than by increasing the complexity of all programs with a rule that has very limited applicability.
Specialization, generalization and inheritance teaching objectives beyond data structures and data types
Authors: LaLonde Wilf R. , Pugh John R.
Published: November 2005

This paper describes our experience in teaching a course in abstract data types over a four year period. Although abstract data types are a major improvement over traditional data structures, they provide only a portion of the concepts needed by experienced designers. The additional concepts needed include such notions as generalizations of data types, their specializations, relationships between data types, and the capability and necessity of abstracting common operations through inheritance mechanisms. Designing an individual abstract data type is akin to "programming in the small" but designing a library of data types introduces new problems that are best solved from the viewpoint of "programming in the large".
The primitive string manipulation (PRISM) language
Authors: Barnett Michael P.
Published: November 2005

This note describes a set of primitives that seem to provide the basis of a general system of string manipulation. The author is using these in some simulation experiments and in instructional material that he is developing. He would appreciate citations to any prior work that uses the same set of primitives, or which has strong similarities to the PRISM approach. Individual details of PRISM have obvious resemblances to particular features of some well known programming languages and formal systems. The precise combination of primitives in PRISM, however, have capabilities that do not seem to be known generally, including possible use in the design of artificial intelligence machines.
Implementation considerations of mapping LISP onto a cellular computer system
Authors: Shao J. , Quick G. E.
Published: November 2005

Cellular Systems have been proposed as a new architecture to end the dominance of the conventional Von-Neumann machine. LISP as a suitable language for such systems is discussed in this paper. An implementation approach is also presented, thereby providing an insight into system realization, especially with regard to parallelism and data localization. This maximises the potential parallelism offered by cellular systems, while minimising the programming effort.
A technique for finding storage allocation errors in C-language programs
Authors: Barach David R. , Taenzer David H. , Wells Robert E.
Published: November 2005

This paper describes a simple tool for diagnosing allocation errors in C-language [Kern 78] programs. Our tool consists of a traced replacement for the standard memory allocator, and a program to analyze traces. We have found this tool quite helpful in making long-running programs (e.g. text editors) more robust.
Code generation in a machine-independent compiler
Authors: Cattell R. G. G. , Newcomer Joseph M. , Leverett Bruce W.
Published: November 2005

This paper presents some code generation issues in the context of the PQCC Production-Quality Compiler-Compiler project [8]. The approach taken is unusual in several ways. The machine-dependent information for selection of code sequences, register assignments, etc., has been separated throughout, in tabular form, from the machine-independent algorithms. This not only greatly simplifies the development of code generators for new machines or languages, but paves the way for automatic generation of these tables from formal machine descriptions such as ISP [1]. A parse-tree-like internal program representation is used, facilitating the use of context and data dependency information about expressions. The code generation process has been broken into several phases. This leads to simplification and better understanding of the code generation process, and also allows important improvements in the quality of generated code. The algorithms for preliminary determination of addressing modes, allocation of registers and other locations, and the code selection case analysis are dlscussed. The algorithms described In the paper are being implemented and used in the PQCC compiler.
Interprocedural dependence analysis and parallelization
Authors: Burke Michael G. , Cytron Ron K.
Published: November 2005

The area of dependence analysis has served as grounds for fruitful research as well as practical implementation. Compilers and tools that utilize dependence information can generate code that takes advantage of parallel resources and storage hierarchies on modern architectures. Here, we offer some historical background on the context and thinking that fostered our 1986 paper. We also attempt to summarize the direction research in this area has taken since the paper's appearance.We present a method that combines a deep analysis of program dependences with a broad analysis of the interaction among procedures. The method is more efficient than existing methods: we reduce many tests, performed separately by existing methods, to a single test. The method is more precise than existing methods with respect to references to multi-dimensional arrays and dependence information hidden by procedure calls. The method is more general than existing methods: we accommodate potentially aliased variables and structures of differing shapes that share storage. We accomplish the above through a unified approach that integrates subscript analysis with aliasing and interprocedural information.
Orbit
Authors: Kranz David , Kelsey Richard , Rees Jonathan , Hudak Paul , Philbin James , Adams Norman
Published: November 2005

Orbit was an optimizing compiler for T, a dialect of Scheme. Its aggressive use of CPS conversion, novel closure representations, and efficient code generation strategies made it the best compiler for a Scheme dialect at the time and for many years to come. The design of T and Orbit directly spawned six PhD theses and one Masters thesis, and influenced many other projects as well, including SML of New Jersey.
Interprocedural side-effect analysis in linear time
Authors: Cooper Keith D. , Kennedy Ken
Published: November 2005

We present a new method for solving Banning's alias-free flow-insensitive side-effect analysis problem. The algorithm employs a new data structure, called the
binding multi-graph
, along with depth-first search to achieve a running time that is linear in the size of the call multi-graph of the program. This method can be extended to produce fast algorithms for data-flow problems with more complex lattice structures.
Higher-order control-flow analysis in retrospect
Authors: Shivers Olin
Published: November 2005

Traditional flow analysis techniques, such as the ones typically employed by optimising Fortran compilers, do not work for Scheme-like languages. This paper presents a flow analysis technique ---
control flow analysis
--- which is applicable to Scheme-like languages. As a demonstration application, the information gathered by control flow analysis is used to perform a traditional flow analysis problem, induction variable elimination. Extensions and limitations are discussed.The techniques presented in this paper are backed up by working code. They are applicable not only to Scheme, but also to related languages, such as Common Lisp and ML.
Space efficient conservative garbage collection
Authors: Boehm Hans J.
Published: November 2005

Both type-accurate and conservative garbage collectors have gained in importance since the original paper was written. Managing unnecessary retention by conservative collectors continues to be an important problem. There appear to be few reimplementations of the techniques we described, but significantly refined descendents of the original implementation are alive and well inside a large number of applications.There has been later work both on quantifying space retention by conservative collectors, and on theoretical bounds for such retention.We call a garbage collector conservative if it has only partial information about the location of pointers, and is thus forced to treat arbitrary bit patterns as though they might be pointers, in at least some cases. We show that some very inexpensive, but previously unused techniques can have dramatic impact on the effectiveness of conservative garbage collectors in reclaiming memory. Our most significant observation is that static data that appears to point to the heap should not result in misidentified references to the heap. The garbage collector has enough information to allocate around such references. We also observe that programming style has a significant impact on the amount of spuriously retained storage, typically even if the collector is not terribly conservative. Some fairly common C and C++ programming styles significantly decrease the effectiveness of any garbage collector. These observations suffice to explain some of the different assessments of conservative collection that have appeared in the literature.
A fast Fourier transform compiler
Authors: Frigo Matteo
Published: November 2005

The FFTW library for computing the discrete Fourier transform (DFT) has gained a wide acceptance in both academia and industry, because it provides excellent performance on a variety of machines (even competitive with or faster than equivalent libraries supplied by vendors). In FFTW, most of the performance-critical code was generated automatically by a special-purpose compiler, called
genfft
, that outputs C code. Written in Objective Caml,
genfft
can produce DFT programs for any input length, and it can specialize the DFT program for the common case where the input data are real instead of complex. Unexpectedly,
genfft
"discovered" algorithms that were previously unknown, and it was able to reduce the arithmetic complexity of some other existing algorithms. This paper describes the internals of this special-purpose compiler in some detail, and it argues that a specialized compiler is a valuable tool.
A retrospective on
Authors: Grant Brian , Philipose Matthai , Mock Markus , Chambers Craig , Eggers Susan J.
Published: November 2005

Previous selective dynamic compilation systems have demonstrated that dynamic compilation can achieve performance improvements at low cost on small kernels, but they have had difficulty scaling to larger programs. To overcome this limitation, we developed DyC, a selective dynamic compilation system that includes more sophisticated and flexible analyses and transformations. DyC is able to achieve good performance improvements on programs that are much larger and more complex than the kernels. We analyze the individual optimizations of DyC and assess their impact on performance collectively and individually.
Multi-model parallel programming in psyche
Authors: Scott M. L. , LeBlanc T. J. , Marsh B. D.
Published: November 2005

Many different parallel programming models, including lightweight processes that communicate with shared memory and heavyweight processes that communicate with messages, have been used to implement parallel applications. Unfortunately, operating systems and languages designed for parallel programming typically support only one model. Multi-model parallel programming is the simultaneous use of several different models, both across programs and within a single program. This paper describes multi-model parallel programming in the Psyche multiprocessor operating system. We explain why multi-model programming is desirable and present an operating system interface designed to support it. Through a series of three examples, we illustrate how the Psyche operating system supports different models of parallelism and how the different models are able to interact.
An implementation of a barotropic Numerical Weather Prediction model in the functional language SISAL
Authors: Chang P. S. , Egan G. K.
Published: November 2005

Numerical Weather Prediction (NWP) is acknowledged as being of vital importance to economy. The demand that NWP places on computing system performance has increased dramatically since the introduction of computer systems and is still growing. This paper describes the implementation of a one-level barotropic spectral NWP model using the high level functional language SISAL. Our initial approach was a direct transliteration from FORTRAN to SISAL, the result of which was a large amount of array copying and loss of parallelism. The algorithm of the model was then rearranged to enable effective exploitation of parallelism by an optimizing SISAL compiler. The parallel implementation technique and its potential for modeling with larger model sizes are discussed, and the improved results for an Encore Multimax multiprocessor are presented.
Scalable lock-free dynamic memory allocation
Authors: Michael Maged M.
Published: November 2005

Dynamic memory allocators (malloc/free) rely on mutual exclusion locks for protecting the consistency of their shared data structures under multithreading. The use of locking has many disadvantages with respect to performance, availability, robustness, and programming flexibility. A lock-free memory allocator guarantees progress regardless of whether some threads are delayed or even killed and regardless of scheduling policies. This paper presents a completely lock-free memory allocator. It uses only widely-available operating system support and hardware atomic instructions. It offers guaranteed availability even under arbitrary thread termination and crash-failure, and it is immune to deadlock regardless of scheduling policies, and hence it can be used even in interrupt handlers and real-time applications without requiring special scheduler support. Also, by leveraging some high-level structures from Hoard, our allocator is highly scalable, limits space blowup to a constant factor, and is capable of avoiding false sharing. In addition, our allocator allows finer concurrency and much lower latency than Hoard. We use PowerPC shared memory multiprocessor systems to compare the performance of our allocator with the default AIX 5.1 libc malloc, and two widely-used multithread allocators, Hoard and Ptmalloc. Our allocator outperforms the other allocators in virtually all cases and often by substantial margins, under various levels of parallelism and allocation patterns. Furthermore, our allocator also offers the lowest contention-free latency among the allocators by significant margins.
Min-cut program decomposition for thread-level speculation
Authors: Johnson Troy A. , Eigenmann Rudolf , Vijaykumar T. N.
Published: November 2005

With billion-transistor chips on the horizon, single-chip multiprocessors (CMPs) are likely to become commodity components. Speculative CMPs use hardware to enforce dependence, allowing the compiler to improve performance by speculating on ambiguous dependences without absolute guarantees of independence. The compiler is responsible for decomposing a sequential program into speculatively parallel threads, while considering multiple performance overheads related to data dependence, load imbalance, and thread prediction. Although the decomposition problem lends itself to a min-cut-based approach, the overheads depend on the thread size, requiring the edge weights to be changed as the algorithm progresses. The changing weights make our approach different from graph-theoretic solutions to the general problem of task scheduling. One recent work uses a set of heuristics, each targeting a specific overhead in isolation, and gives precedence to thread prediction, without comparing the performance of the threads resulting from each heuristic. By contrast, our method uses a sequence of balanced min-cuts that give equal consideration to all the overheads, and adjusts the edge weights after every cut. This method achieves an (geometric) average speedup of 74% for floating-point programs and 23% for integer programs on a four-processor chip, improving on the 52% and 13% achieved by the previous heuristics.
Vectorization for SIMD architectures with alignment constraints
Authors: Eichenberger Alexandre E. , Wu Peng , O'Brien Kevin
Published: November 2005

When vectorizing for SIMD architectures that are commonly employed by today's multimedia extensions, one of the new challenges that arise is the handling of memory alignment. Prior research has focused primarily on vectorizing loops where all memory references are properly aligned. An important aspect of this problem, namely, how to vectorize misaligned memory references, still remains unaddressed.This paper presents a compilation scheme that systematically vectorizes loops in the presence of misaligned memory references. The core of our technique is to automatically reorganize data in registers to satisfy the alignment requirement imposed by the hardware. To reduce the data reorganization overhead, we propose several techniques to minimize the number of data reorganization operations generated. During the code generation, our algorithm also exploits temporal reuse when aligning references that access contiguous memory across loop iterations. Our code generation scheme guarantees to never load the same data associated with a single static access twice. Experimental results indicate near peak speedup factors, e.g., 3.71 for 4 data per vector and 6.06 for 8 data per vector, respectively, for a set of loops where 75% or more of the static memory references are misaligned.
Cost effective dynamic program slicing
Authors: Zhang Xiangyu , Gupta Rajiv
Published: November 2005

Although dynamic program slicing was first introduced to aid in user level debugging, applications aimed at improving software quality, reliability, security, and performance have since been identified as candidates for using dynamic slicing. However, the dynamic dependence graph constructed to compute dynamic slices can easily cause slicing algorithms to run out of memory for realistic program runs. In this paper we present the design and evaluation of a cost effective dynamic program slicing algorithm. This algorithm is based upon a dynamic dependence graph representation that is highly compact and rapidly traversable. Thus, the graph can be held in memory and dynamic slices can be quickly computed. A compact representation is derived by recognizing that all dynamic dependences (data and control) need not be individually represented. We identify sets of dynamic dependence edges between a pair of statements that can
share
a single representative edge. We further show that the dependence graph can be transformed in a manner that increases sharing and sharing can be performed even in the presence of aliasing. Experiments show that transformed dynamic dependence graphs explicitly represent only 6% of the dependence edges present in the full dynamic dependence graph. When the full graph sizes range from 0.84 to 1.95 Gigabytes in size, our compacted graphs range from 20 to 210 Megabytes in size. Average slicing times for our algorithm range from 1.74 to 36.25 seconds across several benchmarks from SPECInt2000/95.
Prefetch injection based on hardware monitoring and object metadata
Authors: Adl-Tabatabai Ali-Reza , Hudson Richard L. , Serrano Mauricio J. , Subramoney Sreenivas
Published: November 2005

Cache miss stalls hurt performance because of the large gap between memory and processor speeds - for example, the popular server benchmark SPEC JBB2000 spends 45% of its cycles stalled waiting for memory requests on the Itanium® 2 processor. Traversing linked data structures causes a large portion of these stalls. Prefetching for linked data structures remains a major challenge because serial data dependencies between elements in a linked data structure preclude the timely materialization of prefetch addresses. This paper presents
Mississippi Delta
(MS Delta), a novel technique for prefetching linked data structures that closely integrates the hardware performance monitor (HPM), the garbage collector's global view of heap and object layout, the type-level metadata inherent in type-safe programs, and JIT compiler analysis. The garbage collector uses the HPM's data cache miss information to identify cache miss intensive traversal paths through linked data structures, and then discovers regular distances (
deltas
) between these linked objects. JIT compiler analysis injects prefetch instructions using deltas to materialize prefetch addresses.We have implemented MS Delta in a fully dynamic profile-guided optimization system: the StarJIT dynamic compiler [1] and the ORP Java virtual machine [9]. We demonstrate a 28-29% reduction in stall cycles attributable to the high-latency cache misses targeted by MS Delta and a speedup of 11-14% on the cache miss intensive SPEC JBB2000 benchmark.
A generalized algorithm for graph-coloring register allocation
Authors: Smith Michael D. , Ramsey Norman , Holloway Glenn
Published: November 2005

Graph-coloring register allocation is an elegant and extremely popular optimization for modern machines. But as currently formulated, it does not handle two characteristics commonly found in commercial architectures. First, a single register name may appear in multiple register classes, where a class is a set of register names that are interchangeable in a particular role. Second, multiple register names may be aliases for a single hardware register. We present a generalization of graph-coloring register allocation that handles these problematic characteristics while preserving the elegance and practicality of traditional graph coloring. Our generalization adapts easily to a new target machine, requiring only the sets of names in the register classes and a map of the register aliases. It also drops easily into a well-known graph-coloring allocator, is efficient at compile time, and produces high-quality code.