Uzamsal Koşut ve Dağıtılmış Benzetimler için İyimser Bir Zaman Yönetim Mekanizması

Abstract

Parallel and distributed simulation enables to run simulations that have heavy computational loads within acceptable time periods. One of the most important problems during the execution of parallel and distributed simulation is the synchronization of parallel processes. To make an unreliable synchronization causes simulation results to be unexpected, wrong or inconsistent. Synchronization methods that are used in parallel and distributed simulations are classified into two main groups. The first one is called conservative time management approach and continuously tries to make parallel processes consistent. Therefore, parallel processes should be synchronized after state transitions. Objective of the other approach, namely optimistic time management, is getting rid of latencies originating from too many synchronizations. Therefore, optimistic time management allows to loosen synchronization mechanism. In an optimistic time management approach, parallel processes can advance to a time ahead of other parallel processes by advancing their local time without caring about synchronization. It is possible that some issues originating from loosened synchronization can show up in a further simulation time. A parallel process which has a greater simulation time than others may receive a message with a past timestamp from them and some inconsistencies may appear in the simulation. In this case, the relevant parallel processes have to recover the simulation state by performing a rollback operation that goes back in the simulation and figures out the issues.

Both time management approaches have their own pros and cons. However, in the last three decades, a lot of studies in the literature that show optimistic time management can be more scalable and preferable appeared. One of the things that can improve the performance of optimistic approaches is reducing the number of rollbacks without breaching integrity of the model. In this thesis, a generic mechanism that improves performance of optimistic time management approaches by reducing number of rollbacks has been proposed for spatially-parallel agent-based simulations. A framework that uses this mechanism has been developed. In the existing methods, a lot of rollback operations may be performed even if they are not necessary. The objective of the proposed method is detecting these unnecessary rollbacks and avoiding to perform them. For this purpose, much before an inconsistency is observed, the proposed method determines if a rollback operation should be performed or not for the past time-stamped messages that will be received in the future. Because of this feature, the proposed method is called Predetermined Rollbacks. The experiments showed that Predetermined Rollbacks achieved significant speedup against conventional optimistic time management mechanisms. In addition to the main contribution, an agent-based modeling and simulation software has been extended with optimistic time management; a well-known control algorithm that is widely used in computer networks has been employed as a dynamic checkpointing scheduler. It has been shown that the number of rollbacks can be reduced by a method that improves the state saving mechanisms.