Stavros Souravlas, Manos Roumeliotis
University of Macedonia
Applied Informatics Dept.
156 Egnatia Str., P.O. Box 1591
540 06 Thessaloniki, GREECE
e-mail: [email protected]
e-mail:[email protected]

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
ISSN: 1311-8080
Year: 2002
Volume: 2
Issue: 3