Scheduling complete trees on two uniform processors with integer speed ratios and communication delays

Jacek Blazewicz (1) , Frédéric Guinand (2) , Bernard Penz (3) , Denis Trystram (2, 4, 5, 6)

1 PUT - Poznan University of Technology
2 LMC - IMAG - Laboratoire de Modélisation et Calcul
3 G-SCOP_ROSP - Recherche Opérationnelle pour les Systèmes de Production
4 ID-IMAG - Informatique et Distribution
5 APACHE - Parallel algorithms and load sharing
6 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation

In this paper, we present an algorithm that builds optimal schedules for complete in-trees on two uniform processors, with arbitrary integer speed ratios, in the presence of communication delays.

Mots clés: Scheduling; communication delays; complete in-trees; uniform processors

Domaines: Recherche opérationnelle [math.OC]

Jacek Blazewicz, Frédéric Guinand, Bernard Penz, Denis Trystram. Scheduling complete trees on two uniform processors with integer speed ratios and communication delays. Parallel Processing Letters, 2000, 10 (4), pp.267-277. ⟨10.1142/S0129626400000263⟩. ⟨hal-00239338⟩