bluuebunny/crossref_metadata_2025 huggingface dataset:
ECOSystem
Authors: Zeng Heng , Ellis Carla S. , Lebeck Alvin R. , Vahdat Amin
Published: November 2005

Energy consumption has recently been widely recognized as a major challenge of computer systems design. This paper explores how to support energy as a first-class operating system resource. Energy, because of its global system nature, presents challenges beyond those of conventional resource management. To meet these challenges we propose the Currentcy Model that unifies energy accounting over diverse hardware components and enables fair allocation of available energy among applications. Our particular goal is to extend battery lifetime by limiting the average discharge rate and to share this limited resource among competing task according to user preferences. To demonstrate how our framework supports explicit control over the battery resource we implemented ECOSystem, a modified Linux, that incorporates our currentcy model. Experimental results show that ECOSystem accurately accounts for the energy consumed by asynchronous device operation, can achieve a target battery lifetime, and proportionally shares the limited energy resource among competing tasks.
Cool-Mem
Authors: Ashok Raksit , Chheda Saurabh , Moritz Csaba Andras
Published: November 2005

This paper presents Cool-Mem, a family of memory system architectures that integrate conventional memory system mechanisms, energy-aware address translation, and compiler-enabled cache disambiguation techniques, to reduce energy consumption in general purpose architectures. It combines statically speculative cache access modes, a dynamic CAM based Tag-Cache used as backup for statically mispredicted accesses, various conventional multi-level associative cache organizations, embedded protection checking along all cache access mechanisms, as well as architectural organizations to reduce the power consumed by address translation in virtual memory. Because it is based on speculative static information, the approach removes the burden of provable correctness in compiler analysis passes that extract static information. This makes Cool-Mem applicable for large and complex applications, without having any limitations due to complexity issues in the compiler passes or the presence of precompiled static libraries. Based on extensive evaluation, for both SPEC2000 and Mediabench applications, 12% to 20% total energy savings are obtained in the processor, with performance ranging from 1.2% degradation to 8% improvement, for the applications studied.
Joint local and global hardware adaptations for energy
Authors: Sasanka Ruchira , Hughes Christopher J. , Adve Sarita V.
Published: November 2005

This work concerns algorithms to control energy-driven architecture adaptations for multimedia applications, without and with dynamic voltage scaling (DVS). We identify a broad design space for adaptation control algorithms based on two attributes: (1) when to adapt or
temporal
granularity and (2) what structures to adapt or
spatial
granularity. For each attribute, adaptation may be
global
or
local.
Our previous work developed a temporally and spatially global algorithm. It invokes adaptation at the granularity of a full frame of a multimedia application (temporally global) and considers the entire hardware configuration at a time (spatially global). It exploits int
er-
frame execution time variability, slowing computation just enough to eliminate idle time before the real-time deadline.This paper explores temporally and spatially local algorithms and their integration with the previous global algorithm. The local algorithms invoke architectural adaptation within an application frame to exploit int
ra-
frame execution variability, and attempt to save energy without affecting execution time. We consider local algorithms previously studied for non-real-time applications as well as propose new algorithms. We find that, for systems without and with DVS, the local algorithms are effective in saving energy for multimedia applications, but the new integrated global and local algorithm is best for the systems and applications studied.
Design and evaluation of compiler algorithms for pre-execution
Authors: Kim Dongkeun , Yeung Donald
Published: November 2005

Pre-execution is a promising latency tolerance technique that uses one or more helper threads running in spare hardware contexts ahead of the main computation to trigger long-latency memory operations early, hence absorbing their latency on behalf of the main computation. This paper investigates a source-to-source C compiler for extracting pre-execution thread code automatically, thus relieving the programmer or hardware from this onerous task. At the heart of our compiler are three algorithms. First,
program slicing
removes non-critical code for computing cache-missing memory references, reducing pre-execution overhead. Second,
prefetch conversion
replaces blocking memory references with non-blocking prefetch instructions to minimize pre-execution thread stalls. Finally,
threading scheme selection
chooses the best scheme for initiating pre-execution threads, speculatively parallelizing loops to generate thread-level parallelism when necessary for latency tolerance. We prototyped our algorithms using the Stanford University Intermediate Format (SUIF) framework and a publicly available program slicer, called
Unravel
[13], and we evaluated our compiler on a detailed architectural simulator of an SMT processor. Our results show compiler-based pre-execution improves the performance of 9 out of 13 applications, reducing execution time by 22.7%. Across all 13 applications, our technique delivers an average speedup of 17.0%. These performance gains are achieved fully automatically on conventional SMT hardware, with only minimal modifications to support pre-execution threads.
Compiler optimization of scalar value communication between speculative threads
Authors: Zhai Antonia , Colohan Christopher B. , Steffan J. Gregory , Mowry Todd C.
Published: November 2005

While there have been many recent proposals for hardware that supports
Thread-Level Speculation
(TLS), there has been relatively little work on compiler optimizations to fully exploit this potential for parallelizing programs optimistically. In this paper, we focus on one important limitation of program performance under TLS, which is stalls due to forwarding scalar values between threads that would otherwise cause frequent data dependences. We present and evaluate dataflow algorithms for three increasingly-aggressive instruction scheduling techniques that reduce the
critical forwarding path
introduced by the synchronization associated with this data forwarding. In addition, we contrast our compiler techniques with related hardware-only approaches. With our most aggressive compiler and hardware techniques, we improve performance under TLS by 6.2-28.5% for 6 of 14 applications, and by at least 2.7% for half of the other applications.
A comparative study of arbitration algorithms for the Alpha 21364 pipelined router
Authors: Mukherjee Shubhendu S. , Silla Federico , Bannon Peter , Emer Joel , Lang Steve , Webb David
Published: November 2005

Interconnection networks usually consist of a fabric of interconnected routers, which receive packets arriving at their input ports and forward them to appropriate output ports. Unfortunately, network packets moving through these routers are often delayed due to conflicting demand for resources, such as output ports or buffer space. Hence, routers typically employ
arbiters
that resolve conflicting resource demands to maximize the number of matches between packets waiting at input ports and free output ports. Efficient design and implementation of the algorithm running on these arbiters is critical to maximize network performance.This paper proposes a new arbitration algorithm called
SPAA
(Simple Pipelined Arbitration Algorithm), which is implemented in the Alpha 21364 processor's on-chip router pipeline. Simulation results show that SPAA significantly outperforms two earlier well-known arbitration algorithms: PIM (Parallel Iterative Matching) and WFA (Wave-Front Arbiter) implemented in the SGI Spider switch. SPAA outperforms PIM and WFA because SPAA exhibits matching capabilities similar to PIM and WFA under realistic conditions when many output ports are busy, incurs fewer clock cycles to perform the arbitration, and can be pipelined effectively. Additionally, we propose a new prioritization policy called the
Rotary Rule,
which prevents the network's adverse performance degradation from saturation at high network loads by prioritizing packets already in the network over new packets generated by caches or memory.
Increasing web server throughput with network interface data caching
Authors: Kim Hyong-youb , Pai Vijay S. , Rixner Scott
Published: November 2005

This paper introduces network interface data caching, a new technique to reduce local interconnect traffic on networking servers by caching frequently-requested content on a programmable network interface. The operating system on the host CPU determines which data to store in the cache and for which packets it should use data from the cache. To facilitate data reuse across multiple packets and connections, the cache only stores application-level response content (such as HTTP data), with application-level and networking headers generated by the host CPU. Network interface data caching can reduce PCI traffic by up to 57% on a prototype implementation of a uniprocessor web server. This traffic reduction results in up to 31% performance improvement, leading to a peak server throughput of 1571 Mb/s.
Programming language optimizations for modular router configurations
Authors: Kohler Eddie , Morris Robert , Chen Benjie
Published: November 2005

Networking systems such as Ensemble, the
x
-kernel, Scout, and Click achieve flexibility by building routers and other packet processors from modular components. Unfortunately, component designs are often slower than purpose-built code, and routers in particular have stringent efficiency requirements. This paper addresses the efficiency problems of one component-based router, Click, through optimization tools inspired in part by compiler optimization passes. This pragmatic approach can result in significant performance improvements; for example, the combination of three optimizations reduces the amount of CPU time Click requires to process a packet in a simple IP router by 34%. We present several optimization tools, describe how those tools affected the design of Click itself, and present detailed evaluations of Click's performance with and without optimization.
Evolving RPC for active storage
Authors: Sivathanu Muthian , Arpaci-Dusseau Andrea C. , Arpaci-Dusseau Remzi H.
Published: November 2005

We introduce Scriptable RPC (SRPC), an RPC-based framework that enables distributed system services to take advantage of active components. Technology trends point to a world where each component in a system (whether disk, network interface, or memory) has substantial computational capabilities; however, traditional methods of building distributed services are not designed to take advantage of these new architectures, mandating wholesale change of the software base to exploit more powerful hardware. In contrast, SRPC provides a direct and simple migration path for traditional services into the active environment.We demonstrate the power and flexibility of the SRPC framework through a series of case studies, with a focus on active storage servers. Specifically, we find three advantages to our approach. First, SRPC improves the performance of distributed file servers, reducing latency by combining the execution of operations at the file server. Second, SRPC enables the ready addition of new functionality; for example, more powerful cache consistency models can be realized on top of a server that exports a simple NFS-like interface. Third, SRPC simplifies the construction of distributed services; operations that are difficult to coordinate across client and server can now be co-executed at the server, thus avoiding costly agreement and crash-recovery protocols.
Implementation of multiple attribute grammar inheritance in the tool LISA
Authors: Mernik Marjan , Žumer Viljem , Lenič Mitja , Avdičaušević Enis
Published: November 2005

Multiple attribute grammar inheritance is a structural organization of attribute grammars where the attribute grammar inherits the specifications from ancestor attribute grammars, may add new specifications or may override some specifications from ancestor specifications. In the paper the implementation of multiple attribute grammar inheritance is described. The proposed approach is successfully implemented in the compiler/interpreter generator tool LISA ver. 2.0.
Denotational semantics of programming languages and compiler generation in PowerEpsilon
Authors: Zhu Ming-Yuan
Published: November 2005

Programming in constructive type theory corresponds to theorem proving in mathematics: the specification plays the role of the proposition to be proved and the program is obtained from the proof. In this paper, we present an approach of using constructive type theory to derive a compiler of a given programming language from its denotational semantic definition. The development is supported by a proof development system called
PowerEpsilon
.
Formal specifications of debuggers
Authors: Zhu Ming-Yuan
Published: November 2005

Programming in constructive type theory corresponds to theorem proving in mathematics: the specification plays the role of the proposition to be proved and the program is obtained from the proof. In this paper, we present an approach of using constructive type theory to derive a debugger of a given programming language from its denotational semantic definition. The development is supported by a proof development system called
PowerEpsilon
.
Tenuring policies for generation-based storage reclamation
Authors: Ungar David , Jackson Frank
Published: November 2005

One of the most promising automatic storage reclamation techniques, generation-based storage reclamation, suffers poor performance if many objects live for a fairly long time and then die. We have investigated the severity of this problem by simulating Generation Scavenging automatic storage reclamation from traces of actual four-hour sessions. There was a wide variation in the sample runs, with garbage-collection overhead ranging from insignificant, during the interactive runs, to severe, during a single non-interactive run. All runs demonstrated that performance could be improved with two techniques: segregating large bitmaps and strings, and mediating tenuring with demographic feedback. These two improvements deserve consideration for any generation-based storage reclamation strategy.
TS: an optimizing compiler for smalltalk
Authors: Johnson Ralph E. , Graver Justin O. , Zurawski Laurance W.
Published: November 2005

TS (Typed Smalltalk) is a portable optimizing compiler that produces native machine code for a typed variant of Smalltalk, making Smalltalk programs much faster. This paper describes the structure of TS, the kinds of optimizations that it performs, the constraints that it places upon Smalltalk, the constraints placed upon it by an interactive programming environment, and its performance.
An integrated color smalltalk-80 system
Authors: Wirfs-Brock Rebecca
Published: November 2005

The Smalltalk-80™ user interface and graphics model are based on monochromatic graphics. One natural step in the evolution of the Smalltalk-80 system is the addition of color. This paper describes an implementation of color Smalltalk. Classes have been defined to manipulate visual color models and colored graphics objects. The extensive collaboration between classes which describe color, classes which perform basic graphics operations, and classes in the user interface is explored. Issues in the design and implementation are examined. Potential future directions for object-oriented color systems are discussed.
Configuring stand-alone smalltalk-80 applications
Authors: Sridhar S.
Published: November 2005

The Smalltalk-80™ programming environment, though powerful for prototyping applications, does not have any mechanisms for constructing a stand-alone version of an application. Traditionally, the application is bundled with an image including the entire development environment. Production applications frequently require that the only interface visible to the end user be that of the application. A common misperception among Smalltalk-80 application developers is that it is impossible to:

develop and deliver applications containing proprietary algorithms,

prevent inspection and modification of the application,

separate the development environment from the delivered application,

provide annotation of the application classes and methods without actually revealing the source code to the end user.

In this paper, we introduce various techniques and mechanisms for meeting these requirements.
Orwell—a configuration management system for team programming
Authors: Thomas Dave , Johnson Kent
Published: November 2005

In this paper, we describe the design and implementation of Orwell, a configuration management tool for multiperson Smalltalk projects. Although the system described has been implemented for Smalltalk, the design is applicable to other languages such as C++, Objective-C or ADA. Smalltalk is well recognized as a productive programming environment for an individual programmer, but its lack of team support is currently a major obstacle in using Smalltalk for a large software project. To support multiperson Smalltalk programming, Orwell provides both source and object code sharing as well as version control on a network of personal workstations. Class ownership is used as the primary means for dividing work among programmers during the lifecycle of a project. Orwell also supports groups of programmers not physically connected to a common file server. We describe our implementation which preserves the productive exploratory environment of Smalltalk. Seamless integration and performance are essential for Orwell to be accepted and used by Smalltalk programmers.
A performance comparison of object and relational databases using the Sun Benchmark
Authors: Duhl Joshua , Damon Craig
Published: November 2005

A general concern about object-oriented systems has been whether or not they are able to meet the performance demands required to be useful for the development of significant production software systems. Attempts to evaluate this assertion have been hampered by a lack of meaningful performance benchmarks that compare database operations across different kinds of databases.

In this paper, we utilize the Sun Benchmark [Rube87] as a means for assessing the performance of an object database and comparing it with existing relational systems. We discuss the benchmark, and many of the implementation issues involved in introducing a relationally oriented benchmark into an object-oriented paradigm. We demonstrate the performance of an object database using Ontologic's Vbase object database platform as an example of a commercially available object database, and we compare these benchmark results against those of existing relational database systems. The results offer strong evidence that object databases are capable of performing as well as, or better than, existing relational database systems.
Intensional concepts in an object database model
Authors: Beech David
Published: November 2005

There is a requirement for a stronger treatment of intentional concepts and more general inferential ability within database systems. A framework for achieving this will be described in terms of extensions to an object data model.

The type Concept is introduced into the model as a subtype of Action. Intentional concepts may then be defined as filters or generators, depending on the nature of the defining formula. In either case, the dual action should be available—provided automatically by the system or explicitly by the user.

Finally, sets and types are treated as special cases of extensional concepts, leading to a novel structure of the hierarchy of system types.
Fabrik: a visual programming environment
Authors: Ingalls Dan , Wallace Scott , Chow Yu-Ying , Ludolph Frank , Doyle Ken
Published: November 2005

Fabrik is a visual programming environment - a kit of computational and user-interface components that can be “wired” together to build new components and useful applications. Fabrik diagrams utilize bidirectional dataflow connections as a shorthand for multiple paths of flow. Built on object-oriented foundations. Fabrik components can compute arbitrary objects as outputs. Music and animation can be programmed in this way and the user interface can even be extended by generating graphical structures that depend on other data. An interactive type system guards against meaningless connections. As with simple dataflow, each Fabrik component can be compiled into an object with access methods corresponding to each of the possible paths of data propagation.
GraphTrace—understanding object-oriented systems using concurrently animated views
Authors: Kleyn Michael F. , Gingrich Paul C.
Published: November 2005

Object-Oriented programming is a powerful means of developing large complex systems. In this paper we address the need to understand the behavior of objects in order to facilitate code sharing and reusability. We describe
GraphTrace
, a tool we have developed that has allowed us to experiment with new ways of visualizing the dynamic behavior of object-oriented programs. Based on our experience with the GraphTrace tool we suggest that being able to present many different views of an object-oriented system and then animating these views concurrently represents a powerful means for understanding such systems.
Process management and exception handling in multiprocessor operating systems using object-oriented design techniques
Authors: Russo Vincent , Johnston Gary , Campbell Roy
Published: November 2005

The programming of the interrupt handling mechanisms, process switching primitives, scheduling mechanisms, and synchronization primitives of an operating system for a multiprocessor require both efficient code in order to support the needs of high-performance or real-time applications and careful organization to facilitate maintenance. Although many advantages have been claimed for object-oriented class hierarchical languages and their corresponding design methodologies, the application of these techniques to the design of the primitives within an operating system has not been widely demonstrated.

To investigate the role of class hierarchical design in systems programming, the authors have constructed the
Choices
multiprocessor operating system architecture using the C++ programming language. During the implementation, it was found that many operating system design concerns can be represented advantageously using a class hierarchical approach, including: the separation of mechanism and policy; the organization of an operating system into layers, each of which represents an abstract machine; and the notions of process and exception management. In this paper, we discuss an implementation of the low-level primitives of this system and outline the strategy by which we developed our solution.
Object-oriented programming: an objective sense of style
Authors: Lieberherr K. , Holland I. , Riel A.
Published: November 2005

We introduce a simple, programming language independent rule (known in-house as the Law of Demeter™) which encodes the ideas of encapsulation and modularity in an easy to follow form for the object-oriented programmer. You tend to get the following related benefits when you follow the Law of Demeter while minimizing simultaneously code duplication, the number of method arguments and the number of methods per class: Easier software maintenance, less coupling between your methods, better information hiding, narrower interfaces, methods which are easier to reuse, and easier correctness proofs using structural induction. We discuss two important interpretations of the Law (strong and weak) and we prove that any object-oriented program can be transformed to satisfy the Law. We express the Law in several languages which support object-oriented programming, including Flavors, Smalltalk-80, CLOS, C++ and Eiffel.
Transformation of data flow analysis models to object oriented design
Authors: Alabiso Bruno
Published: November 2005

This paper describes a strategy to transform Data Flow Analysis into Object Oriented Design. This transformation is performed by extracting information from the Data Flow Model, by enriching with Design decision and by finally producing an Object Oriented Design Model. Semiformal transformation rules are described. Also a special notation is introduced to describe the Object Oriented Design Model. The Model used to represent Data Flow Analysis is the one originally proposed by Yourdon, complemented with Ward-Mellor's Real Time extensions (the “Essential Model”).
An open enviornment for building parallel programming systems
Authors: Bershad Brian N. , Lazowska Edward D. , Levy Henry M. , Wagner David B.
Published: November 2005

PRESTO is a set of tools for building parallel programming systems on shared-memory multiprocessors. PRESTO's goal is to provide a framework within which one can easily build efficient support for any of a wide variety of “models” of parallel programming. PRESTO is designed for easy modification and extension, not only at the level of the primitives and structures made available for the application programmer's use, but also at the level of the run-time kernel that supports parallel applications. PRESTO is implemented in the object-oriented language C++ on a Sequent Balance 21000 and has been used in a number of applications that are described in this paper.
Experiences with poker
Authors: Notkin David , Snyder Lawrence , Socha David , Bailey Mary L. , Forstall Bruce , Gates Kevin , Greenlaw Ray , Griswold Willian G. , Holman Thomas J. , Korry Richard , Lasswell Gemini , Mitchell Robert , Nelson Philip A.
Published: November 2005

Experience from over five years of building nonshared memory parallel programs using the Poker Parallel Programming Environment has positioned us to evaluate our approach to defining and developing parallel programs. This paper presents the more significant results of our evaluation of Poker. The evaluation is driving our next effort in parallel programming environment; many of the results should be sufficiently general to apply to other related efforts.
Compiling Fortran 8x array features for the connection machine computer system
Authors: Albert Eugene , Knobe Kathleen , Lukas Joan D. , Steele Guy L.
Published: November 2005

The Connection Machine® computer system supports a data parallel programming style, making it a natural target architecture for Fortran 8x array constructs. The Connection Machine Fortran compiler generates VAX code that performs scalar operations and directs the Connection Machine to perform array operations. The Connection Machine virtual processor mechanism supports elemental operations on very large arrays. Most array operators and intrinsic functions map into single instructions or short instruction sequences. Noncontiguous array sections, array-valued subscripts, and parallel constructs such as WHERE and FORALL are also readily accommodated on the Connection Machine. In addition to such customary optimizations as common subexpression elimination, the CM Fortran compiler minimizes data motion for aligning array operations, minimizes transfers between the Connection Machine and the VAX and minimizes context switching for masked computations.
Compiling C* programs for a hypercube multicomputer
Authors: Quinn Michael J. , Hatcher Philip J. , Jourdenais Karen C.
Published: November 2005

A data parallel language such as C
*
has a number of advantages over conventional hypercube programming languages. The algorithm design process is simpler, because (1) message passing is invisible, (2) race conditions are nonexistent, and (3) the data can be put into a one-to-one correspondence with the virtual processors. Since data are mapped to virtual processors, rather than physical processors, it is easier to move algorithms implemented on one size hypercube to a larger or smaller system. We outline the design of a C
*
compiler for a hypercube multicomputer. Our design goals are to minimize the amount of time spent synchronizing, limit the number of interprocessor communications, and make each physical processor's emulation of a set of virtual processors as efficient as possible. We have hand translated three benchmark programs and compared their performance with that of ordinary C programs. All three programs—matrix multiplication, LU decomposition, and hyperquicksort—achieve reasonable speedup on a commercial hypercube, even when solving problems of modest size. On a 64-processor NCUBE/7, the C
*
matrix multiplication program achieves a speedup of 27 when multiplying two 64 × 64 matrices, the hyperquicksort program achieves a speedup of 10 when sorting 16,384 integers, and LU decomposition attains a speedup of 7 when decomposing a 256 × 256 system of linear equations. We believe the degradation in machine performance resulting from the use of a data parallel language will be more than compensated for by the increase in programmer productivity.
Using data partitioning to implement a parallel assembler
Authors: Katseff Howard P.
Published: November 2005

A technique for implementing algorithms on a multiprocessor computer system is
data partitioning,
in which input data for a problem is partitioned among many processors that cooperate to solve the problem. This paper demonstrates that data partitioning is a good method for implementing an assembler on a message-passing multiprocessor system: it yields a speedup exceeding a factor of 6 with eight processors. We compare several alternative methods for distributing program text and sharing global information among the processors executing the assembler: operations that are important for a variety of applications implemented with data partitioning.
Automatic discovery of parallelism: a tool and an experiment (extended abstract)
Authors: Burke Michael , Cytron Ron , Ferrante Jeanne , Hsieh Wilson , Sarkar Vivek , Shields David
Published: November 2005

This paper reports preliminary results from applying advanced techniques to the parallelization of sequential programs. Such techniques include interprocedural analysis and the identification of nested parallelism. These techniques have been proposed for exploiting the greater concurrency offered by multiprocessors as compared with vector architectures. The effectiveness of these techniques as applied to some popular numerical Fortran programs is examined. Although extrapolation is difficult, these preliminary results are encouraging indicators of the success of these techniques.
Restructuring Lisp programs for concurrent execution
Authors: Larus James R. , Hilfinger Paul N.
Published: November 2005

This paper describes the techniques that the program transformation system CURARE uses to restructure Lisp programs for concurrent execution in multiprocessor Lisp systems and discusses the problems inherent in producing concurrent programs in a flexible and dynamic programming language such as Lisp.

CURARE's overall organization is similar to other program restructuring systems: it detects potential conflicts between statements in a program, then transforms the program to improve its concurrent performance, and finally inserts synchronization to ensure the program's concurrent behavior. However, the language and programs that CURARE transforms are very different from the FORTRAN programs that are the traditional targets of program restructuring and so CURARE requires new algorithms and approaches, which are described in this paper.
Parallel discrete-event simulation of FCFS stochastic queueing networks
Authors: Nicol David M.
Published: November 2005

Physical systems are inherently parallel; intuition suggests that simulations of these systems may be amenable to parallel execution. The parallel execution of a discrete-event simulation requires careful synchronization of processes in order to ensure the execution's correctness; this synchronization can degrade performance. Largely negative results were recently reported in a study which used a well-known synchronization method on queueing network simulations. In this paper we discuss a synchronization method,
appointments
, which has proven itself to be effective on simulations of FCFS queueing networks. The key concept behind appointments is the provision of
lookahead
. Lookahead is a prediction on a processor's future behavior, based on an analysis of the processor's simulation state. We show how lookahead can be computed for FCFS queueing network simulations, give performance data that demonstrates the method's effectiveness under moderate to heavy loads, and discuss performance trade-offs between the quality of lookahead, and the cost of computing lookahead.
Characterizing the synchronization behavior of parallel programs
Authors: Davis Helen , Hennessy John
Published: November 2005

Contention for synchronization locks and delays waiting for synchronization events can substantially increase the running time of a parallel program. This makes it important to characterize the synchronization behavior of programs and to provide analysis tools to aid both the hardware and software designer in evaluating design alternatives. This paper describes a tracing facility that is incorporated into a synchronization package. This facility provides a portable means to accurately and efficiently characterize parallel programs. The behavior of several applications has been monitored uncovering program characteristics that make it difficult to achieve linear speedup. Our monitoring facility allows a programmer to determine the performance implications of the synchronization structure he has used, and it allows the architect to evaluate various hardware support mechanisms.
Compile-time techniques for efficient utilization of parallel memories
Authors: Gupta Rajiv , Soffa Mary Lou
Published: November 2005

The partitioning of shared memory into a number of memory modules is an approach to achieve high memory bandwidth for parallel processors. Memory access conflicts can occur when several processors simultaneously request data from the same memory module. Although work has been done to improve access performance for vectors, no work has been reported to improve the access performance of scalars. For systems in which the processors operate in a lock-step mode, a large percentage of memory access conflicts can be predicted at compile-time. These conflicts can be avoided by appropriate distribution of data among the memory modules at compile-time. A long instruction word machine is an example of a system in which the functional units operate in a lock-step mode performing operations on data fetched in parallel from multiple memory modules. In this paper, compile-time techniques for distribution of scalars to avoid memory access conflicts are presented. Furthermore, algorithms to schedule data transfers among memory modules to avoid conflicts that cannot be avoided by the distribution of values alone are developed. The techniques have been implemented as part of a compiler for a reconfigurable long instruction word architecture. Results of experiments are presented demonstrating that a very high percentage of memory access conflicts can be avoided by scheduling a very low number of data transfers.
Trace analysis of Erlang programs
Authors: Arts Thomas , Fredlund Lars-Åke
Published: November 2005

The paper reports on an experiment to provide the Erlang programming language with a tool package for convenient trace generation, collection and to support analysis of traces using a set of techniques. Due to the frequent use of state-based software design patterns in Erlang programming we can in many cases recover not only the events from a trace log, but also the program states causing these events. This makes it possible to obtain program models from execution traces. In our work we make use of these program models for program visualization and model checking.
On-the-fly model checking from interval logic specifications
Authors: Hornos Miguel J. , Capel Manuel I.
Published: November 2005

Future Interval Logic (FIL) and its intuitive graphical representation, Graphical Interval Logic (GIL), can be used as the formal description language of model checking tools to verify hardware and software systems. An interval clearly defines the temporal scope over which properties are evaluated. From interval formulas specifying the temporal behavior of a system we obtain their semantically equivalent Büchi automata, but in such a way that our algorithm can be integrated into an on-the-fly model checking tool. As the property automaton can be generated simultaneously with, and guided by, the construction of the system model, it is possible to detect that a property is violated by constructing only a part of both state spaces. This is the first time that this kind of algorithm has been developed for an interval logic. The relations with other automated verification techniques from linear temporal logic are also discussed. Moreover, an appendix with proof of the correctness of our algorithm is included.
Selective memoization
Authors: Acar Umut A. , Blelloch Guy E. , Harper Robert
Published: November 2005

We present a framework for applying memoization selectively. The framework provides programmer control over equality, space usage, and identification of precise dependences so that memoization can be applied according to the needs of an application. Two key properties of the framework are that it is efficient and yields programs whose performance can be analyzed using standard techniques.We describe the framework in the context of a functional language and an implementation as an SML library. The language is based on a modal type system and allows the programmer to express programs that reveal their true data dependences when executed. The SML implementation cannot support this modal type system statically, but instead employs run-time checks to ensure correct usage of primitives.
From symptom to cause
Authors: Ball Thomas , Naik Mayur , Rajamani Sriram K.
Published: November 2005

There is significant room for improving users' experiences with model checking tools. An error trace produced by a model checker can be lengthy and is indicative of a
symptom
of an error. As a result, users can spend considerable time examining an error trace in order to understand the
cause
of the error. Moreover, even state-of-the-art model checkers provide an experience akin to that provided by parsers before syntactic error recovery was invented: they report a single error trace per run. The user has to fix the error and run the model checker again to find more error traces.We present an algorithm that exploits the existence of correct traces in order to localize the error cause in an error trace, report a single error trace per error cause, and generate multiple error traces having independent causes. We have implemented this algorithm in the context of
slam
, a software model checker that automatically verifies temporal safety properties of C programs, and report on our experience using it to find and localize errors in device drivers. The algorithm typically narrows the location of a cause down to a few lines, even in traces consisting of hundreds of statements.
Incremental algorithms for dispatching in dynamically typed languages
Authors: Zibin Yoav , Gil Joseph (Yossi)
Published: November 2005

A fundamental problem in the implementation of object-oriented languages is that of a frugal
dispatching data structure
, i.e., support for quick response to dispatching queries combined with compact representation of the type hierarchy and the method families. Previous theoretical algorithms tend to be impractical due to their complexity and large hidden constant. In contrast, successful practical heuristics, including Vitek and Horspool's
compact dispatch tables
(CT) [16] designed for dynamically typed languages, lack theoretical support. In subjecting CT to theoretical analysis, we are not only able to improve and generalize it, but also provide the first non-trivial bounds on the performance of such a heuristic.Let
n
,
m
l
denote the total number of types, messages, and different method implementations, respectively. Then, the dispatching matrix, whose size is
nm
, can be compressed by a factor of at most ι ≡ (
nm
)/
l
. Our main variant to CT achieves a compression factor of ½ √ι. More generally, we describe a sequence of algorithms CT
1
, CT
2
, CT
3
,..., where CT

d

achieves compression by a factor of (at least)
1
over

d

ι

1—1/
d

, while using
d
memory dereferencing operations during dispatch. This tradeoff represents the first bounds on the compression ratio of constant-time dispatching algorithms.A generalization of these algorithms to a
multiple-inheritance
setting, increases the space by a factor of κ

1-1/
d

, where κ is a metric of the complexity of the topology of the inheritance hierarchy, which (as indicated by our measurements) is typically small. The most important generalization is an
incremental
variant of the CT

d

scheme for a single-inheritance setting. This variant uses at most twice the space of CT

d

, and its time of inserting a new type into the hierarchy is optimal. We therefore obtain algorithms for efficient management of dispatching in dynamic-typing, dynamic-loading languages, such as
Smalltalk
and even the
Java
invokeinterface instruction.
Efficient algorithms for isomorphisms of simple types
Authors: Zibin Yoav , Gil Joseph (Yossi) , Considine Jeffrey
Published: November 2005

The
first order isomorphism problem
is to decide whether two non-recursive types using product- and function-type constructors, are isomorphic under the axioms of commutative and associative products, and currying and distributivity of functions over products. We show that this problem can be solved in
O
(
n
log
2
n
) time and
O
(
n
) space, where is
n
the input size. This result improves upon the
O
(
n
log
2
n
) time and
O
(
n
2
) space bounds of the best previous algorithm. We also describe an
O
(
n
) time algorithm for the
linear isomorphism problem
, which does not include the distributive axiom, whereby improving upon the
O
(
n
log
n
) time of the best previous algorithm for this problem.
A type system for higher-order modules
Authors: Dreyer Derek , Crary Karl , Harper Robert
Published: November 2005

We present a type theory for higher-order modules that accounts for many central issues in module system design, including translucency, applicativity, generativity, and modules as first-class values. Our type system harmonizes design elements from previous work, resulting in a simple, economical account of modular programming. The main unifying principle is the treatment of abstraction mechanisms as computational effects. Our language is the first to provide a complete and practical formalization of all of these critical issues in module system design.
Pure patterns type systems
Authors: Barthe Gilles , Cirstea Horatiu , Kirchner Claude , Liquori Luigi
Published: November 2005

We introduce a new framework of algebraic pure type systems in which we consider rewrite rules as lambda terms with patterns and rewrite rule application as abstraction application with built-in matching facilities. This framework, that we call "Pure Pattern Type Systems", is particularly well-suited for the foundations of programming (meta)languages and proof assistants since it provides in a fully unified setting higher-order capabilities and pattern matching ability together with powerful type systems. We prove some standard properties like confluence and subject reduction for the case of a syntactic theory and under a syntactical restriction over the shape of patterns. We also conjecture the strong normalization of typable terms. This work should be seen as a contribution to a formal connection between logics and rewriting, and a step towards new proof engines based on the Curry-Howard isomorphism.
Interprocedural compatibility analysis for static object preallocation
Authors: Gheorghioiu Ovidiu , Salcianu Alexandru , Rinard Martin
Published: November 2005

We present an interprocedural and compositional algorithm for finding pairs of
compatible
allocation sites, which have the property that no object allocated at one site is live at the same time as any object allocated at the other site. If an allocation site is compatible with itself, it is said to be
unitary
: at most one object allocated at that site is live at any given point in the, execution of the program. We use the results of the analysis to statically preallocate memory space for the objects allocated at unitary sites, thus simplifying the computation of an upper bound on the amount of memory required to execute the program. We also use the analysis to enable objects allocated at several compatible allocation sites to share the same preallocated memory. Our experimental results show that, for our set of Java benchmark programs, 60% of the allocation sites are unitary and can be statically preallocated. Moreover, allowing compatible unitary allocation sites to share the same preallocated memory leads to a 95% reduction in the amount of memory preallocated for these sites.
A calculus for probabilistic languages
Authors: Park Sungwoo
Published: November 2005

As probabilistic computation plays an increasing role in diverse fields in computer science, researchers have designed new languages to facilitate the development of probabilistic programs. In this paper, we develop a probabilistic calculus by extending the traditional lambda calculus. In our calculus, every expression denotes a probability distribution yet evaluates to a regular value. The most notable feature of our calculus is that it is founded upon sampling functions, which map the unit interval to probability domains. As a consequence, we achieve a unified representation scheme for all types of probability distributions. In order to support an efficient implementation of the calculus, we also develop a refinement type system which is capable of distinguishing expressions denoting regular values from expressions denoting probability distributions. We use a novel formulation of the intuitionistic modal logic S4 with an intersection connective in the refinement type system. We present preliminary evidence that a probabilistic language based upon our calculus is viable in applications involving massive probabilistic computation.
Time regions and effects for resource usage analysis
Authors: Kobayashi Naoki
Published: November 2005

Various resources such as files and memory are associated with certain protocols about how they should be accessed. For example, a memory cell that has been allocated should be eventually deallocated, and after the deallocation, the cell should no longer be accessed. Igarashi and Kobayashi recently proposed a general type-based method to check whether a program follows such resource access policies, but their analysis was not precise enough for certain programs. In this paper, we refine their type-based analysis by introducing a new notion of time regions. The resulting analysis combines the merits of two major previous approaches to type-based analysis of resource usage -- linear-type-based and effect-based approaches.
Inferring annotated types for inter-procedural register allocation with constructor flattening
Authors: Amtoft Torben , Muller Robert
Published: November 2005

We introduce an annotated type system for a compiler intermediate language. The type system is designed to support inter-procedural register allocation and the representation of tuples and variants directly in the register file. We present an algorithm that generates constraints for assigning annotations, and prove its soundness with respect to the type system.