Analysis of Optimistic Window-Based Synchronization

This paper studies an analytic model of parallel discrete-event simulation, comparing the costs and benefits of extending optimistic processing to the YAWNS synchronization protocol. The basic model makes standard assumptions about workload and routing; we develop methods for computing performance as a function of the degree of optimism allowed, overhead costs of state-saving, rollback, and barrier synchronization, and LP aggregation. This allows an approximation-based analysis of the range of situations under which optimism is a beneficial extension to YAWNS. We find that limited optimism is beneficial if the processor load is sparse, but that aggregating LPs onto processors improves YAWNS relative performance.