Sponsor:
- DoD Modernization Program
Project Team Members:
Northwestern University
- Prof. Alok Choudhary
- Prof. Wei-keng Liao
Syracuse University
- Prof. Donald Weiner
- Prof. Pramod Varshney
Air Force Research Labs
- Dr. Richard Linerman
- Dr. Mark Linerman
Inter-task Data Redistribution
Applications such as STAP entail multiple algorithms (or processing steps), each of which performs particular functions, to be executed in a pipelined fashion. Each task needs to be parallelized for the required performance. This, in turn, requires addressing the issue of data distribution on the subset of compute nodes on which a task is parallelized to obtain good efficiency and incur minimal communication overhead.
In an integrated system which implements several tasks that feed data to each other, data redistribution is required when it is fed from one parallel task to another. This is because the way data is distributed in one task may not be the most appropriate distribution for another task for algorithmic or efficiency reasons. Data redistribution also allows communication to take place at the beginning and the end of each task.
In the parallel pipeline system shown in Figure pipeline model, compute nodes are partitioned into several disjoint groups and each group is assigned to exactly one task in the pipeline. As one group of nodes completes its computation on one set of input data, its output is to be transferred to its successor group or groups, depending on the structure of the pipeline. Data transfer between two tasks represents interprocessor communication between two groups of compute nodes. Since the data access patterns of one task may be different from its successor tasks, communication patterns can be either a corner-turn or a left-right shift pattern.
For example, given a three-dimensional input array to one parallel task, the array is evenly partitioned into several sub-arrays across multiple compute nodes assigned to this task. This partitioning can be done along one of the array's three axes due to the efficiency of memory access. However, after the completion of computation, partitioning of the output array of one group along the same axis may not be suitable for its successor group. Since any single data layout will not always provide efficient computation for data access along two orthogonal axes, the data re-mapping problem exists when intermediate data is transmitted between different parallel tasks. This communication pattern is called a corner-turn communication pattern, shown in Figure 1(a). A three-dimensional array is partitioned along axis z for task p with 3 compute nodes while it is partitioned along axis x for task q with 4 node\s. Therefore, it may be necessary to reorganize the data during the send phase of one task and receive phase of its successor task. The corner-turn communication pattern involves a complete exchange (all-to-all) pattern between two groups of compute nodes.
On the other hand, the left-right shift communication pattern occurs when an array is partitioned along the same axis between two consecutive parallel tasks. In Figure 1(b), a three-dimensional array is partitioned along axis x for both p and q tasks. Left-right shift communication pattern does not involve data reorganization. Each node in one task only communicates with some of the nodes in its successor task (a many-to-many communication.) Therefore, the communication overhead of left-right shift pattern is much less than the corner-turn pattern.
Click here to go back
