ДонНТУ   Портал магистров

Реферат по теме магистерской работы


«Оптимизация оптимистического протокола – обзор»

Содержание

Введение

Распределенное дискретно-событийное моделирование осуществляется набором логических процессов (ЛП), которые взаимодействуют друг с другом путем отправки сообщений с временными метками, представляющих моделируемые события. Каждый ЛП имеет свои локальные часы, называемые локальным виртуальным временем (ЛВВ), которое показывает продвижение процесса моделирования. Время увеличивается после обработки события на логическом процессоре. Существует два широко известных подхода к процессу моделирования – консервативный и оптимистический. Консервативный протокол дает гарантию, что обработка события не приведет к появлению причинно-следственной ошибки из-за внеочередной обработки. Оптимистический протокол выполняет события жадно без соблюдения ограничений безопасности.

Оптимистичные методы синхронизации допускают появление нарушений очередности выполнения событий, но они обнаруживают и исправляют их. Оптимистичные подходы предлагают два важных преимущества по сравнению с консервативными методами. Во-первых, они могут использовать большую степень параллелизма. Во-вторых, консервативный механизм обычно полагается на применение конкретной информации (например, расстояния между объектами) для того, чтобы определить, какие события являются безопасными для обработки, оптимистические алгоритмы работают без такой информации. С другой стороны, оптимистичные методы могут потребовать больше накладных расходов для вычислений, чем консервативные подходы, что приводит к определенной деградации производительности.

Механизм Time Warp является наиболее известным оптимистичным алгоритмом. Принцип его работы заключается в выполнении событий без гарантии соблюдения последовательного порядка. Если возникает ситуация нарушения естественного порядка временных меток событий, протокол производит откат к необходимому состоянию, используя механизм анти-сообщений. Анти-сообщение – это дубликат ранее отправленного сообщения. Основными недостатками алгоритма Time Warp являются чрезмерное потребление памяти, возможность возникновения каскадных откатов, низкая скорость моделирования в случае частых откатов. Далее описаны существующие алгоритмы оптимизации Time Warp, которые пытаются устранить эти недостатки.

1 Уменьшение расходов на откат

Технология агрессивной отмены старается отменить неправильные вычисления как можно раньше, до того, как любой из процессов начнет использовать некорректные выходные данные. Чтобы реализовать это, все анти-сообщения генерируются во время отката, до того, как произойдет повторное выполнение событий [2]. Технология ленивой отмены напротив не спешит с откатом событий, ожидая подтверждения, что выход неправильный, чтобы не вызывать каскадный откат других физических процессов. Этот метод достаточно эффективен, он может вызвать больший откат зависимых процессов, позволяя им выполнять ошибочные вычисления [1,2]. Ленивые перевычисления в некотором роде схожи с ленивым откатом, но используют задержку отбрасывания вектора состояний вместо задержки отправки анти-сообщений. Адаптивная отмена предназначена для решения проблемы с необходимостью определения стратегии отмены на этапе запуска. Она позволяет процессу самому определять, какую стратегию отмены использовать, основываясь на показателях времени выполнения [1,2]. Fujimoto предложил механизм прямой отмены, который использует разделяемую память для оптимизации отката некорректных вычислений. Если во время выполнения события E1 приходит новое сообщение Е2, механизм ассоциирует указатель на Е2 с событием Е1. Во время отката события Е1, указатель может быть использован для отмены Е2, с применением ленивой или агрессивной отмены [2,3].

Другие подходы были предложены для более раннего ограничения длины последовательных откатов. Prakash и Subramanian [2] присоединяют к сообщениям информацию о состоянии для предотвращения каскадных откатов, что позволяет отфильтровать устаревшие сообщения. Madisetti [2] предложил механизм, который замораживает пространственное распространение некорректных вычислений, основанный на так называемой сфере влияния. Недостаток этого подхода в том, что набор моделирующих процессов, которые могут быть подвергнуты влиянию некорректных вычислений, значительно больше фактического набора, что приводит к отправке ненужных управляющих сообщений [2].

2 Уменьшение потребления памяти

Механизм обрезания [5] предложили использовать для высвобождения используемой памяти. Он основан на восстановлении необходимой памяти из информации о сохраненных состояниях. Если возникает откат к отсутствующему состоянию, то производится откат к первому состоянию до отсутствующего, а затем перевыполнение событий. Ни физические процессы, ни состояние ГВВ не должны быть удалены [4]. Carothers [4,6] применил подход исправления физических процессов как потенциально обратимых. Откат достигается применением обратных операций с использованием текущего состояния и сохраненных входных событий.

2.1 Методы, оптимизирующие сохранение состояний

Периодическое сохранение состояний (Periodic State Saving – PSS) уменьшает накладные расходы путем увеличения интервала сохранения состояний. PSS сохраняет внутреннее состояние после каждых χ обновлений состояния. Если возникает откат и необходимое состояние отсутствует, производится откат к более раннему сохраненному состоянию [7]. Интервал сохранения – это ключевой параметр, который определяет эффективность метода PSS: он регулирует соотношение между общей стоимостью сохранения состояний и количеством перевычислений в повторной обработке сообщений. Fleishmann и Wilsey [7] выполнили эмпирическое исследование четырех адаптивных методов PSS. Они представили эвристику, которая пересчитывает затраты на сохранение состояний и повторную обработку сообщений после каждых N событий. Если время выполнения значительно возросло, интервал сохранения уменьшается на единицу, иначе – увеличивается на единицу. Sköld и Rönngren утверждали, что оптимальный интервал сохранения зависит от времени выполнения или детализации событий для различных типов событий. Их событийно чувствительный метод сохранения состояний зависит от того, какого типа событие было обработано предыдущим, и решает, сохранять ли вектор событий исходя из этой информации.

Francesco Quaglia был предложен алгоритм разреженного сохранения состояний на основе истории событий [8]. Суть алгоритма в том, что каждый ЛП пытается спрогнозировать интервалы виртуального времени, в которые возникнет откат. Данный подход также основан на мониторинге функции стоимости контрольных точек и отката, пересчет которой используется для динамического перерасчета параметра, определяющего процент сохраненных состояний. Механизм инкрементного сохранения состояний (Incremental State Saving – ISS) обычно использует частичное обновление состояния. Инкрементная запись истории состояний ЛП создается путем сохранения старого значения переменной до ее перезаписи и нового значения, которые используется при откате – восстанавливается каждое сохраненное значение переменной в порядке, обратном сохранению. Для улучшения работы методов PSS и ISS были предложены гибридные методы, которые чередуют эти два механизма. Francesco Quaglia [9] предлагает гибридный подход, основанный на комбинировании PSS и ISS. Этот подход предлагает периодически сохранять состояние процесса, и сохранять части обратных преобразований в период между контрольными точками. Настраиваемыми параметрами являются размер интервала и количество частично сохраненных состояний за интервал между двумя контрольными точками.

3 Методы, контролирующие оптимизм

3.1 Неадаптивные протоколы

Первый метод контроля чрезмерного оптимизма использует временные окна. Этот подход ограничивает оптимизм, выполняя события только в пределах окна модельного времени. Первым протоколом, использующим эту технику, является Moving Time Window (MTW). Ключевая проблема – определение наиболее подходящего размера временного окна. Похожая идея была изучена Turner and Xu [10] в протоколе Bounded Time Warp (BTW), где никакие события не обрабатываются до тех пор, пока все процессы не достигли того момента во времени, когда устанавливается новая граница.

Алгоритм Breathing Time Bucket использует оптимистичную обработку с локальными откатами. Этот метод не требует анти-сообщений и, по сути, является безрисковым. Breathing Time Warp [11] является расширением Breathing Time Bucket, которое позволяет ему добавлять некоторый риск. Идея состоит в обработке первых N1 событий вне ГВВ, так же, как в базовом алгоритме Time Warp. Затем протокол переключается обратно в режим Breathing Time Bucket для обработки следующих N2 событий. Если все процессы достигли своего предела обработки событий, то начинается новый расчет ГВВ и запускается новый цикл.

3.2 Адаптивные протоколы, основанные на локальных состояниях

Управляющий механизм Adaptive Time Warp [12] использует метод штрафов для ограничения механизма путем блокировки ЛП на некоторый интервал реального времени (блокирующее окно). Блокирующее окно устанавливается для минимизации суммы общего процессорного времени, потраченного в блокированном состоянии и в состоянии восстановления. Логический процесс может принять решение временно приостановить обработку события, если он только что испытал аномально высокое количество откатов.

Hamnes и Tripathi [13] предложили локальный адаптивный протокол, который предназначен для максимизации продвижения модельного времени (со скоростью продвижения модельного времени α). Этот алгоритм собирает статистику на каждом канале каждого ЛП и использует ее для максимизации α. Вероятностный прямой адаптивный протокол контроля оптимизма [14] похож на рассмотренный выше, однако добавляет вероятностную компоненту в том смысле, что блокировка инициируется с определенной вероятностью.

Параметризованный Time Warp [15] сочетает в себе три адаптационных механизма (периодическое сохранение состояний, ограниченное временное окно, а также приоритет планирования), чтобы минимизировать накладные расходы и увеличить производительность параллельного моделирования. Полезная работа является функцией от нескольких параметров (отношение числа совершенных к общему количеству выполненных событий, число откатов, количество анти-сообщений, длина откатов и т.д.). Период сохранения состояний и границы временного окна увеличиваются при больших значениях параметра полезной работы.

3.3 Адаптивные протоколы, основанные на глобальном состоянии

Протокол Adaptive Memory Managment пытается минимизировать общее время исполнения, а не концентрироваться на одном конкретном критерии. Утверждается, что такой подход не позволяет оптимизировать один из параметров вычислений за счет непропорционального увеличения другого.

Протоколы Near Perfect State Information (NPSI) [16] являются классом адаптивных протоколов, основанных на доступности почти идеальной информации о глобальном состоянии параллельного моделирования. NPSI протоколы используют количественный потенциал ошибки (EPi), связанный с каждым ЛПi, для контроля оптимизма ЛПi. Протокол поддерживает каждый EPi в обновленном состоянии в соответствии с продвижением моделирования. Второй компонент протокола переводит EPi в контроль над агрессивностью и риском ЛПi. Одним из NPSI протоколов является Elastic Time Algorithm (ETA). В ЕТА более дальний ЛПi уходит тем дальше от своего предшественника, чем медленнее его ход из-за сдерживающих притяжение эластичных связей, связывающих его со своим предшественником – отсюда эластичность времени. Напряженность в эластичных связях соответствует потенциалу ошибки ЛПi.

Протокол, основанный на механизме движущегося окна в компьютерных сетях, где получатель и отправитель регулируют с помощью специальных сообщений размер окна, был предложен Kiran и Fujimoto [17]. Оценивается число запланированных необработанных сообщения для каждого процессора, эти оценки используются для определения движущегося окна, которое определяет верхнюю границу числа необработанных сообщений, которое ЛП может запланировать в одно время. Продвижение ГВВ делает сообщения подтвержденным, таким образом позволяя отправить больше сообщений. Применяются три этапа оценки размера окна. Первый – это мгновенный размер окна, требуемый для соответствующего последовательного выполнения. Второй – окно, требуемое до вычисления следующего ГВВ. Третья часть – окно для оптимистических расчетов.

3.4 Адаптивные протоколы, основанные на вероятностных вычислениях

Система MIMDIX использует идеи вероятностной повторной синхронизации для устранения чрезмерно оптимистичного поведения. Специальный процесс вероятностно посылает синхронизационное сообщение всем ЛП, заставляя их синхронизировать метку сообщения. Поддерживая метку синхронизации сообщения близкой к ГВВ, логические процессы можно держать близко друг к другу по времени, тем самым уменьшая риск каскадных откатов.

Damani, Wang и Garg [18] предложили параметрический алгоритм восстановления состояний, где K – это некоторый параметр, который определяет степень оптимизма, используемую для настройки оптимального соотношения между накладными расходами и эффективностью восстановления. K – это целое число в интервале от 0 до N, где N – общее число процессов. Оно определяется как максимальное число процессов, чей отказ может аннулировать некоторое сообщение m.

3.5 Другие адаптивные протоколы

Damani и соавторы в [19] предложили оптимистический алгоритм для быстрой остановки ошибочных вычислений. Этот алгоритм является модификацией Distributed recovery with K-optimistic logging [18]. Схема не требует очереди исходящих сообщений и анти-сообщений. Это приводит к уменьшению накладных расходов памяти и простым алгоритмам управления памятью. Схема также устраняет проблему каскадных откатов, что приводит к ускорению моделирования. Используется агрессивная отмена.

Концепция алгоритма – создание и поддержание транзитивной информационной зависимости между процессами. Поддерживается таблица номеров инкарнации – число откатов, произведенных процессом. В таблице также хранится временная метка сообщения, вызвавшего откат. Если процесс обнаруживает, что он получил запоздавшее сообщение, он рассылает сообщения, содержащие текущий инкарнационный номер k и временную метку сообщения t, а затем блокирует свою работу. Разосланные сообщения показывают, что все состояния инкарнации k с виртуальным временем большим t, являются некорректными. Состояния, зависящие от них, тоже являются некорректными.

Smith, Johnson, и Tygar [20] предложили полностью асинхронный оптимистичный протокол восстановления с минимальными откатами, основанный на методе Optimistic Message Logging. Протокол не требует отправки никаких сообщений и уменьшает максимальное количество откатов для каждого процесса до одного. Существуют два типа сообщений каждый со своим интервалом сохранения – пользовательские (сообщения моделирования) и системные. Журналируются только пользовательские сообщения. Также используется вектор состояний для быстрой загрузки требуемого состояния.

4 Эволюционные подходы

Эволюционные подходы являются относительно новыми среди техник оптимизации алгоритма Time Warp. Алгоритмы основаны на теории эволюции, находят оптимальное решение методом проб и ошибок. Эволюционные алгоритмы начинаются с выбора произвольного решения из пространства решений. Оценивается пригодность каждого кандидата в популяции и отбирается кандидаты для размножения. Затем выбираются пары кандидатов, и осуществляется рекомбинационная операция – создание потомства. После оценки детей процесс отбора повторяется и создается следующее поколение.

Алгоритм GMA (Genetic Modifying Algorithm) [21] решает задачу адаптивной настройки параметров, определяющих режим работы записи и восстановления. Указанные параметры соответствуют текущему режиму журналирования (инкрементный или неинкрементный) и текущему интервалу журналирования. Режимы журналирования и интервалы связаны с набором объектов моделирования – генотипом. Потомство оценивается с помощью функции выживаемости, основанной на количестве совершенных событий. Когда наблюдается повышение производительности, мутации применяются к тем частям генотипа, которые не были затронуты шагом эволюции. Когда обнаруживается ухудшение, восстанавливается снимок генотипа до последней мутации, и возобновляются мутации на нем. Генотип стартует со случайной конфигурации.

Другой генетический алгоритм предложили Wang и Tropper [22] для ограничения оптимизма. Алгоритм итерационным способом определяет оптимальный размер окна, в пределах которого могут выполняться события на процессорах. Каждый процессор имеет свой размер окна. Оценка окон производится исходя из продвижения моделирования. Окна оцениваются в десяти последовательных интервалах ГВВ и коэффициент выживания – среднее из десяти оценок. Родители выбираются либо методом генерации случайных чисел в диапазоне [0,1], либо методом стохастической универсальной выборки, где генерируется одно случайное число в диапазоне [0, 1/с], где с – общее число кандидатов.

5 Алгоритмы вычисления глобального виртуального времени

Глобальное виртуальное время (ГВВ) используется в Time Warp для определения прогресса в моделировании. Значение ГВВ не уменьшается с течением реального времени. Две важные проблемы, решаемые ГВВ, – освобождение памяти и подтверждение неотменяемых операций.

5.1 Централизованное вычисление глобального виртуального времени

В централизованных алгоритмах ГВВ рассчитывается центральным ГВВ-менеджером, который рассылает запросы всем ЛП об их текущем ЛВВ и вычисляет минимальное значение. В этом подходе существуют две проблемы. Во-первых, сообщения в пути, которые потенциально могут вызвать откат учтенного ЛВВ, не берутся в расчет (проблема нестационарности сообщений). Во-вторых, значения ЛВВ были получены от ЛП в разное реальное время, что называется проблемой одновременной отчетности.

Один из первых ГВВ-алгоритмов (Minimum Simulation Time (GVT) Algorithm) был предложен Samadi [23]. ГВВ-менеджер посылает исходящее начальное сообщение ГВВ. После того, как все ЛП прислали ответ на запрос, ГВВ-менеджер вычисляет и рассылает новое значение ГВВ. Проблема нестационарности сообщений решается подтверждением каждого сообщения и отчета ГВВ-менеджеру о минимуме среди всех меток неподтвержденных сообщений и ЛВВ логического процесса. Lin и Lazowska [24] представили некоторые улучшения этого алгоритма. В их алгоритме нет подтверждений для сообщений, но заголовки сообщений содержат порядковый номер. Получающий ЛП может идентифицировать потерянное сообщение как пробел из полученного порядкового номера. Проблема одновременной отчетности решается установкой границ на реальное время отчетности на каждом ЛП такой, что набор интервалов имеет общее реальное время. Каждый ЛП может передавать информацию на ГВВ-менеджер, как только покидает интервал.

Для уменьшения коммуникационной сложности вычисления ГВВ Bellenot [25] использует граф маршрутизации сообщений. Вычисление ГВВ требует двух циклов – один для запуска вычисления ГВВ, второй – для получения локального минимума и вычисления глобального минимума. The multi-level token passing algorithm [26] применяет иерархический метод для распараллеливания вычисления ГВВ. Многоуровневое разложение позволяет параллельно определять минимальное время среди менеджеров каждого уровня.

Bauerr и соавторы [27] предложили алгоритм, в котором нумеруются все сообщения о событиях, проходящие через определенный канал. Логические процессы учитывают номера отправленных и полученных сообщений, и минимальные отметки сообщений о событии с момента последнего отчета о ГВВ.

Алгоритм пассивной реакции GVT (pGVT) [28] может работать в среде с ненадежными каналами связи. В нем ЛП считает время задержки сообщения, чтобы решить, когда отправлять новую информацию о глобальном виртуальном времени ГВВ-менеджеру. Ключевым улучшением является то, что моделируемые по критическому пути ЛП, будут сообщать ГВВ-информацию чаще, чем другие.

Эффективный асинхронный алгоритм представлен Fujimotoo и Hybinette [29]. Он использует разделяемую мультипроцессорную память, которая гарантирует, что никакие два процессора не будут видеть набор операций с памятью возникающими в разном порядке. Алгоритм не требует подтверждения сообщений, FIFO-доставку сообщений или специальные GVT-сообщения.

5.2 Распределенное вычисление глобального виртуального времени

Распределенные алгоритмы ГВВ не требуют ни централизованного менеджера, ни наличия общей памяти между процессами. Mattern [30] представил эффективный распределенный алгоритм моментального снимка для не-FIFO каналов связи, который не требует подтверждения сообщений. Алгоритм определяет два снимка, где второй проталкивается вперед так, что все переходные сообщения заключены между двумя снимками. Проблема знания, когда снимок полный, решается распределенной схемой прекращения обнаружения.

Srinivasan and Reynolds [31] разработали параллельную сеть сокращения (PRN). ЛП пересылают некоторые сведения о состояниях в PRN, которая поддерживается распределенным ГВВ-алгоритмом. Подтверждения приема сообщения также отправляются на сеть. PRN используется для вычисления и распространения минимальных ЛВВ всех ЛП и минимумов меток всех неполученных сообщений. ГВВ становится доступным для каждого ЛП асинхронно.

ГВВ-алгоритм в среде моделирования SPEEDES оптимизирован для поддержки интерактивного распределенного оптимистического моделирования. Проблема нестационарности сообщений решается с помощью очищения всех сообщений на этапе обновления ГВВ. Алгоритм SPEEDES GVT продолжает обрабатывать события во время этой фазы, но и новые сообщения, которые могут быть сгенерированы, удаляются не сразу.

6 Классификация алгоритмов оптимизации оптимистического протокола

Рассмотренные методы оптимизации можно условно разделить на несколько групп согласно решаемой ими проблеме оптимистического протокола и способам достижения результата (рис. 1).

Классификация методов оптимизации оптимистического протокола

Рисунок 1 – Классификация методов оптимизации оптимистического протокола
(анимация: 5 кадров, 10 циклов повторения, 43.5 килобайт)

Однако, нельзя четко разбить алгоритмы на классы, поскольку многие из них, хотя и направлены на улучшение какого-либо показателя эффективности, одновременно влияют и на другие аспекты моделирования. На рис. 2 показаны причинно-следственные связи между методами и алгоритмами оптимизации, а также между характеристиками моделирующей системы.

Причинно-следственные связи между алгоритмами классификации

Рисунок 2 – Причинно-следственные связи между алгоритмами классификации
(анимация: 9 кадров, 10 циклов повторения, 76.7 килобайт)

Выводы

Результатом исследований является классификация алгоритмов по типу оптимизируемой характеристики и методов, применяемых для этой цели, а также анализ алгоритмов с точки зрения их достоинств и недостатков и их влияния на оптимизацию других параметров моделирующей системы.

На момент написания данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2012 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Список источников

  1. Radharamanan Radhakrishnan, Timothy J. McBrayer, Krishnan Subramani, Malolan Chetlur, Vijay Balakrishnan and Philip A. Wilsey. A Comparative Analysis of Various TimeWarp Algorithms Implemented in the WARPED Simulation Kernel. – 1998.
  2. Voon-Yee Vee, Wen-Jing Hsu. Parallel Discrete Event Simulation: A Survey.
  3. Richard M. Fujimoto. Parallel discrete event simulation – 1990.
  4. Bruce Jones, Vanessa Wallace. Time-Event based processing, a Survey.
  5. Bruno R. Preiss, Wayne M. Loucks. Memory Management Techniques for Time Warp on a Distributed Memory Machine. – 1995.
  6. Carothers, C., Perumalla, K., Fujimoto, R.M. Efficient Optimistic Parallel Simulations using Reverse Computation. – 2000.
  7. Josef Fleischmann, Philip A. Wilsey. Comparative Analysis of Periodic State Saving Techniques in Time Warp Simulators. – 1995.
  8. Francesco Quaglia. Event History Based Sparse State Saving in Time Warp. – 1998.
  9. Francesco Quaglia. Rollback-based parallel discrete event simulation by using hybrid state saving. – 1997.
  10. Turner, S.J. and Xu, M.Q. Performance evaluation of the bounded Time Warp algorithm. – 1992.
  11. Jeff S. Steinman. Breathing Time Warp. – 1992.
  12. Ball, D. and Hoyt, S. The adaptive Time-Warp concurrency control algorithm. – 1990.
  13. Hamnes, D. O. and Tripathi, A. Investigations in adaptive distributed simulation. – 1994.
  14. Alois Ferscha. Probabilistic Adaptive Direct Optimism Control in Time Warp.
  15. Avinash C. Palaniswamy, Philip A. Wilsey: Parameterized Time Warp (PTW): An Integrated Adaptive Solution to Optimistic PDES. – 1996.
  16. Srinivasan S., Reynolds P. Elastic Time. – 1998.
  17. Kiran S. Panesar, Richard M. Fujimoto. Adaptive Flow Control in Time Warp. – 1997.
  18. Om P. Damani, Yi-Min Wang, Vijay K. Garg. Distributed Recovery with K-Optimistic Logging.
  19. Om P. Damani, Yi-Min Wang, Vijay K. Garg. Optimistic Distributed Simulation Based on Transitive Dependency Tracking.
  20. Sean W. Smith, David B. Johnson, and J. D. Tygar. Completely Asynchronous Optimistic Recovery with Minimal Rollbacks. – 1995.
  21. Alessandro Pellegrini, Roberto Vitali, Francesco Quaglia. An Evolutionary Algorithm to Optimize Log/Restore Operations within Optimistic Simulation Platforms. – 2011.
  22. Jun Wang, Carl Tropper. Using Genetic Algorithm to Limit the Optimism in Time Warp. – 2009.
  23. Samadi B. Distributed simulation, algorithms and performance analysis. – 1985, 226 c.
  24. Yi-Bing Lin, Edward D. Lazowska. Determining the Global Virtual Time in a Distributed Simulation. – 1990.
  25. Bellenot, S. Global Virtual Time Algorithms. – 1990.
  26. Conception, A.I., Kelly, S.G., Computing global virtual time using the Multiple-Level Token Passing algorithm. – 1991.
  27. Bauer, H., Sporrer, C., Distributed logic simulation and an approach to asynchronous GVT-calculation. – 1992.
  28. D'Souza,L.M., Fan, L.M., Wilsey, P.A. pGvt: An Algorithm for Accurate GVT Estimation. – 1994.
  29. Richard Fujimoto, Maria Hybinette: Computing Global Virtual Time in Shared-Memory Multiprocessors. – 1997.
  30. Mattern, F. Efficient algorithms for distributed snapshots and global virtual time approximation. – 1993.
  31. Srinivasan, S., Reynolgs, P.F. Hardware support for aggressive parallel discrete event simulations. – 1992.