HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

FIFO scheduling of divisible loads with return messages under the one-port model

Olivier Beaumont 1 Loris Marchal Veronika Rehn Yves Robert
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : This paper deals with scheduling divisible load applications on star networks, in presence of return messages. This work is a follow-on of , where the same problem was considered under the 2-port model, where a given processor can simultaneously send and receive messages. Here, we concentrate on the one-port model, where a processor can either send or receive a message at a given time step. The problem of scheduling divisible load on star platforms turns out to be very difficult as soon as return messages are involved. Unfortunately, we have not been able to assess its complexity, but we provide an optimal solution in the special (but important) case of FIFO communication schemes. We also provide an explicit formula for the optimal number of load units that can be processed by a FIFO ordering on a bus network. Finally, we provide a set of MPI experiments to assess the accuracy and usefulness of our results in a real framework.
Document type :
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 7:51:58 PM
Last modification on : Wednesday, March 2, 2022 - 2:12:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 8:49:16 PM


  • HAL Id : inria-00070280, version 1



Olivier Beaumont, Loris Marchal, Veronika Rehn, Yves Robert. FIFO scheduling of divisible loads with return messages under the one-port model. RR-5738, INRIA. 2005, pp.25. ⟨inria-00070280⟩



Record views


Files downloads