-------------------------------------------------------------------------------
				       
				       
		       B O S T O N   U N I V E R S I T Y
				       
			  Computer Science Department
				       
			      C O L L O Q U I U M
				       
			    Tuesday April 19, 1994
				       
				    12:00 Noon
			  (Coffee served at 11:30am)
				       
			    Seminar Room / MCS 135
				       
				       
-------------------------------------------------------------------------------



		Performance Prediction for Parallel Programmers
				       
				 Mark Crovella
			    University of Rochester


   Parallel programs  often behave  in  unexpected ways due  to the complex
   relationship between the structure of a parallel program, the machine on
   which it is run, the number of processors used, the program's input, and
   the measured running  time of  the program.   As a  result,  performance
   tuning is an error-prone, time-consuming process.  In  this talk we will
   describe a  set of tools  and  methods for  assisting  the programmer in
   finding the    best-performing  implementation for   a  program, and  in
   answering  common questions that   arise  during the  performance tuning
   process.

   Our approach is  based on  three contributions:  1) new  metrics for the
   measurement of parallel applications; 2)  a new approach to the analysis
   of parallel  program  performance; and 3)  a  new modelling method  that
   allows the programmer to predict the performance of a program in advance
   of  a complete implementation.   The metrics, which  we call performance
   predicates, provide measurements that are amenable  to analysis, and yet
   completely capture parallel overheads.  The analysis method, lost cycles
   analysis, applies algorithmic  analysis to parallel  overheads, assisted
   by an on-line tool.  The modelling method allows lost cycles analysis to
   be applied to  program fragments,  and  provides rules for   aggregating
   analytic results  into  a model for  the  execution time  of a (possibly
   not-yet-implemented)  parallel application.   We use implementations  of
   subgraph  isomorphism and  2D FFT  on  the SGI   Power Series  and  KSR1
   multiprocessors to  illustrate our methods and tools,   and show how our
   approach  can be  used  to  explain  surprising  performance results and
   predict the performance of alternative implementations of an application
   in   advance  of implementation,   while   avoiding  large  numbers   of
   measurements for performance tuning.

   Host: Prof. Steve Homer

-------------------------------------------------------------------------------
   For more information contact Prof. Azer Bestavros  <bestavros@cs.bu.edu>
-------------------------------------------------------------------------------