Files in this item



application/pdf8924842.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:The mesh of trees architecture for parallel computation
Author(s):Hornick, Scot W.
Department / Program:Electrical and Computer Engineering
Discipline:Electrical and Computer Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
Computer Science
Abstract:This thesis considers the mesh of trees architecture as both a special-purpose and a general-purpose parallel computer. A family of special-purpose VLSI architectures for computing an ($n\sb1 \times n\sb2 \times \cdots \times n\sb{d}$)-point multidimensional DFT over $\doubz\sb{M}$, the ring of integers modulo $M$, is proposed. Using the two-dimensional mesh of trees as a component, these architectures achieve optimal VLSI area $A$ = $\Theta((N\sp2\log\sp{2}M)/T\sp2)$ for any given computation time $T\ \epsilon$ ($\Omega(\log N),O(\sqrt{N\log M})\rbrack.$
The convergence properties of Newton's method are studied. By introducing and formalizing the notion of attunement of a linear system of equations, it is shown that Newton's method provides polylog-time solutions for a broader class of linear systems than was previously supposed. In particular, the system matrix need not be well-conditioned; all that is required is that the known vector be well-attuned to the system matrix. It is then shown that Newton's method can be implemented on a special-purpose architecture based on the three-dimensional mesh of trees. This same architecture can be used to construct the stiffness equations arising from a finite element approximation. Furthermore, it can be hybridized with a systolic array to achieve a processor-time or area-time tradeoff.
Then, in a different vein, the two-dimensional mesh of trees is studied as a general-purpose parallel computer. It is shown that this architecture can afford finer memory granularity and, thereby, reduce the memory redundancy required for deterministic P-RAM simulation. A distributed-memory, bounded-degree network model of parallel computation is proposed that allows one to take greater advantage of the potential for fine-grain memories without sacrificing other aspects of realism. The simulation scheme presented is admitted by this new model and achieves constant memory redundancy.
Issue Date:1989
Rights Information:Copyright 1989 Hornick, Scot Wayne
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI8924842
OCLC Identifier:(UMI)AAI8924842

This item appears in the following Collection(s)

Item Statistics