1991 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 Some of these tech reports are available electronically and are marked as such. Obtain them 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.1991 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-91-01 (available electronically as ucsc-crl-91-01.ps.Z) ACCESSING REPLICATED DATA IN A LARGE-SCALED DISTRIBUTED SYSTEM Richard Golding and Darrell D. E. Long January 1991, 22 pages (paper copy 4.00) Abstract: Replicating a data object improves the availability of the data, and can improve access latency by locating copies of the object near to their use. When accessing replicated objects across an internetwork, the time to access different replicas is non-uniform. Further, the probability that a particular replica is inaccessible is much higher in an internetwork than in a local-area network (LAN) because of partitions and the many intermediate hosts and networks that can fail. We report three replica-accessing algorithms which can be tuned to minimize either access latency or the number of messages sent. These algorithms assume only an unreliable datagram mechanism for communicating with replicas. Our work extends previous investigations into the performance of replication algorithms by assuming unreliable communication. We have investigated the performance of these algorithms by measuring the communication behavior of the Internet, and by building discrete-event simulations based on our measurements. We find that almost all message failues are either transient or due to long-term host failure, so that retrying messages a few times adds only a small amount to the overall message traffic while improving both access latency as long as the probability of message failure is small. Moreover, the algorithms which retry messages on failure provide significantly improved availability over those which do not. *************** UCSC-CRL-91-02 (available electronically as ucsc-crl-91-02.ps.Z, or in two parts as ucsc-crl-91-02.part1.ps.Z and ucsc-crl-91-02.part2.ps.Z) DECISION THEORETIC GENERALIZATIONS OF THE PAC MODEL FOR NEURAL NET AND OTHER LEARNING APPLICATIONS David Haussler (Supersedes 89-30 and 90-52.) December 1990, Revised January 1992, 65 pages (paper copy $10.00) [Also in "Information and Computation", Vol. 100, No.1, September 1992] Abstract: We describe a generalization of the PAC learning model that is based on statistical decision theory. In this model the learner receives randomly drawn examples, each example consisting of an instance x in X and an outcome y in Y , and tries to find a hypothesis h : X --> A , where h in H , that specifies the appropriate action a in A to take for each instance x , in order to minimize the expectation of a loss l(y,a). Here X, Y, and A are arbitrary sets, l is a real-valued function, and examples are generated according to an arbitrary joint distribution on X times Y . Special cases include the problem of learning a function from X into Y , the problem of learning the conditional probability distribution on Y given X (regression), and the problem of learning a distribution on X (density estimation). We give theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain hypothesis spaces H , and show how this implies learnability with bounded sample size, disregarding computational complexity. As an application, we give distribution-independent upper bounds on the sample size needed for learning with feedforward neural networks. Our theorems use a generalized notion of VC dimension that applies to classes of real-valued functions, adapted from Pollard's work, and a notion of *capacity* and *metric dimension* for classes of functions that map into a bounded metric space. *************** UCSC-CRL-91-06 (available electronically as ucsc-crl-91-06.ps.Z) ESTIMATING THE RELIABILITY OF HOSTS USING THE INTERNET D. D. E. Long, J. L. Carroll, and C. J. Park March 1991, 17 pages (paper copy $5.00) Abstract: Modeling the reliability distributed systems, whether through analysis or simulation, requires a good understanding of the reliability of the components. Careful modeling allows highly fault-tolerant distributed data bases and similar applications to be constructed at the least cost. It is often assumed that the failure and repair rates of components are exponentially distributed. This hypothesis is testable for failure rates, though the process of gathering and reducing the data to a usable form can be difficult. By applying an appropriate test statistic, some of the samples were found to have a realistic chance of being drawn from an exponential distribution, while others can be confidently classed as non-exponential. For this study, data were collected from a large number of hosts via the Internet with no special privileges or monitoring facilities. Over 350,000 hosts were considered, and more than 68,000 of these that were judged likely to respond were queried. These hosts were sampled several times over the course of two months to obtain up-times, and finally to determine average host availability. A rich collection of information was gathered in this fashion, allowing estimates of availability, mean-time-to-failure (MTTF) and mean-time-to-repair (MTTR) to be derived. The results reported here correspond with those seen in practice. *************** UCSC-CRL-91-07 (available electronically as ucsc-crl-91-07.ps.Z) EFFECTS OF COEFFICIENT CODING ON JPEG BASELINE IMAGE COMPRESSION Manyun Chang, Glen G. Langdon, Jr., and James L. Murphy June 1991, 25 pages (paper copy $6.00) Abstract: A set of still image compression algorithms JPEG (Joint Photographic Experts Group) is becoming an international standard. Here we apply a methodology to study the compression obtained by each step of the three-step baseline algorithm chosen by JPEG. We also present our results, observations and analysis on simulating the JPEG sequential baseline system. The primary compression gain comes from run-length coding of zero coefficients. Based on our simulator, a comparison of Huffman coder, arithmetic coder and LZW algorithm is also included. *************** UCSC-CRL-91-08 (available electronically as ucsc-crl-91-08.ps.Z) EXPLOITING MULTIPLE I/O STREAMS TO PROVIDE HIGH DATA-RATES Luis-Felipe Cabrera and Darrell D. E. Long April 1991, 17 pages (paper copy $5.00) Abstract: We present an I/O architecture, called Swift, that addresses the problem of data-rate mismatches between the requirements of an application, the maximum data-rate of the storage devices, and the 6ata-rate of the interconnection medium. The goal of Swift is to support integrated continuous multimedia in general purpose distributed systems. In installations with a high-speed interconnection medium, Swift will provide high data-rate transfers by using multiple slower storage devices in parallel. The data-rates obtained with this approach scale well when using multiple storage devices and multiple interconnections. Swift has the flexibility to use any appropriate storage technology, including disk arrays. The ability to adapt to technological advances will allow Swift to provide for ever increasing I/O demands. To address the problem of partial failures, Swift stores data redundantly. Using the UNIX operating system, we have constructed a simplified prototype of the Swift architecture. Using a single Ethernet-based local-area network and three servers, the prototype provides data-rates that are almost three times as fast as access to the local SCSI disk in the case of writes. When compared to NFS, the Swift prototype provides double the data-rate for reads and eight times the data-rate for writes. The data-rate of our prototype scales almost linearly in the number of servers and the number of network segments. Its performance is shown to be limited by the speed of the Ethernet-based local-area network. We also constructed a simulation model to show how the Swift architecture can exploit storage, communication, and processor advances, and to locate the components that will limit I/O performance. In a simulated gigabit/second token ring local-area network the data-rates are seen to scale proportionally to the size of the transfer unit and to the number of storage agents. Keywords: Swift architecture, high-performance storage systems, distributed file systems, distributed disk striping, high-speed networks, high data-rate I/O, client-server model, object server, video server, multimedia, data redundancy, resiliency. *************** UCSC-CRL-91-09 (not available electronically) SIMULATING A DYNAMIC RAM IN COSMOS Don Speck April 1991, 26 pages (paper copy $6.00) Abstract: This report describes the tricks involved in simulating a chip containing a 1-transistor style dynamic RAM using the COSMOS switch-level simulator. The reader is assumed to be familiar with this style of dynamic RAM. The specifics are drawn from a variant of the Caltech Mosaic RAM as modified at UCSC, but most of the tricks generalize to other CMOS dRAMs. The appendix gives a minimal list of attribute labels for the Mosaic RAM. *************** UCSC-CRL-91-10 (available electronically as ucsc-crl-91-08.ps.Z) APPROXIMATION PROPERTIES OF NP MINIMIZATION CLASSES Phokion G. Kolaitis and Madhukar N. Thakur April 1991, 24 pages (paper copy $6.00) Abstract: In this paper we introduce a new approach to the logical definability of NP optimization problems by focusing on the expressibility of feasible solutions. We show that in this framework first-order sentences capture exactly all polynomially bounded optimization problems. We also show that, assuming P not= NP, it is an undecidable problem to tell if a given first-order sentence defines an approximable optimization problem. We then isolate a syntactically defined class of NP minimization problems that contains the MIN SET COVER problem and has the property that every problem in it has a logarithmic approximation algorithm. We conclude by giving a machine-independent characterization of the NP =? co-NP problem in terms of logical expressibility of the MAX CLIQUE problem. *************** UCSC-CRL-91-11 (available electronically as ucsc-crl-91-11.ps.Z) BAYESIAN APPROACH TO EARLY PROBABILITY ESTIMATION IN BINARY ADAPTIVE CODING Ahmad Zandi and Glen G. Langdon Jr. May 1991, 10 pages (paper copy $5.00) Abstract: In a one pass adaptive statistical codng it is required to have a probability distribution on the set of coding alphabet to be used for a symbol *before* it is observed. In particular at the very beginning we have to start with a probability distribution without having any data. This condition is so Bayesian in nature that it is not surprising that a number of people have used the Bayesian approach to the problem. In this report we combine various approaches to this initialization problem for adaptive binary encoding under a general framework. In fact we introduce a single family of priors and show it covers all the known methods of initializing the counts and statistics employed in binary coding. We hope that this general formula makes it easier to choose the most appropriate method for the initialization and what is called *fast attack* for particular problems at hand. We have also added an appendix that gives some historical and mathematical explanation for the most well known cases of the family of priors that we consider. *************** UCSC-CRL-91-12 (not available electronically) DECISIONS IN DIRECT VOLUME RENDERING Jane Wilhelms May 1991, 12 pages (paper copy $5.00) Abstract: There are a great range of possible choices to make in rendering volumetric data. The choices can make a difference in time and space requirements, ease of implementation, and the nature of the final image. Some make an objectifiable difference in image quality, e.g. causing aliasing and incorrect discontinuities and holes. Others cause more subjective variations, and the desired effect is more a matter of personal choice than inaccurate information content. The repercussions of the many choices should be EXAmined before choosing or designing software. What follows is a rather preliminary and subjective discussion of the issues that need to be examined. It certainly isn't complete, but hopefully will stimulate discussion. Most of the discussion concentrates on direct volume rendering, where approaches are especially flexible. Occasional mention is made of methods that extract features such as isosurfaces to produce geometrical representations. *************** UCSC-CRL-91-14 (available electronically as ucsc-crl-91-14.ps.Z) PATTERN ASSOCIATIVITY AND THE RETRIEVAL OF SEMANTIC NETWORKS Robert Levinson (Supersedes 90-30.) April 1991, 37 pages (paper copy $7.00) Abstract: Four methods for the associative retrieval of semantic networks are described. These methods differ from those traditional approaches, such as SNEPS, in which an entire knowledge base is treated as a single network. Here the knowledge base is viewed as an organized collection of networks and is most appropriate for applications (such as bibliographic retrieval) in which pieces of knowledge need to be treated individually. Method I is an arbitrary flat ordering of database graphs, Method II a two-level ordering, and Method III is a full partial order. Method IV is a novel method known as ``hierarchical node descriptor method'' that is based on the ``refinement'' method of subgraph-isomorphism. A ``pattern associativity'' principle explains the development and effectiveness of each of these methods. Moving from Method I through Method IV there is a steady increase in both pattern associativity and efficiency. A theorem is proven that establishes the superiority of Method III over Method II despite the fact that Method II is the method most often used. A brief discussion of how parallelism may be incorporated also accompanies the description of each method. Most of the paper applies these methods to conceptual graphs and a later section shows how the techniques can be extended to other semantic-network formalisms. The paper concludes by showing how generalization graphs constructed through pattern associativity may also have semantic validity in the domains from which they have been derived. Keywords: Algorithm design, associative retrieval, conceptual graphs, databases, graph isomorphism, knowledge representation, parallelism, semantic networks. *************** UCSC-CRL-91-16 (available electronically as ucsc-crl-91-16.ps.Z) FEASIBILITY STUDY ON THE COSTS OF IDDQ TESTING IN CMOS CIRCUITS F. Joel Ferguson and Tracy Larrabee May 1991, 15 pages (paper copy $5.00) Abstract: Many manufacturing defects in static CMOS circuits are not detected by tests generated using the traditional single stuck-at fault model. Many of these defects may be detected as increased propagation delay or as excessive quiescent power supply current (I_DDQ). In this paper we compare the costs of detecting probable manufacturing defects by the resulting excess I_DDQ with the costs of traditional logical testing methods. *************** UCSC-CRL-91-18 (ONLY AVAILABLE ELECTRONICALLY, as ucsc-crl-91-18.ps.Z) ACCESSING REPLICATED DATA IN A LARGE-SCALE DISTRIBUTED SYSTEM Richard Andrew Golding (M.S. Thesis) June 1991, 115 pages (no paper copies available) Abstract: Many distributed applications use replicated data to improve the availability of the data, and to improve access latency by locating copies of the data near to their use. This thesis presents a new family of communication protocols, called *quorum multicasts*, that provide efficient communication services for replicated data. Quorum multicasts are similar to ordinary multicasts, which deliver a message to a set of destinations. The new protocols extend this model by allowing delivery to a subset of the destinations, selected according to distance or expected data currency. These protocols provide well-defined failure semantics, and can distinguish between communication failure and replica failure with high probability. The thesis includes a performance evaluation of three quorum multicast protocols. This required taking several measurements of the Internet to determine distributions for communication latency and failure. The results indicate that the behavior of recent messages is a useful predictor for the performance of the next. A simulation study of quorum multicasts, based on the Internet measurements, shows that these protocols provide low latency and require few messages. A second study that measured a test application running at several sites confirmed these results. *************** UCSC-CRL-91-19 (available electronically as ucsc-crl-91-19.ps.Z) SWIFT: A STORAGE ARCHITECTURE FOR LARGE OBJECTS Luis-Felipe Cabrera and Darrell D. E. Long (Supersedes 89-04.) May 1991, 7 pages (paper copy $5.00) Abstract: Managing large objects with high data-rate requirements is difficult for current computing systems. We describe an Input/Output architecture, called Swift, that addresses the problem of storing and retrieving very large data objects from slow secondary storage at very high data-rates. Applications that require this capability are poorly supported in current systems, even though they are made possible by high-speed networks. These range from storage and visualization of scientific computations to recodring and play-back of color video in real-time. Swift addresses the problem of providing the data rates required by digital video by exploiting the available interconnection capacity and by using several slower storage devices in parallel. We have done two studies to validate the Swift architecture: a simulation study and an Ethernet-based proof-of-concept implementation. Both studies indicate that the aggregation principle proposed in Swift can yield very high data-rates. We present a brief summary of these studies. *************** UCSC-CRL-91-21 (available electronically as ucsc-crl-91-21.ps.Z) QUORUM-ORIENTED MULTICAST PROTOCOLS FOR DATA REPLICATION Richard A. Golding and Darrell D. E. Long June 1991, 9 pages (paper copy $5.00) Abstract: Many wide-area distributed applications use replicated data to improve the availability of the data, and to improve access latency by locating copies of the data near to their use. This paper presents a new family of communication protocols, called *quorum multicasts*, that provide efficient communication services for widely replicated data. Quorum multicasts are similar to ordinary multicasts, which deliver a message to a set of destinations. The new protocols extend this model by allowing delivery to a subset of the destinations, selected according to distance or expected data currency. These protocols provide well-defined failure semantics, and can distinguish between communication failure and replica failure with high probability. We have evaluated their performance, which required taking several traces of the Internet to determine distributions for communication latency and failure. A simulation study of quorum multicasts, based on these measurements, shows that these protocols provide low latency and require few messages. A second study that measured a test application running at several sites confirmed these results. *************** UCSC-CRL-91-22 (available electronically as ucsc-crl-91-22.ps.Z) EMPIRICAL EVALUATION OF MULTILEVEL LOGIC MINIMIZATION TOOLS FOR A FIELD-PROGRAMMABLE GATE ARRAY TECHNOLOGY Martine D. F. Schlag, Pak K. Chan, and Jackson Kong April 1991, 15 pages (paper copy $5.00) Abstract: We examine empirically the performance of multi-level logic minimization tools for a lookup table-based Field-Programmable Gate Array (FPGA) technology. The experiments are conducted by using the university tools *misII* for combinational logic minimization and *mustang* for state assignment, the industrial tools *xnfmap* for technology mapping, and *apr* for automatic placement and routing. We measure the quality of the multi-level minimization tools by the number of *routed* configurable logic blocks (CLBs) in the FPGA realization. We report three results: a) we have developed a new system to support rapid prototyping using FPGAs, b) there is a linear relationship between the number of literals and the number of *routed* CLBs, and c) in all but one of the 31 *MCNC-89* benchmark finite state machines, one-hot state assignment resulted in substantially less CLBs than any other state encoding method. These results are useful to those who prototype a design in FPGAs, and then transfer the design to a different technology (e.g., CMOS standard cell). It provides valuable information on the difference in performance of a design realized in different technologies. *************** UCSC-CRL-91-23 (available electronically as ucsc-crl-91-23.ps.Z) PARALLEL VOLUME RENDERING ON A SHARED-MEMORY MULTIPROCESSOR Judy Challinger July 1991, 15 pages (paper copy $5.00) Abstract: *Volume rendering* is a powerful, but computationally intensive, computer graphics technique for visualizing volumetric data sets. This paper presents results of investigations into techniques for volume rendering using parallel processing on a shared-memory, multiple-instruction, multiple-data (MIMD) architecture. In particular, two widely used algorithms for volume rendering, *raycasting* and *projection*, have been parallelized on a BBN TC2000, and their performance has been measured and analyzed. Preliminary results indicate that the raycasting approach to volume rendering has some advantages for parallelization on this type of architecture. Keywords: Volume rendering, parallel, shared memory, multiprocessor, computer graphics, scientific visualization. *************** UCSC-CRL-91-24 (available electronically as ucsc-crl-91-24.ps.Z) CARAFE: AN INDUCTIVE FAULT ANALYSIS TOOL FOR CMOS VLSI CIRCUITS Alvin Lun-Knep Jee June 1991, 37 pages (paper copy $7.00) Abstract: Traditional fault models for testing CMOS VLSI circuits do not take into account the actual mechanisms that precipitate faults. As a result, the failure modes of a circuit as predicted by these fault models may not reflect the realistic failure modes of the circuit. This thesis reports on the Carafe software which determines the realistic bridge faults of the CMOS circuit based on its layout. Each fault found by Carafe is assigned a relative probability based on the geometry of the fault site and defect distributions of the fabrication process. Carafe improves upon previous software in that it is easier to use, more robust, and more time and memory efficient so that larger circuits can be analyzed. Keywords: Fault models, VLSI testing, CMOS, inductive fault analysis. *************** UCSC-CRL-91-25 (not available electronically) INTERACTIVE GRAPHICAL EXPLORATION OF MULTIDIMENSIONAL NONLINEAR DYNAMICAL SYSTEMS Judy Challinger August 1991, 29 pages (paper copy $6.00) [Also in "International Journal of Bifurcation and Chaos", Vol 2, No 2, 1992 pp. 251-26.] Abstract: This paper discusses the application of an inherently three-dimensional graphical representation tool, isosurfaces, as a means to *interactively* explore and visualize the attractors of a nonlinear dynamical system with a fifteen-dimensional parameter space. A program has been written which allows the scientist to interactively select and visualize three-dimensional subspaces of the fifteen- dimensional parameter space. The dynamical system used for this project is a discrete-time, nonlinear, three-nation Richardson model with economic constraints. This dynamical system, which models the shifting alliances of nations in an arms race, maps an initial point in the unit cube to another point in the unit cube after multiple iterations of the model functions. Using an isosurface function on the resulting volumetric data set, surfaces indicating the changing alliances of nations are generated and rendered. Keywords: Nonlinear dynamical system, visualization, interactive steering. *************** UCSC-CRL-91-26 (available electronically as ucsc-crl-91-26.ps.Z) TRACKING DRIFTING CONCEPTS BY MINIMIZING DISAGREEMENTS David P. Helmbold and Philip M. Long August 1991, 16 pages (paper copy $5.00) Abstract: In this paper we consider the problem of tracking a subset of a domain (called the *target*) which changes gradually over time. A single (unknown) probability distribution over the domain is used to generate random examples for the learning algorithm and measure the speed at which the target changes. We show that if the problem of minimizing the number of disagreements with a sample from among concepts in a class H can be approximated to within a factor k , then there is a simple tracking algorithm for H which can achieve a probability epsilon of making a mistake if the target movement rate is at most a constant times epsilon^{2}/(k(d+k) ln {1 over epsilon}), where d is the Vapnik-Chervonenkis dimension of H . Also, we show that if H is properly PAC-learnable, then there is an efficient (randomized) algorithm that with high probability approximately minimizes disagreements to within a factor of 7d+1, yielding an efficient tracking algorithm for H which tolerates drift rates up to a constant times epsilon^{2}/(d^2 ln {1 over epsilon}). In addition, we prove complementary results for the classes of halfspaces and axis-aligned hyperrectangles showing that the maximum rate of drift that any algorithm (even with unlimited computational power) can tolerate is a constant times epsilon^{2}/d. *************** UCSC-CRL-91-27 (available electronically as ucsc-crl-91-27.ps.Z) METHOD INTEGRATION FOR EXPERIENCE-BASED LEARNING Jeffrey Gould and Robert Levinson August 1991, 18 pages (paper copy $5.00) Abstract: This paper describes how a variety of machine learning methods can be combined synergistically to produce an adaptive pattern-oriented chess program. Major aspects of the following machine learning methods are used: temporal-difference learning, simulated annealing, genetic algorithms, explanation-based generalization, structured concept induction and heuristic evaluation. The need for these methods comes from the research constraints placed on the chess system. The system, "Morph", is limited to using just 1-ply of search, little domain knowledge and no supervised training. Thus, the system is responsible for finding a useful set of features (patterns) for evaluating states and for determining their significance (in the form of weight). To get the learning methods to cooperate effectively some design constraints normally associated with these methods need to be relaxed. The paper also argues that a benefit of a multi-strategy viewpoint is that new research ideas arise from the multiple perspectives. Keywords: machine learning, integrated learning systems, temporal- difference learning, genetic algorithms, pattern induction. *************** UCSC-CRL-91-28 (available electronically as ucsc-crl-91-28.ps.Z) THE WEIGHTED MAJORITY ALGORITHM (Supersedes 89-16) Nick Littlestone and Manfred K. Warmuth October 1991, revised October 26, 1992, 35 pages (paper copy $7.00) Abstract: We study the construction of prediction algorithms in a situation in which a learner faces a sequence of trials, with a prediction to be made in each, and the goal of the learner is to make few mistakes. We are interested in the case that the learner has reason to believe that one of some pool of known algorithms will perform well, but the learner does not know which one. A simple and effective method, based on weighted voting, is introduced for constructing a compound algorithm in such a circumstance. We call this method the Weighted Majority Algorithm. We show that this algorithm is robust in the presence of errors in the data. We discuss various versions of the Weighted Majority Algorithm and prove mistake bounds for them that are closely related to the mistake bounds of the best algorithms of the pool. For example, given a sequence of trials, if there is an algorithm in the pool A that makes at most m mistakes then the Weighted Majority Algorithm will make at most c(log |A| + m) mistakes on that sequence, where c is fixed constant. Keywords: Prediction, mistake, mistake bounds, weighted majority, absolute loss, on-line learning algorithm. *************** UCSC-CRL-91-29 (available electronically as ucsc-crl-91-29.ps.Z) ON-LINE LEARNING OF LINEAR FUNCTIONS Nicholas Littlestone, Philip M. Long, and Manfred K. Warmuth October 1991, rvsd October 1992, 22 pages (paper copy $6.00) Abstract: We present an algorithm for the on-line learning of linear functions which is optimal to within a constant factor with respect to bounds on the sum of squared errors for a worst case sequence of trials. The bounds are logarithmic in the number of variables. Furthermore, the algorithm is shown to be optimally robust with respect to noise in the data (again to within a constant factor). We also discuss an application of our methods to the iterative solution of sparse systems of linear equations. *************** UCSC-CRL-91-30 (available electronically as ucsc-crl-91-30.ps.Z) TEST PATTERN GENERATION FOR REALISTIC BRIDGE FAULTS IN CMOS ICs F. Joel Ferguson and Tracy Larrabee August 1991, 9 pages (paper copy $5.00) Abstract: Two approaches have been used to balance the cost of generating effective tests for ICs and the need to increase the ICs' quality level. The first approach favors using high-level fault models to reduce test generation costs at the expense of test quality, and the second approach favors the use of low-level, technology-specific fault models to increase defect coverage but lead to unacceptably high test generation costs. In this report we (1) present the results of simulations of complete single stuck-at test sets against a low-level model of bridge defects showing that an unacceptably high percentage of such defects are not detected by the complete stuck-at test sets; (2) show how low-level bridge fault models can be incorporated into high-level test generation; and (3) describe our system for generating effective tests for bridge faults and report on its performance. *************** UCSC-CRL-91-33 (not available electronically) AMP: A BUS-BASED PACKET SWITCH DESIGN USING MCM TECHNOLOGY Martin Taylor (M.S. thesis) March 1991, 53 pages (paper copy $9.00) Abstract: AMP is a bus based packet switch implemented as a *silicon-on-silicon* Multi-Chip Module (MCM). The AMP switch system architecture is a special case of a *multi-bus* switching scheme. Such an architecture allows an efficient use of buffering and switching hardware. The implementation targeted MCM technology from the beginning. The fabrication, testing and assembly were done utilizing services which should be made available to academic and research establishments as a MOSIS type brokerage service in the future. Keywords: Packet switch, multi-bus packet switch, multi-chip module. *************** UCSC-CRL-91-34 (not available electronically) LZWBSWRT - A TECHNIQUE FOR HIGH PERFORMANCE UNIVERSAL DELTA DATA COMPRESSION Budi Sutardja (M.S. thesis) June 1991, 51 pages (paper copy $9.00) Abstract: Delta data compression is a technique used to take advantage of the external redundancy of one data object with respect to another related data object. This technique has been used in the storage management subsystem of many revision control systems. The UNIX *diff* algorithm, which works only on line-based text data, is a common delta extraction algorithm. A universal lossless high-performance delta data compressor known as LZWBSWRT is presented. This simple algorithm can perform delta extraction on both text and binary data. Since LZWBSWRT simultaneously performs delta extraction and data compression, the results are often several orders of magnitude better in both execution speed and storage utilization than the combination of UNIX's *diff* and *compress*. This paper develops the finite automata theory of the dictionary- based coder that contributes to the derivation of the LZWBSWRT. Using a concept of extended deterministic finite automata trees (EDFAT), a family of high-performance compression algorithms known as LZWBS is introduced. From this family, we derived LZWBSWRT. Besides applications in revision control systems and version control systems (for which LZWBSWRT was designed), several other viable applications are discussed. These include global database compression, image recognition, computer animation and digital video compression. Keywords: Delta, compression, coding, DFA, DFAT, EDFAT, version, revision, variant, LZW, LZWBS, LZWBSWRT, image recognition, graphics animation, global database compression. *************** UCSC-CRL-91-36 (available electronically as ucsc-crl-91-36.ps.Z) DETERMINING POSSIBLE EVENT ORDERS BY ANALYZING SEQUENTIAL TRACES D. P. Helmbold, C. E. McDowell, and J-Z. Wang September 1991, 28 pages (paper copy $6.00) Abstract: One of the fundamental problems encountered when debugging a parallel program is determining the possible orders in which events could have occurred. Various problems, such as data races and intermittent deadlock, arise when there is insufficient synchronization between the tasks in a parallel program. A sequential trace of an execution can be misleading, as it implies additional event orderings, distorting the concurrent nature of the computation. This paper describes algorithms which generate those event orderings which can be relied on by the programmer from the trace of an execution. By its very nature, the information in an execution trace pertains only to that execution of the program, and may not generalize to other executions. We tackle this difficulty in a systematic way: defining an "inferred program" based on the trace and original program, analyze this inferred program, and prove a relationship between the inferred program and the original. The results of our algorithms can be used by other automated tools such as a data race detector or constraint checker. The basic algorithms described here have been implemented in a working trace analyzer for IBM Parallel Fortran. The trace analyzer graphically presents the discovered event orderings and reports various potential data races in the subject program. Keywords: Data race, time vector, program trace, parallel programming, debugging, distributed systems *************** UCSC-CRL-91-37 (available electronically as ucsc-crl-91-37.ps.Z) EXPERIENCE-BASED CREATIVITY Robert Levinson October 1991, 36 pages (paper copy $7.00) Abstract: This paper argues for a computational model of creativity as the unique and favorable combining of past experiences. It is hypothesized that the inner process that combines the experiences is universal and largely syntactic, i.e. it is only the emotional associations that are attached to encoded experience and not the semantic content of experience that is used by the inner creative process. A chess system, "Morph", has been developed that can be viewed as exploring this model. Morph is limited to 1-ply of search, little domain knowledge and no supervised training. It is only through playing another program, and encoding its experience (as "pattern-weight" pairs) that it can improve. Morph's learning system is a combination of machine learning methods that have been successful in other settings - and is covered in depth. Part of Morph's strength comes from a powerful representation for chess patterns that allows generalizations across positions (experiences). Performance results, including displays of creativity by Morph, are also presented. Keywords: Knowledge representation, machine learning, computer chess. *************** UCSC-CRL-91-38 (not available electronically) MORPH: A PROGRAMMER'S GUIDE W. Paul Zola (Undergraduate Thesis) September 1991, 20 pages (paper copy $6.00) Abstract: Chess has long been used as a testbed for Artificial Intelligence research. There are many good chess playing programs available that perform deep search of the game tree. These programs get their chess-playing power from the depth of the search tree rather than from the sophistication of their position-evaluation heuristics. These programs essentially throw away all the information obtained by evaluating the game tree. This document describes Morph, a chess-playing program based on the completely opposite approach. This program searches only one ply deep and learns from game to game. Morph creates patterns that it uses to evaluate positions that occur in future games. Keywords: Machine Learning, computer chess. *************** UCSC-CRL-91-39 (not available electronically) AUTOMATIC SYNTHESIS OF SELF-TEST USING ASyST Peter Johnson December 1991, 23 pages (paper copy $6.00) Abstract: This thesis describes an automated *Built-In Self-Test* (BIST) technique for general sequential circuits. The technique replaces storage elements in a given circuit with self-test elements. These elements are then connected as a shift register, and used both to generate test patterns and to compress test responses. Benchmarks were run on a number of standard sequential benchmark circuits to determine single stuck-at fault coverage. The results of these tests indicate that the self-test techniques presented here obtain fault coverage similar to that of random test techniques. *************** UCSC-CRL-91-40 (available electronically as ucsc-crl-91-40.ps.Z) FORCE-DRIVEN CONSTRAINED WIRING OPTIMIZATION Tal Dayan and Wayne Wei-Ming Dai October 1991, 13 pages (paper copy $5.00) Abstract: We describe a practical iterative approximation algorithm that can be used for homotopic positioning of Steiner points and vias for minimization of a wiring cost in rubber-band sketches. The algorithm is based on modeling the interconnect as a physical system and iterativly finding it minimum energy state. This method has a wide range of applications including finding Steiner trees, optimization of nets with given topologies, and optimization of constrained nets. It supports multi-layer sketches with obstacles, and can be adapted to various optimization goals by changing the force function. The algorithm can be used to improved the topology or to improve the wiring for a given topology. By controlling, the force functions of the physical system, various aspect of the interconnect such as average or maximal wire length can be improved. *************** UCSC-CRL-91-41 (available electronically as ucsc-crl-91-41.ps.Z) SPHERE PACKING NUMBERS FOR SUBSETS OF THE BOOLEAN n-CUBE WITH BOUNDED VAPNIK-CHERVONENKIS DIMENSION David Haussler October 1991, revised March 1992, revised March, 1992. 14 pages (paper copy $5.00) Abstract: Let V contained in {0,1}^n have Vapnk-Chervonenkis dimension d. Let M(k/n,V) denote the cardinality of the largest W contained in V such that any two distinct vectors in W differ on at least k indices. We show that M(k/n,V) <= (cn/(k+d))^d for some constant c. This improves on the previous best result of ((cn/k)log(n/k))^d. This new result has applications in the theory of empirical processes. *************** UCSC-CRL-91-42 (available electronically as ucsc-crl-91-42.ps.Z) XS - XILINX 2000/3000 FPGA SIMULATOR Jason Zien, Jackson Kong, Pak K. Chan, Martine Schlag October 1991, 39 pages (paper copy $7.00) Abstract: With the growing complexity of field programmable gate arrays (FPGA), there is the growing need for sophisticated design tools to provide higher level abstractions for managing large designs. It is not enough to be able to create large designs; it is also necessary to test and debug them. Debugging FPGA designs on the circuit board is an awkward task, since the designer can only access the input/output pins of the chip. XS provides the designer with the ability to simulate and debug circuit designs quickly, and with access to all internal nets. XS is a batch-mode, unit-delay, event-driven logic simulator written in Gnu C++ for verification of designs under the unix X-window environment. We exploit certain properties in XILINX XC2000/3000/4000 architectures to enhance the performance as well as the accuracy of the simulator. This report serves the dual purposes of being the USER GUIDE as well as documenting the development of XS. *************** UCSC-CRL-91-43 (available electronically as ucsc-crl-91-43.ps.Z, but 4 pages of diagrams are not in the postscript file. Request trs@cse.ucsc.edu to have them sent to you by regular mail.) CALCULATION OF THE LEARNING CURVE OF BAYES OPTIMAL CLASSIFICATION ALGORITHM FOR LEARNING A PERCEPTRON WITH NOISE (supersedes 91-03) David Haussler and Manfred Opper December 1991, rvsd October 1992, 13 pages (paper copy $5.00) Abstract: The learning curve of Bayes optimal classification algorithm when learning a perceptron from noisy random training examples is calculated exactly in the limit of large training sample size and large instance space dimension using methods of statistical mechanics. It is shown that under certain assumptions, in this "thermodynamic" limit, the probability of misclassification of Bayes optimal algorithm is less than that of a canonical stochastic learning algorithm, by a factor approaching the square root of 2 as the ratio of number of training examples to instance space dimension grows. Exact asymptotic learning curves for both algorithms are derived for particular distributions. In addition, it is shown that the learning performance of Bayes optimal algorithm can be approximated by certain learning algorithms that use a neural net with a layer of hidden units to learn a perceptron. *************** UCSC-CRL-91-44 (available electronically as ucsc-crl-91-44.ps.Z) BOUNDS ON THE SAMPLE COMPLEXITY OF BAYESIAN LEARNING USING INFORMATION THEORY AND THE VC DIMENSION David Haussler, Michael Kearns, and Robert Schapire March 1992, 29 pages (paper copy $6.00) Abstract: In this paper we study a Bayesian or average-case model of concept learning with a twofold goal: to provide more precise characterizations of learning curve (sample complexity) behavior that depend on properties of both the prior distribution over concepts and the sequence of instances seen by the learner, and to smoothly unite in a common framework the popular statistical physics and VC dimension theories of learning curves. To achieve this, we undertake a systematic investigation and comparison of two fundamental quantities in learning and information theory: the probability of an incorrect prediction for an optimal learning algorithm, and the Shannon information gain. This study leads to a new understanding of the sample complexity of learning in several existing models. *************** UCSC-CRL-91-45 (available electronically as ucsc-crl-91-45.ps.Z) BORG: A RECONFIGURABLE PROTOTYPING BOARD USING FIELD-PROGRAMMABLE GATE ARRAYS Pak K. Chan, Martine D.F. Schlag, and Marcelo Martin November 1991, 7 pages (paper copy $5.00) Abstract: Field-Programmable Gate Arrays (FPGA) provide a medium to accelerate the process of prototyping digital designs. For designs with multiple FPGAs that need to be connected together, the bottleneck is now the process of wire-wrapping, bread-boarding, or (worse) the construction of a printed circuit board, which cannot be carried out until all FPGA designs are routed. It is because locking or preassigning I/O blocks often prevent FPGA placement/routers from completing the routing.\\ We exploit the reprogrammability of FPGAs and use them for routing. To experiment with the idea, we constructed a PC-based prototyping board that contains two ``user'' FPGAs, two routing FPGAs, and an FPGA that serves as glue logic to the PC bus. To facilitate the design process using the new prototyping board, we developed algorithms and tools that automatically configure the routing FPGAs. We describe the options that we have examined during the development of this board, and how we arrive at some design decisions. The toolset, user FPGAs, and the routing FPGAs and the reprogammability of the FPGAs serve to further reduce the time/cost of constructing prototypes using FPGAs. *************** UCSC-CRL-91-46 (available electronically as ucsc-crl-91-46.ps.Z) SWIFT: USING DISTRIBUTED DISK STRIPING TO PROVIDE HIGH I/O DATA RATES Luis-Felipe Cabrera and Darrell D.E. Long December 1991, 24 pages (paper copy $6.00) Abstract: We present an I/O architecture, called Swift, that addresses the problem of data rate mismatches between the requirements of an application, storage devices, and the interconnection medium. The goal of Swift is to support high data rates in general purpose distributed systems. Swift uses a high-speed interconnection medium to provide high data rate transfers by using multiple slower storage devices in parallel. It scales well when using multiple storage devices and interconnections, and can use any appropriate storage technology, including high-performance devices such as disk arrays. To address the problem of partial failures, Swift stores data redundantly. Using the UNIX operating system, we have constructed a simplified prototype of the Swift architecture. The prototype provides data rates that are significantly faster than access to the local SCSI disk, limited by the capacity of a single Ethernet segment, or in the case of multiple Ethernet segments by the ability of the client to drive them. We have constructed a simulation model to demonstrate how the Swift architecture can exploit advances in processor, communication and storage technology. We consider the effects of processor speed, interconnection capacity, and multiple storage agents on the utilization of the components and the data rate of the system. We show that the data rates scale well in the number of storage devices, and that by replacing the most highly stressed components by more powerful ones the data rates of the entire system increase significantly. Keywords: high-performance storage systems, distributed file systems, distributed disk striping, high-speed networks, high-speed I/O, client-server model, video server, multimedia, data resiliency. ***************