Синхронизация времени в распределенном имитационном моделировании

Использование lookahead (Забегания вперёд)

Для консервативных алгоритмов синхронизации характерной особенностью является использование предварительного просмотра (lookahead). Предположим, что некоторый логический процесс имеет локальное время с отметкой T. Процесс может гарантировать, что любое будущее сообщение, отосланное им, будет иметь временную метку, превосходящую временную метку пришедшего позднее сообщения, на величину, равную T+L. В этом случае говорят, что процесс имеет предварительный просмотр величиной, равной L. Предварительный просмотр используют для того, чтобы вычислить временную метку нулевого сообщения. Величина предварительного просмотра указывает на то, что на протяжении некоторого временного отрезка L исходящих сообщений не будет.
Обсуждаемый алгоритм допускает множество модификаций, таких как, например, подсчёт lookahead по отдельности для различных исходящих дуг, что приводит к значительному уменьшению простоя логических процессов. К отрицательным характеристикам этого алгоритма можно отнести тот факт, что если процессы сильно связаны, то все логические процессы будут продвигаться лишь на очень малые промежутки времени. Таким образом, моделирование по своей сути будет последовательным. Недостатком алгоритма является и то, что при небольших значениях lookahead возможна ситуация циклического ожидания нескольких LP с небольшими продвижениями локальных часов. В некоторых системах возможно, а зачастую и необходимо, использование нулевого предварительного просмотра (zero lookahead), однако обсуждаемый выше алгоритм не допускает нулевых предварительных просмотров.

6. 
   Использование дополнительной информации о временной метке следующего события
   

Рассмотрим подробнее недостатки алгоритмы с нулевыми сообщениями. Итак, одним из недостатков алгоритма является тот факт, что он может сгенерировать слишком большое количество нулевых сообщений. Допустим, что мы имеем два логических процесса LP. Предположим, что оба они заблокированы. Каждый из них достиг временной отметки, равной 100 (T_locLP1 = 100) и значение n. Пусть следующее запланированное событие имеет временную метку, равную 200. Алгоритм с нулевыми сообщениями будет действовать следующим образом: сообщения будут посланы процессами в моменты времени, равные 101, 102, 103 и т.д. Это будет продолжаться до тех пор, пока процессы не достигнут временной отметки, равной 200. После этого событие с временной меткой 200 (e_i, 200), будет выполнено. Т.е., мы видим, что было послано и обработано 100 нулевых сообщений до того момента, когда пришёл черёд ненулевого необработанного события. Из примера рис. 6 видно, что алгоритм с нулевыми сообщениями в этом случае неэффективен. Ситуация ещё более изменится к худшему, если мы будем работать с большим количеством процессов. Рассмотрим пример, который проиллюстрирован на рис. 6.
На рисунке видно, что взаимодействуют 3 логических процесса. Нулевые сообщения запланированы на 5.0, 5.5, 6.0 и т.д., они отсылаются через каждые 0.5 минут единиц модельного времени. Нулевых сообщений гораздо больше, нежели в предыдущем примере. Итак, если lookahead мало, то это приводит c к большому количеству нулевых сообщений.
Проблема заключается в том, что мы используем только текущее модельное время и значение предварительного просмотра (lookahead) для вычисления минимальной временной отметки будущих событий процесса. Ключом к усовершенствованию алгоритма является информация о значении временной метки следующего необработанного события. Если бы все логические процессы, участвующие в моделировании, владели этой информацией, они могли бы сразу перевести локальные часы на отметку 200 (T_locLP1 = 200). Таким образом, мы можем избавиться от описанного выше недостатка алгоритма с нулевыми сообщениями.