bluuebunny/crossref_metadata_2025 huggingface dataset:
Superoptimizer: a look at the smallest program
Authors: Massalin Henry
Published: October 2004

Given an instruction set, the superoptimizer finds the shortest program to compute a function. Startling programs have been generated, many of them engaging in convoluted bit-fiddling bearing little resemblance to the source programs which defined the functions. The key idea in the superoptimizer is a probabilistic test that makes exhaustive searches practical for programs of useful size. The search space is defined by the processor's instruction set, which may include the whole set, but it is typically restricted to a subset. By constraining the instructions and observing the effect on the output program, one can gain insight into the design of instruction sets. In addition, superoptimized programs may be used by peephole optimizers to improve the quality of generated code, or by assembly language programmers to improve manually written code.
Performance and architectural evaluation of the PSI machine
Authors: Taki Kazuo , Nakajima Katzuto , Nakashima Hiroshi , Ikeda Morihiro
Published: October 2004

We evaluated a Prolog machine PSI (Personal Sequential Inference machine) for the purpose of improving and redesigning it. In this evaluation, we measured the execution speed and the dynamic characteristics of cache memory, register file, and branching hardware introduced for high-speed execution of Prolog programs.Execution speed of the PSI firmware interpreter was found to be comparable to that of the DEC-10 Prolog compiled code on the DEC-2060. It was also found that PSI was faster than DEC for executing programs containing much unification and backtracking that require runtime processing.With the cache memory, the hit ratio for application programs was found higher than 96%; this demonstrates that the Prolog execution has much memory access locality. The memory access frequency and the appearance ratio between Read and Write command were also investigated.Concerning the register file, use rate of each dedicated access mode was measured and effect of each mode was discussed. In the branching function we confirmed a high appearance rate of conditional branches and multi-way branches based on tag values.
Firefly: a multiprocessor workstation
Authors: Thacker Charles P. , Stewart Lawrence C.
Published: October 2004

Firefly is a shared-memory multiprocessor workstation that contains from one to seven MicroVAX 78032 processors, each with a floating point unit and a sixteen kilobyte cache. The caches are coherent, so that all processors see a consistent view of main memory. A system may contain from four to sixteen megabytes of storage. Input-output is done via a standard DEC QBus. Input-output devices are an Ethernet controller, fixed disks, and a monochrome 1024 x 768 display with keyboard and mouse. Optional hardware includes a high resolution color display and a controller for high capacity disks. Figure 1 is a system block diagram.The Firefly runs a software system that emulates the Ultrix system call interface. It also supports medium- and coarse-grained multiprocessing through multiple threads of control in a single address space. Communications are implemented uniformly through the use of remote procedure calls.This paper describes the goals, architecture, implementation and performance analysis of the Firefly. It then presents some measurements of hardware performance, and discusses the degree to which SRC has been successful in producing software to take advantage of multiprocessing.
A VLIW architecture for a trace scheduling compiler
Authors: Colwell Robert P. , Nix Robert P. , O'Donnell John J. , Papworth David B. , Rodman Paul K.
Published: October 2004

Very Long Instruction Word (VLIW) architectures were promised to deliver far more than the factor of two or three that current architectures achieve from overlapped execution. Using a new type of compiler which compacts ordinary sequential code into long instruction words, a VLIW machine was expected to provide from ten to thirty times the performance of a more conventional machine built of the same implementation technology.Multiflow Computer, Inc., has now built a VLIW called the TRACE
TM
along with its companion Trace Scheduling
TM
compacting compiler. This new machine has fulfilled the performance promises that were made. Using many fast functional units in parallel, this machine extends some of the basic Reduced-Instruction-Set precepts: the architecture is load/store, the microarchitecture is exposed to the compiler, there is no microcode, and there is almost no hardware devoted to synchronization, arbitration, or interlocking of any kind (the compiler has sole responsibility for runtime resource usage).This paper discusses the design of this machine and presents some initial performance results.
Parallel computers for graphics applications
Authors: Levinthal Adam , Hanrahan Pat , Paquette Mike , Lawson Jim
Published: October 2004

Specialized computer architectures can provide better price/performance for executing image processing and graphics applications than general purpose designs. Two processors are presented that use parallel SIMD data paths to support common graphics data structures as primitive operands in arithmetic expressions. A variant of the C language has been implemented to allow high level language coding of user applications on these processors. High level programming support is designed into the processor architecture that implements parallel object data typing and parallel conditional evaluation in hardware.
A practical approach to developing real-time Ada programs for embedded systems
Authors: Collingbourne L. R.
Published: October 2004

An important aspect of the development of real-time Ada programs is the interaction of the program with the real-target architecture. Many development systems run out of support once the object code has been generated. Developers are often left to find their own way when it comes to getting programs to work on the real-time embedded system. This paper describes a practical approach to developing real-time systems based on online support for building, loading and debugging Ada programs on real targets. The author has been involved in the development of a toolset which enables developers to load programs into the non-homogeneous target memories, and then run them at full speed under interactive control. Breakpoints, monitoring, profiling, and the display and modification of variables may all be achieved using symbolic references. The present toolset design has been extended to a full multiprocessor implementation which is currently under development.
Limitations of Ada for real-time scheduling
Authors: Cornhilll Dennis , Sha Lui , Lehoczky John P.
Published: October 2004

The goal in real-time scheduling is to satisfy the timing requirements of application jobs which often have hard deadlines. There are two aspects to Ada's scheduling policies which are detrimental to achieving this goal. First, Ada's constraints on the language's implementation limit the definition of priority and the task scheduling algorithm to preclude the use of the best algorithms for scheduling jobs with hard deadlines. Second, information about task priority is not used when selecting a task from an entry queue or when choosing among branches of a selective wait statement. Instead, FIFO and arbitrary disciplines are used, respectively, which can unnecessarily lead to missed deadlines, even for very low levels of processor utilization. We suggest some areas for change to make the language more suitable for building real-time systems.
A new paradigm for the design of concurrent systems
Authors: Back Ralph , Kurki-Suonio Reino
Published: October 2004

A concurrent system is usually understood as a collection of
processes
that interact through some
communication mechanisms
. The active components of such a system are the processes; their interaction is described in terms of messages and operations on shared memory. The principal process communication mechanism of Ada, the
rendezvous
, is a high-level mechanism based on synchronizing messages.In this position paper we argue that appropriate design methods and languages for real-time systems should be based on a notion of interaction that is compatible with the corresponding concepts in the implementation language but provides a higher level of abstraction. It is claimed that existing methods do not satisfy this requirement with respect to Ada. A new paradigm is therefore suggested that reverses the traditional setting as follows. The active components of the system are not the processes but the
interactions
in which they participate. Such interactions, called
joint actions
, can be executed whenever they are
enabled
, i.e. when the required processes are free and willing to participate in these actions.This change of viewpoint has an effect on the kind of entities that are described and refined in the design process. In particular, refinement of joint actions changes the
granularity
of the system. i.e. the
atomicity
of events being considered. Another novelty introduced by joint actions is the application of the
production language
paradigm to the design of concurrent systems. As joint actions are a generalization of the rendezvous, Ada is a suitable implementation language for this approach.
Multilanguage programming on the JVM
Authors: Gasperoni Franco , Dismukes Gary
Published: October 2004

The latest trend in our industry, "pervasive computing", predicts the proliferation of numerous, often invisible, computing devices embedded in consumer appliances connected to the ubiquitous Internet. Secure, reliable applications combined with simplicity of use will make or break a company's reputation in this market.The Java "write once, run anywhere" paradigm, introduced by Sun in the mid-90s, is embodied in a widely available computing platform targeting pervasive devices. Although the Java Virtual Machine was designed to support the semantics of the Java programming language, it can also be used as a target for other languages.The Ada 95 programming language is a good match for the Java platform from the standpoint of its portability, security, reliability, and rich feature set. In this article we explain the features that have made Ada the language of choice for software-critical applications and how these features complement the Java programming language while increasing the overall reliability and flexibility of the Java platform.
Safety critical systems based on formal models
Authors: Asplund Lars , Lundqvist Kristina
Published: October 2004

The Ravenscar profile for high integrity systems using Ada 95 is well defined in all real-time aspects. The complexity of the run-time system has been reduced to allow full utilization of formal methods for applications using the Ravenscar profile. In the Mana project a tool set is being developed including a formal model of a Ravenscar compliant run-time system, a gnat compatible run-time system, and an ASIS based tool to allow for the verification of a system including both COTS and code that is reused.
Industrial experience with SPARK
Authors: Chapman Roderick
Published: October 2004

This paper considers a number of large, real-world projects that are using SPARK---an annotated sublauguage of Ada that is appropriate for the development of high-integrity systems. Three projects are considered in some detail where SPARK has made a contribution to meeting the most stringent software engineering standards. The projects are the Ship/Helicopter Operational Limits Instrumentation System (UK Interim Defence Standard 00-55), the MULTOS CA (a high-security system developed to the standards of ITSEC level E6), and the Lockheed C130J Mission Computer (DO-178B Level A). A less successful project is also described. The lessons learnt from these projects show that SPARK offers a cost-effective approach for the construction of high-integrity software when it is deployed judiciously within an appropriate software development process.
Principles of distributed computing
Authors: Rajsbaum Sergio
Published: October 2004

The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, operating systems, verification, internet, and the web.This is the first Distributed Computing Column that I have edited. It consists of four sections: A few thoughts on the role of distributed computing theory, a reprint of the PODC 2000 Influential-Paper Award to statement, a review of the PODC 2000 Conference, and a summary of a paper on robotics presented at the conference. The column concludes with some news and acknowledgments.
Review of Computational Geometry: Algorithms and Applications (2nd ed.) by Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf
Authors: Masum Hassan
Published: October 2004

Computational Geometry
is a wide-ranging introductory text which exposes readers to the main themes in modern computational geometry. Each chapter introduces a subfield of computational geometry, via natural problems and basic algorithms; exercises and notes help to flesh out the chapter material. This second edition of the book is obviously the product of much effort by the authors, and although some improvements are possible, on the whole this book is worth considering both as a text for a first computational geometry course and as a refresher on basic concepts.Features of interest include:
Beginning each chapter with a motivating real-world example,
to naturally introduce the algorithms. The solution of this example leads to the key algorithmic idea of the chapter.
Emphasis on derivation of algorithms,
as opposed to a cookbook-style presentation. The authors often spend a large amount of time to work through several suboptimal solutions for a problem before presenting the final one. While not suitable for the already-knowledgeable practitioner, this gives the far-larger category of students or other less-than-expert readers training in the process of generating new algorithms.
Good layout,
with wide margins containing intuition-generating diagrams. The Notes and Comments section at the end of each chapter also provides useful orientation to further algorithms and context in each subfield.
Wide coverage of algorithms.
As the authors say: "In general we have chosen the solution that is most easy to understand and implement. This is not necessarily the most efficient solution. We also took care that the book contains a good mixture of techniques like divide-and-conquer, plane sweep, and randomized algorithms. We decided not to treat all sorts of variations to the problems; we felt it is more important to introduce all main topics in computational geometry than to give more detailed information about a smaller number of topics."
A real bottom-up operating systems course
Authors: Bovet Daniel P. , Cesati Marco
Published: October 2004

The "Operating Systems" course is included in the Computer Science undergraduate program of almost all universities. It is quite surprising, however, that teachers rarely agree on what should be taught in such courses. Actually, there even isn't a widely agreed definition of what an operating system is.One of the broadest definitions we ever seen has been given in [2]:
The operating system is the collection of functions which make available computing services to people who require them.
Therefore, the operating system must fill the gap between the computer and the services required by the people using it. However, what kind of services should we consider? Isn't writing a document with a word processor a computing service that people require? And what about playing a strategy game, or browsing the Web?Much more restricted definitions of operating system have been given. For example, in [6] we read:
The purpose of an operating system is to provide an environment in which a user can execute programs. The primary goal of an operating system is thus to make the computer system convenient to use. A secondary goal is to use the computer hardware in an efficient manner.
Most Operating Systems courses implicitly adopt this definition or a similar one, because it allows teachers to stick to a well-defined set of canonical topics. Actually, two kinds of operating systems courses may co-exist: one addressed to system administrators and one to system programmers. In the first case, the course should teach how to make use of the many existing features inside an OS, how to tune it up properly, and how to set up proper environments for the users. In the second case, the course should explain how the functions are implemented and which are the main issues and trade-offs to be considered while implementing them.In fact, the first kind of course is seldom included in an undergraduate Computer Science program: this is likely due to the fact that operating systems are quite different from each other, thus the experience gathered on one of them, say Sun Microsystem's Solaris, cannot be readily transfered to another one, say IBM's OS/390. We thus concentrate in the rest of this paper on the second type of course, the standard elective fourth year course of an Undergraduate program in Computer Science.
A proxy-based personal web archiving service
Authors: Rao Herman Chung-Hwa , Chen Yih-Farn , Chen Ming-Feng
Published: October 2004

The Web contains so much information that it is almost beyond measure. How do users manage the useful information that they have seen while screening out the rest that doesn't interest them? Bookmarks help, but bookmarking a page doesn't guarantee that it will be available forever. Search engines are becoming more powerful, but they can't be customized based on the access history of individual users. This paper suggests that a better alternative to managing web information is through a middleware approach based on iPROXY, a programmable proxy server. iPROXY offers a suite of archiving, retrieval, and searching services. It can extend a URL to include commands that archive and retrieve pages. Its modular architecture allows users to plug in new features without having to change existing browsers or servers. Once installed on a network, iPROXY can be accessed by users using different browsers and devices. Internet service providers who offer customers iPROXY will be free to develop new services without having to wait for the dominant browsers to be updated.
Middleware for dependable network services in partitionable distributed systems
Authors: Montresor Alberto , Davoli Renzo , Babaoğlu Özalp
Published: October 2004

We describe the design and implementation of
Jgroup:
a middleware system that integrates group technology with distributed objects and is based on Java RMI. Jgroup supports a programming paradigm called
object groups
and enables development of dependable network services based on replication. Among the novel features of Jgroup is a uniform object-oriented interface for programming both services and their clients. The fact that Jgroup exposes network effects, including partitions, to applications makes it particularly suitable for developing highly-available services in partitionable distributed systems.
Status and future of the Ravenscar profile session summary
Authors: Wellings Andy
Published: October 2004

The session was chaired by Alan Burns who indicated that there had been several position papers received addressing various aspects of the Ravenscar Profile (RP). Based on the material presented in these papers, he suggested that the session consider the following topics:• Implementation and Application Experiences• Completing the Definition• Extending the ModelThe goal of the first topic was mainly to receive general feedback from the implementation teams and application programmers. These had resulted in several issues being raised. The RP only addresses issues relating to tasking; it is silent on all other aspects of the Ada language. However, some had felt that for a Ravenscar implementation to be effective, there were other restrictions that were necessary. These issues are reported under the second topic. Finally, there are many tasking profiles that could be defined. However, there had been no position papers making proposals for new subsets. Instead, papers had identified extensions to the RP that would give more expressive power but at little extra cost. These were discussed under the third topic. Issues to do with extending the RP for Distributed Systems were not considered in this session.
Issues with using Ravenscar and the Ada distributed systems annex for high-integrity systems
Authors: Audsley Neil , Wellings Andy
Published: October 2004

The Distributed Systems Annex (DSA) was designed for general-purpose distributed systems programming. This paper explores the practical use of the DSA in terms of high-integrity real-time distributed systems. In particular, it defines a high-integrity subset of the DSA and considers how such a subset can be implemented using SPARK and Ravenscar.
Implementing a high-integrity executive using Ravenscar
Authors: Audsley Neil , Burns Alan , Wellings Andy
Published: October 2004

This paper discusses the use of the Ravenscar profile in the implementation of an APEX-compliant high-integrity executive. In general, the Ravenscar profile was found to have enough expressive power to implement a large proportion of the executive. However, the lack of dynamic priorities and single item queues were problematic.
On developing and verifying design abstractions for reliable concurrent programming in Ada
Authors: Burns A. , Wellings A. J. , Koelmans A. M. , Koutny M. , Romanovsky A. , Yakovlev A.
Published: October 2004

Ada 95 is an expressive concurrent programming language, which allows building large multi-tasking applications. Much of the complexity of these applications stems from the interactions between the tasks. Design abstractions (such as atomic actions, conversations etc.) have been proposed to deal with such complexity. This paper argues that Petri nets offer a promising, tool-supported, technique for checking the logical correctness of abstractions. The paper illustrates the effectiveness of this approach by showing the correctness of an Ada implementation of the atomic action protocol using a variety of Petri net tools.
Position paper
Authors: Michell Stephen
Published: October 2004

There are some interactions between the Ravenscar Tasking Profile and sequential Ada language constructs which can cause undesirable behaviour for high integrity systems. We examine some of the interactions and discuss potential changes to the definition of the Ravenscar profile to correct the deficiencies found.
Programming atomic multicast in CAN
Authors: Pinho Luís Miguel , Vasques Francisco , Ferreira Luis
Published: October 2004

In Distributed Computer-Controlled Systems (DCCS), a special emphasis must be given to the communication infrastructure, which must provide timely and reliable communication services. CAN networks are usually suitable to support small-scale DCCS. However, they are known to present some reliability problems, which can lead to an unreliable behaviour of the supported applications.In this paper, an atomic multicast protocol for CAN networks is proposed. This protocol explores the CAN synchronous properties, providing a timely and reliable service to the supported applications.The implementation of such protocol in Ada, on top of the Ada version of Real-Time Linux is presented, which is used to demonstrate the advantages and disadvantages of the platform to support reliable communications in DCCS.
The design and implementation of the open Ravenscar kernel
Authors: de la Puente Juan A. , Zamorano Juan , Ruiz José , Fernández Ramón , García Rodrigo
Published: October 2004

This paper describes the design and implementation of Open Ravenscar Kernel (ORK), an open-source real-time kernel of reduced size and complexity, for which users can seek certification for mission-critical space applications. The kernel supports Ada 95 tasking on an ERC32 (SPARC v7) architecture in an efficient and compact way. It is closely integrated with the GNAT runtime library and other tools.
A semantics for dynamic ceiling priorities in Ada
Authors: Real Jorge , Llamosí Albert , Crespo Alfons
Published: October 2004

Several arguments have been given to justify the exclusion of dynamic ceiling priorities for protected objects in Ada. These arguments center on semantic complexity, the risks that can be derived from an erroneous usage of dynamic ceilings, and efficiency. But dynamic ceilings are very convenient for multi-moded systems and to dynamically adapting existing program libraries containing protected objects to new applications. This paper proposes a semantics for dynamic ceilings that does not add complexity to the language semantics or inefficiency to the run time system.
Scale and performance in a distributed file system
Authors: Howard J. , Kazar M. , Menees S. , Nichols D. , Satyanarayanan M. , Sidebotham Robert N. , West M.
Published: October 2004

Andrew is a distributed computing environment being developed in a joint project by Carnegie Mellon University and IBM. One of the major components of Andrew is a distributed file system which constitutes underlying mechanism for sharing information. The goals of the Andrew file system are to support growth up to at least 7000 workstations (one for each student, faculty member, and staff at Carnegie Mellon) while providing users, application programs, and system administrators with the amenities of a shared file system.

A fundamental result of our concern with scale is the design decision to transfer whole files between servers and workstations rather than some smaller unit such as records or blocks, as almost all other distributed file systems do. This paper examines the consequences of this and other design decisions and features that bear on the scalability of Andrew.

Large scale affects a distributed system in two ways: it degrades performance and it complicates administration and day-to-day operation. This paper addresses both concerns and shows that the mechanisms we have incorporated cope with them successfully. We start the initial prototype of the system, what we learned from it, and how we changed the system to improve performance. We compare its performance with that of a block-oriented file system, Sun Microsystems' NFS, in order to evaluate the whole file transfer strategy. We then turn to operability, and finish with issues related peripherally to scale and with the ways the present design could be enchanced.
Using idle workstations in a shared computing environment
Authors: Nichols D.
Published: October 2004

The Butler system is a set of programs running on Andrew workstations at CMU that give users access to idle workstations. Current Andrew users use the system over 300 times per day. This paper describes the implementation of the Butler system and tells of our experience in using it. In addition, it describes an application of the system known as
gypsy servers
, which allow network server programs to be run on idle workstations instead of using dedicated server machines.
Hashed and hierarchical timing wheels: data structures for the efficient implementation of a timer facility
Authors: Varghese G. , Lauck T.
Published: October 2004

Conventional algorithms to implement an Operating System timer module take
Ο
(
n
) time to start or maintain a timer, where
n
is the number of outstanding timers: this is expensive for large
n
. This paper begins by exploring the relationship between timer algorithms, time flow mechanisms used in discrete event simulations, and sorting techniques. Next a timer algorithm for small timer intervals is presented that is similar to the timing wheel technique used in logic simulators. By using a circular buffer or timing wheel, it takes
Ο
(1) time to start, stop, and maintain timers within the range of the wheel.

Two extensions for larger values of the interval are described. In the first, the timer interval is hashed into a slot on the timing wheel. In the second, a hierarchy of timing wheels with different granularities is used to span a greater range of intervals. The performance of these two schemes and various implementation trade-offs are discussed.
The packer filter: an efficient mechanism for user-level network code
Authors: Mogul J. , Rashid R. , Accetta M.
Published: October 2004

Code to implement network protocols can be either inside the kernel of an operating system or in user-level processes. Kernel-resident code is hard to develop, debug, and maintain, but user-level implementations typically incur significant overhead and perform poorly.

The performance of user-level network code depends on the mechanism used to demultiplex received packets. Demultiplexing in a user-level process increases the rate of context switches and system calls, resulting in poor performance. Demultiplexing in the kernel eliminates unnecessary overhead.

This paper describes the
packet filter
, a kernel-resident, protocol-independent packet demultiplexer. Individual user processes have great flexibility in selecting which packets they will receive. Protocol implementations using the packet filter perform quite well, and have been in production use for several years.
A name service for evolving heterogeneous systems
Authors: Schwartz M. , Zahorjan J. , Notkin D.
Published: October 2004

A prototype implementation has been built as part of the Heterogeneous Computer Systems project at the University of Washington. This service supports RPC binding and other applications in our heterogeneous environment. Measurements of the performance of this prototype show that it is close to that of the underlying name services, due largely to the use of specialized caching techniques.
The duality of memory and communication in the implementation of a multiprocessor operating system
Authors: Young M. , Tevanian A. , Rashid R. , Golub D. , Eppinger J.
Published: October 2004

Mach is a multiprocessor operating system being implemented at Carnegie-Mellon University. An important component of the Mach design is the use of memory objects which can be managed either by the kernel or by user programs through a message interface. This feature allows applications such as transaction management systems to participate in decisions regarding secondary storage management and page replacement.

This paper explores the goals, design and implementation of Mach and its external memory management facility. The relationship between memory and communication in Mach is examined as it relates to overall performance, applicability of Mach to new multiprocessor architectures, and the structure of application programs.
Synchronization primitives for a multiprocessor: a formal specification
Authors: Birrell A. , Guttag J. , Horning J. , Levin R.
Published: October 2004

Formal specifications of operating system interfaces can be a useful part of their documentation. We illustrate this by documenting the Threads synchronization primitives of the Taos operating system. We start with an informal description, present a way to formally specify interfaces in concurrent systems, give a formal specification of the synchronization primitives, briefly discuss the implementation, and conclude with a discussion of what we have learned from using the specification for more than a year.
Exploiting virtual synchrony in distributed systems
Authors: Birman K. , Joseph T.
Published: October 2004

We describe applications of a
virtually synchronous
environment for distributed programming, which underlies a collection of distributed programming tools in the
ISIS
2
system. A virtually synchronous environment allows processes to be structured into
process groups
, and makes events like broadcasts to the group as an entity, group membership changes, and even migration of an activity from one place to another appear to occur instantaneously — in other words, synchronously. A major advantage to this approach is that many aspects of a distributed application can be treated independently without compromising correctness. Moreover, user code that is designed as if the system were synchronous can often be executed concurrently. We argue that this approach to building distributed and fault-tolerant software is more straightforward, more flexible, and more likely to yield correct solutions than alternative approaches.
A simple and efficient implementation of a small database
Authors: Birrell A. , Jones M. , Wobber E.
Published: October 2004

This paper describes a technique for implementing the sort of small databases that frequently occur in the design of operating systems and distributed systems. We take advantage of the existence of very large virtual memories, and quite large real memories, to make the technique feasible. We maintain the database as a strongly typed data structure in virtual memory, record updates incrementally on disk in a log and occasionally make a checkpoint of the entire database. We recover from crashes by restoring the database from an old checkpoint then replaying the log. We use existing packages to convert between strongly typed data objects and their disk representations, and to communicate strongly typed data across the network (using remote procedure calls). Our memory is managed entirely by a general purpose allocator and garbage collector. This scheme has been used to implement a name server for a distributed system. The resulting implementation has the desirable property of being simultaneously simple, efficient and reliable.
Reimplementing the Cedar file system using logging and group commit
Authors: Hagmann R.
Published: October 2004

The workstation file system for the Cedar programming environment was modified to improve its robustness and performance. Previously, the file system used hardware-provided labels on disk blocks to increase robustness against hardware and software errors. The new system does not require hardware disk labels, yet is more robust than the old system. Recovery is rapid after a crash. The performance of operations on file system metadata, e.g., file creation or open, is greatly improved.

The new file system has two features that make it atypical. The system uses a log, as do most database systems, to recover metadata about the file system. To gain performance, it uses group commit, a concept derived from high performance database systems. The design of the system used a simple, yet detailed and accurate, analytical model to choose between several design alternatives in order to provide good disk performance.
Implementing TCP/IP on a cray computer
Authors: Borman David A.
Published: October 2004

Cray Research has been supplying TCP/IP networking code with its UNICOS operating system since February 1986. In the last three years, this code has been improved and optimized, yielding up to two orders of magnitude improvement in performance. This paper addresses some of the issues that were addressed to achieve these changes, and some of the other changes that have been made to fit the TCP/IP code into a Cray environment.
Computing the internet checksum
Authors: Braden R. , Borman D. , Partridge C.
Published: October 2004

This memo discusses methods for efficiently computing the Internet checksum that is used by the standard Internet protocols IP, UDP, and TCP.An efficient checksum implementation is critical to good performance. As advances in implementation techniques streamline the rest of the protocol processing, the checksum computation becomes one of the limiting factors on TCP performance, for example. It is usually approapriate to carefully hand-craft the checksum routine, exploiting every machine-dependent trick possible; a fraction of a microsecond per TCP data byte can add up to significant CPU time savings overall.
TCP checksum function design
Authors: Plummer William W.
Published: October 2004

Checksums are included in packets in order that errors encountered during transmission may be detected. For Internet protocols such as TCP [1,9] this is especially important because packets may have to cross wireless networks such as the Packet Radio Network [2] and Atlantic Satellite Network [3] where packets may be corrupted. Internet protocols (e.g., those for real time speech transmission) can tolerate a certain level of transmission errors and forward error correction techniques or possibly no checksum at all might be better. The focus in this paper is on checksum functions for protocols such as TCP where the required reliable delivery is achieved by retransmission.
Security defects in CCITT recommendation X.509
Authors: I'Anson Collin , Mitchell Chris
Published: October 2004

Security defects to be found in C.C.I.T.T. Recommendation X.509-1988 are described together with possible solutions.
The journal review column
Authors: Parberry Ian
Published: October 2004

The journal review column is established to provide readers of
SIGACT News
with up-to-date information on journals and journal-like publications which carry articles of potential interest to theoretical computer scientists. It will include research, survey, review and "popular" publications, theory journals and applied journals, general journals and specialized journals, with the common thread being that they are receptive to theoretical computer science. The term "theoretical computer science" will be interpreted broadly.It is the intent of the column to inform, not to rank or in any way pass judgement on the quality of journals or the articles published therein. Journals to be reviewed include, but are not necessarily restricted to the list appearing in the first column
(SIGACT News
, Vol. 12, No. 3, pp. 27--28, 1989). Suggestions from readers of the column are welcome.
Where is time spent in message-passing and shared-memory programs?
Authors: Chandra Satish , Larus James R. , Rogers Anne
Published: October 2004

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: October 2004

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++.
Hardware and software support for efficient exception handling
Authors: Thekkath Chandramohan A. , Levy Henry M.
Published: October 2004

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.
A technique for monitoring run-time dynamics of an operating system and a microprocessor executing user applications
Authors: Argade Pramod V. , Charles David K. , Taylor Craig
Published: October 2004

In this paper, we present a non-invasive and efficient technique for simulating applications complete with their operating system interaction. The technique involves booting and initiating an application on a hardware development system, capturing the entire state of the application and the microprocessor at a well defined point in execution and then simulating the application on microprocessor simulators. Extensive statistics generated from the simulators on run-time dynamics of the application, the operating system as well as the microprocessor enabled us to tune the operating system and the microprocessor architecture and implementation. The results also enabled us to optimize system level design choices by anticipating/predicting the performance of the target system. Lastly, the results were used to adjust and refocus the evolution of the architecture of both the operating system and the microprocessor.
Trap-driven simulation with Tapeworm II
Authors: Uhlig Richard , Nagle David , Mudge Trevor , Sechrest Stuart
Published: October 2004

Tapeworm II is a software-based simulation tool that evaluates the cache and TLB performance of multiple-task and operating system intensive workloads. Tapeworm resides in an OS kernel and causes a host machine's hardware to drive simulations with kernel traps instead of with address traces, as is conventionally done. This allows Tapeworm to quickly and accurately capture complete memory referencing behavior with a limited degradation in overall system performance. This paper compares trap-driven simulation, as implemented in Tapeworm, with the more common technique of trace-driven memory simulation with respect to speed, accuracy, portability and flexibility.
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: October 2004

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.
AP1000+
Authors: Hayashi Kenichi , Doi Tsunehisa , Horie Takeshi , Koyanagi Yoichi , Shiraki Osamu , Imamura Nobutaka , Shimizu Toshiyuki , Ishihata Hiroaki , Shindo Tatsuya
Published: October 2004

The scalability of distributed-memory parallel computers makes them attractive candidates for solving large-scale problems. New languages, such as HPF, FortranD, and VPP Fortran, have been developed to enable existing software to be easily ported to such machines. Many distributed-memory parallel computers have been built, but none of them support the mechanisms required by such languages. We studied the mechanisms required by parallelizing compilers and proposed a new architecture to support them. Based on this proposed architecture, we developed a new distributed-memory parallel computer, the AP1000+, which is an enhanced version of the AP1000. Using scientific applications in VPP Fortran and C, such as NAS parallel benchmarks, we simulated the performance of the AP1000+.
The performance advantages of integrating block data transfer in cache-coherent multiprocessors
Authors: Woo Steven Cameron , Singh Jaswinder Pal , Hennessy John L.
Published: October 2004

Integrating support for block data transfer has become an important emphasis in recent cache-coherent shared address space multiprocessors. This paper examines the potential performance benefits of adding this support. A set of ambitious hardware mechanisms is used to study performance gains in five important scientific computations that appear to be good candidates for using block transfer. Our conclusion is that the benefits of block transfer are not substantial for hardware cache-coherent multiprocessors. The main reasons for this are (i) the relatively modest fraction of time applications spend in communication amenable to block transfer, (ii) the difficulty of finding enough independent computation to overlap with the communication latency that remains after block transfer, and (iii) long cache lines often capture many of the benefits of block transfer in efficient cache-coherent machines. In the cases where block transfer improves performance, prefetching can often provide comparable, if not superior, performance benefits. We also examine the impact of varying important communication parameters and processor speed on the effectiveness of block transfer, and comment on useful features that a block transfer facility should support for real applications.
Improving the accuracy of static branch prediction using branch correlation
Authors: Young Cliff , Smith Michael D.
Published: October 2004

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.