bluuebunny/crossref_metadata_2025 huggingface dataset:
Data locality and load balancing in COOL
Authors: Chandra Rohit , Gupta Anoop , Hennessy John L.
Published: November 2005

Large-scale shared memory multiprocessors typically support a multilevel memory hierarchy consisting of per-processor caches, a local portion of shared memory, and remote shared memory. On such machines, the performance of parallel programs is often limited by the high latency of remote memory references. In this paper we explore how knowledge of the underlying memory hierarchy can be used to schedule computation and distribute data structures, and thereby improve data locality. Our study is done in the context of COOL, a concurrent object-oriented language developed at Stanford. We develop abstractions for the programmer to supply optional information about the data reference patterns of the program. This information is used by the runtime system to distribute tasks and objects so that the tasks execute close (in the memory hierarchy) to the objects they reference.

We demonstrate the effectiveness of these techniques by applying them to several applications chosen from the SPLASH parallel benchmark suite. Our experience suggests that improving data locality can be simple through a combination of programmer abstractions and smart runtime scheduling.
SW 2 - An object-based programming environment
Authors: Laff Mark R. , Hailpern Brent
Published: November 2005

Programming systems traditionally deal with only a few different types of data objects. Operating-system command languages, for example, are concerned with files and programs. Typical programming languages deal with computer-related objects such as integers, strings, arrays, and records. This is in sharp contrast to the variety of real-world objects that people reason about. Smallworld is a programming environment in which the real world is represented by
objects
that have
properties
. A property represents a fact about the corresponding real-world entity. Thus Smallworld actions (programs), which operate on objects specified in this simple but general way, are “smart”: they consider all of the relevant facts concerning (that is, all of the properties of) the objects they manipulate.

Smallworld was strongly influenced by the design of Smalltalk, especially in the organization of objects into classes and superclasses. The two languages differ (1) in their treatment of the difference between classes and objects that are not classes and (2) in their definition of methods that act on classes. Smallworld minimizes the differences between classes and non-class objects, resulting in a simpler and more consistent system. Where Smalltalk is a programming language using a pure object-oriented paradigm and dependent on a powerful graphical interface, Smallworld is a shell language that runs on conventional terminals and allows multiple program paradigms where appropriate.
Mechanical analysis of program complexity
Authors: Metayer D. Le
Published: November 2005

There has been a great deal of research done which investigates the problem of evaluating the complexity of particular algorithms; little effort however has been applied to the mechanization of this evaluation. This paper presents the ACE (for Automatic Complexity Evaluator) system which is able to analyse reasonably large programs like sorting programs or numerical programs in a fully mechanical way. A complexity function is derived from the initial program. This function is then automatically transformed into its non-recursive equivalent according to MacCarthy's recursion induction principle, using a pre-defined library of recursive definitions (for example id, length, exponential ...). As the execution time is not a decidable property, this transformation will not be possible in all cases. The richer the pre-defined library is, the more likely the system is to succeed. The paper presents the reasons for mechanizing complexity calculus and the problems involved. It describes the operations performed by ACE and its implementation; limitations and further improvements are discussed in conclusion.
Libraries as programs preserved within compiler continuations
Authors: Wells Mark B. , Hug Margaret A. , Silver Rollo
Published: November 2005

An approach to library organization for block-structured languages is given that avoids corrupting such structuring with the introduction of “modules”, “units”, or “packages”. The scheme involves
retentive block structuring
and the preservation of partially compiled programs as
compiler continuations.
Its chief advantage is language simplicity. Its chief disadvantage is, at the present, its proclivity towards redundant file storage. This can possibly be eliminated by adopting a computational model using a one-level store.
The impact of interprocedural analysis and optimization on the design of a software development environment
Authors: Cooper Keith D. , Kennedy Ken , Torczon Linda
Published: November 2005

One of the primary goals of the IR
n
programming environment project is to mount a concerted attack on the problems of performing interprocedural analysis and optimization in a compiler. Few commercial optimizing compilers employ interprocedural techniques because the cost of gathering the requisite information in a traditional compiler is too great. Computing the side effects of a procedure call requires detailed knowledge of the internals of both the called procedure and any procedures invoked either directly or indirectly from it. Thus, the compiler potentially needs information about the internals of every procedure to determine the side effects of procedure calls, even separately compiled procedures. Gathering this information would require examining the source of every procedure in the program - an expensive process, particularly unfortunate since the primary goal of separate compilation is to reduce the amount of recompilation required in response to changes in an individual procedure.

The existence of a software development environment like the IR
n
programming environment [HoKe 84] changes the compilation process enough to make computing such information palatable. Since all modules are developed and all programs are defined using tools of the environment, these tools can cooperate to record the information necessary to do a good job of interprocedural analysis and optimization. Whenever the compiler needs information about possible side effects of a particular procedure, it can simply extract this information from the environment's central database. Because the only mechanism for changing modules or programs is through the tools provided by the environment, the compiler is assured that it will be notified of any changes. Thus, it can use information derived from previous analysis with certain knowledge that the information reflects the current state of the program and its procedures.
A simple software environment based on objects and relations
Authors: MacLennan Bruce J.
Published: November 2005

This paper presents a simple programming system based on a clear separation of
value-oriented programming
and
object-oriented programming
[MacLennan82, MacLennan83a]. The value-oriented component is a conventional functional programming language. The object-oriented component is based on a model of objects and values connected by relations, and on production system-like rules that determine the alteration of these relations through time. It is shown that these few basic ideas permit simple prototyping of a software development environment.
The Mesa programming environment
Authors: Sweet Richard E.
Published: November 2005

People everywhere are developing multi-window, integrated programming environments for their favorite computers and languages. This paper describes the Mesa programming facilities of the Xerox Development Environment (XDE). It is interesting for several reasons. It has existed in something similar to its current form for about 5 years. It has more than 500 users, many interacting with it 8 or more hours a day. Several million lines of code have been written by these users, including large, multi-author systems.

Previous papers have dealt with the Mesa language [Geschke77, Mitchell79], the operating system [Redell79, Lampson80] and the processor architecture on which it runs [Johnsson82, Sweet82]. This paper describes the programming environment: the user illusion, the set of programming tools, and the facilities available for augmenting the environment. Section 2 gives a short history of the environment, including some of our original design goals. Section 3 describes the current state of the user interface and discusses a few of the schemes that were tried and discarded. Section 4 describes some of the program development tools available and discusses how features of the language have influenced their design, and indeed influenced what tools are in the set. Section 5 describes other tools that, although valuable to the programming task, are largely language independent. Section 6 talks about how easy it is to make additions to the system, and gives examples of user additions—some that modify the environment and some that simply provide new tools. Section 7 discusses what we feel are major successes and what we feel needs to be done in the future.
The structure of Cedar
Authors: Swinehart Daniel C. , Zellweger Polle T. , Hagmann Robert B.
Published: November 2005

This paper presents an overview of the Cedar programming environment, focusing primarily on its overall structure: the major components of Cedar and the way they are organized. Cedar supports the development of programs written in a single programming language, also called Cedar. We will emphasize the extent to which the Cedar language, with runtime support, has influenced the organization, comprehensibility, and stability of Cedar.

Produced in the Computer Science Laboratory (CSL) at the Xerox Palo Alto Research Center, Cedar is a research environment supporting the development and use of experimental programs, emphasizing office information and personal information management applications. Although it was clear that some unsolved problems would be addressed, the intent was to combine well-understood methods and technologies to exploit a new generation of high-performance personal computers, including the Xerox 1132 (Dorado) and Xerox 1108 (Dandelion).
Computational reflection in PowerEpsilon
Authors: Zhu Ming-Yuan
Published: November 2005

Reflective programming languages were introduced in order to study programs that need knowledge of their own behavior. In artificial intelligence, this kind of knowledge is heeded, for example, in programs that must explain their behavior to a user. In the study of programming languages, a similar phenomenon occurs in extensible languages, that is, languages in which one can write programs that change the language itself. In this paper, we present an investigation of computational reflection mechanism in a higher-order λ-calculus - PowerEpsilon. We will show that PowerEpsilon is an extremely rich and powerful language for reflective computation.
A bibliography on parallel parsing
Authors: Alblas Henk , op den Akker Rieks , Luttighuis Paul Oude , Sikkel Klaas
Published: November 2005

This bibliography on parallel parsing and recognition of context-free languages covers most of the important publications in this area of computer science and natural language processing. The list of publications is preluded by an introduction which presents an overview of the field.
Passing large dynamic objects out of function frame boundaries
Authors: Sharafuddin Ahsan J. , Ida Nathan , Grover James E.
Published: November 2005

It is a well known fact that passing objects
into
functions by reference (in C++) is more efficient than passing by value. Passing objects, created within functions,
out of
functions by reference could also be more efficient if it wasn't sure to cause memory-leak in the system. Programmers therefore resort to "pass-by-reference, return-by-value". Here we first briefly look at why it is important to be able to return by reference, particularly for large dynamic objects in mathematical applications, and then present a new scheme for doing so. The new method can attain efficiency comparable to that of 'method of reference counting', but without the undesirable side-effects of the latter.
The Concert signature representation
Authors: Auerbach Joshua S. , Russell James R.
Published: November 2005

In the Concert multilanguage distributed programming system, interface specification is the responsibility of programming languages, not a separate IDL. However, an IDL is still necessary in order to define equivalence between declarations in different languages. A single representation is also desirable internally to economize on aspects of the implementation. Consequently, Concert has an IDL as an intermediate language, produced by compiler front-ends and not normally manipulated by programmers. It is formally separated into a
contract
, which defines interoperability and an
endpoint modifier
, which captures the local choice of representation. Only contracts are used to define interface equivalence. Our choice of what kinds of information to put in the contract was motivated by a desire to be minimal, thereby enabling maximum feasible interoperability between different expressions of the same abstraction in the same or different languages.
Beyond definition/use
Authors: Allen Robert , Garlan David
Published: November 2005

Large software systems require decompositional mechanisms in order to make them tractable. Traditionally, MILs and IDLs have played this role by providing notations based on definition/use bindings. In this paper we argue that current MIL/IDLs based on definition/use have some serious drawbacks. A significant problem is that they fail to distinguish between "implementation" and "interaction" relationships between modules. We propose an alternative model in which components interact along welldefined lines of communication -- or connectors. Connectors are defined as protocols that capture the expected patterns of communication between modules. We show how this leads to a scheme that is much more expressive for architectural relationships, that allows the formal definition of module interaction, and that supports its own form of automated checks and formal reasoning.
A pragmatic approach to software synthesis
Authors: Freitag Burkhard , Margaria Tiziana , Steffen Bernhard
Published: November 2005

We present a practice oriented tool for software synthesis that supports the interface-correct configuration of complex systems from a library of reusable software components. Besides simply checking the interface-correctness of a link by means of type constraints, the tool is also designed to propose software components for solving a (loosely) specified problem within a certain context. In particular, it identifies possible interfacing modules that in case of an interface-conflict may serve for the right conversion, transformation or parameter configuration. We illustrate our tool, which is based on the deductive database system
LOLA
, in three application specific settings.
A checkable interface language for pointer-based structures
Authors: Russell James R. , Strom Robert E. , Yellin Daniel M.
Published: November 2005

We present a technique for analysing structural constraints on data aggregates in high-level languages. Our technique includes a formal constraint language and a dataflow algorithm for automatically checking equality constraints. The constraint language is used to augment the type information on program interfaces. For example, one can specify that a procedure must return aggregates A and B where each element in aggregate A points to some element in aggregate B, and that parameter C will have the properties of a rooted tree both on input and output. Our dataflow algorithm tracks the constraints which must apply at each statement in order for the procedure to satisfy its interface, and detects invalid programs which fail to satisfy the constraints on their interfaces. We apply our technique to several examples.Our work is motivated by the requirements for expressive interface definition languages for distributed systems, and by the desire to mechanically check program modules against their interfaces. Our analysis techniques also yield information which may enable compilers and stub generators to produce better implementations.
A client-side stub interpreter
Authors: Kessler Peter B.
Published: November 2005

We have built a research operating system in which all services are presented through interfaces described by an interface description language. The system consists of a micro-kernel that supports a small number of these interfaces, and a large number of interfaces that are implemented by user-level code. A typical service implements one or more interfaces, but is a client of many other interfaces that are implemented elsewhere in the system. We have an interface compiler that generates client-side and server-side stubs to deliver calls from clients to servers, providing location transparency if the client and server are in different address spaces. The code for client-side stubs was occupying a large amount of the text space of our clients, so a stub interpreter was written to replace the clientside stub methods. The result was that we traded 125K bytes of stub code for 13K bytes of stub descriptions and 4K bytes of stub interpreter. This paper describes the stub interpreter, the stub descriptions, and discusses some alternatives.
Interface definition language conversions
Authors: Gay David E.
Published: November 2005

A large heterogeneous network contains many applications developed in different environments, each with its own incompatible interface definition language. One way of dealing with this diversity is to define a conversion from the interfaces of one system into another, thus giving access from the second system to the first. This presents a number of difficulties, amongst which is the different representation of recursive types in different languages. This paper gives two algorithms for converting the representation of such recursive types between different styles of interface definition languages.
Persistent shared object support in the Guide system
Authors: Hagimont Daniel , Chevalier P.-Y. , Freyssinet A. , Krakowiak S. , Lacourte S. , Mossière J. , Rousset de Pina X.
Published: November 2005

The purpose of the Guide project is to explore the use of shared objects for communication in a distributed system, especially for applications that require cooperative work. Since 1986, two prototypes have been implemented respectively on top of Unix (Guide-1) and Mach 3.0 (Guide-2). They have been used for the development of distributed cooperative applications, allowing us to validate or reject many design choices in the system.

This paper gathers the lessons learned from our experience and compares the basic design choices with those in other distributed object-oriented systems. The lessons may be summarized as follows. This system layer must provide a generic interface for the support of several object-oriented languages. It must manage fine grained objects and enforce protection between objects and processes. These requirements can be achieved with an acceptable trade-off between protection and efficiency.
Extensible file system (ELFS)
Authors: Karpovich John F. , Grimshaw Andrew S. , French James C.
Published: November 2005

Scientific applications often manipulate very large sets of persistent data. Over the past decade, advances in disk storage device performance have consistently been outpaced by advances in the performance of the rest of the computer system. As a result, many scientific applications have become I/O-bound, i.e. their run-times are dominated by the time spent performing I/O operations. Consequently, the performance of I/O operations has become critical for high performance in these applications. The ELFS approach is designed to address the issue of high performance I/O by treating files as typed objects. Typed file objects can exploit knowledge about the file structure and type of data. Typed file objects can selectively apply techniques such as prefetching, parallel asynchronous file access, and caching to improve performance. Also, by typing objects, the interface to the user can be improved in two ways. First, the interface can be made easier to use by presenting file operations in a more natural manner to the user. Second, the interface can allow the user to provide an “oracle” about access patterns, that can allow the file object to improve performance. By combining these concepts with the object-oriented paradigm, the goal of the ELFS methodology is to create flexible, extensible file classes that are easy to use while achieving high performance. In this paper we present the ELFS approach and our experiences with the design and implementation of two file classes: a two dimensional dense matrix file class and a multidimensional range searching file class.
Development of an OO infrastructure for mainframe database applications
Authors: Rothering Darryl James
Published: November 2005

Large mainframe installations need and want to exploit the advantages of Object Technology (OT), but without totally abandoning their legacy environments. Implementing Object Orientation in such a COBOL/CICS/DB2 environment is a challenge: there is neither language support, nor development tools, nor execution infrastructure, nor testing utilities. Yet Object Orientation can be fully implemented, and a project can still meet rigorous performance requirements and tough delivery time scales. The key is to develop an infrastructure. This paper relates the lessons learned in designing and implementing such an OO infrastructure at British Telecom.
Reducing cross domain call overhead using batched futures
Authors: Bogle Phillip , Liskov Barbara
Published: November 2005

In many systems such as operating systems and databases it is important to run client code in a separate protection domain so that it cannot interfere with correct operation of the system. Clients communicate with the server by making cross domain calls, but these are expensive, often costing substantially more than running the call itself. This paper describes a new mechanism called batched futures that transparently batches possibly interrelated client calls. Batching makes domain crossings happen less often, thus substantially reducing the cost. We describe how the mechanism is implemented for the Thor object-oriented database system, and presents performance results showing the benefit of the mechanism on various benchmarks.
Persistent storage for a workflow tool implemented in Smalltalk
Authors: Beck Bob , Hartley Steve
Published: November 2005

This paper describes a new workflow model and its implementation in Smalltalk. The paper also details problems with using a RDBMS as the persistent store for the workflow tool and the subsequent experiences in using an ODBMS for this purpose. The final solution was a
coexistence approach
, using the RDBMS for legacy corporate data and the ODBMS for the process description and workflow status data.
A status report on the OO7 OODBMS benchmarking effort
Authors: Carey Michael J. , DeWitt David J. , Kant Chander , Naughton Jeffrey F.
Published: November 2005

The OO7 Benchmark was first published in 1993, and has since found a home in the marketing literature of various object-oriented database management system (OODBMS) vendors. The OO7 Benchmark (as published) was the initial result of an ongoing OODBMS performance evaluation effort at the University of Wisconsin. This paper provides an update on the status of the effort on two fronts: single-user and multi-user. On the single-user front, we review and critique the design of the initial OO7 Benchmark. We discuss some of its faults, the reasons for those faults, and things that might be done to correct them. On the multi-user front, we describe our current work on the development of a multi-user benchmark for OODBMSs. This effort includes changes and extensions to the OO7 database and the design of a family of interesting multi-user workloads.
Combining contracts and exemplar-based programming for class hiding and customization
Authors: Lortz Victor B. , Shin Kang G.
Published: November 2005

For performance reasons, client applications often need to influence the implementation strategies of libraries whose services they use. If an object-oriented library contains multiple service classes customized for different usage patterns, applications can influence service implementations by instantiating the customized classes that match their needs. However, with many similar service classes, it can be difficult for applications to determine which classes to instantiate. Choosing the wrong class can result in very subtle errors since a customized class might use optimizations that work only over a restricted domain. In this paper, we show how client-side software contracts and exemplar-based class factories can be used to construct customized server objects. By expressing priorities and requirements in contracts, clients can delegate service class selection to the library and thereby avoid implicit dependencies on the library implementation. We have used this approach in the implementation of a real-time database system.
Agora
Authors: Codenie Wim , De Hondt Koen , D'Hondt Theo , Steyaert Patrick
Published: November 2005

Agora is a framework for exploring object-oriented languages. In this paper we will discuss a particular prototype-based instance of Agora that features a general mixin-based approach to (multiple) inheritance. One of the major innovations of Agora is that many important features of object-orientation including inheritance, slot access, reification, cloning and inline objects are introduced by means of message passing rather than by ordinary programming structures.The syntax and semantics of Agora is explained and illustrated with examples. Furthermore, an FTP-site is given where a Smalltalk implementation of Agora can be found.
The C++ interface in objectivity
Authors: Agarwal Rakesh
Published: November 2005

Computerized databases are essential and inseparable components of a vast majority of today's information systems. Database systems are used at all levels of management, research and production to provide uniform access and control of consistent information. Computer aided software engineering system require extensive database system support. Several industrial and academic research and development projects attempt to provide this support by using conventional database management systems or special purpose data managers.Object-oriented database management system technology provides a set of capabilities which are required by computer integrated software engineering systems. Our objective is to take advantage of this new technology and develop computer integrated software engineering systems that support complete user-defined life cycles with uniform interface and logical centralized database support. This paper presents Objectivity (DEC Object/DB) in relation to its architectural issues and shows how applications can be developed by the help of C++ interface.
Remarks on A methodology for implementing highly concurrent data
Authors: Skudlarek Joseph P.
Published: November 2005

Recently, a novel pair of process synchronization instructions,
load_linked
and
store_conditional
, were introduced into the computing repertoire. These instructions were used to define two novel and intriguing protocols for process synchronization, a lock free and a wait free protocol; these protocols do not require critical sections, and can be used for fault-tolerant processing. Additionally, the lock free protocol guarantees that at least one process will always make progress, while the wait free protocol guarantees that all processes will make progress. Herlihy [1993] does a superb job of presenting and illustrating these concepts and ideas. However, there are a number of issues and errors concerning correctness, clarity, and completeness that were left unaddressed, and they are identified and resolved in this paper.
Better C
Authors: Wang Thomas
Published: November 2005

C programmers are plagued by a variety of problems rooted at the language level. Memory corruption and memory leakage are two related problems that are hard to fix. The results are delayed or failed software projects.Better C is an Object-Oriented language based on the C language. Better C supports exception handling, the separation of abstraction versus implementation, and most importantly, an automatic memory manager suitable for interactive applications.With Better C, programmers can routinely write programs without memory problems.The motivation, and the description of Better C will be presented, with some examples to illustrate the key points.
Eliminate memory fragmentation through holes in the heap
Authors: Wang Thomas
Published: November 2005

Memory allocators have memory fragmentation problem, which can result in large amount of wasted memory. The capability to create unmapped pages in the heap can eliminate most of the memory fragmentation, and reduce paging I/O activity. This has implications to both manual, and automatic memory management.
Separating data and control transfer in distributed operating systems
Authors: Thekkath Chandramohan A. , Levy Henry M. , Lazowska Edward D.
Published: November 2005

Advances in processor architecture and technology have resulted in workstations in the 100+ MIPS range. As well, newer local-area networks such as ATM promise a ten- to hundred-fold increase in throughput, much reduced latency, greater scalability, and greatly increased reliability, when compared to current LANs such as Ethernet.

We believe that these new network and processor technologies will permit tighter coupling of distributed systems at the hardware level, and that distributed systems software should be designed to benefit from that tighter coupling. In this paper, we propose an alternative way of structuring distributed systems that takes advantage of a communication model based on remote network access (reads and writes) to protected memory segments.

A key feature of the new structure, directly supported by the communication model, is the separation of
data transfer
and
control transfer
. This is in contrast to the structure of traditional distributed systems, which are typically organized using message passing or remote procedure call (RPC). In RPC-style systems, data and control are inextricably linked—all RPCs must transfer both data and control, even if the control transfer is unnecessary.

We have implemented our model on DECstation hardware connected by an ATM network. We demonstrate how separating data transfer and control transfer can eliminate unnecessary control transfers and facilitate tighter coupling of the client and server. This has the potential to increase performance and reduce server load, which supports scaling in the face of an increasing number of clients. For example, for a small set of file server operations, our analysis shows a 50% decrease in server load when we switched from a communications mechanism requiring both control transfer and data transfer, to an alternative structure based on pure data transfer.
Scheduling and page migration for multiprocessor compute servers
Authors: Chandra Rohit , Devine Scott , Verghese Ben , Gupta Anoop , Rosenblum Mendel
Published: November 2005

Several cache-coherent shared-memory multiprocessors have been developed that are scalable and offer a very tight coupling between the processing resources. They are therefore quite attractive for use as compute servers for multiprogramming and parallel application workloads. Process scheduling and memory management, however, remain challenging due to the distributed main memory found on such machines. This paper examines the effects of OS scheduling and page migration policies on the performance of such compute servers. Our experiments are done on the Stanford DASH, a distributed-memory cache-coherent multiprocessor. We show that for our multiprogramming workloads consisting of sequential jobs, the traditional Unix scheduling policy does very poorly. In contrast, a policy incorporating cluster and cache affinity along with a simple page-migration algorithm offers up to two-fold performance improvement. For our workloads consisting of multiple parallel applications, we compare space-sharing policies that divide the processors among the applications to time-slicing policies such as standard Unix or gang scheduling. We show that space-sharing policies can achieve better processor utilization due to the operating point effect, but time-slicing policies benefit strongly from user-level data distribution. Our initial experience with automatic page migration suggests that policies based only on TLB miss information can be quite effective, and useful for addressing the data distribution problems of space-sharing schedulers.
Integration of message passing and shared memory in the Stanford FLASH multiprocessor
Authors: Heinlein John , Gharachorloo Kourosh , Dresser Scott , Gupta Anoop
Published: November 2005

The advantages of using message passing over shared memory for certain types of communication and synchronization have provided an incentive to integrate both models within a single architecture. A key goal of the FLASH (FLexible Architecture for SHared memory) project at Stanford is to achieve this integration while maintaining a simple and efficient design. This paper presents the hardware and software mechanisms in FLASH to support various message passing protocols. We achieve low overhead message passing by delegating protocol functionality to the programmable node controllers in FLASH and by providing direct user-level access to this messaging subsystem. In contrast to most earlier work, we provide an integrated solution that handles the interaction of the messaging protocols with virtual memory, protected multiprogramming, and cache coherence. Detailed simulation studies indicate that this system can sustain message-transfers rates of several hundred megabytes per second, effectively utilizing projected network bandwidths for next generation multiprocessors.
Software overhead in messaging layers
Authors: Karamcheti Vijay , Chien Andrew A.
Published: November 2005

Despite improvements in network interfaces and software messaging layers, software communication overhead still dominates the hardware routing cost in most systems. In this study, we identify the sources of this overhead by analyzing software costs of typical communication protocols built atop the active messages layer on the CM-5. We show that up to 50–70% of the software messaging costs are a direct consequence of the gap between specific network features such as arbitrary delivery order, finite buffering, and limited fault-handling, and the user communication requirements of in-order delivery, end-to-end flow control, and reliable transmission. However, virtually all of these costs can be eliminated if routing networks provide higher-level services such as in-order delivery, end-to-end flow control, and packet-level fault-tolerance. We conclude that significant cost reductions require changing the constraints on messaging layers: we propose designing networks and network interfaces which simplify or replace software for implementing user communication requirements.
Where is time spent in message-passing and shared-memory programs?
Authors: Chandra Satish , Larus James R. , Rogers Anne
Published: November 2005

Message passing and shared memory are two techniques parallel programs use for coordination and communication. This paper studies the strengths and weaknesses of these two mechanisms by comparing equivalent, well-written message-passing and shared-memory programs running on similar hardware. To ensure that our measurements are comparable, we produced two carefully tuned versions of each program and measured them on closely-related simulators of a message-passing and a shared-memory machine, both of which are based on same underlying hardware assumptions.

We examined the behavior and performance of each program carefully. Although the cost of computation in each pair of programs was similar, synchronization and communication differed greatly. We found that message-passing's advantage over shared-memory is not clear-cut. Three of the four shared-memory programs ran at roughly the same speed as their message-passing equivalent, even though their communication patterns were different.
Performance of a hardware-assisted real-time garbage collector
Authors: Schmidt William J. , Nilsen Kelvin D.
Published: November 2005

Hardware-assisted real-time garbage collection offers high throughput and small worst-case bounds on the times required to allocate dynamic objects and to access the memory contained within previously allocated objects. Whether the proposed technology is cost effective depends on various choices between configuration alternatives. This paper reports the performance of several different configurations of the hardware-assisted real-time garbage collection system subjected to several different workloads. Reported measurements demonstrate that hardware-assisted real-time garbage collection is a viable alternative to traditional explicit memory management techniques, even for low-level languages like C++.
eNVy
Authors: Wu Michael , Zwaenepoel Willy
Published: November 2005

This paper describes the architecture of eNVy, a large non-volatile main memory storage system built primarily with Flash memory. eNVy presents its storage space as a linear, memory mapped array rather than as an emulated disk in order to provide an efficient and easy to use software interface.

Flash memories provide persistent storage with solid-state memory access times at a lower cost than other solid-state technologies. However, they have a number of drawbacks. Flash chips are write-once, bulk-erase devices whose contents cannot be updated in-place. They also suffer from slow program times and a limit on the number of program/erase cycles. eNVy uses a copy-on-write scheme, page remapping, a small amount of battery backed SRAM, and high bandwidth parallel data transfers to provide low latency, in-place update semantics. A cleaning algorithm optimized for large Flash arrays is used to reclaim space. The algorithm is designed to evenly wear the array, thereby extending its lifetime.

Software simulations of a 2 gigabyte eNVy system show that it can support I/O rates corresponding to approximately 30,000 transactions per second on the TPC-A database benchmark. Despite the added work done to overcome the deficiencies associated with Flash memories, average latencies to the storage system are as low as 180ns for reads and 200ns for writes. The estimated lifetime of this type of storage system is in the 10 year range when exposed to a workload of 10,000 transactions per second.
Hardware and software support for efficient exception handling
Authors: Thekkath Chandramohan A. , Levy Henry M.
Published: November 2005

Program-synchronous exceptions, for example, breakpoints, watchpoints, illegal opcodes, and memory access violations, provide information about
exceptional
conditions, interrupting the program and vectoring to an operating system handler. Over the last decade, however, programs and run-time systems have increasingly employed these mechanisms as a performance optimization to detect
normal
and
expected
conditions. Unfortunately, current architecture and operating system structures are designed for exceptional or erroneous conditions, where performance is of secondary importance, rather than normal conditions. Consequently, this has limited the practicality of such hardware-based detection mechanisms.

We propose both hardware and software structures that permit efficient handling of synchronous exceptions by user-level code. We demonstrate a software implementation that reduces exception-delivery cost by an order-of-magnitude on current RISC processors, and show the performance benefits of that mechanism for several example applications.
Avoiding conflict misses dynamically in large direct-mapped caches
Authors: Bershad Brian N. , Lee Dennis , Romer Theodore H. , Chen J. Bradley
Published: November 2005

This paper describes a method for improving the performance of a large direct-mapped cache by reducing the number of conflict misses. Our solution consists of two components: an inexpensive hardware device called a Cache Miss Lookaside (CML) buffer that detects conflicts by recording and summarizing a history of cache misses, and a software policy within the operating system's virtual memory system that removes conflicts by dynamically remapping pages whenever large numbers of conflict misses are detected. Using trace-driven simulation of applications and the operating system, we show that a CML buffer enables a large direct-mapped cache to perform nearly as well as a two-way set associative cache of equivalent size and speed, although with lower hardware cost and complexity.
Surpassing the TLB performance of superpages with less operating system support
Authors: Talluri Madhusudhan , Hill Mark D.
Published: November 2005

Many commercial microprocessor architectures have added
translation lookaside buffer
(TLB) support for
superpages
. Superpages differ from segments because their size must be a power of two multiple of the base page size and they must be aligned in both virtual and physical address spaces. Very large superpages (e.g., 1MB) are clearly useful for mapping special structures, such as kernel data or frame buffers. This paper considers the architectural and operating system support required to exploit medium-sized superpages (e.g., 64KB, i.e., sixteen times a 4KB base page size). First, we show that superpages improve TLB performance only after invasive operating system modifications that introduce considerable overhead.

We then propose two subblock TLB designs as alternate ways to improve TLB performance. Analogous to a subblock cache, a
complete-subblock TLB
associates a tag with a superpage-sized region but has valid bits, physical page number, attributes, etc., for each possible base page mapping. A
partial-subblock TLB
entry is much smaller than a complete-subblock TLB entry, because it shares physical page number and attribute fields across base page mappings. A drawback of a partial-subblock TLB is that base page mappings can share a TLB entry only if they map to consecutive physical pages and have the same attributes. We propose a physical memory allocation algorithm,
page reservation
, that makes this sharing more likely. When page reservation is used, experimental results show partial-subblock TLBs perform better than superpage TLBs, while requiring simpler operating system changes. If operating system changes are inappropriate, however, complete-subblock TLBs perform best.
Dynamic memory disambiguation using the memory conflict buffer
Authors: Gallagher David M. , Chen William Y. , Mahlke Scott A. , Gyllenhaal John C. , Hwu Wen-mei W.
Published: November 2005

To exploit instruction level parallelism, compilers for VLIW and superscalar processors often employ static code scheduling. However, the available code reordering may be severely restricted due to ambiguous dependences between memory instructions. This paper introduces a simple hardware mechanism, referred to as the
memory conflict buffer
, which facilitates static code scheduling in the presence of memory store/load dependences. Correct program execution is ensured by the memory conflict buffer and repair code provided by the compiler. With this addition, significant speedup over an aggressive code scheduling model can be achieved for both non-numerical and numerical programs.
LCM
Authors: Larus James R. , Richards Brad , Viswanathan Guhan
Published: November 2005

Higher-level parallel programming languages can be difficult to implement efficiently on parallel machines. This paper shows how a flexible, compiler-controlled memory system can help achieve good performance for language constructs that previously appeared too costly to be practical.

Our compiler-controlled memory system is called Loosely Coherent Memory (LCM). It is an example of a larger class of Reconcilable Shared Memory (RSM) systems, which generalize the replication and merge policies of cache-coherent shared-memory. RSM protocols differ in the action taken by a processor in response to a
request
for a location and the way in which a processor
reconciles
multiple outstanding copies of a location. LCM memory becomes temporarily inconsistent to implement the semantics of C** parallel functions efficiently. RSM provides a compiler with control over memory-system policies, which it can use to implement a language's semantics, improve performance, or detect errors. We illustrate the first two points with LCM and our compiler for the data-parallel language C**.
Improving the accuracy of static branch prediction using branch correlation
Authors: Young Cliff , Smith Michael D.
Published: November 2005

Recent work in history-based branch prediction uses novel hardware structures to capture branch correlation and increase branch prediction accuracy. We present a profile-based code transformation that exploits branch correlation to improve the accuracy of static branch prediction schemes. Our general method encodes branch history information in the program counter through the duplication and placement of program basic blocks. For correlation histories of eight branches, our experimental results achieve up to a 14.7% improvement in prediction accuracy over conventional profile-based prediction without any increase in the dynamic instruction count of our benchmark applications. In the majority of these applications, code duplication increases code size by less than 30%. For the few applications with code segments that exhibit exponential branching paths and no branch correlation, simple compile-time heuristics can eliminate these branches as code-transformation candidates.
Fine-grain access control for distributed shared memory
Authors: Schoinas Ioannis , Falsafi Babak , Lebeck Alvin R. , Reinhardt Steven K. , Larus James R. , Wood David A.
Published: November 2005

This paper discusses implementations of fine-grain memory access control, which selectively restricts reads and writes to cache-block-sized memory regions. Fine-grain access control forms the basis of efficient cache-coherent shared memory. This paper focuses on low-cost implementations that require little or no additional hardware. These techniques permit efficient implementation of shared memory on a wide range of parallel systems, thereby providing shared-memory codes with a portability previously limited to message passing.

This paper categorizes techniques based on where access control is enforced and where access conflicts are handled. We incorporated three techniques that require no additional hardware into Blizzard, a system that supports distributed shared memory on the CM-5. The first adds a software lookup before each shared-memory reference by modifying the program's executable. The second uses the memory's error correcting code (ECC) as cache-block valid bits. The third is a hybrid. The software technique ranged from slightly faster to two times slower than the ECC approach. Blizzard's performance is roughly comparable to a hardware shared-memory machine. These results argue that clusters of workstations or personal computers with networks comparable to the CM-5's will be able to support the same shared-memory interfaces as supercomputers.