Some results on scheduling flat trees in LogP Model

摘要

This paper deals with the problem of scheduling a flat tree in the LogP model. A flat tree refers here, to either a Fork or to a Join graph. LogP is a computational model which allows to describe a wide range of parallel machines in a realistic but simple way. We first report some experiments on an IBM-SP machine to assess this model. Then The problem of scheduling a Fork graph with an unbounded number of processors is Studied. This study is extended to the case of Join graphs by showing the equivalence Of the corresponding scheduling problems. The purpose of this paper is to show that some scheduling problems remain tractable Even in fine computational models like LogP.