leff@CSVAX.SEAS.SMU.EDU (Laurence Leff) (07/16/90)
Bibliography of Technical Reports
Computer Sciences Department
University of Wisconsin
April 1990 - June 1990
For copies, send requests to:
Technical Report Librarian
Computer Sciences Department
University of Wisconsin
1210 W. Dayton Street
Madison, WI 53706 USA
%A Ingo Althofer
%A Gautam Das
%A David Dobkin
%A Deborah Joseph
%T Generating Sparse Spanners for Weighted Graphs
%D October 1989
%R TR 882
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X Given a graph $G$, a subgraph $G'$ is a $t$-spanner of $G$, if for every
$u,~v~\(mo~V$, the distance from $u$ to $v$ in $G'$ is at most $t$ times longer
than the distance in $G$. In this paper we give a very simple algorithm
for constructing sparse spanners for arbitrary weighted graphs.
We then apply this algorithm to obtain specific results for planar
graphs and Euclidean graphs.
We discuss the optimality of our results and present several nearly matching
lower bounds.
%A M.-C. Chiang
%A G.S. Sohi
%T Evaluating Design Choices for Shared Bus Multiprocessors in a
Throughput-Oriented Environment
%D April 1990
%R TR 927
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X This paper considers the evaluation of design choices in multiprocessors
with a single, shared bus interconnect operating in a \fIthroughput-oriented\fR,
multiprogrammed environment.
That is, an environment in which each task is being executed
on a single processor and the performance of the multiprocessor
is measured by its overall throughput.
To evaluate design choices, we develop mean value analysis
analytical models and validate our models by comparing their results
against the results of a trace-driven simulation
analysis for over 5000 multiprocessor configurations.
The trace-driven simulation uses actual programs and
simulates their execution in a throughput-oriented environment.
Using multiprocessor throughput as a performance metric and
the mean value analysis models as tools, we evaluate several design choices.
We find that: i) cache block sizes that yield the best performance
in a multiprocessor differ from the block sizes that yield the
best uniprocessor cache-only performance metrics,
ii) a larger cache set associativity might be warranted in
a multiprocessor even though it might not be warranted in a uniprocessor
iii) a split transaction, pipelined bus yields much higher multiprocessor
throughput than a circuit switched bus,
especially for larger main memory latencies, and iv) increasing the bus
width appears to be an effective way of improving multiprocessor
throughput.
%A Anthony Rich
%A Marvin Solomon
%T A Logic-Based Approach to System Modelling
%D April 1990
%R TR 928
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X Managing a complex software system requires a description of how its
components are related to one another.
We propose a new approach to this problem based on logic programming.
All objects in the system are defined by
.i terms
that describe their format,
functionality, components, and origin.
Each of these properties is itself a pattern that can be matched against other
object descriptions by the unification algorithm.
Thus, for example, the
.i format
of a Pascal compiler written in C is
.q C ;
its
.i functionality
it is to translate an object whose format is
.q Pascal
into an object with format
.q "object code"
while preserving functionality.
The inference algorithm is sufficiently powerful to describe cross-compiling
and bootstrapping (that a compiler can compile itself).
Our approach is sufficiently flexible that all aspects of the software
configuration can specified in a single language.
It allows a complex specification to be split into manageable pieces.
For example, the input/output behavior of a compiler can be specified
separately from the fact that this behavior is implemented by combining the
functionalities of parsing and code generation.
We present the approach in detail by working through an extended example.
We discuss its advantages and limitations, and outline our plans for
further research on its applicability to a variety of problems in system
specification and building.
%A James R. Larus
%T Parallelism in Numeric and Symbolic Programs
%D April 1990
%R TR 929
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X This paper explains a new technique for estimating and understanding
the speed improvement that results when programs execute on a parallel
computer. This approach traces a sequential program to record a small
set of significant events. From this compact trace, a parallelism
analyzer (\fBllpp\fP) regenerates a full address trace that also
identifies events such as loop initiation and termination. The
analyzer uses this information to simulate parallel execution of the
program's loops.
In addition to predicting a program's parallel performance, \fBllpp\fP
measures many aspects of the program's dynamic behavior. This paper
presents measurements of six substantial C programs. These results
indicate that the three symbolic (non-numeric) programs differ
substantially from the numeric programs and, as a consequence, cannot
be parallelized automatically with the same compilation techniques.
%A Donovan Schneider
%A David J. DeWitt
%T Tradeoffs in Processing Complex Join Queries via Hashing in
Multiprocessor Database Machines
%D April 1990
%R TR 930
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X During the past five years the design, implementation, and evaluation
of join algorithms that exploit large main memories and parallel
processors has received a great deal of attention.
However, most of this work has addressed the problem of executing
joins involving only two relations.
In this paper we examine the problem of processing multi-way join queries
through hash-based join methods in a shared-nothing database environment.
We first discuss how the choice of a format for a complex query can
significantly affect performance in a multiprocessor database machine.
Experimental results obtained from a simulation study are then
presented to demonstrate the tradeoffs of left-deep and right-deep
scheduling strategies for complex join query evaluation.
These results demonstrate that right-deep scheduling strategies
can provide significant performance advantages in large multiprocessor
database machines, even when memory is limited.
%A W. Brent Seales
%A Charles R. Dyer
%T Modeling the Rim Appearance
%D May 1990
%R TR 931
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X Representing the rim of a 3D solid shape and the occluding contour
that it generates is a difficult problem because of their dependence
on viewpoint and on the local and global geometry of the shape.
Describing how the rim and occluding contour change as a function
of viewpoint organizes the features of the occluding contour
for indexing and matching.
This organization makes the features of the occluding contour explicit
for matching in a dynamic context where image features are
changing over time, and in a static context where matching methods must
iteratively refine an estimation of viewpoint.
This paper introduces a novel, viewer-centered approach to modeling the
geometry of the visible occluding contour of solid 3D shape.
The \fIrim appearance representation\fR models the exact appearance of
the occluding contour formed by the edges of a polyhedron which is
assumed to be an approximation of a smooth shape.
An algorithm is presented for constructing the rim appearance representation.
Bounds on space and time are given, and implementation results show that
the rim appearance representation is significantly smaller than the
aspect graph or the aspect representation.
%A Gary L. Schultz
%A Robert R. Meyer
%T A Three-Phase Algorithm for Block-Structured Optimization
%D May 1990
%R TR 932
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X We develop a decomposition method, based on barrier
functions, for solving block angular linear programs. The convergence
properties of the method are briefly described. We then
present promising computational results for one of the largest classes of
linear programming models occurring in the literature, a set of
multicommodity flow problems with up to 100,000 constraints and 300,000
variables.
%A Robert Hartley Clark
%T The Efficient Parallel Solution of Generalized Network Flow Problems
%D May 1990
%R TR 933
%X This thesis is principally concerned with the discussion of two
efficient parallel codes for the generalized network flow problem. Both
of the codes are variants of the primal simplex method for generalized
networks, and both were implemented by the author on a shared memory
multiprocessor, the Sequent Symmetry S81. PGRNET, the first code,
exploits parallelism in the pivoting and the pricing operation.
Parallel pivoting is made possible by the disjoint nature of the basis
graphs. Two processors may execute pivots simultaneously if the pivots
involve updating different basis components (quasi-trees), and locking
is used to ensure that processors have exclusive access to quasi-trees
during the execution of a pivot. The second code, TPGRNET, exploits
parallelism in the pricing operation and overlaps pricing and pivoting.
Pivots are executed serially by a host processor, pivot arcs are
selected from a collection of shared candidate lists by a selecting
processor, and all remaining processors compute reduced costs in
parallel and store pivot-eligible arcs in the shared candidate lists.
TPGRNET is more efficient than PGRNET for problems having only a few
quasi-trees in an optimal basis. Computational results for PGRNET for
transportation problems with 30,000 nodes and over 320,000 arcs are
given, and speedups over GRNET2, a state-of-the-art serial program range
from 3.8 to 11.1 on 19 processors. Results for TPGRNET are given for
large scale transportation and transshipment problems,and speedups over
GRNET2 range from 2.6 to 8.8. A hybrid algorithm that can invoke PGRNET
or TPGRNET is briefly described, and results are given, with speedups
ranging from 6.1 to 13.2. Two test problems with more than a million
variables were solved by PGRNET with speedups ranging from 7.0 to 11.0.
This thesis develops a technique for testing the "parallelizability" of
a problem instance to determine a lower bound for the number of disjoint
quasi-trees in any optimal basis of the problem. A technique is also
given that can be used to generate a problem instance that is guaranteed
to have a certain minimum number of quasi-trees in any optimal basis.
%A Gary L. Schultz
%A Robert R. Meyer
%T A Structured Interior Point Method
%D May 1990
%R TR 934
%X We develop a structured interior point method for block angular
optimization and describe the convergence properties of the method.
Excellent computational results are presented for a class of large-scale
linear programming models. These models are multicommodity flow
problems that arise from an Air Force MAC application and generate
problems as large as 100,000 rows and 300,000 columns.
%A Mark Allmen
%A Charles R. Dyer
%T Computing Spatiotemporal Surface Flow
%D May 1990
%R TR 935
%X Spatiotemporal surface flow is the natural extension of optic
flow to spatiotemporal surfaces. For every point on a surface, the instantaneous
velocity of that point on the surface is recovered. This paper presents
a method for making full use of the information available in a spatiotemporal
surface. Using the low-level structure of spatiotemporal surfaces,
translational and rotational motion parallel to the image plane is recovered.
Rather than use the partial derivatives of the surface as done in most
gradient-based optic flow methods, we use the gradient of a function on
the spatiotemporal surface. It is observed that arc length of a contour
does not change if that contour is moved in the direction of motion on
the surface. Motivated by this observation, a function measuring arc
length change is defined on a spatiotemporal surface. The direction of
motion of a contour undergoing motion parallel to the image plane is
shown to be perpendicular to the gradient of this function. It is also
shown that this gradient approximates the direction of motion when object
motion in the scene is not parallel to the image plane. This method is
used to compute the spatiotemporal surface flow in sequences of edge images
and gray level images.
%A David J. DeWitt
%A Philippe Futtersack
%A David Maier
%A Fernando Velez
%T A Study of Three Alternative Workstation-Server Architectures for
Object Oriented Database Systems
%D May 1990
%R TR 936
%X In the engineering and scientific marketplaces, the workstation-server
model of computing is emerging as the standard of the 1990s.
Implementing an object-oriented database system in this
environment immediately presents the design choice of how to partition
database functionality between the server and workstation processors.
To better understand the alternatives to this fundamental design decision,
we analyze three different workstation-server architectures, evaluating
them both qualitatively and through benchmarking of prototypes. The
three approaches are labeled
.i "object server" ,
in which individual objects pass between the server and workstation,
.i "page server" ,
in which a disk page is the unit of transport and the server buffers
pages, and
.i "file server",
where whole pages are transferred as well, but they are accessed directly
by the workstation process via a remote file service (namely, NFS).
We built prototypes of all three architectures, using a stripped-down version
of the WiSS storage system as a starting point. To compare the performance
of the prototypes, and to experiment with sensitivity to data placement
and cache sizes, we developed our own object manager benchmark, the
.i "Altair Complex-Object Benchmark"
(ACOB). This benchmark supports experiments that vary both clustering
(inter-object locality) and smearing (intra-object locality). The test
suite of benchmarks includes queries for scanning the entire database
and traversing and updating complex objects.
We present the results of several experiments run using ACOB on the three
prototypes, along with results from a single-server version of
WiSS that serves as a reference point.
Our main conclusions are that the page-server and file-server
architectures benefit most from clustering, that the relative performance
of the page- and object-server architectures is very sensitive
to the degree of database clustering and the size of the workstation's
buffer pool relative to the size of the database,
and that, while the file-server architecture dominates
the page-server architecture on read-intensive operations,
the opposite is true on write-intensive operations.
.ig XXX
These results point to
a hybrid architecture to maximize performance: direct reads of pages
by the workstation
process with buffering of writes on the server. The success of this hybrid
approach, however, is contingent on avoiding high message traffic for
lock and space-allocation requests.
.XXX
%A Michael Carey
%A Eugene Shekita
%A George Lapis
%A Bruce Lindsay
%A John McPherson
%T An Incremental Join Attachment for Starburst
%D June 1990
%R TR 937
%X In this paper we describe the design, implementation, and performance of
an incremental join facility that has been added as an extension to the
Starburst extensible DBMS. This facility provides an efficient access
path for joins that materialize many-to-one relationships,
and it works by maintaining hidden pointer fields embedded in related
tuples. The facility was constructed for two reasons: as an experiment
in using pointers in the internals of a relational DBMS, and as a
stress-test of the Starburst extension architecture. In addition to
describing the join facility and its performance, we also summarize
what it taught us about extensibility both in Starburst and in general.
%A Daniel Ralph
%T Rank-1 Support Functionals and the Rank-1 Generalized Jacobian,
Piecewise Linear Homeomorphisms
%D May 1990
%R TR 938
%X This research consists of two main topics broadly related
as studies of nondifferentiable systems.
The first, involving convex and nonsmooth analysis,
is aimed at extending the classical Jacobian to nondifferentiable
vector functions.
The second is on a characterization of the homeomorphisms in a certain
class of piecewise linear mappings.
This is useful eg. in approximating certain piecewise smooth systems.
For the first, let $X$,$Y$ be separated, locally
convex topological vector spaces
over $IR$ with $Y$ semi-reflexive; $X sup *$, $Y sup *$ be the respective
topological dual spaces of $X$, $Y$; and
$CL(X,Y)$ be the space of continuous linear mappings from $X$ to $Y$.
We introduce the
.i
rank-1 support functionals
.r
of sets
$GAMMA~subset~CL(X,Y)$
.EQ
sigma sub GAMMA sup 1~~:~~X~times~Y sup * ->~~IR~union~"{" inf "}"~:~
( x , lambda )~->~{roman "sup"} from {A \(mo GAMMA }~lambda~A~x
.EN
and characterize the extended real
functions on $X~times~Y sup *$ which are rank-1 support functions.
The proof uses
H$o dotdot$rmander's [H$o dotdot$r] characterization
of classical support functions.
As an immediate application we characterize the
fans [Iof81, Iof82] which are, up to closed values,
spanned by their handles.
Now assume $X$,$Y$ are normed spaces and
let $g~:~X~->~Y$ be Lipschitz near $x sub *~\(mo~X$.
The
.i
rank-1 generalized Jacobian
.r
of $g$, a set valued
derivative for $g$ at points where the classical Jacobian may not exist,
is studied. We show existence (nonemptiness) of
the rank-1 generalized Jacobian
.EQ
\(pd sup 1 g (x sub * ) sub = sup def "{" A\(mo CL(X,Y)~|~ \(fa~(u,~ lambda )~\(mo ~ X ~ times ~ Y sup * "," ~ lambda ~ Au ~\(<=~"("~ lambda ~g~ ")" sup omicron "("
x sub * ; u")" "}"
.EN
where $"("lambda g ")"sup omicron "(" x sub *~; \(m. ")"$
is the Clarke generalized directional
derivative [Cla] of the real function $lambda g$.
We actually show that the mapping $"(" u,~ lambda ")" ~ -> ~
"("lambda g")" sup omicron "("x sub *~;u~")"$ is a rank-1 support function
of a nonempty set.
Existence extends readily to more general spaces.
This is a considerable advance on
the most general previous existence result in this area, due
to Thibault [Thi82].
Some basic properties of the rank-1 generalized
Jacobian are explored.
In our second topic we study a class of piecewise linear maps from
$IR sup n$ to $IR sup n$ called
.i
pl-normal
.r
maps.
These are the
normal maps [Rob90] induced by linear mappings and polyhedral convex sets.
Solving such systems
is important in many optimization and equilibrium problems.
Robinson's [Rob90] homeomorphism theorem characterizes
the pl-normal maps that are homeomorphisms, i.e.\ gives
conditions for unique continuous solvability of such
systems.
We provide a new and shorter proof of this result.