bluuebunny/crossref_metadata_2025 huggingface dataset:
COMFY—comfortable set of control primitives for machine language programming
Authors: Baker Henry G.
Published: November 2005

Structured programming advocates the elimination of the GOTO from the set of primitives for a computer language. Yet at the machine language level, almost all machines offer only the conditional or unconditional branch as the basic control primitive. Vaughan Pratt has suggested using instead pseudo-non-deterministic programming (as well as the COMFY name). We present a new set of machine language control primitives based on Pratt's suggestion which are simpler to implement than if-then-else and do-while and are more flexible at the same time. The machine language implementation of these primitives requires nothing more complicated than a stack; the size of the stack needed (exclusive of programmer-defined subroutine control points) is
O
(
d
), where
d
is the operator depth of the program. This is much less space and machine complexity than would be required for a true backtracking control structure. The user can emulate if-then-else, do-while, repeat-until, etc., with macros using these primitives if he so desires.
Considerations in developing a formally-based visual programming language reference manual
Authors: Carter Debbie K. , Baker Albert D.
Published: November 2005

A language reference manual provides a definitive document containing complete and accurate details about the legality and meaning of the language's constructs. Some key decisions in writing a language reference manual are how to specify syntax, how to specify semantics, and how to structure the manual. Some of these components to a language reference manual have been active areas of research in the visual programming language community. The specific issue of how to put these together into a language reference manual has not been a strong part of this discussion. This paper reviews the recent research on specification methods and language presentation, and evaluates these methods for use within a visual programming language reference manual. The suggested specification that results from the evaluation is tested using SLAM II, a visually oriented queuing network simulation language which has enjoyed wide commercial use since its introduction in 1979.
Garment
Authors: Zheng Naixiao , Zheng Hongjun , Qiu Zongyan
Published: November 2005

Domain-specific languages are closely related to interface languages of domain-oriented software. Thus, the specifications of such software can be abstracted to specifications of language systems, and implementation of such software can be abstracted to implementation of the language systems. As a unified model to support software development and research, a mechanism named
Garment
for abstracting and encapsulating languages is proposed.
Garment
provides a unified framework for defining languages (syntax and semantics) and describing relations between languages (which are classified as inheritance, shielding and extension). Finally, an experimental environment, which supports software development with Garment, is introduced briefly.
Consummating virtuality to support more polymorphism in C++
Authors: Chen Wen-Ke , Sun Jia-Su , Tang Zhi-Min
Published: November 2005

Inheritance together with virtual functions in C++ provides programmers much polymorphism, an important facility of object-oriented design and programming. However, they can hardly be applied to enrich a family of classes (including the base classes and their derived classes) with some common features. Multiple inheritance and virtual base classes are usually hired to solve such a problem, or templates can also be employed for the same purpose. Unfortunately, these approaches are unnatural and costly. Moreover, virtual base classes deflect from the concept of dynamic binding behind virtual functions and therefore complicate the incomplete virtuality in C++. In this paper, we demonstrate that truly virtual base classes can be utilized to solve the problem effectively and efficiently, and can be used to express explicitly what virtual base classes do implicitly in a more flexible and lucid way. In addition, they along with virtual data members can provide further polymorphism and a type-safe and efficient alternative to constrained genericity and multiple inheritance in some cases, and hence facilitate the design and implementation of extensible and portable software, especially libraries of classes.
A new model for integrated nested task and data parallel programming
Authors: Subhlok Jaspal , Yang Bwolen
Published: November 2005

High Performance Fortran (HPF) has emerged as a standard language fordata parallel computing. However, a wide variety of scientific applications are best programmed by a combination of task and data parallelism. Therefore, a good model of task parallelism is important for continued success of HPF for parallel programming. This paper presents a task parallelism model that is simple, elegant, and relatively easy to implement in an HPF environment. Task parallelism is exploited by mechanisms for dividing processors into subgroups and mapping computations and data onto processor subgroups. This model of task parallelism has been implemented in the Fx compiler at Carnegie Mellon University. The paper addresses the main issues in compiling integrated task and data parallel programs and reports on the use of this model for programming various flat and nested task structures. Performance results are presented for a set of programs spanning signal processing, image processing, computer vision and environment modeling. A variant of this task model is a new approved extension of HPF and this paper offers insight into the power of expression and ease of implementation of this extension.
Compiler and software distributed shared memory support for irregular applications
Authors: Lu Honghui , Cox Alan L. , Dwarkadas Sandhya , Rajamony Ramakrishnan , Zwaenepoel Willy
Published: November 2005

We investigate the use of a software distributed shared memory (DSM) layer to support irregular computations on distributed memory machines. Software DSM supports irregular computation through demand fetching of data in response to memory access faults. With the addition of a very limited form of compiler support, namely the identification of the section of the indirection array accessed by each processor, many of these on-demand page fetches can be aggregated into a single message, and prefetched prior to the access fault.We have measured the performance of this approach for two irregular applications, moldyn and nbf, using the Tread-Marks DSM system on an 8-processor IBM SP2. We find that it has similar performance to the inspector-executor method supported by the CHAOS run-time library, while requiring much simpler compile-time support. For moldyn, it is up to 23% faster than CHAOS, depending on the input problem's characteristics; and for nbf, it is no worse than 14% slower. If we include the execution time of the inspector, the software DSM-based approach is always faster than CHAOS. The advantage of this approach increases as the frequency of changes to the indirection array increases. The disadvantage of this approach is the potential for false sharing overhead when the data set is small or has poor spatial locality.
Ace
Authors: Raghavachari Mukund , Rogers Anne
Published: November 2005

Customizing the protocols used to manage accesses to different data structures within an application can improve the performance of shared-memory programs substantially [10, 21]. Existing systems for using customizable protocols are, however, hard to use because they force programmers to rely on low-level mechanisms for manipulating these protocols. Since several shared-memory systems implement protocols in software and can support customizable protocols, the development of intuitive abstractions for the use of application-specific protocols ia important.We have designed a language,
Ace
, that integrates support for customizable protocols with minimal extensions to C.
Ace
applications are developed using the standard shared-memory model with a default sequentially consistent protocol. Performance can then be optimized, with minor modifications to the application, by experimenting with different protocol libraries. In this paper, we isolate the issues involved in providing language support for using customizable protocols and present novel language abstractions for their easy use. We describe the implementation of a compiler and runtime system for
Ace
, and discuss the issues involved in their design. We also present measurements that demonstrate that
Ace
has good performance compared to an efficient software distributed shared-memory system.
Optimizing communication in HPF programs on fine-grain distributed shared memory
Authors: Chandra Satish , Larus James R.
Published: November 2005

Unlike compiler-generated message-passing code, the coherence mechanisms in shared-memory systems work equally well for regular and irregular programs. In many programs, however compile-time information about data accesses would permit data to be transferred more efficiently---if the underlying shared-memory system offered suitable primitives. This paper demonstrates that cooperation between a compiler and a memory coherence protocol can improve the performance of High Performance Fortran (HPF) programs running on fine-grain distributed shared memory system up to a factor of 2, while retaining the versatility and portability of shared memory. As a consequence, shared memory's performance becomes competitive with message passing for regular applications, while not affecting (or in some cases, even improving) its large advantage for irregular codes. This paper describes the design of our implementation and reports experimental results.
Experiences with non-numeric applications on multithreaded architectures
Authors: Sodan Angela , Gao Guang R. , Maquelin Olivier , Schultz Jens-Uwe , Tian Xin-Min
Published: November 2005

Distributed-memory machines have proved successful for many challenging numerical programs that can be split into largely independent computation-intensive subtasks requiring little data exchange (although the amount of exchanged data may be large). However, many irregular applications---e.g. in the AI field --- have a fairly tight data coupling that often results from the use of shared data structures, making them in many cases not amenable to parallelization on distributed-memory machines. EARTH is an efficient multithreaded architecture that supports in particular large numbers of small data exchanges by means of low start-up times and the ability of tolerance of even small latencies. In this paper, we show the benefits provided by EARTH for applications of this sort by presenting experimental results from several AI applications run on the MANNA machine, which is a distributed-memory machine with a very high-performance communicantion network. EARTH-MANNA is shown to extend the range of programs that can be parallelized and run effectively on distributed-memory machines.
Parallel breadth-first BDD construction
Authors: Yang Bwolen , O'Hallaron David R.
Published: November 2005

With the increasing complexity of protocol and circuit designs, formal verification has become an important research area and binary decision diagrams (BDDs) have been shown to be a powerful tool in formal verification. This paper presents a parallel algorithm for BDD construction targeted at shared memory multiprocessors and distributed shared memory systems. This algorithm focuses on improving memory access locality through specialized memory managers and partial breadth-first expansion, and on improving processor utilization through dynamic load balancing. The results on a shared memory system show speedups of over two on four processors and speedups of up to four on eight processors. The measured results clearly identify the main source of bottlenecks and point out some intereeting directions for further improvements.
Relaxed consistency and coherence granularity in DSM systems
Authors: Zhou Yuanyuan , Iftode Liviu , Sing Jaswinder Pal , Li Kai , Toonen Brian R. , Schoinas Ioannis , Hill Mark D. , Wood David A.
Published: November 2005

During the past few years, two main approaches have been taken to improve the performance of software shared memory implementations: relaxing consistency models and providing fine-grained access control. Their performance tradeoffs, however, we not well understood. This paper studies these tradeoffs on a platform that provides access control in hardware but runs coherence protocols in software, We compare the performance of three protocols across four coherence granularities, using 12 applications on a 16-node cluster of workstations. Our results show that no single combination of protocol and granularity performs best for all the applications. The combination of a sequentially consistent (SC) protocol and fine granularity works well with 7 of the 12 applications. The combination of a multiple-writer, home-based lazy release consistency (HLRC) protocol and page granularity works well with 8 out of the 12 applications. For applications that suffer performance losses in moving to coarser granularity under sequential consistency, the performance can usually be regained quite effectively using relaxed protocols, particularly HLRC. We also find that the HLRC protocol performs substantially better than a single-writer lazy release consistent (SW-LRC) protocol at coase granularity for many irregular applications. For our applications and platform, when we use the original versions of the applications ported directly from hardware-coherent shared memory, we find that the SC protocol with 256-byte granularity performs best on average. However, when the best versions of the applications are compared, the balance shifts in favor of HLRC at page granularity.
Application restructuring and performance portability on shared virtual memory and hardware-coherent multiprocessors
Authors: Jiang Dongming , Shan Hongzhang , Singh Jaswinder Pal
Published: November 2005

The performance portability of parallel programs across a wide range of emerging coherent shared address space systems is not well understood. Programs that run well on efficient, hardware cache-coherent systems often do not perform well on less optimal or more commodity-based communication architectures. This paper studies this issue of performance portability, with the commodity communication architecture of interest being page-grained shared virtual memory. We begin with applications that perform well on moderat scale hardware cache-coherent systems, and find that they do not do so well on SVM systems. Then, we examine whether and how the applications can be improved for SVM systems --- through data structuring or algorithmic enhancements---and the nature and difficulty of the optimization. Finally, we examine the impact of the successful optimizations on hardware-coherent platforms themselves, to see whether they are helpful, harmful or neutral on those platforms. We develop a systematic methodology to explore optimizations in different structured classes. The results, and the difficulty of the optimizations, lead insight not only into performance portability but also into the viability of SVM as a platform for these types of applications.
Performance implications of communication mechanisms in all-software global address space systems
Authors: Lim Beng-Hong , Chang Chi-Chao , Czajkowski Grzegorz , von Eicken Thorsten
Published: November 2005

Global addressing of shared data simplifies parallel programming and complements message passing models commonly found in distributed memory machines. A number of programming systems have been designed that synthesize global addressing purely in software on such machines. These systems provide a number of communication mechanisms to mitigate the effect of high communication latencies and overheads. This study compares the mechanisms in two representative all-software systems: CRL and Split-C. CRL uses region-based caching while Split-C uses split-phase and push-based data transfers for optimizing communication performance. Both systems take advantage of bulk data transfers.By implementing a set of parallel applications in both CRL and Split-C, and running them on the IBM SP2, Meiko CS-2 and two simulated architectures, we find that split-phase and push-based bulk data transfers are essential for good performance. Region-based caching benefits applications with irregular structure and with sufficient temporal locality, especially under high communication latencies. However, caching also hurts performance when there is insufficient data reuse or when the size of caching granularity is mismatched with the communication granularity. We find the programming complexity of the communication mechanisms in both languages to be comparable. Based on our results, we recommend that an ideal system intended to support diverse applications on parallel platforms should incorporate the communication mechanisms in CRL and Split-C.
Shared-memory performance profiling
Authors: Xu Zhichen , Larus James R. , Miller Barton P.
Published: November 2005

This paper describes a new approach to finding performance bottlenecks in shared-memory parallel programs and its embodiment in the Paradyn Parallel Performance Tools running with the Blizzard fine-grain distributed shared memory system. This approach exploits the underlying system's cache coherence protocol to detect data sharing patterns that indicate potential performance bottlenecks and presents performance measurements in a data-centric manner. As a demonstration, Parodyn helped us improve the performance of a new shared-memory application program by a factor of four.
Improving parallel shear-warp volume rendering on shared address space multiprocessors
Authors: Jiang Dongming , Singh Jaswinder Pal
Published: November 2005

This paper presents a new parallel volume rendering algorithm and implementation, based on shear warp factorization, for shared address space multiprocessors. Starting from an existing parallel shear-warp renderer, we use increasingly detailed performance measurements on real machines and simulators to understand performance bottlenecks. This leads us to a new parallel implementation that substantially outperforms and out-scales the old one on a range of shared address space platforms, from bus-based centralized memory machine to hardware-coherent distributed memory machines to networks of computers connected by page-based shared virtual memory. The results demonstrate that real time volume rendering is promising on general purpose multiprocessors, and illustrate the utility of tool hierarchies in conjunction with algorithmic and application knowledge to understand memory system interactions and improve parallel algorithms.
LoPC
Authors: Frank Matthew I. , Agarwal Anant , Vernon Mary K.
Published: November 2005

Parallel algorithm designers need computational models that take first order system costs into account, but are also simple enough to use in practice. This paper introduces the LoPC model, which is inspired by the LogP model but accounts for contention for message processing resources in parallel algorithms on a multiprocessor or network of workstations. LoPC takes the
L
,
o
and
P
parameters directly from the LogP model and uses them to predict the cost of contention,
C
.This paper defines the LoPC model and derives the general form of the model for parallel applications that communicate via active messages. Model modifications for systems that implement coherent shared memory abstractions are also discussed. We carry out the analysis for two important classes of applications that have irregular communication. In the case of parallel applications with homogeneous all-to-any communication, such as sparse matrix computations, the analysis yields a simple rule of thumb and insight into contention costs. In the case of parallel client-server algorithms, the LoPC analysis provides a simple and accurate calculation of the optimal allocation of nodes between clients and servers. The LoPC estimates for these applications are shown to be accurate when compared against event driven simulation and against a sparse matrix computation on the MIT Alewife multiprocessor.
Web pages that reproduce themselves by JavaScript
Authors: Kanada Yasusi
Published: November 2005

A JavaScript program in a Web page can clear the page content including the program itself and generate new content. The program can generate exactly the same content including the program itself. This means that a Web page can reproduce itself by JavaScript program that is included in the page. Although exact reproduction is useless, inexact reproduction, which transform part of the content, is usable for more practical purpose. For example, Web pages that change its view from outline mode to detail mode by clicking a button in the page can be implemented using this method. This method can also applicable to other types of documents, such as SGML or XML, if the document may contain self-reproductive program. Another method for reproducing Web pages without reproducing programs is also mentioned. Reproductive Web pages partially but really work on Netscape Navigator.
An evaluation of high performance Fortran
Authors: Hansen Per Brinch
Published: November 2005

High Performance Fortran (HPF) is evaluated by rewriting sequential model programs for Householder reduction, simulated annealing, and grid relaxation. The author concludes that HPF has severe conceptual and practical limitations.
Set of tools for native code generation for the Java virtual machines
Authors: Azañón Esteire Oscar , Lovelle Juan Manuel Cueva
Published: November 2005

J--- is a set of tools designed for system developers who need to generate native code for the Java virtual machine. This set of tools is composed by a disassembler, an assembler, an integrated environment and a class library that hides the binary format used by JVM to represent its classes. This package includes comprehensive documentation, which allows its use without any previous knowledge on JVM. The project is not platform specific, and it is currently running on Windows95, WindowsNT and Xwindow.
Recovering software architecture from multiple source code analyses
Authors: Chase Melissa P. , Christey Steven M. , Harris David R. , Yeh Alexander S.
Published: November 2005

We describe the experiences we have had in using ManSART - a software architecture recovery tool that we developed and are employing in the analysis of large scale legacy software systems. ManSART uses a battery of standard data flow, control flow, and program slicing capabilities to automatically recover architectural features from source code. This source code analysis is enabled by representations called analysis. Analysis modules describe the interfaces of each component in a multiple component system. ManSART uses these modules to focus source code analysis and to store the results.
A new algorithm for scalar register promotion based on SSA form
Authors: Sastry A. V. S. , Ju Roy D. C.
Published: November 2005

We present a new register promotion algorithm based on Static Single Assignment (SSA) form. Register promotion is aimed at promoting program names from memory locations to registers. Our algorithm is profile-driven and is based on the scope of intervals. In cases where a complete promotion is not possible because of the presence of function calls or pointer references, the proposed algorithm is capable of eliminating loads and stores on frequently executed paths by placing loads and stores on less frequently executed paths. We also describe an efficient method to incrementally update SSA form when new definitions are cloned from an existing name during register promotion. On SPECInt95 benchmarks, our algorithm removes about ~12% of memory operations which access scalar variables.
Simplification of array access patterns for compiler optimizations
Authors: Paek Yunheung , Hoeflinger Jay , Padua David
Published: November 2005

Existing array region representation techniques are sensitive to the complexity of array subscripts. In general, these techniques are very accurate and efficient for simple subscript expressions, but lose accuracy or require potentially expensive algorithms for complex subscripts. We found that in scientific applications, many access patterns are simple even when the subscript expressions are complex. In this work, we present a new, general array access representation and define operations for it. This allows us to aggregate and simplify the representation enough that precise region operations may be applied to enable compiler optimizations. Our experiments show that these techniques hold promise for speeding up applications.
An implementation of complete, asynchronous, distributed garbage collection
Authors: Le Fessant Fabrice , Piumarta Ian , Shapiro Marc
Published: November 2005

Most existing reference-based distributed object systems include some kind of acyclic garbage collection, but fail to provide acceptable collection of cyclic garbage. Those that do provide such GC currently suffer from one or more problems: synchronous operation, the need for expensive global consensus or termination algorithms, susceptibility to communication problems, or an algorithm that does not scale. We present a simple, complete, fault-tolerant, asynchronous extension to the (acyclic) cleanup protocol of the SSP Chains system. This extension is scalable, consumes few resources, and could easily be adapted to work in other reference-based distributed object systems---rendering them usable for very large-scale applications.
Run-time code generation and modal-ML
Authors: Wickline Philip , Lee Peter , Pfenning Frank
Published: November 2005

This paper presents a typed programming language and compiler for run-time code generation. The language, called ML', extends ML with modal operators in the style of the Mini-ML'

e

language of Davies and Pfenning. ML' allows programmers to use types to specify precisely the stages of computation in a program. The types also guide the compiler in generating target code that exploits the staging information through the use of run-time code generation. The target machine is currently a version of the Categorical Abstract Machine, called the CCAM, which we have extended with facilities for run-time code generation.This approach allows the programmer to express the staging that he wants directly to the compiler. It also provides a typed framework in which to verify the correctness of his staging intentions, and to discuss his staging decisions with other programmers. Finally, it supports in a natural way multiple stages of run-time specialization, so that dynamically generated code can be used in the generation of yet further specialized code.This paper presents an overview of the language, with several examples of programs that illustrate key concepts and programming techniques. Then, it discusses the CCAM and the compilation of ML' programs into CCAM code. Finally, the results of some experiments are shown, to demonstrate the benefits of this style of run-time code generation for some applications.
Thin locks
Authors: Bacon David F. , Konuru Ravi , Murthy Chet , Serrano Mauricio
Published: November 2005

Language-supported synchronization is a source of serious performance problems in many Java programs. Even single-threaded applications may spend up to half their time performing useless synchronization due to the thread-safe nature of the Java libraries. We solve this performance problem with a new algorithm that allows lock and unlock operations to be performed with only a few machine instructions in the most common cases. Our locks only require a partial word per object, and were implemented without increasing object size. We present measurements from our implementation in the JDK 1.1.2 for AIX, demonstrating speedups of up to a factor of 5 in micro-benchmarks and up to a factor of 1.7 in real programs.
Fast, effective code generation in a just-in-time Java compiler
Authors: Adl-Tabatabai Ali-Reza , Cierniak Michał , Lueh Guei-Yuan , Parikh Vishesh M. , Stichnoth James M.
Published: November 2005

A "Just-In-Time" (JIT) Java compiler produces native code from Java byte code instructions during program execution. As such, compilation speed is more important in a Java JIT compiler than in a traditional compiler, requiring optimization algorithms to be lightweight and effective. We present the structure of a Java JIT compiler for the Intel Architecture, describe the lightweight implementation of JIT compiler optimizations (e.g., common subexpression elimination, register allocation, and elimination of array bounds checking), and evaluate the performance benefits and tradeoffs of the optimizations. This JIT compiler has been shipped with version 2.5 of Intel's VTune for Java product.
Understanding class evolution through atomic changes
Authors: Rangarajan K. , Eswar P.
Published: November 2005

Class-based object-oriented programming languages encourage developers to implement a software system as a collection of classes and objects. When the software evolves across versions for various reasons, changes are made to one or more classes in the original version. Our research focus is on studying the class evolution pattern looking for clues about minimizing retest effort. In this article, we show that class evolution is governed by a finite set of

atomic changes

that are language-specific, discuss some properties of these changes and show how they may be identified for a programming language.
Static header as sentinel
Authors: Ancona Massimo , Cazzola Walter
Published: November 2005

Writing code to handle dynamic data structures might seem to be an easy task, but write an efficient, readable and maintainable code is not such a simple task.In this short note we investigate some problems in developing code for handling dynamic data structures, and we propose techniques to overcome them. We take into account the interesting method proposed by Qiu in SIGPLAN Notices [3].Many authors have addressed the problem of handling dynamic data structures by suggesting several clever tricks to simplify dynamic data structures management [4, 2] and to avoid the non-uniform behavior of empty data structures, and access to the first and the last element. In particular, the use of
data sentinels
and
dummy headers
makes the implementation more orthogonal and easy to maintain. The cost is a slightly increased size in space which is negligible when compared with the benefits produced.
Per Brinch Hansen's concerns about high performance Fortran
Authors: Offner Carl D.
Published: November 2005

Per Brinch Hansen's criticisms of High Performance Fortran in the March issue of this journal are examined and shown to be without foundation.
Optimizing away C++ exception handling
Authors: Schilling Jonathan L.
Published: November 2005

A high performance implementation of C++ exception handling is crucial, because exception handling overhead is distributed across all code. The commonly-used table-driven approach to implementing exception handling can be augmented by an optimization that seeks to identify functions for which (contrary to first appearance) no exception handling tables need be generated at all. This optimization produces modest but useful gains on some existing C++ code, but produces very significant size and speed gains on code that uses empty exception specifications, avoiding otherwise serious performance losses.
Adaptive plug-and-play components for evolutionary software development
Authors: Mezini Mira , Lieberherr Karl
Published: November 2005

In several works on design methodologies, design patterns, and programming language design, the need for program entities that capture the patterns of collaboration between several classes has been recognized. The idea is that in general the unit of reuse is not a single class, but a slice of behavior affecting a set of collaborating classes. The absence of large-scale components for expressing these collaborations makes object-oriented programs more difficult to maintain and reuse, because functionality is spread over several methods and it becomes difficult to get the "big picture". In this paper, we propose
Adaptive Plug and Play Components
to serve this need. These components are designed such that they not only facilitate the construction of complex software by making the collaborations explicit, but they do so in a manner that supports the evolutionary nature of both structure and behavior.
Logical observable entities
Authors: Rossie Jonathan G.
Published: November 2005

We show how finite-state machines can standardize the protocol used by a component object to notify other interested objects of its state changes, resulting in a more effective use of static types to constrain both parties, and a more efficient dissemination of information. The enhanced component specification is called a
logical observable entity
, or LOE. We address two key issues in effectively applying such a strategy: how to extend subtyping to consider the state machines, and how to ensure some kind of compliance between the state-machine specification and its implementation. This leads to an unusual subtyping predicate for LOEs on the one hand, and a prototype code generation strategy on the other.
Compound types for Java
Authors: Büchi Martin , Weck Wolfgang
Published: November 2005

Type compatibility can be defined based on name equivalence, that is, explicit declarations, or on structural matching. We argue that component software has demands for both. For types expressing individual contracts, name equivalence should be used so that references are made to external semantical specifications. For types that are composed of several such contracts, the structure of this composition should decide about compatibility.We introduce compound types as the mechanism to handle such compositions. To investigate the integrability into a strongly typed language, we add compound types to Java and report on a mechanical soundness proof of the resulting type system.Java users benefit from the higher expressiveness of the extended type system. We introduce compound types as a strict extension of Java, that is without invalidating existing programs. In addition, our proposal can be implemented on the existing Java Virtual Machine.
Multiple dispatch as dispatch on Tuples
Authors: Leavens Gary T. , Millstein Todd D.
Published: November 2005

Many popular object-oriented programming languages, such as C++, Smalltalk-80, Java, and Eiffel, do not support multiple dispatch. Yet without multiple dispatch, programmers find it difficult to express binary methods and design patterns such as the "visitor" pattern. We describe a new, simple, and orthogonal way to add multimethods to single-dispatch object-oriented languages, without affecting existing code. The new mechanism also clarifies many differences between single and multiple dispatch.
Contraint-based polymorphism in Cecil
Authors: Litvinov Vassily
Published: November 2005

We present a static type system for object-oriented languages which strives to provide static typechecking without resorting to dynamic "type casts," restricting what code the programmer can write, or being too verbose or difficult to use in practice. The type system supports bounded parametric polymorphism where the bounds on type variables can be expressed using general recursive subtype or signature constraints, with F-bounded polymorphism and covariant type parameters being special cases.We implemented this type system in the Cecil language and used it to successfully typecheck a 100,000-line Cecil program, the Vortex optimizing compiler. Our experience was very good: dynamically-typed code needed very little rewriting. We also observed several common programming situations that presented a challenge for our type system. We discuss these situations and ways to typecheck them statically.
Segregating heap objects by reference behavior and lifetime
Authors: Seidl Matthew L. , Zorn Benjamin G.
Published: November 2005

Dynamic storage allocation has become increasingly important in many applications, in part due to the use of the object-oriented paradigm. At the same time, processor speeds are increasing faster than memory speeds and programs are increasing in size faster than memories. In this paper, we investigate efforts to predict heap object reference and lifetime behavior at the time objects are allocated. Our approach uses profile-based optimization, and considers a variety of different information sources present at the time of object allocation to predict the object's reference frequency and lifetime. Our results, based on measurements of six allocation intensive programs, show that program references to heap objects are highly predictable and that our prediction methods can successfully predict the behavior of these heap objects. We show that our methods can decrease the page fault rate of the programs measured, sometimes dramatically, in cases where the physical memory available to the program is constrained.
An empirical analysis of instruction repetition
Authors: Sodani Avinash , Sohi Gurindar S.
Published: November 2005

We study the phenomenon of instruction repetition, where the inputs and outputs of multiple dynamic instances of a static instruction are repeated. We observe that over 80% of the dynamic instructions executed in several programs are repeated and most of the repetition is due to a small number of static instructions. We attempt understand the source of this repetitive behavior by categorizing dynamic program instructions into dynamic program slices at both a global level and a local (within function) level. We observe that repeatability is more an artifact of how computation is expressed, and less of program inputs. Function-level analysis suggests that many functions are called with repeated arguments, though almost all of them have side effects. We provide commentary on exploiting the observed phenomenon and its sources in both software and hardware.
VISA
Authors: Van Meter Rodney , Finn Gregory G. , Hotz Steve
Published: November 2005

In this paper we describe the implementation of VISA, our Virtual Internet SCSI Adapter. VISA was built to evaluate the performance impact on the host operating system of using IP to communicate with peripherals, especially storage devices. We have built and benchmarked file systems on VISA-attached emulated disk drives using UDP/IP. By using IP, we expect to take advantage of its scaling characteristics and support for heterogeneous media to build large, long-lived systems. Detailed file system and network CPU utilization and performance data indicate that it is possible for UDP/IP to reach more than 80% of SCSI's maximum throughput without the use of network coprocessors. We conclude that IP is a viable alternative to special-purpose storage network protocols, and presents numerous advantages.
Dependence based prefetching for linked data structures
Authors: Roth Amir , Moshovos Andreas , Sohi Gurindar S.
Published: November 2005

We introduce a dynamic scheme that captures the accesspat-terns of linked data structures and can be used to predict future accesses with high accuracy. Our technique exploits the dependence relationships that exist between loads that produce addresses and loads that consume these addresses. By identzj+ing producer-consumer pairs, we construct a compact internal representation for the associated structure and its traversal. To achieve a prefetching eflect, a small prefetch engine speculatively traverses this representation ahead of the executing program. Dependence-based prefetching achieves speedups of up to 25% on a suite of pointer-intensive programs.
Cache-conscious data placement
Authors: Calder Brad , Krintz Chandra , John Simmi , Austin Todd
Published: November 2005

As the gap between memory and processor speeds continues to widen, cache eficiency is an increasingly important component of processor performance. Compiler techniques have been used to improve instruction cache pet$ormance by mapping code with temporal locality to different cache blocks in the virtual address space eliminating cache conflicts. These code placement techniques can be applied directly to the problem of placing data for improved data cache pedormance.In this paper we present a general framework for Cache Conscious Data Placement. This is a compiler directed approach that creates an address placement for the stack (local variables), global variables, heap objects, and constants in order to reduce data cache misses. The placement of data objects is guided by a temporal relationship graph between objects generated via profiling. Our results show that profile driven data placement significantly reduces the data miss rate by 24% on average.
Overlapping execution with transfer using non-strict execution for mobile programs
Authors: Krintz Chandra , Calder Brad , Lee Han Bok , Zorn Benjamin G.
Published: November 2005

In order to execute a program on a remote computer, it mustfirst be transferred over a network. This transmission incurs the over-head of network latency before execution can begin. This latency can vary greatly depending upon the size of the program., where it is located (e.g., on a local network or across the Internet), and the bandwidth available to retrieve the program. Existing technologies, like Java, require that a jle be filly transferred before it can start executing. For large files and low bandwidth lines, this delay can be significant.In this paper we propose and evaluate a non-strict form of mobile program execution. A mobile program is any program that is transferred to a different machine and executed. The goal of nonstrict execution is to overlap execution with transfer; allowing the program to start executing as soon as possible. Non-strict execution allows a procedure in the program to start executing as soon as its code and data have transferred. To enable this technology, we examine several techniques for rearranging procedures and reorganizing the data inside Java classjles. Our results show that nonstrict execution decreases the initial transfer delay between 31% and 56% on average, with an average reduction in overall execution time between 25% and 40%.
Investigating optimal local memory performance
Authors: Temam Olivier
Published: November 2005

Recent work has demonstrated that, cache space is often poorly utilized. However, no previous work has yet demonstrated upper bounds on what a cache or local memory could achieve when exploiting both spatial and temporal locality. Belady's MIN algorithm does yield an upper bound, but exploits only temporal locality. In this article, we present an optimal replacement algorithm for local memory that exploits temporal locality and spatial locality simultaneously. This algorithm is an extension of Belady's algorithm. We prove the optimality of this new algorithm with respect to minimizing misses, and we show experimentally that the algorithm produces nearly minimum memory traffic on the SPEC95 benchmarks. Like Belady's algorithm, our algorithm requires the entire program trace. It selects replacement victims and the number of words it fetches at once based on future accesses. Many different spatial locality strategies can be implemented with this algorithm. With an optimal strategy, the algorithm yields an upper bound that enables us to evaluate alternative implementations to today's caches. We further demonstrate the utility of this algorithm as an analysis tool by evaluating several intermediate strategies between cache and optimal to highlight the limitations of the cache line paradigm using the SPEC95 benchmarks.
Precise miss analysis for program transformations with caches of arbitrary associativity
Authors: Ghosh Somnath , Martonosi Margaret , Malik Sharad
Published: November 2005

Analyzing and optimizing program memory performance is a pressing problem in high-performance computer architectures. Currently, software solutions addressing the processor-memory performance gap include compiler-or programmer-applied optimizations like data structure padding, matrix blocking, and other program transformations. Compiler optimization can be effective, but the lack of
precise
analysis and optimization frameworks makes it impossible to confidently make optimal, rather than heuristic-based, program transformations. Imprecision is most problematic in situations where hard-to-predict cache conflicts foil heuristic approaches. Furthermore, the lack of a
general
framework for compiler memory performance analysis makes it impossible to understand the combined effects of several program transformations.The Cache Miss Equation (CME) framework discussed in this paper addresses these issues. We express memory reference and cache conflict behavior in terms of sets of equations. The mathematical precision of CMEs allows us to find true optimal solutions for transformations like blocking or padding. The generality of CMEs also allows us to reason about interactions between transformations applied in concert. Unlike our prior work, this framework applies to caches of arbitrary associativity. This paper also demonstrates the utility of CMEs by presenting precise algorithms for intra-variable padding, inter-variable padding, and selecting tile sizes. Our experiences with CMEs implemented in the SUIF system show that they are a unifying mathematical framework offering the generality and precision imperative for compiler optimizations on current high-performance architectures.
A look at several memory management units, TLB-refill mechanisms, and page table organizations
Authors: Jacob Bruce L. , Mudge Trevor N.
Published: November 2005

Virtual memory is a staple in modem systems, though there is little agreement on how its functionality is to be implemented on either the hardware or software side of the interface. The myriad of design choices and incompatible hardware mechanisms suggests potential performance problems, especially since increasing numbers of systems (even embedded systems) are using memory management. A comparative study of the implementation choices in virtual memory should therefore aid system-level designers.This paper compares several virtual memory designs, including combinations of hierarchical and inverted page tables on hardware-managed and software-managed translation lookaside buffers (TLBs). The simulations show that systems are fairly sensitive to TLB size; that interrupts already account for a large portion of memory-management overhead and can become a significant factor as processors execute more concurrent instructions; and that if one includes the cache misses inflicted on applications by the VM system, the total VM overhead is roughly twice what was thought (10--20% rather than 5--10%).
Higher-order arity raising
Authors: Hannan John , Hicks Patrick
Published: November 2005

Arity raising, also known as variable splitting or flattening, is the program optimization which transforms a function of one argument into a function of several arguments by decomposing the structure of the original one argument into individual components in that structure. This optimization eliminates the need for the structuring of the components and also allows more arguments to be passed in registers during a function call. We present a formal specification of arity raising for a higher-order functional language. This specification supports the general arity raising of functions, even for functions which are passed as arguments or returned as values. We define a practical algorithm, based on algorithm
W
, which implements arity raising, and we prove this algorithm sound with respect to the deductive system. These results provide a declarative framework for reasoning about arity raising and support a richer form of the transformation than is currently found in compilers for functional languages.