Exploiting lookahead in parallel simulation

Lookahead is the ability of a process to predict its future behavior. The feasibility of implicit lookahead for non-FCFS stochastic queuing systems is demonstrated. Several lookahead exploiting techniques are proposed for round-robin (RR) system simulations. An algorithm that generates lookahead in O(1) time is described. Analytical models and experiments are constructed to evaluate these techniques. A lookahead technique for preemptive priority (PP) systems is evaluated using an analytical model. The performance metric for these techniques is the lookahead ratio, which is correlated with other performance measures of more direct interest, such as speedup. The analyses show that using implicit lookahead can significantly improve the lookahead ratios of RR and PP system simulations.>