| CS-93-60 | ||||
|---|---|---|---|---|
| Title | OPTIMUM LOGIC ENCODING AND LAYOUT WIRING FOR VLSI DESIGN: A GRAPH-THEORETIC APPROACH | |||
| Authors | Chuan-Jin 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
hazard-free
asynchronous,
circuits.
We
show
that
these
two
problems
have
the
same
combinatorial
structure,
which
can
be
captured
by
a
new
graph-theoretic
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 NP-complete. We present an integer linear programming formulation for maximum balance of signed hypergraphs, and a polynomial-size 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 real-weighted 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 so-called cluster-cover 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 polynomial-size linear programming formulation. For the case of multi-way splits ($k >3$), it provides a direct and efficient local search for timing-driven 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 hazard-free 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 GRAPH-THEORETIC APPROACH (PDF) |
Compressed
PostScript: OPTIMUM LOGIC ENCODING AND LAYOUT WIRING FOR VLSI DESIGN: A GRAPH-THEORETIC APPROACH (PS.Z) | ||
| CS-93-57 | ||||
|---|---|---|---|---|
| Title | A Rationale for Both Nesting and Inheritance in Object-Oriented 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 object-oriented 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: 223-237 | |||
| Report | A Rationale for Both Nesting and Inheritance in Object-Oriented Design (PDF) |
Compressed
PostScript: A Rationale for Both Nesting and Inheritance in Object-Oriented Design (GZIP) | ||
| CS-93-55 | ||||
|---|---|---|---|---|
| Title | Sequential and Parallel Algorithms for Embedding Problems on Classes of Partial k-Trees | |||
| Authors | A. Gupta and N. Nishimura | |||
| Abstract | We present sequential and parallel algorithms for various embedding problems on bounded degree partial k-trees and k-connected partial k-trees; these include subgraph isomorphism and topological embedding, known to be NP-complete for general partial k-trees. 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 tree-like representation of the graph (the tree-decomposition 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 k-Trees (PDF) |
Compressed
PostScript: Sequential and Parallel Algorithms for Embedding Problems on Classes of Partial k-Trees (PS.Z) | ||
| CS-93-54 | ||||
|---|---|---|---|---|
| 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) | ||
| CS-93-52 | ||||
|---|---|---|---|---|
| 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) | ||
| CS-93-49 | ||||
|---|---|---|---|---|
| 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 envelope-reducing 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 2-sum 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 Gibbs-Poole-Stockmeyer (GPS) algorithm or the reverse Cuthill-McKee (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) | |
| CS-93-48 | ||||
|---|---|---|---|---|
| Title | A Goal-Directed Functionally-Based 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
computer-assisted
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
second-language
learner
develop
a
more
natural
and
appropriate
style,
and
produce
higher
quality
translations
of
text. A foundation for AI-based computational style has been laid by DiMarco, with extensions by Green, Makuta-Giluk, Mah, and Payette in generation, rhetoric, comparative stylistics, and intelligent computer-aided 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 human-independent computer analysis of style is a feasible goal for computational linguistics. | |||
| Date | Sept 1993 | |||
| Comments | Masters Thesis | |||
| Report | A Goal-Directed Functionally-Based Style Analyzer (PDF) |
Compressed
PostScript: A Goal-Directed Functionally-Based Style Analyzer (PS.Z) | ||
| CS-93-46 | ||||
|---|---|---|---|---|
| Title | Performing Group-by Before Join | |||
| Authors | P. Yan and P.-A. Larson | |||
| Abstract | Assume that we have an SQL query containing joins and a group-by. The standard way of evaluationg this type of query is to first perform all the joins and then the group-by operation. However, it may be possible to perform the group-by early, that is, to push the group-by 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 Group-by Before Join (PDF) |
Compressed
PostScript: Performing Group-by Before Join (PS.Z) | ||
| CS-93-43 | ||||
|---|---|---|---|---|
| Title | Constraint-Based 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 | Constraint-Based Rendering for Scenes with High Dynamic Ranges (PDF) |
Compressed
PostScript: Constraint-Based Rendering for Scenes with High Dynamic Ranges (PS.GZ) | ||
| CS-93-42 | ||||
|---|---|---|---|---|
| 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) | ||
| CS-93-41 | ||||
|---|---|---|---|---|
| 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 well-known 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) | ||
| CS-93-40 | ||||
|---|---|---|---|---|
| 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, null-space basis, row-space 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) | |
| CS-93-38 | ||||
|---|---|---|---|---|
| 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) | ||
| CS-93-33 | ||||
|---|---|---|---|---|
| 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 non-positive 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) | ||
| CS-93-31 | ||||
|---|---|---|---|---|
| Title | Computing Values and Derivatives of Bezier and B-spline 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 B-spline 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 B-spline Tensor Products (PDF) |
Compressed
PostScript: Computing Values and Derivatives of Bezier and B-spline Tensor Products (PS.Z) | ||
| CS-93-30 | ||||
|---|---|---|---|---|
| Title | An Illustration Technique for Unstructured 3-D Meshes | |||
| Authors | N.P. Konrad and R.B. Simpson | |||
| Abstract |
Geometric
relations
in
an
irregular
3-D
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 3-D Meshes (PDF) |
Compressed
PostScript: An Illustration Technique for Unstructured 3-D Meshes (PS.Z) | ||
| CS-93-29 | ||||
|---|---|---|---|---|
| Title | The Design and Analysis of Asynchronous Up-Down Counters | |||
| Authors | J.P.L. Segers | |||
| Abstract |
The
goal
of
this
report
is
to
investigate
up-down
counter
implementations
in
the
framework
of
delay-insensitive
circuits.
An
up-down
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
up-down
N-counter
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.
Up-down
counters
have
many
applications.
For
example,
they
can
be
useful
in
implementing
queues
or
stacks. Various implementations for up-down N-counters 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 Up-Down Counters (PDF) |
Compressed
DVI: The Design and Analysis of Asynchronous Up-Down Counters (DVI) | ||
| CS-93-28 | ||||
|---|---|---|---|---|
| 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 elastic-bucket 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) | ||
| CS-93-27 | ||||
|---|---|---|---|---|
| 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) | |
| CS-93-26 | ||||
|---|---|---|---|---|
| Title | Enhancing Software Design Reuse: Nesting in Object-Oriented 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
object-oriented
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 Object-Oriented Design (PDF) |
Compressed
PostScript: Enhancing Software Design Reuse: Nesting in Object-Oriented Design (PS.Z) | ||
| CS-93-25 | ||||
|---|---|---|---|---|
| Title | Model Checking Timing Requirements | |||
| Authors | J.M. Atlee and J. Gannon | |||
| Abstract | Model checking has been used successfully to analyze concurrent, finite-state 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 real-time properties can be verified with a model checker for branching-time temporal logic. In addition, we compare our system for analyzing SCR requirements with other model checkers that verify properties of real-time systems. | |||
| Date | February 1994 | |||
| Comments | Submitted to TOSEM for publication. | |||
| Report | Model Checking Timing Requirements (PDF) |
Compressed
PostScript: Model Checking Timing Requirements (PS.Z) | ||
| CS-93-24 | ||||
|---|---|---|---|---|
| Title | Conflict-Free Accedss to Rectangular Subarrays in Parallel Memory Modules | |||
| Authors | D. Erickson | |||
| Abstract |
In
a
parallel
computing
environment,
we
consider
conflict-free
access
to
constant-perimeter
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
conflict-free
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
constant-perimeter
rectangular
subarrays. A square is `perimeter rectangular conflict-free' (p_rcf) if it is conflict-free for all rectangular subarrays whose perimeter is less than or equal to 2p. If p is even, the problem is to provide conflict-free 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 conflict-free 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 constant-perimeter rectangular subarrays, in particular all (x-i)(y+i) rectangular subarrays of an (n)(n) array for all nonnegative i where p=x+y. The linear results for the constant-perimeter 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 conflict-free access to constant-area rectangular subarrays. An upper bound is found using a technique of relating conflict-free access to the chromatic number of a graph. In addition to bounds for constant-area 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 | Conflict-Free Accedss to Rectangular Subarrays in Parallel Memory Modules (PDF) |
Compressed
PostScript: Conflict-Free Accedss to Rectangular Subarrays in Parallel Memory Modules (GZIP) | ||
| CS-93-23 | ||||
|---|---|---|---|---|
| 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
(k-1)
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) | ||
| CS-93-22 | ||||
|---|---|---|---|---|
| Title | On Object Layout for Multiple Inheritance | |||
| Authors | W. Pugh and G.E. Weddell | |||
| Abstract |
We
consider
the
problem
of
encoding
objects
for
object-oriented
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:object-oriented 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) | ||
| CS-93-21 | ||||
|---|---|---|---|---|
| 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 step-by-step 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 step-by-step 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 context-free language recognition. | |||
| Date | May 1993 | |||
| Report | No report | |||
| CS-93-20 | ||||
|---|---|---|---|---|
| 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
multi-modal
interactive
systems)
using
a
state-machine-based
approach.
ADVcharts
combine
concepts
from
Abstract
Data
Views
(ADVs),
with
notations
from
Objectcharts,
Statecharts,
and
Petri-nets.
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
user-interface
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 VDM-like 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) | ||
| CS-93-17 | ||||
|---|---|---|---|---|
| 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) | ||
| CS-93-16 | ||||
|---|---|---|---|---|
| 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) | ||
| CS-93-15 | ||||
|---|---|---|---|---|
| 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) | ||
| CS-93-14 | ||||
|---|---|---|---|---|
| Title | User Interface High-Order Architectural Models | |||
| Authors | L.M.F. Carneiro, M.H. Coffin, D.D.Cowan and C.J.P.Lucena | |||
| Abstract |
Many
user-interface
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 user-interface architectural designs is presented in this paper. This new classification scheme is based on derivations of designs. We analyze the initial specification and the high-order 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 high-order architecture, and comparing it with architectures at similar and lower levels of abstraction. | |||
| Date | February 1993 | |||
| Report | User Interface High-Order Architectural Models (PDF) |
Compressed
PostScript: User Interface High-Order Architectural Models (GZIP) | ||
| CS-93-13 | ||||
|---|---|---|---|---|
| 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 3-d 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) | ||
| CS-93-05 | ||||
|---|---|---|---|---|
| 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) | ||
| CS-93-03 | ||||
|---|---|---|---|---|
| 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) | ||
| CS-93-02 | ||||
|---|---|---|---|---|
| Title | Linear and Non-linear Methods for the Incompressible Navier-Stokes 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 conjugate-gradient-like 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 Non-linear Methods for the Incompressible Navier-Stokes Equations (PDF) |
Compressed
PostScript: Linear and Non-linear Methods for the Incompressible Navier-Stokes Equations (PS.Z) | ||
| CS-93-01 | ||||
|---|---|---|---|---|
| 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 shell-callable 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) | ||