CS-551: Homework Assignment -- Data distribution & HPF

BU/CLA CS-551

Parallel Computing: Models, Languages, and Architectures

Data distribution & HPF

Define the ceiling division function (using Fortran integer arithmetic with truncation toward zero) as:

CD(J,K) = (J+K-1)/K

Similarily, define the ceiling remainder function as:

CR(J,K) = J-K*CD(J,K)

Let (d) be the size of a distributee in a certain dimension. Let (p) be the size of the processor arrangement in the corresponding dimension. For simplicity, assume all dimensions have a lower bound of 1.

BLOCK(m) means that a distributee position, whose index along that dimension is (j), is mapped to an abstract processor whose index along the corresponding dimension of the processor arrangement is CD(j,m) (note that (m*p >= d) must be true), and is position number m+CR(j,m) among positions mapped to that abstract processor. The first distributee position in abstract processor (k) along that axis is position number 1+m*(k-1). By definition, BLOCK means the same as BLOCK(CD(d,p)).

CYCLIC(m) means that a distributee position, whose index along that dimension is (j), is mapped to an abstract processor whose index along the corresponding dimension of the processor arrangement is 1+MODULO(CD(j,m)-1,p). The first distributee position in abstract processor (k) along that axis is position number 1+m*(k-1). By definition, CYCLIC means the same as CYCLIC(1).

Prove that CYCLIC(m) and BLOCK(m) imply the same distribution when m*p >= d.
When do CYCLIC and BLOCK (without argument expressions) imply the same distribution?

This document has been prepared by Professor Azer Bestavros <best@cs.bu.edu> as the WWW Home Page for CS-551, which is part of the NSF-funded undergraduate curriculum on parallel computing at BU.

Date of last update: November 22, 1994.