Cluster-based static scheduling: theory and practice

• C. Boeres UFF
• V. E. F. Rebello UFF

Resumo

Task scheduling is a key element in achieving high performance from multicomputer systems. To be efficient, scheduling algorithms must be based on a cost model appropriate for computing systems in use. The optimal scheduling of tasks is NP-hard, and a large number of heuristic algorithms have been proposed for a variety of scheduling conditions (graph types, granularities or cost models). This paper studies the problem of task scheduling under the LogP model and presents both theoretical and experimental results for a cluster-based, task duplication methodology.

Palavras-chave: Processor scheduling, Delay, Optimal scheduling, Concurrent computing, Costs, Grid computing, Parallel machines, High performance computing, Scheduling algorithm, Parallel processing