D. Finley, J.R. Ramos, V. Rego, and J. Sang (USA)
modeling and simulation methodologies,discrete-event simulation, round-robin scheduling
An efficient computation-based algorithm for effecting round-robin service in discrete-event simulation systems is presented. The new algorithm improves upon an older com putational algorithm which itself is an improvement over naive round-robinscheduling currently in use in thread-based simulation libraries and run-time systems. The naive ap proach can be prohibitively expensive due to thread con text switch overhead. The original computational algorithm avoids much of this context-switching but offers a run-time complexity of only On2, because the processing of each ar rival and departure event requires a traversal of the entire job pool. In this paper, we propose an improved algorithm which reduces run-time complexity to Onlogn. This is achieved through a novel use of relative keys to maintain the service order in an order-statistic tree, while making the need for a job pool update with each arrival or departure unnecessary. Empirical results are presented to compare performance with previously proposed algorithms and to show that this im proved algorithm is more efficient, especially when the job pool size is large.
Important Links:
Go Back
