1993 Technical Reports | SCS | UW
[Please remove <h1>]
| 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. |
| Date |
|
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 classiffications: 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 |
|
Adobe
PDF |
Compressed
PostScript |
| 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.
Key Words: programming languages, program specification, software
design and implementa- tion, software engineering |
| Date |
March 1994 |
| Report |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
|
|
| 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 behavior 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
Latex |
|
Adobe
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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
Latex |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |
| 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 |
|
|
Adobe
PDF |
Compressed
PostScript |