## Files in this item

FilesDescriptionFormat

application/pdf

8924842.pdf (4MB)
(no description provided)PDF

## Description

 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 Degree: Ph.D. Genre: Dissertation 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 Type: Text Language: English URI: http://hdl.handle.net/2142/23253 Rights Information: Copyright 1989 Hornick, Scot Wayne Date Available in IDEALS: 2011-05-07 Identifier in Online Catalog: AAI8924842 OCLC Identifier: (UMI)AAI8924842
﻿