1992 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.1992 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-92-01 (available electronically as ucsc-crl-92-01.ps.Z) DEBUGGING OPTIMIZED CODE WITHOUT BEING MISLED Max Copperman March 1992, 40 pages (paper copy $8.00) 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. This mismatch may occur due to statement reordering and discontiguous code generated from a statement. 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 closely enough that the user need not make severe changes in debugging strategies. Another situation that can mislead the user is when optimization has caused 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 gives and proves 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. The information a compiler must make available to the debugger for this task is also described. Keywords: Categories and Subject Descriptors: D.2.5 [Software Engineering]: Testing and Debugging --- debugging aids; D.2.6 [Software Engineering]: Programming Environments; D.3.4 [Programming Languages]: Processors --- code generation, compilers, optimization General Terms: Algorithms, Languages Additional Keywords and Phrases: debugging, compiler optimization, reaching definitions, noncurrent variables *************** UCSC-CRL-92-02 (available electronically as ucsc-crl-92-02.ps.Z) EARLY SYSTEM ANALYSIS OF CACHE PERFORMANCE FOR RISC SYSTEMS: MCM DESIGN TRADE-OFFS James D. Roberts and Wayne W.-M. Dai March 1992, 50 pages (paper copy $9.00) Abstract: This report presents a prototype early analysis tool for exploring trade-offs in cache architecture and packaging and inter- connection (P/I) technology for RISC microprocessor based systems. We define early analysis as the evaluation of system trade-offs, including implementation technology effects, at pre-netlist phases of development. Prior work in cache performance estimation and P/I modeling are combined and extended to be more specific to RISC systems. After describing the model, several case studies are presented. Although limited by the accuracy of the first-order model as well as by assumptions and estimations regarding input data, these studies indicate general trends and quantify several important trade-offs for multi-chip model systems. MCM characteristics favor larger off-chip caches, with improved performance as well as yield advantages. When combined with flip-chip mounting, MCM technology also permits cache system architectural changes which can significantly improve perfor- mance. The prototype is not intended as a design tool, but rather to demonstrate the utility and importance of an interactive early analysis tool, combining architecture and implementation technology issues. Suggestions for future tool development are made. *************** UCSC-CRL-92-03 (available electronically as ucsc-crl-92-03.tar.Z) DESCRIPTIVE COMPLEXITY OF #P FUNCTIONS Sanjeev Saluja, K.V. Subrahmanyam, and Madhukar N. Thankur January 1992, 20 pages (paper copy $6.00) Abstract: 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 obtained in this way 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. These results set the foundation for further study of the descriptive complexity of the class #P. In contrast, we show, under reasonable complexity theoretic assumptions, that it is an undecidable problem to tell if a counting problem expressed in our framework is polynomial time computable or is approximable by a randomized polynomial time algorithm. Finally, we discuss some open problems which arise naturally from this work. *************** UCSC-CRL-92-04 (available electronically as ucsc-crl-92-04.ps.Z) A SIMULATION STUDY OF REPLICATION CONTROL PROTOCOLS USING VOLATILE WITNESSES Perry K. Slope, Jehan-Franc,ois Pa^ris, Darrell D.E. Long January 1992, 10 pages (paper copy $5.00) Abstract: Voting protocols guarantee the consistency of replicated data objects by disallowing all access requests that cannot gather a sufficient quorum of replicas. The performance of voting protocols can be greatly enhanced by adding to the replicas small independent entities that hold no data but can attest to the state of the replicated data object. It has been recently proposed to store these *witnesses* in volatile storage. Volatile witnesses respond faster to write requests than those stored in stable storage. They can also be more easily regenerated as many local area networks contain a majority of diskless sites. We present a simulation study of the availability afforded by two voting protocols using volatile witnesses and investigate the impact of access rates, network topology and witness placement on the availability of the replicated data. Keywords: replicated data management, replication control protocols, voting, witnesses, discrete event simulation. *************** UCSC-CRL-92-05 (not available electronically) INTERACTIVE LANGUAGE-BASED OBJECT MANIPULATION Sharon Rose Fischler and Jane Wilhelms February 1992, 17 pages (paper copy $5.00) Abstract: If a user were to imagine the most convenient method of manipulating objects, it would probably be language-based. However, natural language understanding is notoriously difficult for computers, and the difficulty is exacerbated in the case of computer graphics by the need for geometric output, not just ``conceptual'' understanding or high-level inferencing. General text understanding techniques have not been successfully generally applied to scene generation; more typically, a few task-specific commands, such as ``walk'', are implemented in detail and independently. We have chosen a more generalizable, bottom-up approach of developing a small natural class of commands useful for object manipulation. We believe this is a first step toward a much more natural method for object manipulation using computer graphics. Keywords: User interfaces, 3D workspaces, interactive computer graphics, 3D graphics, computer graphics methodology, virtual reality, real-time graphics. *************** UCSC-CRL-92-06 (available electronically as ucsc-crl-92-06.ps.Z) ROUTABILITY-DRIVEN TECHNOLOGY MAPPING FOR LookUp TABLE-BASED FPGAs Martine Schlag, Jackson Kong, and Pak K. Chan February 1992, 19 pages (paper copy $5.00) Abstract: A new algorithm for technology mapping of LookUp Table-based Field-Programmable Gate Arrays (FPGAs) is presented. It has the capability of producing slightly more *compact* designs (using less cells (CLBs)) than some existing mappers. More significantly, it has the flexibility of trading routability with compactness of a design. Research in this area has focussed on minimizing the number of cells. However, minimizing the number of cells without regard to routability is ineffective. Since placment and routing is really the most time-consuming part of the FPGA design process, producing a routable design with a slightly larger number of cells is preferable than producing a design using fewer cells which is difficult to route, or in the worst case unroutable. We have implemented our algorithm in the Rmap program, and studied routability of two other mappers with respect to Rmap in this paper. In general Rmap produces mappings with better routability characteristics, and more significantly Rmap produces routable mappings when other mappers do not. *************** UCSC-CRL-92-07 (not available electronically) AN ANALYSIS OF APPROACHES TO RAY-TRACING CURVILINEAR GRIDS Shankar Ramamoorthy and Jane Wilhelms April 1992, 25 pages (paper copy $6.00) Abstract: Curvilinear grids are composed of six-sided cells which may be considered as resulting from the deformation of a regular rectilinear grid. Unlike regular grids the cells may not be identical in shape, size or orientation. Such grids occur in areas such as computational fluid dynamics (CFD) and finite element methods. Direct volume rendering can be a useful tool for visualizing scalar data on curvilinear grids from CFD. It is possibly more desirable for such smoothly varying fields than isosurface methods that use binary thresholding. Volume rendering research has largely concentrated on rendering scalar fields on regular grids, and recent algorithms allow nearly interactive renderings on moderately sized volumes. These techniques do not readily carry over to rendering curvilinear grids. Curvilinear grids pose a number of challenges to a volume rendering algorithm. In this report, we discuss the problems of ray-casting curvilinear grids and present techniques for speedup at the expense of extra storage. *************** UCSC-CRL-92-08 (not available electronically) OPTICAL JUKEBOX RETRIEVAL PERFORMANCE IN ELECTRONIC LIBRARIES UTILIZING CYCLIC SCHEDULING David E. Levy and Patrick E. Mantey March 1992, 18 pages (paper copy$5.00) Abstract: The optical jukebox emerges as the economic choice for storing huge quantities of data objects in today's electronic libraries. Sequential access to collections in an electronic library with a very large number of holdings significantly limits library response when requests are frequent, as found in large-scale library systems. Therefore, we consider an alternative scheduling method which takes advantage of specific user and application characteristics found in a library environment. In this paper, we address the performance benefits of cyclic scheduling of user requests in electronic libraries where retrievals are the primary tasks. An approximate model of the retrieval performance is developed in terms of average waiting times for retrieval of objects from an optical jukebox using a cyclic service strategy. This model considers variability in service and its evaluation involves an iterative approach. In addition, the goal of the approximation is motivated by providing a user-interface prompt which indicates the expected waiting times for requested documents. *************** UCSC-CRL-92-09 (available electronically as ucsc-crl-92-09.ps.Z) USING DATA STRIPING IN A LOCAL AREA NETWORK Luis-Felipe Cabrera and Darrell D. E. Long March 1992, 22 pages (paper copy $6.00) Abstract: We use the technique of storing the data of a single object across several storage servers, called data striping, to achieve high transfer data rates in a local area network. Using parallel paths to data allows a client to transfer data to and from storage at a higher rate than that supported by a single storage server. We have imple- mented a network data service, called Swift, that uses data striping. Swift exhibits the expected scaling property in the number of storage servers connected to a network and in the number of interconnection networks present in the system. We have also simulated a version of Swift to explore the limits of possible future configurations. We observe that the system can evolve to support very high speed interconnection networks as well as large numbers of storage servers. Since Swift is a distributed system made up of independently replaceable components, any component that limits the performance can either be *replaced* by a faster component when it becomes available or can be *replicated* and used in parallel. This should allow the system to incorporate and exploit emerging storage and networking technologies. *************** UCSC-CRL-92-10 (available electronically as ucsc-crl-92-10.ps.Z) EXPERIENCE-BASED ADAPTIVE SEARCH Jeffrey Gould and Robert Levinson April 1992, 25 pages (paper copy $6.00) Abstract: This paper describes adaptive predictive search (APS), a learning system framework, which given little initial domain knowledge, increases its predictive abilities in complex problems domains. APS systems are termed experience-based learners because they are given as much responsibility for the learning process as possible. This framework has been applied to a number of complex 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. In addition to APS, Morph, an APS chess system, is described in detail. Through training, despite little initial domain knowledge and using only one ply of search, Morph has managed several dozen draws and two wins against a traditional search based chess program stronger than most tournament players. Keywords: machine learning, integrated learning systems, pattern induction, genetic algorithms, temporal-difference learning. *************** UCSC-CRL-92-11 (available electronically as ucsc-crl-92-11.ps.Z) OPTIMAL DESIGN OF SELF-DAMPED LOSSY TRANSMISSION LINES IN A TREE NETWORK FOR MULTICHIP MODULE Jimmy S.-H. Wang and Wayne W.-M. Dai April 1992, revised December 1992, 19 pages (paper copy $5.00) Abstract: This paper addresses some of the problems encountered in propagating high-speed signals through lossy transmission lines on the substrates of silicon-on-silicon thin-film multichip modules (MCM). Instead of terminated by resistors, the lossy lines on the thin-film multichip modules can be structured to critically damp out the signal resonances, they are thus called *optimal, self-damped lossy transmission lines*. It is easiest to manufacture interconnection lines with fixed metal and dielectric thicknesses, and vary only the line width. This results in specific dependency of line width on length for self-damped lines. In this paper, we present the a simple and robust method of designing self-damped lossy transmission lines in a tree network for multichip module. We vary the width of each branch of the network to meet certain electrical damping criteria. This results in stable operation as long as the lossy transmission line is shorter than the quarter wave length of the highest frequency component of interests. The lengths of lines on the silicon-on-silicon thin-film MCM substrate usually does not exceed this limit. If certain designs require larger substrate or higher speed, the materials and structural properties of the substrate (for example the dielectric thickness) is changed according to the method. Keywords: transmission line, lossy, self-damped, critical damped, multichip module, multi-terminal network, distributed termination. *************** UCSC-CRL-92-13 (available electronically as ucsc-crl-92-13.ps.Z) GROUP MEMBERSHIP IN THE EPIDEMIC STYLE Richard A. Golding and Kim Taylor (supersedes UCSC-CRL-91-32) March 1992, 12 pages (paper copy $5.00) Abstract: Existing group membership mechanisms provide consistent views of membership changes. However, they require heavyweight synchronous multicast protocols. We present a new lightweight group membership mechanism that allows temporary inconsistencies in membership views. This mechanism uses *epidemic communication* techniques to ensure that all group members eventually converge to a consistent view of membership. Members can join or leave groups, and we show that the mechanism is resilient to k <= n - 2 members failing by crashing, where n is the number of members in the group. Keywords: group membership, distributed systems, weak consistency replication. *************** UCSC-CRL-92-14 (available electronically as ucsc-crl-92-14.ps.Z) A REPLICATED MONITORING TOOL Darrell D. E. Long August 1992, 4 pages (paper copy $5.00) Abstract: Modeling the reliability of distributed systems requires a good understanding of the reliability of the components. Careful modeling allows highly fault-tolerant distributed applications to be constructed at the least cost. Realistic estimates can be found by measuring the performance of actual systems. An enormous amount of information about system performance can be acquired with no special privileges via the Internet. A distributed monitoring tool called a tattler is described. The system is composed of a group of tattler processes that monitor a set of selected hosts. The tattlers cooperate to provide a fault-tolerant distributed data base of information about the hosts they monitor. They use weak-consistency replication techniques to ensure their own fault-tolerance and the eventual consistency of the data base that they maintain. *************** UCSC-CRL-92-15 (available electronically as ucsc-crl-92-15.ps.Z) SORTING AND SEARCHING WITH A FAULTY COMPARISON ORACLE Philip M. Long May 1992, revised November 1992, 6 pages (paper copy $5.00) Abstract: We study sorting and searching using a comparison oracle that ``lies.'' First, we prove that an algorithm of Rivest, Meyer, Kleitman, Winklmann and Spencer for searching in an n-element list using a comparison oracle that lies E times requires at most O(log n + E) comparisons, improving the best previously known bound of log n + E log log n + O(E log E). A lower bound, easily obtained from their results, establishes that the number of comparisons used by their algorithm is within a constant factor of optimal. We apply their search algorithm to obtain an algorithm for sorting an n element list with E lies that requires at most O(n log n + En) comparisons, improving on the algorithm of Lakshmanan, Ravikumar and Ganesan, which required at most O(n log n + En + E^2) comparisons. A lower bound proved by Lakshmanan, Ravikumar and Ganesan establishes that the number of comparisons used by our sorting algorithm is optimal to within a constant factor. *************** UCSC-CRL-92-19 (available electronically as ucsc-crl-92-19.ps.Z) SPECTRAL K-WAY RATIO-CUT PARTITIONING -- PART I: PRELIMINARY RESULTS Pak K. Chan, Martine Schlag and Jason Zien May 1992, 12 pages (paper copy $5.00) Abstract: Recent research on partitioning has focussed on the ratio-cut cost metric which maintains a balance between the sizes of the edges cut and the sizes of the partitions without fixing the size of the partitions a priori. Iterative approaches and spectral approaches to two-way ratio-cut partitioning have yielded higher quality partitioning results. In this paper we develop a spectral approach to multi-way ratio-cut partitioning which provides a generalization of the ratio-cut cost metric to k-way partitioning and a lower bound on this cost metric. Our approach uses Lanczos algorithm to find the k smallest eigenvalue/eigenvector pairs of the Laplacian of the graph. The eigenvectors are used to construct an orthogonal projection to map a vertex (of the graph) in an n-dimensional space into a k-dimensional subspace. We exploit the (near) orthogonality of the projected points to effect high quality clustering of points in a k-dimensional subspace. An efficient algorithm is presented for coercing the points in the k-dimensional subspace into k-partitions. Advancement over the current work is evidenced by the results of experiments on the standard MCNC benchmarks. *************** UCSC-CRL-92-21 (ONLY available electronically, as ucsc-crl-92-21.ps.Z) AUTOMATIC PROCESS SELECTION FOR LOAD BALANCING William Osser (M.S. Thesis) June 1992 (No paper copies available.) Abstract: Distributed operating systems give users access to multiple computational engines throughout the system network. Users of one workstation are not hindered by the CPU intensive applications run on a different workstation. However, when a large number of machines in the network are idle, the efficiency of computation is decreased. Load balancing promises to alleviate this problem by sharing the workload on heavily loaded workstations with lightly loaded workstations. A threshold can be established so that only a limited number of processes are transferred to the lightly loaded sites, so that the load at those sites does not inhibit local execution of processes. While load balancing has been studied extensively, there have been few studies on determining which processes should be relocated to increase the throughput of the system. We present an automatic process selector for load balancing that chooses processes to be relocated based on the history of its performance. We have implemented this system on the Sprite distributed operating system. *************** UCSC-CRL-92-22 (available electronically as ucsc-crl-92-22.ps.Z) TOWARDS A MORE COMPREHENSIVE THEORY OF LEARNING IN COMPUTERS Philip M. Long (Ph.D. thesis) June 1992, 108 pages (paper copy $14.00) Abstract: We attempt to determine the theoretical boundaries of the ability of computers to learn. We consider several rigorous models of learning, aimed at addressing types of learning problems excluded from earlier models. In Part I, we consider learning dependencies between real-valued quantities in situations where the environment is assumed to be an adversary, operating within constraints that model the prior knowledge of the learner. While our assumptions as to the form of these dependencies is taken from previous work in statistics, this work is distinguished by the fact that the analysis is worst case. In Part II, we consider learning in situations in which the learner's enviroment is assumed to be at least partially random. We consider methods for extending the tools for learning {0,1}-valued functions to apply to the learning of many-valued and real-valued functions. We also study the learning of {0,1}-valued functions in situations in which the relationship to be learned is gradually changing as learning is taking place. *************** UCSC-CRL-92-23 (available electronically as ucsc-crl-92-23.ps.Z) PROTEIN MODELING USING HIDDEN MARKOV MODELS: ANALYSIS OF GLOBINS David Haussler, Anders Krogh, Saira Mian, Kimmen Sjolander. June 1992, revised Sept. 1992, 24 pages (paper copy $6.00) Abstract: We apply Hidden Markov Models (HMMs) to the problem of statistical modeling and multiple sequence alignment of protein families. A variant of the Expectation Maximization (EM) algorithm known as the Viterbi algorithm is used to obtain the statistical model from the unaligned sequences. In a detailed series of experiments, we have taken 400 unaligned globin sequences, and produced a statistical model entirely automatically from the primary (unaligned) sequences. We use no prior knowledge of globin structure. Using this model, we obtained a multiple alignment of the 400 sequences and 225 other globin sequences that agrees almost perfectly with a structural alignment by Bashford et al. This model can also discriminate all these 625 globins from nonglobin protein sequences with greater than 99% accuracy, and can thus be used for database searches. *************** UCSC-CRL-92-24 (available electronically as ucsc-crl-92-24.ps.Z) A FURTHER NOTE ON HENNESSY'S ``SYMBOLIC DEBUGGING OF OPTIMIZED CODE'' Max Copperman and Charles E. McDowell (supersedes 91-04) [To appear in TopLas.] April 1992, 9 pages (paper copy $5.00) Abstract: When attempting to debug optimized programs, most debuggers may give misleading information about the value of variables at breakpoints. Hennessy proposed a set of algorithms for generating optimized code and determining when, in the generated code, the reported values would be misleading, and under certain circumstances actually recovering the ``expected'' value of the variable (i.e., one that would not be misleading). We point out where the assumptions made by Hennessy need to be revised due to advances in compiler and debugger technology, and give references for current work on this revised problem. *************** UCSC-CRL-92-25 (available electronically as ucsc-crl-92-25.ps.Z) PRODUCING AN ACCURATE CALL-STACK TRACE IN THE OCCASIONAL ABSENCE OF FRAME POINTERS (supersedes 90-62) Max Copperman March 1992, 16 pages (paper copy $5.00) Abstract: An interactive debugger should be able to provide a call-stack trace, listing active subroutines in reverse order of their invocations. This facility relies on information provided by code within each called routine. This paper describes alternative ways to support this facility in the circumstance that this code is optimized away. Categories and Subject Descriptors: D.2.5 [Software Engineering]: Testing and Debugging --- *debugging aids*; D.2.6 [Software Engineering]: Programming Environments; D.3.4 [Programming Languages]: Processors --- *code generation, compilers, optimization*. General Terms: Algorithms, Languages. Additional Keywords and Phrases: debugging, compiler optimization, call-stack trace, run-time stack. *************** UCSC-CRL-92-26 (available electronically as ucsc-crl-92-26.ps.Z) END-TO-END PERFORMANCE PREDICTION FOR THE INTERNET (work in progress) Richard A. Golding June 1992, 29 pages (paper copy $6.00) Abstract: Many applications designed for wide-area systems use replication to provide a service at multiple locations. From which site should a client choose to obtain service? A client can specify its needs in terms of communication latency, bandwidth, or error rate. This specification must be matched against the expected performance available from each site. I present the results of two experiments that measured end-to-end performance, and discuss how the results can be used for prediction. *************** UCSC-CRL-92-27 (available electronically as ucsc-crl-92-27.ps.Z) SMART POINTERS: THEY'RE SMART, BUT THEY'RE NOT POINTERS Daniel R. Edelson June 1992, 22 pages (paper copy $6.00) Abstract: There are numerous times when a C++ user could benefit from a pointer variant that has more functionality than is provided by the basic, language-defined pointer. For example, type-accurate garbage collection, reference counting, or transparent references to distributed or persistent objects, might be implemented with classes that provide pointer functionality. The C++ language directly supports one kind of pointer substitute, the smart pointer, in the form of overloadable indirection operators: -> and *. In this paper we evaluate how *seamlessly* smart pointers can replace raw pointers. The ideal is for client code not to care whether it is using raw pointers or smart pointers. For example, if a typedef selects whether raw or smart pointers are used throughout the program, changing the value of the typedef should not introduce syntax errors. Unfortunately, C++ does not support pointer substitutes well enough to permit seamless integration. This paper presents the desired behavior of smart pointers in terms of the semantics of raw pointers that the smart pointers try to emulate. Then, we describe several ways of implementing smart pointers. For each, we show cases in which the smart-pointers fail to behave like raw pointers. From among the choices, we explain which is the best for emulating the standard pointer conversions. *Accessors* are similar to smart pointers, but have certain advantages. This paper discusses the differences between accessors and smart pointers, and shows why our conclusions about type conversion behavior also apply to accessors. Whether a programmer prefers smart pointers or accessors, this paper shows the limitations and recommends an implementation. *************** UCSC-CRL-92-28 (available electronically as ucsc-crl-92-28.ps.Z) PRECOMPILING C++ FOR GARBAGE COLLECTION Daniel R. Edelson June 1992, 21 pages (paper copy $6.00) Abstract: Our research is concerned with compiler-independent, efficient and convenient garbage collection for C++. Most collectors proposed for C++ have either been implemented in a library or in a compiler. As an intermediate step between those two, this paper proposes using precompilation techniques to augment a C++ source program with code to allow mostly type-accurate garbage collection. There are two key precompiler transformations. The first is automatic generation of *smart pointer* classes. The precompiler defines the smart pointer classes and the user utilizes them instead of raw pointers. These smart pointers supply functionality that allows the collector to locate the root set for collection. The second transformation augments the C++ program with code that allows the garbage collector to locate internal pointers within objects. This paper describes the precompiler and the garbage collector. The paper includes a brief (1500 word) survey of related techniques. *************** UCSC-CRL-92-30 (available electronically as ucsc-crl-92-30.ps.Z) THE PERFORMANCE OF WEAK-CONSISTENCY REPLICATION PROTOCOLS Richard A. Golding and Darrell D. E. Long July 1992, 9 pages (paper copy $5.00) Abstract: Weak-consistency replication protocols can be used to build wide-area services that are scalable, fault-tolerant, and useful for mobile computer systems. We have developed the *timestamped anti-entropy* protocol, which provides reliable eventual delivery with a variety of message orderings. Pairs of replicas periodically exchange update messages; in this way updates eventually propagate to all replicas. In this paper we present a detailed analysis of the fault tolerance and the consistency provided by this protocol. The protocol is extremely robust in the face of site and network failure, and it scales well to large numbers of replicas. *************** UCSC-CRL-92-31 (available electronically as ucsc-crl-92-31.ps.Z) A WEAK-CONSISTENCY ARCHITECTURE FOR DISTRIBUTED INFORMATION SERVICES Richard A. Golding July 1992, 17 pages (paper copy $5.00) Abstract: Services provided on wide-area networks like the Internet present several challenges. The reliability, performance, and scalability expected of such services often requires they be implemented using multiple, replicated servers. One possible architecture implements the replicas as a {\em weak-consistency process group.} This architecture provides good scalability and availability, handles portable computer systems, and minimizes the effect of users on each other. The key principles in this architecture are component independence, a process group protocol that provides small summaries of database contents, caching database {\em slices}, and the {\em quorum multicast} client-to-server communication protocol. A distributed bibliographic database system serves as an example. *************** UCSC-CRL-92-32 (available electronically as ucsc-crl-92-32.ps.Z) FAULT INTERPRETATION: FINE-GRAIN MONITORING OF PAGE ACCESSES Daniel R. Edelson July 1992, revised November 1992, 19 pages (paper copy $5) Abstract: This paper presents a technique for obtaining fine-grain information about page accesses from standard virtual memory hardware and UNIX operating system software. This can be used to monitor all user-mode accesses to specified regions of the address space of a process. Application code can intervene before and/or after an access occurs, permitting a wide variety of semantics to be associated with memory pages. The technique facilitates implementing complex replication or consistency protocols on transparent distributed shared memory and persistent memory. The technique can also improve the efficiency of certain generational and incremental garbage collection algorithms. This paper presents our implementation and suggest several others. Efficiency measurements show faults to be about three orders of magnitude more expensive than normal memory accesses, but two orders of magnitude less expensive than page faults. Information about how to obtain the code via anonymous ftp appears at the end of the paper. ************** UCSC-CRL-92-34 (ONLY available electronically as ucsc-crl-92-34.ps.Z) CENSUS: COLLECTING HOST INFORMATION ON A WIDE-AREA NETWORK Nitin K. Ganatra (B.A. Thesis) June 1992, 47 pages (No paper copies available.) Abstract: The exponential growth of the Internet presents new problems in recording global network information. The Domain Name System provided a way to cope with the enormous growth rates by distributing network information among all domains. This distribution accomplished its goal of eliminating the need for a central database, but at the same time eliminated the source of centralized network information. Such information is useful in applications dealing with resource discovery on the Internet and in studies of the network topography. Census is a program to traverse the Internet domain tree and collect information by recursively querying name servers for host information and other sub-domains. During the development of the Census program (about 6 months), the host population of the Internet has grown in size by 30 percent, and has showed no sign of abating. ************** UCSC-CRL-92-35 (available electronically as ucsc-crl-92-35.ps.Z) DYNAMIC CONSTRAINED DELAUNEY TRIANGULATION AND APPLICATION TO MULTICHIP MODULE LAYOUT Yizhi Lu (M.S. Thesis) December 1991, 46 pages (paper copy $8.00) Abstract: The *Voronoi diagram* is a partition of a set S of N points in a plane, such that each region is the locus of the points (x, y) closer to a point of S than to any other point of S. If no four points are co-circular, the *Delaunay triangulation* is the straight-line dual of the Voronoi diagram. The triangulation may be *constrained*, that is, a set of straight-line segments may be prespecified. This thesis presents some characteristics of constrained Delaunay triangulation and introduces a set of numerically stable algorithms for incremently constructing and updating constrained Delaunay triangulation. The dynamic constrained Delaunay triangulation algorithms have been implemented in a layout system for multichip modules. It has been used as the underlying data representation for rubber-band sketch, a topological routing for one layer. We have proved the O(n log n) expected running time for the Delauney triangulation algorithm. Keywords: Voronoi diagram, Delaunay triangulation, constrained Delauney triangulation, layout, multichip module, topological routing. ************** UCSC-CRL-92-36 (available electronically as ucsc-crl-92-36.ps.Z) MULTI-LEVEL HIERARCHICAL RETRIEVAL Robert Levinson and Gerard Ellis July 1992, 20 pages (paper copy $5.00) Abstract: As large databases of conceptual graphs are developed for complex domains, efficient retrieval techniques must be developed to manage the complexity of graph-matching while maintaining reasonable space requirements. This paper describes a novel method ``the multi-level hierarchical retrieval method" that exploits redundancy to improve both space and execution time efficiency. The method involves search in multiple partially ordered (by ``more-general-than") hierarchies such that search in a simpler hierarchy reduces the search time in the hierarchy of next complexity. The specific hierarchies used are: the traditional partial order over conceptual graphs; a partial order over node descriptors; a partial order over ``descriptor units"; and finally, the simplest partial order is the traditional type hierarchy. ************** UCSC-CRL-92-37 (available electronically as ucsc-crl-92-37.ps.Z) HOW WELL DO BAYES METHODS WORK FOR ON-LINE PREDICTION OF {+- 1} VALUES? David Haussler and A. Barron July 1992, 28 pages (paper copy $6.00) Abstract: We look at sequential classification and regression problems in which {+- 1}-labeled instances are given on-line, one at a time, and for each new instance, before seeing the label, the learning system must either predict the label, or estimate the probability that the label is +1. We look at the performance of Bayes method for this task, as measured by the total number of mistakes for the classification problem, and by the total log loss (or information gain) for the regression problem. Our results are given by comparing the performance of Bayes method to the performance of a hypothetical "omniscient scientist" who is able to use extra information about the labeling process that would not be available in the standard learning protocol. The results show that Bayes methods perform only slightly worse than the omniscient scientist in many cases. These results generalize previous results of Haussler, Kearns and Schapire, and Opper and Haussler. ************** UCSC-CRL-92-38 (available electronically as ucsc-crl-92-38.ps.Z) BOUNDS ON APPROXIMATE STEEPEST DESCENT FOR LIKELIHOOD MAXIMIZATION IN EXPONENTIAL FAMILIES Nicolo` Cesa-Bianchi, Anders Krogh, and Manfred K. Warmuth October 1992, 7 pages (paper copy $5.00) Abstract: An approximate steepest descent strategy converging, in families of regular exponential densities, to maximum likelihood estimates of density functions is described. These density estimates are also obtained by an application of the principle of minimum relative entropy subject to empirical constraints. We prove tight bounds on the increase of the log-likelihood at each iteration of our strategy for families of exponential densities whose log-densities are spanned by a set of bounded basis functions. Keywords: exponential families, minimum relative entropy estimation, steepest descent. ************** UCSC-CRL-92-39 (available electronically as ucsc-crl-92-39.ps.Z) GEOMETRIC TRANSFORMATIONS FOR A RUBBER-BAND SKETCH David Joseph Staepelaere (M.S. Thesis) September 1992, 63 pages (paper copy $10.00) Abstract: The flexible rubber-band sketch is a useful representation for routing interconnect. In addition to supporting an incremental design style, rubber-bands provide a flexible framework for generating layout under performance constraints. However, due to reasons of compatibility between CAD tools, it may be necessary at times to convert a rubber-band sketch to a more restricted geometry such as rectilinear or octilinear wiring. This paper presents an efficient method, based on the enhanced plane sweep, for converting a rubber- band sketch to a topologically equivalent rectilinear or octilinear wiring with minimum wire length. A sketch with n rubber-band segments can be converted to a restricted geometry with m segments in O(n \log n + m) time. In addition to guaranteeing minimum wire length, the technique uses heuristic methods to reduce the total number of jogs. ************** UCSC-CRL-92-40 (available electronically, as ucsc-crl-92-42.tar.Z) WAVE SPREADING EVALUATION OF INTERCONNECT SYSTEMS Haifang Liao and Wayne Wei-Ming Dai October 1992, 19 pages (paper copy $5.00) Abstract: With continual progress in integrated circuit processing, operating speeds and new technologies are emerging. The accurate high frequency analysis is needed to design the high performance system. This paper derives general multiport interconnect constraints and presents a new approach -- Wave Spreading Evaluation (WSE) which uses S-parameters based network techniques to analyze coupled, multiconductor, high speed analog and digital integrated circuit interconnect systems. WSE is based on the spreading process of voltage waves, the input sources are transformed into initial spreading waves. The spreading process is independent of input sources, and every step of wave spreading meets the constraints of KCL and KVL, the convergence condition is always met for passives network. The continual spreading of voltage waves will create accurate results. Keywords: scattering parameter, multiport component, multiport interconnect node, wave spreading. ************** UCSC-CRL-92-42 (available electronically, as ucsc-crl-92-42.ps.Z) EVIDENCE FOR A SATISFIABILITY THRESHOLD FOR RANDOM 3CNF FORMULAS Tracy Larrabee and Yumi Tsuji November 1992, 9 pages (paper copy $5.00) Abstract: This paper presents empirical evidence of a satisfiability threshold in random 3CNF formulas. The paper also expands on and supports the conjecture of Mitchell, Selman, and Levesque that *hard* randomly generated CNF formulas will be hard for any reasonable satisfiability algorithm. We report statistics for a much larger set of variables than have been previously reported; in particular, we show that for each clause to variable ratio less than 4.2, the percentage of satisfiable formulas increases, and for each clause to variable ratio greater than 4.2, the percentage of satisfiable formulas decreases as a function of number of variables. We found that several algorithms behaved qualitatively in the same fashion. We report on the relative performance of each algorithm. Keywords: backtracking, logic, reasoning, satisfiability, threshold behavior. **************** UCSC-CRL-92-43 (available electronically as ucsc-crl-92-43.ps.Z) S-PARAMETER BASED MACRO-MODEL OF DISTRIBUTED-LUMPED NETWORKS USING PADE' APPROXIMATION Haifang Liao, Rui Wang, Rajit Chandra, and Wayne Dai October 1992, 17 pages (paper copy $5.00) Abstract: A Scattering-Parameters (S-Parameters) based macromodel of distributed-lumped networks is presented, The networks can include capacitive cutsets, inductive loops, RLC meshes, and lossy transmission lines. An efficient network reduction algorithm is developed to reduce the original network into a network containing one multiport component together with the sources and loads of interest. The S-Parameters of the circuit components are approximated by Taylor series to simplify the reduction process. Pade' approximation is used to derive the macromodel. The macromodel is very flexible that the accuracy of the model can be controlled by adjusting the order of approximation. The experimental results indicate that our model can approach the accuracy of SPICE with one or two order less computing time. Keywords: scattering parameter, macromodel, multiport component, multiport interconnect node, component merging, network reduction, capacitive cutsets, inductive loops, RLC meshes, lossy transmission line, delay, Taylor series, and Pade' approximation ************** UCSC-CRL-92-45 (only available electronically, as ucsc-crl-92-45.ps.Z) DESIGN CHOICES FOR WEAK-CONSISTENCY GROUP COMMUNICATION Richard A. Golding and Darrell D. E. Long October 1992 Abstract: Many wide-area distributed applications can be implemented using distributed group communication, a mechanism for coordinating the activities of related processes running at different sites. We have developed a modular architecture for group communication systems that can be used to build a system tailored to application requirements. We focus on *weak consistency* mechanisms for group communication, since these allow highly efficient operation on wide-area internetworks. We examine several design choices that can be made in building a weakly-consistent group communication mechanism, and discuss the decisions we made in building two very different wide-area applications. The architecture accommodates both systems well, and allows several application-specific decisions that increase efficiency and flexibility. Keywords: group membership, weak consistency replication, mobile computing systems, bibliographic databases, reliability measurements ************** UCSC-CRL-92-46 (available electronically, as ucsc-crl-92-46.ps.Z) SOME FUTURE DIRECTIONS IN FAULT MODELING AND TEST PATTERN GENERATION RESEARCH F. Joel Ferguson and Tracy Larrabee October 1992, 22 pages (paper copy $6.00) Abstract: This document presents the current state of fault modeling research and lists research options that leverage the Carafe-Nemesis software packages and the knowledge gained from their use. ************** UCSC-CRL-92-47 (available electronically, as ucsc-crl-92-47.ps.Z) [92-47 is also available as directory ~ftp/pub/karplus/ucsc-report.tar.Z. This tarred directory has the .ps file of the report itself, plus all relevant .tex, .bib, .doc, .sty files, as well as makeindex, the awk file, dummy-thesis, etc.] USING THE ucsc-report LaTeX STYLE FILE FOR UCSC TECHNICAL REPORTS Kevin Karplus October 1992, 25 pages (paper copy $6.00) Abstract: This technical report describes how to use LaTeX to produce technical reports in the proper format for the UCSC Baskin Center for Computer Engineering and Informaiton Sciences series. The style file can also be used for various other reports and articles, including theses in a format acceptable to the UCSC Division of Graduate Studies. Two other style files are described: *ucletter* for business letters that generate University of California letterhead and *handout* for class handouts. The report itself is written using the *ucsc-report* style file, so that the .tex file can be used as an example file. The reader is expected to refer to Lamport's manual [Lamport, 1986] and to the local guide [Computer Engineering, 1990] for details on how to use LaTeX. Keywords: LaTeX, typesetting, document compiler, *ucsc-report*, *ucletter*, handout style file. ************** UCSC-CRL-92-48 (available electronically, as ucsc-crl-92-48.tar.Z) S-PARAMETER BASED MACRDO MODEL OF DISTRIBUTED-LUMPED NETWORKS USING EXPONENTIALLY DECAYED POLYNOMIAL FUNCTION Haifang Liao, Wayne Wei-Ming Dai, Rui Wang, and Fung-Yuel Chang November 1992, 20 pages (paper copy $5.00) Abstract: A Scattering-Parameters (S-Parameters) based macromodel of distributed-lumped networks is presented. The networks can include capacitive cutsets, inductive loops, RLC meshes, and loss transmission lines. An efficient network reduction algorithm is developed to reduce the original network into a network containing one multiport component together with the sources and loads of interest. The S-Parameters of the circuit components are approximated by Taylor series to simplify the reduction process. Exponentially Decayed Polynomial Function (EDPF) approximation is used to derive the macromodel, the higher accuracy can be obtained by selecting time constant according to an error criterion. The macromodel is always stable for a stable system and very flexible that the accuracy of the model can be controlled by adjusting the order of approximation. The experimental results indicate that our model can approach the accuracy of SPICE with one or two order less computing time. Keywords: scattering parameter, macromodel, multiport component, multiport interconnect node, component merging, network reduction, capacitive cutsets, inductive loops, RLC meshes, lossy transmission line, delay and Taylor series. ************** UCSC-CRL-92-52 (ONLY available electronically, as ucsc-crl-92-52.ps.Z) WEAK-CONSISTENCY GROUP COMMUNICATION AND MEMBERSHIP Richard Andrew Golding (Ph.D. dissertation) December 1992 Abstract: Many distributed systems for wide-area networks can be built conveniently, and operate efficiently and correctly, using a *weak consistency group communication* mechanism. This mechanism organizes a set of *principals* into a single logical entity, and provides methods to multicast messages to the members. A weak consistency distributed system allows the principals in the group to differ on the value of shared state at any given instant, as long as they will eventually converge to a single, consistent value. A group containing many principals and using weak consistency can provide the reliability, performance, and scalability necessary for wide-area systems. I have developed a framework for constructing group communication systems, for classifying existing distributed system tools, and for constructing and reasoning about a particular group communication model. It has four components: message delivery, message ordering, group membership, and the application. Each component may have a different implementation, so that the group mechanism can be tailored to application requirements. The framework supports a new message delivery protocol, called *timestamped anti-entropy*, which provides reliable, eventual message delivery; is efficient; and tolerates most transient processor and network failures. It can be combined with message ordering implementations that provide ordering guarantees ranging from unordered to total, causal delivery. A new group membership protocol completes the set, providing temporarily inconsistent membership views resilient to up to k simultaneous principal failures. The Refdbms distributed bibliographic database system, which has been constructed using this framework, is used as an example. Refdbms databases can be replicated on many different sites, using the group communication system described here. Keywords: replicated data, wide-area networks, anti-entropy, epidemic replication, frameworks. *************** UCSC-CRL-92-53 (available electronically as ucsc-crl-92-53.ps.Z) A NOTE ON BIT-MAPPED FREE SECTOR MANAGEMENT Darrell D. E. Long December 1992, 3 pages ($5.00) *************** UCSC-CRL-92-54 (available electronically as ucsc-crl-92-54.ps.Z) ON WEAK LEARNING David P. Helmbold and Manfred K. Warmuth December 1992, 37 pages ($7.00) Abstract: An algorithm is a weak learning algorithm if with some small probability it outputs a hypothesis with error slightly below 50%. This paper presents relationships between weak learning, weak prediction (where the probability of being correct is slightly larger than 50%), and consistency oracles (which decide whether or not a given set of examples is consistent with a concept in the class). Our main result is a simple polynomial prediction algorithm which makes only a single query to a consistency oracle and whose predictions have a polynomial edge over random guessing. We compare this prediction algorithm with several of the standard prediction techniques, deriving an improved worst case bound on Gibbs Algorithm in the process. We use our algorithm to show that a concept class is polynomially learnable if and only if there is a polynomial probabilistic consistency oracle for the class. Since strong learning algorithms can be built from weak learning algorithms, our results also characterizes strong learnability. *************** UCSC-CRL-92-55 (available electronically as ucsc-crl-92-55.ps.Z) A COMPARISON OF TWO IMPLEMENTATIONS OF THE TOKEN RING PRIORITY FUNCTION Ivan Fellner, Ivan Racko, Milos Racek, Karol Fabian, and Darrell Long December 1992, 12 pages ($5.00) Abstract: System performance is strongly influenced by the quality of its implementations. We describe four ways of evaluating the performance of two implementations of the priority mechanism used in the Token Ring local area network. We use various methods for comparing the small priority machine's differences and show how a simplified comparison can lead to bad results. With connection to the evaluation complexity, we also consider the simulation cost of the implementation process. ***************