bluuebunny/crossref_metadata_2025 huggingface dataset:
Interleaving
Authors: Laudon James , Gupta Anoop , Horowitz Mark
Published: November 2005

There is an increasing trend to use commodity microprocessors as the compute engines in large-scale multiprocessors. However, given that the majority of the microprocessors are sold in the workstation market, not in the multiprocessor market, it is only natural that architectural features that benefit only multiprocessors are less likely to be adopted in commodity microprocessors. In this paper, we explore multiple-context processors, an architectural technique proposed to hide the large memory latency in multiprocessors. We show that while current multiple-context designs work reasonably well for multiprocessors, they are ineffective in hiding the much shorter uniprocessor latencies using the limited parallelism found in workstation environments. We propose an alternative design that combines the best features of two existing approaches, and present simulation results that show it yields better performance for both multiprogrammed workloads on a workstation and parallel applications on a multiprocessor. By addressing the needs of the workstation environment, our proposal makes multiple contexts more attractive for commodity microprocessors.
The effectiveness of multiple hardware contexts
Authors: Thekkath Radhika , Eggers Susan J.
Published: November 2005

Multithreaded processors are used to tolerate long memory latencies. By executing threads loaded in multiple hardware contexts, an otherwise idle processor can keep busy, thus increasing its utilization. However, the larger size of a multi-thread working set can have a negative effect on cache conflict misses. In this paper we evaluate the two phenomena together, examining their combined effect on execution time.

The usefulness of multiple hardware contexts depends on: program data locality, cache organization and degree of multiprocessing. Multiple hardware contexts are most effective on programs that have been optimized for data locality. For these programs, execution time dropped with increasing contexts, over widely varying architectures. With unoptimized applications, multiple contexts had limited value. The best performance was seen with only two contexts, and only on uniprocessors and small multiprocessors. The behavior of the unoptimized applications changed more noticeably with variations in cache associativity and cache hierarchy, unlike the optimized programs.

As a mechanism for exploiting program parallelism, an additional processor is clearly better than another context. However, there were many configurations for which the addition of a few hardware contexts brought as much or greater performance than a larger multiprocessor with fewer than the optimal number of contexts.
“Use-once” variables and linear objects
Authors: Baker Henry G.
Published: November 2005

Programming languages should have 'use-once' variables in addition to the usual 'multiple-use' variables. 'Use-once' variables are bound to
linear
(
unshared, unaliased, or singly-referenced
) objects. Linear objects are cheap to access and manage, because they require no synchronization or tracing garbage collection. Linear objects can elegantly and efficiently solve otherwise difficult problems of functional/mostly-functional systems---e.g., in-place updating and the efficient initialization of functional objects. Use-once variables are ideal for directly manipulating
resources
which are inherently linear such as freelists and 'engine ticks' in reflective languages.A 'use-once' variable must be dynamically referenced
exactly once
within its scope. Unreferenced use-once variables must be explicitly killed, and multiply-referenced use-once variables must be explicitly copied; this duplication and deletion is subject to the constraint that some linear datatypes do not support duplication and deletion methods. Use-once variables are bound only to linear objects, which may reference other linear or non-linear objects. Non-linear objects can reference other non-linear objects, but can reference a linear object only in a way that ensures mutual exclusion.Although implementations have long had
implicit
use-once variables and linear objects, most languages do not provide the programmer any help for their utilization. For example, use-once variables allow for the safe/controlled use of reified language implementation objects like single-use continuations.Linear objects and use-once variables map elegantly into dataflow models of concurrent computation, and the graphical representations of dataflow models make an appealing
visual linear programming language
.
ParsesraP
Authors: Beaty Steven J.
Published: November 2005

In the past, there have been many different descriptive languages used to specify the syntax of information read into programs. These types of descriptions have not been used to produce the output of programs. Output has used ad hoc methods. This paper presents a method to use a single specification to produce a consumer of input, and a producer of output.
Umbriel—another minimal programming language
Authors: Terry P. D.
Published: November 2005

Umbriel is the name of a simple Modula-like programming language, expressly intended for teaching introductory imperative programming.Umbriel, like Oberon, is the name of a moon of Uranus. Miranda is the smallest of her moons, but that name is already bespoke in the programming language game. So is Ariel, the original name chosen for the new language.
PROMIS
Authors: Kokol Peter , Žumer Viljem , Brest Janez , Mernik Marjan
Published: November 2005

The application of measurement technology in software engineering was not recognised enough in last decades, but recent trends show that software metrics are becoming more and more important. Indeed the development and use of adequate measurement of software and its design process are essential to the production of cost-effective and quality software. Actually, software metrics are not only significant as analysis instruments, but regarding the present iterative software design paradigms, they are likewise becoming powerful synthesis mechanisms. The main objective of this paper is to show that modern software tools and especially compiler-compilers, metric life cycle model and fractal metrics can improve the situation and make the development and use of software metrics more efficient and effective.
L-systems with inheritance
Authors: Borovikov Igor A.
Published: November 2005

L-objects are introduced as L-systems with some object-oriented extensions. Inheritance is the principal new feature of L-objects. We discuss both the abstract basis and the program implementation of the new L-systems technique. The L-objects programming language defined here brings new qualities to L-systems design: modularity, code reusability, polymorphism and data abstraction.
Dynamically-valued constants
Authors: Schilling Jonathan L.
Published: November 2005

Languages such as Ada and C++ allow programmers to declare an object as a constant, even though the object has a dynamic initial value. The benefits of using this construct are given. A sample of actual C++ code is measured to see how often dynamically-valued constants are used, and how often they could be used. This result is compared to previously published results for Ada sample code, and to some Ada code where this feature was consciously employed. The comparisons indicate that this language feature is generally underused. Possible reasons for this underuse are discussed.
A correspondence between continuation passing style and static single assignment form
Authors: Kelsey Richard A.
Published: November 2005

We define syntactic transformations that convert continuation passing style (CPS) programs into static single assignment form (SSA) and vice versa. Some CPS programs cannot be converted to SSA, but these are not produced by the usual CPS transformation. The CPS→SSA transformation is especially helpful for compiling functional programs. Many optimizations that normally require flow analysis can be performed directly on functional CPS programs by viewing them as SSA programs. We also present a simple program transformation that merges CPS procedures together and by doing so greatly increases the scope of the SSA flow information. This transformation is useful for analyzing loops expressed as recursive procedures.
A simple graph-based intermediate representation
Authors: Click Cliff , Paleczny Michael
Published: November 2005

We present a graph-based intermediate representation (IR) with simple semantics and a low-memory-cost C++ implementation. The IR uses a directed graph with labeled vertices and ordered inputs but unordered outputs. Vertices are labeled with opcodes, edges are unlabeled. We represent the CFG and basic blocks with the same vertex and edge structures. Each opcode is defined by a C++ class that encapsulates opcode-specific data and behavior. We use inheritance to abstract common opcode behavior, allowing new opcodes to be easily defined from old ones. The resulting IR is simple, fast and easy to use.
GC
Authors: Aubry Pascal , Gautier Thierry
Published: November 2005

Based on an abstraction of the time as a discrete logical time, the synchronous languages, armed with a strong semantics, enable the design of safe real-time applications. Some of them are of imperative style, while others are declarative. Academic and industrial teams involved in synchronous programming defined together three intermediate representations, on the way to standardization:

• IC, a parallel format of imperative style,

• GC, a parallel format of data-flow style,

• OC, a sequential format to describe automata.

In this paper, we describe more specifically the format GC, and its links with the synchronous data-flow language SIGNAL. Thanks to the first experimentations, GC reveals itself as a powerful representation for graph transformations, code production, optimization, hardware synthesis, etc.
Verification of ANDF components
Authors: Broustaut Frédéric , Fabre Christian , de Ferrière François , Ivanov Éric , Fiorentini Mauro
Published: November 2005

This paper presents validation work done on ANDF at the Open Software Foundation Research Institute. The ultimate ANDF scenario splits a compiler into two separate components (producer/installer). This changes the compiler validation process as the two components have to be validated separately. This paper presents the originality and the difficulties of such an approach and summarizes the status of two pieces of software to which the OSF-RI has contributed: the
ANDF Validation Suite
and the
General ANDF Interpreter
.
Parallel skeletons for structured composition
Authors: Darlington John , Guo Yi-ke , To Hing Wing , Yang Jin
Published: November 2005

In this paper, we propose a straightforward solution to the problems of compositional parallel programming by using skeletons as the uniform mechanism for structured composition. In our approach parallel programs are constructed by composing procedures in a conventional base language using a set of high-level, pre-defined, functional, parallel computational forms known as
skeletons
. The ability to compose skeletons provides us with the essential tools for building further and more complex application-oriented skeletons specifying important aspects of parallel computation. Compared with the process network based composition approach, such as PCN, the skeleton approach abstracts away the fine details of connecting communication ports to the higher level mechanism of making data distributions conform, thus avoiding the complexity of using lower level ports as the means of interaction. Thus, the framework provides a natural integration of the compositional programming approach with the data parallel programming paradigm.
Software caching and computation migration in Olden
Authors: Carlisle Martin C. , Rogers Anne
Published: November 2005

The goal of the
Olden
project is to build a system that provides parallelism for general purpose C programs with minimal programmer annotations. We focus on programs using dynamic structures such as trees, lists, and DAGs. We demonstrate that providing both software caching and computation migration can improve the performance of these programs, and provide a compile-time heuristic that selects between them for each pointer dereference. We have implemented a prototype system on the Thinking Machines CM-5. We describe our implementation and report on experiments with ten benchmarks.
Efficient support for irregular applications on distributed-memory machines
Authors: Mukherjee Shubhendu S. , Sharma Shamik D. , Hill Mark D. , Larus James R. , Rogers Anne , Saltz Joel
Published: November 2005

Irregular computation problems underlie many important scientific applications. Although these problems are computationally expensive, and so would seem appropriate for parallel machines, their irregular and unpredictable run-time behavior makes this type of parallel program difficult to write and adversely affects run-time performance.

This paper explores three issues—partitioning, mutual exclusion, and data transfer—crucial to the efficient execution of irregular problems on distributed-memory machines. Unlike previous work, we studied the same programs running in three alternative systems on the same hardware base (a Thinking Machines CM-5): the CHAOS irregular application library, Transparent Shared Memory (TSM), and eXtensible Shared Memory (XSM). CHAOS and XSM performed equivalently for all three applications. Both systems were somewhat (13%) to significantly faster (991%) than TSM.
Fuzzy array dataflow analysis
Authors: Collard Jean-François , Barthou Denis , Feautrier Paul
Published: November 2005

Exact array dataflow analysis can be achieved in the general case if the only control structures are
do
-loops and structural
if
s, and if loop counter bounds and array subscripts are affine expressions of englobing loop counters and possibly some integer constants. In this paper, we begin the study of dataflow analysis of dynamic control programs, where arbitrary
if
s and
while
s are allowed. In the general case, this dataflow analysis can only be fuzzy.
Optimal mapping of sequences of data parallel tasks
Authors: Subhlok Jaspal , Vondran Gary
Published: November 2005

Many applications in a variety of domains including digital signal processing, image processing and computer vision are composed of a sequence of tasks that act on a stream of input data sets in a pipelined manner. Recent research has established that these applications are best mapped to a massively parallel machine by dividing the tasks into modules and assigning a subset of the available processors to each module. This paper addresses the problem of optimally mapping such applications onto a massively parallel machine. We formulate the problem of optimizing throughput in task pipelines and present two new solution algorithms. The formulation uses a general and realistic model for inter-task communication, takes memory constraints into account, and addresses the entire problem of mapping which includes clustering tasks into modules, assignment of processors to modules, and possible replication of modules. The first algorithm is based on dynamic programming and finds the optimal mapping of
k
tasks onto
P
processors in

O(P
4
k
2
)

time. We also present a heuristic algorithm that is linear in the number of processors and establish with theoretical and practical results that the solutions obtained are optimal in practical situations. The entire framework is implemented as an automatic mapping tool for the Fx parallelizing compiler for High Performance Fortran. We present experimental results that demonstrate the importance of choosing a good mapping and show that the methods presented yield efficient mappings and predict optimal performance accurately.
Automatic alignment of array data and processes to reduce communication time on DMPPs
Authors: Philippsen Michael
Published: November 2005

This paper investigates the problem of aligning array data and processes in a distributed-memory implementation. We present complete algorithms for compile-time analysis, the necessary program restructuring, and subsequent code-generation, and discuss their complexity. We finally evaluate the practical usefulness by quantitative experiments.

The technique presented analyzes complete programs, including branches, loops, and nested parallelism. Alignment is determined with respect to offset, stride, and general axis relations. Placement of both data and processes are computed in a unifying framework based on an extended preference graph and its analysis. Dynamic redistributions are derived.

The experimental results are very encouraging. The optimization algorithms implemented in our Modula-2* compiler improved the execution times of the programs by an average over 40% on a MasPar MP-1 with 16384 processors.
Interactive learning in a beginning CS course
Authors: Chowdhury Ashraful A.
Published: November 2005

The learning ability of students depends on how they learn and on how they acquire the knowledge. Studies indicate that, in general, 11% of people learn through hearing and 83% through sight. Also, people tend to remember 10% of what they read, 20% of what they hear, 30% of what they see, and 90% of what they say as they do things. While these figures are only approximate and subject to exceptions, they do indicate how teaching techniques might be improved.
Object-oriented programming for embedded systems
Authors: Maclean Stuart , Smith Sean
Published: November 2005

Embedded systems are hard to program. Much of the effort is concentrated on processor-management code, effort totally unrelated to the application being built. Concurrent programming in embedded systems introduces even more problems --- mechanisms are needed to protect critical data areas. The application of object modeling to such mechanisms results in numerous benefits: fewer programming errors, enhanced portability and improved reuse. We present some simple in techniques for realising these benefits.
Compiler support for software-based cache partitioning
Authors: Mueller Frank
Published: November 2005

Cache memories have become an essential part of modern processors to bridge the increasing gap between fast processors and slower main memory. Until recently, cache memories were thought to impose unpredictable execution time behavior for hard real-time systems. But recent results show that the speedup of caches can be exploited without a significant sacrifice of predictability. These results were obtained under the assumption that real-time tasks be scheduled
non-preemptively
.This paper introduces a method to maintain predictability of execution time within
preemptive
, cached real-time systems and discusses the impact on compilation support for such a system. Preemptive systems with caches are made predictable via software-based cache partitioning. With this approach, the cache is divided into distinct portions associated with a real-time task, such that a task may only use its portion. The compiler has to support instruction and data partitioning for each task. Instruction partitioning involves non-linear control-flow transformations, while data partitioning involves code transformations of data references. The impact on execution time of these transformations is also discussed.
Using e-mail as a classroom tool
Authors: Workman Mark E.
Published: November 2005

At Frank Phillips College all students taking Computing Principles (mostly CIS majors) and students taking Microcomputer Applications (many majors) have e-mail accounts. Access to e-mail is through networked on-campus labs. In these introductory computing classes, students are required to use e-mail to express concerns and submit some assignments to the instructor. At times, students must use e-mail for other purposes such as to receive class assignments and projects or to announce information concerning special events.
Using
Karel the robot
as a classroom motivator
Authors: Larason Katherine
Published: November 2005

Computer science teachers often have occasion to discuss and explain the ideas of data, programs, and algorithms to computer novices. These ideas can be explained in general terms or as an introduction to further study. Computer literacy textbooks devote considerable space to develop fundamental software concepts. The first chapters of CS1 texts extend the discussion to topics such as abstraction, modularization, and information hiding.
The top 10 reasons why OOP can't be taught in CS1
Authors: Decker Rick , Hirshfield Stuart
Published: November 2005

Over the past year we have changed our CS 1 course from a standard Pascal-based, procedural programming course into one that emphasizes C++ and object-oriented programming (OOP). While our experience to date indicates that this was a good decision for both our students and our department, the decision did not come easy. We struggled long and hard with many, if not most, of the questions and issues that have come to be associated with teaching OOP to undergraduates. This paper recounts our struggles, and presents our responses to the more serious of the pedagogical questions that we considered. In hindsight, many of the reasons we came up with for not using OOP in CS1 are seen to reflect our lack of understanding of the paradigm, our fear of the language, and our past experience teaching Pascal and the procedural paradigm. Furthermore, we believe that our reservations (which appear to be quite common) stemmed from a growing body of misleading OOP folklore that is contrary to our experience and that this paper attempts to dispel.
Lessons from the experiences of leading-edge object technology projects in Hewlett-Packard
Authors: Malan Ruth , Coleman Derek , Letsinger Reed
Published: November 2005

A study of leading-edge HP object technology projects was conducted to understand the current state of object-oriented practice, and projects' object-oriented analysis and design method needs. In this paper, we distill general best practices and pitfalls from the lessons learned in these projects. We also consider how the OOA/D methods support what the businesses have set out to accomplish, where they are deficient, and how they are being modified to better support project needs. We draw upon these lessons to point out areas where OOA/D methods and CASE tools require improvement.
Using a prototype-based language for user interface
Authors: Smith Walter R.
Published: November 2005

Object-oriented user interface frameworks are usually implemented in a class-based language. We chose instead to develop a prototype-based language, NewtonScript, for this purpose. We found that prototype inheritance has compelling advantages over classes in the domain of user interface programming, and can help overcome the memory constraints of a small machine.
Type feedback vs. concrete type inference
Authors: Agesen Ole , Hölzle Urs
Published: November 2005

Two promising optimization techniques for object-oriented languages are type feedback (profile-based receiver class prediction) and concrete type inference (static analysis). We directly compare the two techniques, evaluating their effectiveness on a suite of 23 S
ELF
programs while keeping other factors constant.Our results show that both systems inline over 95% of all sends and deliver similar overall performance with one exception: S
ELF
's automatic coercion of machine integers to arbitrary-precision integers upon overflow confounds type inference and slows down arithmetic-intensive benchmarks.We discuss several other issues which, given the comparable run-time performance, may influence the choice between type feedback and type inference.
Bidirectional object layout for separate compilation
Authors: Myers Andrew C.
Published: November 2005

Existing schemes for object layout and dispatch in the presence of multiple inheritance and separate compilation waste space and are slower than systems with single inheritance. This paper describes the
bidirectional object layout
, a new scheme for object layout that produces smaller objects and faster method invocations than existing schemes by automatically optimizing particular uses of multiple inheritance. The bidirectional object layout is used for the programming language Theta, and is applicable to languages like C++. This paper also demonstrates how to efficiently implement method dispatch when method signatures are allowed to change in subclasses. Most current statically compiled languages require identical signatures for efficiency.
Sound polymorphic type inference for objects
Authors: Eifrig Jonathan , Smith Scott , Trifonov Valery
Published: November 2005

A polymorphic, constraint-based type inference algorithm for an object-oriented language is defined. A generalized form of type, polymorphic
recursively constrained
types, are inferred. These types are expressive enough for typing objects, since they generalize recursive types and F-bounded polymorphism. The well-known tradeoff between inheritance and subtyping is mitigated by the type inference mechanism. Soundness and completeness of type inference are established.
On the semantic diversity of delegation-based programming languages
Authors: Malenfant J.
Published: November 2005

The prototype-based programming model has always been difficult to characterize precisely. Its basic principle advocates concrete objects as the only mean to model concepts, yet current languages promote methodologies reintroducing abstract constructions to manage efficiently groups of similar objects. In this paper, we propose a rational reconstruction of delegation-based programming languages that identifies programming models going beyond traditional prototypes. We also introduce a new classification of delegation-based languages, which clarifies these models, and we discuss their relative merits. We finally bring to the fore the existence of more and more structured delegation-based languages forming a continuum between pure prototype-based languages and class-based ones.
Subject-oriented composition rules
Authors: Ossher Harold , Kaplan Matthew , Harrison William , Katz Alexander , Kruskal Vincent
Published: November 2005

Subject-oriented programming supports composition of object-oriented programs or program fragments called
subjects
. This paper presents an approach to the
composition rules
used to specify composition details. Rules can be generic, allowing different subrules to be "plugged into" higher-level rules, and they include a means of specifying exceptions to general rules. We give definitions of a number of useful, generic rules, including
merge
and
override
, as a first step towards a generally-useful composition rule library. We also outline an object-oriented framework for implementing rules, which we are currently building as part of our support for subject-oriented programming in C++.
Compiling away the meta-level in object-oriented concurrent reflective languages using partial evaluation
Authors: Masuhara Hidehiko , Matsuoka Satoshi , Asai Kenichi , Yonezawa Akinori
Published: November 2005

Meta-level programmability is beneficial for parallel/distributed object-oriented computing to improve performance, etc. The major problem, however, is
interpretation overhead
due to mta-circular interpretation. To solve this problem, we propose a compilation framework for object-oriented concurrent reflective languages using partial evaluation. Since traditional partial evaluators do not allow us to directly deal with meta-circular interpreters written with concurrent objects, we devised techniques such as pre-/post-processing, a new proposed
preaction
extension to partial evaluation in order to handle side-effects, etc. Benchmarks of a prototype compiler for our language ABCL/R3 indicate that (1) the meta-level interpretation is essentially 'compiled away,' and (2) mta-level optimizations in a parallel application, running on a Fujitsu MPP AP1000, exhibits only 10--30% overhead compared to the hand-crafted source-level optimization in a non-reflective language.
A framework for network protocol software
Authors: Hüni Hermann , Johnson Ralph , Engel Robert
Published: November 2005

Writing software to control networks is important and difficult. It must be efficient, reliable, and flexible. Conduits+ is a framework for network software that has been used to implement the signalling system of a mullti-protocol ATM access switch. An earlier version was used to implement TCP/IP. It reduces the complexity of network software, makes it easier to extend or modify network protocols, and is sufficiently efficient. Conduits+ shows the power of a componentized object-oriented framework and of common object-oriented design patterns.
Creating the architecture of a manufacturing framework by design patterns
Authors: Schmid Hans Albrecht
Published: November 2005

The class and interaction structure of object-oriented designs may become fairly complex, and consequently difficult to develop and understand. Design patterns allow to govern this complexity. This paper presents the design process of a domain-specific black-box framework for the control of automated manufacturing systems. The design is performed as a sequence of transformation steps, guided by the use of generative design patterns. Starting out from a domain-specific model, which does not provide a degree of reusability sufficiently high for a framework, the transformation steps increase the reusability until a satisfactory degree is reached. The resulting class and interaction structure allows to create each application of the considered manufacturing subdomain by selecting, configuring and parameterizing of the framework classes.
Problem-oriented object memory
Authors: Kristensen Anders , Low Colin
Published: November 2005

This paper presents the notion of problem-oriented object memory, and its realization in a distributed object-based programming system,
Penumbra
. This system allows location transparent object invocation, object migration and caching. Its distinguishing feature, however, is its support for problem-oriented object sharing.Problem-oriented object memory is an object model that allows exploitation of application specific semantics by relaxing strict consistency in favour of performance.Our work addresses the problem of achieving scalability of shared write-intensive data in an environment of networked workstations. We have successfully applied the presented ideas to the management of a highly demanding telecoms application.
Evolving to objects—the Witches' Brew
Authors: Barton Don , Arnold Tom
Published: November 2005

"Double, double toil and trouble, fire burn and cauldron bubble" … chant the witches of Macbeth. Take a corporation with a rich, decades-old history of providing on-line services on MVS mainframes, coupled with a vision of the future including OO design and programming, DCE for client-server infrastructure, heterogeneous platform mixes across the Unix and PC worlds, and plan to tie that back to the established systems - and you have a Witches' Brew of your own. The question for our project has been "How to introduce OO technology into an existing project framework with the least effort and most benefit?". Recent industry experience reports detailing the blending of OO and DCE indicate that this has not been easy; our experience confirms that, but our approach has allowed us to utilize the strengths of OO to minimize the complexities inherent in the mix.
Flow-sensitive interprocedural constant propagation
Authors: Carini Paul R. , Hind Michael
Published: November 2005

We present a flow-sensitive interprocedural constant propagation algorithm, which supports recursion while only performing one flow-sensitive analysis of each procedure. We present experimental results which show that this method finds substantially more constants than previous methods and is efficient in practice. We introduce new metrics for evaluating interprocedural constant propagation algorithms which measure the number of interprocedural constant values that are propagated. We use these metrics to provide further experimental results for our algorithm.
Corpus-based static branch prediction
Authors: Calder Brad , Grunwald Dirk , Lindsay Donald , Martin James , Mozer Michael , Zorn Benjamin
Published: November 2005

Correctly predicting the direction that branches will take is increasingly important in today's wide-issue computer architectures. The nameprogram-basedbranch prediction is given to static branch prediction techniques that base their prediction on a program's structure. In this paper, we investigate a new approach to program-based branch prediction that uses a body of existing programs to predict the branch behavior in a new program. We call this approach to program-based branch prediction,evidence-based static prediction, or ESP. The main idea of ESP is that the behavior of acorpusof programs can be used to infer the behavior of new programs. In this paper, we use a neural network to map static features associated with each branch to the probability that the branch will be taken. ESP shows significant advantages over other prediction mechanisms. Specifically, it is a program-based technique, it is effective across a range of programming languages and programming styles, and it does not rely on the use of expert-defined heuristics.

In this paper, we describe the application of ESP to the problem of branch prediction and compare our results to existing program-based branch predictors. We also investigate the applicability of ESP across computer architectures, programming languages, compilers, and run-time systems. Averaging over a body of 43 C and Fortran programs, ESP branch prediction results in a miss rate of 20%, as compared with the 25% miss rate obtained using the best existing program-based heuristics.
Simple and effective link-time optimization of Modula-3 programs
Authors: Fernández Mary F.
Published: November 2005

Modula-3 supports development of modular programs by separating an object's interface from its implementation. This separation induces a runtime overhead in the implementation of objects, because it prevents the compiler from having complete information about a program's type hierarchy. This overhead can be reduced at link time, when the entire type hierarchy becomes available. We describe opportunities for link-time optimization of Modula-3, present two link-time optimizations that reduce the runtime costs of Modula-3's opaque types and methods, and show how link-time optimization could provide C++ which the benefits of opaques types at no additional runtime cost.

Our optimization techniques are implemented in mld, a retargetable linker for the MIPS, SPARC, and Intel 486, mld links a machine-independent intermediate code that is suitable for link-time optimization and code generation. Linking intermediate code simplifies implementation of the optimizations and makes it possible to evaluate them on a wide range of architectures. mld's optimizations are effective: they reduce the total number of instructions executed by up to 14% and convert as many as 79% of indirect calls to direct calls.
Better static memory management
Authors: Aiken Alexander , Fähndrich Manuel , Levien Raph
Published: November 2005

Static memory management replaces runtime garbage collection with compile-time annotations that make all memory allocation and deallocation explicit in a program. We improve upon the Tofte/Talpin region-based scheme for compile-time memory management[TT94]. In the Tofte/Talpin approach, all values, including closures, are stored in regions. Region lifetimes coincide with lexical scope, thus forming a runtime stack of regions and eliminating the need for garbage collection. We relax the requirement that region lifetimes be lexical. Rather, regions are allocated late and deallocated as early as possible by explicit memory operations. The placement of allocation and deallocation annotations is determined by solving a system of constraints that expresses all possible annotations. Experiments show that our approach reduces memory requirements significantly, in some cases asymptotically.
Optimizing parallel programs with explicit synchronization
Authors: Krishnamurthy Arvind , Yelick Katherine
Published: November 2005

We present compiler analyses and optimizations for explicitly parallel programs that communicate through a shared address space. Any type of code motion on explicitly parallel programs requires a new kind of analysis to ensure that operations reordered on one processor cannot be observed by another. The analysis, based on work by Shasha and Snir, checks for cycles among interfering accesses. We improve the accuracy of their analysis by using additional information from post-wait synchronization, barriers, and locks.

We demonstrate the use of this analysis by optimizing remote access on distributed memory machines. The optimizations include
message pipelining
, to allow multiple outstanding remote memory operations, conversion of two-way to one-way communication, and elimination of communication through data re-use. The performance improvements are as high as 20-35% for programs running on a CM-5 multiprocessor using the Split-C language as a global address layer.
The LRPD test
Authors: Rauchwerger Lawrence , Padua David
Published: November 2005

Current parallelizing compilers cannot identify a significant fraction of parallelizable loops because they have complex or statically insufficiently defined access patterns. As parallelizable loops arise frequently in practice, we advocate a novel framework for their identification: speculatively execute the loop as a doall, and apply a fully parallel data dependence test to determine if it had any cross-iteration dependences; if the test fails, then the loop is re-executed serially. Since, from our experience, a significant amount of the available parallelism in Fortran programs can be exploited by loops transformed through
privatization
and
reduction parallelization
, our methods can speculatively apply these transformations and then check their validity at run-time. Another important contribution of this paper is a novel method for
reduction recognition
which goes beyond syntactic pattern matching; it detects at run-time if the values stored in an array participate in a reduction operation, even if they are transferred through private variables and/or are affected by statically unpredictable control flow. We present experimental results on loops from the PERFECT Benchmarks which substantiate our claim that these techniques can yield significant speedups which are often superior to those obtainable by inspector/executor methods.
Tile size selection using cache organization and data layout
Authors: Coleman Stephanie , McKinley Kathryn S.
Published: November 2005

When dense matrix computations are too large to fit in cache, previous research proposes tiling to reduce or eliminate capacity misses. This paper presents a new algorithm for choosing problem-size dependent tile sizes based on the cache size and cache line size for a direct-mapped cache. The algorithm eliminates both capacity and self-interference misses and reduces cross-interference misses. We measured simulated miss rates and execution times for our algorithm and two others on a variety of problem sizes and cache organizations. At higher set associativity, our algorithm does not always achieve the best performance. However on direct-mapped caches, our algorithm improves simulated miss rates and measured execution times when compared with previous work.
Garbage collection using a dynamic threatening boundary
Authors: Barrett David A. , Zorn Benjamin G.
Published: November 2005

Generational techniques have been very successful in reducing the impact of garbage collection algorithms upon the performance of programs. However, all generational algorithms occasionally promote objects that later become garbage, resulting in an accumulation of garbage in older generations. Reclaiming this
tenured
garbage without resorting to collecting the entire heap is a difficult problem. In this paper, we describe a mechanism that extends existing generational collection algorithms by allowing them to reclaim tenured garbage more effectively. In particular, our
dynamic threatening boundary
mechanism divides memory into two spaces, one for shortlived, and another for long-lived objects. Unlike previous work, our collection mechanism can dynamically adjust the boundary between these two spaces either forward or backward in time, essentially allowing data to become untenured. We describe an implementation of the dynamic threatening boundary mechanism and quantify its associated costs. We also describe a policy for setting the threatening boundary and evaluate its performance relative to existing generational collection algorithms. Our results show that a policy that uses the dynamic threatening boundary mechanism is effective at reclaiming tenured garbage.
A comparative study of linked list sorting algorithms
Authors: Shene Ching-Kuang
Published: November 2005

Carraway recently published an article [2] describing a sorting algorithm (the sediment sort) for doubly linked lists. He claimed that the sediment sort is one of the fastest and most efficient sorts for linked list, and planned to determine its complexity. In this article, a comparative study will be presented to show that the sediment sort is only a minor variation of the bubble sort which has been known to the computer science community for more than three decades and that the sediment sort is perhaps the slowest algorithm for sorting linked lists.
Functional back-ends within the lambda-sigma calculus
Authors: Hardin Thérèse , Maranget Luc , Pagano Bruno
Published: November 2005

We define a weak λ-calculus, λσ
w
, as a subsystem of the full λ-calculus with explicit substitutions λσ⇑. We claim that λσ
w
could be the archetypal output language of functional compilers, just as the λ-calculus is their universal input language. Furthermore, λσ⇑ could be the adequate theory to establish the correctness of simplified functional compilers. Here, we illustrate these claims by proving the correctness of two simplified compilers and runtime systems modeled as abstract machines. We first present the Krivine machine. Then, we give the first formal proofs of Cardelli's FAM and of its compiler.
Storage use analysis and its applications
Authors: Serrano Manuel , Feeley Marc
Published: November 2005

In this paper we present a new program analysis method which we call
Storage Use Analysis
. This analysis deduces how objects are used by the program and allows the optimization of their allocation. This analysis can be applied to both statically typed languages (e.g. ML) and latently typed languages (e.g. Scheme). It handles side-effects, higher order functions, separate compilation and does not require CPS transformation. We show the application of our analysis to two important optimizations: stack allocation and unboxing. The first optimization replaces some heap allocations by stack allocations for user and system data storage (e.g. lists, vectors, procedures). The second optimization avoids boxing some objects. This analysis and associated optimitations have been implemented in the Bigloo Scheme/ML compiler. Experimental results show that for many allocation intensive programs we get a significant speedup. In particular, numerically intensive programs are almost 20 times faster because floating point numbers are unboxed and no longer heap allocated.
Deriving structural hylomorphisms from recursive definitions
Authors: Hu Zhenjiang , Iwasaki Hideya , Takeichi Masato
Published: November 2005

In functional programming, small programs are often glued together to construct a complex program. Program fusion is an optimizing process whereby these small programs are fused into a single one and intermediate data structures are removed. Recent work has made it clear that this process is especially successful if the recursive definitions are expressed in terms of hylomorphisms. In this paper, we propose an algorithm which can automatically turn all practical recursive definitions into structural hylomorphisms making program fusion be easily applied.
Optimality and inefficiency
Authors: Lawall Julia L. , Mairson Harry G.
Published: November 2005

We investigate the computational efficiency of the
sharing graphs
of Lamping [Lam90], Gonthier, Abadi, and Lévy [GAL92], and Asperti [Asp94], designed to effect so-called
optimal evaluation
, with the goal of reconciling optimality, efficiency, and the clarification of reasonable cost models for the λ-calculus. Do these graphs suggest reasonable cost models for the λ-calculus? If they are optimal, are they efficient?We present a brief survey of these optimal evaluators, identifying their common characteristics, as well as their shared failures. We give a lower bound on the efficiency of sharing graphs by identifying a class of λ-terms that are normalizable in Θ(
n
) time, and require Θ(
n
) "fan interactions," but require Ω(2

n

) bookkeeping steps. For [GAL92], we analyze this anomaly in terms of the dynamic maintenance of deBruijn indices for intermediate terms. We give another lower bound showing that sharing graphs can do Ω(2

n

) work (via fan interactions) on graphs that have no β-redexes. Finally, we criticize a proposed cost model for λ-calculus given by Frandsen and Sturtivant [FS91], showing by example that the model does not take account of the size of intermediate forms. Our example is a term requiring Θ(2

n

) steps while having proposed cost Θ(
n
). We propose some cost models that both reflect this parameter, and simultaneously reconcile key concepts from optimal reduction.
Inductive, coinductive, and pointed types
Authors: Howard Brian T.
Published: November 2005

An extension of the simply-typed lambda calculus is presented which contains both well-structured inductive and coinductive types, and which also identifies a class of types for which general recursion is possible. The motivations for this work are certain natural constructions in category theory, in particular the notion of an algebraically bounded functor, due to Freyd. We propose that this is a particularly elegant core language in which to work with recursive objects, since the potential for general recursion is contained in a single operator which interacts well with the facilities for bounded iteration and coiteration.
The semantics of Scheme with future
Authors: Moreau Luc
Published: November 2005

We present the formal semantics of future in a Scheme-like language which has both side-effects and first-class continuations. Correctness is established by proving that programs annotated by future have the same observable behaviour as their non-annotated counterparts, even though evaluation may be parallel.
Cogen in six lines
Authors: Thiemann Peter J.
Published: November 2005

We have designed and implemented a program-generator generator (PGG) for an untyped higher-order functional programming language. The program generators perform continuation-based multi-level offline specialization and thus combine the most powerful and general offline partial evaluation techniques. The correctness of the PGG is ensured by deriving it from a multi-level specialize. Our PGG is extremely simple to implement due to the use of multi-level techniques and higher-order abstract syntax.
A provable time and space efficient implementation of NESL
Authors: Blelloch Guy E. , Greiner John
Published: November 2005

In this paper we prove time and space bounds for the implementation of the programming language NESL on various parallel machine models. NESL is a sugared typed λ-calculus with a set of array primitives and an explicit parallel map over arrays. Our results extend previous work on provable implementation bounds for functional languages by considering space and by including arrays. For modeling the cost of NESL we augment a standard call-by-value operational semantics to return two cost measures: a DAG representing the sequential dependence in the computation, and a measure of the space taken by a sequential implementation. We show that a NESL program with
w
work (nodes in the DAG),
d
depth (levels in the DAG), and
s
sequential space can be implemented on a
p
processor butterfly network, hypercube, or CRCW PRAM using
O
(
w/p
+
d
log
p
) time and
O
(
s
+
dp
log
p
) reachable space.
1
For programs with sufficient parallelism these bounds are optimal in that they give linear speedup and use space within a constant factor of the sequential space.