OS and Networks Commons^™

A Toolkit For Specializing Production Operating System Code, Crispin Cowan, Dylan Mcnamee, Andrew P. Black, Calton Pu, Jonathan Walpole, Charles Krasic, Perry Wagle, Qian Zhang

Computer Science Faculty Publications and Presentations

Specialization has been recognized as a powerful technique for optimizing operating systems. However, specialization has not been broadly applied beyond the research community because the current techniques, based on manual specialization, are time-consuming and error-prone. This paper describes a specialization toolkit that should help broaden the applicability of specializing operating systems by assisting in the automatic generation of specialized code, and {\em guarding} the specialized code to ensure the specialized system continues to be correct. We demonstrate the effectiveness of the toolkit by describing experiences we have had applying it in real, production environments. We report on our experiences with …

Physical Media Independence: System Support For Dynamically Available Network Interfaces, Jon Inouye, Jim Binkley, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Advances in hardware technology has fueled the proliferation of dynamically configurable network interface cards. This empowers mobile laptop users to select the most appropriate interface for their current environment. Unfortunately, the majority of system software remains "customized" for a particular network configuration, and assumes many network characteristics remain invariant over the runtime of the software. Physical Media Independence (PMI) is the concept of making assumptions about a particular device explicit, detecting events which invalidate these assumptions, and recovering once events are detected. This paper presents a model supporting PMI. Based on device availablilty, the model identifies implicit device-related assumptions made …

Multimedia Applications Require Adaptive Cpu Scheduling, Veronica Baiceanu, Crispin Cowan, Dylan Mcnamee, Calton Pu, Jonathan Walpole

Computer Science Faculty Publications and Presentations

CPU scheduling and admission testing for multimedia applications have been extensively studied, and various solutions have been proposed using assorted simplifying assumptions. However, we believe that the complexity and dynamic behavior of multimedia applications and systems make static solutions hard to apply in real-world situations. We are analyzing the difficulties that arise when applying the rate-monotonic (RM) scheduling algorithm and the corresponding admission tests for CPU management, in the context of real multimedia applications running on real systems. RM requires statically predictable, periodic workloads, and while multimedia applications appear to be periodic, in practice they exhibit numerous variabilities in workload. …

Resource/Dataflow Graph Operating System Development, Sriram J. Coimbatore

Electrical & Computer Engineering Theses & Dissertations

Implementation of a new dataflow schedule model is the objective of this thesis. The dataflow model algorithm called the resource/dataflow graph model is implemented on a peer-to-peer communication network comprising of six personal computers. This dataflow model is implemented making use of an earlier dataflow model called ATAMM (Algorithm to Architecture Mapping Model) developed by ODU and National Aeronautics and Space Administration (NASA). Development issues include modification of the RDFG testbed operating system and a scheme to transfer data buffers using the ethernet channel from one processor to another processor. This, in turn, equips each sub-module of an application with …

Concept Hierarchy Memory Model: A Neural Architecture For Conceptual Knowledge Representation, Learning, And Commonsense Reasoning, Ah-Hwee Tan, Hui-Shin Vivien Soon

Research Collection School Of Computing and Information Systems

This article introduces a neural network based cognitive architecture termed Concept Hierarchy Memory Model (CHMM) for conceptual knowledge representation and commonsense reasoning. CHMM is composed of two subnetworks: a Concept Formation Network (CFN), that acquires concepts based on their sensory representations; and a Concept Hierarchy Network (CHN), that encodes hierarchical relationships between concepts. Based on Adaptive Resonance Associative Map (ARAM), a supervised Adaptive Resonance Theory (ART) model, CHMM provides a systematic treatment for concept formation and organization of a concept hierarchy. Specifically, a concept can be learned by sampling activities across multiple sensory fields. By chunking relations between concepts as …

Scheduling Processors For Distributed, Critical, Real-Time Systems, Hari K. Narasimhamurthy

Electrical & Computer Engineering Theses & Dissertations

The development of a procedure to obtain cyclo-static schedules for distributed, critical real-time applications is presented in this thesis. The applications considered in this thesis are characterized by hard deadlines and periodic inputs. The applica­ tions are described by a data flow graph model which guarantees performance. Given the data flow graph representation, processors are scheduled to complete tasks as specified in the representation. The scheduling technique separates the scheduling of tasks in time and the assignment of processors to tasks. While different criteria exist for task scheduling, a schedule which minimizes latency and maximizes throughput is used in this …

Customizable Operating Systems, Jonathan Walpole, Crispin Cowan, Andrew P. Black, Jon Inouye, Calton Pu, Shanwei Cen

Computer Science Faculty Publications and Presentations

A customizable operating system is one that can adapt to improve its functionality or performance. The need for customizable and application-specific operating systems has been recognized for many years, but they have yet to appear in the commercial market. This paper explores the notion of operating system customizability and examines the limits of existing approaches. The paper begins by surveying system structuring approaches for the safe and efficient execution of customizable operating systems. Then it discusses the burden that existing approaches impose on application software, and explores techniques for reducing this burden. Finally, support for customizability in the Synthetix project …

Device And Physical Data Independence For Multimedia Presentations, Richard Staehli, Jonathan Walpole, David Maier

Computer Science Faculty Publications and Presentations

Multimedia computing promises access to any type of visual or aural medium on the desktop. But in this networked future, will every type of media be accessible from every terminal device? Current multimedia standards do not allow content that is authored for high-bandwidth workstations to scale down for low-bandwidth applications. The problem is that application requests are commonly interpreted as requests for the highest possible quality and resource overloads are handled by ad hoc methods. We can begin to solve this problem by specifying Quality of Service (QOS) requirements based on functionality rather than on content encoding and device capabilities.

Device And Physical Data Independence For Multimedia Presentations, Richard Staehli, Jonathan Walpole, David Maier

Computer Science Faculty Publications and Presentations

Multimedia computing promises access to any type of visual or aural medium on the desktop. But in this networked future, will every type of media be accessible from every terminal device? Current multimedia standards do not allow content that is authored for high-bandwidth workstations to scale down for low-bandwidth applications. The problem is that application requests are commonly interpreted as requests for the highest possible quality and resource overloads are handled by ad hoc methods. We can begin to solve this problem by specifying Quality of Service (QOS) requirements based on functionality rather than on content encoding and device capabilities.

Mpvm: A Migration Transparent Version Of Pvm, Jeremy Casas, Dan Clark, Ravi Konuru, Steve Otto, Robert Prouty, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Parallel Virtual Machine (PVM) is a widely-used software system that allows a heterogeneous set of parallel and serial UNIX-based computers to be programmed as a single message-passing parallel machine, In this paper, an extension to PVM to support dynamic process migration is presented. Support for migration is important in general-purpose workstation environments since it allows parallel computations to co-exist with other applications, using idle-cycles as they become available and off-loading from workstations when they are no longer free. A description and evaluation of the design and implementation of the prototype Migratable PVM system is presented together with some performance results.

Scheduling Of Parallel Jobs On Dynamic, Heterogenous Networks, Dan Clark, Jeremy Casas, Steve Otto, Robert Prouty, Jonathan Walpole

Computer Science Faculty Publications and Presentations

In using a shared network of workstations for parallel processing, it is not only important to consider heterogeneity and differences in processing power between the workstations but also the dynamics of the system as a whole. In such a computing environment where the use of resources vary as other applications consume and release resources, intelligent scheduling of the parallel jobs onto the available resources is essential to maximize resource utilization. Despite this realization, however, there are few systems available that provide an infrastructure for the easy development and testing of these intelligent schedulers. In this paper, an infrastructure is presented …

Optimizing Object Invocation Using Optimistic Incremental Specialization, Jon Inouye, Andrew P. Black, Charles Consel, Calton Pu, Jonathan Walpole

Computer Science Faculty Publications and Presentations

To make object invocation efficient, it is important to minimize overhead. In general, overhead is incurred in order to maintain transparency; with the advent of mobile computer systems, persistence, increasing security and privacy concerns, transparency becomes more expensive and overhead is increasing. Invocation mechanisms maintain transparency by finding objects, choosing communication media, performing data translation into common formats (e.g., XDR), marshalling arguments, encrypting confidential data, etc. Performing all of these operations on every invocation would lead to unacceptable performance, so designers often avoid operations by specializing object invocation for more restricted environments. For example, the Emerald compiler performs several optimizations …

Adaptive Resonance Associative Map, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

This article introduces a neural architecture termed Adaptive Resonance Associative Map (ARAM) that extends unsupervised Adaptive Resonance Theory (ART) systems for rapid, yet stable, heteroassociative learning. ARAM can be visualized as two overlapping ART networks sharing a single category field. Although ARAM is simpler in architecture than another class of supervised ART models known as ARTMAP, it produces classification performance equivalent to that of ARTMAP. As ARAM network structure and operations are symmetrical, associative recall can be performed in both directions. With maximal vigilance settings, ARAM encodes pattern pairs explicitly as cognitive chunks and thus guarantees perfect storage and recall …

Objects To The Rescue! Or Httpd: The Next Generation Operating System, Andrew P. Black, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This position paper suggests that object-oriented operating systems may provide the means to meet the ever-growing demands of applications. As an example of a successful OOOS, we cite the http daemon. To support the contention that httpd is in fact an operating system, we observe that it implements uniform naming, persistent objects and an invocation meta-protocol, specifies and implements some useful objects, and provides a framework for extensibility.We also believe that the modularity that is characteristic of OO systems should provide a performance benefit rather than a penalty. Our ongoing work in the Synthetix project at OGI is exploring the …

A User-Level Process Package For Concurrent Computing, Ravi Konuru, Steve Otto, Jonathan Walpole, Robert Prouty, Jeremy Casas

Computer Science Faculty Publications and Presentations

A lightweight user-level process(ULP) package for parallel computing is described. Each ULP has its own register context, stack, data and heap space and communication with other ULPs is performed using locally synchronous, location transparent, message passing primitives. The aim of the package is to provide support for lightweight over-decomposition, optimized local communication and transparent dynamic migration. The package supports a subset of the Parallel Virtual Machine(PVM) interface[Sun90).

Dynamic Task Scheduling For The Atamm Multicomputer Operating System Using Embedded Firmware On Microcontrollers, Sudhir Sastry

Electrical & Computer Engineering Theses & Dissertations

A dynamic task scheduling strategy for the distributed processing of large grain dataflow algorithms using embedded firmware on an ATAMM testbed consisting of interconnected microcontrollers is presented in this thesis. The ODU/NASA developed Algorithm to Architecture Mapping Model, ATAMM, uses marked graph models to specify data and control flow for the execution of iterative, deterministic large grain dataflow algorithms in a multicomputing environment. The testbed consists of a bank of four 68HC11 microcontrollers that communicate over a token bus. The token bus arbitration scheme used is contention free and well suited for real-time computing applications. The execution of data flow …

Script-Based Qos Specifications For Multimedia Presentations, Richard Staehli, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Multimedia presentations can convey information not only by the sequence of events but by their timing. The correctness of such presentations thus depends on the timing of events as well as their sequence and content. This paper introduces a formal specification language for playback of real-time presentations. The main contribution of this language is a quality of service (QOS) specification that relaxes resolution and synchronization requirements for playback. Our definitions give a precise meaning to the correctness of a presentation. This specification language will form the basis for a QOS interface for reservation of operating system resources.

Porting Chorus To The Pa-Risc: Overall Evaluation, Jonathan Walpole, Marion Hakanson, Jon Inouye, Ravi Konuru

Computer Science Faculty Publications and Presentations

This document is part of a series of reports describing the design decisions made in porting the Chorus Operating System kernel to the Hewlett-Packard 9000 Series 800 workstation. This document summarizes the matches and mis-matches between Chorus and the PA-RISC and outlines the general lessons learned during the project.

This document is intended for people who are interested in (a) the separation of machinedependent micro-kernel code from machine-independent micro-kernel code, (b) the interaction between operating system design and the PA-RISC architecture, and (c) the portability ofthe Chorus operating system.

The first report in the series, Porting Chorus to the PA-RISe: …

Porting Chorus To The Pa-Risc: Virtual Memory Manager, Jon Inouye, Marion Hakanson, Ravi Konuru, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This document describes the port ofthe Chorus virtual memory manager to the Hewlett-Packard Precision Architecture rusc (PA-RISC) workstation. The information contained in this paper will be of interest to people who:

• intend to port the Chorus virtual memory section. • intend to port a virtual memory design to the Hewlett-Packard PA-RISC.

The reader is strongly encouraged to read the following PA-Chorus documents before reading this document:

• Technical Report CSE-92-3, Porting Chorus to the PA-RISC: Project Overview

Porting Chorus To The Pa-Risc: Project Overview, Jonathan Walpole, Marion Hakanson, Jon Inouye, Ravi Konuru

Computer Science Faculty Publications and Presentations

This document is part of a series of reports describing the design decisions made in porting the Chorus Operating System to the Hewlett-Packard 9000 Series 800 workstation. This document presents an overview of the project, and outlines the other reports in the series and the relationships between them.

Porting Chorus To The Pa-Risc: Building, Debugging, Testing And Validation, Ravi Konuru, Marion Hakanson, Jon Inouye, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This document is part of a series of reports describing the design decisions made in porting the Chorus Operating System to the Hewlett-Packard 9000 Series 800 workstation. This document describes the environment for building the Chorus kernel, the various kernel tests, and the debugging environment used for porting the Chorus operating system to the HP PA-RISC.

The information contained in this paper will be of interest to people who wish to:

• Use the PA-Chorus kernel for development and/or modification, • Know about the build environment for Chorus kernel on PA-RISC, • Know about the PA-Chorus approach to debugging, • …

Smimd - A Synchronous Multiple Instruction Multiple Data Computer Architecture, Cathy C. Roberts

Computer Science Theses & Dissertations

This thesis assesses the feasibility of utilizing a hypercube interconnect topology to link a heterogeneous processor array in a very long instruction word (VLIW) computer architecture. The research focused upon the selection of a suitable arrangement of processors for the computer and the subsequent demonstration of the architecture's capability to handle simple loop iterations. Previous attempts at VLIW computer design are summarized, the new SMIMD architecture is presented, and suggestions for future research are given. The thesis concludes with results of the initial performance evaluations of the architecture design.

Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

This thesis is primarily concerned with two problems of interconnecting components in VLSI technologies. In the first case, the goal is to construct efficient interconnection networks for general-purpose parallel computers. The second problem is a more specialized problem in the design of VLSI chips, namely multilayer channel routing. In addition, a final part of this thesis provides lower bounds on the area required for VLSI implementations of finite-state machines. This thesis shows that networks based on Leiserson's fat-tree architecture are nearly as good as any network built in a comparable amount of physical space. It shows that these "universal" networks …

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

Computer Science: Faculty Publications and Other Works

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda + lg n lg lg n) with probability 1-O(1/n). The best previous …

Randomized Routing On Fat-Trees, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda+lgnlglgn) with probability 1-O(1/ …