IJPAM: Volume 2, No. 3 (2002)
REDISTRIBUTION OF FIXED EXCHANGED
MESSAGES OVER A MULTIPROCESSOR GRID
University of Macedonia
Applied Informatics Dept.
156 Egnatia Str., P.O. Box 1591
540 06 Thessaloniki, GREECE
Abstract.This paper presents a mathematical model used to solve an instance of the problem of redistributing data over a parallel processor grid during run-time. This particular instance is moving from a cyclic(r) redistribution on a P-processor grid to cyclic(s) on a P-processor grid, where s is a multiple of r. In this paper, we introduce mathematical definitions and propositions concerning important factors of the data redistribution problem between parallel processors. These are the total communication cost, the communications pattern and the communication scheduling, that is, the messages to be exchanged between processors. The total cost factor is critical when redistributing data, since the redistribution is performed during run-time. The communication pattern is directly induced by the redistribution parameters. When scheduling the communication processor pairs, it is important to know which processors can communicate. The communication scheduling organizes the redistribution in communicating steps, such that each processor sends and receives one message at each time. Scheduling is based on a number of matrix transformations, which correspond to local memory operations of the processors involved.
Received: April 23, 2002
AMS Subject Classification: 68M07
Key Words and Phrases: redistribution, block-cyclic redistribution, communication scheduling, cost analysis, communication pattern
Source: International Journal of Pure and Applied Mathematics