Lubachevsky–Stillinger algorithm: Difference between revisions

Revision as of 17:48, 29 March 2016

Revision as of 14:26, 12 April 2016

Line 40:

== History ==

The LSA was a by-product of an attempt to find a fair measure of [[speedup]] in [[Parallel algorithm|parallel]] [[simulations]]. The [[Time Warp (algorithm)|Time Warp]] parallel simulation algorithm by David Jefferson was advanced as a method to simulate asynchronous spatial interactions of fighting units in combat models on a [[parallel computer]].<ref>F. Wieland, and D. Jefferson, Case studies in serial and parallel simulations, Proc. 1989 Int'l Conf. Parallel Processing, Vol.III, F. Ris, and M. Kogge, Eds., pp. 255-258. </ref> Colliding particles models<ref>P. Hontales, B. Beckman, et al., Performance of the colliding pucks simulation of the Time Warp operating systems, Proc. 1989 SCS Multiconference, Simulation Series, SCS, Vol. 21, No. 2, pp. 3-7. </ref> offered similar simulation tasks with spatial interactions of particles but clear of the details that are non-essential for exposing the simulation techniques. The [[speedup]] was presented as the ratio of the execution time on a [[uniprocessor]] over that on a [[multiprocessor]], when executing the same parallel [[Time Warp]] algorithm. Boris D. Lubachevsky noticed that such a speedup assessment might be faulty because executing a [[parallel algorithm]] for a task on a uniprocessor is not necessarily the fastest way to perform the task on such a machine. The LSA was created in an attempt to produce a faster uniprocessor simulation and hence to have a more fair assessment of the [[parallel speedup]]. Later on, a parallel simulation algorithm,

different from the Time Warp, was also proposed, that, when run on a uniprocessor, reduces to the LSA.<ref>B.D. Lubachevsky, Simulating Billiards: Serially and in Parallel, Int.J. in Computer Simulation, Vol. 2 (1992), pp. 373-411.</ref>