Vortrag G. Schreiber, TU Hamburg

[Maria Cherry]

                          UNIVERSITAET WIEN 
          INSTITUT FUER SOFTWARETECHNIK UND PARALLELE SYSTEME
                            gemeinsam mit 
                                VCPC 
           EUROPEAN CENTRE FOR PARALLEL COMPUTING AT VIENNA 


      EINLADUNG ZU EINEM VORTRAG IM RAHMEN DES INSTITUTS-KOLLOQUIUMS:
                
               Redistribution of Linear Data Distributions 

 			      Gerald Schreiber 
                             TU Hamburg-Harburg
                           Technische Informatik I


                 ZEIT: Montag, 6. 10. 1997, 17 Uhr c.t.
       ORT: Institut fuer Softwaretechnik und Parallele Systeme
                  1090 Wien, Liechtensteinstrasse 22, 
                         Seminarraum, Mezzanin


Abstract


Within the data parallel programming paradigm, the choice of the data
distribution is often decisive for the performance attainable. The
main factors controlled by the data distribution are: number and size
of messages to be communicated, overlap of communication and 
computation, and load balancing. As those factors cannot be adjusted
independently, it is apparent that the choice of ``the right'' data
distribution is highly application dependent. From that arise two
requirements: it is necessary for a parallel programming environment
to provide for a variety of data distributions and for the possibility
to redistribute data at runtime.

The basic data distributions defined by HPF (block, cyclic, and
block-cyclic) have found their way into numerous other parallel
programming environments and have proved to be sufficient for many
numerical algorithms operating on regular data structures. However,
for other areas of application, e.g. image processing, a higher
flexibility is required.  

The redistribution of data, although specified in HPF, is discouraged
because of its potentially very high communication effort.
Nevertheless, redistribution can often lead to better performance
especially when applications are built from library functions having
differing prefered data distribution. In these cases, the potential
performance loss due to unsuitable data distribution often outweighs
the cost of a data redistribution. In parallel image processing, this
situation is encountered when high-level functions are applied after
low-level image preprocessing has taken place. The nearest neighbor
data dependencies of low-level functions call for block-type
distributions, whereas more complex distributions are required for the
global data dependencies in higher levels.

In the literature, data redistribution is often considered independent
from the underlying communication network. While this allows to
control the number and size of messages, it imposes limitations to the
optimization of node and edge congestion.  In this talk, data
distributions stemming from bit and linear permutations are
introduced. These distributions cover a subset of the basic data
distributions defined by HPF. The focus of the talk will be on
algorithms for the efficient redistribution of bit and linear data
distributions. The algorithms presented are designed to minimize node
and edge congestion assuming a de Bruijn communication network.