Technical Reports and MS Project Reports

Over the last few years, a number of research groups have made considerable progress on the design of high speed networks- on the order of a few hundred Mbps to the few Gbps. The emphasis of this work has been on the design of packet switches and on the design of network access protocols. However, this work has not yet addressed the internetworking and transport level issues in the high speed internet. As part of our effort on the design of VHSI model, we considered the appropriateness of recently proposed ...Read More

Lsim2 is gate/switch-level digital logic simulator. It enables users to model digital circuits both at the gate and switch level and incorporates features the support investigation of the simulation task itself. Lsim2 is an augmented version of the original lsim* with the addition of several new MSI-type components models. This user's manual describes procedures for specifying a circuit in lsim2, mechanisms for controlling the simulation, and approaches to modeling systems.

Since the paper by Kirkpatrick, Gelatt and Vecchi in 1983, the use of Simulated Annealing (SA) in solving combinatoric optimization problems has increased substantially. The SA algorithm has been applied to difficult problems in the difficult problems in the digital design automation such as cell placement and wire routing. While these studies have yielded good or near optimum solutions, they have required very long computer execution times (hours and days). These long times, coupled with the recent availability of the number of commercial parallel processors, has prompted the search for ...Read More

This paper presents model of hierarchical discrete-event simulation algorithm running on a hypercube architecture. We assume a static allocation of system components to processors in the hypercube. We also assume a global clock algorithm, with an event-based time increment. Following development of the performance model, we describe an application of the model in the area of digital systems simulation. Hierarchical levels included are gate level (NAND, NOR, and NOT gates) and MSI level (multiplexors, shift registers, etc.). Example values (gathered from simulations running on standard von Neumann architectures) are provided ...Read More

This paper presents a method for automatically generating user interfaces to programs. All possible legal strings of input to a moderately interactive program, taken together, specify the input language of that program. A grammar for such a language is fundamentally knowledge about the language, and that knowledge can be used to assist the program's user in constructing legal program input. The set of words which can appear next in an input sentence, the 'Next set', is defined and a technique for calculating it with a modified version of Prologs's Definite ...Read More

This report describes an object-oriented tool that has been developed for viewing graphs on a Macintosh II computer using Allegro Common Lisp. The tool is useful for visualizing data which can be represented in tree or graph form. The graphs can be viewed for far away to get a global view, and from close up so that the labels on the vertices can be discerned. Scrolling can be performed at a nearly infinite number of resolutions, and a search feature makes it easy to find any node rapidly. Although the ...Read More

We present the design of a transaction system which supports tuple-oriented database operations in the concurrent environment. An implementation of this system for the NCUBE Corporation NCUBE-7 hypercube processor is described. The implementation includes both the basic kernel to support the database operations and two software packages to assist users of the system.

This manual describes how to use the CTIX Message System for interprocess communication in a distributed application program. The CTIX Message System is a package of message-passing facilities developed by the Concurrent Systems Group of the Department of Computer Science at Washington University, It provides a process-to-process asynchronous, buffered communication medium. The package is implemented on a network of Convergent Technologies (CT) MiniFrame workstations. These workstations support the CTIX (the Ct's version of UNIX System V) operating system and the TCP/IP network protocols.

Simulation needs for design analysis, verification, and testing have become increasingly important as integrated circuit size and complexity have grown. One technique for dealing with this problem is to utilize hierarchical modeling and simulation methods. This paper presents an analysis of hierarchical simulation systems in terms of two performance measures; the number of statements required for describing a system, and the simulation system execution time associated with a given hierarchical system representation. A model of hierarchical simulation system performance is developed. The performance of the hierarchical simulator, lsim2, is examined ...Read More

Once the BEMAS [13] system was completed and recorded in Common Lisp, research efforts were channeled toward three primary areas. This report will present a briefly review of some research in these areas, which are: parallelizing truth maintenance systems, parallelizing production systems, and parallel search. The area of parallel search has been studied by many over the past years and we will only present current research that has been accomplished. This review represents the beginning research into the development of a parallel inference model.

This paper is a user's manual for BEMAS, a BE lief MA intenance System. BEMAS is a menu driven system which provides an easy to use interface between a user and a knowledge base. Given a set of data, and a set of rules, BEMAS will help the user to identify an object by analyzing the properties of that object. Data can be added and deleted at any time, either directly or by deleting beliefs on which the data is dependent. BEMAS maintains the relations and dependencies between data using ...Read More

We propose to measure the memory capacity of a state machine by the numbers of discernible states, where two states are defined to be discernible if the machine manifests the identical input-output mapping in both states. According to the definition, a neuron network of n>0 inputs and one output, with an uncountable set of internal states, has the memory capacity of log2TF(n), where TF(n) is the number of different Boolean functions the network can realize with different synaptic weight and threshold values. It is shown that such a network with ...Read More

In this paper we present the database applications of the Show and Tell Language (STL) and demonstrate the relational completeness of the language. STL is a visual programming language designed for novice computer users who are not familiar with keyboarding. A program can be constructed by using only a pointing device, except for textual data entry. A program can be constructed by using only a pointing device, except for textual data entry. Various programming concepts such as subroutine, iteration, recursion, concurrency, exception, and so forth are represented by two-dimensional graphic ...Read More

The Determinism Hypothesis (Marcus, 1980) has given rise to much debate. The hypothesis makes explicit the idea that Natural Language interpretation need not depend in any fundamental way on the use of pseudo-parallelism or backtracking. We are exploring the consequences of this hypothesis in attempting to develop approaches to parsing which integrates current work in parallel distributed adaptive networks. We follow the basic approach of "Wait-and-See" parsing (WASP) which has shown the Natural Language interpretation of all but some varieties of "garden-path" sentences can be deterministically performed using a stack, ...Read More

This report describes the design of a Clock Generator Chip. The purpose of this chip is to generate a non-overlapping three-phrase clock from single 50% duty-cycle clock. The design includes combinational logic, VLSI layout, and logic and timing simulations.

An extension of classical theory of connection networks is defined and studied. This extension models systems in which multiple connections of differing data rates share the links within a network. We determine conditions under which the Clos and Cantor networks are strictly nonblocking for multirate traffic. We also determine conditions under which the Benes Network and variants of the Cantor and Clos networks are rearrangeable. We find that strictly nonblocking operation can be obtained for multirate traffic with essentially the same complexity as in the classical context.

Noahnet is an experimental flood local area network with features such as high reliability and high performance. Noahnet uses a randomly connected graph topology with four to five interconnections per node and a flooding protocol to route messages. In Noahnet flooding, the routing of a message from a source to the destination node is a two step process: flooding-growth and flooding-contraction. During the growth of flooding, the message propagates to every node which is not occupied with a message and is reachable from the source node. During the contraction of ...Read More

This paper is a first attempt at formulating a framework for high speed communication in an environment comprising a mix of subnetworks with widely varying characteristics. It is motivated in part by recent work on high speed packet switching and in part by work on interworking of computer networks. The work on high speed packet switching is expected to lead to the development of large public networks capable of supporting applications ranging form low speed data to voice, high speed data and video. If such networks are to realize their ...Read More

This report addresses the problem of constructing DNA restriction maps from random-close data produced by cutting the whole DNA structure with restriction enzyme and measuring possibly overlapping segments. Our approach to DNA mapping is based on the overlapping segments that occur between adjacent clones. The shortest common superstring problem (SCS) and the shortest common matching string problem (SCMS) are discussed as abstract computational models of DNA mapping. Since these string problems are NP-complete, we need efficient approximation algorithms to avoid excessive computational complexity. Some greedy algorithms to SCMS are presented ...Read More

This paper is concerned with the use of program visualization as a means for the understanding, debugging, and monitoring of large-scale concurrent programs. Following an overview of the shared dataspace paradigm and the declarative approach to visualization, the paper discusses: (1) mechanisms for specifying declarative visualization in the shared dataspace paradigm and ways of relating the specifications to program verification; (2) a computational model which provides a unified framework for comparing both visual and nonvisual algorithms; and (3) strategies for implementing declarative visualization on parallel machines.

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. This paper reports on progress we have made toward the development of prototype implementation of a shared dataspace language, Swarm, on a hypercube multiprocessor. The paper includes an informal overview of the Swarm language, describes the design organization of a transaction processing system which forms the kernels of a Swam implementation, and explains the algorithms implementing a subset of Swarm embedded ...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. This paper reports on the progress we have made toward the development of a formal operational model for Swarm and a few of the language and programming implications of the model. The paper has four parts: an overview of ...Read More

Our ultimate goal is to develop the software support needed for the design, analysis, understanding, and testing of programs involving many thousands of concurrent processes running on a highly parallel multiprocessor. We are currently evaluating the use of a shared dataspace paradigm as the basis for a new programming language supporting large-scale concurrency. The language is called SDL (Shared Dataspace Language). In SDL, a content-addressable dataspace is examined and altered by concurrent processes using atomic transactions much like those in a traditional database. Associated with each process is a programmer-defined ...Read More

The display of three-dimensional medical data is becoming more common, but current hardware and image rendering algorithms do not generally allow real-time interaction with the image by the user. Real-time interactions, such as image rotation, utilize the motion processing capabilities of the human visual system, allowing a better understanding of the structures being imaged. Recent advances in general purpose graphics display equipment could make real-time interaction feasible in clinical setting. We have evaluated the capabilities of one type of advanced display architecture, the PIXAR Imaging Computer, for real-time interaction while ...Read More

This paper describes the design of the Packet Switch Element Chip, one of the components of a high speed broadcast packet switching network. The chip is a 2x2 switch element, from which a switch fabric of arbitrary size can be constructed. It is currently being implemented in 3um, CMOS technology.

The Advanced Communications Systems Project is concerned with new communication technologies that can support a wide range of different communication applications in the context of large public networks. Communication networks in common use today have been tailored to specific applications and while they perform their assigned functions well, they are difficult to adapt to new uses. There currently are no general purpose networks, rather there are telephone networks, low-speed data network and cable television networks. As new communication applications proliferate, it becomes clear that in the long term, a more ...Read More

The Advanced Communications Systems Project is concerned with new communication technologies that can support a wide range of different communication applications in the context of large public networks. Communication networks in common use today have been tailored to specific applications and while they perform their assigned functions well, they are difficult to adapt to new uses. There currently are no general purpose networks, rather there are telephone networks, low-speed data network and cable television networks. As new communication applications proliferate, it becomes clear that in the long term, a more ...Read More

The patent application included in this report describes a buffer management system for use in a packet network supporting general multipoint communication. In multipoint connections with multiple transmitters, it is not possible to enforce bandwidth usage strictly by monitoring individual transmitters. We describe a method together with practical implementation that monitors the bandwidth use of various connections within the network and in the event of overload, protects the connections that are operating within their bandwidth allotment.

In this note, we show that wide-sense nonblocking networks can be obtained by cascading a pair of Cantor networks or a pair of Clos networks. The only constraint placed on the routing algorithms is that branching be restricted to the second network in the cascade. This result yields practical network for multipoint communication with complexities O(N(logN)2 and O(N1+1/r).

In this paper we lay a mathematical foundation for processes that communicate via directed communication channels. We start from a collection of primitive specifications. Particular correctness concerns partition this collection into equivalence classes, which can serve as abstract specifications. The theory is illustrated by taking as correctness concern absence of computation interference. In this case the abstract specification space can be identified with the space of delay-insensitive specifications.

In Trace Theory the notion of a process is defined in terms of a set of finite-length traces over an alphabet. These processes are used as the semantics for a program notation. The program text for a recursive component naturally gives rise to an equation over trace sets. This paper takes two approaches at the analysis of that equation. The first approach is based on a partial order and it concentrates on the projection operator for processes. This yields a condition under which the greatest solution of that equation can ...Read More

This paper describes the design of the Packet Switch Element Chip, one of the components of a high speed broadcast packet switching network. The chip is a 2x2 switch element, from which a switch fabric of arbitrary size can be constructed. It is currently being implemented in 2um CMOS technology.

In this paper we consider the probable performance of three polynomial time approximation algorithms for the Steiner tree problem with respect to a specific random graph model. The Steiner problem asks us to find a minimum cost spanning subgraph (tree) for a subset D of modes in a graph.

In this paper, we prove that the worst case performance of the Steiner tree approximation algorithm by Rayward-Smith is within two times optimal and that two is the best bound in the sense that there are instances for which RS will do worse than any value less than two.

We present a new algorithm for computing the QR factorization of an mxn Toeplitz matrix in O(mn) multiplications. The algorithm exploits the procedure for the rank-1 modification and the fact that successive columns of a Toeplitz matrix are related to each other. Both matrices Q and R are generated column by column, starting for their first columns. Each column is calculated from the previous column after rank-1 modification to the matrix R and a step of Gramm-Schmidt orthogonalization process applied to two auxiliary vectors.

We analyze and compare three algorithms for "downdating" the Cholesky factorization of a positive definite matrix. Although the algorithms are closely related, their numerical properties differ. Two algorithms properties of the algorithms, we compare their computational complexity and their suitability for implementation on parallel or vector computers.

We propose a novel algorithm and architecture for minimum variance distortions less response (MVDR) beamforming. Our approach extracts the least squares residual element directly, and requires only one systolic array for the many look directions.

We present a new algorithm and systolic array for adaptive beamforming. Our approach improves on McWhirter's pioneering work in two respects. First, our algorithm uses only orthogonal transformations and this should have better numerical properties. Second, the algorithms can be implemented on one single pxp triangular array of programmable processors that offers a throughput of one residual element per cycle.

We have applied logic programming to the problem of designing knowledge representation systems. This report describes a Generalized Database System, PRODB, that has been implemented in Prolog. It also describes two extensions to the basic PRODB core. First, knowledge representation and consistency-checking features have been added to PRODB to enhance its ability to consistently represent knowledge, especially in an Engineering domain. Second, extensions to Prolog's definite clause grammar mechanism have been used to create interfaces to a knowledge base directly from grammars describing the input languages. The interface to the ...Read More

We relate two concepts in graph theory and algorithmic complexity, namely the search number and the vertex separation of a graph. Lengauer has previously related vertex separation to progressive black/white pebble demand. Let a (G) denote the search number and vs(G) denote the vertex separation of a connected, undirected graph G. We show that vs(G) < s(G) < vs(G) +2 and we give a simple transformation from G to G^1 such that vs(G^1) = s(G). We give algorithm that, for any tree T, compute vs(T) in linear time and compute ...Read More

A fundamental need in future information systems is an effective method of accurately representing and monitoring dynamic, real-world situations inside a computer. Information is represented using an Extended Open World Assumption (EOWA), in which the data are explicitly true or false. Reasoning within the EOWA is done through the use of a dynamic dependency net which only represents those beliefs and justifications that are both currently valid and in current use. In this paper, we present definitions and uses of the EOWA and dynamic dependency net in our current research ...Read More

This paper is a user's manual for BEMAS, a Belief Maintenance System. BEMAS is a menu driven system which provides an easy to use interface between a user and a knowledge base. Given a set of data, and a set of rules, BEMAS will help the user to identify an object by analyzing the properties of that object. Data can be added and deleted at any time, either directly or by deleting beliefs on which the data is dependent. BEMAS maintains the relations and dependencies between data using a dynamic ...Read More

Connection management refers to the collection of protocols, algorithms and data structure used to establish and maintain multipoint connections in the broadcast packet network. This report documents an initial proposal for a set of connection management protocols that allows user to specify arbitrary multipoint connections in flexible and application-independent fashion. It also contains a set of detailed scenarios illustrating how the protocols would be used.

Feng and Wu have described a fault diagnosis method for a class of multi-stage interconnection networks including the banyan, delta and omega networks. We extend their method to switch fabrics containing several cascaded networks. We also show the method can be applied to system in which the processor performing the testing does not have direct access to all input and output ports.

This report introduces a new parallel computation model that is suitable for pursuit of large scale concurrency. Our goal is to develop a semantically clean paradigm for distributed computation with fine-grained parallelism. Our approach is to demote the notion of process as the key concept in organizing large scale parallel computation. We promote, instead, the notion of transaction, an anonymous atomic action void of internal state, as the basic element of computation. We propose to organize a computation as a network, called a transaction net, of databases connected by transactions. ...Read More

The WUDMA Image Processing System provides a framework that allows many image processing packages to function as the single system. It currently contains several packages that provide a powerful range of image processing tools for use in teaching and research. The WUDMA System overcomes the lack of standardization in image processing by providing bridges between diverse software packages and shielding the user from incompatibilities inherent in the software. As such, it may be considered as a paradigm from integrating packages in other application areas.

We consider the problem of arbitration access to a tree structured communication channel with large geographic extent, providing multipoint communication among a set of terminals. In our model, terminals transmit information in bursts consisting of many packets and compete for the right to transmit bursts. In the simplest case, the channel allows only one terminal to transmit at a time; this can be extended to k concurrent transmitters. The problem resembles contention resolution in local area networks. It is distinguished by the topology of the channel, the magnitude of the ...Read More