1993 TECHNICAL REPORTS University of California at Santa Cruz Baskin Center for Computer Engineering and Information Sciences Santa Cruz, California 95064 U.S.A. ELECTRONIC COPIES Most of these tech reports are available electronically as compressed postscript files - the filenames are listed next to the tech report numbers. Obtain these files either of the following ways: 1. through anonymous ftp from ftp.cse.ucsc.edu, in the directory pub/tr. Log in as "anonymous", use your email address as password, specify "binary" before getting compressed *.Z files: ftp% cd pub/tr ftp% binary ftp% get ucsc-crl-year-number.ps.Z ftp% get INDEX ftp% mget ABSTRACTS* ftp% quit Uncompress *.Z files before printing: % uncompress ucsc-crl-year-number.ps.Z Send the uncompressed .ps file to your local printer: % lpr -P(your_local_postscript_printer) ucsc-crl-year-number.ps (Sometimes a report consists of multiple .ps files in a tarred and compressed directory, in the form ucsc-crl-year-number.tar.Z. First uncompress the directory, then de-tar it (% tar xvf filename.tar), ' then print the .ps files separately.) 2. by mail to automatic mail server rnalib@ftp.cse.ucsc.edu. Put commands on the subject line or in the body of the message: @@ send ucsc-crl-year-number.ps.Z from tr @@ send INDEX from tr @@ send ABSTRACTS.1993 from tr @@ list tr (gives a list of the files in the tr directory) @@ help commands (gives a list of mail server commands) You may request more than one tech report at a time. The reports you receive back will be in multiple sections with directions at the beginning of each and an "advance" message saying that all the sections are coming. Save the sections to separate files, and then do a /bin/sh to each file in the proper order: % /bin/sh file1 % /bin/sh file2 etc. This should produce a file with the format ucsc-crl-year-number.ps.Z which you then uncompress and print as described above. PAPER COPIES Order paper copies from: Technical Report Library, Baskin Center for Computer Engineering & Information Sciences, UCSC, Santa Cruz CA 95064, U.S.A. Payment in advance is required. Purchase orders are not accepted. Checks or money orders must be for U.S. dollars, payable through a U.S. bank, and made out to "UC Regents". QUESTIONS: trs@cse.ucsc.edu *************** UCSC-CRL-93-01 (available electronically as ucsc-crl-93-01.ps.Z) SPRAY RENDERING: A NEW FRAMEWORK FOR VISUALIZATION Alex Pang and Kyle Smith January 1993, 16 (paper copy $5.00) Abstract: We propose a new framework for doing scientific visualization that allows the users to freely explore their data set. This framework uses a metaphorical abstraction of a virtual can of spray paint that can be used to render data sets and make them visible. Different cans of spray paint may be used to color the data differently. Different types of spray paint may also be used to highlight different features in the data set. To achieve this, individual paint particles are endowed with intelligent behavior. This idea offers several advantages over existing methods: (1) it generalizes the current techniques of surface, volume and flow visualization under one coherent framework; (2) it works with regular and irregular grids as well as sparse and dense data sets; (3) it allows selective progressive refinement and can be implemented on parallel architectures in a straight forward manner; (4) it is modular, extensible and provides scientists with the flexibility for exploring relationships in their data sets in natural and artistic ways. *************** UCSC-CRL-93-02 (available electronically as ucsc-crl-93-02.ps.Z) RAPID EXPLORATION OF CURVILINEAR GRIDS USING DIRECT VOLUME RENDERING Allen Van Gelder and Jane Wilhelms October 1993, 13 pages (paper copy $5.00) Abstract: Fast techniques for direct volume rendering over curvilinear grids of hexahedral cells are developed. This type of 3D grid is common in computational fluid dynamics and finite element analysis. Four new projection methods are presented and compared with each other and with previous methods for tetrahedral grids and rectilinear grids. All four methods use polygon-rendering hardware for speed. A simplified algorithm for visibility ordering, which is based on a combination of breadth-first and depth-first searches, is described. A new multi-pass blending method is described that reduces visual artifacts that are introduced by linear interpolation in hardware where exponential interpolation is needed. Multi-pass blending is of equal interest to hardware-oriented projection methods used on rectilinear grids. Visualization tools that permit rapid data banding and cycling through transfer functions, as well as region restriction, are described. *************** UCSC-CRL-93-03 (available electronically as ucsc-crl-93-03.ps.Z) THE SWIFT/RAID DISTRIBUTED TRANSACTION DRIVER Bruce R. Montague January 1993, 32 pages (paper copy $7.00) Abstract: This document describes a distributed transaction driver developed to support the reimplementation of Swift with added RAID (Redundant Arrays of Inexpensive Disks) functionality. Both a high-level overview and a low-level program description are provided. The Swift system was developed to investigate the use of disk striping to achieve high I/O performance. The transaction driver described here has been used to implement RAID-0, RAID-4, and RAID-5 Swift systems. Swift uses a network of workstations in a manner similar to a redundant disk array, i.e., an application on a client node requests I/O via library routines which evenly distribute I/O across multiple server nodes. Data blocks in RAID files are distributed over the servers. RAID-0 contains no redundancy/parity information, RAID-4 uses a dedicated parity node, and RAID-5 uses distributed parity. The original Swift system used a straight-forward RAID-0 scheme that did not readily scale to RAID-4 and RAID-5 implementations. The transaction driver described here was developed to cope with the distributed concurrent programming problems posed by these implementations. In principle, this transaction driver can be used for a wide variety of distributed concurrent programming problems. Keywords: Swift, RAID, concurrent programming, transactions, distributed systems. *************** UCSC-CRL-93-04 (available electronically as ucsc-crl-93-04.ps.Z) LAYER ASSIGNMENT FOR RUBBER BAND ROUTING Tal Dayan and Wayne Wei-Ming Dai January 1993, 18 pages (paper copy $5.00) Abstract: The flexibility of the rubber-band wire model is very promising for routing and optimizing today's complex VLSI and MCM. In this paper we described a practical layer assignment algorithm used with a rubber band router. The algorithm uses a steepest descent approach with an heuristic function which estimate the wiring length of the generated assignment. We formulate the cost function and present an efficient way to compute it. The use of the cost function enable to control the final layout and to achieve balance between wire length and number of vias. The algorithm can be use as well for cost-driven one an a half layer designs in which one wiring layer has only short "jumpers" and is embedded in the ground layer. *************** UCSC-CRL-93-05 (available electronically as ucsc-crl-93-05.ps.Z) [Postscript file does not contain some of the diagrams. Write to trs@cse.ucsc.edu to have them sent to you via regular mail.] REINAS: REAL-TIME ENVIRONMENTAL INFORMATION NETWORK AND ANALYSIS SYSTEM: CONCEPT STATEMENT Darrell D.E. Long, Patrick E. Mantey, Alex T. Pang, Glen G. Langdon, Jr., Robert A. Levinson, Harwood G. Kolsky, Bruce R. Gritton, Carlyle H. Wash, and Leslie K. Rosenfeld January 1993, 69 pages (paper copy $10.00) Abstract: REINAS is a research and development program with the goal of designing, developing and testing an operational prototype system for data acquisition, data management and visualization. This system is to support the real-time utilization of advanced instrumentation in environmental science where continuous time measurements and improved spatial resolution allow monitoring and understanding of environmental phenomena in much greater detail than has previously been possible. The system will also support the retrospective use of integrated environmental data sets. The scientific problem chosen to provide a focus for study is in the area of air-sea-land interaction, in particular, seabreeze development and the oceanic response to it in Monterey Bay. The project is a multi-year effort of the Baskin Center for Computer Engineering and Information Sciences of the University of California, Santa Cruz, in cooperation with the environmental and marine scientists from the Naval Postgraduate School (NPS), Monterey Bay Aquarium Research Institute (MBARI), and the Center for Ocean Anallysis and Prediction (NOAA/COAP). This report is the Concept Statement for the REINAS project in which the initial system requirements and project plan for the system is described along with a preliminary architecture and its subsystems for data collection, data management, processing and visualization which are required for real-time operational applications in the marine environment. The objective of this document is to provide project participants and reviewers a baseline description of the problem that REINAS is targeting, the technology to be applied, and a plan for meeting project goals. The concepts discussed are meant to provide clear and concise direction for project activities and clear evaluation criteria for products produced by the REINAS team. Collected in the appendices of this report are details and documentation concerning the data sources, related projects, etc. that seem related to REINAS. *************** UCSC-CRL-93-06 (available electronically as ucsc-crl-93-06.ps.Z) SCHEDULING REAL-TIME DISK TRANSFERS FOR CONTINUOUS MEDIA APPLICATIONS Darrell D.E. Long and Madhukar N. Thakur January 1993, 7 pages (paper copy $5.00) Abstract: We study how continuous media data can be stored and accessed in the Swift distributed I/O architecture. We provide a scheme for scheduling real-time data transfers that satisfies the strict requirements of continuous media applications. Our scheme allows large data objects to be stored and retrieved concurrently from multiple disks so as to satisfy the high data rate requirements which are typical of real-time video and audio data. To do this, data transfer requests are split into smaller requests which are then handled by the various components of Swift. We study on-line algorithms that respond to a data request by promising to either satisfy or reject it. Each response must be made before the next request is seen by the algorithm. We discuss two different performance measures to evaluate such algorithms and show that no on-line algorithm can optimize these criteria to less than a constant fraction of the optimal. Finally, we propose an algorithm for handling such requests on-line and the related data structures. *************** UCSC-CRL-93-07 (available electronically as ucsc-crl-93-07.ps.Z) TRANSPARENT REMOTE PROCEDURE CALLS Michelle Denise Abram (M.S. Thesis) December 1992, 67 pages (paper copy $10.00) Abstract: With the vastly increased need for computing power in modern computing environments, the ability to distribute jobs across machine boundaries has become essential. The main drawback of distributed computing is the excessive complexity of network programming. One way to solve this problem is to create an environment that emulates the typical programming environment. This is the basis of remote procedure calls (RPC). A remote procedure call is the execution of a procedure that resides on a foreign host. A program at the remote site receives data from the caller, calls the procedure locally, and returns the result. To the programmer, remote procedure calls closely resemble local procedure calls. This is a well developed idea, and a number of RPC packages have been implemented. The problem with most of these packages is that complex initialization routines are required to use them. It is unnecessary to concern the programmer with the underlying connectivity and packet exchange mechanisms required to implement an RPC package. Further, these initialization requirements undermine the central goal of RPC programming: transparent distributed computing. We present a remote procedure call package that has been designed to relieve the programmer of this burden without sacrificing power. *************** UCSC-CRL-93-08 (available electronically as ucsc-crl-93-08.ps.Z) DESCRIPTIVE COMPLEXITY OF OPTIMIZATION AND COUNTING PROBLEMS Madhukar Narayan Thakur (Ph.D. thesis) December 1992, 121 pages (paper copy $14.00) Abstract: This thesis is about the descriptive complexity of two function classes, namely, NP optimization problems and #P counting problems. It is divided into two parts. In Part I we investigate NP optimization problems from a logical definability standpoint. We show that the class of optimization problems whose optimum is definable using first-order formulae coincides with the class of polynomially bounded NP optimization problems on finite structures. Next, we analyze the relative expressive power of various classes of optimization problems in this framework. We introduce an alternate approach to the logical definability of NP optimization problems by focusing on the expressibility of feasible solutions. We study the relationships between classes defined in these two frameworks. We identify sufficient syntactic conditions for approximability and isolate rich classes of approximate problems. Some of our results show that logical definability has different implications for NP maximization problems than it has for NP minimization problems, in terms of both expressive power and approximation properties. Regarding the relationship between approximability and logical definability, we show that, assuming P /= NP, it is undecidable to tell if a given first-order sentence defines an approximable optimization problem. Finally, we provide a machine-independent characterization of the NP ?= co-NP problem in terms of logical expressibility of the MAX CLIQUE problem. We conclude Part I by discussing some future directions in this line of research. In Part II, we give a logic based framework for defining counting problems and show that it exactly captures the problems in Valiant's counting class #P. We study the expressive power of the framework under natural syntactic restrictions and show that some of the subclasses so obtained contain problems in #P with interesting computational properties. In particular, using syntactic conditions, we isolate a class of polynomial time computable #P problems, and also a class in which every problem is approximable by a polynomial time randomized algorithm. We show, under reasonable complexity theoretic assumptions, that it is undecidable to tell if a counting problem expressed in our framework is polynomial time computable or is approximable by a randomized polynomial time algorithm. This work sets the foundation for further study of the descriptive complexity of the class #P. *************** UCSC-CRL-93-09 (available electronically as ucsc-crl-93-09.ps.Z) MODELING REPLICA DIVERGENCE IN A WEAK-CONSISTENCY PROTOCOL FOR GLOBAL-SCALE DISTRIBUTED DATA BASES Richard A. Golding and Darrell D. E. Long February 1993, 18 pages (paper copy $5.00) Abstract: Distributed database systems for wide-area networks must scale to very large numbers of replicas in order to provide acceptable availability and response time. Weak-consistency replication protocols, such as the *timestamped anti-entropy* (TSAE) protocol we have developed, allow a database to scale to hundreds or thousands of replicas. The TSAE protocol allows updates to be processed by a single replica, then propagated from one replica to another in the background, causing replicas to temporarily diverge. The divergence is resolved in a short time and is resolved correctly even in the presence of temporary replica failure and network partition. We present a detailed analysis of the update propagation latency and the divergence between replicas caused by this protocol. *************** UCSC-CRL-93-10 (available electronically as ucsc-crl-93-10.ps.Z) LOGICAL DEFINABILITY OF NP OPTIMIZATION PROBLEM Phokion G. Kolaitis and Madhukar N. Thakur June 1993, 30 pages (paper copy $7.00) Abstract: We investigate here NP optimization problems from a logical definability standpoint. We show that the class of optimization problems whose optimum is definable using first-order formulae coincides with the class of polynomially bounded NP optimization problems on finite structures. After this, we analyze the relative expressive power of various classes of optimization problems that arise in this framework. Some of our results show that logical definiability has different implications for NP maximization problems than it has for NP minimization problems, in terms of both expressive power and approximation properties. *************** UCSC-CRL-93-11 (available electronically as ucsc-crl-93-11.ps.Z) USING AN OBJECT-ORIENTED FRAMEWORK TO CONSTRUCT WIDE-AREA GROUP COMMUNICATION MECHANISMS Richard A. Golding and Darrell D. E. Long March 1993, 11 pages (paper copy $5.00) Abstract: Many wide-area distributed applications, including distributed databases, can be implemented using a group communication mechanism. We have developed a family of weak-consistency group communication mechanisms, based on the timestamped anti-entropy communication protocol, that provides the scalability and fault-tolerance needed by wide-area systems. We discuss an object-oriented framework for constructing this kind of group communication mechanism, and how its components can be selected to take advantage of specific application semantics. We examine several design choices that we made in building two very different wide-area distributed database applications, and how this framework led to simple, efficient implementations in both systems. *************** UCSC-CRL-93-13 (available electronically as ucsc-crl-93-13.ps.Z) SAMPLE COMPRESSION, LEARNABILITY, AND THE VAPNIK-CHERVONENKIS DIMENSION Sally Floyd and Manfred Warmuth March 1993, 23 pages (paper copy $6.00) Abstract: Within the framework of pac-learning, we explore the learnability of concepts from samples using the paradigm of sample compression schemes. A concept is a subset of some instance domain X and a concept class a set of concepts. A sample compression scheme of size d for a concept class C consists of a compression function and a reconstruction function. The compression function, given a finite sample set consistent with some concept in C, chooses a subset of k examples as the compression set. The reconstruction function, given a compression set of k examples, reconstructs a hypothesis on X. Given a compression set produced by the compression function from a sample of a concept in C, the reconstruction function must be able to reproduce a hypothesis consistent with that sample. We demonstrate that the existence of a fixed-size sample compression scheme for a class C is sufficient to ensure that the class C is learnable. We define maximum and maximal classes of VC dimension d. For every maximum class of VC dimension d, there is a sample compression scheme of size d, and for sufficiently-large maximum classes there is no sample compression scheme of size less than d. We discuss briefly classes of VC dimension d that applies to some maximal and nonmaximum classes. It is unknown whether there is a sample compression scheme of size d for every class of VC dimension d. *************** UCSC-CRL-93-14 (available electronically as ucsc-crl-93-14.ps.Z) MASSIVELY PARALLEL BIOSEQUENCE ANALYSIS Richard Hughey April 1993, 12 pages (paper copy $5.00) Abstract: Massive parallelism is required for the analysis of the rapidly growing biosequence databases. First, this paper compares and benchmarks methods for dynamic programming sequence analysis on several parallel platforms. Next, a new hidden Markov model method and its implementation on several parallel machines is discussed. Finally, the results of a series of experiments using this massively parallel implementation are described. *************** UCSC-CRL-93-16 (available electronically as ucsc-crl-93-16.ps.Z) STOCHASTIC CONTEXT-FREE GRAMMARS FOR MODELLING RNA Yasubimi Sakakibara, Michael Brown, Rebecca C. Undersood, I. Saira Mian and David Haussler June 8, 1993 24 pages (paper copy $6.00) Abstract: Stochastic context-free grammars (SCFGs) are applied to the problems of folding, aligning and modeling families of homologous RNA sequences. These models capture the common primary and secondary structure of the sequences with a context-free grammar, much like those used to define the syntax of programming languages. SDFGs generalize the hidden Markov models used in related work on protein and DNA sequences. The novel aspect of this work is that the SCFGs developed here are learned automatically from initially unaligned and unfolded training sequences. To do this, a new generalization of the forward- backward algorithm, commonly used to train hidden Markov models, is introduced. This algorithm is based on tree grammars, and is more efficient than the inside-outside algorithm, which was previously proposed to train SCFGs. This method is tested on the family of transfer RNA (tRNA) sequences. The results show that the model is able to reliably discriminate tRNA sequences from other RNA sequences of similar length, that it can reliably determine the secondary structure of new tRNA sequences, and that it can produce accurate multiple alignments of large collections of tRNA sequences. The model is also extended to handle introns present in tRNA genes. *************** UCSC-CRL-93-17 (available electronically as ucsc-crl-93-17.ps.Z) PERFECT-BALANCE PLANAR CLOCK ROUTING WITH MINIMAL PATH LENGTH (Supersedes 92-12) Qing Zhu and Wayne W.M. Dai March 1993, 27 pages (paper copy $6.00) Abstract: The design of high speed digital VLSI circuits prefers that the clock net is routed on the metal layer with the smallest RC delay. This strategy not only avoids the difficulties of having different electrical parameters on different layers, but also eliminates the delay and attenuation of the clock signal through vias. The clock phase-delay is also decreased. In this paper, we present a novel algorithm, based on hierarchical max-min optimization, to construct a planar clock tree which can be embedded on a single metal layer. The clock tree achieves equal path length---the length of the path from the clock source to each clock terminal is exactly the same. In addition, the path length from the source to clock terminals is minimized. Some examples including industrial benchmarks have been tested and the results are promising. We further optimize the geometry of the clock tree to minimize both the skew and path delay of the clock signal while maintaining the planarity of the clock network. Some premilinary results are promising which achieve near zero skew by using SPICE simulation. *************** UCSC-CRL-93-18 (available electronically as ucsc-crl-93-18.ps.Z) OPTIMAL SIZING OF HIGH SPEED CLOCK NETWORKS BASED ON DISTRIBUTED RC AND LOSSY TRANSMISSION LINE MODELS Qing Zhu, Wayne W.M. Dai, and Joe G. Xi April 1993, 20 pages (paper copy $5.00) Abstract: We have proposed an efficient measure to reduce the clock skew by assigning the clock network with variable branch widths. This measure has long been used for ``H'' clock tree. This paper formulates the optimal sizing of a general clock network as an optimization problem which minimizes the clock skew in a feasible set of widths. This feasible set of branch widths is decided by the process technology and routing resources. The skew minimization problem is turned into a least-squares estimation problem, and a modified Gauss-Marquardt's method is then used to determine the optimal widths of clock branches. This optimization method combines the best features of the methods based on Taylor series and methods based on gradients. An efficient algorithm is also proposed that assigns the good initial widths especially for a clock tree which let the later optimization process converge much more quickly. Our method is very flexible and can handle the general clock network including loops. The clock network can exhibit distributed RC and lossy transmission line behaviors. The method employs a scattering-parameters based delay macromodel to evaluate the timing of the clock network during the optimization process. The major objective of our sizing method is to minimize the skew, but as a by-product that the largest path delay is also reduced. *************** UCSC-CRL-93-19 (available electronically as ucsc-crl-93-19.ps.Z) C++ CLASSES FOR THE EFFICIENT MANIPULATION AND STORAGE OF HIERARCHICAL OBJECTS Dean R. E. Long May 1993, 54 pages (paper copy $9.00) Abstract: Many applications must efficiently store and manipulate complex objects. Often sub-objects or entire objects are identical. Memory use can be decreased by the use of object handles which point to shared objects in place of actual objects. If the objects are hierarchical, sub-objects can also be represented with handles, allowing many operations to manipulate handles instead of whole objects. The copy-on-write and object registration techniques presented here reduce the cost of storing, copying, modifying, and matching hierarchical objects. Using object registration, identical objects are detected and shared, allowing objects to be uniquely identified by their location in memory. Copy-on-write object semantics allows increased sharing and reduced copying, while hierarchical copy-on-write objects using handles allows copies to have deep-copy behavior but shallow-copy cost. *************** UCSC-CRL-93-20 (ONLY available electronically as ucsc-crl-93-20.ps.Z) COMPARING TWO GARBAGE COLLECTORS FOR C++ Daniel R. Edelson January 1992 Abstract: Our research is concerned with compiler-independent, tag-free garbage collection for the C++ programming language. This paper presents a mark-and-sweep collector, and explains how it ameliorates shortcomings of a previous copy collector. The new collector, like the old, uses C++'s facilities for creating abstract data types to define a *tracked reference* type, called _roots_, at the level of the application program. A programmer wishing to utilize the garbage collection service uses these roots in place of normal, raw pointers. We present a detailed study of the cost of using roots, as compared to both normal pointers and reference counted pointers, in terms of instruction counts. We examine the efficiency of a small C++ application using roots, reference counting, manual reclamation, and conservative collection. Coding the application to use garbage collection, and analyzing the resulting efficiency, helped us identify a number of memory leaks and inefficiencies in the original, manually reclaimed version. We find that for this program, garbage collection using roots is much more efficient than reference counting, though less efficient than manual reclamation. It is hard to directly compare our collector to the conservative collector because of the differing efficiencies of their respective memory allocators. *************** UCSC-CRL-93-21 (ONLY available electronically as ucsc-crl-93-21.ps.Z) DEBUGGING OPTIMIZED CODE WITHOUT BEING MISLED Max Copperman May 1993 Abstract: Optimizing compilers produce code that impedes source-level debugging. Examples are given in which optimization changes the behavior of a program even when the optimizer is correct, showing that in some circumstances it is not possible to completely debug an unoptimized version of a program. Source-level debuggers designed for unoptimized code may mislead the debugger user when invoked on optimized code. One situation that can mislead the user is a mismatch between where the user expects a breakpoint to be located and the breakpoint's actual location. A mismatch may occur due to statement reordering or discontiguous code generated from a statement. This work describes a mapping between statements and breakpoint locations that ameliorates this problem. The mapping enables debugger behavior on optimized code that approximates debugger behavior on unoptimized code closely enough that the user need not make severe changes in debugging strategies. This work presents a method of determining when this has occurred, proves the method correct, and shows how a debugger can describe the relevant effects of optimization. The determination method is more general than previously published methods, handling global optimization, flow graph transformations, and not being tightly coupled to optimizations performed by a particular compiler. The information a compiler must make available to the debugger for this task is also described. A third situation that can mislead the user is when optimization has eliminated information in the run-time (procedure activation) stack that the debugger uses (on some architectures) to provide a call stack trace. This work gives several methods of providing the expected stack trace when the run-time stack does not contain this information. *************** UCSC-CRL-93-22 (available electronically as ucsc-crl-93-22.ps.Z) DOING IT WITH MIRRORS: LOW BUDGET STEREO GRAPHICS Allen Van Gelder and Jane Wilhelms January 1994, 11 pages, (paper copy $5.00) Abstract: Intereactive stereoscopic images can be viewed on a graphics workstation by producing side-by-side images and viewing through a simple mirror device. However, it is important that the viewing device have pairs of adjustable nonparallel mirrors so large windows can be viewed without the human's sightlines needing to diverge, or ``look wall-eyed". Trans- formations to produce the correct images for this viewing method are described. Previous work applied to the case where both left and right images were to be superimposed and multiplexed in the same region of the screen, often called anaglyphs. Such cases are adequately handled by a translation and an off-axis perspective transformation. The same kind of transformation can be used with a parallel-mirror device, but such devices have practical limitations. This paper shows that nonparallel mirrors require a somewhat more complicated transformation involving scene rotations as well. Derivation of the correct angle of rotation is the main difficulty in computing this transformation. The transformation can be implemented by a sequence of graphics library procedures. Advantages and disadvantages of nonparallel mirror methods are discussed. *************** UCSC-CRL-93-23 (ONLY available electronically as ucsc-crl-93-23.ps.Z) PROVIDING PERFORMANCE GUARANTEES IN AN FDDI NETWORK Darrell D.E. Long, Carol Osterbrock, and Luis-Felipe Cabrera June 1993 Abstract: A network subsystem supporting a continuous media file system must guarantee a minimum, throughput, a maximum delay, and a maximum jitter. We present a transport protocol that provides these guarantees. To support different types of service, our protocol is built from modules selected to meet the requirements of each communications session. A buffering technique is used to provide jitter guarantees. To provide throughput and delay guarantees, network performance is optimized based on the required transfer rate. The effects of controlling transmission rate and packet size are presented. The resulting transport protocol is modeled on a simulated FDDI network and the results are analyzed. We show that the protocol provides the required guarantees for the anticipated types of traffic. *************** UCSC-CRL-93-24 (ONLY available electronically as ucsc-crl-93-24.ps.Z) DEBUGGING OPTIMIZED CODE WITHOUT BEING MISLED: CURRENCY DETERMINATION Max Copperman June 1993 Abstract: Correct optimization can change the behavior of an incorrent program, therefore at times it is necessary to debug optimized code. However, optimizing compilers produce code that impedes source-level debugging. Optimization can cause an inconsistency between where the user expects a breakpoint to be located and the breakpoint's actual location. This paper describes a mapping between statements and breakpoint locations that ameliorates this problem. The mapping enables debugger behavior on optimized code that approximates debugger behavior on unoptimized code sufficiently closely for the user to use traditional debugging strategies. Optimization can also cause the value of a variable to be noncurrent---to differ from the value that would be predicted by a close reading of the source code. This paper presents a method of determining when this has occurred, and shows how a debugger can describe the relevant effects of optimization. The determination method is more general than previously published methods; it handles global optimization and many flow graph transformations, and it is not tightly coupled to optimizations performed by a particular compiler. Necessary compiler support is also described. *************** UCSC-CRL-93-25 (Available electronically as ucsc-crl-93-25.ps.Z) A STUDY OF UNDETECTABLE NON-FEEDBACK SHORTS FOR THE PURPOSE OF PHYSICAL-DFT Richard McGowen and F. Joel Ferguson July 1993, 10 pages (Paper copy $5.00) Abstract: Undetectable shorts may decrease the long term reliability of a circuit, cause intermittent failures, add noise and delay, or increase test pattern generation costs. This paper describes the undetectable non-feedback shorts that are likely to occur in standard cell implementations of the ISCAS`85 combinational test circuits. For the MCNC implementation of the circuits, all shorts between adjacent wires were extracted and the undetectable ones analyzed. We found that approximately 0.2% are undetectable and that nearly half of these can be easily predicted before the physical layout of the circuit is generated. Since only a small percentage of the shorts are undetectable, and many of the undetectables are easily identifiable, it appears that it is possible to reduce the likelihood, or completely eliminate, the occurrence of a large portion of these shorts by incorporating design for test strategies into routing software. *************** UCSC-CRL-93-26 (ONLY available electronically as ucsc-crl-93-26.ps.Z) TYPE-SPECIFIC STORAGE MANAGEMENT Daniel Edelson (PH.D. Thesis) May 1993 Abstract: This dissertation explores the limits of integrating garbage collection (GC) and other memory management techniques into `industrial-strength' statically-typed object-oriented programming languages (OOPLs). GC cannot entirely replace man- ual reclamation in such languages. However, providing GC as an alternative has many benefits. We discuss various aspects of the integration of garbage collectors into programming languages such as C++. This thesis includes: - a comparison of the behavior of smart pointers with that of normal pointers, and examples of how smart pointers help integrate compiler- independent memory management algorithms into a program; - a presentation of fault interpretation, which is a technique for improv- ing certain algorithms (including some generational garbage collection algorithms) through a novel use of virtual memory protection, and, - a discussion of the memory management components we provide, which include: two garbage collectors, a precompiler and additional tools. *************** UCSC-CRL-93-27 (ONLY available electronically as ucsc-crl-93-27.ps.Z) TYPE-SPECIFIC STORAGE MANAGEMENT (shortened version) Daniel Edelson May 1993 This report is a shorter version of UCSC-CRL-93-26. Extensive source code in appendices is omitted from this version. *************** UCSC-CRL-93-28 (available electronically as ucsc-crl-93-28.ps.Z) SCATTERING PARAMETER TRANSIENT ANALYSIS OF INTERCONNECT NETWORKS WITH NONLINEAR TERMINATIONS USING RECURSIVE CONVOLUTION Haifang Liao and Wayne Wei-Ming Dai June 1993, 16 pages (Paper copy $5.00) Abstract: A novel method for analyzing interconnect networks with nonlinear terminations is presented. The circuit is partitioned into linear and nonlinear networks. A scattering parameter based macromodel is introduced to model the linear network. An efficient network reduction algorithm is developed to reduce the linear network into a network containing one multiport component (macromodel) together with sources and loads of interest. Exponentially Decayed Polynomial Functions (EDPF) are used to approximate the scattering parameters of the macromodel, which is always stable for stable circuits. In order to incorporate the macromodel into a SPICE like circuit simulator, a simplified recursive convolution formula is developed and Norton equivalent circuits are derived based on recursive convolution. Experiment results indicate that our method can approach the accuracy of SPICE3e2 with order of magnitudes less computing time. *************** UCSC-CRL-93-29 (available electronically as ucsc-crl-93-29.ps.Z) A CLASS OF SYNCHRONIZATION OPERATIONS THAT PERMIT EFFICIENT RACE DETECTION David P. Helmbold and Charles E. McDowell August 1993, 13 pages (Paper copy $5.00) Abstract: We present an efficient algorithm for ``precisely'' determining the possible alternate orderings of events from a program trace for a class of synchronization operations. The class includes, post and wait without clear, a restricted form of semaphores, and message passing where the sender names the receiver. The ordering information is precise in that a race detection system could be built using the ordering information such that if the program does not contain any data races for a given input, no races will be reported, and if the the program does contain data races, at least one of those races will be reported. *************** UCSC-CRL-93-30 (available electronically as ucsc-crl-93-30.ps.Z) WHAT IS A RACE IN A PROGRAM AND WHEN CAN WE DETECT IT? David P. Helmbold and Charles E. McDowell August 1993, 21 pages (Paper copy $6.00) Abstract: This paper presents a taxonomy of methods for detecting race conditions in parallel programs, shows how recent results fit into the taxonomy, and presents some new results for previously unexamined points in the taxonomy. It also presents a taxonomy of ``races'' and suggested terminology. *************** UCSC-CRL-93-31 (available electronically as ucsc-crl-93-31.ps.Z) CHARACTERIZATIONS OF LEARNABILITY FOR CLASSES OF {0,...,N}-VALUED FUNCTIONS Shai Ben-David, Nicolo Cesa-Bianchi, David Haussler, and Philip Long August 1993, 22 pages (Paper copy $6.00) Abstract: We investigate the PAC learnability of classes of {0,...,n}-valued functions. For n = 1 it is known that the finiteness of the Vapnik- Chervonenkis dimension is necessary and sufficient for learning. In this paper we present a general scheme for extending the VC-dimension to the case n > 1. Our scheme defines a wide variety of notions of dimension in which several variants of the VC-dimension, previously introduced in the context of learning, appear as special cases. Our main result is a simple condition characterizing the set of notions of dimension whose finiteness is necessary and sufficient for learning. This provides a variety of new tools for determining the learnability of a class of multi-valued functions. Our characterization is also shown to hold in the "robust" variant of PAC model and for any "reasonable" loss function. ************** UCSC-CRL-93-32 (available electronically as ucsc-crl-93-32.part1.ps.Z and ucsc-crl-93-32.part2.ps.Z) HIDDEN MARKOV MODELS IN COMPUTATIONAL BIOLOGY: APPLICATIONS TO PROTEIN MODELING Anders Krogh, Michael Brown, I. Saira Mian, Kimmen Sjolander, and David Haussler August 1993, 62 pages (Paper copy $10.00) Abstract: Hidden Markov Models (HMMs) are applied to the problems of statistical modeling, database searching and multiple sequence alignment of protein families and protein domains. These methods are demonstrated on the globin family, the protein kinase catalytic domain, and the EF-hand calcium binding motif. In each case the parameters of an HMM are estimated from a training set of unaligned sequences. After the HMM is built, it is used to search the SWISS-PROT 22 database for other sequences that are members of the given protein family, or contain the given domain. The HMM produces multiple alignments of good quality that agree closely with the alignments produced by programs that incorporate three-dimensional structural information. When employed in discrimination tests (by examining how closely the sequences in a database fit the globin, kinase and EF-hand HMMs), the HMM is able to distinguish members of these families from non-members with a high degree of accuracy. Both the HMM and PROFILESEARCH (a technique used to search for relationships between a protein sequence and multiply aligned sequences) perform better in these tests than PROSITE (a dictionary of sites and patterns in proteins). The HMM appears to have a slight advantage over PROFILESEARCH in terms of lower rates of false negatives and false positives, even though the HMM is trained using only unaligned sequences, whereas PROFILESEARCH requires aligned training sequences. Our results suggest the presence of an EF-hand calcium binding motif in a highly conserved and evolutionarily preserved putative intracellular region of 155 residues in the alpha-1 subunit of L-type calcium channels which play an important role in excitation-contraction coupling. This region has been suggested to contain the functional domains that are typical or essential for all L-type calcium channels regardless of whether they couple to ryanodine receptors, conduct ions or both. ************** UCSC-CRL-93-33 (available electronically as ucsc-crl-93-33.ps.Z) A HIDDEN MARKOV MODEL THAT FINDS GENES IN E. COLI DNA Anders Krogh, I. Saira Mian, and David Haussler April 1993, Revised May 1994, 24 pages (Paper copy $6.00) Abstract: A hidden Markov model (HMM) has been developed to find protein coding genes in E. coli DNA using E. coli genome DNA sequence from the EcoSeq6 database maintained by Kenn Rudd. This HMM includes states that model the codons and their frequencies in E. coli genes, as well as the patterns found in the intergenic region, including repetitive extragenic palindromic sequences and the Shine-Delgarno motif. To account for potential sequencing errors and or frameshifts in raw genomic DNA sequence, it allows for the (very unlikely) possiblity of insertions and deletions of individual nucleotides within a codon. The parameters of the HMM are estimated using approximately one million nucleotides of annotated DNA in EcoSeq6 and the model tested on a disjoint set of contigs containing about 325,000 nucleotides. The HMM finds the exact locations of about 80% of the known E. coli genes, and approximate locations for about 10%. It also finds several potentially new genes, and locates several places were insertion or deletion errors and or frameshifts may be present in the contigs. Based on further examination and analysis of the results from the parser, we describe a new putative S-adenosyl-L-methionine methyltransferase domain that appears to be present in proteins from a variety of phylogenetically diverse organisms and organelles. ************** UCSC-CRL-93-34 (available electronically as ucsc-crl-93-34.ps.Z) REINAS: REAL-TIME ENVIRONMENTAL INFORMATION NETWORK AND ANALYSIS SYSTEM: PHASE II REQUIREMENTS DEFINITION P.E. Mantey, J.J. Garcia-Luna, H.G. Kolsky, D.D.E. Long, A.T. Pang, E.C. Rosen, C. Tang, B.R. Montague, M. D. Abram, W.W. Macy, B.R. Gritton (MBARI), J. Padman, W. Nuss July 1993, 68 pages (Paper copy $10.00) Abstract: REINAS is a research and development program with the goal of designing, developing and testing an operational prototype system for data acquisition, data management, and visualization. This system is to support the real-time utilization of advanced instrumentation in environmental science where continuous time measurements and improved spatial resolution allow monitoring and understanding environmental phenomena in much greater detail than has previously been possible. The system will also support the retrospective use of integrated environmental data sets. The project is a multi-year effort of the Baskin Center for Computer Engineering and Information Sciences of the University of California, Santa Cruz, in cooperation with environmental scientists from the Naval Postgraduate School (NPS), Monterey Bay Aquarium Research Institute (MBARI), and the Center for Ocean Analysis and Prediction (NOAA/COAP). This report documents the second phase of the REINAS project during which detailed requirements for the system were defined. During this phase the user requirements for the system were sharpened, evaluations of the key components of the system were carried out, and selections of the technologies to be used in the prototype system were made. A project plan for the system is described along with a refined version of the architecture and its subsystems for data collection, data management, processing, and visualization. The objective of this document is to provide project participants and reviewers with a detailed requirements definition of REINAS as it enters the design and prototype implementation phase. It spells out the technologies to be applied, and the plans for implementing the project goals. ************** UCSC-CRL-93-35 (available electronically as ucsc-crl-93-35.ps.Z) EXTRACTING TIME-OF-FLIGHT DELAY FROM SCATTERING PARAMETER BASED MACROMODEL Haifang Liao and Wayne Wei-Ming Dai August 1993, 13 pages (Paper copy $5.00) Abstract: A novel and efficient method for transient analysis of interconnect systems is presented. The method is based on the scattering parameter technique. By extracting the propagation delay of the lossy transmission line and developing an efficient network reduction method, we compute the lower order model of the interconnect system for evaluating the exponentially charging time, keeping track of time-of-flight delay. The accuracy of the system response can be greatly improved from the extraction of the time-of-flight. ************** UCSC-CRL-93-36 (available electronically as ucsc-crl-93-36.ps.Z) WORST-CASE QUADRATIC LOSS BOUNDS FOR ON-LINE PREDICTION OF LINEAR FUNCTIONS BY GRADIENT DESCENT Nicolo Cesa-Bianchi, Philip M. Long, and Manfred K. Warmuth October 1993, 29 pages (Paper copy $6.00) Abstract: In this paper we study the performance of gradient descent when applied to the problem of on-line linear prediction in arbitrary inner product spaces. We show worst-case bounds on the sum of the squared prediction errors under various assumptions concerning the amount of a priori information about the sequence to predict. The algorithms we use are variants and extensions of on-line gradient descent. Whereas our algorithms always predict using linear functions as hypotheses, none of our results requires the data to be linearly related. In fact, the bounds proved on the total prediction loss are typically expressed as a function of the total loss of the best fixed linear predictor with bounded norm. All the upper bounds are tight to within constants. Matching lower bounds are provided in some cases. Finally, we apply our results to the problem of on-line prediction for classes of smooth functions. ************** UCSC-CRL-93-37 (available electronically as ucsc-crl-93-37.ps.Z) DATA FILTERING AND DISTRIBUTION MODELING ALGORITHMS FOR MACHING LEARNING Yoav Freund (Ph.D. Thesis) September 1993, 140 pages (Paper copy $15.00) Abstract: This thesis is concerned with the analysis of algorithms for machine learning. The main focus is on the role of the distribution of the examples used for learning. Chapters 2 and 3 are concerned with algorithms for learning concepts from random examples. Briefly, the goal of the learner is to observe a set of labeled instances and generate a hypothesis that approximates the rule that maps the instances to their labels. Chapter 2 describes and analyses an algorithm for improving the performance of a general concept learning algorithm by selecting those labeled instances that are most informative. This work is an improvement over previous work by Schapire. The analysis provides upper bounds on the time, space and number of examples that are required for concept learning. Chapter 3 is concerned with situations in which the learner can select, out of a stream of random instances, those for which it wants to know the label. We analyze an algorithm of Seung et.al. for selecting such instances, and prove that it is effective for the Perceptron concept class. Both Chapters 2 and 3 show situations in which a carefully selected exponentially small fraction of the random training examples are sufficient for learning. Chapter 4 is concerned with learning distributions of binary vectors. Here we present a new distribution model that can represent combinations of correlation patterns. We describe two different algorithms for learning this distribution model from random examples, and provide experimental evidence that they are effective. We conclude, in Chapter 5, with a brief discussion of the possible use of our algorithms in real world problems and compare them with classical approaches from pattern recognition. ************** UCSC-CRL-93-38 (available electronically as ucsc-crl-93-38.ps.Z) EXPLOITING THE PHYSICS OF STATE-SPACE SEARCH Robert Levinson October 1993, 12 pages (Paper copy $5.00) Abstract: This paper is a blueprint for the development of a fully domain-independent single agent and multi-agent heuristic search system. The paper gives a graph-theoretic representation of search problems based on conceptual graphs, and outlines two different learning systems. One, an ``informed learner" makes use of the the graph-theoretic definition of a search problem or game in playing and adapting to a game in the given environment. The other a ``blind learner" is not given access to the rules of a domain, but must discover and then exploit the underlying mathematical structure of a given domain. These learning agents are based on generalizing the understanding obtained with the Morph chess system to all games involving the interactions of abstract mathematical relations. Blind learner can be viewed as a type of neural network that makes explicit use of fuzzy graph-isomorphism to exploit at a ``meta-level" analogous states of the net itself. Publically available software has been developed for supporting research in blind learning and informed learning in the context of general problem-solving. The paper is based on studying the graph-theoretic structure of large open problems in machine learning research and giving a reasoned, unifying, framework for working toward their solution. In a field seeking comprehensive theories and general testbeds we hope that providing such a framework and software for exploration is an important contribution. The ultimate success of the framework awaits further investigation. ************** UCSC-CRL-93-39 (available electronically as ucsc-crl-93-39.ps.Z) TOWARDS DOMAIN-INDEPENDENT MACHINE INTELLIGENCE Robert Levinson November 1993, 13 pages (Paper copy $5.00) Abstract: Adaptive predictive search (APS), is a learning system framework, which given little initial domain knowledge, increases its decision-making abilities in complex problems domains. In this paper we give an entirely domain-independent version of APS that we are implementing in the PEIRCE conceptual graphs workbench. By using conceptual graphs as the ``base language" a learning system is capable of refining its own pattern language for evaluating states in the given domain that it finds itself in. In addition to generalizing APS to be domain-independent and CG-based we describe fundamental principles for the development of AI systems based on the structured pattern approach of APS. It is hoped that this effort will lead the way to a more principled, and well-founded approach to the problems of mechanizing machine intelligence. The APS framework has been applied to a number of complex problem domains (including chess, othello, pente and image alignment) where the combinatorics of the state space is large and the learning process only receives reinforcement at the end of each search. The unique features of the APS framework are its pattern-weight representation of control knowledge and its integration of several learning techniques including temporal difference learning, simulated annealing, and genetic algorithms. Morph, an APS chess sytem, is now being translated into PEIRCE. ************** UCSC-CRL-93-40 (available electronically as ucsc-crl-93-40.ps.Z) A STUDY OF THE RELIABILITY OF HOSTS ON THE INTERNET K. B. Sririam (Masters Thesis) June 1993, 55 pages (Paper copy $9.00) Abstract: This thesis is a study of the failure statistics of hosts on the Internet. To cross-verify our estimates of failure rates, we measure three different kinds of observations about hosts on the Internet - the time interval between failure, the number of failures in a certain time interval, and the length of time a host has been up at an arbitrary instant of time. These observations are made on different samples of hosts on the Internet. We present statistical results that allow us to derive estimates about the failure statistics of the population from these three different types of observations. The estimates from the three experiments are slightly different but comparable, providing three independent sources of evidence about the failure statistics of hosts on the Internet. We also attempt to explain the observations by modeling the statistical process with two distributions - the exponential and Weibull distribution. The observed data are explained well (in a statistical sense) by both models, but the Weibull model fits the observed sample better. We believe this to be evidence that the failure rates of hosts on the Internet are nearly constant, but with a high initial value that quickly decreases to a constant as the machine continues to run. ************** UCSC-CRL-93-42 (available by papercopy only) AN APPROACH TO THE DECOMPOSITION OF LARGE STOCHASTIC MODELS Alexandre Brandwajn September 1993, 12 pages (Paper copy $5.00) Abstract: A large family of decomposition methods largely used in the solution of queueing models divides the queueing model into smaller subsystems. The latter must be solved for all values of the state description retained for the aggregate model which represents the interactions among the subsystems. For a larger queueing system, even with relatively simple decomposed subsystems, this may represent a significant computational effort. The goal of our approach is to avoid the evaluation of the subnetworks for all values of the state description vector. Instead, we propose to track the probability distribution for the aggregate state description, and to evaluate the subnetwork in the regions where this probability exhibits a local maximum. In other regions, we propose to evaluate the subnetwork at only a few points. Outside the evaluation points, we use a simple curve fitting to generate the missing points. ************** UCSC-CRL-93-43 (available electronically as ucsc-crl-93-43.ps.Z) OPTIMAL DESIGN OF SELF-DAMPED LOSSY TRANSMISSION LINES FOR MULTICHIP MODULES Jimmy Shinn-Hwa Wang and Wayne Wei-Ming Dai October 1993, 22 pages (Paper copy $6.00) Abstract: This paper presents a simple and robust method of designing the lossy-transmission-line interconnects in a network for multichip modules. This paper is the first to identify that the performance-driven-layout optimal objective is to minimize both the maximum path delay and the maximum damping ratio together. The optimal performance is achieved entirely through wire-sizing on any general network which may contains loops. This method uses wire-sizing entirely to meet the electrical damping criteria to solve the problems encountered in propagating high-speed signals through unterminated lossy transmission lines on the substrates of multichip modules (MCM). The optimal design method is based on a new improved scattering-parameters (S-parameters) based macro-model of distributed-lumped networks that keeps track of the time-of-flight term in the transfer functions. The wire-sizing optimal design concept is to relate the layout parameter (line width) and the transfer function (damping ratio, and natural undamped frequency) to the signal propagation delay. The optimal design method results in fast and stable signal propagation for single-source multi-receiver networks on multichip modules without using termination resistors. Multi-receiver networks on High Performance MCM process technologies are designed for illustration. ************** UCSC-CRL-93-44 (available electronically as ucsc-crl-93-44.ps.Z) TRANSIENT ANALYSIS OF INTERCONNECTS WITH NONLINEAR DRIVER USING MIXED EXPONENTIAL FUNCTION APPROXIMATION Haifang Liao, Rui Wang, and Wayne Wei-Ming Dai October 1993, 16 pages (Paper copy $5.00) Abstract: This paper presents a new technique that can efficiently and accurately evaluate the timing response of high speed interconnects, of which transient analysis becomes ever more important with the higher circuit speeds and finer feature sizes. This method is based on the scattering parameter macromodel, whose transfer function will be approximated by a new approximation function called Mixed Exponential Function (MEF). By taking advantage of the best properties of Pade approximation and Exponentially Decayed Polynomial function, this method efficiently achieves high accuracy afforded by the former, and high stability by the latter. A driver model suitable for sub-micron CMOS design is also presented to incorporate the nonlinearity of the circuit elements. The interconnect macro model and the nonlinear driver model combined with the Mixed Exponential Function approximation provide accuracy comparable to that of SPICE at a speed one to two orders of magnitude faster. ************** UCSC-CRL-93-45 (available electronically as ucsc-crl-93-45.ps.Z) HIERARCHICAL CLOCK ROUTING SCHEME FOR MULTI-CHIP MODULES BASED ON AREA PAD INTERCONNECTION Qing Zhu and Wayne Wei-Ming Dai October 1993, 17 pages (Paper copy $5.00) Abstract: The flip-chip technology for multi-chip modules provides area pads through solder bumps which are distributed over the entire chip surface. Clock skew has been identified as one of major limiting factors for high speed VLSI systems. We propose a two level clock routing scheme for a MCM-packaged VLSI system by making use of area pads and high connectivity of MCM substrate. The die is partitioned small isochronal regions with a area pad assigned for each bin. We implement the clock network of the MCM system in two levels. A global clock network with longer wires is routed on the MCM substrate which connects the clock source of the module to all clock area pads of dice. Inside every isochronous bin of a die, a delay-bounded clock tree is constructed from clock pad to clocked elements. Experimental results show this two level clock routing scheme dramatically reduces the clock wires and achieves high clocking performance of the whole MCM system. ************** UCSC-CRL-93-46 (available electronically as ucsc-crl-93-46.ps.Z) TRANSIENT ANALYSIS OF INTERCONNECTS WITH NONLINEAR DRIVER USING MIXED EXPONENTIAL FUNCTION APPROXIMATION Haifang Liao, Rui Wang, and Wayne Wei-Ming Dai October 1993, 16 pages (Paper copy $5.00) Abstract: The timing-driven routing of a critical net can be implemented as a delay-bounded minimum Steiner tree. This routing tree has the path delays always limited no larger than a delay bound D, while the total wire length is minimized. The delay bound is usually specified at the system/logic design stage. The routing maintains this delay bound to guarantee the correct timing of the finally implemented system in physical layout. We propose a new algorithm of constructing delay bounded minimum Steiner tree. This algorithm is designed based on the observation that this tree can be obtained based on the trade-off between two other special types of Steiner tree: (1) minimum Steiner tree and (2) minimum path delay Steiner tree, by taking into account of a delay bound D. We also proposed a new algorithm of constructing the minimum delay Steiner tree. During the tree growing, the Elmore delay is incremently updated in constant time. These novel Steiner tree algorithms have been applied on a clock routing scheme for multi-chip modules based on area pad interconnections. ************** UCSC-CRL-93-47 (available electronically as ucsc-crl-93-47.ps.Z) SCALABLE PARALLEL DIRECT VOLUME RENDERING FOR NONRECTILINEAR COMPUTATIONAL GRIDS Judith Challinger (Ph.D. Thesis) November 1993, 144 pages (Paper copy $15.00) Abstract: Various approaches to the problem of parallelizing direct volume rendering algorithms are discussed, and a scalable approach to parallel direct volume rendering of nonrectilinear computational grids is presented. The algorithm is general enough to handle non-convex grids and cells, grids with voids, grids constructed from multiple grids (multi-block grids), and embedded geometrical primitives. The algorithm is designed for a highly parallel MIMD architecture which features both local memory and shared memory with non-uniform memory access times. It has beem implemented on a BBN TC2000 and benchmarked on several datasets. An analysis of the speedup and efficiency of the algorithm is given and any sources of inefficiency are indentified. The trade-off between load balancing requirements and the loss of coherence due to the image-space task decomposition is examined. A variation of the algorithm which provides fast image updated for a changing transfer function is also presented. A distributed approach to controlling the execution of the volume render is used and the graphical user interface designed for this purpose is briefly described. ************** UCSC-CRL-93-48 (available electronically as ucsc-crl-93-48.ps.Z) ELIMINATION OF UNDETECTABLE SHORTS DURING CHANNEL ROUTING Richard McGowen and F. Joel Ferguson November 1993, 12 pages (Paper copy $5.00) Abstract: In this paper we present a procedure for reducing the probability of undetectable shorts occurring in routing channels. This procedure is implemented by modifying a channel router to predict many of the shorts that are undetectable and place the associated signal wires in non-adjacent tracks. For the designs we routed, we found that the probability of an undetectable non-feedback short between horizontal lines in the routing channels was reduced by 32.4% with no increase in the number of routing tracks required and little increase in routing computation cost. ************** UCSC-CRL-93-49 (available electronically as ucsc-crl-93-49.ps.Z) AUTOMATED TERMINATION ANALYSIS FOR LOGIC PROGRAMS Kirack Sohn (Ph.D. Thesis) November 1993, 115 pages (Paper copy $14.00) Abstract: The question of whether logic programs with function symbols terminate in a top-down (Prolog-like) execution is considered. Automated termination analysis is an essential tool for generating a suitable control in modern deductive database systems, such as LDL and NAIL! We describe a method of identifying a nonnegative linear combination of bound argument sizes, which (if found) strictly decreases in a top-down execution of logic programs. Testing a termination condition is transformed to a feasibility problem of linear inequalities using duality theory of linear programming. For nontrivial termination proofs, we often need to know the relationship among argument sizes of a predicate. We formalize the relationship by a fixpoint of ``recursive transformation" mimicking immediate consequence operator. Since the transformation sometimes fails to finitely converge, we provide some practical techniques to resolve this problem. We also need to indicate which arguments are bound to ground terms during goal reduction. A method for deriving such binding information is described in the framework of abstract interpretation. Positive propositional formula are used to represent groundness dependency among arguments of a predicate. This methodology can handle nonlinear recursion, mutual recursion, and cases in which no specific argument is certain to decrease. Several programs that could not be shown to terminate by earlier published methods are handled successfully. ************** UCSC-CRL-93-50 (available electronically as ucsc-crl-93-50.ps.Z) SIMULATING NETWORK TRAFFIC IN AN ASSOCIATIVE PROCESSING ENVIRONMENT Claude S. Noshpitz (M.S. Thesis) December 1993, 53 pages (Paper copy $9.00) Abstract: This thesis considers issues related to the design of a distributed computing system optimized for research in the area of artificial intelligence applications. We introduce the Associative Processing Environment, a computing model explicitly designed to provide support at the machine level for systems that learn. Issues relating to the implementation of a multicomputer based on this model are discussed with a focus on the development of an effective processor interconnection network. We describe APES, a software tool for the simulation of message traffic in such a system, and present a series of experiments testing the behavior of a parallelized AI application on several topologies. We conclude that the behavior of the application is such that an assumption of uniformly distributed random traffic fails to capture essential aspects of the program's communication activity. ************** UCSC-CRL-93-51 (available electronically as ucsc-crl-93-51.ps.Z) LEARNING BINARY RELATIONS USING WEIGHTED MAJORITY VOTING Sally A. Goldman and Manfred K. Warmuth December 1993, 19 pages (Paper copy $5.00) Abstract: In this paper we apply a weighted majority voting algorithm to the problem of learning a binary relation between two sets of objects. When using exponentially many weights, the mistake bound of the algorithm is essentially optimal. We present a construction where a number of copies of our algorithm divide the problem amongst themselves and learn the relation cooperatively. In this construction the total number of weights is polynomial. The mistake bounds are non-optimal (at least when compared to the best bound obtainable when computational resources are ignored) but significantly improve previous mistake bound bounds achieved by polynomial algorithms. Moreover our method can handle noise, which widens the applicability of the results.