bluuebunny/crossref_metadata_2025 huggingface dataset:
An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches
Authors: Kim Changkyu , Burger Doug , Keckler Stephen W.
Published: October 2004

Growing wire delays will force substantive changes in the designs of large caches. Traditional cache architectures assume that each level in the cache hierarchy has a single, uniform access time. Increases in on-chip communication delays will make the hit time of large on-chip caches a function of a line's physical location within the cache. Consequently, cache access times will become a continuum of latencies rather than a single discrete latency. This non-uniformity can be exploited to provide faster access to cache lines in the portions of the cache that reside closer to the processor. In this paper, we evaluate a series of cache designs that provides fast hits to multi-megabyte cache memories. We first propose physical designs for these Non-Uniform Cache Architectures (NUCAs). We extend these physical designs with logical policies that allow important data to migrate toward the processor within the same level of the cache. We show that, for multi-megabyte level-two caches, an adaptive, dynamic NUCA design achieves 1.5 times the IPC of a Uniform Cache Architecture of any size, outperforms the best static NUCA scheme by 11%, outperforms the best three-level hierarchy--while using less silicon area--by 13%, and comes within 13% of an ideal minimal hit latency solution.
Increasing web server throughput with network interface data caching
Authors: Kim Hyong-youb , Pai Vijay S. , Rixner Scott
Published: October 2004

This paper introduces network interface data caching, a new technique to reduce local interconnect traffic on networking servers by caching frequently-requested content on a programmable network interface. The operating system on the host CPU determines which data to store in the cache and for which packets it should use data from the cache. To facilitate data reuse across multiple packets and connections, the cache only stores application-level response content (such as HTTP data), with application-level and networking headers generated by the host CPU. Network interface data caching can reduce PCI traffic by up to 57% on a prototype implementation of a uniprocessor web server. This traffic reduction results in up to 31% performance improvement, leading to a peak server throughput of 1571 Mb/s.
A stream compiler for communication-exposed architectures
Authors: Gordon Michael I. , Thies William , Karczmarek Michal , Lin Jasper , Meli Ali S. , Lamb Andrew A. , Leger Chris , Wong Jeremy , Hoffmann Henry , Maze David , Amarasinghe Saman
Published: October 2004

With the increasing miniaturization of transistors, wire delays are becoming a dominant factor in microprocessor performance. To address this issue, a number of emerging architectures contain replicated processing units with software-exposed communication between one unit and another (e.g., Raw, SmartMemories, TRIPS). However, for their use to be widespread, it will be necessary to develop compiler technology that enables a portable, high-level language to execute efficiently across a range of wire-exposed architectures.In this paper, we describe our compiler for StreamIt: a high-level, architecture-independent language for streaming applications. We focus on our backend for the Raw processor. Though StreamIt exposes the parallelism and communication patterns of stream programs, some analysis is needed to adapt a stream program to a software-exposed processor. We describe a partitioning algorithm that employs fission and fusion transformations to adjust the granularity of a stream graph, a layout algorithm that maps a stream graph to a given network topology, and a scheduling strategy that generates a fine-grained static communication pattern for each computational element.We have implemented a fully functional compiler that parallelizes StreamIt applications for Raw, including several load-balancing transformations. Using the cycle-accurate Raw simulator, we demonstrate that the StreamIt compiler can automatically map a high-level stream abstraction to Raw without losing performance. We consider this work to be a first step towards a portable programming model for communication-exposed architectures.
Mondrian memory protection
Authors: Witchel Emmett , Cates Josh , Asanović Krste
Published: October 2004

Mondrian memory protection (MMP) is a fine-grained protection scheme that allows multiple protection domains to flexibly share memory and export protected services. In contrast to earlier page-based systems, MMP allows arbitrary permissions control at the granularity of individual words. We use a compressed permissions table to reduce space overheads and employ two levels of permissions caching to reduce run-time overheads. The protection tables in our implementation add less than 9% overhead to the memory space used by the application. Accessing the protection tables adds than 8% additional memory references to the accesses made by the application. Although it can be layered on top of demand-paged virtual memory, MMP is also well-suited to embedded systems with a single physical address space. We extend MMP to support segment translation which allows a memory segment to appear at another location in the address space. We use this translation to implement zero-copy networking underneath the standard read system call interface, where packet payload fragments are connected together by the translation system to avoid data copying. This saves 52% of the memory references used by a traditional copying network stack.
A polynomial-time algorithm for solving NP-hard problems in practice
Authors: Huang Xiaofei
Published: October 2004

Constraint-based optimization, which is NP-hard, describes a large class of problems in many fields, especially in formulating early perception tasks. For example, Shape from shading of a polyhedron [12, 11] in computer vision can be formulated under such a paradigm. Some of the traditional problem-solving methods, like the exhaustive search, guarantee finding the global solution, but are too expensive in practice. Local Search, Simulated Annealing, Tabu Search, and the evolutionary algorithms have no general conditions to stop searching when the global optimum is what we are looking for. In this paper, we will present a polynomial-time algorithm [5 ]for solving the practical problems. The algorithm has many interesting computational properties not possessed by the classic ones. It is guaranteed to converge linearly, insensitive to the perturbations to its initial conditions and intermediate solutions. The closeness of the solutions to the optimal ones in cost is always provided by the algorithm so that we can stop search when the gap is closed or is small enough. It has a number of sufficient conditions for identifying optimal solutions, and a number of necessary conditions for reducing the search spaces. With 1,000 test problems randomly generated by computer, the Local Search algorithm with multiple restarts has a successful rate of only 0.2% after 25 iterations, and the Simulated Annealing algorithm [7, 2 ] with a linear cooling scheme has a successful rate of 1.5% after 250,000 steps. In contrast, the new algorithm achieved a successful rate of over 98% after only 7.27 iterations on average.
A methodology for protocol design and specification based on an extended state transition model
Authors: Chung Richard
Published: October 2004

A lot of effort is being dedicated world-wide to defining Open Systems Interconnection (OSI) protocol standards and tools for formally describing them. However, little work is done in developing methods for applying these tools to the development of new protocols.

This paper presents such a methodology based on OSI and software engineering principles. It provides general guidelines for designing protocols based on an extended state transition formal description technique (FDT). It emphasizes a systematic, analytical and algorithmic approach to achieve completeness of protocol specification during the protocol design process. Its possible application to the development of OSI protocol standards is discussed and suggested for study by the standards community.
Datagram routing for internet multicasting
Authors: Aguilar Lorenzo
Published: October 2004

We present a solution to the problem of multidestination routing in internetworks. The component subnets of these internets share a common datagram internet layer, and the gateways and hosts can determine the next gateway en route to a foreign net. Our datagram routing offers high resilience to network failures, major reductions in network traffic, and no changes whatsoever to the subnetwork routing. The routing follows “shortest” paths as defined by the distance criteria of an internet. We intend to use the algorithm as an option of the DoD Internet Protocol with only minor changes to IP while preserving interoperability with IP modules not supporting multidestination.
Interactive verification of communication software on the basis of CIL
Authors: Krumm H. , Drobnik O.
Published: October 2004

The CIL-approach for the development of communication services is based on the programming language CIL (Communication Service Implementation Language) and a CIL-compatible theory of program execution. The theory contains a first-order predicate calculus and an event-oriented model of program execution. The verification of programs written in CIL is supported by the automated generation of program axioms and by an interactive theorem prover tailored to the predicate calculus. Interactive verification during the design phase leads to early detection and localization of design errors and helps to reduce the efforts for debugging and testing. The paper describes the principles of the language, the theory, and the interactive verification tool. The design of a program realizing a transport service exemplifies the CIL-approach.
Interfacing to the 10Mbps ethernet
TM
Authors: Nabielsky Jose
Published: October 2004

This paper documents our efforts to connect our network front-ends to the 10 Mbps Ethernet,
TM
and presents some quantitative and qualitative results that may prove useful to those who, like us, are implementing a distributed-function architecture built upon a high-speed local area network.
The derivation of performance expressions for communication protocols from timed petri net models
Authors: Razouk Rami R.
Published: October 2004

Petri Net models have been extended in a variety of ways and have been used to prove the correctness and evaluate the performance of communication protocols. Several extensions have been proposed to model time. This work uses a form of Timed Petri Nets and presents a technique for symbolically deriving expressions, which describe system performance. Unlike past work on performance evaluation of Petri Nets which assumes a priori knowledge of specific time delays, the technique presented here applies to a wide range of time delays so long as the delays satisfy a set of timing constraints. The technique is demonstrated using a simple communication protocol.
Analytic solution of an integrated performance model of a computer communication network with window flow control
Authors: Thomasian Alexander , Bay Paul
Published: October 2004

A method for analyzing the performance of computer communication networks using queueing network models (QNM's) is presented in this paper. The user/computer sites are interconnected by a wide-area network with an end-to-end window flow-control mechanism. The QNM for the system including the communication subnet and the host computers is intractable because of blocking due to window flow control and memory constraints at computer systems, even under otherwise analytically favorable assumptions. The approximate solution method, which is based on iteration and decomposition, combines several recently developed computationally inexpensive algorithms to compute user response times, taking into account the delay in the communication network and the processing time at computer systems. We also introduce a fast non-iterative procedure to analyze QNM's with external arrivals and with population size constraints, such that blocked customers are queued. The effect of the choice of window sizes and minimum link/bifurcated routing on system performance is investigated.
A class of tree algorithms with variable message length
Authors: Gerakoulis D. P. , Saadawi T. N. , Schilling D. L.
Published: October 2004

In this paper we present and analyze a class of tree algorithms with variable message length. First we analyze the algorithm according to which a message, consisting of a number of packets, is transmitted continuously after the successful transmission of its first packet, referred to as the tree algorithm with variable message length. The analysis of the algorithm is presented for the two cases of small number of users and of large number of users. In both cases the analysis shows a considerable improvement for the maximum throughput, which gets larger as the average message length increases. Second, we present the reservation tree algorithm, R-Tree, which uses &test& packets instead of the message's first packet to resolve the collision among users. The R-Tree maximum throughput approaches one as the average message length increases, which for single packet messages can be a maximum throughput of 0.776 for infinite number of users.
Protocol testing methdology development at NBS
Authors: Blanc Robert P.
Published: October 2004

The National Bureau of Standards has three primary goals in computer networking.

1. To develop networking and protocol standards which meet U.S. Government and industry requirements and will be implemented in off-the-shelf, commercial products.

2. To develop testing methodologies to support the development and implementation of computer network protocols; and

3. To assist Government and industry users in the application of advanced networking technologies, and computer and communication manufacturers, in the implementation of standard protocols.

To support these objectives, NBS has laboratory activities where prototypes of draft protocol standards are implemented and tested in a variety of communications environments (e.g. global networks, local networks, office systems networks), supporting different applications (e.g. file transfer, message processing), on difference kinds and sizes of computers. The primary purposes are to advance the state of the art in measurement methodologies for advanced computer networking technologies, and to determine protocol implementation correctness and performance.

NBS views testing as a cooperative research effort and works with other agencies, private sector companies and other countries in the development of methodologies. At this time, this cooperation involves five network laboratories in other countries and over 20 computer manufacturers.

The test methodologies developed at NBS are well documented and the testing tools themselves are developed with an objective of portability and made available to many organizations engaged in protocol development and implementations.

Consistent with goals, NBS standards developments, research in testing methodologies, and technical assistance are characterized by direct industry/government cooperation and mutual support.
Physically dispersing an operating system
Authors: Jensen E. Douglas
Published: October 2004

Computer systems can be &distributed& in many different senses - for example: the user access (such as remote terminals); the system geography (such as a computer network); the processing (such as a multiprocessor or a multicomputer); the data (such as a partitioned or a replicated database); the operating system (such as a network OS or a decentralized OS). These senses of distribution are not independent, and each has its own advantages and disadvantages in various circumstances, as well as its own research problems. However, some senses are becoming better understood than others, and some are becoming recognized as more fundamentally important than others. Distributing the user access or the system geography per se can be regarded as neither especially challenging nor critically fundamental technology. Distributing the (user portion of the) processing is important, and the ease of doing so is, to a first order approximation, determined by the extent and manner in which the data and operating system are distributed. It currently seems to be these latter two aspects of computing whose distribution involves the most essential, and difficult, new technology.
Multiprocessors and computer networks
Authors: Solomon Marvin
Published: October 2004

In this brief note, I would like to review the histories of computer networking and multiprocessor architecture and suggest ways in which these two streams of research are flowing back together and enriching each other. One can view both fields of research as departures from an original von Neumann computer organization consisting of a central
processing unit (CPU)
acting on data in a main memory and interacting with the outside world through
peripheral devices
.
I/S attitudes: toward theoretical and definitional clarity
Authors: Goodhue Dale
Published: October 2004

There has long been a recognized need to measure the "success" or efficacy of information systems and the implementation process. Various constructs related to success have been suggested such as user attitudes, use, performance, and value. The attitude construct has received a great deal of attention for both theoretical and operational reasons. This paper focuses on the need for a convincing theoretical model linking systems or policies and user attitudes on the one hand, and user attitude and performance or value on the other. Using job satisfaction research as a reference discipline for understanding the relationship between attitudes and performance, a model of I/S attitudes, beliefs, and performance is developed. This model suggests that performance is affected by the correspondence or "fit" between the task requirements and the functionality of the I/S environment. In addition a distinction between beliefs and attitudes is recommended. While satisfaction might be best determined by measuring attitudes, the correspondence between task and functionality is best determined by measuring beliefs. The implications of this model for future research are discussed.
The impact of planning languages on the development of corporate models
Authors: Tillman Gerald J. , Watson Hugh J.
Published: October 2004

Since their introduction in the late 1960's, planning languages have continued to evolve and to have a growing impact on corporate modeling. In order to better understand how planning languages affect the predevelopment, development, and implementation and use phases of corporate modeling, eight corporate models developed using a planning language and two developed using a general-purpose language were investigated. The findings suggest that planning languages impact corporate modeling in important ways.
Utilization as a dependent variable in MIS research
Authors: Trice Andrew W. , Treacy Michael E.
Published: October 2004

Utilization of an information system is an important and frequently measured is the conduit through which informationtechnology can affect performance. This paper addresses measurement issues associated with utilization variables. The discussion is motivated by a review of the literature and an examination of four relevant reference theories. It is asserted that utilization can be measured effectively if the measures chosen correspond to the measures suggested by an appropriate reference theory.
Rational for the design of reusable abstract data types implemented in Ada
Authors: Genillard C. , Ebel N. , Strohmeler A.
Published: October 2004

Reusable abstract data types may be implemented in Ada as generic packages. First we will state some design goals, then outline our solution, address its rationale and show why alternatives have to be rejected. The presented design rules have already been applied successfully for implementing a rather wide set of abstract data types.
Mixing coroutines and processes in an Ada tasking implementation
Authors: Vestal S.
Published: October 2004

Not all tasks in an Ada program make use of the full functionality defined in the language reference manual. Certain idiomatic uses of Ada tasks allow these tasks to be implemented as coroutines. This paper presents a method for mixing coroutines and processes to achieve a full implementation for Ada tasking. This approach allows a variety of trade-offs to be made between the level of concurrency, synchronization expense, and scheduling fairness. This, in turn, allows tuning the runtime support for specific application requirements and hardware capabilities.
Parameterization: a case study
Authors: Tracz Will
Published: October 2004

This paper describes the parameterization of a simple Ada program. Ada was designed to include many programming language constructs that facilitate the development of parameterized software abstractions. By presenting parameterization as a series of incremental steps that separate and refine data abstractions, this paper illustrates certain Ada language features, programming design decisions, and tradeoffs that need to be taken into consideration when developing adaptable, reusable software. Once the parameterization process is quantified, a description of how existing programs can be automatically parameterized is presented.
The internet worm program: an analysis
Authors: Spafford Eugene H.
Published: October 2004

On the evening of 2 November 1988, someone infected the Internet with a
worm
program. That program exploited flaws in utility programs in systems based on BSD-derived versions of UNIX. The flaws allowed the program to break into those machines and copy itself, thus
infecting
those systems. This program eventually spread to thousands of machines, and disrupted normal activities and Internet connectivity for many days.This report gives a detailed description of the components of the worm program---data and functions. It is based on study of
two
completely independent reverse-compilations of the worm and a version disassembled to VAX assembly language. Almost no source code is given in the paper because of current concerns about the state of the "immune system" of Internet hosts, but the description should be detailed enough to allow the reader to understand the behavior of the program.The paper contains a review of the security flaws exploited by the worm program, and gives some recommendations on how to eliminate or mitigate their future use. The report also includes an analysis of the coding style and methods used by the author(s) of the worm, and draws some conclusions about his abilities and intent.
The experimental literature of the internet: an annotated bibliography
Authors: Mogul Jeffrey C.
Published: October 2004

The DARPA Internet is the most successful experiment in heterogeneous internetworking. It connects computer systems from almost every major vendor, using a wide variety of wide-area and local-area network technology, and is in continual use by thousands of people. This annotated bibliography covers the literature of the Internet as an experiment: publications which convey the experience acquired by the experimenters.
Network and nodal architectures for the internetworking between frame relaying services
Authors: Lai Wai Sum
Published: October 2004

Frame relaying is a new CCITT-recommended packet mode bearer service in ISDNs for data communications. Its major characteristics are out-of-band call control and link layer multiplexing.Requirements for the interworking between frame relaying services are the support for a multi-network, multi-vendor environment, and the integration of call control. After a comparison of the service characteristics of packet switching, circuit switching, and frame relaying, we conclude that the
inter-nodal
interworking strategy meets these requirements better than the
internetwork
interworking strategy.To understand better the requirements of a network architecture for the provision of frame relaying service, and to lend support for the standardization of the inter-nodal interworking strategy, a preliminary view on the functional structure of a network node is presented.
The complexity of the circularity problem for attribute grammars: a note on a counterexample for a simpler construction
Authors: Engelfriet Joost
Published: October 2004

It is shown in [Dil] that the construction in [Jaz] is incorrect. A correct version of the construction can be found in [EngFil].
How To Answer It
Authors: Salenieks Peter , Farringdon Michael G .
Published: October 2004

A light hearted corollary to Dana Angluin's ideas on the notion of 'proof' is presented. It offers useful advice to people who attend seminars and conferences, either to speak or to listen.
The Spring kernel: a new paradigm for real-time operating systems
Authors: Stankovic J. A. , Ramamritham K.
Published: October 2004

Next generation real-time systems will require greater flexibility and predictability than is commonly found in today's systems. These future systems include the space station, integrated vision/robotics/AI systems, collections of humans/robots coordinating to achieve common objectives (usually in hazardous environments such as undersea exploration or chemical plants), and various command and control applications. The Spring kernel is a research oriented kernel designed to form the basis of a flexible, hard real-time operating system for such applications. Our approach challenges several basic assumptions upon which most current real-time operating systems are built and subsequently advocates a new paradigm based on the notion of predictability and a method for on-line dynamic guarantees of deadlines. The Spring kernel is being implemented on a network of (68020 based) multiprocessors called SpringNet.
Operating system support for adaptive distributed real-time systems in DRAGON SLAYER
Authors: Wedde H. F. , Alijani G. S. , Brown W. G. , Chen S. , Kang G.
Published: October 2004

We analyze current and future needs in building adaptive real-time systems, and then formulate a series of design requirements for their hardware/interconnection, operating system, and application levels from which we derive a plea for a
layered and integrated system design.
We report on the novel distributed operating system DRAGON SLAYER which provides highly reliable and adaptive kernel services for real-time applications. It supports the novel file system MELODY which, in order to both meet real-time constraints and provide for high availability in a hazardous environment, allows for replicating, relocating, or deleting of file copies. Such copies may also assume a different status regarding the recency, reliability, and consistency of their information: They may be
public
or
private.
Status changes as well as file replication, deletion, or relocation are analyzed and managed by
local file assigners
, based on cost and time delay criteria and - for public copies - on cooperation with all file assigners responsible for the other public copies of a given file. A distributed implementation of our integrated system design model is currently being completed in our labs in order to serve as a
distributed real-time testbed.
For systems modeled according to our design requirements all relevant parameters could be checked and fine-tuned according to the environmental situation for the tested system.- We also report on a sensitivity study that shows how promptly the MELODY file system reacts to changing environmental situations (changing request patterns). Our findings are discussed, future work is outlined.
The real-time operating system of MARS
Authors: Damm A. , Reisinger J. , Schwabl W. , Kopetz H.
Published: October 2004

This paper gives a short overview of the architecture of the distributed real-time system MARS (
MA
intainable
R
eal-Time
S
ystem) and describes the design and implementation of its operating system. The main purpose of the MARS kernel is to achieve a timely execution of hard real-time tasks and to provide an efficient communication mechanism suitable for distributed real-time systems.
An object-oriented methodology for database/knowledgebase coupling: an implementation of the structured entity model in Nexpert system
Authors: Higa Kunihiko , Sheng R. L.
Published: October 2004

Advantages of a coupled database/knowledgebase (DB/KB) have been widely recognized by both researchers and practitioners. The issue addressed in this paper is how to achieve a natural and effective DB/KB coupling. A major weakness of a typical database system is its lack of semantic support. A knowledge-based system can provide semantic support to a database system. On the other hand, development of a large effective knowlgedebase is difficult because of its limited capacity to and maintain factual data. A database system can help a knowledge-based system overcome this weakness. Thus DB/KB coupling enhances functionality of both participating database systems and knowledge-based systems. The Structured Entity Model (SEM) method, an object-oriented methodology which initially was developed as a logical database design, is capable of accommodating a natural and effective DB/KB coupling design. SEM is derived from System Entity Structure, which is a hierarchical knowledge representation for simulation modeling. Because of the hierarchical structure and decomposition constructs of SEM, it can help a designer perform top-down structured analysis and design of databases. SEM also achieves a high level of semantic expressiveness by using a frame representation for entities and three general association categories (aspect, specialization, and multiple decomposition) for relationships. Update and query constraints and other semantics can be stored in each frame. This also enables SEM to have high potential as a knowledge representation scheme for a knowledgebase. Since both database schema and knowledge structure are produced from the same SEM structure, they are naturally coupled through a common SEM structure. In this paper, the use of SEM as a methodology for producing a coupled DB/KB is described. SEM is implemented using Nexpert system This implementation is illustrated through a DB/KB coupling example based on an Integrated Office Information System (IOIS)
Addressing the problem of software library management for object oriented and conventional operator/operand systems, utilizing the entity-relationship approach
Authors: Clark G. , Clark J. , Ling T. W.
Published: October 2004

Large commercial and research establishments who attempt to reuse software to construct operable systems confront the problem of code management. The increasing availability and usage of Computer Aided Software Engineering, CASE, tools coupled with the production of highly reusable code modules induces the need for more sophisticated and versatile library management facilities. This paper describes how the entity relationship approach can be used to address the problem of library management for design, code, and program management libraries. This approach to library management is independent of software development methodologies, hence is capable of supporting object oriented and convential operator/operand system designs and implementations.
Reducing unpredictability in Ada executions
Authors: Mazzanti F.
Published: October 2004

One of the most drastic examples of uncertainty of a program execution is surely that of an unrecoverable run-time error causing the failure of the whole program.This kind of failure is possible also in the case of Ada, and is allowed by the occurrence of a particular class of run-time errors for which there is no requirement on Ada compilers or interpreters to provide either a static or run-time detection. When one of these undetected errors occurs the program execution is said to become "erroneous" (i.e. no more governed by Ada rules) and and its effect is considered "unpredictable". An unrecoverable failure of the whole program (e.g. caused by a memory protection violation, or by a run-time system internal error) is just one of the possible symptoms of the program erroneousness.A study on the possible ways to cope with this kind of errors has been carried out inside the activity of the EEC MAP project n. 755 "SFD-APSE". In particular, the attention has been concentrated on the possibility of detecting at run time the occurrence of erroneous executions and on the possibility of recovering from them in a safe way.In this paper the project results are shortly summarized and the possible directions for further activity are pointed out.
Forcing the completion of abnormal tasks
Authors: Papay D.
Published: October 2004

The
abort
statement is used to bring about the unconditional completion of one or more tasks. However, some tasks are not required to become complete immediately upon execution of the abort statement and can continue to execute, perhaps indefinitely. While the use of forced synchronization points will bring about the completion of such tasks, they can produce undesirable run-time behavior in "normal" tasks. This paper presents an alternative to unconditional forced synchronization that allows abnormal tasks to become complete, but does not interfere with normal tasks.
A data acquisition and information handling system in Ada for electron spectroscopy
Authors: Carlsson M. , Asplund L.
Published: October 2004

A distributed, real time, data acquisition computer system for electron spectroscopy, ESCA, is presented. The design and implementation in Ada involves windowing, menus, forms, graphical presentation, multitasking and instrumental communication. Our experience using Ada is discussed. Ada has been used in all phases. Data types and packages are presented. It is found that the language is very suitable for scientific purposes.
The role of Ada in contemporary interface technology
Authors: Boyd S.
Published: October 2004

This report addresses certain issues relevant to Ada interface technology, and identifies technical and organizational barriers to Ada's effective use as an interface medium. The report provides examples from the SQL Ada area, and the proposed POSIX Ada standard, and presents the argument that the principles which motivate good software design must be applied in the development of workable interface standards.
Database theory column
Authors: Kanellakis P. , Abiteboul S.
Published: October 2004

The study of database logic programs, popularly known as Datalog programs, is one of the principal research themes in database theory today. Datalog is the simplest formalism available for describing rule-based programming and, thus, of interest to the larger computer science community. A key optimization problem is to estimate the depth of recursion of a database logic program, as a function of the size of its input database. Deciding bounded recursion for a given program, i.e., determining whether its depth of recursion is bounded by a constant independent of the input, turns out to be a basic and surprisingly subtle task. In the first database theory column, we review the progress made on understanding bounded recursion and list some of the outstanding open questions. For the readers, who are not familiar with the terminology, we include the relevant definitions.
A lower bound on the size of universal sets for planar graphs
Authors: Chrobak M. , Karloff H.
Published: October 2004

A
Fáry embedding
of a planar graph
G
is an embedding of
G
into the plane, no edges crossing, with each edge embedded as a straight line segment. A set
A
C IR
2
is said to be
n-universal
if every
n
-node planar graph has a Fáry embedding into
A.
We show that any
n
-universal set has size at least 1.098
n
, for sufficiently large
n.
Primitive recursion without implicit predecessor
Authors: Fischer M. J. , Fischer E. , Beigel R.
Published: October 2004

The
primitive recursive functions
are the least class of functions on the natural numbers containing the constant, successor, and projection functions, and closed under composition and the rule of primitive recursion. A weakened rule of primitive recursion, lacking implicit predecessor, is shown nevertheless to be adequate for defining all of the primitive recursive functions. However, it is conjectured that the still weaker rule of iteration is not adequate, and it is shown that an easily characterized class of 1-Place functions that includes predecessor cannot be defined when only 0- and 1-place intermediate functions are allowed.
Comments on “security problems in the TCP/IP protocol suite”
Authors: Kent S.
Published: October 2004

In the April issue of
Computer Communication Review,
S. M. Bellovin described attacks on protocols in the TCP/IP suite [1]. He stated that the attacks were "inherent in the protocols, regardless of the correctness of any implementations." His article proposed specific defenses against these attacks and discussed more comprehensive defenses. This note attempts to place in perspective some of the concerns cited by Bellovin and to correct some errors present in his article, especially in his discussion of comprehensive defenses.
Using one-way functions for authentication
Authors: Gong L.
Published: October 2004

Techniques are suggested to construct authentication protocols on a basis of one-way functions rather than encryption algorithms. This approach is thought of interest for several reasons. It appears that this approach could achieve, at least, equally simple and capable protocols.
A connectionless congestion control algorithm
Authors: Finn G. G.
Published: October 2004

This paper describes a congestion control algorithm that operates within a connectionless network environment. The algorithm controls a source's transmission rate, with that rate determined by feedback from the point of congestion. The algorithm is well suited to operate from within the IP layer of the TCP/IP protocol suite. An analytic model is developed to examine isolated aspects of the algorithm's behavior. A simulator was written to further test its behavior under a variety of topologies, loads, and path bandwidths. The results achieved are presented.
Improving the efficiency of the OSI checksum calculation
Authors: Sklower K.
Published: October 2004

It is known that using larger byte--sizes to access memory usually results in faster computations of checksum algorithms. This paper proposes two different ways to use larger byte--sizes to improve the performance of the OSI checksum. First, an algorithm is presented that computes the 8--bit checksum using 16-bit integers. It is shown that this algorithm yields a 5 to 20 percent performance improvement on many architectures. Second, the benefits of expanding the basic computation unit of the OSI checksum algorithm to 16--bits integers is considered. This change can yield an additional performance improvement of up to 50% and greatly extended error detection properties, although it is incompatible with the current standard. The measurements of these algorithms are compared with some taken of checksums in common use, such as IP and XNS†.
Simple but effective techniques for NUMA memory management
Authors: Bolosky W. , Fitzgerald R. , Scott M.
Published: October 2004

Multiprocessors with non-uniform memory access times introduce the problem of placing data near the processes that use them, in order to improve performance. We have implemented an automatic page placement strategy in the Mach operating system on the IBM ACE multiprocessor workstation. Our experience indicates that even very simple automatic strategies can produce nearly optimal page placement. It also suggests that the greatest leverage for further performance improvement lies in reducing
false sharing
, which occurs when the same page contains objects that would best be placed in different memories.
The implementation of a coherent memory abstraction on a NUMA multiprocessor: experiences with platinum
Authors: Cox A. , Fowler R.
Published: October 2004

PLATINUM is an operating system kernel with a novel memory management system for
Non-Uniform Memory Access
(NUMA) multiprocessor architectures. This memory management system implements a
coherent memory
abstraction. Coherent memory is uniformly accessible from all processors in the system. When used by applications coded with appropriate programming styles it appears to be nearly as fast as local physical memory and it reduces memory contention. Coherent memory makes programming NUMA multiprocessors easier for the user while attaining a level of performance comparable with hand-tuned programs.

This paper describes the design and implementation of the PLATINUM memory management system, emphasizing the coherent memory. We measure the cost of basic operations implementing the coherent memory. We also measure the performance of a set of application programs running on PLATINUM. Finally, we comment on the interaction between architecture and the coherent memory system.

PLATINUM currently runs on the BBN Butterfly Plus Multiprocessor.
Exploiting read-mostly workloads in the FileNet file system
Authors: Edwards D. , Mckendry M.
Published: October 2004

Most recent studies of file system workloads have focussed on loads imposed by general computing. This paper introduces a significantly different workload imposed by a
distributed application system
. The FileNet system is a distributed application system that supports document image processing. The FileNet file system was designed to support the workload imposed by this application. To characterize the
read-mostly
workload applied to the file system and how it differs from general computing environments, we present statistics gathered from live production installations. We contrast these statistics with previously published data for more general computing.

We describe the key algorithms of the file system, focusing on the caching approach. A
bimodal
client caching approach is employed, to match the file modification patterns observed. Different cache consistency algorithms are used depending on usage patterns observed for each file. Under most conditions, files cached at workstations can be accessed without contacting servers. When a file is subject to frequent modification that causes excessive cache consistency traffic, caching is disabled for that file, and servers participate in all open and close activities.

The data from production sites is examined to evaluate the success of the approach under its applied load. Contrasts with alternative approaches are made based on this data.
Improving the efficiency of UNIX buffer caches
Authors: Braunstein A. , Riley M. , Wilkes J.
Published: October 2004

This paper reports on the effects of using hardware virtual memory assists in managing file buffer caches in UNIX. A controlled experimental environment was constructed from two systems whose only difference was that one of them (XMF) used the virtual memory hardware to assist file buffer cache search and retrieval. An extensive series of performance characterizations was used to study the effects of varying the buffer cache size (from 3 Megabytes to 70 MB); I\O transfer sizes (from 4 bytes to 64 KB); cache-resident and non-cache-resident data;
READ
s and
WRITE
s; and a range of application programs.

The results: small
READ/WRITE
transfers from the cache (≤1 KB) were 5O% faster under XMF, while larger transfers (≥8 KB) were 20% faster. Retrieving data from disk, the XMF improvement was 25% and 1O% respectively, although
OPEN/CLOSE
system calls took slightly longer in XMF. Some individual programs ran as much as 40% faster on XMF, while an application benchmark suite showed a 7-15% improvement in overall execution time. Perhaps surprisingly. XMF had fewer translation lookaside buffer misses.
Performance of Firefly RPC
Authors: Schroeder M. , Burrows M.
Published: October 2004

In this paper, we report on the performance of the remote procedure call implementation for the Firefly multiprocessor and analyze the implementation to account precisely for all measured latency. From the analysis and measurements, we estimate how much faster RPC could be if certain improvements were made.

The elapsed time for an inter-machine call to a remote procedure that accepts no arguments and produces no results is 2.66 milliseconds. The elapsed time for an RPC that has a single 1440-byte result (the maximum result that will fit in a single packet) is 6.35 milliseconds. Maximum inter-machine throughput of application program data using RPC is 4.65 megabits/second, achieved with 4 threads making parallel RPCs that return the maximum sized result that fits in a single RPC result packet. CPU utilization at maximum throughput is about 1.2 CPU seconds per second on the calling machine and a little less on the server.

These measurements are for RPCs from user space on one machine to user space on another, using the installed system and a 10 megabit/second Ethernet. The RPC packet exchange protocol is built on IP/UDP, and the times include calculating and verifying UDP checksums. The Fireflies used in the tests had 5 Micro VAX II processors and a DEQNA Ethernet controller.
The portable common runtime approach to interoperability
Authors: Weiser M. , Demers A. , Hauser C.
Published: October 2004

Operating system abstractions do not always reach high enough for direct use by a language or applications designer. The gap is filled by language-specific runtime environments, which become more complex for richer languages (CommonLisp needs more than C+ +, which needs more than C). But language-specific environments inhibit integrated multi-lingual programming, and also make porting hard (for instance, because of operating system dependencies). To help solve these problems, we have built the Portable Common Runtime (PCR), a language-independent and operating-system-independent base for modern languages. PCR offers four interrelated facilities: storage management (including universal garbage collection), symbol binding (including static and dynamic linking and loading), threads (lightweight processes), and low-level I/O (including network sockets). PCR is “common” because these facilities simultaneously support programs in several languages. PCR supports C. Cedar, Scheme, and CommonLisp intercalling and runs pre-existing C and CommonLisp (Kyoto) binaries. PCR is “portable” because it uses only a small set of operating system features. The PCR source code is available for use by other researchers and developers.
The Amber system: parallel programming on a network of multiprocessors
Authors: Chase J. , Amador F. , Lazowska E. , Levy H. , Littlefield R.
Published: October 2004

This paper describes a programming system called
Amber
that permits a single application program to use a homogeneous network of computers in a uniform way, making the network appear to the application as an integrated multiprocessor. Amber is specifically designed for high performance in the case where each node in the network is a shared-memory multiprocessor.

Amber shows that support for loosely-coupled multiprocessing can be efficiently realized using an object-based programming model. Amber programs execute in a uniform network-wide object space, with memory coherence maintained at the object level. Careful data placement and consistency control are essential for reducing communication overhead in a loosely-coupled system. Amber programmers use object migration primitives to control the location of data and processing.