1988-89 TECHNICAL REPORTS
         University of California at Santa Cruz 
Baskin Center for Computer Engineering and Information Sciences 
          Santa Cruz, California  95064   U.S.A.

(To obtain these tech reports, see directions at the beginning of 
the file ABSTRACTS.1991.)

**********
UCSC-CRL-88-28  (available electronically as ucsc-crl-88-28.ps.Z)
REPRESENTING BOOLEAN FUNCTIONS WITH IF-THEN-ELSE DAGs
Kevin Karplus
November 1988, 24 pages (paper copy $4.00)
Abstract:  This article describes the use of binary decision diagrams 
(BDDs) and if-then-else DAGs for representing and manipulating Boolean 
functions. 
     Two-cuts are defined for binary decision diagrams, and the 
relationship is exhibited between general if-then-else expressions and 
the two-cuts of a BDD for the same function.  An algorithm for computing
all two-cuts of a BDD in O(n2) time is given.
     A new canonical form for if-then-else DAGs, analogous to Bryant's 
canonical form for BDDs, is introduced.  The canonical form is based on
representing the lowest non-trivial two-cut in the corresponding BDD, 
while Bryant's canonical form represents the highest two-cut.  
Expressions in Bryant's canonical form or in the new canonical form are
shown to be prime and irredundant.
     Some applications of if-then-else DAGs to multi-level logic 
minimization are given, and the Printform transformations for reducing 
the complexity of if-then-else DAGs are presented.
Keywords:  Boolean functions, Binary decision diagrams, if-then-else 
trees, if-then-else DAGs, two-cuts, Bryant's canonical form.
**********
UCSC-CRL-88-29  (available as ucsc-crl-88-29.ps.Z)
USING IF-THEN-ELSE DAGs FOR MULTI-LEVEL LOGIC MINIMIZATION
Kevin Karplus
November 1988, 21 pages (paper copy $4.00)
Abstract:  This article describes the use of if-then-else DAGs for 
multi-level logic minimization.
     A new canonical form for if-then-else DAGs, analogous to Bryant's 
canonical form for binary decision diagrams (BDDs), is introduced.  
Two-cuts are defined for binary decision diagrams, and a relationship is
exhibited between general if-then-else expressions and the two-cuts of a
BDD for the same function.  The canonical form is based on representing
the lowest non-trivial two-cut in the corresponding BDD, instead of the
highest two-cut, as in Bryant's canonical form.
     The definitions of prime and irredundant expressions are extended 
to if-then-else DAGs.  Expressions in Bryant's canonical form or in the
new canonical form can be shown to be prime and irredundant.
     Objective functions for minimization are discussed, and estimators
for predicting the area and delay of the circuit produces after 
technology mapping are proposed.
     A brief discussion of methods for applying don't-care information 
and for factoring expressions is included.
Keyword:  Logic minimization.
**********
UCSC-CRL-89-04  (available electronically as ucsc-crl-89-04.tar.Z)
SWIFT: A STORAGE ARCHITECTURE FOR VERY LARGE OBJECTS\ 
Luis-Felipe Cabrera and Darrell Long
October 1989, 18 pages (paper copy $4.00)
Abstract:  Managing large objects with high performance requirements is
difficult for current computing systems.  The increasing disparity 
between the fastest network transfer rate and the fastest disk transfer
rate requires resolution.  We describe an architecture, called Swift, 
that solves the problem of storing and retrieving very large data
objects from slow secondary storage at very high data rates.
Applications requiring very high data rates range from visualization of
scientific computations to storage and retrieval of color video.
     Swift successfully addresses this issue by exploiting the available
interconnection capacity and by using several slower storage devices 
concurrently.  We study the performance characteristics of a local-area
implementation of Swift using a parametric simulation model.  Our 
analysis considers a system composed of several high-performance work 
stations connected to multiple storage agents via a high-speed local 
area network.  Swift compares favorably with other concurrent I/O
architectures, such as disk arrays, in terms of maximum aggregate data 
rate, reliability, and resource requirements.
Keywords: high-performance storage systems, disk striping, high-speed
networks, I/O throughput, client-server model, data redundancy, 
server resiliency.
**********
UCSC-CRL-89-20  (available electronically as ucsc-crl-89-20.ps.Z)
HIGH-SPEED NETWORKS AND THE INTERNET
Daniel R. Helman and Darrell D. E. Long
September 1989, 9 pages (paper copy $4.00)
Abstract:  So far much of the work in advanced networks has been 
concentrated on high-speed transmission and the design of low-level 
packet switching mechanisms.  Less is known about interfacing and 
integrating such networks into our existing data and telecommunications
systems.  We examine one aspect of this problem, interfacing these 
networks to existing LAN systems based on standard protocols.  An 
internetworking structure is proposed, and supported with experimental 
evidence.
**********
UCSC-CRL-89-42   (available electronically as 89-42.ps.Z)
ANALYZING TRACES WITH ANONYMOUS SYNCHRONIZATION
David P. Helmbold, Charles E. McDowell, and Jian-Zhong Wang 
December 1989, 21 pages (paper copy$4.00)
Abstract:  In a parallel system, events can occur concurrently.  
However, programmers are often forced to rely on misleading 
sequential traces for information about their program's behavior.
We present a series of algorithms which extract ordering information 
from a sequential trace with anonymous semaphore-style synchronization.
     We view a program execution as a partial ordering of events, and  
define which executions are consistent with a given trace.  Although 
it is generally not possible to determine which of the consistent 
executions occurred, we define the notion of ``safe orderings'' which 
can be relied on regardless of which execution generated the trace.
     The main results of the paper are algorithms which determine many 
of the ``safe orderings''.  The first algorithm starts from a sequential
trace and creates a partially ordered canonical execution.  The second 
algorithm strips away the ordering relationships particular to the 
canonical execution, so that the resulting partial order is safe.  The 
third algorithm increases the amount of ordering information while 
maintaining a safe partial order.  All three algorithms are accompanied
by proofs of correctness.  Finally, an algorithm is presented to detect
critical regions, to distinguish unordered sequential events from 
concurrent events.
Keywords: virtual time, program tracing, parallel processing, debugging.
**********