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 :
Reports
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070280
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 7:51:58 PM
Last modification on : Tuesday, December 11, 2018 - 10:58:13 AM
Long-term archiving on : Sunday, April 4, 2010 - 8:49:16 PM

Identifiers

  • HAL Id : inria-00070280, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

515

Files downloads

509