Автор: Bruce Jones, Vanessa Wallace
Перевод: Воротникова Ю.А.
Событийная обработка используется во многих вычислительных процессах. Существует два способа обработки событий: консервативный, который требует, чтобы все входные данные были известны до дальнейшей обработки, и оптимистический, который допускает рискованную обработку. Эта статья в основном охватывает оптимистическую модель, хотя она также рассматривает некоторые достоинства консервативной обработки.
Оптимистическая событийная обработка в основном упоминается в контексте моделирования. Это не единственный возможный случай оптимистической или консервативной событийной обработки. Обработка событий используется во многих программах. При работе программ вызовы процедур, выполнение инструкций ассемблирующих языков также являются формами событийной обработки. Событие является вызовом. При оптимистической обработке это может принять форму вызова программы без наличия всех файлов и данных, вызова процедуры без наличия всех аргументов или выполнения инструкций на ассемблере без завершения необходимых промежуточных вычислений. Последнее является наиболее очевидным в конвейерных микропроцессорах, которые используют предсказание ветвлений и отмену неверных результатов.
Консервативная обработка событий оказалась наиболее интуитивно понятной при проектировании, сборке проекта и запуске. Она основана на концепции того, что логический процесс получает самое последнее входное событие и применяет его к процессу, которому он принадлежит. Процессы не могут создавать события, которые существуют в более раннем виртуальном времени, чем текущее виртуальное время выполнения процесса (будущие события не могут повлиять на события в прошлом).
Потому что это самые ранние события и вся обработка завершена к тому времени. Однако таким образом проще всего проектировать, компилировать и запускать однопоточные программы, реализация в многопоточной среде становится проблематичной. Проблема вытекает из гарантии причинно–следственности. Все события для данного процесса должны быть доступны, прежде чем процесс можно запускать. Это требует либо сегмента, который координирует все задачи, либо методики, которая позволяет задачам знать, когда причинно–следственная связь гарантирована, без необходимости синхронизации задач.
Использование единственной координационной точки событий создает узкое место. В худшем случае эта структура будет деградировать до выполнения в однопоточном режиме, независимо от количества процессоров. Консервативные протоколы интуитивно понятны, кроме случаев, когда их пытаются распараллелить на нескольких процессорах. Их легко реализовать на одном процессоре – разработка ориентирована на однопроцессорные архитектуры (серийная обработка). Обработка содержит очередь событий, наиболее ранее событие которой обрабатываются и выходные события возвращаются в очередь(и).
Консервативный алгоритм Chandy, Misra и Bryant'а [36] использует распределенную временную схему, которая позволяет выполняться элементам, как только они готовы, в попытке использовать больше параллелизма в логике моделирования. Дополнительный параллелизм достигается за счет более сложных элементов и оценки стоимости тупиков. После обнаружения тупика, он будет решен путем нахождения минимального времени события среди всех невостребованных событий в системе.
Его основная методология проста. Алгоритм прост в реализации, имеет простое управление и структуры данных. Он хорошо работает до тех пор, пока все статические каналы одинаково используются. Большая дисперсия событий в пространстве и времени не является причиной для беспокойства. Кроме того, потребление памяти является консервативным.
Одним из недостатков алгоритма CBM является высокая стоимость поддержания синхронности времени в распределенной системе. Должна существовать глобальная контрольная точка или метод согласования текущего/следующего GVT среди распределенных систем. Данный консервативный алгоритм не максимизирует параллелизм из–за единственной точки контроля времени (или принятия решения о том, который из процессов имеет большие накладные расходы из–за сообщений). Кроме того, механизм синхронизации блокирует процессор и, как следствие, склонен к тупикам. Обработка не может легко справиться с выходными сообщениями, время которых не возрастает монотонно (события со временем задержки). Это происходит потому, что время входного события используется для вычисления LVTH локального процессора, которое позволяет знать, продолжать ли обработку событий. Способом решения этой проблемы является создание сообщений самому себе, указывая, что выходное значение «х» будет сгенерировано после задержки.
Тупиков в алгоритме CBM можно избежать путем передачи нулевого сообщения (null–сообщения) [37], которое используются для объявления отсутствия реальных сообщений. Таким образом, при получении null–сообщение логический процесс знает, что не может принимать реальные сообщения по соответствующей входящей связи до момента времени, указанного в null–сообщении. Обработка null–сообщения, таким образом, просто сбрасывает значение блокировки входящей связи. Так как тупик в параллельном моделировании, как правило, вызван циклическими обратными связями в модели сети, то для выхода из тупика, как правило, должно быть передано огромное количество null–сообщений из этих циклов. Тем не менее, в некоторых случаях логические процессы не должны заблокироваться, если обратная связь может быть обнаружена.
Алгоритм carrier–null–сообщений разработали Cai и Turner [37] для выявления наличия циклической обратной связи в ходе моделирования, а также для улучшения прогнозирования обнаружения циклической обратной связи. Обнаружение циклической обратной связи и улучшение прогнозирования делают необходимым использование специального протокола сообщений – carrier–null–сообщений. Подобный алгоритму CBM, алгоритм carrier–null–сообщений также состоит из пяти последовательных шагов: ввод, моделирование, расчет 1, вывод, и расчет 2. Работа алгоритма сarrier–null–сообщений отличается от алгоритма CBM на шаге моделирования и вывода, как описали Cai и Turner [37]. Тем не менее, алгоритм carrier–null–сообщений имеет дело только с определенными сетями обратной связи. Для того, чтобы эффективно использовать алгоритм, должны быть разработаны более сложные стратегии (например, моделирование на логических процессах сетей с несколькими иерархическими цепочками обратных связей).
На основании доказательства эффективности планировщика для многопоточного программирования Cai и Turner [38] разработали предсказуемый и надежный консервативный алгоритм. Моделирование включает в себя стиль выполнения «разделяй и властвуй», который не требует использования null–сообщений или обнаружения тупиковых ситуаций. Алгоритм является надежным, потому он может быть использован для моделирования приложений, где локальное прогнозирование мало или равно нулю, или когда информацию для прогноза трудно извлечь. Хотя может быть использована локальная прогнозирующая информация, алгоритм устойчив и тем, что он также включает в себя глобальный расчет безопасного времени, до которого события могут быть обработаны благополучно. Алгоритм оригинален тем, что он включает как локальную, так и глобальную информацию в расчет безопасного времени для каждого логического процесса. В результате было получено хорошее ускорение, когда средняя степень параллелизма велика по сравнению с количеством процессоров.
Dag Consistent Parallel Simulation алгоритм моделирования Cai и Turner был еще более улучшен Lim, Low, and Turner [39] изменением вычисления безопасного времени на виртуальную платформу моделирования. Было установлено, что вычисления безопасного времени могут быть смягчены для дальнейшей потенциальной возможности выполнения большего числа событий в супер–шаге. Существует два преимущества этого модифицированного алгоритма. Сначала он просто объединяет прогнозирующие значения при вычислении безопасного времени, значительно сокращая количество необходимых супер–шагов. Также внешние события логического процесса больше не ограничены необходимостью генерироваться по порядку.
Оптимистическое управление событиями было реализовано в ответ на проблемы выполнения в консервативном стиле, когда речь идет о параллельном выполнении. Наиболее затратной в консервативном исполнении является гарантия причинно–следственности. Если причинно–следственность была ослаблена, но обеспечена за счет коррекции, вычисление с предполагаемым входным значением может улучшить время выполнения, если предположение о входном значении будет правильным. В некоторых случаях выход процесса не может измениться, если предположить, что вход был неправильным. Для обеспечения причинно–следственности через коррекцию должен быть механизм восстановления прошлого состояния, если предполагаемое значение оказалось неверными. На основе этого принципа была предложена операционная система Time Warp [28].
Time Warp имеет одну очередь входных событий. События обрабатываются в порядке низшего значения временной метки. Выходные события не буферизируются, потому что нет никаких требований к тому, чтобы выходные события появлялись в порядке увеличения времени как в консервативной системе Chandy–Misra [36]. Физический процесс отслеживает свое локальное виртуальное время, которое вытекает непосредственно из времени событий входной очереди. Если обнаруживается, что локальное виртуальное время процесса больше, чем время события из очереди, выполняемый процесс узнает, что он обработал события вне временного порядка и имеет место нарушение причинно–следственных связей. Time Warp исправляет нарушение причинно–следственности «откатом» в предыдущее состояние, и процессом генерируются анти–сообщения для отмены любых неверных данных на выходе.
Откат и затраты, связанные с сохранением информации для возможности отката, являются большими накладными расходами, связанными с оптимистической обработкой по алгоритму Time Warp. Откат не только аннулирует результаты физического процесса за счет анти–сообщений, откат может стать причиной возникновения других событий для аннуляции результатов других физических процессов и потенциально вызвать каскадный откат. Аннулирование обработки приводит к тому, что выполнение повторится с новыми данными, и, возможно, разными результатами. Необходим также значительный объем памяти для поддержания механизма отката. Для каждого состояния все данные, все варианты состояний должны быть сохранены, также как и копия исходящего события и входного события, которые вызвали переход.
Существует несколько предложенных и протестированных методов, которые должны справляться с тенденцией алгоритма Time Warp к использованию процессора для вычислений, которые в дальнейшем будут недействительными, существованию затрат на откат, потреблению памяти и сетевого трафика между процессами. К ним относятся оптимизация на основе движущегося окна, ленивая/агрессивная/адаптивная отмены, контроль интервалов точек сохранения.
Агрессивная отмена делает предположение, что большинство выходных значений будут изменены, когда выполнение вернется в точку локального виртуального времени, которая была непосредственно перед откатом. Концепцией является получение анти–сообщений для отмены ошибочного вывода до того, как любой другой физический процесс использует его в расчетах. Чтобы сделать это, все анти–сообщения генерируются во время отката, до того, как произойдет повторное выполнение событий. Этот метод работает достаточно хорошо, когда процесс выполняется как ряд состояний (машина состояний), которые используют входные события для перехода в различные состояния, выходные события генерируется в новых состояниях. Это не очень хорошо работает, когда физические процессы моделируют одношаговые функции с малым временным шагом или без него.
Ленивая отмена делает предположение, что малая часть выходных данных изменится, если новое событие добавится к последовательности. Концепция заключается в задержке отправки анти–сообщений, пока не подтверждено, что выход неправильный, чтобы не вызывать откат других физических процессов. В результате, процесс производит откат и начинает выполнять измененный список входных событий. Если какие–либо выходные события были изменены в процессе перевыполнения, рассылаются анти–сообщения, сопровождаемые исправленными выходными событиями, если таковые имеются. Если в результате перевыполнения выясняется, что нет никаких изменений в выходном сообщении, ничего не меняется, и предыдущее выходное сообщение остается неизменным. Если результат перевыполнения таков, что нет выходного сообщения для виртуального времени, когда в предыдущем выполнении создавалось выходное сообщение, анти–сообщение отправляется, чтобы отменить ошибочное сообщение, и никаких новых сообщений не создается. Хотя этот метод эффективен при обработке машины без состояний, он может вызвать больший откат зависимых процессов, позволяя им выполняться дальше в виртуальном времени, прежде чем произойдет исправление.
Адаптивная отмена предназначена для решения проблемы с необходимостью определения стратегии отмены на этапе запуска. Чтобы иметь возможность статически определить оптимальную стратегию отмены до выполнения, требуется совершенное знание среды исполнения. Кроме того, статические политики не позволяют среде выполнения адаптивно меняться на полпути исполнения. Существует ситуация, когда агрессивная отмена может быть наиболее эффективной в начале, но в ходе последующего выполнения, ленивая отмена может стать более эффективной. По Wilsey, в ходе испытаний было установлено, что оптимальная стратегия была чувствительна к тому, как физические процессы были разделены на логические процессы (разделяющая схема). Адаптивная отмена позволяет процессу самому определять, какую стратегию отмены использовать, основываясь на показателях времени выполнения.
Адаптивный алгоритм работает, вычисляя коэффициент попадания. Коэффициент попадания, по существу, является процентом откаченных выходных сообщений, где вывод не изменился. Для предотвращения чрезмерных накладных расходов, глубина набора экземпляров (фильтрация глубины) определяется при запуске. Фильтрация глубины – это количество хранимых сравнений результатов выходных сообщений для расчета коэффициента попадания. Определены два порога. A2L_Threshold – пороговый коэффициент попадания, при котором алгоритм переходит от агрессивной к ленивой отмене (A2L). L2A_Threshold – это порог, при котором алгоритм переходит от ленивой к агрессивной отмене. Значение A2L_Threshold должно быть больше или равно значению L2A_Threshold. Быстрое переключение между ленивой и агрессивной отменой препятствует большой глубине фильтра (уменьшает статистическую дисперсию), редко вызывает механизм управления и создания гистерезиса в переключаемых значениях, делая A2L_Threshold неравным L2A_Threshold. Тестирование (путем измерения времени выполнения) по Wilsey показало, что адаптивная отмена могла бы работать так же эффективно, как оптимально выбранный протокол отмены.
Наибольшее потребление ресурсов в системе Time Warp приходится на использование памяти для отката информации о состоянии, хранение входных и выходных сообщений. Поскольку хранение входных событий необходимо для расчетов после отката и копии выходных сообщений необходимы, чтобы выявить любые анти–сообщения, которые должны быть отправлены, большинство разработок имеют методы для уменьшения места, необходимого для копий физических состояний процесса (контрольные точки).
Это механизм, который Preiss и Loucks [15] предложили использовать для управления памятью, когда система использует критически большой объем памяти. Это не метод минимизации использования памяти, а метод для более вероятного завершения выполнения за счет высвобождения используемой памяти, но некритичного распределения памяти. По сравнению с искусственным откатом (Artificial Rollback) и механизмами отмены, он обещает возможность ограниченного восстановления памяти, при этом не заставляя физические процессы совершать резервное копирования в виртуальное время, как это делают механизм отмены и искусственный откат. Механизм обрезания основан на восстановлении необходимой памяти из информации о сохраненных состояниях физического процесса. Если возникает откат к отсутствующему теперь состоянию, это заканчивается откатом к первому в виртуальном времени состоянию до отсутствующего, а затем проходу вперед, используя сохраненные входные события для пересчета этого состояния. Есть ограничения для обрезки. Ни физические процессы, ни состояние GVT не должны быть удалены. Выбор состояний зависит от реализации и выходит за пределы ограничений механизма обрезания.
Периодическое сохранение состояний было первоначально предложено Jefferson [28] как способ снижения накладных расходов на хранение состояний в системе Time Warp. Оригинальный документ не дал никакого развития периодическим контрольным точкам на то время.
Обнаружив, что алгоритм периодического сохранения состояний Lin, Preis, Loucks и Lazowska [2] является вычислительно сложным, Fleischmann и Wilsey [6] предложили простой эвристический алгоритм, основанный на диспетчерском управлении в теории управления. Эвристика пытается сбалансировать два типа накладных расходов – стоимость сохранения состояний против стоимости прохода вперед по несохраненным состояниям. Функция стоимости является производной от суммы затрат на сохранение состояния и затрат на проход вперед по несохраненным состояниям. Интервал сохранения пересчитывается каждый N интервалов времени (обычно 100), если предыдущий шаг увеличивал интервал, и если функция стоимости на самом деле увеличивается, интервал сохранения будет уменьшаться на единицу. Если наблюдалось снижение функции стоимости, интервал сохранения будет дальше увеличиваться. Эвристический алгоритм симметричен, если предыдущий шаг уменьшает интервал сохранения. Эффективно работает эвристический локальный поиск минимума в процессе контроля. Так как эвристический алгоритм применяется во время выполнения программы, он также способен обрабатывать динамические изменения в поведении отката и интервала сохранения.
Учитывая, что значительную часть накладных расходов составляет сохранение состояний, Carothers [20] применил подход исправления физических процессов как потенциально обратимых. Откат будет достигнут применением обратных операций с использованием текущего состояния и сохраненных входных событий, чтобы пройти откатываемые состояния обратно. В случае, если операции не полностью обратимы (например, операция уничтожения), используется сохранение частичной информации состояния для необратимых частей процесса в выходных событиях. Был также создан обратимый генератор случайных чисел с периодом 2121, так как некоторые процессы требуют псевдослучайных расчетов событий, вызывающих вероятностные события. Обратимые физические процессы были написаны от руки, но механизм генерации компилятором обратных операций был описан на диаграммах. Побочный эффект использования обратимого подхода был обнаружен в форме значительного увеличения скорости.
Wilsey, Palaniswamy и Aji [7] предложили метод, в котором физические процессы не должны хранить данные о прошлых состояниях. Они разделили физические процессы на две категории: memoried – выходные события определяются как значениями входных событий, так и внутренними значениями состояний (сохраненной историей значений, до их текущего значения), а memoryless – процессы, чьи выходные события непосредственно определяются значениями их входных событий. Для реализации этой схемы, входные события были разделены на два набора входных очередей. Они были отсортированы как по переменной «категория», на которую они влияют, так и по времени прибытия. Это позволило физическому процессу определить входные значений для отката путем просмотра сразу всех входных события с предыдущим время отката, вызвавшим событие, и перейти дальше от этой точки.
Консервативные методы обработки были включены в это исследование по двум причинам. Во–первых, консервативные методы являются предпочтительным путем обработки событий (данных), в том числе в параллельных системах. Во–вторых, потому что Time Warp или оптимистическая обработка событий были улучшениями оригинального алгоритма Chandy–Misra [36]. Если смотреть в будущее, то основной акцент будет ставиться на оптимистические методы обработки. Это связано с ограничением, которое заключается в том, что для передаче данных используются электрические сигналы. Эти ограничения возникают из–за того, что тактовая частота микропроцессоров зачастую выше радиоволн, используемых в радиопередатчиках. Поскольку частоты достигли гигагерц, небольшая дорожка на материнской плате длиной 3 дюйма становится полноправной волновой антенной. Эта дорожка, выступая в качестве антенны, будет тратить некоторую долю мощности сигнала на излучение радиоволн, будет более чувствительной к индуктивной связи, что приведет к тому, что передаваемый сигнал будет искажен (нужно разрешение Найквиста приблизительно 3 порядка для пропускания резонирующих прямоугольных импульсов. Третий порядок Найквиста является 3–й гармоникой). Это приведет к использованию слабосвязанных параллельных систем для решения проблем, и консервативная обработка имеет очевидную тенденцию к ограничению параллельной обработки путем ее синхронизации и проверки причинно–следственности.
1. On–Line Configuration of a Time Warp Parallel Discrete Event Simulator. Radharamanan Radhakrishnan, Nael Abu–Ghazaleh, Mololan Chetlur, Philip A. Wilsey, Dept of ECES, PO Box 210030, Cincinnati University, Cincinnati OH 45221–0030, Proceedings of the 1998 International Conference on Parallel Processing, August 10–14, 1998 ISBN 0–8186–8650–2
2. Selecting the checkpoint interval in time warp simulation. Y.B.Lin, B.R. Preiss, W.M.Loucks, E.D.Lazowska, Proceedings of the 7th Workshop on Parallel and Distributed Simulation (PADS), pages 3–10. Society for Computer Simulation, July 1993
3. Feedback Control in Time Warp Synchronized Parallel Simulators. Philip A. Wilsey, Dept of ECES, PO Box 210030, Cincinnati University, Cincinnati OH 45221–0030, First International Workshop on Distributed Interactive Simulation and Real Time Applications, 1997
4. An Analytical Comparison of Periodic Check–Pointing and Incremental State Saving. A. Palaniswamy, P. A. Wilsey, Society for Computer Simulation{PADS 93}, July 1993, pages 127–134.
5. Adaptive Check–Pointing in Time Warp. R.Ronngren and R. Ayani, Proceedings of the 8th Workshop on Parallel and Distributed Simulation{PADS 94}, pages 110–117, Society for Computer Simulation.
6. Comparative Analysis of periodic state saving techniques in time warp simulators. J. Fleischmann, P.A.Wilsey, Proceedings of the 9th Workshop on Parallel and Distributed Simulation {PADS 95}, pages 50–58, June 1995
7. Rollback Relaxation: A Technique for Reducing Rollback Costs in Optimistically Synchronized Parallel Simulators. Philip A. Wilsey, Avinash Palaniswamy, Sandeep Aji, Center for Digital Systems Engineering, University of Cincinnati, Cincinnati OH 45221–0030, Proceeding of the International Conference on Simulation and Hardware Description Languages, SHDL–1994
8. The adaptive Time–Warp concurrency control algorithm. D. Ball & S. Hoyt, Distributed Simulation pgs 174–177, Society for Computer Simulation, Jan 1990
9. Adaptive bounded time windows in an optimistically synchronized simulator. Palaniswamy & P.A. Wilsey, Third Great Lakes Symposium on VLSI, pages 114–118, 1993
10. Performance evaluation of the bounded Time Warp algorithm. S.J. Turner and M. Q. Xu, Proceedings of the SCS Multiconference on Parallel and Distributed Simulation 24(3):117–126, 1992
11. A performance study of the cancelback protocol for time warp. S.R.Das & R.M. Fujimoto, Proceedings of the 7th Workshop on Parallel and Distributed Simulation. Jul 1993 pages 135–142
12. An adaptive memory management protocol for Time Warp parallel simulation. S.R.Das and R.M.Fujimoto, "Sigmetrics", pgs 201–210, May 1994
13. Investigations in adaptive distributed simulation. D. O. Hamnes and A. Tripathi. Proceedings of the 8th Workshop on Parallel and Distributed Simulation PADS(94)" pages 20–23. Society for Computer Simulation, July 1994
14. Optimal Memory Management for Time Warp Parallel simulation. Y.B. Lin & B.R.Preiss. ACM Transactions on Modeling and Computer Simulation, 1(4):283–307, Oct 1991.
15. Memory Management Techniques for Time Warp on a Distributed Memory Machine. Bruno R. Preiss, Wayne M. Loucks, Department of Electrical and Computer Engineering, University of Waterloo, Waterloo ON N2L 3G1 {Ontario, Canada}, The Institute of Electrical and Computer Engineers, 1995
16. Optimistic Fossil Collection for Time Warp Simulation. Christopher H. Young, Philip A. Wilsey, Computer Architecture Design Laboratory, Dept. of ECES, PO Box 210030, Cincinnati OH 45221–0030, Proceedings of the Hawaiian International Conference on System Sciences HICSS–1996
17. Optimism: Not Just For Event Execution Anymore. Christopher H. Young, Radharamanan Radhakrishnan, Philip A. Wilsey. Dept of ECES, University of Cincinnati, Cincinnati OH 45221–0030, 13th Workshop on Parallel and Distributed Simulation, PADS–1999
18. Performance Benefits of Optimism in Fossil Collection. Christopher H. Young, Radharamanan Radhakrishnan, Philip A. Wilsey. Dept. of ECES, University of Cincinnati, Cincinnati OH 54221–0030, Proceedings of the Hawaii International Conference on System Sciences, HICSS’99
19. Dynamically Switching between Lazy and Aggressive Cancellation in a Time Warp Parallel Simulator. Raghundandan Rajan, Philip A. Wilsey, Center for Digital Systems Engineering, Dept. of ECE, PO Box 210030, University of Cincinnati, Cincinnati OH 45221–0030, Proceedings of the 28th Annual Simulation Symposium, ASS–1995
20. Efficient Optimistic Parallel Simulations using Reverse Computation. Christopher D. Carothers, Dep. Computer Science Rennselaer Polytechnic Institute, Kalyan S. Perumalla & Richard M. Fujimoto, College of Computing, Georgia Inst. Tech.
21. A Control Mechanism for Parallel Discrete Simulation. L. M. Sokol, B. K. Stucky, V. S. Hwang. Proceedings of the 1989 International conference on Parallel Processing, Vol 3, pp 250–254, 1989
22. Performance evaluation of the bounded Time Warp Algorithm. S. Turner, M. Xu. Proceedings of the 6th Workshop on Parallel and Distributed Simulation pp117–128, 1992
23. Concurrency Preserving Partitioning(CPP) for Parallel Logic Simulation. Hong. K. Kim, Jack Jean. Proceedings of the 10th Workshop on Parallel and distributed Simulation, pp98–105, 1996
24. Load Balancing and Work Load Minimization of Overlapping Parallel Tasks. V. Krishnaswamy, G. Hasteer, P. Banerjee. Proceedings of the 1997 International Conference on Parallel Processing, Aug 1997
25. Asynchronous Distributed Simulation via a Sequence of Parallel Computations. K. M. Chandy, J. Misra. Communications of the ACM, Vol 24, No 11, pgs198–206 April 1981
26. Parallel and Distributed Simulation of Discrete Event Systems. Alois Ferscha. Contributed to Handbook of Parallel and Distributed Computing, McGraw–Hill, 1995 NOTE: This one had a detailed summary of different mechanisms, though from a simulation point of view.
27. Distributed Discrete–Event Simulation. J. Misra, ACM Computing Surveys, 18(1):39–65, 1986
28. Distributed Simulation and the Time Warp Operating System. David Jefferson, Brian Beckman, Fred Wieland, Leo Blume, Mike DiLorento, Phil Hontalas, Pierre Laroche, Kathy Sturdevant, Jack Tupman, Van Warren, John Wedel, Herb Younger, Steve Bellenot. NOTE: Original Class article
29. Parallel Discrete–Event Simulation of FCFS Stochastic Queuing Networks. D. M. Nicol, Proceedings of the ACM/SIGPLAN APPEALS 1988, pgs124–137
30. Algorithms for distributed termination detection. F. Mattern, Distributed Computing, 2:161–175, 1987
31. Distributed Deadlock Detection. K. M. Chandy, J. Misra, L. M. Haas, ACM Transactions on Computer Systems, 1(2):144–156, May 1983
32. Bounded Lag Distributed Discrete Event Simulation. B. D. Lubachevsky, Proceedings of the SCS Multiconference on Distributed Simulation 19(3) pgs183–191 SCS, Feb1988
33. An Algorithm for Distributed Discrete–Event Simulation – The ‘Carrier Null’ Message Approach. Wentong Cai, Steven J. Turner, Proceedings of the SCS Multiconference on Distributed Simulation Vol 22(1), pages 3–8. SCS January 1990
34. An Algorithm for Reducing Null–Messages of CMB Approach in Parallel Discrete Event Simulation. Wenton Cai, Steven J. Turner.
35. OFC: A Distributed Fossil–Collection Algorithm for Time–Warp. Christopher H. Young, Nael B. Abu–Ghazaleh, Philip A. Wilsey. Proceedings of the 12th International Conference on Distributed Computing DISC–1998
36. An Evaluation of the Chandy–Misra–Bryant Algorithm for Digital Logic Simulation. Larry Soule and Anoop Gupta, Computer Systems Laboratory, Standford University, CA 94305, Distributed Simulation, Volume 24(2), Pages 129–138, California, SCS. Simulation: a Predictable and Robust Conservative.
37. An Algorithm For Reducing Null–Message of CMB Approach in Parallel Discrete Event Simulation. Wentong Cai, Stephen J. Turner Dag Consistent Parallel Simulaition
38. Dag Consistent Parallel Simulation: a Predictable and Robust Conservative Algorithm Wentong Cai, Stephen J. Turner.
39. Relaxing SafeTime Computation of a Conservative Simulation Algorithm. Chu–Cheow Lim, Yoke–Hean Low, and Stephen J. Turner.