Isotropic graphs with applications to parallel computation
Piertracaprina, Andrea
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/18965
Description
Title
Isotropic graphs with applications to parallel computation
Author(s)
Piertracaprina, Andrea
Issue Date
1994
Doctoral Committee Chair(s)
Liu, C.L.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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 ad-hoc 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 ad-hoc 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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
