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.