Data distribution concepts for parallel image processing

Data distributions gained a considerable interest in the field of data parallel programming. In most cases they are key factors for the efficiency of the implementation. In this paper we analyze data distributions suited for parallel image processing and those defined by some of todays more popular parallel languages (HPF, Vienna Fortran, pC++) and libraries (ScaLAPACK). The majority of them belong to the class of bit permutations. These permutations can efficiently be realized on networks that are based on shuffle permutations. As a result we propose to widen the scope of data distributions tolerated by parallel languages and libraries towards classes of distributions. For the large class of the so called normal algorithms we demonstrate that it is possible to implement library functions that can handle a large subclass of distributions thereby avoiding redistribution. As the application level of programming data distributions are to be handled analogously to data types