Engineering Commons^™

On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy

Computer Science: Faculty Publications and Other Works

We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.

Efficient Accommodation Of May-Alias Information In Ssa Form, Ron Cytron, Reid Gershbein

All Computer Science and Engineering Research

We present an algorithm for incrementally including may-alias information into Static Single Assignment form by computing a sequence of increasingly precise (and correspondingly larger) partial SSA forms. Our experiments show significant speedup of our method over exhaustive use of may-alias information, as optimization problems converge well before most may-aliases are needed.

Exact Dominance Without Search In Decision Trees, Nilesh L. Jain, Ronald P. Loui

All Computer Science and Engineering Research

In order to improve understanding of how planning and decision analysis relate, we propose a hybrid model containing concepts from both. This model is comparable to [Hartman90], with slightly more detail. Dominance is simple concept in decision theory. In a restricted version of our model, we give conditions under which dominance can be detected without search: that is, it can be used as a pruning strategy to avoid growing large trees. This investigation follows the lead of [Wellman87]. The conditions seem hard to meet, but may nevertheless be useful in forward-chaining situations without focus, such as [Breese87]. It may be …

The Programmers' Playground: I/O Abstraction For Heterogeneous Distributed Systems, Kenneth J. Goldman, Michael D. Anderson

All Computer Science and Engineering Research

A new high-level approach to interprocess communication in heterogeneous distributed systems in introduced, This approach, called I/O Abstraction, allows one to write each functional component of a distributed system as an encapsulated program that acts upon a set of local data structures, some of which may be published for external use. The functional components are separately configured by establishing logical connections among the published data structures. In order to illustrate this approach, we describe the The Programmers' Playground, a high-level language "veneer" and protocol designed to support I/O abstraction in heterogeneous computing environment. Support for communication among programs written in …

Computing Specificity, Ronald Loui, J. Norman, K. Stiefvater, A. Merrill, A. Costello, J. Olson

All Computer Science and Engineering Research

This note reports on an effort to implement a version of Poole's rule for specificity. Relatively, efficient implementation relies on correcting and improving a pruning lemma of Simari-Loui [92]. This in turn requires revision of Poole's specificity concept. The resulting system is a usable knowledge representation system with first-order-language and defeasible reasoning. Sample input and output are included in an appendix. It is a good candidate for multiple inheritance applications; it is useful for planning, but limited by the underlying search for plans.

Packet Routing In Networks With Long Wires, Ronald I. Greenberg, H.-C. Oh

Computer Science: Faculty Publications and Other Works

In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of “congestion” and “dilation” measures for a set of packet paths. We give, for any constant ε > 0, a randomized on-line algorithm for routing any set of N packets in O((Clg^ε(Nd)+Dlg(Nd))/lglg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into account, and d is the longest path in terms of number of wires. We also …

Process And Policy: Resource-Bounded Non-Demonstrative Reasoning, Ronald P. Loui

All Computer Science and Engineering Research

This paper investigates the appropriateness of formal dialectics as a basis for non-monotonic and defeasible reasoning that takes computational limits seriously. Rules that can come into conflict should be regarded as policies, which are inputs to deliberative processes. Dialectical protocols are appropriate for such deliberations when resources are bounded and search is serial. AI, it is claimed here, is now perfectly positioned to correct many misconceptions about reasoning that have resulted from mathematical logic's enormous success in this century: among them (1) that all reasons are demonstrative, (2) that rational belief is constrained, not constructed, (3) that process and disputation …

Separating Structure From Function In The Specification And Design Of Distributed Systems, Kenneth J. Goldman

All Computer Science and Engineering Research

A distributed system is viewed as a collection of functional components and a unifying structure that defines relationships among the components. In the paper, we advocate a particular approach to distributed system specification and design in which the structure of a distributed system is specified separately from the functional components. This permits one to reason about individual functional components in isolation, and encourages one to make explicit not only the input/output behavior of the functional components but also the logical placement of these components within the overall structure of the system. We describe a new software tool for the specification, …

Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley

Computer Science: Faculty Publications and Other Works

We present a linear-time algorithm for determining the minimum height of a single-layer routing channel. The algorithm handles single-sided connections and multiterminal nets. It yields a simple routability test for single-layer switchboxes, correcting an error in the literature.

Dna Mapping Algorithms: Strategies For Single Restriction Enzyme And Multiple Restriction Enzyme Mapping, Will Gillett

All Computer Science and Engineering Research

An approach to high-resolution restriction-fragment DNA mapping, known as Multiple-Restriction-Enzyme mapping (MRE mapping), is present. This approach significantly reduces the uncertainty of clone placement by using clone ends to synchronize the position in of clones within different maps, each map being constructed from fragment-length data produced by digestion of each clone with a specific restriction enzyme. Maps containing both fragments-length data and clone-end data are maintained for each restriction enzyme, and synchronization between two such maps is achieved by requiring them to have "compatible" clone-end map projections. Basic definitions of different kinds of maps, such as restriction sites maps, restriction …

Can Pac Learning Algorithms Tolerate Random Attribute Noise?, Sally A. Goldman, Robert H. Sloane

All Computer Science and Engineering Research

This paper studies the robustness of pac learning algorithms when the instances space is {0,1}n, and the examples are corrupted by purely random noise affecting only the instances (and not the labels). In the past, conflicting results on this subject have been obtained -- the "best agreement" rule can only tolerate small amounts of noise, yet in some cases large amounts of noise can be tolerated. We show that the truth lies somewhere in between these two alternatives. For uniform attribute noise, in which each attribute is flipped independently at random with the same probability, we present an algorithm that …

Neural Modeling And Control Of A Distillation Column, James Edward Steck, K. Krishnamurthy, Bruce M. Mcmillin, Gary G. Leininger

Mechanical and Aerospace Engineering Faculty Research & Creative Works

Control of a nine-stage three-component distillation column is considered. The control objective is achieved using a neural estimator and a neural controller. The neural estimator is trained to represent the chemical process accurately, and the neural controller is trained to give an input to the chemical process which will yield the desired output. Training of both the neural networks is accomplished using a recursive least squares training algorithm implemented on an Intel iPSC/2 multicomputer (hypercube). Simulated results are presented for a numerical example.

The 3-Tier Structured Access Protocol To Control Unfairness In Dqdb Mans, Lakshmana N. Kumar, Andreas D. Bovopoulos

All Computer Science and Engineering Research

This paper addresses the unfairness problem appearing in 802.6-based DQDB MANs. Traffic load demand is characterized as low (below 0.4 of the channel capacity), normal (from 0.4 to 0.9 of the channel capacity) or heavy (greater than 0.9 of the channel capacity). At low loads the 802.6 protocol is acceptably fair. At normal loads, however, the protocol performance is markedly unfair. The unfairness is related to the latency in transporting a request. At heavy loads the unfairness is both latency-related and flooding-related. In this paper, both types of unfairness are carefully analyzed. As a control measure, a 3-Tier Structured Access …

Deterministic Approximations To Co-Production Problems With Service Constraints And Random Yields, Gabriel R. Bitran, Thin Yin Leong

Research Collection School Of Computing and Information Systems

Production planning problems where multiple item categories are produced simultaneously are examined. The items have random yields and are used to satisfy the demands of many products. These products have specification requirements that overlap. An item originally targeted to satisfy the demand of one product may be used to satisfy the demand of other products when it conforms to their specifications. Customers' demand must be satisfied from inventory. The problem is formulated with service constraints and a near-optimal solution is provided to the problem with a fixed planning horizon. Simple heuristics are proposed for the problem solved with a rolling …

Finding A Maximum-Density Planar Subset Of A Set Of Nets In A Channel, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We present efficient algorithms to find a maximum-density planar subset of n 2-pin nets in a channel. The simplest approach is to make repeated usage of Supowit's dynamic programming algorithm for finding a maximum-size planar subset, which leads to O(n^3) time to find a maximum-density planar subset. But we also provide an algorithm whose running time is dependent on other problem parameters and is often more efficient. A simple bound on the running time of this algorithm is O(nlgn+n(t+1)w), where t is the number of two-sided nets, and w is the number of nets in the output. Though the worst-case …

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

Energy-Related Feature Abstraction For Handwritten Digit Recognition, Thomas H. Fuller Jr.

All Computer Science and Engineering Research

Most handwritten character recognizers use either graphical (static) or first-order dynamic data. Our research speculates that the mental signal to write a digit might be partially encoded as an energy profile. We used artificial neural networks (ANN) to analyze energy-related features (first and second time derivatives) of handwritten digits of 20 subjects and later 40 subjects. An experimenal environment was developed on a NeXTstation with a real-time link to a pen-based GO computer. Although such an experiment cannot confirm an energy profile encoded in the writer, it did indicate the usefulness of energy-related features by recognizing 94.5% of the 600 …

Composite Stock Cutting Through Simulated Annealing, Hanan Lutfiyya, Bruce M. Mcmillin, Pipatpong Poshyanonda, Cihan H. Dagli

Computer Science Faculty Research & Creative Works

This paper explores the use of Simulated Annealing as an optimization technique for the problem of Composite Material Stock Cutting. The shapes are not constrained to be convex polygons or even regular shapes. However, due to the composite nature of the material, the orientation of the shapes on the stock is restricted. For placements of various shapes, we show how to determine a cost function, annealing parameters and performance. © 1992.

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: 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 The Chorus Supervisor And Related Low-Level Functions To The Pa-Risc, 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.

The Supervisor is the name given by Chorus to a collection of low-level functions that are machine dependent and have to be implemented when Chorus is ported from one machine to another. The Supervisor is responsible for interrupt, trap and exception handling, managing low-level thread initialization, context switch, kernel initialization, managing simple devices (timer and console) and offering a low-level debugger. This document describes the port of the Supervisor and related low-level functions. …

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

Computer Science Faculty Publications and Presentations

We started out with the low level Tut (HP-CX 2.0) boot code. One of our goals was to reuse as much of this code as possible, which would reduce the amount of low level code we would have to debug. This was very important, especially fiince the RP 9000/834 has a very complex I/O architecture and we lacked any sophisticated debugging tools. Writing the PA-Chorus boot code involved modifying the Tut code to match the Chorus startup sequence. In the remainder of this section, we present an overview of the PA-RISC boot mechanisms and the Chorus startup sequence. Sectlon 2 …

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, • …