TY - JOUR

T1 - Conservative parallel simulation for systems with no lookahead prediction

AU - Lin, Yi-Bing

AU - Lazowska, Edward D.

AU - Baer, Jean Loup

PY - 1990/1

Y1 - 1990/1

N2 - The most popular conservative parallel simulation approach is the Chandy-Misra approach, referred to here as the Chandy-Misra basic scheme (CMB). When a CMB simulation includes a feedback loop (i.e., when a message may 'circulate' in a loop of processes), there is the probability that deadlocks will occur. To deal with deadlocks in Chandy-Misra simulations, two modified algorithms, the Chandy-Misra deadlock avoidance (DA) and deadlock recovery (DR) algorithms, have been proposed. The DA algorithm is widely used for simulating systems with lookahead prediction. The DR algorithm has been recognized, up to this point, as the only conservative approach for simulating systems with no lookahead prediction. This paper shows that a better approach for simulating systems with no lookahead prediction is to reconfigure the system such that there is no feedback loop, and use the CMB algorithm to perform the simulation. We identify the overheads of this approach, and devise both an analytical model and a number of simulation experiments to estimate its performance.

AB - The most popular conservative parallel simulation approach is the Chandy-Misra approach, referred to here as the Chandy-Misra basic scheme (CMB). When a CMB simulation includes a feedback loop (i.e., when a message may 'circulate' in a loop of processes), there is the probability that deadlocks will occur. To deal with deadlocks in Chandy-Misra simulations, two modified algorithms, the Chandy-Misra deadlock avoidance (DA) and deadlock recovery (DR) algorithms, have been proposed. The DA algorithm is widely used for simulating systems with lookahead prediction. The DR algorithm has been recognized, up to this point, as the only conservative approach for simulating systems with no lookahead prediction. This paper shows that a better approach for simulating systems with no lookahead prediction is to reconfigure the system such that there is no feedback loop, and use the CMB algorithm to perform the simulation. We identify the overheads of this approach, and devise both an analytical model and a number of simulation experiments to estimate its performance.

UR - http://www.scopus.com/inward/record.url?scp=0025231166&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0025231166

SN - 0735-9276

VL - 22

SP - 144

EP - 149

JO - Simulation Series

JF - Simulation Series

IS - 1

T2 - Proceedings of the SCS Multiconference on Distributed Simulation

Y2 - 17 January 1990 through 19 January 1990

ER -