Technical Reports and MS Project Reports

This document describes the motivation, language description, and experience using FrIL, an intermediate language for a compiler's "middle-end." FrIL has subbessfully supported a two-semester compiler construction sequence, where the first semester included code generation from a C-like language and the second semester included advanced data flow analysis and program transformation.

A multimedia ATM network is shared by media streams with different performance requirements. For media streams such as file transfers, the preservation of bursts and the provision of guarantees for loss probability at the burst level is of primary importance, while, for media streams such as voice, loss guarantees at the cell level are sufficient. Continuous media have stringent delay jitter requirements. Finally, some applications require loss-free transmission. In this paper, the first complete traffic management scheme for multimedia ATM networks is introduced. The traffic management scheme supports four different ...Read More

When using random clone overlap based methods to make DNA maps, fragment matching mistakes, the incorrect matching of similar length restriction fragments, are a common problem that produces incorrect maps. Previous work presented the Restricted Splitting Algorithm (or RSA), which is useful for repairing a map containing a fragment mistake when the location of the mistake is known. This work presents an algorithm, called FIX, which attempts to identify the location of the fragment matching mistake and then uses the RSA to repair the map containing the mistake. In essense, ...Read More

A technique called Synchronized Double Digest Mapping (SDDM) is presented; it combines classical Double Digest Mapping (DDM) and Multiple-Restriction-Enzyme Mapping (MREM). Classical DDM is a technique for determining the order of restriction fragments in a clone given three digestions of the clone: a digestion by enzyme1, a digestion by enzyme2, and a digestion by enzyme1 and enzyme2 combined. All algorithms for applying this technique are exponential (in the number of fragments present in the clone) in nature. MREM is an extension of classical high-resolution restriction-fragment mapping of a YAC or ...Read More

A framework is given for specifying nonblocking traffic limits in a connection-oriented communications network. In this framework, connections may be point-to-point or mutlipoint, and the data rates may vary from one connection to another. The traffic limits may be "flat", or they may also be hierarchical, representing communities of interest within the network that have higher traffic among themselves than with the rest of the network. The communication networks are constructed from switches (or nodes) and trunks, which connect pairs of switches. This framework is intended to model Asynchronous Transfer ...Read More

Clocked (synchronous) and self-timed (asynchronous) represent the two prinicipal methodologies associated with timing control and synchronization of digital systems. In this paper, clocked and the asynchronous instruction pipelines are modeled and compared. The approach which yields the best performance is dependent on technology parameters, operating range and pipeline algorithm characteristics. Design curves are presented which permit selection of the best approach for a given application and technology environment.

Two experiments for evaluating psychophysical distortion metrics for JPEG-encoded images are described. The first is a threshold experiment, in which subjects determined the bit rate or level of distortion at which distortion was just noticeable. The second is a suprathreshold experiment in which subjects ranked image blocks according to perceived distortion. The results of these experiments were used to determine the predictive value of a number of computer image distortion metrics. It was found that mean-square-error is not a good predictor of distortion thresholds or suprathreshold perceived distortion. Some simple ...Read More

Supervised Competitive Learning (SCL) assembles a set of learning modules into a supervised learning system to address the stability-plasticity dilemma. Each learning module acts as a similarity detector for a prototype, and includes prototype resetting (akin to that of the ART) to respond to new prototypes. SCL has usually employed backpropagation networks as the learning modules. It has been tested with two feature abstractors: about 30 energy-based features, and a combination of energy-based and graphical features (about 60). Anout 75 subjects have been involved. In recent testing (15 college students), ...Read More

SCL assembles a set of learning modules into a supervised learning system to address the stability-plasticity dilemma. Each learning module acts as a similarity detector for a prototype, and includes prototype resetting (akin to that of ART) to respond to new prototypes. Here (Part I) we report SCL results using back-propagation networks as the learning modules. We used two feature extractors: about 30 energy-based features, and a combination of energy-based and graphical features (about 60). SCL recognized 98% (energy) and 99% (energy/graphical) of test digits, and 91% (energy) and 96% ...Read More

This paper presents the analysis of an improved distributed checkpointing algorithm. It shows that the message volume of Koo and Toueg's distributed checkpointing algorithm approaches 3fN for large checkpoint intervals where N is the number of processes and processes randomly send messages to f other processes. Thus, the average mesage volume is O(n2). We show how Koo and Toueg's algorithm can be modified so as to avoid this O9n2) overhead and derive an accurate estimate of the message volume. The overhead is reduced by using dependency knowledge to substantially reduce ...Read More

This paper shows how Koo and Toueg's distributed checkpointing algorithm can be modified so as to substantially reduce the average message volume. It attempts to avoid O(n{squared}) messages by using dependency knowledge to reduce the number of checkpoint request messages. Lemmas on consistency and termination are also included.

We present two algorithms that use membership and equivalence queries to exactly identify the concepts given by the union of s discretized axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. The first algorithm receives at most s*d counterexamples and uses time and membership queries polynomial in s and logn for d any constant. Further, all equivalence queries made can be formulated as the union of O(s*d*log(s)) axis-parallel boxes. Next, we introduce a new complexity measure that better captures the complexity of a union ...Read More

I/O abstraction is offered as a new high-level approach to interprocess communication. Functional components of a concurrent system are written as encapsulated modules that act upon local data structures, some of which may be published for external use. Relationships among modules are specified by logical connections among their published data structures. Whenever a module updates published data, I/O takes place implicitly according to the configuration of logical connections. The Programmer's Playground, a software library and run-time system supporting I/O abstraction, is described. Design goals include high-level communication among programs written ...Read More

A unified model of distributed systems that accomodates both shared-memory and message-passing communication is proposed. An extension of the I/O automaton model of Lynch and Tuttle, the model provides a full range of types of atomic accesses to shared memory, from basic reads and writes to read-modify-write. In addition to supporting the specification and verification of shared memory algorithms, the unified model is particularly helpful for proving correspondences between atomic shared objects and invocation-response systems and for proving the correctness of systems that contain both message passing and shared memory ...Read More

We introduce a formal model of teaching in which the teacher is tailored to a particular learner, yet the teaching protocol is designed so that no collusion is possible. Not surprisingly, such a model remedies the non-intuitive aspects of otehr models in which the teacher must successfully teach any consistent learner. We prove that any class that can be exactly identified by a deterministic polynomial-time algorithm with access to a very rich set of example-based queries is teachable by a computationally unbounded teacher and a polynomial-time learner. In addition, we ...Read More

Multimedia workstation architectures differ from current architecture in these respects – they have multiple specialized processing units, a high speed I/O interconnect mechanism, a high speed broadband network interface and a real-tie multitasking operating systems (OS) that provides QoS guarantees. These systems will primarily be used to run distributed applications that require high network throughput and predictable delay and delay jitter for real-time traffic. We argue the need for a different protocol organization and processing architecture in order to achieve this. We show how the emerging hardware architecture and OS ...Read More

In this paper, the N-body simulation problem is considered, its parallel implementation described, its execution time performance is modeled and compared with measured results, and two alternative load balancing algorithms for enhancing performance investigated. Parallel N-body techniques are widely applied in various fields and possess characteristics that challenge the computation and communication capabilities of parallel computing systems and are therefore good candidates for use as parallel benchmarks. Performance models may be used to estimate the performance of an algorithm on a given system, identify performance bottlenecks and study the performance ...Read More

The quality of performance of a decision-support system (or an expert system) is determined to a large extent by its underlying preference model (or knowledge base). The difficulties in preference and knowledge acquisition make them a major focus of current research in decision-support and expert systems. Researchers have used various concepts to develop promising acquisition techniques. One of the concepts used is knowledge maintenence where the knowledge base is changed in response to incorrect or inadequate performance by the expert system. This dissertation investigates a preference acquisition technique based on ...Read More

Computers have been used in radiation therapy since the early 1960s to perform dose calculations. In the last decade, researchers have developed computer-based clinical decision-support systems for assisting in different decision-making tasks in radiation therapy. This paper reviews eleven prototype systems developed for target volume delineation, treatment planning, treatment plan evaluation, and treatment machine diagnosis. The advent of three-dimensional (3D) conformal radiation therapy (CRT) provides radiation oncologists with the opportunity to consider innovative beam arrangements which were not possible in two-dimensional class solutions. The difficulty of manually generating the thousands ...Read More

The evaluation of radiation treatment plans involves making trade-offs among doses delivered to the tumor volumes and nearby normal tissues. Evaluating state-of-the-art three-dimensional (3D) plans is a difficult task because of the huge amount of planning data that needs to be deciphered. Multiattribute utility theory provides a methodology for specifying trade-offs and selecting the optimal plan from many competing lans. Using multiattribute utility theory, we are developing a clinically meaningful objective plan-evaluation model for 3D radiation treatment plans. Our model incorporates three of the factors involved in radiation treatment evaluation ...Read More

We report an experiment designed to compare human-human spoken dialogues with human-computer spoken dialogue. Our primary purpose was to collect data on the kinds of protocols that were used to control the interaction. Three groups of 12 subjects each were asked to complete tasks over the phone. These tasks involved the use of custom-calling features such as call-forwarding and speed-dialing. The experimental procedure was a new variation on the Wizard of Oz (WOZ) technique that allowed much clearer comparisons to be made between human-human and human-computer interactions. Subjects in the ...Read More

TRAINREC is a system for training feedforward and recurrent neural networks that incorporates several ideas. It uses the conjugate-gradient method which is demonstrably more efficient than traditional backward error propagation. We assume epoch-based training and derive a new error function having several desirable properties absent from the traditional sum-of-squared-error function. We argue for skip (shortcut) connections where appropriate and the preference for a sigmoidal yielding values over the [-1,1] interval. The input feature space is often over-analyzed, but by using singular value decomposition, input patterns can be conditioned for better ...Read More

The integration of video and audio into computers requires the support of continuous streams at the hardware level. This paper proposes a bus bandwidth management and access arbitration scheme for a multimedia workstation. It is assumed that a multimedia workstation consists of several specialized processing modules which are linked by a packet-switched bus. Using the proposed scheme, the bus can support a mix of real-time continuous media streams and random transactions while fulfilling special requirements corresponding to each traffic type. Specifically, the bus provides very fast response to random transactions ...Read More

SCL assembles a set of learning modules into a supervised learning system to address the stability-plasticity dilemma. Each learning module acts as a similarity detector for a prototype, and includes prototype resetting (akin to that of ART) to respond to new prototypes. Here (Part I) we report SCL results using back-propagation networks as the learning modules. We used two feature extractors: about 30 energy-based features, and a combination of energy-based and graphical features (about 60). ACL recognized 96% (energy) and 99% (energy/graphical) of test digits, and 91% (energy) and 96% ...Read More

Representation poses important challenges to connectionism. The ability to structurally compose representaitons is critical in achieving the capability considered necessary for cognition. We are investigating distributed patterns that represent structure as part of a larger effort to develop a natural language processor. Recursive Auto-Associative Memory (RAAM) representations show unusual promise as a general vehicle for representing classical symbolic structures in a way that supports compositionality. However, RAAMs are limited to representations for fixed-valence structures and can often be difficult to train. We provide a technique for mapping any ordered collection ...Read More

The development of computationally informed formalisms for reasoning with defeasible rules affords new accounts of familiar forms of reasoning. This paper points to recent accounts of defeasible reasoning and portrays analogy, decision, and theory-formation as essentially defeasible, in the same way that statistical reasoning has been portrayed. Each portrayal depends largely on the idea of partial computation, which is inherent in actual reasoning, largely ignored by past formalisers, and formalizable now.

We discuss the problem of representing utility in planning systems that are based on Allen's [83] popular ontology for planning, which represents actions and events as time intervals. We identify a small number of primitive functions on time intervals which may be helpful in representing preference and also in eliminating dominated actions. Assuming that utility can be decomposed to take advantage of these primitives, these functions provide one solution to the problem of specifying utility in such expressive planning languages. We identify a restricted class of utility expressions that generate ...Read More

Cell loss is an inherent problem of ATM networks. The magnitude of the service degeneration caused by cell loss depends on the application and loss distribution. This paper introduces a new performance criterion, called effective loss, which can quantitatively measure this degradation. Effective loss is particularly suitable for block-oriented transmissions, such as file transfer applications, but can also be applied to a broad range of other applications. In this paper the effective loss measure is applied to the study of the effectiveness of bandwidth reservation mechanisms in an ATM multiplexer. ...Read More

This chapter considers the problems of expressing logic and constructing proofs in fault tolerant connectionist networks that are based on energy minimalism. Given a first-order-logic knowledge base and a bound k, a symmetric network is constructed (like a Boltzman machine or a Hopfield network) that searches for a proof for a given query. If a resolution-based proof of length no longer than k exists, then the global minima of the energy function that is associated with the network represent such proofs. If no proof exist then the global minima indicate ...Read More

This work delineates the relation between logic and symmetric neural networks. The motivation is two-fold: 1) to study the capabilities and limitations of connectionist networks with respect to knowledge representatoin; and 2) to develop a new kind of inference negine that is expressive, massively parallel, capable of coping with nonmonotonic or noisy knowledge and capable of learning. The thesis shows that propositional logic can be implemented efficiently in networks where hidden units allow the representation of arbitrary constraints. An inference engine is constructed which can obtain its knowledge either by ...Read More

The chapter presents methods for efficiently representing logic formulas in connectionist networks that perform energy minimization. Algorithms are given for transforming any formula into a network in linear time and space and for learning representations of unknown formulas by observing examples of satisfying truth assignments. The relaxation process that underlies networks of energy minimization reveals an efficient hill climbing algorithm for satisfiability problems. Experimental results indicate that the parallel implementation of the algorithm with give extremely good average-case performance, even for large-scale, hard satisfiability problems (randomly generated).

The Washington University MultiMedia eXplorer (MMX) is a complete, host-independent multimedia system capable of transmitting and receiving JPEG-compressed video, CD-quality audio, and high-resolution radiographic images over the Washington University broadband ATM network. If the host is equipped with an ATM interface card, normal network traffic is supported via "T" and "Y" connections. The MMX consists of an ATMizer and three multimedia subsystems. The ATMizer implements the host interface, the interface to the ATM network, and the interface to the three multimdeia channels. This paper describes the architecture of the MMX, ...Read More

The Washington University Multimedia System (MMS) is a complete multimedia system capable of transmitting and receiving video, audio, and radiological images, in addition to normal network traffic, over the Washingon University broadband ATM network. The MMS consists of an ATMizer and three multimedia subsystems. The ATMizer implements the host interface, the interface to the ATM network, and the interface to the three multimedia subsystems. The video sybsystem encodes and decodes JPEG compressed video using two hardware compression engines. The audio subsystem encodes and decodes CD-quality stereo audio. The high-speed radiological ...Read More

Program visualization may be viewed as a mapping from programs to graphical representations. This simple idea provides a formal framework for a new taxonomy of program visualization systems. The taxonomy is compared briefly against previous attempts to organize the program visualization field. The taxonomic principles and their motivation are explained in detail with reference to a number of existing systems, especially Balsa, Tango, and Pavane.

This paper presents a model of concurrency (Dynamic Synchrony) whose distinctive feature is a novel formal treatment of synchronization. Synchrony is defined as the coordinated execution of two or more actions. The dynamic aspect comes from the fact that the definition of which actions must be executed synchronously can change freely during the execution of the program. This unique modeling capability comes with a UNITY-stype assertional logic that can be applied to program verification and derivation. This paper shows that the proposed proof logic can be used to verify programs ...Read More

This thesis describes a number of techniques for segmenting non-cursive handwritten digits into individual characters. It strongly emphasizes on a recognition-segmentation algorithm, which uses the linear regression method to recognize those strokes which consist of one or more straight-lined parts. A new method of sampling the pen data according to the pen speed, hence giving a more uniform points concentratino distribution, is also introduced. It is shown how several of our segmenting techniques, such as relative stroke lengths, relative stroke positions, order of stroke entry, stroke direction, stroke intersection, etc. ...Read More

Dynamic reconfiguration is explored in the context of I/O abstraction, a new programming model that defines the communication structure of a system in terms of connections among well-defined data interfaces for the modules in the system. The properties of I/O abstraction, particularly the clear separation of computation from communication and the availability of a module's state information, help simplify the reconfiguration strategy. Both logical and physical reconfiguration are discussed, with an emphasis on a new module migration mechanism that (1) takes advantage of the underlying I/O abstraction model, (2) avoids ...Read More

This paper describes an architecture for a multicast virtual circuit switch using cell recycling. This is the first nonblocking switch architecture that is optimal in both the switching network complexity and the amount of memory required for multicast address translation. Furthermore, it is optimal in the amount of effort required for multicast connection modification. This architecture makes it both technically and economically feasible to construct the large switching systems that will ultimately be needed for wide scale deployment of Broadband ISDN to residential users. In particular, we estimate that systems ...Read More

Many multipoint virtual circuit switching systems have been proposed for use in ATM networks. The inherent flexibility of ATm networks and the desire to use them for a wide range of different applications makes it impractical to rely on statistical traffic models, motivating a renewed interest in nonblocking networks. While the various multipoint architectures can all be configured to be nonblocking, for most, the cost quickly becomes prohibitive. We examine the complexity of several multipoint switch architectures, taking into account the switching network, the memory needed for routing and the ...Read More

In this paper we make an analogy between the time that storage must be maintained in an optimistic simulation and the blocking time in a conservative simulation. By exploring this analogy, we design two new Global Virtual Time (GVT) protocols for Time Warp systems. The first simple protocol is based on the null message scheme proposed for clock advancement in some conservative approaches; this yields what we call Local Guaranteed Time. Our main contribution is a second new protocol that is inspired by Misra's circulating marker scheme for deadlock recovery ...Read More

Supervised Competitive Learning (SCL) is described in an accompanying paper [1]; SCL assembles a set of learning modules into a supervised learning system to address the stability-plasticity dilemma. That paper reported results using backpropagation networds as the learning modules (SCL/BP). Here (Part II) we report SCL results using learning modules based on fuzzy logic (SCL/FZ). Although its learning algorithm is very different from that of backpropagation networks, fuzzy logic also suffers the stability-plasticity dilemma. A simulator on handwritten digit and gesture recognition was constructed to demonstrate the utility of SCL/FZ; ...Read More

This paper examines the performance of synchronous checkpointing in a distributed computing environment with and without load redistribution. Performance models are developed, and optimum checkpoint intervals are determined. The analysis extends earlier work by allowing for multiple nodes, state dependent checkpoint intervals, and a performance metric which is coupled with failure-free performance and the speedup functions associated with implementation of parallel algorithms. Expressions for the optimum checkpoint intervals for synchronous checkpointing with and without load redistribution are derived and the results are then used to determine when load redistribution is ...Read More

Early work in the dield of natural language processing was based on the assumption that humans interact with computers in the same way they do with other humans. However, more recent work seems to indicate otherwise. We conducted an experiment to explore human-computer interactions for a limited domain. The results that we obtained are consistent with recent findings. In a limited domain, when communicating with computers, people keep utterances very brief, pronomial references to a minimum and the conversation very focused. From the data that we have gathered, it is ...Read More

Current natural language processing systems have a wide coverage of English, but are unforgiving of errors and generate numerous alternative but irrelevant analyses. These problems are exacerbated when speech is the input medium rather than text, because speech recognizers generate their own errors and ambiguities. These errors, together with the user's informality of speech, can lead to extremely large search spaces of possible interpretations. To add to the complexity, only very small subsets of English can be analyzed semantically. For our domain, which is very limited, our approach is to ...Read More

Although speech recognition has improved significantly in recent years, it use in commercial environments has been limited by the inability of systems to model conventional co-operative dialogue. Any natural language systems for co-operative dialogue should at least be able to account for the many types of sub-dialogues that occur in conversations. Plan-based techniques provide a computationally powerful method for handling such dialogues. We discuss in this report our first attempt at building a plan-recognizer for an overall speech-driven system which interacts via a naturally restricted subset of English in a ...Read More