About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
3rd International ICST Conference on Simulation Tools and Techniques

Research Article

Random graph generation for scheduling simulations

Download1389 downloads
Cite
BibTeX Plain Text
  • @INPROCEEDINGS{10.4108/ICST.SIMUTOOLS2010.8667,
        author={Daniel  Cordeiro and Gr\^{e}gory  Mouni\^{e} and Swann  Perarnau and Denis  Trystram and Jean-Marc  Vincent and Fr\^{e}d\^{e}ric  Wagner},
        title={Random graph generation for scheduling simulations},
        proceedings={3rd International ICST Conference on Simulation Tools and Techniques},
        publisher={ICST},
        proceedings_a={SIMUTOOLS},
        year={2010},
        month={5},
        keywords={Scheduling simulation algorithm validation random graphs generation},
        doi={10.4108/ICST.SIMUTOOLS2010.8667}
    }
    
  • Daniel Cordeiro
    Grégory Mounié
    Swann Perarnau
    Denis Trystram
    Jean-Marc Vincent
    Frédéric Wagner
    Year: 2010
    Random graph generation for scheduling simulations
    SIMUTOOLS
    ICST
    DOI: 10.4108/ICST.SIMUTOOLS2010.8667
Daniel Cordeiro1,*, Grégory Mounié1,*, Swann Perarnau1,*, Denis Trystram1,*, Jean-Marc Vincent1,*, Frédéric Wagner1,*
  • 1: LIG, Grenoble University, 51, avenue Jean Kuntzmann, 38330 Montbonnot Saint Martin, France.
*Contact email: cordeiro@imag.fr, mounie@imag.fr, perarnau@imag.fr, trystram@imag.fr, vincent@imag.fr, wagner@imag.fr

Abstract

In parallel and distributed systems, validation of scheduling heuristics is usually done by simulation on randomly generated synthetic workloads, typically represented by task graphs. Since there is no single generation method that models all possible workloads for scheduling problems, researchers often re-implement the classical generation algorithms or even implement ad hoc ones. A bad choice of generation method can mislead the validation of the algorithm due to biases it can induce. Moreover, different implementations of the same randomized generation method may produce slightly different graphs. These problems can harm the experimental comparison of scheduling algorithms. In order to provide a comparison basis we propose GGen -- a unified and standard implementation of classical task graph generation methods used in the scheduling domain. We also provide an in-depth analysis of each generation method, emphasizing important graph properties that may influence scheduling algorithms.

Keywords
Scheduling simulation algorithm validation random graphs generation
Published
2010-05-16
Publisher
ICST
http://dx.doi.org/10.4108/ICST.SIMUTOOLS2010.8667
Copyright © 2010–2025 ICST
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL