DAGSim: A Simulator for DAG Scheduling Algorithms

Abstract : Scheduling the tasks of a distributed application has been an active field of research for several decades. The classic scheduling problem is to find a assignment of application tasks onto a set of distributed resources in a way that minimizes the overall application execution time. This problem can be formulated for different classes of applications and computing environments. It has been shown that most non-trivial instances of the scheduling problem are NP-complete. As a result, many research works propose different solutions including heuristic-based algorithms, guided random searches, and genetic algorithms. However, it is difficult to determine which solutions are practical for real scenarios. Indeed, most available results ignore many characteristic of large computing environments such as dynamically changing resource performance and availability, complex network topologies and network contention, data storage issues, or inaccuracy of resource performance estimates. In this paper, we present DAGSim, a simulator specifically designed to evaluate scheduling algorithms for application structured as Directed Acyclic dependency Graphs (DAGs). This simulator is built on top of Simgrid~\cite{simgrid}, a toolkit for the fast and accurate simulation of distributed applications with realistic assumptions concerning the computing environment. We describe the implementation of DAGSim and how it was used to implement two well-known scheduling algorithms (DCP~\cite{DCP} and DLS~\cite{DLS}). After giving preliminary results with these two algorithms, we give implementation recommendations for further improvement of Simgrid and DAGSim.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101833
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:07:32 AM
Last modification on : Sunday, May 19, 2019 - 1:20:45 AM

File

RR2000-46.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101833, version 1

Collections

Citation

Aubin Jarry, Henri Casanova, Francine Berman. DAGSim: A Simulator for DAG Scheduling Algorithms. [Research Report] LIP RR-2000-46, Laboratoire de l'informatique du parallélisme. 2000, 2+8p. ⟨hal-02101833⟩

Share

Metrics

Record views

7

Files downloads

16