Technical Reports and MS Project Reports

The arguments against centralized solutions focus on the performance bottleneck associated with a single central uniprocessor having a limited throughput and, possibly, a small number of ports. These limitations can be overcome to some extent if the central processor is replaced by a modern SIMD (Single Instruction Multiple Data) machine. Several orders of magnitude gains in parallelism are thus achievable while maintaining the logical simplicity of a centralized control. We call such a scheme parallel synchronous control (PSC). In this paper, we explore this approach by presenting a PSC solution ...Read More

Synchrony continues to be an important concern in concurrent programming. Existing languages and models have introduced a great variety of constructs for expressing and managing synchronization among sequential processes or atomic actions. This paper puts forth a model in which synchrony is viewed as a relation among atomic actions, a relation which may evolve with time. The model is shown to be convenient for expressing formally the semantics of synchrony as it appears in many of the languages and models proposed to date. Among such models Swarm is singled out ...Read More

This paper describes the design of the Axon host-network interface architecture, and performance factors determining its design. The Axon project is investigating an integrated design of the host architecture, operating systems, and communications protocols to allow applications to utilise the high bandwidth provided by the next generation of communications networks. The Axon host architecture and network interface is designed to provide a path directly between the network interface with direct access to host memory, capable of delivering bandwidth in excess of 1 Gbps to applications. This provide the ability to ...Read More

ATM switching systems are required to maintain ordering for cells within a given virtual circuit. This is most commonly achieved using a switching system in which cells in a given virtual circuit are routed along a common path through the switching system. This solution has the drawback that it can lead to significant virtual circuit blocking unless the switching network is engineered with a large speed advantage, relative to the external links. Switching systems in which cells are routed independently, on the other hand, can balance the load dynamically and ...Read More

This paper describes several improvements to Lee's multicast switch architecture. Our improvements make Lee's architecture practical, allowing it to achieve maximum network throughput under worst-case conditions and drastically reducing the amount of memory required for addressing of multicast cells. These improvements allow multicast to be added to a 256 port switch with 150 Mb/s links at a cost of about two additional chips per port.

Genetic Algorithms have been gaining much interest since the early 1970's and have intrigued people from the fields of machine learning, artificial intelligence, neural networks and operations research. This paper describes the approach of genetic algorithms applied to neural networks. The experiments were conducted using various functions such as XOR,AND,SINE and different network sizes. Based on the experimental data, we concluded that for small network architectures represented by the functions (SINE,ENCODE,etc), genetic algorithms were not effective and the desired results were not achieved within a reasonable period of time.

There have been a number of ATM switching system architectures proposed, but little in the way of comparison to indicate which architectures are preferable from a cost standpoint given specific performance requirements. This paper considers a range of performance requirements and compares various architectures base don the number of pin-limited chips needed to realize a system which can meet the requirements. Our results indicate that certain architectures, for example the Knockout network, are not competitive within the range we considered. Other architectures perform reasonably well in some cases, but less ...Read More

Several current DNA mapping projects are based on detection of overlaps between cloned DNA molecules. This thesis places the problem of overlap detection in a probabilistic framework by deriving, for each of the relevant overlap types, expressions for the probability that a postulated overlap is correct. In addition, computationally feasible approximations for the probability expressions are developed. These expressions have been implemented and, using the implementations, the validity of both the original and the approximated probability expressions is verified.

This technical report describes preliminary research investigating the relationship between information theory and Bayes' theory for estimation of the probability of clone overlap for the use in DNA restriction mapping. A number of languages (along with information theoretic metrics) capable of describing a hypothesized overlap are presented. For each language, the MML criterion is applied to the encoded overlaps of a pair of clones to search for that overlap which is most probable. The objective is to order the pair's encoded overlaps, based on the MML criterion, from the most ...Read More

In this paper the functionality requirements of a user-network interface for bandwidth allocation are discussed. Such requirements include the capability to provide end users with a variety of non-deteriorating connection types. In addition effective policy enforcement and traffic shaping mechanisms are required to facilitate network management and the efficient utilization of network resources. Based on these requirements, a user-network interface model is proposed, and its performance is studied. Its intrinsic properties are revealed for two cases, a Poisson source and a bursty source.

Troubleshooting measurement equipment can be complex and time consuming task. We developed a system that incorporates model-based diagnosis to troubleshoot measurement instrumentation systems. It consists of a knowledge representation scheme for modeling the structure and behavior of measurement systems and the ability to reason from first principles about these models. It accepts observed values from the user and returns a list of components that are suspected of failing. The current system was developed using the object oriented approach and was designed to be reusable for a variety of measurement systems. ...Read More

Visualization is defined as the transformation of information into a graphical form. In recent years, visualization has increasingly been used in a variety of applications. Our work focuses on the visualization of concurrent computations. We wish to collect information about the operational behavior of concurrent computations. We wish to collect information into a graphical representation, and display the resulting image.

This paper describes the underlying model for a visualization environment concerned with exploring, monitoring, and presenting concurrent computations. The model is declarative in the sense that visualization is treated as the composition of several mappings which, as a whole, map computational states into full-color images of a 3-D geometric world. The mappings defining the visualizations are specified using a rule-based notation. The visualization methodology is proof-based, i.e., it captures abstract formal properties of programs (e.g. safety and progress) rather than operational details. An algorithm for termination detection in diffusing computations ...Read More

We have implemented a Prolog execution engine for the shared-database language Swarm extended with visualization capabilities. We call this execution engine SwarmExec. SwarmExec runs on a Macintosh Iifx under Advanced A.I. Systems' Prolog (AAIS) and communicates over an Ethernet connection with a Silicon Graphics Personal Iris which serves as a graphical engine and renders the visualizations. This paper describes the major design elements of SwarmExec. A basic familiarity with Swarm and its visualization extensions is assumed; the interested reader is referred to the referenced papers.

The term shared dataspace refers to the general class of programming languages in which the principal means of communication among the concurrent components of programs is a common, content-addressable data structure called a dataspace. In the programming language and artificial intelligence communities, there is considerable interest in such languages, e.g. logic-based languages, production rule systems, and the Linda language. However, these languages have not been the subject of extensive program verification research. This paper specifies a proof system for a shared dataspace programming notation called Swarm-- a program logic similar ...Read More

This document summarizes usage and activities associated with the NCUBE computer system. The system is located within the Computer and Communications Research Center on the 3rd floor of Bryan Hall, School of Engineering and Applied Science, Washington University, St. Louis, Missouri. We begin with a brief review of the machine's hardware characteristics and then proceed to reviewing user activities.

In this paper z-transform theory is used to develop the discrete orthonormal wavelet transform for multidimensional signals. The tone is tutorial and expository. Some rudimentary knowledge of z-transforms and vector spaces is assumed. The wavelet transform of a signal consists of a sequence of inner products of a signal computed against the elements of a complete orthonormal set of basis vectors. the signal is recovered as a weighted sum of a basis vectors. This paper addresses the necessary and sufficient conditions that such a basis must respect. An algorithm for ...Read More

This paper describes the modification made to the design of the Broadcast Translation Circuit based on test results from the first fabrication run. The document updates WUCS-89-52, which outlines the design of the BTC in full detail.

This paper describes the testing methodology for the Broadcast Translation Circuit. It covers logic simulation, timing simulation, and a single push-button test for the device. The document is intended to be a supplement to documents WUCS-89-52 and WUCS-90-19, which outline the design of the BTC in full details. The intent of a push-button test is to have a single test that causes the device to process every type of packets that it could receive. This would include various combination of RC and OP fields, a test that examines every table ...Read More

This report documents the intent and use of a suite of programs for simulating the production of DNA restriction fragment data, as might come from the biological laboratory doing work in DNA mapping. This suite includes programs for (a) creating a random strand of DNA, (b) creating random clones given a strand of DNA, (c) taking a clone and applying a restriction enzyme to create restriction fragments, and (d) creating a nucleotide map of how the clones relate to one another within the original DNA strand. Besides this fundamental software, ...Read More

We define the logically synchronous multicast problem, which imposes a natural and useful structure on message delivery order in an asynchronous system. In this problem, a computation proceeds by a sequence of multicasts, in which a process sends a message to some arbitrary subset of the processes, including itself. A logically synchronously multicast protocol must make it appear to every process as if each multicast occurs simultaneously at all participants of that multicast (sender plus receivers). Furthermore, if a process continually wishes to sends a message, it must eventually be ...Read More

The importance of scientific visualization for both science and engineering endeavors has been well recognized. Televisualization becomes necessary because of the physical distribution of data, computation resources, and users involved in the visualization process. However, televisualization poses a number of challenges to the designers of communication protocols. A pipelined televisualization (PTV) model is proposed for efficient implementation of a class of visualization applications. Central to the proposed research is the development of a segment of streaming IPC (interprocess communication) mechanism in support of efficient pipelining across very high speed internetworks. ...Read More

The problem of determining which events occur "between" two bounding events A and B in partially-ordered logical time is equivalent to being able to list, for a directed acyclic graph, the vertices on all paths with origin a and terminus b. We present four approaches to this problem, each progressively less memory-intensive. The two most promising of these approaches are examined in depth.

The problem of determining which events occur "between" two bounding events A and B in partially-ordered logical time is equivalent to being able to list, for a directed acyclic graph, the vertices on all paths with origin a and terminus b. Four approaches to this problem are presented, each exploiting more knowledge about this work's application domain and hence becoming progressively less memory intensive. The two most promising of these approaches are examined in depth.

A novel process algebra is presented; algebraic expressions specify delay-insensitive circuits in terms of voltage-level transitions on wires. The approach appears to have several advantages over traditional state-graph and production-rule based methods. The wealth of algebraic laws makes it possible to specify circuits concisely and facilitates the verification of designs. Individual components can be composed into circuits in which signals along internal wires are hidden from the environment.

The important feature of this work is the combination of minimizing a function with desirable properties, using the conjugate gradient method (cgm). The method has resulted in significant improvements for both easy and difficult training tasks. Two major problems slow the rate at which large back propagation neural networks (bpnns) can be taught. First is the linear convergence of gradient descent used by modified steepest descent method (msdm). Second is the abundance of saddle points which occur because of the minimization of the sum of squared errors. This work offers ...Read More

This paper describes the Psi-decomposition of a signal, in which the signal is written as a weighted sum of certain elementary synthesizing functions. The set S of synthesizing functions consists of dilated and translated versions of two parent functions, which are concentrated in both the time and frequency domains. The weighting constant in the Psi-decomposition define a transform called the Phi-transform. The Phi-Transform of a signal captures both the frequency content and the temporal evolution of a non stationary signal. The Phil-transform is linear, continuous, and continuously invertible. The set ...Read More

This report details research plans to extend work on hybrid deterministic parsing. The approach is hybrid in its combination of symbolic and sub-symbolic (connectionist) approaches. The research is investigating (1) new and more robust architectures for deterministic parsing which are hybrid mixtures of symbolic and sub-symbolic components, (2) combinations of syntax with lexical access and other components of natural language processing in order to determine how the distributed patterns of connectionism may enable better interfaces among these components, and (3) properties of the rules in the rule-based deterministic processing of ...Read More

In the last two decades, mathematical theories have been helping computer scientists see, in a fresh light, problems in the area of programming methodology and solve these problems more efficiently and reliably than before. In this series of seminars we demonstrate the application of mathematics in parallel languages and programming.

In this paper we present a mathematical model for CSP-like language. This model handles both safety and liveness properties of "purely parallel" CSP processes, as well as CSP processes with internal machine states. A refinement order is defined in this model which is a combination of the refinement order in CSP's failure model and the refinement order for sequential programs. Finally, related work and applications are discussed.

This paper presents an overview of the design and development of a real-time (30 frames/sec) simulation testbed for evaluating and comparing image compression algorithms. The system was motivated by the need to visualize the performance of a novel compression algorithm when operating on moving pictures originating from "live" video sources. The simulation utilities are designed to exploit the parallelism of a Pixar Image Computer and high-throughput of a parallel disk assembly. The design of two key utilities are discussed: (1) A program to format precomputed four channel (RGBA) 256 X ...Read More

This paper describes a novel method of character recognition targeted for extracting complex annotations found in engineering documents. The results of this work will make it possible to capture the information contained in documents used to support facilities management and manufacturing. The recognition problem is made difficult in part because characters and text may be expressed in arbitrary fonts and orientations. Our approach includes a novel incremental strategy based on the multi-scale representation of wavelet decompositions. Our approach is motivated by biological mechanisms of the human visual systems. Using wavelets ...Read More

Previous matching algorithms have achieved high speeds through algorithm simplification and/or relied on custom hardware. The objective of our work has been the development a robust high-speed stereo matcher by exploiting parallel algorithms executing on general purpose SIMD machines. Our approach is based on several existing techniques dealing with the classification and evaluation of matches, the application of ordering constraints, and relaxation-based matching. The techniques have been integrated and reformulated in terms of parallel execution on the theoretical SIMD machine. Feasibility is demonstrated by implementation on a commercially available SIMD ...Read More

A workshop on defeasible reasoning with specificity was held in under the Arch in St. Louis during April 1989, with support fro AAAI and McDonnell Douglas, and the assistance of Rockwell Science Center Palo Alto and the Department of Computer Science of Washington University. The document includes a report on the proceedings and parts of the workshop notes that can be distributed. These include the schedule, lists of participants, synopses of systems, and benchmark problems.

This project provides a good case study of expert system development with untrained experts over a short period of time. We describe the development of a working medical screening and diagnosis expert system for use at the Women, Infants and Children (WIC) clinics in Madison County, Illinois. The system was designed and implemented over the period of four months. A large number of knowledge acquisition techniques were employed, some of them customized in ways that greatly increased their effectiveness. This paper explores the development of THE WIC Advisor, from problem ...Read More

A high-level area model of Benes and crossbar networks in a VLSI environment is presented. The areas of both networks are then compared for different design parameters. The results are also compared to those obtained by Franklin [Fr81] for banyan and crossbar networks. The geometric chip layout employs two metal layers for the interconnection paths. It is show that both Benes and crossbar grow in area as O(N)2, where N is the network size.

Quadratic energy minimization is the essence of certain connectionist models. We define high order connectionist models to support the minimization of high order energy functions and we prove that high order energy functions are equivalent to quadratic ones. We show that the standard quadratic models can minimize high order functions using additional hidden units and we demonstrate trade-offs of size (number of hidden units), order of the model, and fan-out. We prove an equivalence between the problem of satisfiability in propositional calculus and the problem of minimization of energy functions. ...Read More

The arguments against centralized solutions focus on the performance bottleneck associated with a single central uniprocessor having a limited throughput and, possibly, a small number of ports. These limitations can be overcome to a large extent if the central processor is replaced by a modem SIMD (Single Instruction Multiple Data) machine. Several order of magnitude gains in parallelism are thus achievable while maintaining the logical simplicity of a centralized control. We call such a scheme parallel synchronous control (PSC). In this paper, we explore this approach by presenting a PSC ...Read More

The Advanced Micro Devices TAXI chip set was chosen as the serial interface for the Fast Packet Switch. In order to fully understand the operation of the chip set, and in order to fully characterize the chip set's operation, several tests were performed using actual TAXI components. These tests included TAXI-to-TAXI tests and tests with optical data links. The operation of the asynchronous transmitter handshake was also investigated in detail. The results of these tests indicate that the TAXI chip set is well built and very reliable.

Technical reviews are an integral part of the software development process for any company concerned with software quality. This paper is neither a survey nor a comparative study of existing approaches but an attempt to reexamine the technical review process from a new perspective, the corporate culture. It is the contention of this paper that technically sound methods are effective only in a climate where (1) reviews are an integral part of the local culture and (2) there is no clear understanding of the kinds of technical and organizational needs ...Read More

The term shared dataspace refers to the general class of models and languages in which the principal means of communication is a common, content-addressable data structure called a dataspace. Swarm is a simple language we have used as a vehicle for the investigation of the shared dataspace approach to concurrent computation. It is the first shared dataspace language to have an associated assertional-style proof system. An important feature of Swarm is its ability to bring a variety of programming paradigms under a single, unified model. In a series of related ...Read More

Swarm is a computational model which extends UNITY in three important ways: (1) UNITY's fixed set of variables is replaced by an unbounded set of tuples which are addressed by content rather than by name; (2) UNITY's static set of statements is replaced by a dynamic set of transactions; and (3) UNITY's static II-composition is augmented by dynamic coupling of transactions into synchronic groups. This paper overviews the Swarm model, introduced the synchronic group concept, and illustrates their use in the expression of dynamically structured programs. A UNITY-style programming logic ...Read More

This paper describes the Axon host-network interface architecture. The Axon project is investigating an integrated design of host architecture, operating systems, and communications protocols to allow applications to utilize the high bandwidth provided by the next generation of communications networks. The Axon host architecture and network interface is designed to provide a high bandwidth low latency path directly between the network and host memory. A pipelined communications processor (CMP) serves as a network interface with direct access to host memory, capable of delivering bandwidth in excess of 1 Gbps to ...Read More

This paper provides a method of analyzing the queueing behavior of switching networks constructed from switches that employ shared buffering or parallel bypass input buffering. It extends that queuing models first introduced by Jenq and later generalized by Szymanski and Shaikh to handle these classes of networks. Our analysis explicitly models the state of an entire switch and infers information about the distribution of packets associated with particular inputs or outputs when needed. Earlier analyses of networks constructed from switches using input buffering attempt to infer the state of a ...Read More

Asynchronous Transfer Mode (ATM) has been expected to be the basis for the next generation communication networks. The point of queuing analysis for ATM networks is to evaluate the behavior of bursty traffic. Periodicity of the traffic is another significant characteristic of some applications, and is difficult to treat by means of evaluating the queuing theories. This report describes between arriving and departing traffic. The results obtained by this method include packet loss rate and queue length distribution. And it is shown that periodic bursty traffic has, in general, moderate ...Read More

This paper describes the design of the PP3 packet processor chip. PP3 is one of the four component chips in a packet processor used in the high speed broadcast packet switching network [Tu88]. Together with the other three component chips, PP3 provides the interface between the fiber optic links and the switch fabric. PP3 in currently being fabricated in 2 μm CMOS technology.

The performance of a network subject to either state dependent or state independent flow control is investigated. In the state dependent case, the flow control policy is a function of the total number of packets for which the controller has not yet received an acknowledgment. In this case it is shown that the optimal flow control is a sliding window mechanism. The effect of the delayed feedback on the network performance as well as the size of the window are studied. The state independent optimal rate is also derived. The ...Read More

We investigate the dynamical behavior of a decentralized network that is shared by users, each trying to achieve its own objectives.