PARSEC: ПАРАЛЛЕЛЬНАЯ МОДЕЛИРУЮЩАЯ СРЕДА ДЛЯ СЛОЖНЫХ СИСТЕМ

Rajive Bagrodia, Richard Meyer, Mineo Takai, Yu-an Chen, Xiang Zeng, Jay Martin, Ha Yoon Song University of California, Los Angeles (UCLA) Перевод с английского: Меренков А.В. Источник: http://www.wl.unn.ru/~ragozin/mat/parsec_computer.pdf

---

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

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

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

Кроме того, моделирование параллельных программ обычно страдает от 30 до 50-ти замедляющих факторов на процессор. Это означает, что моделирование параллельной программы , исполняющейся от 5 до 15 минут на 128-ядерном процессоре, может занять от нескольких недель до нескольких месяцев даже на самых современных последовательных рабочих станциях. Так как размер физической системы увеличивается, требования моделей к размеру памяти может легко превысить возможности рабочих станций.

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

Еще один недостаток для широкого использования моделирования состоит в стоимости проектирования модели и ее поддержки. Затраты на подробные имитационные модели сложных систем могут легко соперничать с расходами на сами физические системы.

Среда моделирования, которую мы разработали в UCLA, предназначена для попытки решить некоторые из этих вопросов, предоставляя следующие возможности:

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

Наша среда состоит из трех основных компонентов: язык моделирования параллельных систем, называющийся Parsec (от англ. Parsec — PARallel Simulation Environment for Complex systems), его GUI, называющееся Pave, а также портируемые системы исполнения, которые реализуют алгоритмы моделирования.

Parsec основан на языке моделирования Maisie, со следующими значительными изменениями:

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

ПАРАЛЛЕЛЬНЫЕ ПРОТОКОЛЫ МОДЕЛИРОВАНИЯ

Моделирование состоит из серии мероприятий, которые должны быть выполнены в определенные моменты времени. На одном процессоре, эти события могут быть помещены в центральную очередь для того, чтобы глобальный алгоритм обработки списка событий мог правильно их вызывать. Однако при параллельной обработке список событий не только распределен так, что каждый процессор имеет только его часть, но события могут также поступать асинхронно от других процессоров. Для параллельного моделирования дискретных событий (PDES — parallel discrete event simulation), требуется дополнительная информация, чтобы убедиться, что каждый процессор выполняет события в правильном порядке. Были разработаны и в настоящее время изучаются три основных типа параллельных протоколов синхронизации: консервативный, оптимистичный, смешанный (может включать подмодели, выполняющиеся и в консервативном, и в оптимистическом режиме).

Структура моделирования

Параллельные имитационные модели, как правило, программируются как набор логических процессов (ЛП), каждый из которых моделирует один или несколько физических процессов в системе. События в физической системе моделируются путем передачи сообщений между соответствующими процессами, где каждое сообщение содержит временную метку его возникновения в физической системе (что означает, что термины «событие» и «сообщение» можно использовать как взаимозаменяемые). Каждый ЛП имеет следующие переменные:

• Ближайшее время вывода (ЕОТ — Earliest output time). ЕОТ — это нижняя граница временной метки каждого будущего сообщения, отправляемого ЛП. Если ЕОТ равняется бесконечности для некоторого ЛП с именем S, то остальные ЛП могут быть выполнены независимо от S. Примером такого ЛП является процесс погружения.
• Ближайшее время ввода (EIT — Earliest input time). EIT — это нижняя граница временной метки какого-либо будущего сообщения, которое ЛП может получить. EIT для ЛП — это ближайшее время, через которое он может получить сообщение от другого ЛП. EIT в ЛП равняется бесконечности, если ни один из других ЛП не отсылает ему сообщение. Исходный процесс является примером такого ЛП.
• Предпросмотр. Предпросмотр — это. будущий интервал времени, через который ЛП может полностью предсказать события, которые он будет генерировать. Используется для расчета ЕОТ. Например, рассмотрим сервер, функционирующий по методу «первый вошел, первый вышел"(FIFO), который обрабатывает каждое входящее задание за ? единиц времени. Если сервер находится в режиме ожидания в какой-то момент времени т, его предпросмотром является delta и ЕОТ(Т + delta).

В общем, предпросмотр (и, следовательно EIT и ЕОТ) ЛП зависят от состояния ЛП, которое динамически изменяется в процессе моделирования. Относительное значение этих переменных определяет степень детализации и синхронизации модели. Если в EOT ЛП гораздо больше, чем его текущее время симуляции, другие ЛП в системе, скорее всего, выполняются самостоятельно за более длительные интервалы времени.

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

Синхронизация

Наиболее часто используются следующее модели PDES: либо оптимистическая (все ЛП выполняются в оптимистическом режиме) или консервативная (все ЛП выполняются в консервативном режиме). Консервативный ЛП не может взаимодействовать со случайностными ошибками – событиями, возникающими вне временной последовательности – поэтому он будет обрабатывать только события с отметками времени меньше, чем его EIT. Есть ряд алгоритмов, которые вычисляют EIT каждого ЛП распределенным образом, и Parsec включает в себя многие из них. В общем, предпросмотр модели и ее топология значительно влияют на производительность консервативных алгоритмов.

Оптимистический ЛП может обрабатывать события с временными отметками, большими, чем его EIT, но основной протокол синхронизации должен выявлять и исправлять случайностные ошибки. Простейшим механизмом для этого является оптимистический ЛП, который периодически сохраняет или делает контрольные точки своего состояния. Если оказывается, что ЛП обработал сообщения в неправильном порядке, он может откатиться к соответствующей контрольной точке, начиная с которой события обрабатывается в корректной последовательности. Кроме того, оптимистический алгоритм должен периодически вычислить нижнюю границу, которая также называется глобальное виртуальное время (GVT — global virtual time). Оно представляет собой временную метку самого раннего глобального события. Контрольные точки с временными отметками раньше, чем GVT могут быть восстановлены. При использовании нашей модели оптимистическому ЛП достаточно сохранить одну контрольную точку состояния с временной меткой, меньше, чем его EIT. (Минимальным EIT для всех оптимистических ЛП является разумная нижняя граница GVT модели.)