Exploiting Lookahead in Parallel Simulation

Yi-Bing Lin, Edward D. Lazowska

Research output: Contribution to journalArticle

35 Scopus citations

Abstract

Parallel simulation is an important practical technique for improving the performance of simulations. The most effective approach to parallel simulation depends on the characteristics of the system being simulated. One key characteristic is called lookahead. In Chandy-Misra deadlock avoidance simulation, lookahead must exist in the simulated system in order to avoid deadlock. Fujimoto recognized that, independent of its effect on deadlock, lookahead has a significant effect on the performance (speedup) of a simulation. In Fujimoto's study, explicit lookahead is assumed, i.e., the lookahead is known before the simulation begins, and it does not change during the simulation. Another kind of lookahead, called implicit lookahead, was introduced by Nicol for simulating FCFS stochastic queueing systems; implicit lookahead can be exploited to yield performance benefits even when explicit lookahead does not exist. In this paper, we show the feasibility of implicit lookahead for non-FCFS systems. We propose several lookahead exploiting techniques for round-robin (RR) system simulations. We design an algorithm that generates lookahead in O(1) time. Both analytical models and experiments are constructed to evaluate these techniques. We also evaluate a lookahead technique for preemptive priority (PP) systems 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. Our analyses show that exploiting implicit lookahead can significantly improve the lookahead ratios of RR and PP system simulations.

Original languageEnglish
Pages (from-to)457-469
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Volume1
Issue number4
DOIs
StatePublished - 1 Jan 1990

Keywords

  • Conservative parallel simulation
  • deadlock avoidance
  • discrete event simulation
  • lookahead
  • preemptive priority systems
  • round-robin systems

Fingerprint Dive into the research topics of 'Exploiting Lookahead in Parallel Simulation'. Together they form a unique fingerprint.

  • Cite this