Files in this item
Files  Description  Format 

application/pdf 9503296.pdf (4MB)  (no description provided) 
Description
Title:  Isotropic graphs with applications to parallel computation 
Author(s):  Piertracaprina, Andrea 
Doctoral Committee Chair(s):  Liu, C.L. 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Computer Science 
Abstract:  This thesis studies the construction of expanding graphs and their applications to parallel computation. In particular, we consider explicit construction techniques, based on finite fields, that provide graphs which exhibit good expansion properties at low densities and can be efficiently implemented. These techniques are related to the one introduced by Morgenstern, based on quotients of the projective linear group over a finite field, which was originally employed for constructing bounded concentrators of density q, for any prime power $q > 2$. We first analyze a subfamily of Morgenstern's bounded concentrators showing their excellent expansion properties in some special cases, and proving a number of important structural properties. We then generalize the technique, constructing expanding graphs that are suitable to design memory organization schemes for multiprocessor systems where M shared variables are to be distributed among N processors connected by a network (a problem largely studied in the context of PRAM simulation). We devise three schemes for $M\in O(N\sp{1.5}),\ M\in O(N\sp2)$ and $M\in O(N\sp3)$, respectively, on the Module Parallel Computer (MPC), consisting of N processors fully interconnected. In each scheme the variables are replicated into a (constant) number of copies, and the distribution of the copies among the processors is governed by a certain expanding graph. An adhoc access protocol allows the processors to read or write in parallel any set of N variables in time $O(N\sp{1/3}),\ O(N\sp{1/2})$ and $O(N\sp{2/3})$, respectively, in the worst case. The three schemes have a practical implementation and represent the first explicit deterministic memory organization schemes for the MPC to achieve a nontrivial time performance. Finally, we develop a memory organization scheme to distribute $M = N\sp\alpha$ variables, 1 $<$ $\alpha$ $<$ 2, among N processors interconnected by a mesh. The memory distribution is governed by a hierarchical structure, consisting of a cascade of expanding graphs, and an adhoc access protocol allows the processors to read or write in parallel any set of N variables in time that, for $\alpha\leq 3/2$ is close to the $\Omega(\sqrt{N})$ lower bound imposed by the network's diameter, and that, in general, never exceeds $N\sp{5/8}$. This scheme has an efficient implementation and represents the first explicit deterministic memory organization scheme on a bounded degree network. Moreover, it uses the properties of the underlying expanding graphs to control both memory contention and network congestion, two problems that previous works have always tackled separately. 
Issue Date:  1994 
Type:  Text 
Language:  English 
URI:  http://hdl.handle.net/2142/18965 
Rights Information:  Copyright 1994 Piertracaprina, Andrea 
Date Available in IDEALS:  20110507 
Identifier in Online Catalog:  AAI9503296 
OCLC Identifier:  (UMI)AAI9503296 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science