Engineering Commons^™

Self-Stabilization By Counter Flushing, George Varghese

All Computer Science and Engineering Research

A useful way to design simple and robust protocols is to make them self-stabilitizing. We describe a simple technique for self-stabilization called counter flushign which is applicable to a number of distributed algorithms. A randomized version of counter flushing is shown to have extremely small expected stabilization time. We show how our technique helps to crisply understand and improve some previous distributed algorithms. Then we apply it to a variety of total algorithms for deadlock detection, propagation of information with feedback, resets and snapshots. Our stabilizing snapshot protocol has much better complexity than the previous stabilizing non-blocking snapshot protocol. Hence …

Catching Up With The Networks: Host I/O At Gigabit Rates, Zubin D. Dittia, Jerome R. Cox Jr., Guru M. Parulkar

All Computer Science and Engineering Research

The last few years have seen network data rates skyrocket from a few Mbps to a Gbps or more. However, a lack of integration of the host-netowrk interface, the operating system, and network protocols has resulted in end-applications seeing only a small fraction of this total bandwidth being available for data transfer. The emergence of demanding applications in the realms of multimedia and virtual reality provides further impetus in the drive to overcome this problem. In this paper, we present the design of a high performance ATM host-network interface for workstations and servers that can support a bidirecitonal sustained data …

Performance Comparison Of Asynchronous Adders, Mark A. Franklin, Tienyo Pan

All Computer Science and Engineering Research

In asynchronous systems, average function delays principally govern overall throughput. This paper compares the performance of six adder designs with respect to their average delays. Our results show that asynchronous addres (32 or 64-bits) with a hybrid structure (e.g., carry-select addres) run 20-40% faster than simple ripple-carry addres. Hybrid adders also outperform high-cost, strictly synchronous conditional-sum adders.

Speculative Computation: Overcoming Communication Delays In Parallel Algorithms, Vasudha Govindan, Mark A. Franklin

All Computer Science and Engineering Research

Communication latencies and delays are a major source of performance degradation in parallel computing systems. It is importnat to "mask" these communication delays by overlapping them with useful computation in order to obtain good parallel performance. This paper proposes speculative computation as a technique to mask communication latencies. Speculative computation is discussed in the context of synchronous iterative algorithms. Processors speculate the contents of messages that are not hyet received and perform computation based on the speculated values. When the messages are received, they are compared with the speculated values and, if the error is unacceptable, the resulitng computation is …

Design Of A Large Scale Multimedia Server, Milind M. Buddhikot, Guru Parulkar, Jerome R. Cox Jr.

All Computer Science and Engineering Research

Large scale multimedia storage servers will be an integral part of the emerging distributed multimedia computing infrastructure. However, given the modest rate of improvements in storage transfer rates, designing servers that meet the demands of multimedia applications is a challenging task that needs significant architectural innovation. Our research project, called Massively-parallel And Real-time Storage (MARS) architecture, is aimed at the design and prototype implementation of a large scale multimedia storage server. It uses some of the well-known techniques in parallel I/O, such as data striping and Redundant Arrays of Inexpensive Disks (RAID) and an innovative ATM based interconnect inside the …

Practical Methods For Approximating Shortest Paths On A Convex Polytope In R3, John Hershberger, Subhash Suri

All Computer Science and Engineering Research

We propose a n extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions. Given a convex polytope P with n vertices and two points p,q on its surface, let dp (p,q) denote the shortest path distance between p and q on the surface of P. Our algorithm produces a path of length at most 2 × dp(p,q) in time O(n). Extending this results, we can also compute ana pproximation of the shortest path tree rooted at an arbitrary point χ Є P in time O(n log n). In the approximate tree, …

High-Performance Training Of Feedforward & Simple Recurrent Networks, Barry L. Kalman, Stan C. Kwasny

All Computer Science and Engineering Research

TRAINREC is a system for training feedforward and recurrent neural networks that incorporates several ideas. It uses the conjugate-gradient method which is demonstrably more efficient than traditional backward error propagation. We assume epoch-based training and derive a new error function having several desirable properties absent from the traditional sum-of-squared-error function. We argue for skip (shortcut) connections where appropriate and the preference for a sigmoidal yielding values over the [-1,1] interval. The input feature space is often over-analyzed, but by using singular value decomposition, input patterns can be conditioned for better learning often with a reduced number of input units. Recurrent …

Universal Continuous Media I/O: Design And Implementation, Charles D. Cranor, Gurudatta M. Parulkar

All Computer Science and Engineering Research

The problem this paper addresses is how to modify an existing operating system's I/O subsystem to support new high-speed networks and high-bandwidth multimedia applications that will play an important role in future computing environments. The proposed I/O subsystem is called universal continuous media I/O (UCM I/O). This paper will cover the preliminary design of UCM I/O, some of the trade-offs and issues that need to be addressed in order to implement UCM I/O, and a summary of work in progress.

Reasoning About Places, Times, And Actions In The Presence Of Mobility, C. Donald Wilcox, Gruia-Catalin Roman

All Computer Science and Engineering Research

The current trend toward portable computing systems (e.g., cellular phones, laptop computers) brings with it the need for a new paradigm for thinking about designing distributed applications. We introduce the term mobile to refer to distributed systems that include moving, autonomous agents which loosely cooperate to accomplish a tastk. The fluid nature of hte interconnections between components in a mobile system provides new challenges and new opportunities for the research community. While we do not propsoe to have fully grasped the consequences of these systems, we believe that the notions of place, time, and action will be central in any …

Pipelined And Superscalar Architectures In Clocked And Asynchronous Environments, Mark A. Franklin, Tienyo Pan

All Computer Science and Engineering Research

In this paper, a set of simple, general, yet practical performance models for RISC architectures are developed. These models apply to a wide range of systems that include both pipelined and superscalar systems operating in either clocked or asynchronous environments. The models permit quantitative evaluation of various design choices (e.g., the number of pipelines in the system, the pipeline depth, and the choice between clocked and asynchronous methodologies) as functions of technology parameters, environmental operating parameters, and pipeline function characteristics. Design curves are presented indicating optimal pipeline depth and number of pipelines to employ under various conditions.

An Evaluation Of The Pavane Visualization System, Kenneth C. Cox, Gruia-Catalin Roman

All Computer Science and Engineering Research

The Pavane program visualization system is an implementation of the declarative paradigm of visualization. After a brief report on the status of the Pavane implementation, we present the results of an evaluation of the usability of Pavane. This evaluation is based on the use of Pavane by its developers to construct program visualizations, on its use in a classroom setting as a tool for examining executing programs, and on its application to some simple scientific visualizations.

Visual Specification Of Interprocess And Intraprocess Communication, T. Paul Mccartney, Kenneth J. Goldman

All Computer Science and Engineering Research

We present a visual specification language for constructing distributed applications and their direct manipulation graphical user interfaces. Each distributed application consists of a collection of independent modules and a configuration of logical connections that define communication among the data interfaces of the modules. Our specification language uses a single visual mechanism that allows end-users to define interprocess communication among distributed modules and to define intraprocess communication among objects within a module. This seamless specification provides a general encapsulation/abstraction mechanism and is designed to support dynamic change to the communication structure. User interfaces are completely decoupled from the module(s) they control.

Trading Packet Headers For Packet Processing, George Varghese

All Computer Science and Engineering Research

In high speed networks, packet processing is relatively expensive while bandwidth is cheap. This begs the question: what fields can be added to packets to make packet processing easier? By exploring this question, we device a number of novel mechanisms to speed up packet processing. With the advent of new standards for hte Data Link, Network, and Transport lyaers, we believe there is an opportunity to apply these techniques to improve the performance of real protocols. First, we suggest adding a data manipulation header to an easily accessible portion of each packet. This header contains pointers to fields (in various …

Cmap, Ken Cox, John Dehart

All Computer Science and Engineering Research

This document specifies a Connection Management Access Protocol (CMAP) for call management in high-speed packet switched networks. We target CMAP to networks employing the Asynchronous Transfer Mode (ATM) communication standard. CMAP specifies the access procedues exercised by network clients to manipulate multipoint calls; it is thus a User-Network Interface (UNI) signalling protocol. We define a multipoint call as a group of multipoint connections. A multipoint connection is a communication channel between two or more clients or endpoints of the network, where all data sent by one client is received by all other clients who have elected to receive. A point-to-point …

Cell Tracking Using A Distributed Algorithm For 3d Image Segmentation, Vikas Awasthi, Keith W. Doolittle, Guru Parulkar, James G. Mcnally

All Computer Science and Engineering Research

We have developed and tested an automated method for simultaneous 3D tracking of numerous, flourescently-tagged cells. The procedure uses multiple thresholding to segment individual cells at a starting timepoint, and then iteratively applies a template-matching algorithm to locate a particular cell's position at subsequent time points. To speed up the method, we have developed a distributed implementation in which template matching is carried out in parallel on several different server machines. The distributed implementation showed a monotonic decrease in response time with increasing number of servers (up to 15 tested), demonstrating that the tracking algorithm is well suited to parallelization, …

Efficient Quality Of Service Support In Multimedia Computer Operating Systems, Raman Gopalakrishna, Guru M. Parulkar

All Computer Science and Engineering Research

This report describes our approach towards providing quality of service (QoS) guarantees for network communication within the endsystems to support multimedia applications. We first address the problem of QoS specification by identifying a set of application classes and their QoS parameters that cover the communication requirements of most applications. We then describe the QoS mapping problem, and show how requirements for resources (such as the CPU, the network interface adaptor and network connections) can be automatically derived from the application QoS parameters. We then deal with the QoS enforcement issue in which we describe techniques for scheduling protocol processing threads …

Morphing Binary Trees, John Hershberger, Subhash Suri

All Computer Science and Engineering Research

We investigate the problem of transforming one binary tree into another by rotatoins, subject to certain weight ocnstraints on the nodes of the trees. These constraints arise in the problem of "morphing" one simple polygon to another simple polygon by continuous deformatinos (translations and scalings) that preserve the turn angles and the simplicity of the polygon; the two polygons must have the same sequence of turn angles. Our main theorem is that two arbitrary n-leaf binary trees satisfying our weight constraint can be morphed into each other with O(n log n) rotations. Furthermore, we also present an O(n log n) …

Distributed Data Layout, Scheduling And Playout Control In A Large Scale Multimedia Storage Server, Milind M. Buddhikot, Guru Parulkar

All Computer Science and Engineering Research

No abstract provided.

Boxgraph: A Two-Dimensional Visual Computation Model, Takayuki Dan Kimura, Timothy B. Brown

All Computer Science and Engineering Research

Traditional computation models such as Turing machines, lambda-calculus, Markov's normal algorithms, are not suitable models for visual programming languages because they are all based on one-dimensional text strings and visual programming uses two-dimensional graphic diagrams. We propose a two-dimensional computation model, called Boxgraph, that requires no text. The syntax of the model consists of nested boxes connected by arrows, and the semantics consists of dataflow and the concept of consistency. The expressive power of the model is demonstrated by constructing representations of a binary full adder, the Fibonacci function, and the GCD function. The model, with a small extension to …

Learning And Teaching Of Boolean And Geometric Classes, H. David Mathias

All Computer Science and Engineering Research

We consider the concept classes of DNF formulas and unions of discretized, axis-parallel d-dimensional boxes in discretized d-dimensional space with respect to several different learning models. In the model of learning with queries we present an algorithm to learn unions of boxes. We introduce a model of teaching that prevents illicit communication between the teacher and the leaner but that captures the intuitive aspect of teaching: a learner should perform at least as well with a cooperative teacher as with an adversarial teacher. We propose the study of teaching of DNF formulas and unions of boxes in this model. We …

Proposal For Research Distribution Of Gigabit Network Technology, Jonathan Turner

All Computer Science and Engineering Research

In 1993, APRA funded a major program at Washingotn University to create gigabit networking technology and create a gigabit testbed based on this technology. This program is now nearing the end of its first year and is making excellent proress towards its research and technical objectives. This note a proposes a program that would lead to the export of this technology to research groups in networking and gigabit applications with an interest in using it to further their own research activities.

Test 1679: John Deere 7200 Powerquad Diesel 16-Speed, Nebraska Tractor Test Lab

Nebraska Tractor Tests

EXPLANATION OF THE TEST PROCEDURE

General

Tractors are tested at the University of Nebraska according to the Agricultural Tractor Test Code approved by the American Society of Agricultural Engineers and the Society of Automotive Engineers or official Nebraska test procedure.

The manufacturer selects the tractor to be tested and certifies that it is a stock model. Each tractor is equipped with the common power consuming accessories such as power steering, power lift pump, generator, etc., if available. Power consuming accessories may be disconnected only when the means for disconnecting can be reached from the operating station. An official representative of …

Test 1683: Agco Allis 9670 Diesel 18-Speed, Nebraska Tractor Test Lab

Nebraska Tractor Tests

EXPLANATION OF THE TEST PROCEDURE

General

Tractors are tested at the University of Nebraska according to the Agricultural Tractor Test Code approved by the American Society of Agricultural Engineers and the Society of Automotive Engineers or official Nebraska test procedure.

The manufacturer selects the tractor to be tested and certifies that it is a stock model. Each tractor is equipped with the common power consuming accessories such as power steering, power lift pump, generator, etc., if available. Power consuming accessories may be disconnected only when the means for disconnecting can be reached from the operating station. An official representative of …

Test 1674: Agco-Allis 9630 Diesel 18-Speed, Nebraska Tractor Test Lab

Nebraska Tractor Tests

EXPLANATION OF THE TEST PROCEDURE General Tractors are tested at the University of Nebraska according to the Agricultural Tractor Test Code approved by the American Society of Agricultural Engineers and the Society of Automotive Engineers or official Nebraska test procedure. The manufacturer selects the tractor to be tested and certifies that it is a stock model. Each tractor is equipped with the common power consuming accessories such as power steering, power lift pump, generator, etc., if available. Power consuming accessories may be disconnected only when the means for disconnecting can be reached from the operating station. An official representative of …

Test 1676: White 6125 Diesel 18-Speed, Nebraska Tractor Test Lab

Nebraska Tractor Tests

EXPLANATION OF THE TEST PROCEDURE General Tractors are tested at the University of Nebraska according to the Agricultural Tractor Test Code approved by the American Society of Agricultural Engineers and the Society of Automotive Engineers or official Nebraska test procedure. The manufacturer selects the tractor to be tested and certifies that it is a stock model. Each tractor is equipped with the common power consuming accessories such as power steering, power lift pump, generator, etc., if available. Power consuming accessories may be disconnected only when the means for disconnecting can be reached from the operating station. An official representative of …

Test 1680: John Deere 7400 Syncroplus Diesel 12-Speed, Nebraska Tractor Test Lab

Nebraska Tractor Tests

EXPLANATION OF THE TEST PROCEDURE

General

Tractors are tested at the University of Nebraska according to the Agricultural Tractor Test Code approved by the American Society of Agricultural Engineers and the Society of Automotive Engineers or official Nebraska test procedure.

The manufacturer selects the tractor to be tested and certifies that it is a stock model. Each tractor is equipped with the common power consuming accessories such as power steering, power lift pump, generator, etc., if available. Power consuming accessories may be disconnected only when the means for disconnecting can be reached from the operating station. An official representative of …

Test 1675: Agco Allis 9650 Diesel 18-Speed, Nebraska Tractor Test Lab

Nebraska Tractor Tests

EXPLANATION OF THE TEST PROCEDURE General Tractors are tested at the University of Nebraska according to the Agricultural Tractor Test Code approved by the American Society of Agricultural Engineers and the Society of Automotive Engineers or official Nebraska test procedure. The manufacturer selects the tractor to be tested and certifies that it is a stock model. Each tractor is equipped with the common power consuming accessories such as power steering, power lift pump, generator, etc., if available. Power consuming accessories may be disconnected only when the means for disconnecting can be reached from the operating station. An official representative of …

Test 1681: John Deere 7400 Powrquad Diesel 16-Speed, Nebraska Tractor Test Lab

Nebraska Tractor Tests

EXPLANATION OF THE TEST PROCEDURE

General

Tractors are tested at the University of Nebraska according to the Agricultural Tractor Test Code approved by the American Society of Agricultural Engineers and the Society of Automotive Engineers or official Nebraska test procedure.

The manufacturer selects the tractor to be tested and certifies that it is a stock model. Each tractor is equipped with the common power consuming accessories such as power steering, power lift pump, generator, etc., if available. Power consuming accessories may be disconnected only when the means for disconnecting can be reached from the operating station. An official representative of …

Test 1684: Agco Allis 9690 Diesel 18-Speed, Nebraska Tractor Test Lab

Nebraska Tractor Tests

EXPLANATION OF THE TEST PROCEDURE

General

Tractors are tested at the University of Nebraska according to the Agricultural Tractor Test Code approved by the American Society of Agricultural Engineers and the Society of Automotive Engineers or official Nebraska test procedure.

The manufacturer selects the tractor to be tested and certifies that it is a stock model. Each tractor is equipped with the common power consuming accessories such as power steering, power lift pump, generator, etc., if available. Power consuming accessories may be disconnected only when the means for disconnecting can be reached from the operating station. An official representative of …

Test 1685: White 6175 Diesel 18-Speed, Nebraska Tractor Test Lab

Nebraska Tractor Tests

EXPLANATION OF THE TEST PROCEDURE

General

Tractors are tested at the University of Nebraska according to the Agricultural Tractor Test Code approved by the American Society of Agricultural Engineers and the Society of Automotive Engineers or official Nebraska test procedure.

The manufacturer selects the tractor to be tested and certifies that it is a stock model. Each tractor is equipped with the common power consuming accessories such as power steering, power lift pump, generator, etc., if available. Power consuming accessories may be disconnected only when the means for disconnecting can be reached from the operating station. An official representative of …