Software experiments such as BLAST are hard to reproduce even if identical hardware is available because external data sets could have changed, software used in the original experiment may be unavailable, or the input parameters for the experiment may not be documented. This paper presents Rex, a toolset that allows one to record an experiment and archive its apparatus, replay an experiment, conduct new experiments on a recorded apparatus, and compare differences between experiments. The execution time overhead of recording experiments is on average about 2%; the space overhead of an archive ranges from 8 MB to 5 GB.

The key to performance improvements in the multi-core era is for software to utilize the available concurrency. This paper presents a lightweight programming framework called Gossamer that is easy to use, enables the solution of a broad range of parallel programming problems, and produces efficient code. Gossamer contains (1) a set of high-level annotations that one adds to a sequential program to specify concurrency and synchronization, (2) a source-to-source translator that produces an optimized program that uses our threading library, and (3) a run-time system that provides efficient threads and synchronization. Gossamer supports iterative and recursive parallelism, pipelined computations, domain decomposition, and MapReduce computations.

General-purpose operating systems, such as Linux, are increasingly being used in embedded systems. Computational resources are usually limited, and embedded processors often have a limited amount of memory. This makes code size especially important. This paper describes techniques for automatically reducing the memory footprint of general-purpose operating systems on embedded platforms. The problem is complicated by the fact that kernel code tends to be quite different from ordinary application code, including the presence of a significant amount of hand-written assembly code, multiple entry points, implicit control flow paths involving interrupt handlers, and frequent indirect control flow via function pointers. We use a novel "approximate decompilation" technique to apply source-level program analysis to hand-written assembly code. A prototype implementation of our ideas on an Intel x86 platform, applied to a Linux kernel that has been configured to exclude unnecessary code, obtains a code size reduction of close to 24%

There is increasing interest in using general-purpose operating systems, such as Linux, on embedded platforms. It is especially important in embedded systems to use memory efficiently because embedded processors often have limited physical memory. This paper describes an automatic technique for reducing the memory footprint of general-purpose operating systems on embedded platforms by keeping infrequently executed code on secondary storage and loading such code only if it is needed at run time. Our technique is based on an old idea - memory overlays - and it does not require hardware or operating system support for virtual memory. A prototype of the technique has been implemented for the Linux kernel. We evaluate our approach with two benchmark suites: MiBench and MediaBench, and a Web server application. The experimental results show that our approach reduces memory requirements for the Linux kernel code by about 53% with little degradation in performance.

EPIC (explicitly parallel instruction computing) architectures, exemplified by the Intel Itanium, support a number of advanced architectural features, such as explicit instruction-level parallelism, instruction predication, and speculative loads from memory. However, compiler optimizations that take advantage of these features can profoundly restructure the program's code, making it potentially difficult to reconstruct the original program logic from an optimized Itanium executable. This paper describes techniques to undo some of the effects of such optimizations and thereby improve the quality of reverse engineering such executables.

Modern architectures, such as the Intel Itanium, support speculation, a hardware mechanism that allows the early execution of expensive operations possibly even before it is known whether the results of the operation are needed. While such speculative execution can improve execution performance considerably, it requires a significant amount of complex support code to deal with and recover from speculation failures. This greatly complicates the tasks of understanding and re-engineering speculative code. This paper describes a technique for removing speculative instructions from optimized binary programs in a way that is guaranteed to preserve program semantics, thereby making the resulting "unspeculated" programs easier to understand and more amenable to reengineering using traditional reverse engineering techniques.

A coarse-grain parallel program typically has one thread (task) per processor, whereas a fine-grain program has one thread for each independent unit of work. Although there are several advantages to fine-grain parallelism, conventional wisdom is that coarse-grain parallelism is more efficient. This paper illustrates the advantages of fine-grain parallelism and presents an efficient implementation for shared-memory machines. The approach has been implemented in a portable software package called Filaments, which employs a unique combination of techniques to achieve efficiency. The performance of the fine-grain programs discussed in this paper is always within 13% of a hand-coded coarse-grain program and is usually within 5%. © 1998 John Wiley & Sons, Ltd.

Distributed shared memory (DSM) alleviates the need to program message passing explicitly on a distributed-memory machine. In order to reduce memory latency, a DSM replicates copies of data. This paper examines several current approaches to controlling thrashing caused by false sharing in a DSM. Then it introduces a novel memory consistency protocol, writer-owns, which detects and eliminates false sharing at run time. In iterative computations, where the data is accessed similarly every iteration, the writer-owns protocol can have tremendous benefits because the overhead of eliminating false sharing is only incurred once. Performance results show that the writer-owns protocol is competitive with and often better than existing approaches.

SR is a language for programming distributed systems ranging from operating systems to application programs. On the basis of our experience with the initial version, the language has evolved considerably. In this paper we describe the current version of SR and give an overview of its implementation. The main language constructs are still resources and operations. Resources encapsulate processes and variables that they share; operations provide the primary mechanism for process interaction. One way in which SR has changed is that both resources and processes are now created dynamically. Another change is that inheritance is supported. A third change is that the mechanisms for operation invocation—call and send—and operation implementation—proc and in—have been extended and integrated. Consequently, all of local and remote procedure call, rendezvous, dynamic process creation, asynchronous message passing, multicast, and semaphores are supported. We have found this flexibility to be very useful for distributed programming. Moreover, by basing SR on a small number of well-integrated concepts, the language has proved easy to learn and use, and it has a reasonably efficient implementation.

Abstract This paper describes two mechanisms – reproduction sets and metafiles – that provide low‐cost, semi‐automatic file replication and location transparency facilities for an interconnected collection of machines running Berkeley Unix. A reproduction set is a collection of files that the system attempts to keep identical; this is done on a ‘best effort’ basis, with the system relying on the user to handle unusual situations. A metafile is a special file that contains symbolic pathnames of other files, each of which may be on any machine in the network; opening a metafile results in opening an available constituent file. Examples are given to illustrate the use of these mechanisms. Their implementation and performance are also described.

This paper describes the design of the Saguaro operating system for computers connected by a local-area network. Systems constructed on such an architecture have the potential advantages of concurrency and robustness. In Saguaro, these advantages are made available to the user through several mechanisms. One is channels, an interprocess communication and synchronization facility that allows the input and output of different commands to be connected to form general graphs of communicating processes. Two additional mechanisms are provided to support semitransparent file replication and access: reproduction sets and metafiles. A reproduction set is a collection of files that the system attempts to keep identical on a "best effort" basis. A metafile is a special file that contains symbolic pathnames of other files; when a metafile is opened, the system selects an available constituent file and opens it instead. The advantages of concurrency and robustness are also realized at the system level by the use of pools of server processes and decentralized allocation protocols. Saguaro also makes extensive use of a type system to describe user data such as files and to specify the types of arguments to commands and procedures. This enables the system to assist in type checking and leads to a user interface in which command-specific templates are available to facilitate command invocation.

Distributed systems make possible both a high degree of concurrency and robustness in the face of failure. One approach to achieving these goals is to employ pools of servers implementing major system functions. This paper describes the concept of pools of servers, and presents logically distributed, robust algorithms for one problem arising in this approach: the allocation of servers to clients. Three types of allocation problems are identified: free servers, preferred servers, and retentive servers. Allocation protocols based upon the idea of hash addressing are described and analyzed.

This paper reexamines deadlock prevention in the context of multiprocessor or distributed systems. The essential idea is to have a deadlock prevention process that executes “on-the-fly”, i.e. in parallel with processes that use resources. The prevention process determines in advance those requests that could be satisfied. The effect of this approach is to reduce greatly the overhead imposed by deadlock prevention. The contributions of the paper are an efficient algorithm for predicting which requests could be granted and efficient process interaction protocols for on-the-fly prevention. The predictor algorithm is also used for efficient determination of delayed requests that can be granted after a release.

Abstract This paper presents a new approach to the treatment of arrays in Pascal and Pascal‐like languages. The proposed mechanisms allow arrays to be used flexibly in assignments and as parameters to procedures while at the same time preserving the benefits of strong type checking. Several examples to illustrate the mechanisms are presented. Their implementation is also described.

Abstract SR is a new language for programming software containing many processes that execute in parallel. The language allows an entire software system that controls a potentially large collection of processors to be programmed as an integrated set of software modules. The key language mechanisms are resources, operations and input statements. The language supports separate compilation, type abstraction, and dynamic communication links; it also contains novel treatments of arrays and procedures. This paper gives an overview of the language mechanisms, discusses some of the major design decisions and describes one implementation.

A new proposal for synchronization and communication in parallel programs is presented.The proposal synthesizes and extends aspects of procedures, coroutines, critical regions, messages, and monitors.It provides a single notation for parallel programming with or without shared variables and is suited for either shared or distributed memory architectures.The essential new concepts are operations, input statements, and resources.The proposal is illustrated by the solutions of a variety of parallel programming problems; its relation to other parallel programming proposals is also discussed.

A new approach to information flow in sequential and parallel programs is presented. Flow proof rules that capture the information flow semantics of a variety of statements are given and used to construct program flow proofs. The method is illustrated by examples. The applications of flow proofs to certifying information flow policies and to solving the confinement problem are considered. It is also shown that flow rules and correctness rules can be combined to form an even more powerful proof system.

Interesting program properties other than functional correctness can be addressed and proved using axiomatic logic. An information flow logic that defines the flow semantics of a parallel programming language is presented. Proofs in this logic can be used to certify programs with respect to information security policies. The flow logic can also be combined with correctness logics to form an even more powerful deductive system.

Modula is a new programming language for implementing dedicated, parallel systems. Following a systematic design technique, this paper illustrates the use of Modula for the design of a message switching communication system. A message switching system poses a number of interesting. problems: a high degree of concurrent activity exists, a variety of I/O devices need to be controlled, messages can have multiple destinations, and messages can be preempted. The strengths and weaknesses of Modula with respect to these specific problems and its utility as a general purpose language are evaluated.

An important component of a programming language for writing operating systems, or other large parallel systems, is the set of access control facilities. Two principles for access control, expressive power and access validation, are discussed. Then two new language mechanisms are presented: one for expressing the static structure and access rights of parallel systems, the other for controlling dynamic access to shared objects (monitors). The use of the proposed mechanisms is illustrated by examples including a file system. Finally, the relationships between the mechanisms, access validation, and the safety problem are discussed.

Abstract This paper describes a nucleus for controlling process interaction in multiprogramming systems. The nucleus has three components: a set of primitive operations and data structures for the management of processes and resources, a library of service routines for implementing a variety of resource management strategies and facilities for cleanly handling all input‐output and interrupts. The process management component is straightforward, but the resource facilities are novel in permitting the dynamic definition and control of classes of real or virtual resources. Resources are considered to be anything on which a process can be blocked and consequently encompass consumable (message‐like) as well as conventional, re‐usable objects. Applications of the nucleus as well as some implementation details are also presented.