Uzamsal koşut ve dağıtılmış benzetimler için iyimser bir zaman yönetim mekanizması
An optimistic time management mechanism for spatially parallel and distributed simulations
Yazar: BİLGE KAAN GÖRÜR
Danışman: DOÇ. DR. KAYHAN MUSTAFA İMRE ; PROF. DR. MEHMET HALİT SEYFULLAH OĞUZTÜZÜN
Hacettepe Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2019
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Ayrık olay benzetimi = Discrate event simulation ; Dağıtık benzetim = Distributed simulation ; Eş zamanlama =

Özet:
Koşut ve dağıtılmış işlem teknolojileri, ağır işlem gücü gerektiren benzetimlerin kabul edilebilir sürelerde koşturulmasını sağlar. Benzetimlerin koşut veya dağıtılmış olarak çalıştırılmasındaki en önemli sorunlardan bir tanesi de koşut çalışan işlemler arasında yapılması gereken zaman uyumlamadır. Zaman uyumlamanın sağlıklı bir şekilde yapılmaması benzetim sonuçlarının beklenenden farklı, yanlış veya tutarsız olmasına neden olur. Koşut ve dağıtılmış benzetim sistemlerinde zaman uyumlama yöntemleri iki başlık altında ele alınmaktadır. Bunlardan ilki sakıngan zaman yönetim yaklaşımı olup, bu yaklaşımda koşut işlemlerin sürekli olarak tutarlı bir şekilde ilerlemesi sağlanır. Bunu yapabilmek için de koşut çalışan işlemler durum değişikliklerinden sonra bir zaman uyumlama sürecine girmek durumundadırlar. Bir diğer yaklaşım olan iyimser zaman yönetim yaklaşımı ise sakıngan zaman yönetim yaklaşımındaki zaman uyumlamadan kaynaklı gecikmeleri ortadan kaldırmayı amaçlar. Bunun için de zaman uyumlama mekanizmalarının gevşetilmesini önerir. İyimser zaman yönetim yaklaşımında koşut işlemler, zaman uyumlamayı beklemeden yerel benzetim zamanlarını ilerleterek diğer koşut işlemlerin daha ilerisinde bir zamana gidebilirler. Bu durumda, ilerleyen bir zamanda zaman uyumlamanın gevşekliğinden kaynaklı sorunların ortaya çıkması mümkündür. Diğer koşut işlemlerin ilerisinde bir yerel zamana sahip bir koşut işlem, geçmiş zamanda işlemesi gereken bir iletiyi alabilir ve benzetimde tutarsızlıklar ortaya çıkar. Böyle bir durumda ilgili koşut işlem(ler)in geri sarma sürecine (benzetimin geçmiş bir zamanına geri dönerek ilgili sorunları çözmesi) girmesi söz konusudur.

Her iki zaman yönetim yaklaşımının birbirine göre artıları ve eksileri olduğu bilinse de, özellikle son 30 yılda iyimser yaklaşımların daha ölçeklenebilir ve tercih edilebilir olduğunu gösteren bir çok çalışmaya rastlanmaktadır. İyimser yaklaşımların başarımını daha da artırmanın bir yolu, maliyeti çok yüksek olabilen geri sarma süreçlerinin sayısını işlem bütünlüğünü bozmadan azaltabilmektir. Bu tez kapsamında geri sarma işlemlerini azaltarak iyimser yaklaşımların başarımını daha da artırmak için uzamsal-koşut benzetimlere yönelik genel amaçlı bir mekanizma önerilmiş ve bu mekanizmayı kullanan bir uygulama çatısı geliştirilmiştir. Mevcut yöntemlerde geri sarma işlemlerinin tamamen gereksiz olduğu bazı durumlarda bile gerçekleştirilmesi mümkün olabilmektedir. Önerilen mekanizmanın asıl amacı bu gereksiz geri sarma işlemlerinin tespit edilmesi ve bunlardan kaçınılabilmesinin sağlanmasıdır. Benzetimde henüz bir tutarsızlık ortaya çıkmadan önce, ileri tarihte ortaya çıkabilecek geri sarmaların hangi durumlarda gerçekten gerekli olduğu, hangi durumlarda ise kaçınılabilir olduğu önerilen yöntem sayesinde belirlenir. Bu özelliğinden dolayı önerilen yönteme Öngörülmüş Geri Sarma mekanizması adı verilmiştir. Yapılan deneyler Öngörülmüş Geri Sarma mekanizmasının bilinen iyimser yaklaşımlara göre kayda değer hızlanmalar sağladığını göstermiştir. Ayrıca bu ana katkısının yanı sıra tez çalışmaları kapsamında; bir etmen tabanlı modelleme ve benzetim yazılımı iyimser zaman yönetimi yaklaşımıyla genişletilmiş, denetim noktası alma zamanlarını belirleyen dinamik yaklaşımlar için yeni bir yöntem uygulanmış ve geri sarma sayısının durum kaydetme mekanizmalarını iyileştiren bir yöntemle azaltılabileceği de gösterilmiştir.

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.