Announcing the
			 Final Examination of
			    Thomas J. Loos
			       for the
	  Degree of Doctor of Philosophy in Computer Science
		      November 15, 1996 10:00 AM
			  Lindley Hall 215D

Dissertation: A New Model for Solving the Data Distribution Problem

The data distribution problem is the problem of determining the layout
or   distribution of computer   data  in preparation  for executing  a
program  on a parallel computer  such that the   execution time of the
program is minimized.  The specific case  considered in this thesis is
the execution  of a parallel  iterative  linear systems  solver  code,
whose data primarily consist  of the matrix and  vectors of the linear
system to be  solved and vectors used  by the solver code to determine
the system's solution.

Data distributions are commonly determined  using a graph partitioning
algorithm, which  is input a graph  of the matrix  of interest.  Graph
partitioning algorithms typically try  to minimize the number of edges
cut   by   the partitioning,   which is    a    rough measure  of  the
communications  required by the   solver code.  Results are  presented
that  show the number  of  edges cut  is  a poor  predictor the solver
code's execution time.  This is because the  calculation of the number
of edges cut  ignores the algorithm used  to solve the linear  system,
the matrix data structure, and parallel computational environment, all
of which affect the solver code's execution time.

The approximate execution time (AET) metric is proposed to replace the
number of edges  cut as the measure  of a data distribution's quality.
The AET metric  is  based on a model  of  parallel program performance
that   assumes a parallel  program spends  most of  its time executing
kernels, or functions that  perform basic operations.  The AET  metric
estimates  the performance of  a solver code   based on combining cost
estimates of each   of the solver code's   kernels.   This provides  a
comparatively easy way to model solver codes while leading to the best
currently available estimates of a solver  code's execution time.  The
solver code HMPE was written as part of  the thesis in accord with the
model of  a parallel program  described above.   Results show the  AET
metric  accurately predicts the  execution time  of  HMPE, in terms of
time per solver iteration.

Outline of Studies			Educational Career

Major: Computer Science			B.S. - University of Nebraska-Lincoln, 1986
Minor: Mathematics			M.S. - North Carolina State University, 1987

			 Committee in Charge

Assistant Professor Randall Bramley, Chair, 855-7790, Computer Science
Professor Dennis Gannon, Computer Science
Assistant Professor Michael Jolly, Mathematics
Professor David Wise, Computer Science


				Approved:   _________________________________________
					    Randall Bramley

(Any member of the Graduate Faculty may attend. As a courtesy, please notify the 
Committee Chairman in advance)