The cost of terminating parallel discrete-event simulations

Simple item page
dc.contributor.authorSanjeevan, Vasanten
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2014-03-14T21:46:33Zen
dc.date.adate2009-09-29en
dc.date.available2014-03-14T21:46:33Zen
dc.date.issued1992en
dc.date.rdate2009-09-29en
dc.date.sdate2009-09-29en
dc.description.abstractSimulation models use many different rules to decide when to terminate. Parallel simulations generally use a single, simple rule: each process comprising the simulation terminates after a predefined period of time. A number of parallel simulation protocols have been proposed that enforce constraints on the order in which processes are scheduled in parallel so that the result of a parallel simulation is the same as that of the corresponding sequential simulation. Parallel simulations protocols can be broadly classified into two categories: conservative and optimistic. Conservative protocols can be subclassified into synchronous and asynchronous protocols. In this thesis, our objective is to compare the predicted and measured wall clock running times of parallel simulations for conservative-synchronous and optimistic protocols with and without termination conditions. We propose eight algorithms for mechanically adding an arbitrary termination condition to a conservative-synchronous non-terminating parallel simulation. Informal arguments about the expected performance of each algorithm are made, and the arguments are confirmed through measurement of the simulation of a torus network with three termination conditions using the conservative-synchronous Bounded Lag protocol on a shared memory multiprocessor. We also propose four algorithms for mechanically adding a termination condition to an optimistic non-terminating parallel simulation. We make informal arguments about the expected performance of these algorithms and report on the actual performance of the simulation of the torus network benchmark with two of these algorithms and the same three termination conditions using the optimistic Time Warp protocol on a message-passing multiprocessor. In addition to the torus network benchmark for the optimistic protocol, we also report on the performance of a colliding pucks simulation with these two algorithms and three additional termination conditions. Our study indicates that termination conditions which require exhaustive evaluation introduce substantial running time overhead. We propose and evaluate a scheme to reduce this overhead.en
dc.description.degreeMaster of Scienceen
dc.format.extentviii, 66 leavesen
dc.format.mediumBTDen
dc.format.mimetypeapplication/pdfen
dc.identifier.otheretd-09292009-020138en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-09292009-020138/en
dc.identifier.urihttp://hdl.handle.net/10919/44921en
dc.language.isoenen
dc.publisherVirginia Techen
dc.relation.haspartLD5655.V855_1992.S322.pdfen
dc.relation.isformatofOCLC# 26487403en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.lccLD5655.V855 1992.S322en
dc.subject.lcshComputer science -- Mathematicsen
dc.subject.lcshComputer simulationen
dc.subject.lcshParallel processing (Electronic computers)en
dc.titleThe cost of terminating parallel discrete-event simulationsen
dc.typeThesisen
dc.type.dcmitypeTexten
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LD5655.V855_1992.S322.pdf
Size:
3.35 MB
Format:
Adobe Portable Document Format
Description:
Download

Collections

Masters Theses