University of Waterloo

1993 technical reports

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)