Perfect Sampling for Fork-Join networks. - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2005

Perfect Sampling for Fork-Join networks.

Résumé

In this paper, we show how to design a perfect simulation for Markovian fork-join networks, or equivalently, free-choice Petri nets. For pure fork-join networks and for event graphs, the simulation time can be greatly reduced by using extremal initial states, namely blocking states, although such nets do not exhibit any natural monotonicity property. Another approach for perfect simulation of pure fork-join networks is based on a (max,plus) representation of the system. For that, we show how the theory of (max,plus) stochastic systems can be used to provide perfect samplings. Finally, experimental runs show that the (max,plus) approach couples within fewer steps but needs a larger simulation time than the Markovian approach.
Dans cet article, nous montrons comment simuler de manière exacte les réseaux fork-join markoviens, ou réseaux de Petri à choix libres. Pour les réseaux fork-join purs, ou graphes d’ événements, le temps de simulation peut être très fortement réduit en utilisant des états initiaux extrémaux,bien que ces réseaux ne satisfassent aucune propriété naturelle de monotonicité. Une autre approche pour la simulation parfaite des réseaux fork-join purs est basée sur la représentation (max,plus) de ces systèmes.Pour cela, nous montrons comment la théorie (max,plus) des systèmes stochastiques peut être utilisée pour fournir une simulation parfaite. Enfin, des expérimentations montrent que l’approche (max,plus) couple en moins d’ étapes, mais nécessite un temps d’exécution plus long que l’approche markoviene.
Fichier principal
Vignette du fichier
RR2005-12.pdf (275.66 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101888 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101888 , version 1

Citer

Anne Bouillard, Bruno Gaujal. Perfect Sampling for Fork-Join networks.. [Research Report] LIP RR-2005-12, Laboratoire de l'informatique du parallélisme. 2005, 2+14p. ⟨hal-02101888⟩
47 Consultations
105 Téléchargements

Partager

Gmail Facebook X LinkedIn More