[Colloquium] Gomez/Dissertation Defense/1-20-05

[Margaret Jaffey]

	Department of Computer Science/The University of Chicago

			*** Dissertation Defense ***


Candidate:  Ernesto Gomez

Defense Date:  Thursday, January 20, 2005

Time and Location:  9:00 a.m. in Ryerson 251

Thesis Title:  Single Program Task Parallelism

Abstract:

The SPMD (Single Program - Multiple Data) paradigm used by most
common distributed processing software such as MPI leaves open
the possibility that different sections of code within the same
program will execute concurrently, as a result of logic depending
on data which is different at each process. This leads to the implicit
formation of subgroups of processes executing common code, but
these sets are not known until runtime since they are data-dependent.
We call these process sets Merging Implicit Process Sets (MIPS).

We describe an analysis of the program CFG (control flow graph) that
allows identification of the points in the program at which the process
set changes either through a group splitting into subgroups or
by a merge of subgroups into a larger group. We show the conditions
on the program code which permit us to prove that these split and
merge points can be identified, and derive an algorithm to do so.
We show conditions on communications required to ensure determinism
and freedom from deadlock in an MIPS execution.

We further describe a technique called Overlapping, in which intervals
between variable definition and use at sender and receiver are  
overlapped
to permit a runtime system to dynamically schedule communication
while minimizing waits at either process, and a Shortcutting
technique which can sometimes be used in conjunction with MIPS to
potentially obtain super scalar computational speedup.

We present a software library called SOS (Shortcutting, Overlapping
and MIPS) which implements the necessary runtime code.

Candidate's Advisor:  Prof. L. Ridgway Scott

------------------------------------------------------------------------ 
---------
A draft copy of Mr. Gomez's dissertation is available in Ry 161A.
------------------------------------------------------------------------ 
----------

--  
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margaret P. Jaffey				margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)		(773) 702-6011
The University of Chicago		http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-