Minimizing the Data Transfer in Evaluating an Expression in a Distributed-Memory Parallel-Processing System

Hiroshi OHTA  Kousuke SAKODA  Koichiro ISHIHARA  

IEICE TRANSACTIONS on Information and Systems   Vol.E77-D   No.3   pp.288-298
Publication Date: 1994/03/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
computer systems,  algorithm,  parallel processing,  distributed memory,  data transfer,  

Full Text: PDF>>
Buy this Article

In a distributed-memory parallel-processing system, the overhead of data transfer among the processors is so large that it is important to reduce the data transfer. We consider the data transfer in evaluating an expression consisting of data distributed among the processors. We propose some algorithms which assign the operators in the expression to the processors so as to minimize the number or the cost of data transfers, on the condition that the data allocation to the processors is given. The basic algorithm is given at first, followed by some variations.