Tomasz Kalinowski, Iskander Kort, Denis Trystram

List scheduling of general task graphs under LogP model

865

Abstract

List scheduling is the most frequently used scheduling technique.. Worst case analysis of this approach as well as experimental studies were performed for various computational models.

However, many new models have been proposed during the last decade with the aim to provide a realistic but still simple and general model of parallel computation. LogP is one of the most popular models so far suggested. It takes into account the time a computation processor spends to manage a communication. Many experimental studies on current parallel architectures have shown that such a parameter cannot be neglected.

The aim of this report is to assess the applicability of the list scheduling approach to the LogP model. More precisely, we present two adaptations of the Earliest Task First (ETF) heuristic. Then, we establish an upper bound on list schedules under LogP model. Finally, we present an extensive experimental study for different graph classes and model instances.

Key words: scheduling, computational models.