bluuebunny/crossref_metadata_2025 huggingface dataset:
Macro processing in high-level languages
Authors: Sakharov Alexander
Published: November 2005

A macro language is proposed. It enables macro processing in high-level programming languages. Macro definitions in this language refer to the grammars of the respective programming languages. These macros introduce new constructs in programming languages. It is described how to automatically generate macro processors from macro definitions and programming language grammars written in the lex-yacc format. Examples of extending high-level languages by means of macros are given.
The Hermes language in outline form
Authors: Lowry Andy
Published: November 2005

Hermes is an experimental language for writing disgributed applications and systems. The language is fully described elsewhere[1]. This report summarizes the major features of The language and provides numerous short code fragments to illustrate the various constructs. Missing from this report is any discussion of user-defined constraints, which are in any case not yet supported in the prototype implementation we have developed. Those wishing to obtain the prototype software may do so via anonymous ftp to software.watson.ibm.com (IP address 129.34.139.5); the files/pub/README.FTP and/pub/hermes/README provide further instructions.
Hamming numbers, lazy evaluation, and eager disposal
Authors: Yuen C. K.
Published: November 2005

The generation of Hamming numbers is used as a case study for discussing storage management for transient data structures in language processors.
Treating statement sequences as block objects
Authors: Mössenböck Hanspeter
Published: November 2005

We propose a language construct for treating statement sequences as block objects that can be passed to procedures as arguments. Block objects are well known from Smalltalk but are not available in most other languages. We show how to implement block objects efficiently.
Lively linear Lisp
Authors: Baker Henry G.
Published: November 2005

Linear logic has been proposed as one solution to the problem of garbage collection and providing efficient "update-in-place" capabilities within a more functional language. Linear logic conserves accessibility, and hence provides a
mechanical metaphor
which is more appropriate for a distributed-memory parallel processor in which copying is explicit. However, linear logic's lack of sharing may introduce significant inefficiencies of its own.We show an efficient implementation of linear logic called
Linear Lisp
that runs within a constant factor of non-linear logic. This Linear Lisp allows RPLACX operations, and manages storage as safely as a non-linear Lisp, but does not need a garbage collector. Since it offers assignments but no sharing, it occupies a twilight zone between functional languages and imperative languages. Our Linear Lisp Machine offers many of the same capabilities as combinator/graph reduction machines, but without their copying and garbage collection problems.
Feature inversion
Authors: Wong K. C.
Published: November 2005

This paper briefly summarizes the work we have done on language versions determination in distributed systems. It is shown that a computer program can still be successfully compiled, locally or remotely, even though the host node does not support the desired version(s) and/or the program is written in multiple versions, disjoint or not. The approach is especially appropriate for those systems with a high potential to grow and expand frequently.
Empirical measurements of six allocation-intensive C programs
Authors: Zorn Benjamin , Grunwald Dirk
Published: November 2005

Dynamic memory management is an important part of a large class of computer programs and high-performance algorithms for dynamic memory management have been, and will continue to be, of considerable interest. This paper presents empirical data from a collection of six allocation-intensive C programs. Extensive statistics about the allocation behavior of the programs measured, including the distributions of object sizes, lifetimes, and interarrival times, are presented. This data is valuable for the following reasons: first, the data from these programs can be used to design high-performance algorithms for dynamic memory management. Second, these programs can be used as a benchmark test suite for evaluating and comparing the performance of different dynamic memory management algorithms. Finally, the data presented gives readers greater insight into the storage allocation patterns of a broad range of programs. The data presented in this paper is an abbreviated version of more extensive statistics that are publically available on the internet.
Another C Threads library
Authors: Cattaneo G. , Di Giore G. , Ruotolo M.
Published: November 2005

In this paper we present the main results achieved with the implementation of an efficient multithread library, hereinafter called DIA_Thread library, built on the top of a shared memory symmetric multiprocessor environment. The idea which led us to this project was the lack of a
minimal
common layer which, as far the multitasking concerns, should help us to make our applications portable among different architectures and/or operating systems. In fact, there are more and more multiprocessor machines available but it is still difficult to exploit the inherent parallelism of the underlying hardware inside a single user application because the available tools are often different in performance and semantics.This package is intendend to be portable. It consists of less than two thousands lines of C code and only a few lines of assembly code. Moreover bif effort was spent to design the main structures in order to have a package absolutely architecture independent, that is, the dependencies on the host operating system were minimized and no assumption was made on the processor configuration, both on their total number and their basic interprocess communication support.The DIA_Thread library basically provides few functions to activate and manage multiple flows of control with a little extra overhead. The useer application may be split in a virtually unlimited number of threads which will carry on their own task communicating each other by means of common memory areas protected by semaphores.
A new approach to debugging optimized code
Authors: Brooks Gary , Hansen Gilbert J. , Simmons Steve
Published: November 2005

Debugging optimized code is a desirable capability not provided by most current debuggers. Users are forced to debug the unoptimized code when a bug occurs in the optimized version. Current research offers partial solutions for a small class of optimizations, but not a unified approach that handles a wide range of optimizations, such as the sophisticated optimizations performed by supercomputer compilers.

The trend with current research is to make the effects of optimization transparent, i.e., provide the same behavior as that of the unoptimized program. We contend that this approach is neither totally feasible nor entirely desirable. Instead, we propose a new approach based on the premise that one should be able to debug the optimized code. This implies mapping the current state of execution back to the original source, tracking the location of variables, and mapping compiler-synthesized variables back to user-defined induction variables. To aid the user in understanding program behavior, various visual means are provided, e.g., different forms of highlighting and annotating of the source/assembly code. While this unavoidably requires the user to have a basic understanding of the optimizations performed, it permits the user to see what is actually happening, infer the optimizations performed, and detect bugs. An example illustrates the effectiveness of visual feedback.

To support conventional debugger functionality for optimized code, the compiler must generate additional information. Current compiler-debugger interfaces (CDIs) were neither designed to handle this new information nor are they extensible in a straight forward manner. Therefore, a new CDI was designed that supports providing visual feedback and the debugging of optimized code. This paper specifies the details of a new CDI and relates each feature back to the debugger functionality it supports.
Dynascope
Authors: Sosič Rok
Published: November 2005

This paper introduces program
directing
, a new way of program interaction. Directing enables one program, the
director
, to monitor and to control another program, the
executor
. One important application of program directing is human interaction with complex computer simulations.

The Dynascope programming environment is designed specifically to support directing in traditional, compiled languages. It provides a framework and building blocks for easy construction of sophisticated directors. Directors are regular programs that perform the directing of executors through Dynascope primitives. Dynascope is built around the concept of the
execution stream
which provides a complete description of the executor's computational behavior. The source code of executors requires no changes in order to be subjected to directing.

This paper gives an overview of the Dynascope system. Sample applications are presented: debugging register allocation, animation of procedure calls, and a complex artificial life simulation. The performance of Dynascope is illustrated by real time measurements.
The design and implementation of HoME
Authors: Ogata Kazuhiro , Kurihara Satoshi , Inari Mikio , Doi Norihisa
Published: November 2005

HoME is a version of Smalltalk which can be efficiently executed on a multiprocessor and can be executed in parallel by combining a Smalltalk process with a Mach thread and executing the process on the thread. HoME is nearly the same as ordinary Smalltalk except that multiple processes may execute in parallel. Thus, almost all applications running on ordinary Smalltalk can be executed on HoME without changes in their code.

HoME was designed and implemented based on the following fundamental policies: (1) theoretically, an infinite number of processes can become active; (2) the moment a process is scheduled, it becomes active; (3) no process switching occurs; (4) HoME is equivalent to ordinary Smalltalk except for the previous three policies.

The performance of the current implementation of HoME running on OMRON LUNA-88K, which had four processors, was measured by benchmarks which execute in parallel with multiple processes. In all benchmarks, the results showed that HoME's performance is much better than HPS on the same workstation.
Compiling dataflow analysis of logic programs
Authors: Tan Jichang , Lin I-Peng
Published: November 2005

Abstract interpretation is a technique extensively used for global dataflow analyses of logic programs. Existing implementations of abstract interpretation are slow due to interpretive or transforming overhead and the inefficiency in manipulation of global information. Since abstract interpretation mimics standard interpretation, it is a promising alternative to compile abstract interpretation into the framework of the WAM (Warren Abstract Machine) for better performance. In this paper, we show how this approach can be effectively implemented in a low-cost manner. To evaluate the possible benefits of this approach, a prototype dataflow analyzer has been implemented for inference of mode, type and variable aliasing information of logic programs. For a subset of benchmark programs in [15], it significantly improves the performance by a factor of over 150 on the average.
Register allocation for software pipelined loops
Authors: Rau B. R. , Lee M. , Tirumalai P. P. , Schlansker M. S.
Published: November 2005

Software pipelining is an important instruction scheduling technique for efficiently overlapping successive iterations of loops and executing them in parallel. This paper studies the task of register allocation for software pipelined loops, both with and without hardware features that are specifically aimed at supporting software pipelines. Register allocation for software pipelines presents certain novel problems leading to unconventional solutions, especially in the presence of hardware support. This paper formulates these novel problems and presents a number of alternative solution strategies. These alternatives are comprehensively tested against over one thousand loops to determine the best register allocation strategy, both with and without the hardware support for software pipelining.
Probabilistic register allocation
Authors: Proebsting Todd A. , Fischer Charles N.
Published: November 2005

A new global register allocation technique,
probabilistic register allocation
, is described. Probabilistic register allocation quantifies the costs and benefits of allocating variables to registers over live ranges so that excellent allocation choices can be made. Local allocation is done first, and then global allocation is done iteratively beginning in the most deeply nested loops. Because local allocation precedes global allocation, probabilistic allocation does not interfere with the use of well-known, high-quality local register allocation and instruction scheduling techniques.
Rematerialization
Authors: Briggs Preston , Cooper Keith D. , Torczon Linda
Published: November 2005

This paper examines a problem that arises during global register allocation –
rematerialization
. If a value cannot be kept in a register, the allocator should recognize when it is cheaper to recompute the value (rematerialize it) than to store and reload it. Chaitin's original graph-coloring allocator handled simple instance of this problem correctly. This paper details a general solution to the problem and presents experimental evidence that shows its importance.

Our approach is to tag individual values in the procedure's SSA graph with information specifying how it should be spilled. We use a variant of Wegman and Zadeck's
sparse simple constant
algorithm to propagate tags throughout the graph. The allocator then splits live ranges into values with different tags. This isolates those values that can be easily rematerialized from values that require general spilling. We modify the base allocator to use this information when estimating spill costs and introducing spill code.

Our presentation focuses on rematerialization in the context of Chaitin's allocator; however, the problem arises in any global allocator. We believe that our approach will work in other allocators–while the details of implementation will vary, the key insights should carry over directly.
Avoiding unconditional jumps by code replication
Authors: Mueller Frank , Whalley David B.
Published: November 2005

This study evaluates a global optimization technique that avoids unconditional jumps by replicating code. When implemented in the back-end of an optimizing compiler, this technique can be generalized to work on almost all instances of unconditional jumps, including those generated from conditional statements and unstructured loops. The replication method is based on the idea of finding a replacement for each unconditional jump which minimizes the growth in code size. This is achieved by choosing the shortest sequence of instructions as a replacement. Measurements taken from a variety of programs showed that not only the number of executed instructions decreased, but also that the total cache work was reduced (except for small caches) despite increases in code size. Pipelined and superscalar machines may also benefit from an increase in the average basic block size.
Simple and efficient BURS table generation
Authors: Proebsting Todd A.
Published: November 2005

A simple and efficient algorithm for generating bottom-up rewrite system (BURS) tables is described. A small prototype implementation produces tables 10 to 30 times more quickly than the best current techniques. The algorithm does not require novel data structures or complicated algorithmic techniques. Previously published methods for the on-the-fly elimination of states are generalized and simplified to create a new method,
triangle trimming
, that is employed in the algorithm.
Fast mutual exclusion for uniprocessors
Authors: Bershad Brian N. , Redell David D. , Ellis John R.
Published: November 2005

In this paper we describe restartable atomic sequences, an
optimistic
mechanism for implementing simple atomic operations (such as
Test-And-Set
) on a uniprocessor. A thread that is suspended within a restartable atomic sequence is resumed by the operating system at the beginning of the sequence, rather than at the point of suspension. This guarantees that the thread eventually executes the sequence
atomically
. A restartable atomic sequence has significantly less overhead than other software-based synchronization mechanisms, such as kernel emulation or software reservation. Consequently, it is an attractive alternative for use on uniprocessors that do no support atomic operations. Even on processors that do support atomic operations in hardware, restartable atomic sequences can have lower overhead.

We describe different implementations of restartable atomic sequences for the Mach 3.0 and Taos operating systems. These systems' thread management packages rely on atomic operations to implement higher-level mutual exclusion facilities. We show that improving the performance of low-level atomic operations, and therefore mutual exclusion mechanisms, improves application performance.
Closing the window of vulnerability in multiphase memory transactions
Authors: Kubiatowicz John , Chaiken David , Agarwal Anant
Published: November 2005

Multiprocessor architects have begun to explore several mechanisms such as prefetching, context-switching and software-assisted dynamic cache-coherence, which transform single-phase memory transactions in conventional memory systems into multiphase operations. Multiphase operations introduce a
window of vulnerability
in which data can be invalidated before it is used. Losing data due to invalidations introduces damaging livelock situations. This paper discusses the origins of the window of vulnerability and proposes an architectural framework that closes it. The framework is implemented in Alewife, a large-scale multi-processor being built at MIT.
Access normalization
Authors: Li Wei , Pingali Keshav
Published: November 2005

In scalable parallel machines, processors can make local memory accesses much faster than they can make remote memory accesses. In addition, when a number of remote accesses must be made, it is usually more efficient to use block transfers of data rather than to use many small messages. To run well on such machines, software must exploit these features. We believe it is too onerous for a programmer to do this by hand, so we have been exploring the use of restructuring compiler tecnology for this purpose. In this paper, we start with a language like FORTRAN-D with user-specified data distribution and develop a systematic loop transformation strategy called
access normalization
that restructures loop nests to exploit locality and block transfers. We demonstrate the power of our techniques using routines from the BLAS (Basic Linear Algebra Subprograms) library. An important feature of our approach is that we model loop transformations using
invertible
matrices and integer lattice theory, thereby generalizing Banerjee's framework of unimodular matrices [5].
Some comments on “Pitfalls in Prolog Programming”
Authors: Clocksin W F
Published: November 2005

In their useful article "Pitfalls in Prolog Programming", Ng and Ma [1] discuss some ways that novice programmers can be confused while learning Prolog. They suggest that the confusions result from certain properties of Prolog, in particular the way that it diverges from the "ideal" of programming in pure logic. In fact, I suggest that Ng and Ma are attributing to Prolog powers that it simply does not have, and that confusions are usually the result of the novice's misplaced confidence in his abilities to reason about programs.
From semi-syntactic lexical analyzer to a new compiler model
Authors: Shyu Y H
Published: November 2005

This paper introduces the "semi-syntactic lexical analyzer", a new concept of lexical analyzer which is capable of recognizing program fragments. The significant results of such an analyzer are that some syntactic analysis can be omitted, better intermediate or object codes can be generated and a new compiler model is thus derived. The main difference among currently used models and our new model is that currently used models separate input symbol stream into tokens, while our new model separates them into "meaningful units" (simple expressions or even part of an expression) if possible. We found that separating them into meaningful units is much easier for further analysis, translation and optimization.
A variation of Knoop, Rüthing, and Steffen's
Lazy Code Motion
Authors: Drechsler Karl-Heinz , Stadel Manfred P.
Published: November 2005

Morel and Renvoise discussed in 1979 a universal method for global code optimization in a compiler. By suppressing partial redundancies their method achieves several optimization techniques - such as moving loop invariant computations out of a loop or deleting redundant computations - at once. Their algorithm moves computations to earlier places in execution paths to eliminate partial redundancies. The movement is controlled by some heuristics.The heuristics and algorithms used by Morel and Renvoise sometimes cause difficulties for practical use. Subsequent papers partly circumvented these difficulties by slightly modifying the heuristics and the algorithms. Knoop, Rüthing, and Steffen published in their paper
Lazy Code Motion
an optimal algorithm for the elimination of partial redundancies which entirely prevents these difficulties. This paper presents a variant of their algorithm which is better prepared for practical use.
Fips
Authors: Passia Jacek , Löhr Klaus-Peter
Published: November 2005

Fips is a language that integrates functional and imperative programming in a clean way. On the one hand, it is a full-fledged functional language with pattern matching, non-strict functions, polymorphism and data abstraction. On the other hand, it can be viewed as an imperative language which uses side-effect-free functions and, due to the functional heritage, is markedly more expressive than conventional languages. In addition, Fips features an unusual treatment of undefined values which allows for simple exception handling and backtracking.
Monitors and concurrent Pascal
Authors: Hansen Per Brinch
Published: November 2005

This is a personal history of the early development of the monitor concept and its implementation in the programming language Concurrent Pascal. The paper explains how monitors evolved from the ideas of Dahl, Dijkstra, Hoare, and the author (1971-73). At Caltech the author and his students developed and implemented Concurrent Pascal and used it to write several model operating systems (1974-75). A portable implementation of Concurrent Pascal was widely distributed and used for system design (1976-90). The monitor paradigm was also disseminated in survey papers and text books. The author ends the story by expressing his own mixed feelings about monitors and Concurrent Pascal.
A history of ALGOL 68
Authors: Lindsey C. H.
Published: November 2005

ALGOL 68 is a language with a lot of “history”. The reader will hear of discord, resignations, unreadable documents, a minority report, and all manner of politicking. But although ALGOL 68 was produced by a committee (and an unruly one at that), the language itself is no camel. Indeed, the rigorous application of the principle of “orthogonality” makes it one of the cleanest languages around, as I hope to show. Moreover, when the language came to be revised, the atmosphere was quite different enabling a much more robust and readable defining document to be produced in a spirit of true cooperation. There are some lessons here for future language design efforts, but I am not optimistic that they have been learned.
The beginning and development of FORMAC (FORmula MAnipulation Compiler)
Authors: Sammet Jean E.
Published: November 2005

The first widely available programming language for symbolic mathematical computation to have significant practical usage was FORMAC (FORmula MAnipulation Compiler). This paper discusses the earliest conceptual work in detail, and then provides information about later developments of the language. Other languages and systems of the early and mid-1960s are described briefly, with emphasis on their relation to FORMAC. There are also a few glimpses into the software management process at IBM. Finally there is an evaluation of FORMAC and its influence.
Ada—the project
Authors: Whitaker William A.
Published: November 2005

The Department of Defense (DoD) High Order Language Commonality program began in 1975 with the goal of establishing a single high order computer programming language appropriate for DoD real-time embedded computer systems. A High Order Language Working Group (HOLWG) was chartered to formulate the DoD requirements for High Order Languages, to evaluate existing languages against those requirements, and to implement the minimal set of languages required for DoD use. Other parts of the effort included administrative initiatives toward the eventual goal. Specifically, DoD Directive 5000.29 which provided that new defense systems should be programmed in a DoD “approved” and centrally controlled high order language and DoD Instruction 5000.31 which gave the interim defining list
of approved languages. The HOLWG language requirements were widely distributed for comment throughout the military and civil communities worldwide. Each successive version of the requirements, from STRAWMAN through STEELMAN, produced a more refined definition of the proposed language. During the requirement development process, it was determined that the set of requirements generated was both necessary and sufficient for all major DoD applications (and the analogous large commercial applications). Formal evaluations were performed on dozens of existing languages. It was concluded that no existing language could be adopted as a single common high order language for the DoD, but that a single language meeting essentially all the requirements was both feasible and desirable. Four contractors were funded to produce competitive prototypes. A first-phase evaluation reduced the designs to two, which were carried to completion. In turn, a single language design was subsequently chosen. Follow-on steps included the test and evaluation of the language, control of the language and validation of compilers. The production of compilers and a program development and tool environment were to be accomplished separately by the individual Service Components. The general requirements and expectations for the environment and the control of the language were addressed in another iterative series of documents. A language validation capability (the test code suite) and associated facilities were established to assure compliance to the language definition of compilers using the name “Ada”. The name Ada was initially protected by a DoD-owned trademark.
A parallel programming environment supporting multiple data-parallel modules
Authors: Seevers Bradley K. , Quinn Michael J. , Hatcher Philip J.
Published: November 2005

We describe a system that allows programmers to take advantage of both control and data parallelism through multiple data-parallel modules. This system extends C-type stream I/O to include inter-module communication channels. The programmer writes each module separately, then develops a specification that instructs the system how to connect the modules together. Our current system extends the Dataparallel C language and runs on the Intel iWarp computing system.
Typographical extensions for programming languages
Authors: Abrahams Paul W.
Published: November 2005

Using extended typography, we can design programming languages that utilize modem display and input technologies, thus breaking out of the ASCII straitjacket. We assume that a language has three representations: a visual representation that describes its displayed form, an internal representation defined for each implementation, and an interchange representation, expressed in pure ASCII, that is defined across all implementations. Using extended typography we can use distinctive typefaces to indicate keywords, thus removing the need to reserve them, and can introduce a variety of new symbols more meaningful than those used in most current programming languages. One benefit is the possibility of arbitrary user-defined operators. We can also introduce new kinds of brackets and methods of pairing brackets visually. Extended typography also helps to solve the problems of writing programs in languages other than English.
C++ in eight weeks
Authors: Chandra Kailash
Published: November 2005

A course on Object-Oriented programming in C++ was taught for the first time in the summer of 1992 at Pittsburg State University in the Computer Science - Information Systems Department. This paper is based on that experience. It presents the course description, the topics covered, the computational environment, the evaluation activities, the programming assignments, the tests given, and the student evaluations. It is found that the course can be successful if many problems are done from the very beginning and various projects are assigned first without the class concept and then with the class concept. It is also felt that a first course in programming using C++ could be as successful as Pascal, while using C may not be a good idea in the first course.
An approach toward mechanization of acquiring reusable software components
Authors: Fei Zongming , Lu Jian
Published: November 2005

This paper gives a method for acquiring reusable software components automatically. Two categories of resources are distinguished, i.e., reusable patterns and reusable building blocks. It employs explanation--based learning method to analyse the concrete software design and generate its structural description, which, combined with semantic constraints, constitutes the reusable patterns. In order to obtain reusable building blocks, it applies both deduction and induction to construct the functional description of code fragment hierarchically, which , associated with code , is truly reusable in some sense. The ability of the system is enhanced with the acquisition of these reusable components and the scope of solvable problems is enlarged by employing them.
“D
2
R”
Authors: Rost Johann
Published: November 2005

The task-level dataflow language D
2
R ("Dynamic Dataflow Representation") is suggested (Version 1.0). D
2
R uses dynamic branching, loops with data-dependent numbers of iterations and alternatives. The dataflow information can be expressed either as a program text or as graph. Primarily the model has been developed for cooperation with dynamic task scheduling algorithms. Its suitability is demonstrated by examples. The representation supports environments allowing to simultaneously execute multiple user programs ("space sharing") as well as to restrict the assignments of task and data nodes to special processors (e.g. I/O nodes). The system has been implemented using the multi transputer system "DAMP" /Bauch-91/.
How to give a good research talk
Authors: Peyton Jones Simon L. , Hughes John , Launchbury John
Published: November 2005

Giving a good research talk is not easy. We try to identify some things which we have found helpful, in the hope that they may be useful to you.
Programmable syntax macros
Authors: Weise Daniel , Crew Roger
Published: November 2005

Lisp has shown that a programmable syntax macro system acts as an adjunct to the compiler that gives the programmer important and powerful abstraction facilities not provided by the language. Unlike simple token substitution macros, such as are provided by CPP (the C preprocessor), syntax macros operate on Abstract Syntax Trees (ASTs). Programmable syntax macro systems have not yet been developed for syntactically rich languages such as C because rich concrete syntax requires the manual construction of syntactically valid program fragments, which is a tedious, difficult, and error prone process. Also, using two languages, one for writing the program, and one for writing macros, is another source of complexity. This research solves these problems by having the macro language be a minimal extension of the programming language, by introducing explicit code template operators into the macro language, and by using a type system to guarantee, at macro definition time, that all macros and macro functions only produce syntactically valid program fragments. The code template operators make the language context sensitive, which requires changes to the parser. The parser must perform type analysis in order to parse macro definitions, or to parse user code that invokes macros.
Improving the cache locality of memory allocation
Authors: Grunwald Dirk , Zorn Benjamin , Henderson Robert
Published: November 2005

The allocation and disposal of memory is a ubiquitous operation in most programs. Rarely do programmers concern themselves with details of memory allocators; most assume that memory allocators provided by the system perform well. This paper presents a performance evaluation of the reference locality of dynamic storage allocation algorithms based on trace-driven simualtion of five large allocation-intensive C programs. In this paper, we show how the design of a memory allocator can significantly affect the reference locality for various applications. Our measurements show that poor locality in sequential-fit allocation algorithms reduces program performance, both by increasing paging and cache miss rates. While increased paging can be debilitating on any architecture, cache misses rates are also important for modern computer architectures. We show that algorithms attempting to be space-efficient by coalescing adjacent free objects show poor reference locality, possibly negating the benefits of space efficiency. At the other extreme, algorithms can expend considerable effort to increase reference locality yet gain little in total execution performance. Our measurements suggest an allocator design that is both very fast and has good locality of reference.
Using lifetime predictors to improve memory allocation performance
Authors: Barrett David A. , Zorn Benjamin G.
Published: November 2005

Dynamic storage allocation is used heavily in many application areas including interpreters, simulators, optimizers, and translators. We describe research that can improve all aspects of the performance of dynamic storage allocation by predicting the lifetimes of short-lived objects when they are allocated. Using five significant, allocation-intensive C programs, we show that a great fraction of all bytes allocated are short-lived (> 90% in all cases). Furthermore, we describe an algorithm for liftetime prediction that accurately predicts the lifetimes of 42–99% of all objects allocated. We describe and simulate a storage allocator that takes adavantage of lifetime prediction of short-lived objects and show that it can significantly improve a program's memory overhead and reference locality, and even, at times, improve CPU performance as well.
Register allocation with instruction scheduling
Authors: Pinter Shlomit S.
Published: November 2005

We present a new framework in which considerations of both register allocation and instruction scheduling can be applied uniformly and simultaneously. In this framework an optimal coloring of a graph, called the
parallel interference graph
, provides an optimal register allocation and preserves the property that no false dependences are introduced, thus all the options for parallelism are kept for the scheduler to handle. For this framework we provide heuristics for trading off parallel scheduling with register spilling.
Lifetime-sensitive modulo scheduling
Authors: Huff Richard A.
Published: November 2005

This paper shows how to software pipeline a loop for minimal register pressure without sacrificing the loop's minimum execution time. This novel
bidirectional slack-scheduling
method has been implemented in a FORTRAN compiler and tested on many scientific benchmarks. The empirical results—when measured against an absolute lower bound on execution time, and against a novel
schedule-independent
absolute lower bound on register pressure—indicate near-optimal performance.
Experiences using the ParaScope Editor
Authors: Hall Mary W. , Harvey Timothy J. , Kennedy Ken , McIntosh Nathaniel , McKinley Kathryn S. , Oldham Jeffrey D. , Paleczny Michael H. , Roth Gerald
Published: November 2005

The ParaScope Editor is an interactive parallel programming tool that assists knowledgeable users in developing scientific Fortran programs. It displays the results of sophisticated program analyses, provides a set of powerful interactive transformations, and supports program editing. This paper summarizes experiences of scientific programmers and tool designers using the ParaScope Editor. We evaluate existing features and describe enhancements in three key areas: user interface, analysis, and transformation. many existing features prove crucial to successful program parallelization. They include interprocedural array side-effect analysis and program and dependence view filtering. Desirable functionality includes improved program navigation based on performance estimation, incorporating user assertions in analysis and more guidance in selecting transformations. These results offer insights for the authors of a variety of programming tools and parallelizing compilers.
Integrating message-passing and shared-memory
Authors: Kranz David , Johnson Kirk , Agarwal Anant , Kubiatowicz John , Lim Beng-Hong
Published: November 2005

This paper discusses some of the issues involved in implementing a shared-address space programming model on large-scale, distributed-memory multiprocessors. While such a programming model can be implemented on both shared-memory and message-passing architectures, we argue that the transparent, coherent caching of global data provided by many shared-memory architectures is of crucial importance. Because message-passing mechanisms ar much more efficient than shared-memory loads and stores for certain types of interprocessor communication and synchronization operations, hwoever, we argue for building multiprocessors that efficiently support both shared-memory and message-passing mechnisms. We describe an architecture, Alewife, that integrates support for shared-memory and message-passing through a simple interface; we expect the compiler and runtime system to cooperate in using appropriate hardware mechanisms that are most efficient for specific operations. We report on both integrated and exclusively shared-memory implementations of our runtime system and two applications. The integrated runtime system drastically cuts down the cost of communication incurred by the scheduling, load balancing, and certain synchronization operations. We also present preliminary performance results comparing the two systems.
A concurrent copying garbage collector for languages that distinguish (im)mutable data
Authors: Huelsbergen Lorenz , Larus James R.
Published: November 2005

This paper describes the design and implementation of a concurrent compacting garbage collector for languages that distinguish mutable data from immutable data (
e.g.
, ML) as well for languages that manipulate only immutable data (
e.g.
, pure functional languages such as Haskell). The collector runs on shared-memory parallel computers and requires minimal mutator/collector synchronization. No special hardware or operating system support is required.

Our concurrent collector derives from sequential semi-space copying collectors. The collector requires that a heap object includes
forwarding pointer
in addition to its data fields. An access to an immutable object can be satisfied either by the original or the forwarded copy of the object. A mutable object is always accessed through the forwarded copy, if one exists.

Measurements of this collector in a Standard ML compiler on a shared-memory computer indicate that it eliminates perceptible garbage-collection pauses by reclaiming storage in parallel with the computation proper. All observed pause times are less than 20 milliseconds. We describe extensions for the concurrent collection of multiple mutator threads and refinements to our design that can improve its efficiency.
An equational language for data-parallelism
Authors: Rao Pushpa , Walinsky Clifford
Published: November 2005

Data-parallelism provides a clean conceptual framework for parallel programming. We are developing two programming languages: a high level equational language, called EL
*
, and a low-level implementation language. Both languages exploit data-parallelism instead of control-parallelism. EL
*
is a declarative data-parallel language. EL
*
programs are high-level equational specifications that use extensive pattern-matching and recursion. The language's syntax and semantics are intended to be clear and simple. Recursive forms are restricted to enable translation to efficient data-parallel operations. EL
*
programs are compiled into FP
*
, a variant of Backus's FP, where parallel operations are more explicit and low-level. The target language has a rich set of functions for performing communication, and computation. It also has a powerful set of combining forms that generate large highly-parallel functions from smaller program units. Prototype compilers have been implemented for both languages, and they demonstrate good performance. Several linear algebra and non-numeric problems have been programmed with relative ease using EL
*
. We are currently developing compilation techniques for a wider range of scientific problems that have more complex parallel solutions, and are continuing to expand the language's scope.
Transforming high-level data-parallel programs into vector operations
Authors: Prins Jan F. , Palmer Daniel W.
Published: November 2005

Efficient parallel execution of a high-level data-parallel language based on nested sequences, higher order functions and generalized iterators can be realized in the vector model using a suitable representation of nested sequences and a small set of transformational rules to distribute iterators through the constructs of the language.
Generating local addresses and communication sets for data-parallel programs
Authors: Chatterjee Siddhartha , Gilbert John R. , Long Fred J. E. , Schreiber Robert , Teng Shang-Hua
Published: November 2005

Generating local addresses and communication sets is an important issue in distributed-memory implementations of data-parallel languages such as High Performance Fortran. We show that for an array
A
affinely aligned to a
template
that is distributed across
p
processors with a
cyclic(k)
distribution, and a computation involving the regular section
A(l:h:s)
, the local memory access sequence for any processor is characterized by a finite state machine of at most
k
states. We present fast algorithms for computing the essential information about these state machines, and extend the framework to handle multidimensional arrays. We also show how to generate communication sets using the state machine approach. Performance results show that this solution requires very little runtime overhead and acceptable preprocessing time.
Implementing an irregular application on a distributed memory multiprocessor
Authors: Chakrabarti Soumen , Yelick Katherine
Published: November 2005

Parallelism with irregular patterns of data, communication and computation is hard to manage efficiently. In this paper we present a case study of the Gro¨bner basis problem, a symbolic algebra application. We developed an efficient parallel implementation using the following techniques. First, a sequential algorithm was rewritten in a
transition axiom
style, in which computation proceeds by non-deterministic invocations of guarded statements at multiple processors. Next, the algebraic properties of the problem were studied to modify the algorithm to ensure correctness in spite of locally inconsistent views of the share data structures. This was used to design data structures with very little overhead for maintaining consistency. Finally, an application-specific scheduler was designed and tuned to get good performance. Our distributed memory implementation achieves impressive speedups.
Parallelizing algorithms for symbolic computation using MAPLE
Authors: Siegl Kurt
Published: November 2005

||MAPLE|| (speak: parallel Maple) is a portable system for parallel symbolic computation. The system is built as an interface between the parallel declarative programming language Strand and the sequential computer algebra system Maple, thus providing the elegance of Strand and the power of the existing sequential algorithms in Maple.

The implementation of different parallel programming paradigms shows that it is fairly easy to parallelize even complex algebraic algorithms using this system. Sample applications (among them algorithms solving multivariate nonlinear equation systems) are implemented on various parallel architectures. For example a straightforward parallelization of the complex and important problem of real root isolation has been parallelized using a generic Strand program of fewer than 20 lines of code and a slight modification of 5 lines in the original sequential Maple source. Even with such a simple modification we gained a speed-up of 5 times, that is better than those reported by others in the literature.
Leapfrogging
Authors: Wagner David B. , Calder Bradley G.
Published: November 2005

A
future
is a language construct that allows programmers to expose parallelism in applicative languages such as MultiLisp [5] with minimal effort. In this paper we describe a technique for implementing futures, which we call
leapfrogging
, that reduces blocking due to load imbalance. The utility of leapfrogging is enhanced by the fact that it is completely platform-independent, is free from deadlock, and places a bound on stack sizes that is at most a small constant times the maximum stack size encountered during a sequential execution of the same computation. We demonstrate the performance of leapfrogging using a prototype implementation written in C++.
An efficient implementation scheme of concurrent object-oriented languages on stock multicomputers
Authors: Taura Kenjiro , Matsuoka Satoshi , Yonezawa Akinori
Published: November 2005

Several novel techniques for efficient implementtion of concurrent object-oriented languages on general purpose, stock multicomputers are presented. These techniques have been developed in implementing our concurrent object-oriented language ABCL on a Fujitsu Laboratory's experimental multicomputer AP1000 consisting of 512 SPARC chips. The propsed intra-node scheduling mechanism reduces the cost of local message passing. The cost of intra-node asynchronous message passing is about 20 SPARC instructions in the bst case, including locality checking, dynamic method lookup, and scheduling. The minimum latency of asynchronous internode message passing is about 9μs, or about 120 instructions, employing the self-dispatching mechanism independently proposed by Eicken et al. A large scale benchmark which involves 9,000,000 message passings shows 440 times speedup on the 512 nodes system compared to the sequential version of the same algorithm. We rely on simple hardware support for message passing and use no specialized architectural supports for object-oriented computing. Thus, we are able to enjoy the benefits of future progress in standard processor technology. Our result shows that concurrent object-oriented languages can be implemented efficiently on conventional multicomputers.