'A Simulation Study of Load-Imbalance Problem in Distributed Graph Exploration Algorithms'
Author
Niaz, Adnan
Term
10. Term
Education
Publication year
2006
Abstract
Projektet undersøger, hvorfor distribueret model checking, som kører på flere computere, kan få belastningsubalance, hvor nogle noder laver langt mere arbejde end andre. Model checking udforsker automatisk et systems tilstandsrummet (alle mulige tilstande og overgange), typisk repræsenteret som en graf. Fordi grafgennemløb er centralt, byggede vi modeller af graf-udforskende strategier med Möbius-rammeværket. Vi brugte derefter data udtrukket fra en UPPAAL-model til at køre simulationer. Vi sammenlignede modellerne på ydeevne, tomgangstid og belastningsubalance. Resultaterne viser lav tomgangstid, når tilstandsrummet er perfekt balanceret mellem arbejdere. Vi drøfter årsagerne til denne adfærd og skitserer fremtidigt arbejde.
This project examines why distributed model checking algorithms, which run across multiple computers, can suffer from load imbalance, where some nodes do much more work than others. Model checking automatically explores a system’s state space (all possible states and transitions), typically represented as a graph. Because graph exploration is central, we built models of graph-exploring strategies using the Möbius framework. We then used data extracted from an UPPAAL model to run simulations. We compared the models on performance, idle time, and load imbalance. Our results show low idle time when the state space is perfectly balanced across workers. We discuss reasons behind this behavior and outline future work.
[This abstract was generated with the help of AI]
Documents