All Computer Science and Engineering Research

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

This paper describes application software and programming tools designed for use with the Defense Mapping Agency's (DMA) Standard Linear Format (SLF) for Digital Cartographic Feature Data. The Standard Linear Format (SLF) is briefly described in this report. It was designed as a standard for the exchange of digital cartographic features on magnetic tape. The format specifies descriptive fields about feature data, as well as specifying the representation of the features. The application software described in this report can transfer files or tapes in this format to relational database maintained under... Read More

This paper describes the design of the Broadcast Translation Chip, one of the components of a high speed packet switch. The chip allows the packet switch to handle multi-point as well as point-to-point connections. It will be implemented in 1.5 Um CMOS technology.

SDL (Shared Dataspace Language) is a language for writing and visualizing programs consisting of thousands of processes executing on a highly-parallel multiprocessor. SDL is based on a model in which processes use powerful transactions to manipulate abstract views of a virtual, content-addressable data structure called the dataspace. The process society is dynamic and supports varying degrees of process anonymity. The transactions are executed over abstract views of the dataspace. This facilitates elegant conceptualization of dataspace transformations and compact program representation. Processes and transactions enable SDL to combine elements of both... Read More

We started with an approach intended for the formalization of software/hardware interactions in distributed systems and applied it to an elevator control problem. The emphasis on physical relevance, intrinsic to the approach, has resulted in a new treatment of the elevator problem, one which reflects faithfully the structural and behavioral properties of the system components and which allows the designer to work on the algorithm for elevator movement and its proof in the realistic context of the total system. In addition to presenting the model we discuss several issues important... Read More

This paper is concerned with the development of a novel approach to edge based stereo matching. In the context of an incremental matching strategy we have replaced the traditional hierarchical (coarse-fine) matching by an approach called complexity control base matching. Our implementation of this method allows the user to select interactively features which (given the context provided by previous matches) are most likely to be matched successfully. The selection is done at the resolution of the original image and employs a rich set of features properties (e.g., edge strength, orientation,... Read More

Due to the large cost involved in generating effective input vectors to test MOS circuits, finding ways to reduce this test vector generation cost is of considerable interest. In this paper, empirical results show the fault coverage obtained form MOS transistor-level fault simulation using randomly generated test inputs can be approximated by the fault coverage obtained using the test vectors generated from classical stuck-at-zero and stuck-at-one fault simulation on logic-gate-level circuits. Applying this results, an approach is presented to reduce the cost of test vector generation for MOS circuits.

The following notes document in a succinct manner the use of the system PRODB. The system is still evolving and several new features are in the process of being added. PRODB is a prototype system that is being used as an exploration vehicle of the possible extensions to the relational model through logic programming. The system consists of a relational database system having a relational algebra type language as a query language. It is written in Prolog and it extends the capabilities of Prolog predicates with the relational algebra operators... Read More

The Advanced Communication 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. Communications 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 networks and cable television networks. As new communications applications proliferate, it becomes clear that in the long term, a more... Read More

The Advanced Communication 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. Communications 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 networks and cable television networks. As new communications applications proliferate, it becomes clear that in the long term, a more... Read More

Recent research in switching has concentrated on various forms of statistical switching networks capable of supporting user connections of arbitrary bandwidth. Fast packet switching is one approach that has gained a lot of attention and is being studied by many researchers. This paper addresses the problem of how the configuration of user connections affects the loading of the internal links of a switching fabric used for fast packet switching. It introduces a systematic method of analyzing the effects of a given traffic configuration and applies this method to the analysis... Read More

The broadcast packet network is a form of communications network based on high speed packet switches with a flexible multi-point connection capability, making them suitable for a wide variety of applications. This paper gives preliminary specifications for the integrated circuits being designed for the prototype switching system to be constructed at Washington University.

The design of flexible communications systems, supporting a wide range of applications is the principal challenge facing the communications industry today. This paper focuses on the problem of multipoint communications, suitable for supporting such applications as entertainment video distribution, voice/video teleconferencing and LAN interconnection. We review the key issues involved in the design of multipoint communication networks, including switching system architecture, connection management, multipoint routing and congestion control. We conclude that flexible multipoint communications networks are technically feasible given current technology, and while there are many research issues requiring further... Read More

This proposal addresses the problem of routing connections in a large scale packet switched communications system supporting multipoint communication. In this proposal a number of topics are considered including: the requirements imposed by routing in a large system, the Steiner tree problem of distributed algorithms which have access to limited information. In addition, this proposal outlines the work done to date and work that remains to be done.

The problem considered in this paper is to find an assignment of logic components to processors which will achieve logic simulation speed-ups approaching the ideal for large processor populations. This problem becomes particularly important when a significant portion of the speed-up expected from logic simulation engines is attributed to load sharing (as opposed to obtaining speed-up by employing specialized hardware to carry out specific tasks associated with the simulation process such as event queue manipulation or function evaluation). Our research considers this problem for a particular multiprocessor simulation architecture for... Read More

Adaptive Histogram Equalization (AHE), a method of contrast enhancement which is sensitive to local spatial information in an image, has been proposed as a solution to the problem of the inability of ordinary display devices to depict the full dynamic intensity range in some medical images. This method is automatic, reproducible, and simultaneously displays most of the information contained in the grey-scale contrast of the image. However, it has not been known whether the use of AHE causes the loss of diagnostic information relative to the commonly-used method intensity windowing.... Read More

In this paper we consider a problem of parsing a two-dimensional visual programming language Show and Tell on a two-dimensional array of processors. A program in Show and Tell is a bit-mapped, two-dimensional pattern satisfying a certain set of grammatical rules. The pattern consists of partially ordered set of rectilinear boxes and arrows distributed over the space of nxn pixel area. The corresponding directed graph, the box graph, where boxes are nodes and arrows are directed edges, may not have a cycle in a Show and Tell program. The cycle... Read More

This paper reports the results of a simulation study undertaken to evaluate a high performance packet switching fabric supporting point-to-point and multipoint communications. This switching fabric contains several components each based on conventional binary routing networks. The most novel element is the Copy Network which performs the packet replication needed for multipoint connections. We present results characterizing the performance of the Copy Network, in particular quantifying its dependence on fanout and the location of active sources. We also evaluate several architectural alternatives for conventional binary routing networks. For example, we... Read More

Lsim is a gate/switch level digital logic similar. It enables users to model digital circuits both at the gate and switch level and incorporates features that support investigation of the simulation task itself. This user's manual describes the procedures used to specify a circuit to lsim and control the simulation of the circuit (i.e., specifying inputs vectors, running the simulation, and monitoring output signals).

This paper presents a unified approach to mixed-mode simulation. It investigates the algorithms for both logic and circuit simulation, considering their similarities and differences, and a general framework is presented for integrating the two algorithms in uniform manner. The time advance mechanisms and component functional evaluations of the algorithms are show to be similar in nature, and mechanisms for the translation of information represented uniquely in the two algorithms are given. The resulting integrated algorithms is capable of performing mixed-mode simulation, where a circuit is partitioned into discrete and continuous... Read More

A visual programming language is presented. This language uses interactive graphics to convey notion such as subroutine, recursion, block structure, parallel and serial processing to school children. Currently the system is interpreter based. To overcome the inefficiency of the interpreter based system, a compiler is implemented for this language. This report gives an overview of the compiler and the details about the parser, semantic analyzer and the code generator. Finally, a performance comparison between the interpreter based system and the compiler based system is given.

Computer technology, and more broadly information technology, is invigorating a fundamental transformation in our society form an industrial economy to an information economy. A review of the short history and present state of information technology identifies two major undercurrents: the miniaturization of computer components which has produced a million-fold increase in the complexity possible in a single chip of silicon and the integration of four previously separate areas of information technology: computation, communication, databases and the user interface. Microelectronics, computer networks, data storage and user amenities are the basic technologies... Read More

This paper describes a method for detecting and segmenting spherical features using the gradient angle transform. An analysis of the gradient angle for ideal spheres is presented, with a discussional of how this may be used to locate the boundaries of the sphere. The algorithms used by a program which detects and segments spherical features are then presented. The results of applying the programs to images with naturally-occurring spherical features are given.

In radiology, as a result if the increased utilization of digital imaging modalities, such as computed tomography (CT) and magnetic resonance imaging (MRI), over a third of the images produced in a typical radiology department are currently in digital form, and this percentage is steadily increasing, Image compression provides a means for the economical storage and efficient transmission of these diagnostic pictures. The level of coding distortion than can be accepted for clinical diagnosis purposes is not yet well-defined. In this paper we introduce some constraints on the design of... Read More

This paper considers various physical constraints which influence the design of interconnection networks used in multiprocessor systems. Design expressions are presented for implementing an N log N packet passing interconnection network composed for circuit switched crossbar chip modules. Expressions reflecting chip level and board level pin and area constraints are derived and used to determine the network delay expected at a given clock frequency. Logic and memory delay, signal path delay, clock skew and clock tree delay parameters are defined and used to determine the maximum frequency which can be... Read More

This report introduces the idea of expressing programming concepts in a two-dimensional (pictorial) language. A specific two-dimensional language, Show and Tell, is briefly presented and formalisms that might be used to define the syntax of such a language are discussed. An abstraction of Show and Tell is defined, and a specific grammar formalism is presented for defining the syntax of this abstraction. The mechanisms found in expert systems are shown to be sufficient to parse languages defined by this formalism.

A parallel computation model suitable for icon based visual programming languages is proposed. The model is uses to design a functional programming language for school children. A computation is specified by boxes and arrows forming a partially ordered set of nested boxes. Loops and Boolean data tokens are eliminated from the traditional dataflow model. Block structures are logical consistency (exception) are added. A declarative semantics of the model is defined formally. Using the formalism it is proved that the model is determinate.

A visual language Show and Tell is introduced as a programming language for home information systems, integrating the computer capabilities of managing computation, communications, and database. It is shown that keyboardless programming is possible with Show and Tell. The language is implemented on the Apple Macintosh personal computer. The semantic model of the language is based on the concepts of dataflow and completion. A Show and Tell program is a partially ordered set of nested boxes and arrows. Traditional programming constructs such as subroutine, iteration, record structure recursion, exception, concurrency... Read More

The purpose of this report is to introduce essential features of the Show and Tell Language system to those computer users who are already familiar with some high-level programming language such as FORTRAN, BASIC or PASCAL. This manual is not intended for school children. Some familiarity with the Macintosh user interface and the MacPaint application program is assumed. It is also assumed that the Show and Tell application program disk and the Sample program are available to the reader. The basic programming concepts in Show and Tell are introduced in... Read More

The design of a Software Development Environment (SDE) represents a very interesting point of contact between data engineering and software engineering. In this context data engineering becomes the cornerstone for successful software engineering practices. This paper attempts to bring about a better understanding of the difficulties associated with this task by considering sources of complexity in SDE design.

A new approach to modelling distributed systems is presented. It uses sequential processes and event synchronization as building blocks to construct a cohesive picture of the interdependent requirements for the functionality, architecture, scheduling policies, and performance attributes of a distributed system. A language called CSPS (an extension of Hoare's CSP) is used in the illustration of the approach. Employing CSP as a base allows modelled systems to be verified using techniques already developed for verifying CSP programs and leads to the emergence of a uniform incremental strategy for verifying both... Read More

We describe a simple and efficient heuristic algorithm for the graph coloring problem and show that for all k greater or equal to 1, it finds an optimal coloring for almost all k-colorable graphs. We also show that an algorithm proposed by Brelaz and justified on experimental grounds optimally colors almost all k-O(n+m logk) time when n is the number of vertices and m the number of edges. The new implementation of Brelaz's algorithm runs an O(mlogn) time. We observe that the popular greedy heuristic works poorly on k-colorable graphs.

This paper describes the shortest common matching string problem, which arises from a data analysis problem in molecular genetics, and shows that it is NP-complete.

The high costs associated with logic simulation of large VLSI based circuits has led to the need for new computer architecture tailored to the simulation task. Such architectures have the potential for significant speed-ups over software-based logic simulators executing on standard sequential computers. This paper presents a model of one class of multiprocessor simulation architectures and compares the performance of some of these machines using data obtained from simulation of VLSI circuits. In addition, we discuss the implications of our results on machine design and examine the sensitivity of the... Read More

The high costs associated with logic simulation of large VLSI based systems have led to the need for new computer architectures tailored to the simulation task. Such architecture have the potential for significant speed-ups over standard software based logic simulators. Several commercial simulation engines have bene produced to satisfy needs in this area. To properly explore the space of alternative simulation architectures, data is required on the simulation process itself. This paper presents a framework for such data gathering activity and uses the data in estimating the maximum speed-up attainable... Read More

Design of high performance hardware and software based gate-switch level logic simulators requires knowledge about the logic simulation process itself. Unfortunately, little data is publically available concerning key aspects of this process. An example of this is the lack of published empirical measurements relating to the time distribution of events generated by such simulators. This paper presents a gate-switch level logic simulator lsim which is oriented towards the collection of data about the simulation process. The basic components of lsim are reviewed, and its relevant data gathering facilities are discussed.... Read More

Progressive transmission of digital pictures permits the receiver to reconstruct an approximate picture first, then gradually improves the quality of image reconstruction. A performance criterion is formulated for the evaluation of alternative schemes. The use of transform coding techniques to achieve progressive transmission is discussed. Application of the concept of progressive transmission to electronic radiology is introduced, and simulation results for individual images and panels of digital diagnostic images are presented. The relative quality of intermediate reconstruction seems to be superior to that of other progressive transmission techniques.

A new computation model suitable for icon based programming languages is proposed. The model is used to design a programming language for school children on the Macintosh personal computer. The model consists of boxes and arrows forming a partially ordered set of nested boxes. Loops and Boolean data tokens are eliminated from the traditional dataflow model. Block structures and logical consistency (exception) are added. Using a formal definition of the model it is proved that the model is determinate.

This document describes recent enhancements to the WUDMA image processing laboratory that implement improvements suggested by experience gained during the WUDMA I program. More recent improvements to the software are mentioned as well as a discussion of some of the design issues faced during the early stages of conception. Finally, some ongoing projects and future plans are mentioned.

This paper describes a system level specification approach that enables the designer to formulate and answer questions regarding the system's logical correctness and performance characteristics when the interaction between the hardware and the software is important, i.e., when the impact of faults, failures, communication delay, hardware selection, scheduling policies, etc., must be considered. In the simplest terms, our concern extends beyond the traditional software correctness questions by addressing the issue of employing logical verification techniques to determine software correctness and performance characteristics when running on a particular distributed hardware architectures... Read More

This paper describes a high performance packet switching network that can be used to provide voice, data and video communication on a large scale. A novel feature of the system is its flexible broadcast capability, which makes it suitable for a wide range of applications, including commercial television distribution and conferencing. The basic switching capability is provided by a high performance packet switch, called Switch Module (SM), which terminates up to 63 fiber optic communications links (FOL), operating at a speed of 100 Mbs. The SM is designed as a... Read More

The Integrated Services Digital Network (ISDN) has been proposed as a wat of providing integrated voice and data communications services on a universal or near-universal basis. In this paper, I argue that the evolutionary approach inherent in current ISDN proposals in unlikely to provide an effective long tern solution and advocate a more revolutionary approach, based on the use of advanced packet switching technology. The bulk of this paper is devoted to a detailed description of an Integrated Services Packet Network (ISPN), which I offer as an alternative to current... Read More

We define a natural probability distribution over the set of k-colorable graphs on n vertices and study the probable performance of several algorithms on graphs selected from this distribution. The main results are listed below. • We describe an algorithm to determine if a given n vertex graph is k-colorable, which runs in time O(n + m log k), where m is the number of edges. We show that this algorithm can successfully identify almost all random k-colorable graphs for constant or slowly growing values of k. • We show... Read More

The high costs associated with logic simulation of large VLSI based systems have led to the need for new computer architectures tailored to the simulation task. Such architecture have the potential for significant speedups over standard software based logic simulators. Several commercial simulation engines have been produced to satisfy need in this area. To properly explore the space of alternative simulation architectures, data is required on the simulation process itself. This paper presents a framework for such data gathering activity by first examining possible sources of speedup in the logic... Read More

With the growth in chip size and reduction in line width, delays in driving long lines have become increasingly important in determining overall chip level performance. In synchronous systems the proper distribution of the clock signal is critical in determining system throughput. This paper considers the problem of optimal driving clock lines. A general delay model is developed and applied to a clock tree where the path distances from the root node to each of the leaf nodes are all equal. This strategy reduces clock skew and increases clock rates.... Read More

A number of recent articles have focused on the design of high speed discrete-event simulation (DES) machines for digital logic simulation. These investigations are in response to the enormous costs associated with the simulation of complex (VLSI) digital circuits for logic verification and fault analysis. One approach to reducing simulation costs is to design special purpose digital computers that are tailored to the logic simulation test. This paper is concerned with the architecture of such logic machines. The paper has three principal parts. First, a taxonomy of logic machine architectures... Read More

The contents of a requirements specification is presented in light of the consensus reached both theoreticians and practitioners. The desirable properties of a requirements specification justified from a functionalist viewpoint and it is suggested that changes in the way one uses requirements may alter the relative significance of different properties. Finally, a classification requirements specification techniques is proposed and used as a backdrop against which current issues in the requirements engineering field are examined. The emphasis is on identifying general problem areas rather than offering the reader a literature survey.... Read More

A taxonomy is introduced and used as a backdrop against which current state-of-the-art in the requirements engineering field is reviewed. The emphasis is on identifying general trends and issues rather than offering the reader a literature survey. The contents of a requirements specification is presented in light of the consensus reached by both theoreticians and practitioners. The desirable proper ties of a requirements may alter the relative significance of difference properties. Finally, the classification of requirements specification techniques is approached from a total system design perspective. The paper shows that,... Read More

This paper establishes a formal foundation for the specification of Geographic Data Processing (GDP) requirements. The emphasis is placed on modeling data and knowledge requirements rather than processing needs. A subset of first order logic is proposed as the principal means for constructing formalizations of the GDP requirements in a manner that is independent of the data representation. Requirements executability is achieved by selecting a subset of logic compatible with the inference mechanisms available in Prolog. GDP significant concepts such as time, space and accuracy have been added to the... Read More

A design study of a Picture Communication Network is presented with special emphasis on those issues that differ from conventional networks. The large amount of data in an image together with the requirement for a rapid response time make a wide-band transmission medium a necessity. The wide-band medium is perceived as a collection of parallel broadcast channels. Four different logical organizations are proposed for this architecture. Design equations are developed and cost-performance curves are generated. Advantages of one organization over another under different circumstances are pointed out.

We consider the problem of embedding one graph in another, where the cost of an embedding is the maximum distance in the target graph separating vertices that are adjacent in the source graph. An important special case, know as the bandwidth minimization problem, is when the target graph is a path. This author has shown that for random graphs having bandwidth at most k, a well-known heuristic produces solutions having cost not more than 3k with high probability. This paper considers generalizations of this heuristic and analyzes their performance in... Read More