leff@smu.CSNET.UUCP (02/22/87)
Bibliography of Technical Reports Computer Science Department University of Wisconsin July 1986 - December 1986 For copies, send requests to: Technical Reports Librarian Computer Science Department University of Wisconsin 1210 W. Dayton St. Madison, WI 53706 @Indicates report is available at no charge. #Indicates report is a Ph.D. thesis and supplies are limited. *Indicates report is NOT available; contact author. %A Parter, Seymour V. %T Remarks on Multigrid Convergence Theorems %D July 1986 %R @TR 634 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: Multigrid has become an important iterative method for the solution of discrete elliptic equations. However, there is much to be done in the theory of convergence proofs. At the present time there are two general two-level methods for general convergence proofs: an algebraic approach and a duality approach. While these theories do not give sharp estimates they provide good, general rigorous convergence theorems. In this note we study the relationship between these theories. While the approach and thought-process leading to these theories are different, the results are essentially the same. Indeed, the basic estimated required by these theories are the same. %A Barton P. Miller and Jong-Deok Choi %A Jong-Deok Choi %T Breakpoints and Halting in Distributed Programs %D July 1986 %R @TR 648 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: Interactive debugging requires that the programmer be able to halt a program at interesting points in its execution. This paper presents an algorithm for halting a distributed program in a consistent state, and presents a definition of distributed breakpoints with an algorithm for implementing the detection of these breakpoints. The Halting Algorithm extends Chandy and Lamport's algorithm for recording global state and solves the problem of processes that are not fully connected or frequently communicating. The definition of distributed breakpoints is based on those events that can be detected in a distributed system. Events that can be partially ordered are detectable and form the basis for the breakpoint predicates, and from the breakpoint definition comes the description of an algorithm that can be used in a distributed debugger to detect these breakpoints. %A Raphael Finkel %A Bahman Barzideh %A Chandreshekhar W. Bhide %A Man-On Lam %A Donald Nelson %A Ramesh Polisetty %A Sriram Rajaraman %A Igor Steinberg %A G. A. Venkatesh %T Experience with Crystal, Charlotte and Lynx: Second Report %D July 1986 %R @TR 649 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: This paper describes several recent implementations of distributed algorithms at Wisconsin that use the Crystal multicomputer, the Charlotte operating system, and the Lynx language. This environment is an experimental testbed for design of such algorithms. Our report is meant to show the range of applications that we have found reasonable in such an environment and to give some of the flavor of the algorithms that have been developed. We do not claim that the algorithms are the best possible for these problems, although they have been designed with some care. In several cases they are completely new or represent significant modifications of existing algorithms. We present distributed implementations of PLA folding, a heuristic for the travelling-salesman problem, incremental update of spanning trees, ray tracing, the simplex method, and the Linda programming language. Together with our previous report, this paper leads us to conclude that the environment is a valuable resource and will continue to grow in importance in developing new algorithms. %A Barton P. Miller %A David L. Presotto %A Michael L. Powell %T DEMOS/MP: The Development of a Distributed Operating System %D July 1986 %R @TR 650 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: The DEMOS/MP operating system has moved from a super computer with a simple addressing structure to a network of microcomputers. This transformation was done without significant changes to the semantics of the original DEMOS, i.e., existing DEMOS programs should run on DEMOS/MP. The changes to DEMOS were simplified by the structure of its primitive objects and the functions over those objects. The structure of DEMOS links and processes were the major contributors to the simplicity. The changes made to produce DEMOS/MP involved the internal structure of link, modification to parts of the kernel, and limited changes to the various system processes. %A Leonard Uhr %T Toward a Computational Information-Processing Model of Object Perception %D July 1986 %R *TR 651 %I Computer Sciences Department, University of Wisconsin %X Abstract: Integrating What Is Known Into a Running Model. This paper describes the first version of an information-processing model (to be programmed for an appropriately structured parallel-serial multi-computer network) for the visual recognition of complex objects. The model will be run to exhibit its behavior, and tested, evaluated, and compared with living visual systems, and with other models. It should also serve, where the brain's mechanisms are not yet known, as a test-bed to evaluate alternate possible structures. Such an enterprise now appears to be feasible. Consider these highlights of pertinent facts: .The retina and primary visual cortex, with their massively parallel and to some extent serial structure of processes, detect spots, colors, families of oriented edges, and other features. .Much is now known about the cortex's columnar structure, and the topology of links within and between columns, hypercolumns, modules, and areas. .Roughly 20 cortical visual areas have been discovered. A great deal is known about the many links between them, the way they map information, and the processes each effects. .The recent firm evidence for neurons in the temporal lobe that respond selectively, in 70 to 200 msec, to face, different particular faces, complex parts of faces, and other complex objects, strongly suggests that these neurons are involved at a culminating stage in the complex structure of processes that perceives patterned objects. Temporal lobe lesions make complex objects like faces unrecognizable, while leaving other visual processes largely undisturbed. .The brain's massive parallelism makes this enormous speed possible. The relatively slow msec response times of its basic computing elements, the neurons, means that the maximum possible serial depth of processes is a few dozen to a few hundred at most. This paper first organizes key known facts about the visual system and describes the model. (Later sections give more detail, and pinpoint important facts still unknown.) It also briefly examines this model's relation to parallel computer architectures, to other models for visual perception, and to computer vision programs, emphasizing those from which this model grew. The goal is to develop a model/theory that exhibits the brain/mind's behavior on difficult recognition tasks, and suggests plausible mechanisms where facts are not yet uncovered, or firm. The running program should show that the model is precise and consistent, and how well the separate parts work together. It should suggest new questions and experiments. This first version incorporates only what appears essential to achieve a simple yet realistic working model. The final discussion examines possible improvements. %A Mark A. Holliday %T Deterministic Time and Analytical Models of Parallel Architectures %D July 1986 %R #TR652 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: In parallel computer architectures many events are of constant duration. For example, a fetch of a cache block, ignoring resource contention, takes a fixed number of clock cycles. Analytical performance modeling techniques that include deterministic time have previously been proposed. However, serious restrictions on the set of allowed models are imposed in these previous techniques. In this dissertation we extend these previous modeling techniques by removing those restrictions. Those restrictions fall into two classes: those involving the construction of the state space and those involving the analysis of the state space. We propose interpretations for performance measures when those restrictions are removed. In this general case, the state space represents an arbitrary, finite state, discrete parameter Markov Chain. We also present algorithms that efficiently construct and analyze the state space in the general case. Our technique is called Generalized Timed Petri Nets (GTPN). It has been implemented in a tool and has been used to develop models for several interesting architectures. The two most important studies examine bus-based multiprocessors. Performance degradation due to memory and bus interference in multiprocessors with a single-stage interconnection network has been frequently examined. Using the GTPN we are able to derive exact performance estimates in the important case when memory access times are constant and interrequest times are non-zero. Previously only approximate estimates and simulation results existed. Caches are an important means for reducing memory contention in bus-based multiprocessors. Our second study is the first analytical performance comparison of the key features of protocols that maintain cache consistency when a single shared bus is assumed. %A Raphael Finkel %A Michael L. Scott %A William K. Kalsow %A Yeshayahu Artsy %A Hung-Yang Chang %A Prasun Dewan %A Aaron J. Gordon %A Bryan Rosenburg %A Marvin H. Solomon %A Cui-Qing Yang %T Experience with Charlotte: Simplicity versus Function In a Distributed Operating System %D July 1986 %R @TR653 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: This paper presents a retrospective view of the Charlotte distributed operating system, which is intended as a testbed for developing techniques and tools for exploiting large-grain parallelism to solve computation-intensive problems. Charlotte was constructed over the course of approximately 5 years, going through several distinct versions as the underlying hardware and our ideas for implementation changed. Charlotte rests on several underlying design decisions: (1) it is a software layer on the Crystal multicomputer, (2) processes do not share memory, (3) communication is on reliable, symmetric, bi-directional paths named by capabilities, and (4) absolute information is stored at each end of a communication path. Our implementation taught us that our dual goals of simplicity and function were not easily reached. In particular, the issue of simplicity is quite complex; quests for simplicity in various areas often conflict with each other. This paper explores how the design decisions we made to satisfy our goals incurred implementation cost and required extra levels of software, but resulted in a high-quality testbed for experimentation in distributed algorithm design. %A Seymour V. Parter %T Estimates for Multigrid Methods Based on Red-Black Gauss-Seidel Smoothings %D July 1986 %R @TR654 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: The MGR[v] algorithms of Ries, Trottenberg and Winter, the algorithms 2.1 and 6.1 of Braess and the Algorithm 4.1 of Verfurth are all multigrid algorithms for the solution of the discrete Poisson equation (with Dirichlet boundary conditions) based on red-black Gauss-Seidel smoothing. Both Braess and Verfurth give explicit numerical upper bounds on the rate of convergence of their methods in convex polygonal domains. In this work we reconsider these problems and obtain improved estimates for the h-2h Algorithm 4.1 as well as W-cycle estimates for both schemes in non-convex polygonal domains. The proofs do not depend on the strengthened Cauchy inequality. %A Yeshayahu Artsy %A Hung-Yang Chang %A Raphael Finkel %T Processes Migrate in Charlotte %D August 1986 %R @TR655 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: Process migration in a distributed operating system is a facility to dynamically relocate processes among component computers. In recent years, several studies have been conducted concerning the need for process migration and the algorithms to perform it efficiently. Only a few successful implementations of process migration have been reported. A process-migration facility has been implemented in Charlotte, a message-based distributed operating system. Process migration policy is decided by a user-level utility called the Starter, while the mechanism is handled by the kernel. A distributed squad of Starters can enforce regional and global process migration policy. Several migration efforts can proceed in the system concurrently. Migration can be aborted due to a change in the load; the migrating process can be rescued in many cases of machine failure. Migration is transparent to the migrating process and to other processes communicating with it. Once a process is migrated out of a machine, no trail of stubs or dangling links is left to interfere with future communication. This paper gives an overview of Charlotte, discusses the design of the process migration facility, details its implementation, and gives some preliminary cost results. Process migration was implemented in mid-1985 and has been used experimentally since then. %A Tobin Jon Lehman %T Design and Performance Evaluation of a Main Memory Relational Database System %D August 1986 %R #TR656 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: Most previous work in the area of main memory database systems has focused on the problem of developing techniques that work well with a very large buffer pool. This dissertation addresses the problems of database architecture design, query processing, concurrency control, and recovery for a memory resident relational database, an environment with a very different set of costs and priorities. An architecture for a memory-resident database system is presented, along with a discussion of the differences between memory-resident database systems and conventional disk-based database systems. Index structures are then studied for a memory-resident database environment. The T Tree, a new index structure designed for use in this environment, is introduced and compared with several existing index structures: Arrays, AVL Trees, B Trees, Extendible Hashing, Linear Hashing, Modified Linear Hashing and Chained Bucket Hashing. The T Tree is shown to perform well in a memory-resident environment. Several of the index structures are then used to examine relational join and projection algorithms for a main memory database environment. Experimental results show that a Merge Join algorithm that uses a T Tree index is usually the best method, and that a simple Hash Join algorithm is usually second best. Recovering a memory-resident database is different from recovering a disk-oriented database, so a different approach is taken in this dissertation. Existing proposals for memory-resident database recovery treat the database as a single entity, so recovery and checkpoint operations are applied to the entire database. A new design is proposed that allows logging, checkpointing and recovery to be done at the relation or index level, providing a form of demand recovery. After a crash with undemanded relations being recovered by a background task. Finally, the cost issues for concurrency control are different for a memory-resident database system. Locking is more costly on a per database access basis, so it must be made more efficient. Multiple granularity locking is desirable, but it would be too expensive if several levels of locks needed checking for every database reference. An algorithm is presented that uses locks with a dynamic level of granularity, with locks being escalated or de-escalated in size to meet the system's concurrency requirements. %A Allan Bricker %A Tad Lebeck %A Barton P. Miller %T DREGS: A Distributed Runtime Environment for Game Support %D August 1986 %R *TR657 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: DREGS, a distributed environment for game support, simplifies the task of implementing multi-player games. DREGS solves the problems of concurrency control, synchronization, and communication as they apply to distributed games. DREGS provides support for the update and control of replicated objects and uses a central arbitration scheme to enforce a strict ordering of events. DREGS has been implemented to run under any 4.3BSD Unix compatible system and operates across a network of heterogeneous architectures. A game description language, GDL, provides a framework for programming multi-player distributed games. GDL is a simple language that generates complex distributed programs. It is an object-based language, where objects are defined in terms of their input events and their corresponding actions. The programmer writes the game as if it were a serial program, without concern for concurrent activities. GDL also frees the programmer from the details of device and network interfaces. The combination of the DREGS runtime and GDL frees a game designer from the distributed aspects of multi-player games. This freedom allows designers to concentrate their efforts on better, more interesting games. DREGS has been used to implement an N-way talk program, a tank game, and a flying saucer space game. %A Matthew T. Thazhuthaveetil %T A Structured Memory Access Architecture for LISP %D August 1986 %R #TR658 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: Lisp has been a popular programming language for well over 20 years. The power and popularity of Lisp are derived from its extensibility and flexibility. These two features also contribute to the large semantic gap that separates Lisp from the conventional von Neumann machine, typically leading to the inefficient execution of Lisp programs This dissertation investigates how the semantic gap can be bridged. We identify function calling, environment maintenance, list access, and heap maintenance as the four key run-time demands of Lisp programs, and survey the techniques that have been developed to meet them in current Lisp machines. Previous studies have revealed that Lisp list access streams show spatial locality as well as temporal locality of access. While the presence of temporal locality suggests the use of fast buffer memories, the spatial locality displayed by a Lisp program is implementation dependent and hence difficult for a computer architect to exploit. We introduce the concept of structural locality as a generalization of spatial locality, and describe techniques that were used to analyze the structural locality shown by the list access streams generated from a suite of benchmark Lisp programs. This analysis suggests architectural features for improved Lisp execution. The SMALL Lisp machine architecture incorporates these features. It partitions functionality across two specialized processing elements whose overlapped execution leads to efficient Lisp program evaluation. Trace-driven simulations of the SMALL architecture reveal the advantages of this partition. In addition, SMALL appears to be a suitable basis for the development of a multi-processing Lisp system. %A Udi Manber %T Using Mathematical Induction to Design Computer Algorithms %D August 1986 %R @TR660 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: An analogy between proving mathematical theorems and designing computer algorithms is explored in this paper. This analogy provides an elegant methodology for designing algorithms, explaining their behavior, and understanding their key ideas. The paper identifies several mathematical proof techniques, mostly based on induction, and presents analogous algorithm design techniques. Each of these techniques is illustrated by several examples of algorithms. %A M. A. Sridhar %T Efficient Algorithms for Multiple Pattern Matching %D August 1986 %R #TR661 %I Computer Sciences Department %C Madison, WI %X Abstract: We address the problem of finding an occurrence of one of several given patterns in a given text string. The Aho-Corasick algorithm solves this problem by constructing a modified finite automaton and using this to scan the text string left to right. This yields an algorithm that runs in time linear in the text length. The Boyer-Moore algorithm scans the text right to left, looking for an occurrence of one pattern. It has a sublinear average running time, and can be modified to be linear-time in the worst case. We extend the Boyer-Moore algorithm to handle multiple patterns. Two new algorithms are developed and analyzed. Both operate by remembering previous matches. Given a text string of length N and patterns with maximum length D, the first algorithm remembers no more than 1 + log D previous matches, and consults O(N log D) text characters. Algorithms for performing the necessary preprocessing are also developed. The second algorithm is designed for a different time-space tradeoff. For any given k, it consults O(kN log D) text characters, and remembers no more than t/k nonperiodic matches at any time, where t is the number of patterns. The dominating feature of a sublinear average-case running time is retained by both algorithms. %A Dennis Draheim %A Bart Miller %A Steven Snyder %T A Reliable and Secure UNIX Connection Service %D August 1986 %R @TR662 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: Distributed programs require a method for processes residing on different machines to identify each other and establish communication. One method is to provide a special connection service to perform this task. A good connection service should be easy to use. It should allow arbitrary processes to connect to each other as well as helping client processes to connect to server processes. It should provide location transparency; that is, the programmer should not have to know the network address of a process to connect to it. The connection service should be reliable. It should provide a way for a process to establish the identity of the user associated with the process to which it has connected, and to communicate securely with that process. We have implemented a connection service for Berkeley UNIX that is reliable, available, secure, and easy to use. The connection service achieves ease of use through a simple interface based on the library routine meet. Meet allows one process to connect to another by specifying arbitrary names for itself and the other process. The connection service imposes no naming conventions of its own so it can be used with most name spaces and naming services. The service is location-transparent. It also provides a routine for posting services. Reliable and available service is provided by replicating connection servers. Each server knows about all pending connection requests. The connection service provides continuous service as long as at least one server is running. Connections can be authenticated by an authentication server that works in cooperation with the connection server. Secure communication is achieved via the RSA public-key encryption algorithm. The connection server was put in regular use in June 1986. Our limited experience indicates that it satisfies an important need of UNIX users. %A David Kamowitz %T Experimental Results for Multigrid and Transport Problems %D September 1986 %R @TR663 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: An experimental study of the applicability of a multigrid algorithm to the solution of the neutron transport problem in a slab is described. Only the simplest choices are made for the components of the algorithm. Experimental results indicate that the coarse grid operator obtained from finite differences works better and is cheaper than the Galerkin choice. %A Charles V. Stewart %A Charles R. Dyer %T A Scheduling Algorithm for the Pipelined Image-Processing Engine %D September 1986 %R @TR664 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: In this paper we present a heuristic scheduling algorithm for the National Bureau of Standards' Pipelined Image-Processing Engine (PIPE). PIPE is a special purpose machine for low-level image processing consisting of a linearly connected array of processing stages. A program is specified as a planar directed acyclic graph where each node represents an operation on an image, and each arc represents an image output by one operation and input to another. The algorithm uses the greedy approach to schedule operations on a stage. It uses several heuristics to control the movement of images between stages. The worst case time for the schedule generated by the algorithm is O(N) times the optimal schedule, where N is the maximum width of the graph. Several examples are given where the algorithm generates a nearly optimal schedule. %A Ze-Nian Li %A Leonard Uhr %T Comparative Timings for a Neuron Recognition Program on Serial and Pyramid Computers %D September 1986 %R @TR665 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: This paper examines the time needed by a program that recognizes neurons in photomicrographs when it is executed on a conventional serial computer (a VAX 11/750), and compares this with the time that would be needed if it were executed on an appropriate parallel-serial pyramid multi-computer. As the size of the image array increases from 64x64 to 4,096x4,096 the estimates of the pyramid's increases in speed grow from 350 times as fast as the VAX to 1,276,300 times as fast. %A Prasun Dewan %T Automatic Generation of User Interfaces %D September 1986 %R #TR666 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: In traditional interactive programming environments, each application individually manages its interaction with the human user. The result is duplication of effort in implementing user interface code and non-uniform - hence confusing - input conventions. It would be useful if the user interface of an application could be automatically generated. This idea requires an application-independent model of user interaction together with a programming environment that supports the model. Recent work in user interface design has suggested that editing can be used as a general model of interaction. This dissertation presents an approach that supports this model. This approach allows applications to be created as objects. An object is a instance of a class that describes the data encapsulated by the object and the methods to manipulate them. Between each object and the user is a dialogue manager. The dialogue manager receives messages from the object, which name variables that can be edited by the user. It displays the variables using the data definition in the class of the object, offers the user a structure editing interface to modify them, and sends new values back in messages to the object. The object can then execute methods to make its internal data consistent with the displayed data. Thus, from the point of view of the objects, the user appears to be another object that can send and receive messages. From the point of view of the user, the objects appear to be data that can be edited. The dialogue manager acts as an intermediary between the object and the user, translating between the languages of object interaction and user interaction. A dialogue manager is provided automatically by the environment. The utility of our approach is demonstrated through discussion, examples, and implementation of its major components. %A Umakishore Ramachandran %T Hardware Support for Interprocess Communication %D September 1986 %R #TR667 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: Access to system services in traditional uniprocessor operating systems are requested via protected procedure calls, whereas in message-based operating systems they are requested via message passing. Since message exchange is the basic kernel mechanism in message-based operating systems, the performance of the system depends crucially on the rate of message exchange. The advent of local area networking has sparked interest in message-based operating systems. One of the main problems in existing multicomputer message-based operating systems has been the slowness of interprocess communication. This speed limitation is often due to the processing overhead associated with message passing. Previous studies implicitly assume that only communication between processes on different nodes in the network is expensive. However, we show that there is considerable processing overhead for local communication as well. Therefore, we propose hardware support in the form of a message coprocessor. Our solution to the message-passing problem has two components: a software partition, and a hardware organization. To determine an effective solution we followed a three-step process: First, we profiled the kernels of four operating systems to identify the major components of system overhead in message passing. The results suggested a partitioning of the software between the host and the message coprocessor. Second, we implemented such a partition on a multiprocessor and measured its performance. Based on these results, we proposed bus primitives for supporting the interactions between the host, the message coprocessor, and the network devices. We designed the bus in detail to show the feasibility of the primitives from the point of view of hardware implementation. Through the simplicity of the design, we show that our bus proposal is cost effective in this environment. Finally, we used Timed Petri nets to model and analyze several system architectures and show the effectiveness of our software partition and hardware organization for solving the message-passing problem. %A Gilbert Verghese %A Shekhar Mehta %A Charles R. Dyer %T Image Processing Algorithms for the Pipelined Image-Processing Engine %D September 1986 %R @TR668 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: In this paper we describe nine basic vision algorithms for the National Bureau of Standards' Pipelined Image-Processing Engine (PIPE). The algorithms presented are: local peak detection, median filtering, thinning, the Hough transform for line detection, photometric stereo, n-bit point operations, detecting edges at multiple resolutions, stereo vision, and multiresolution, model-based object recognition. %A Mary Vernon %A John Zahorjan %A Edward D. Lazowska %T A Comparison of Performance Petri Nets and Queueing Network Models %D September 1986 %R @TR669 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: Queueing networks (QNs) and performance Petri nets (PPNs) are two approaches to answering performance questions about computer systems. While QNs were originally designed to model resource contention among independent jobs and PPNs were designed to model parallel systems containing synchronization, there is clearly some overlap in the systems that can be modeled using each. In this paper we address this overlap with the goal of indicating whether the two models are fundamentally the same, or whether there are intrinsic differences that make one approach more powerful than the other for particular application domains. There seem to be two characteristics of a modeling approach that are most important in determining how it may be profitably employed. The first is notation: what models can be expressed, and perhaps more importantly, how convenient is it to specify a particular class of models? The second feature is the evaluation technique: what performance measures can be computed from the model, and what computational effort is required to do so? Our comparison of QNs and PPNs therefore concentrates on these two aspects. It is conceivable that the shortcomings of either approach in a particular environment might be addressed by adopting features of the other better suited to that environment. We consider this possibility for making improvements to the notations and evaluation efficiencies of the two modeling approaches. %A Bryan S. Rosenburg %T Automatic Generation of Communication Protocols %D October 1986 %R #TR670 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: This dissertation describes an effort to improve application-level communication efficiency by using information provided by, and derived from, the application itself. We define a simple language for describing the static form of conversations between application processes. A conversation description serves as a form of service specification for the conversation's underlying communication protocol. It specifies the types of messages required by the conversation and provides a regular expression that defines the set of legal sequences of messages between the conversation's participants. We also define structures we call plans that application processes can use dynamically to participate in conversations. A plan is a regular expression a process can construct to describe its desire to send or receive messages allowed by its active conversations. The plan mechanism is a generalization of the CSP guarded alternative construct. It allows processes to describe future as well as immediate intentions. Conversation descriptions and plans contain application-specific information that can be used to enhance the efficiency of the application's communication. Other useful information can be derived from measurements made while the application is running. We present strategies for collecting and using information from these sources. These strategies attempt to use application-specific information to reduce the number of low-level messages needed to accomplish the application's communication. We have implemented a version of the protocol generation system that supports application processes to be executed on the Crystal multicomputer. We describe several typical applications and evaluate their performance. We show that application-specific information from several sources can be used to significantly improve the efficiency of the application's communication. %A Thomas Reps %T Incremental Evaluation for Attribute Grammars with Unrestricted Movement Between Tree Modifications %D October 1986 %R @TR671 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: This paper concerns the design of editors that perform checks on a language's context-dependent constraints. Our particular concern is the design of an efficient, incremental analysis algorithm for systems based on the attribute-grammar model of editing. With previous incremental evaluation algorithms for arbitrary noncircular attribute grammars, the editing model required there to be a restriction on the operation that moves the editing cursor: moving the cursor was limited to just a single step in the tree - either to the parent node or to one of the child nodes of the current cursor location. This paper describes a new updating algorithm that can be used when an arbitrary movement of the cursor in the tree is permitted. After an operation that restructures the tree, the tree's attributes can be updated with a cost of O ((1 + |AFFECTED|) m) m), where m is the size of the tree and AFFECTED is the subset of the tree's attributes that require new values, when the cost is amortized over a sequence of tree modifications. The editing cursor may be moved from its current location to any other node of the tree in a single, unit-cost operation. %A Robert Howard Gerber %T Dataflow Query Processing Using Multiprocessor Hash-Partitioned Algorithms %D October 1986 %R #TR672 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: In this thesis, we demonstrate that hash-partitioned query processing algorithms can serve as a basis for a highly parallel, high performance relational database machine. In addition to demonstrating that parallelism can really be made to work in a database machine context, we will show that such parallelism can be controlled with minimal overhead using dataflow query processing techniques that pipeline data between highly autonomous, distributed processes. For this purpose, we present the design, implementation techniques, and initial performance evaluation of Gamma, a new relational database machine. Gamma is a fully operational prototype consisting of 20 VAX 11/750 computers. The Gamma architecture illustrates that a high performance database machine can be constructed without the assistance of special purpose hardware components. Finally, a simulation model of Gamma is presented that accurately reflects the measured performance of the actual Gamma prototype. Using this simulation model, we explore the performance of Gamma for large multiprocessor systems with varying hardware capabilities. %A Raphael Finkel %A Gautam Das %A Dhruva Ghoshal %A Kamal Gupta %A Ganesh Jayaraman %A Mukesh Kacker %A Jaspal Kohli %A Viswanathan Mani %A Ananth Raghaven %A Michael Tsang %A Sriram Vajapeyam %T Experience With Crystal, Charlotte and Lynx - Third Report %D November 1986 %R @TR673 %I Computer Sciences Department %C Madison, WI %X Abstract: This paper describes several recent implementations of distributed algorithms at Wisconsin that use the Crystal multicomputer, the Charlotte operating system, and the Lynx language. This environment is an experimental testbed for design of such algorithms. Our report is meant to show the range of applications that we have found reasonable in such an environment and to give some of the flavor of the algorithms that have been developed. We do not claim that the algorithms are the best possible for these problems, although they have been designed with some care. In several cases they are completely new or represent significant modifications of existing algorithms. We present distributed implementations of the stable marriage problem, finding roots of an equation, Gaussian elimination, finding minimal dominating sets, PLA folding, the Hough transform, the Banker's algorithm, the n-queens problem, and quick-sort. Together with our previous two reports, this paper leads us to conclude that the environment is a valuable resource and will continue to grow in importance in developing new algorithms. %A Susan Horwitz %T Adding Relational Databases to Existing Software Systems: Implicit Relations and A New Relational Query Evaluation Method %D November 1986 %R @TR674 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: Interactive software systems should include query handlers. Query handlers based on the relational database model are attractive because the model provides a uniform, non-procedural approach to query writing. Standard relational database systems require that all information be stored in relations; however, the data structures used by existing software systems are generally non-relational, and it is impractical to replace them with relations. A new kind of relations, implicit relations, and a new approach to query evaluation based on the use of access functions allow software systems to include relational query facilities without giving up existing non-relational data structures. The new query-evaluation method can also be used in traditional relational databases, and may be more efficient than traditional evaluation methods when applied to queries that use set operations. %A R. J. Chen %A R. R. Meyer %T A Scaled Trust Region Method For A Class of Convex Optimization Problems %D December 1986 %R @TR675 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: Piecewise-linear approximation of nonlinear convex objective functions in linearly constrained optimization produces subproblems that may be solved as linear programs. This approach to approximation may be used for nonseparable as well as separable functions, and for the former class (the focus of this paper), it lies between linear and quadratic approximation, we consider two devices: rectangular trus regions and dynamic scaling. The use of rectangular trust regions in conjunction with the type of piecewise-linear approximation considered here actually serves to simplify rather than complicate the approximating problems. This is a result of the equivalence of the trust region and the use of a limited number of segments in the approximation. The approach to dynamic scaling considered here may be applied to problems in which each objective function term is a convex function of a linear function of the variables. This scaling device allows the algorithm to adjust the approximation between an underestimating function (corresponding to a linear approximation) and an overestimating function (the nonseparable analog of the overestimate associated with separable approximation of convex functions.) The scaling factor is adjusted in accordance with the acceptance criteria associated with the trust region method. Computational experience is cited for some large-scale problems arising from traffic assignment applications. The algorithm considered here also has the property that it allows such problems to be decomposed into a set into a set of smaller optimization problems at each major iteration. These smaller problems correspond to linear single-commodity networks, and may be solved in parallel. Results are given for the distributed solution of these problems on the CRYSTAL multicomputer. %A Anil Allan Pal %T Generating Execution Facilities for Integrated Programming Environments %D November 1986 %R #TR676 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: This thesis presents an approach to the problem of generating execution facilities for integrated programming environments from specifications of the dynamic semantics of programming languages. The approach is based on techniques used in semantics-directed compiler generators, using a denotational semantic description of the language. These techniques are adapted to the special nature of an integrated programming environment, in particular the need to provide incremental translation and interactive execution. In interpreters generated using our system, programs are translated into denotations that are represented as linked structures containing pointers to the compiled code of denotation functions. This representation is compact, provides reasonable execution efficiency, and is easy to maintain incrementally during program modification. The correspondence between the executable representation and the parse tree of the program can be exploited to permit the user to interact with the program at runtime in terms of source-language constructs, thus providing support for interactive execution. We show how many of the features of previous hand-coded integrated programming environments can be incorporated naturally into the generated execution facilities. %A Mitali Bhattacharyya %A David Cohrs %A Barton Miller %T Implementation of a Visual Unix Process Connector %D December 1986 %R @TR677 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: UPCONN is a tool used by a programmer to visually describe the connections between the processes in a distributed program and to execute the distributed program. With UPCONN, the implementation of processes in a program is separated from the description of the connections between them. The programmer is provided with a screen editor which enables processes to be described and allows the connections between these processes to be specified. When a distributed program is described, UPCONN allows the user to execute the program or save the program for later use. UPCONN has a modular design which makes it easily extendible and allows its parts to be used independently. A library of processes and procedures is included to perform specialized tasks, such as message monitoring and file access. The library provides a method for adding new features to UPCONN. Several existing UNIX utilities can be linked in with UPCONN to provide a variety of functions. UPCONN is implemented under 4.3BSD UNIX and runs on a network of homogeneous computers. %A Ze-Nian Li %A Leonard Uhr %T Pyramid Vision Using Key Features to Integrate Image-Driven Bottom-Up and Model-Driven Top-Down Processes %D December 1986 %R @TR678 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: Pyramid-like parallel hierarchical structures have been shown to be suitable for many computer vision tasks, and to have the potential for achieving the speeds needed for the real-time processing of real-world images. We are developing algorithms to explore the pyramid's massively parallel and shallowly serial-hierarchical computing ability in an integrated system that combines both low level and higher level vision tasks. Micro-modular transforms are used to embody the program's knowledge of the different objects it must recognize. This paper describes pyramid vision programs that, starting with the image, use transforms that assess key features to dynamically imply other feature-detecting and characterizing transforms, and additional top-down, model-driven processes to apply. Program performance is presented for four real-world images of buildings. The use of key features in pyramid vision programs and the related search and control issues are discussed. To expedite the detection of various key features, feature-adaptable windows are developed. In addition to image-driven bottom-up and model-driven top-down processing, lateral search is used, and is shown to be helpful, efficient, and feasible. The results indicate that, with the use of key features and the combination of a variety of powerful search patterns, the pyramid-like structure is effective and efficient for supporting parallel and hierarchical object recognition algorithms. %A Charles R. Dyer %T Multiscale Image Understanding %D December 1986 %R @TR679 %I Computer Sciences Department, University of Wisconsin %C Madison, WI %X Abstract: This paper reviews methods for understanding multiscale (also called multiresolution) image descriptions. We include work related to the construction and analysis of image representations which make explicit properties of edges, shape and texture at multiple scales. In addition we present two applications of multiscale techniques for model-based object recognition and texture segmentation.