CPRC-TR92207-S

Title:	  Relaxing SIMD Control Flow Constraints Using Loop 
	  Transformations

Authors:  R. v. Hanxleden*, K. Kennedy, C. Koelbel, R. Das, J. Saltz  

Date:	  August 1992

* student author

Keywords:
  Distributed memory, Irregular applications, Communication analysis,
  Data flow analysis, Fortran D, High Performance Fortran

Abstract:

Many loop nests in scientific codes contain a parallelizable outer
loop but have an inner loop for which the number of iterations varies
between different iterations of the outer loop.  When running this
kind of loop nest on a SIMD machine, the SIMD-inherent restriction to
single program counter common to all processors will cause a
performance degradation relative to comparable MIMD implementations.
This problem is not due to limited parallelism or bad load balance, it
is merely a problem of control flow.

This paper presents a loop transformation, which we call loop
flattening, that overcomes this limitation by letting each processor
advance to the next loop iteration containing useful computation, if
there is such an iteration for the given processor.  We study a
concrete example derived fro a molecular dynamics code and compare
performance results for flattened and unflattened versoins of this
kernel on two SIMD machines, the CM-2 and the DECmpp 12000.  We then
evaluate loop flattening from the compiler's perspective in terms of
arguing that loop flattening, whethere performed by the programmer or
by the compiler, introduces negligible overhead and can significantly
improve the performance of scientific codes for solving irregular
problems. 


Appeared in:  Proceedings of the ACM SIGPLAN '92 Conference on Program
	      Language Design and Implementation, San Francisco, CA