CS9360  

Title  OPTIMUM LOGIC ENCODING AND LAYOUT WIRING FOR VLSI DESIGN: A GRAPHTHEORETIC APPROACH  
Authors  ChuanJin Shi  
Abstract 
This
thesis
addresses
two
problems
in
VLSI
design:
constrained
via
minimization
—
which
aims
at
minimizing
the
number
of
vias
between
routing
layers
—
and
constrained
logic
encoding
—
a
problem
fundamental
to
the
design
of
synchronous,
and
hazardfree
asynchronous,
circuits.
We
show
that
these
two
problems
have
the
same
combinatorial
structure,
which
can
be
captured
by
a
new
graphtheoretic
model,
called
signed
hypergraph.
They
can
be
formulated
as
two
new
optimization
problems,
namely
maximum
balance
and
minimum
covering,
related
to
a
balance
property
of
signed
hypergraphs. On the theoretical side, we establish a structural characterization of balanced signed hypergraphs. We then prove that both maximum balance and minimum covering are NPcomplete. We present an integer linear programming formulation for maximum balance of signed hypergraphs, and a polynomialsize linear programming formulation for the case of planar signed graphs. We show that maximum balance in a planar signed hypergraph reduces to the minimum hypergraph $T$join in its planar dual. We address the problem of modeling signed hypergraphs by realweighted hypergraphs or graphs. We settle a conjecture of Lengauer which states that a clique is a best approximate model for a hyperedge, even if dummy vertices are allowed. We present a local search algorithm for the maximum balance problem, with one pass running in linear time. We describe a simple greedy peeling heuristic for minimum covering. We prove that greedy peeling has a guaranteed performance bound for solving a class of VLSI optimization problems of the socalled clustercover structure. On the practical side, our work on constrained via minimization breaks new ground for the case of $k$way splits ($k \leq 3$) with a compact reduction to graph $T$joins and a polynomialsize linear programming formulation. For the case of multiway splits ($k >3$), it provides a direct and efficient local search for timingdriven layer assignment and an optimal modeling scheme for good approximation algorithms. For logic synthesis, we present a unified approach to optimum state assignment for synchronous and hazardfree asynchronous circuit design. We have implemented our results as two experimental CAD tools. As demonstrated on a set of industry benchmarks, our tools outperform existing tools in terms of both solution quality and CPU time.  
Comments  A thesis presented to the University of Waterloo in fulfilment of the thesis requirement for the degree of Doctor of Philosophy in Computer Science.  
Report  OPTIMUM LOGIC ENCODING AND LAYOUT WIRING FOR VLSI DESIGN: A GRAPHTHEORETIC APPROACH (PDF) 
Compressed
PostScript: OPTIMUM LOGIC ENCODING AND LAYOUT WIRING FOR VLSI DESIGN: A GRAPHTHEORETIC APPROACH (PS.Z) 
CS9357  

Title  A Rationale for Both Nesting and Inheritance in ObjectOriented Design  
Authors  L.M.F. Carneiro, D.D. Cowan, and C.J.P. Lucena  
Abstract  It has been observed that design of complex objects such as software requires both decomposition by form (atomic objects) and decomposition by function (nesting) in order to reduce the design to a set of manageable components. However, the objectoriented design paradigm mostly supports decomposition by form. This paper uses a simple example to motivate the need for nesting (decomposition by function) and illustrates how nesting might be incorporated into a design language. We then demonstrate how the introduction of nesting into software specification and design significantly increases reusability. ADVcharts, a new visual formalism, and VDM are used to provide a semantics for nesting.  
Date  December 1993  
Comments  This paper was published in the Proceedings of the VII Software Engineering Symposium  Rio de Janeiro  RJ  Brazil  Pages: 223237  
Report  A Rationale for Both Nesting and Inheritance in ObjectOriented Design (PDF) 
Compressed
PostScript: A Rationale for Both Nesting and Inheritance in ObjectOriented Design (GZIP) 
CS9355  

Title  Sequential and Parallel Algorithms for Embedding Problems on Classes of Partial kTrees  
Authors  A. Gupta and N. Nishimura  
Abstract  We present sequential and parallel algorithms for various embedding problems on bounded degree partial ktrees and kconnected partial ktrees; these include subgraph isomorphism and topological embedding, known to be NPcomplete for general partial ktrees. As well as contributing to our understanding of the types of graphs for which these problems are tractable, this paper introduces new methods for solving problems on graphs. In particular, we make use of a treelike representation of the graph (the treedecomposition of the graph) to apply techniques used to solve problems on trees to solve problems on more general classes of graphs.  
Date  February 1994  
Report  Sequential and Parallel Algorithms for Embedding Problems on Classes of Partial kTrees (PDF) 
Compressed
PostScript: Sequential and Parallel Algorithms for Embedding Problems on Classes of Partial kTrees (PS.Z) 
CS9354  

Title  Towards Automated Detection of Feature Interactions  
Authors  K.H. Braithwaite and J.M. Atlee  
Abstract  The feature interaction problem occurs when the addition of a new feature to a system disrupts the existing services and features. This paper describes a tabular notation for specifying the functional behavior of features. It also describes how four classes of feature interactions can be detected when features are specified in this new notation. Our goal is to develop a tool that can automatically analyze feature specifications and detect interactions at the specification stage of development.  
Date  February 1994  
Comments  Appeared in the Second International Workshop on Feature Interactions in Telecommunications Software Systems.  
Report  Towards Automated Detection of Feature Interactions (PDF) 
Compressed
PostScript: Towards Automated Detection of Feature Interactions (GZIP) 
CS9352  

Title  Abstract Data Views: A Module Interconnection Concept to Enhance Design for Reusability  
Authors  D.D. Cowan and C.J.P. Lucena  
Abstract  The Abstract Data View (ADV) design model was originally created to specify clearly and formally the seperation of the user interface from the application component or Abstract Data Type (ADT), and to provide a systematic design method that is independent of specific application environments. Such a method should lead to a high degree of reuse of both interface components and their associated ADTs. The material in this paper extends the concept of ADVs to encompass the general specification of interfaces between objects in the same or different computing environments. This approach to specifying interfaces clearly seperates objects from each other, since objects do not need to know how they are used, or how they obtain services from other objects. Thus, objects which are designed to minimize knowledge of the environment in which they are used, are more amenable to reuse.  
Date  March 1994  
Report  Abstract Data Views: A Module Interconnection Concept to Enhance Design for Reusability (PDF) 
Compressed
PostScript: Abstract Data Views: A Module Interconnection Concept to Enhance Design for Reusability (GZIP) 
CS9349  

Title  A spectral algorithm for envelope reduction of sparse matrices  
Authors  A. Pothen, S.T. Barnard and H.D. Simon  
Abstract  The problem of reordering a sparse symmetric matrix to reduce its envelope size is considered. A new spectral algorith for computing an envelopereducing reordering is obtained by associating a Laplacian matrix with the given matrix and the sorting the components of a specified eigenvector of the Laplacian. This Laplacin eigenvector solves a continuous relaxation of a discrete problem related to envelope minization called the minimum 2sum problem. The permutaion vector computed by the spectral algorith is a closest permutation vector to the specified Laplacian eigenvector. Numerical results show that the new reordering algorithm usually computes smaller envelope size than those obtained from the current standards such as the GibbsPooleStockmeyer (GPS) algorithm or the reverse CuthillMcKee (RCM) algorithm in SPARSPAK, in some cases reducing the envelope by more than a factor of two.  
Date  October 1993  
Report  README  A spectral algorithm for envelope reduction of sparse matrices (PDF) 
Compressed
PostScript: A spectral algorithm for envelope reduction of sparse matrices (PS.Z) 
CS9348  

Title  A GoalDirected FunctionallyBased Style Analyzer  
Authors  P. Hoyt  
Abstract 
If
sophisticated
natural
language
systems
are
to
handle
the
full
range
of
communication,
then
they
must
be
able
to
account
for
the
nuances
and
subtleties
of
linguistic
style.
A
computational
treatment
of
style
would
be
highly
advantageous
to
natural
language
understanding
and
generation,
with
particular
relevance
to
intelligent
computerassisted
language
instruction
and
machine
translation.
These
systems
would
be
able
to
understand
more
complex
and
expressive
language,
produce
text
suitable
for
a
specific
occasion,
help
a
secondlanguage
learner
develop
a
more
natural
and
appropriate
style,
and
produce
higher
quality
translations
of
text. A foundation for AIbased computational style has been laid by DiMarco, with extensions by Green, MakutaGiluk, Mah, and Payette in generation, rhetoric, comparative stylistics, and intelligent computeraided language instruction, respectively. These researchers found that DiMarco's work, while an important step in computational stylistics, was limited due to the lack of a theoretical foundation. DiMarco and Hirst provided a preliminary theoretical foundation and Green extended their work. This thesis unifies these complementary, and sometimes contradictory, theories of syntactic style. A definitive grammar of style, based on this revised theory, is developed and used to implement a stylistic analyzer, Asset. The revised theory of syntactic style and its implementation show that humanindependent computer analysis of style is a feasible goal for computational linguistics.  
Date  Sept 1993  
Comments  Masters Thesis  
Report  A GoalDirected FunctionallyBased Style Analyzer (PDF) 
Compressed
PostScript: A GoalDirected FunctionallyBased Style Analyzer (PS.Z) 
CS9346  

Title  Performing Groupby Before Join  
Authors  P. Yan and P.A. Larson  
Abstract  Assume that we have an SQL query containing joins and a groupby. The standard way of evaluationg this type of query is to first perform all the joins and then the groupby operation. However, it may be possible to perform the groupby early, that is, to push the groupby operation past one or more joins. Early grouping may reduce the query precessing cost by reducing the amount of data participating in joins. We formally define the problem, adhering strictly to the semantics of NULL and duplicate elimination in SQL2, and prove necessary and sufficient conditions for deciding when this transformation is valid. In practice, it may be expensive or even impossible to test whether the conditions are satisfied. Therefore, we also present a more practical algorithm that test a simple, sufficient condition. This algorithm is fast and detects a large subclass of transformable queries.  
Date  November 1993  
Comments  The major part of this paper will appear in the Proceedings of the 10th International Conference on Data Engineering(1994).  
Report  Performing Groupby Before Join (PDF) 
Compressed
PostScript: Performing Groupby Before Join (PS.Z) 
CS9343  

Title  ConstraintBased Rendering for Scenes with High Dynamic Ranges  
Authors  L. Fang  
Abstract 
Many
researchers
have
examined
rendering
techniques
with
a
focus
on
realistic
image
synthesis.
Ray
tracing
and
radiosity,
which
are
the
most
successful
current
methodologies,
are
based
on
the
physics
of
light
and
surfaces.
Neither
considers
display
device
limitations
or
properties
of
human
visual
perception.
Furthermore,
the
synthetic
camera
model
has
shown
its
deficiency
in
rendering
scenes
with
high
dynamic
ranges
onto
display
devices
with
lower
dynamic
ranges. A new rendering framework is proposed. Human visual properties are incorporated into the framework to increase the effective visual contrast. It is known in visual perception that brightness is not a monotonic function of intensity. The perceived brightness is affected by the intensities of the surrounding area. It is also known that human vision is insensitive to low frequency spatial intensity variation. In the proposed framework, to preserve the visual contrast in one image, the contrasts across edges are maintained while the intensities in large areas are slowly varied. Based on the proposed framework, a modified rendering pipeline is presented and a prototype system is implemented. The system generates the contrast constraints by invoking a modified visible surface algorithm. Then, the problem of satisfying the constraint hierarchy is transformed into a bounded linear least squares (BLLS) problem. Numerical algorithms are employed to solve the BLLS problem.  
Date  October 1993  
Comments  Masters Thesis  1993  
Report  ConstraintBased Rendering for Scenes with High Dynamic Ranges (PDF) 
Compressed
PostScript: ConstraintBased Rendering for Scenes with High Dynamic Ranges (PS.GZ) 
CS9342  

Title  A Query Sampling Method of Estimating Local Cost Parameters in a Multidatabase  
Authors  Q. Zhu and P.A. Larson  
Abstract  In a multidatabase system (MDBS), some query optimization information related to local database sys tems may not be available at the global level because of local autonomy. To perform global query optimization, a method is required to derive the necessary local information. This paper presents a new method that employs a query sampling technique to estimate the cost parameters of an autonomous local database system. We introduce a classification for grouping local queries and suggest a cost estimation formula for the queries in each class. We present a procedure to draw a sample of queries from each class and use the observed costs of sample queries to determine the cost parameters by multiple regression. Experimental re sults indicate that the method is quite promising for estimating the cost of local queries in an MDBS.  
Report  A Query Sampling Method of Estimating Local Cost Parameters in a Multidatabase (PDF) 
Compressed
PostScript: A Query Sampling Method of Estimating Local Cost Parameters in a Multidatabase (GZIP) 
CS9341  

Title  Weighted Graph Based Ordering Techniques for Preconditioned Conjugate Gradient Methods  
Authors  S.S. Clift and W.P. Tang  
Abstract  We describe the basis for a matrix ordering heuristic for improving incomplete factorization for preconditioned conjugate gradient techniques applied to anisotropic PDE's. Several new matrix ordering techniques, derived from wellknown algorithms in combinatorial graph theory, which attempt to implement this heuristic, are described. These ordering techniques are tested against a number of matrices arising from linear anisotropic PDE's, and compared with other matrix ordering techniques. A variation of RCM is shown to generally improve the quality of incomplete factorization preconditioners.  
Date  August 1993  
Comments  Submitted to: BIT  
Report  Weighted Graph Based Ordering Techniques for Preconditioned Conjugate Gradient Methods (PDF) 
Compressed
PostScript: Weighted Graph Based Ordering Techniques for Preconditioned Conjugate Gradient Methods (PS.Z) 
CS9340  

Title  The Sparse Basis Problem and Multilinear Algebra  
Authors  A. Pothen, R.A. Brualdi and S. Friedland  
Abstract 
Let
A
be
a
k
by
n
underdetermined
matrix.
The
sparse
basis
problem
for
the
row
space
W
of
A
is
to
,nd
a
basis
of
W
with
the
fewest
number
of
nonzeros.
Suppose
that
all
the
entries
of
A
are
nonzero,
and
that
they
are
algebraically
independent
over
the
rational
number
field.
Then
every
nonzero
vector
in
W
has
at
least
n

k
+
1
nonzero
entries.
Those
vectors
in
W
with
exactly
n

k
+
1
nonzero
entries
are
the
elementary
vectors
of
W.
A
simple
combinatorial
condition
that
is
both
necessary
and
suficient
for
a
set
of
k
elementary
vectors
of
W
to
form
a
basis
of
W
is
presented
here.
A
similar
result
holds
for
the
null
space
of
A
where
the
elementary
vectors
now
have
exactly
k
+
1
nonzero
entries.
These
results
follow
from
a
theorem
about
nonzero
minors
of
order
m
of
the
(m
1)st
compound
of
an
m
by
n
matrix
with
algebraically
independent
entries)
which
is
proved
using
multilinear
algebra
techniques.
This
combinatorial
condition
for
linear
independence
is
a
first
step
towards
the
design
of
algorithms
that
compute
sparse
bases
for
the
row
and
null
space
without
imposing
arti,cial
structure
constraints
to
ensure
linear
independence. AMS(MOS) subject classifications: primary 65F50, 65K05, 15A96. Keywords: elementary vector, matrix compound, nullspace basis, rowspace basis, sparse matrix, wedge product.  
Date  September 1993  
Report  README  The Sparse Basis Problem and Multilinear Algebra (PDF) 
Compressed
PostScript: The Sparse Basis Problem and Multilinear Algebra (PS.Z) 
CS9338  

Title  On Correctness and Efficiency for Advancing Front Techniques of Finite Element Mesh Generation  
Authors  S. Farestam and R.B. Simpson  
Abstract 
Advancing
front
techniques
are
a
family
of
methods
for
finite
element
mesh
gener
ation
that
are
particularly
effective
in
dealing
with
complicated
boundary
geometries.
In
the
first
part
of
this
paper,
conditions
are
presented
which
ensure
that
any
planar
aft
algorithm
that
meets
these
conditions
terminates
in
a
finite
number
of
steps
with
a
valid
triangulation
of
the
input
domain.
These
conditions
are
described
by
specifying
a
framework
of
subtasks
that
can
accommodate
many
aft
methods
and
by
prescribing
the
minimal
requirements
on
each
subtask
that
ensure
correctness
of
an
algorithm
that
conforms
to
the
framework. An important efficiency factor in implementing an aft is the data structure used to represent the unmeshed regions during the execution of the algorithm. In the second part of the paper, we discuss the use of the constrained Delaunay triangulation as an efficient abstract data structure for the unmeshed regions. We indicate how the cor rectness conditions of the first part of the paper can be met using this representation. In this case, we also discuss the additional requirements on the framework which en sure that the generated mesh is a constrained Delaunay triangulation for the original boundary. Classifications: AMS(MSC) 65N50, 65Y25; CR G.1.8, I.3.5 Keywords:unstructured meshes, finite element method, Delaunay triangulation  
Date  July 1993  
Report  On Correctness and Efficiency for Advancing Front Techniques of Finite Element Mesh Generation (PDF) 
Compressed
PostScript: On Correctness and Efficiency for Advancing Front Techniques of Finite Element Mesh Generation (GZIP) 
CS9333  

Title  Preconditioned Conjugate Gradient Methods for Three Dimensional Linear Elasticity  
Authors  J.K. Dickinson  
Abstract  A finite element modelling of three dimensional elasticity problems gives rise to large sparse matrices. To improve upon direct solution methods, various new preconditioning methods are developed and examined, as well as some generally standard techniques, for use in preconditioned conjugate gradient iterative solution techniques. Developments of incomplete factorizations based on levels of fill, drop tolerance, and a two level hierarchical basis are used to build the preconditioning matrices. The problem of nonpositive pivots occurring during factorization is also addressed by the use of several techniques. Computational tests are carried out for problems generated using unstructured tetrahedral meshes with quadratic basis functions. The performance of the iterative methods is compared to a standard direct sparse matrix solver. Various problems with up to 70,000 degrees of freedom are considered during which the effect of a range of average element aspect ratios, including small (<< 1) aspect ratios, on the performance of the PCG method is examined. A brief review is also made of stopping criteria for conjugate gradient solvers. One method based on the norm of the residual and an estimate of the smallest eigenvalue of the matrix system was implemented and tested with poor results.  
Date  June 1993  
Comments  Masters Thesis  1993  
Report  Preconditioned Conjugate Gradient Methods for Three Dimensional Linear Elasticity (PDF) 
Compressed
PostScript: Preconditioned Conjugate Gradient Methods for Three Dimensional Linear Elasticity (PS.Z) 
CS9331  

Title  Computing Values and Derivatives of Bezier and Bspline Tensor Products  
Authors  S. Mann, T. DeRose and G. Windenback  
Abstract  When evaluating tensor product surfaces it is often necessary to calculate both the position and the normal to the surface. We give an efficient algorithm for evaluating Bezier and Bspline tensor products for such information. The algorithm is an extension of a method for computing the position and tangent to a Bezier curve, and is asymptotically twice as fast as the standard bilinear algorithm.  
Date  May 1993  
Report  Computing Values and Derivatives of Bezier and Bspline Tensor Products (PDF) 
Compressed
PostScript: Computing Values and Derivatives of Bezier and Bspline Tensor Products (PS.Z) 
CS9330  

Title  An Illustration Technique for Unstructured 3D Meshes  
Authors  N.P. Konrad and R.B. Simpson  
Abstract 
Geometric
relations
in
an
irregular
3D
polyhedron
or
tetrahedral
mesh
are
often
difficult
to
comprehend,
even
for
relatively
few
vertices.
A
technique
for
illustrating
such
meshes
which
aids
this
comprehension
is
described
in
terms
of
several
independent
components,
i.e.
edge
representation,
viewpoint
and
perspective
projection,
and
lighting.
These
images
are
suitable
for
embedding
in
dynamic
displays,
or
in
publications. Heuristics for the effective use of these components are discussed and the technique is demonstrated on three small configurations from the recent literature.  
Date  November 1993  
Comments  Submitted, 29/09/1993, to Graphics Interface '94 Conference.  
Report  An Illustration Technique for Unstructured 3D Meshes (PDF) 
Compressed
PostScript: An Illustration Technique for Unstructured 3D Meshes (PS.Z) 
CS9329  

Title  The Design and Analysis of Asynchronous UpDown Counters  
Authors  J.P.L. Segers  
Abstract 
The
goal
of
this
report
is
to
investigate
updown
counter
implementations
in
the
framework
of
delayinsensitive
circuits.
An
updown
counter
is
a
counter
on
which
two
operations
can
be
performed:
an
increment
by
one
and
a
decrement
by
one.
For
N
larger
than
zero,
an
updown
Ncounter
counts
in
the
range
from
zero
through
N.
In
the
counters
we
design,
the
value
of
the
counter,
or
its
count,
cannot
be
read,
but
it
is
possible
to
detect
whether
the
counter's
value
is
zero,
N,
or
somewhere
in
between.
Updown
counters
have
many
applications.
For
example,
they
can
be
useful
in
implementing
queues
or
stacks. Various implementations for updown Ncounters are presented for any N larger than zero. All counter designs are analyzed with respect to three performance criteria, namely area complexity, response time, and power consumption. One of the designs is optimal with respect to all three performance criteria. Its area complexity grows logarithmically with N, and its response time and power consumption are independent of N.  
Date  May 1993  
Report  The Design and Analysis of Asynchronous UpDown Counters (PDF) 
Compressed
DVI: The Design and Analysis of Asynchronous UpDown Counters (DVI) 
CS9328  

Title  Skip Lists and Probabilistic Analysis of Algorithms  
Authors  T. Papadakis  
Abstract 
This
thesis
is
concerned
with
various
forms
of
skip
lists,
and
with
probabilistic
analyses
of
algorithms.
We
investigate
three
topics;
one
topic
from
each
of
these
two
areas,
and
another
topic
common
to
both
of
them. First, we consider Pugh's skip list. We derive exact and asymptotic expressions for the average search costs of a fixed key and of an average key. Our results improve previously known upper bounds of these two average search costs. We also derive exact and asymptotic expressions for the variance of the search cost for the largest key. Next, we propose several versions of deterministic skip lists. They all have guaranteed logarithmic search and update costs per operation, they lead to an interesting "bridge" structure between the original skip list and standard search trees, they are simpler to implement than standard balanced search trees, and our experimental results suggest that they are also competitive in terms of space and time. Finally, we consider the elasticbucket trie, a variant of the standard trie, in which each external node (bucket) has precisely as many key slots as the number of keys stored in it. We examine the number of buckets of each size, and we derive exact and asymptotic expressions for their average values, as well as asymptotic expressions for their variances and covariances under the closely related "Poisson model" of randomness. Our experimental results suggest that maintaining only two bucket sizes may be a very reasonable practical choice.  
Date  May 1993  
Comments  PhD Thesis  1993  
Report  Skip Lists and Probabilistic Analysis of Algorithms (PDF) 
Compressed
DVI: Skip Lists and Probabilistic Analysis of Algorithms (DVI) 
CS9327  

Title  A Clique Tree Algorithm for Partitioning a Chordal Graph  
Authors  A. Pothen, B.W. Peyton and X. Yuan  
Abstract 
A
partitioning
problem
on
chordal
graphs
that
arises
in
the
solution
of
sparse
triangular
systems
of
equations
on
parallel
computers
is
considered.
Roughly
the
problem
is
to
partition
a
chordal
graph
G
into
the
fewest
transitively
orientable
subgraphs
over
all
perfect
elimination
orderings
of
G,
subject
to
a
certain
precedence
relationship
on
its
vertices.
In
earlier
work,
a
greedy
scheme
that
solved
the
problem
by
eliminating
a
largest
subset
of
vertices
at
each
step
was
described,
and
an
algorithm
implementing
the
scheme
in
time
and
space
linear
in
the
number
of
edges
of
the
graph
was
provided.
Here
a
more
efficient
greedy
scheme,
obtained
by
representing
the
chordal
graph
in
terms
of
its
maximal
cliques,
which
eliminates
a
subset
of
the
leaf
cliques
at
each
step
is
described.
Several
new
results
about
minimal
vertex
separators
in
chordal
graphs,
and
in
particular
the
concept
of
a
critical
separator
of
a
leaf
clique,
are
employed
to
prove
that
the
new
scheme
solves
the
partitioning
problem.
We
provide
an
algorithm
implementing
the
scheme
in
time
and
space
linear
in
the
size
of
the
clique
tree. AMS(MOS) subject classifications: primary 65F50, 65F05, 68R10. Keywords:chordal graph, clique tree, critical separator, directed acyclic graph, perfect elimination ordering, sparse triangular solution, vertex separator, transitive closure, transitive perfect elimination ordering.  
Date  May 1993  
Report  README  A Clique Tree Algorithm for Partitioning a Chordal Graph (PDF) 
Compressed
PostScript: A Clique Tree Algorithm for Partitioning a Chordal Graph (PS.Z) 
CS9326  

Title  Enhancing Software Design Reuse: Nesting in ObjectOriented Design  
Authors  D.D. Cowan and C.J.P. Lucena  
Abstract 
It
has
been
observed
that
design
of
complex
objects
such
as
software
requires
both
decom
position
by
form
(atomic
objects)
and
decomposition
by
function
(nesting)
in
order
to
reduce
the
design
to
a
set
of
manageable
components.
However,
the
objectoriented
design
paradigm
mostly
supports
decomposition
by
form.
This
paper
uses
a
simple
example
to
motivate
the
need
for
nesting
(decomposition
by
function)
and
illustrates
how
nesting
might
be
incorporated
into
a
design
language.
We
conclude
that
the
introduction
of
nesting
into
software
specification
and
design
significantly
increases
reusability. Keywords: programming languages, program specification, software design and implementa tion, software engineering  
Date  March 1994  
Report  Enhancing Software Design Reuse: Nesting in ObjectOriented Design (PDF) 
Compressed
PostScript: Enhancing Software Design Reuse: Nesting in ObjectOriented Design (PS.Z) 
CS9325  

Title  Model Checking Timing Requirements  
Authors  J.M. Atlee and J. Gannon  
Abstract  Model checking has been used successfully to analyze concurrent, finitestate systems. In this paper, we extend the Software Cost Reduction (SCR) requirements notation to specify systems' timing requirements. We describe an analysis tool that transforms timed SCR specifications into timed reachability graphs, and show how some realtime properties can be verified with a model checker for branchingtime temporal logic. In addition, we compare our system for analyzing SCR requirements with other model checkers that verify properties of realtime systems.  
Date  February 1994  
Comments  Submitted to TOSEM for publication.  
Report  Model Checking Timing Requirements (PDF) 
Compressed
PostScript: Model Checking Timing Requirements (PS.Z) 
CS9324  

Title  ConflictFree Accedss to Rectangular Subarrays in Parallel Memory Modules  
Authors  D. Erickson  
Abstract 
In
a
parallel
computing
environment,
we
consider
conflictfree
access
to
constantperimeter
rectangular
subarrays,
using
a
natural
formulation
in
terms
of
latin
squares.
For
parallel
matrix
computations,
there
are
frequently
portions
of
data,
referred
to
as
templates,
that
one
desires
to
be
stored
and
retrieved
in
such
a
way
that
one
can
operate
on
the
data
simultaneously
with
each
processor
working
on
one
element
of
the
template.
If
more
than
one
processor
attempts
to
retrieve
data
from
a
single
memory
module
during
the
same
memory
cycle,
there
is
a
memory
conflict.
When
the
array
is
stored
to
allow
the
desired
templates
to
be
accessible
from
the
memory
modules
without
memory
conflicts,
it
is
conflictfree
for
that
set
of
templates.
In
this
thesis,
we
examine
a
set
of
structured
templates
where
the
number
of
template
instances
defined
by
template
grows
with
respect
to
the
maximum
size
of
a
template.
In
particular,
we
examine
the
set
of
constantperimeter
rectangular
subarrays. A square is `perimeter rectangular conflictfree' (p_rcf) if it is conflictfree for all rectangular subarrays whose perimeter is less than or equal to 2p. If p is even, the problem is to provide conflictfree access to all rectangular subarrays of size ((p/2)i)*((p/2)+i) for (p/2) < i <(p/2). We show that the necessary number of memory modules is ((p/2)^2)  p+1. Furthermore, ((p/2)^2)  p+1 memory modules are sufficient, and there is a linear skewing scheme to realize this bound. If p is odd, the problem is to provide conflictfree access to all rectangular subarrays of size (floor(p/2)i)(ceiling(p/2)+i) for floor(p/2)< i < floor(p/2). We show that the necessary number of memory modules is floor(p/2)^2, and there is a linear skewing scheme that realizes this bound. We also provide bounds and constructions for subsets of constantperimeter rectangular subarrays, in particular all (xi)(y+i) rectangular subarrays of an (n)(n) array for all nonnegative i where p=x+y. The linear results for the constantperimeter rectangular subarrays hold when the subarrays are stretched by a factor of v where v is relatively prime to the number of memory modules. A subarray is stretched by v if every vth element in a row and every vth row is selected. In this situation, the perimeter includes only those elements in the rectangular subarray and not those elements skipped because of the stretch. Thus, the perimeter of a given rectangular subarray is the same regardless of its stretch. In addition, the perimeter results provide a lower bound for conflictfree access to constantarea rectangular subarrays. An upper bound is found using a technique of relating conflictfree access to the chromatic number of a graph. In addition to bounds for constantarea rectangular subarrays, some computational results are provided. Finally, we propose a new method for defining skewing schemes, in particular, skewing schemes defined by permutations.  
Date  May 1993  
Comments  PhD Thesis  1993  
Report  ConflictFree Accedss to Rectangular Subarrays in Parallel Memory Modules (PDF) 
Compressed
PostScript: ConflictFree Accedss to Rectangular Subarrays in Parallel Memory Modules (GZIP) 
CS9323  

Title  Threshold Schemes with Hierarcical Information  
Authors  D. Erickson  
Abstract 
Consider
the
problem
of
n
trustees,
any
k
of
which
are
needed
to
be
in
agreement
to
make
an
action
x.
In
addition,
if
only
(k1)
are
in
agreement,
we
would
like
to
ensure
that
the
action
can
not
be
made.
Solutions
to
this
type
of
problem
have
been
independently
proposed
by
Shamir
(1979)
and
Blakley(1979).
The
solution
is
commonly
referred
to
as
a
threshold
scheme. Numerous uses for threshold schemes are presented. These uses range from protecting encryption keys to preventing military and management actions without proper authority. Several general methods for implementing such schemes are examined in the literature. In this thesis we look at methods based on polynomial interpolation, on the intersection properties in finite geometries, and, more generally, Steiner systems, on those utilizing error correcting codes, and on those employing the Chinese Remainder Theorem. Some of the threshold schemes in the literature present variations to the general scheme including the detection and the prevention of cheating. Others explore the implementation of threshold schemes that permit a hierarchy of authority for the participants in the scheme. The aim of this thesis is to present and explore variations and expansions of existing methods for threshold schemes to accommodate hierarchical information. Some of the proposed schemes not only provide hierarchical information but also implement hierarchical authority.  
Date  May 1993  
Comments  Master's Thesis  1990  
Report  Threshold Schemes with Hierarcical Information (PDF) 
Compressed
PostScript: Threshold Schemes with Hierarcical Information (PS.Z) 
CS9322  

Title  On Object Layout for Multiple Inheritance  
Authors  W. Pugh and G.E. Weddell  
Abstract 
We
consider
the
problem
of
encoding
objects
for
objectoriented
programming
languages
that
allow
subtyping
and
multiple
inheritance
among
class
definitions.
This
is
an
important
problem
since
a
choice
of
encoding
will
determine
the
implementation
for
a
number
of
common
operations:
extracting
a
property
value
from
an
object,
comparing
two
object
references
for
equality,
and
expression
retyping. We expand on earlier work in [9] in which we proposed a new algorithm for obtaining an object encoding that assigns a fixed o set to each property. This allows property values to be extracted with the same efficiency as in systems that do not provide multiple inheritance. We present both analytic and experimental evidence that suggests that this is an important performance issue and that our method works well in practice. Keywords:objectoriented programming languages, object encoding, compilation.  
Date  May 1993  
Report  On Object Layout for Multiple Inheritance (PDF) 
Compressed
PostScript: On Object Layout for Multiple Inheritance (GZIP) 
CS9321  

Title  Pointers versus Arithmetic in PRAMs  
Authors  P. Dyment, F.Fich, N.Nishimura, P.Ragde and L.Ruzzo  
Abstract 
Manipulation
of
pointers
in
shared
data
structures
is
an
important
communication
mechanism
used
in
many
parallel
algorithms.
Indeed,
many
fundamental
algorithms
do
essentially
nothing
else.
A
Parallel
Pointer
Machine,
(or
PPM)
is
a
parallel
model
having
pointers
as
its
principal
data
type.
PPMs
have
been
characterized
as
PRAMs
obeying
two
restrictions
—
first,
restricted
arithmetic
capabilities,
and
second,
the
CROW
memory
access
restriction
(Concurrent
Read,
Owner
Write,
a
commonly
occurring
special
case
of
CREW). We present results concerning the relative power of PPMs (and other arithmetically restricted PRAMs) versus CROW PRAMs having ordinary arithmetic capabilities. First, we prove lower bounds separating PPMs from CROW PRAMs. For example, any stepbystep simulation of an $n$processor CROW PRAM by a PPM requires time $\Omega(\log\log n)$ per step. Second, we show that this lower bound is tight — we give such a stepbystep simulation using $O(\log\log n)$ time per step. As a corollary, we obtain sharply improved PPM algorithms for a variety of problems, including deterministic contextfree language recognition.  
Date  May 1993  
Report  No report 
CS9320  

Title  ADV Charts: a Visual Formalism for Describing Abstract Data Views  
Authors  L.M.F. Carneiro, D.D. Cowan and C.J.P. Lucena  
Abstract 
This
paper
introduces
a
new
visual
formalism,
called
ADVcharts,
for
specifying
the
behaviour
of
interactive
systems
(including
multimodal
interactive
systems)
using
a
statemachinebased
approach.
ADVcharts
combine
concepts
from
Abstract
Data
Views
(ADVs),
with
notations
from
Objectcharts,
Statecharts,
and
Petrinets.
ADVcharts
are
part
of
the
ADV
specification
approach.
In
this
paper,
we
abbreviate
the
``ADV
specification
approach''
term
to
ADVspec.
The
ADVspec
allows
the
designer
to
express
visually
both
the
relationship
among
the
userinterface
objects
and
the
flow
of
control
of
an
interactive
system
using
a
single
integrated
approach.
It
is
intended
that
the
ADVspec
will
serve
as
a
foundation
for
a
future
design
methodology
for
interactive
systems. In particular, we show some aspects of design specific to interactive systems, such as the association of input and output events with particular Abstract Data Views, the concurrency of the components of a user interface, and the representation of various modes (input and output) in the design of an interactive system. The semantics of ADVcharts are presented through the specification of some examples, and we demonstrate that ADVcharts can be used as a visual specification language to represent highly interactive systems from the perspective of the user interface. We conclude this paper by demonstrating that VDMlike specifications can be derived directly from ADVcharts, thus providing the ADV concept with complementary visual and textual formalisms.  
Report  ADV Charts: a Visual Formalism for Describing Abstract Data Views (PDF) 
Compressed
PostScript: ADV Charts: a Visual Formalism for Describing Abstract Data Views (PS.Z) 
CS9317  

Title  Towards CAAI: Computer Assisted Application Integration  
Authors  D.D. Cowan, R.G. Veitch and C.J.P. Lucena  
Abstract  As the manipulation and use of information forms the base of our economic structure, knowledge workers will become software application integrators. That is, knowledge workers who are experts in their specific domain and its related software, will need to "glue" together databases, analysis, simulation, modelling and visualization tools in order to produce timely information for their organization. In order to perform application integration easily we first need to define a coherent supporting architecture and a programming model. This paper outline this architecture and the programming model and indicates that many of the components to implement this model are available. Unfortunately, the design of many of these components is not consistent, thus, making it difficult for a knowledge worker to integrate applications without a large amount of "inside" technical information. Through the definition of these models we have highlighted the problems that need to be resolved. The architecture and programming model described in this paper are based on a large number of experimental systems developed as part of our research program.  
Date  February 1994  
Report  Towards CAAI: Computer Assisted Application Integration (PDF) 
Compressed
PostScript: Towards CAAI: Computer Assisted Application Integration (PS.Z) 
CS9316  

Title  Program Design & Implementation with Abstract Data Views  
Authors  A.B. Potengy, C.J.P. Lucena, D.D. Cowan and R. Ierusalimschy  
Abstract  Creating new applications by integrating user interface and application components is a relatively new idea which is currently of wide interest. A significant part of this problem is clearly defining the separation between user interface and application components. This paper uses simple examples to illustrate a new design and implementation approach based on the concept of an abstract data view (ADV), a structuring method which cleanly defines this separation.  
Date  February 1994  
Report  Program Design & Implementation with Abstract Data Views (PDF) 
Compressed
PostScript: Program Design & Implementation with Abstract Data Views (PS.Z) 
CS9315  

Title  Information Repository Requirements of the CORDS Multidatabase Service  
Authors  N. Coburn and P.A. Larson  
Abstract  A multidatabase is a virtual database. As such, it requires support for the storage and retrieval of its operational data. That is, it requires the equivalent of the data dictionary or catalogue found in traditional relational databases. The CORDS project is a collaborative effort between several IBM laboratories and several North American universities. The goal of the CORDS project is to investigate and prototype a distributed environment which supports the development and operation of distributed applications. The CORDS Multidatabase project is one component within the CORDS environment. A second component of this environment is an Information Repository. We are investigating the viability of using the Information Repository as a means of implementing the Multidatabase catalogue. This report states the (current) Multidatabase data requirements on the Information Repository. We have attempted to outline our future requirements as clearly and broadly as possible. However, since we are creating a research prototype the requirements may change as we gain experience and understanding.  
Date  March 1993  
Report  Information Repository Requirements of the CORDS Multidatabase Service (DVI)  Information Repository Requirements of the CORDS Multidatabase Service (PDF) 
CS9314  

Title  User Interface HighOrder Architectural Models  
Authors  L.M.F. Carneiro, M.H. Coffin, D.D.Cowan and C.J.P.Lucena  
Abstract 
Many
userinterface
design
models
(usually
expressed
through
architectural
designs),
expressed
at
different
levels
of
abstraction,
have
been
proposed
in
the
literature.
These
models
have
been
classified
according
to
several
criteria.
The
various
design
models
are
explicitly
or
implicitly
derivable
from
a
high
order
model
which
constitutes
its
specification.
Existing
classification
schemes
do
not
reflect
this
derivation
process. A new classification scheme for userinterface architectural designs is presented in this paper. This new classification scheme is based on derivations of designs. We analyze the initial specification and the highorder design models which correspond to models proposed in the literature at various levels of abstraction. The goal of the present study is to discuss issues such as relevant properties of ``design families'' (related to design trajectories), specification notations to be used as initial design steps, and ``implementation biases'' induced by different design families. In particular, we put the Abstract Data View model in perspective by reviewing its specification, presenting its highorder architecture, and comparing it with architectures at similar and lower levels of abstraction.  
Date  February 1993  
Report  User Interface HighOrder Architectural Models (PDF) 
Compressed
PostScript: User Interface HighOrder Architectural Models (GZIP) 
CS9313  

Title  Preconditioned Conjugate Gradient Methods for Three Dimensional Linear Elasticity  
Authors  J.K. Dickinson and P.A. Forsyth  
Abstract 
Finite
element
modelling
of
three
dimensional
elasticity
problems
gives
rise
to
large
sparse
matrices.
Various
preconditioning
methods
are
developed
for
use
in
precon
ditioned
conjugate
gradient
iterative
solution
techniques.
Incomplete
factorizations
based
on
levels
of
/ll,
drop
tolerance,
and
a
two
level
hierarchical
basis
are
developed.
Various
techniques
for
ensuring
that
the
incomplete
factors
have
positive
pivots
are
presented.
Computational
tests
are
carried
out
for
problems
generated
using
unstruc
tured
tetrahedral
meshes.
Quadratic
basis
functions
are
used.
The
performance
of
the
iterative
methods
is
compared
to
a
standard
direct
sparse
matrix
solver.
Problems
with
up
to
70,000
degrees
of
freedom,
and
small
(<<
1)
element
aspect
ratio
are
considered. Keywords:Three dimensional elasticity, preconditioning, hierarchical basis Running Title:PCG methods for 3d elasticity AMS Subject Classification:65F10, 65N30  
Date  February 1993  
Report  Preconditioned Conjugate Gradient Methods for Three Dimensional Linear Elasticity (PDF) 
Compressed
DVI: Preconditioned Conjugate Gradient Methods for Three Dimensional Linear Elasticity (DVI.Z) 
CS9305  

Title  Mathematical Output Presentation in User Interfaces for Computer Algebra Systems  
Authors  T. R. Tyhurst  
Abstract 
In
recent
years,
the
evolution
of
user
interfaces
for
Computer
Algebra
Systems
has
lagged
behind
both
the
advances
in
the
algebra
engines
which
they
serve,
and
the
general
developments
seen
in
user
interface
principles
as
a
whole.
The
increased
availability
of
bitmapped
display
devices
and
the
graphical
user
interface
software
running
upon
them
has
served
to
demonstrate
the
limitations
of
existing
computer
algebra
system
interfaces. This thesis discusses some of the design and implementation issues inherent in the construction of an effective user interface for computer algebra systems. The emphasis is upon the efficient handling of the output of algebra systems, and effective techniques for presenting the mathematical content to the user, particularly when the expressions are large. A new user interface for the Maple system is described in light of the issues discussed, and a new variation on an algorithm for breaking long mathematical expressions over multiple lines is presented.  
Date  October 1992  
Report  Mathematical Output Presentation in User Interfaces for Computer Algebra Systems (PDF) 
Compressed
PostScript: Mathematical Output Presentation in User Interfaces for Computer Algebra Systems (PS.Z) 
CS9303  

Title  On Lambert's W Function  
Authors  R.M. Corless, G.H. Gonnet, D.E.G. Hare and D.M. Jeffrey  
Abstract  The Lambert W function is defined to be the multivalued inverse of the function w→we^w It has many applications in pure and applied mathematics, some of which are briefly described here. We present a new discussion of the complex branches of W, an asymptotic expansion valid for all branches, an efficient numerical procedure for evaluating the function to arbitrary precision, and a method for the symbolic integration of expressions containing W.  
Date  January 1993  
Report  On Lambert's W Function (PDF) 
Compressed
PostScript: On Lambert's W Function (PS.Z) 
CS9302  

Title  Linear and Nonlinear Methods for the Incompressible NavierStokes Equations  
Authors  Simon S. Clift and Peter A. Forsyth  
Abstract  In this study, the discretized finite volume form of the two dimensional, incompressible Navier Stokes equations is solved using both a frozen coefficient and a full Newton nonlinear iteration. The optimal method is a combination of these two techniques. The linearized equations are solved using a conjugategradientlike method (CGSTAB). Various different types of preconditioning are developed. Completely general sparse matrix methods are used. Investigations are carried out to determine the effect of finite volume cell anisotropy on the preconditioner. Numerical results are given for several test problems.  
Date  January 1993 Revised August 1993  
Comments  Submitted to: International Journal for Numerical Methods in Fluids  
Report  Linear and Nonlinear Methods for the Incompressible NavierStokes Equations (PDF) 
Compressed
PostScript: Linear and Nonlinear Methods for the Incompressible NavierStokes Equations (PS.Z) 
CS9301  

Title  GRAIL: Enginering Automata in C++  
Authors  D. Raymond and D. Wood  
Abstract  Grail is a package for computing with finite automata and regular expressions, written in C++. Grail supports input and output of textual descriptions of automata and regular expressions, conver sions between automata and regular expressions, and other opera tions. Grail can be used as a set of shellcallable processes, a library of functions, or as individual C++ classes. This docu ment describes the history, design, and organization of Grail; the appendix contains a list of all classes and a short descrip tion of each function.  
Date  January 1993  
Report  GRAIL: Enginering Automata in C++ (PDF) 
Compressed
PostScript: GRAIL: Enginering Automata in C++ (GZIP) 