Technical Reports and MS Project Reports

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