Isotropic graphs with applications to parallel computation

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.U of I OnlyETDs are only available to UIUC Users without author permissio