Contention-free communication scheduling for array redistribution

Array redistribution is required often in programs on distributed memory pa rallel computers. It is essential to use efficient algorithms for redistrib ution, otherwise the performance of the programs may degrade considerably. The redistribution overheads consist of two parts: index computation and in terprocessor communication. If there is no communication scheduling in a re distribution algorithm, the communication contention may occur, which incre ases the communication waiting time. In order to solve this problem, in thi s paper, we propose a technique to schedule the communication so that it be comes contention-free, Our approach initially generates a communication tab le to represent the communication relations among sending nodes and receivi ng nodes. According to the communication table, we then generate another ta ble named communication scheduling table. Each column of communication sche duling table is a permutation of receiving node numbers in each communicati on step. Thus the communications in our redistribution algorithm are conten tion-free. Our approach can deal with multi-dimensional "shape changing red istribution". (C) 2000 Elsevier Science B.V. All rights reserved.