Parsec: параллельная моделирующая среда для сложных систем.

Авторы: Rajive Bagrodia, Richard Meyer, Mineo Takai, Yu-an Chen, Xiang Zeng, Jay Martin, Ha Yoon Songs.

Перевод с английского: Мельников А.И.

Источник: http://scalable-networks.com/pdf/parsec.pdf

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

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

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

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

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

Другой недостаток использования моделирования – это цена разработки модели и её поддержки. Стоимость проектирования и разработки детализированных моделей для сложных систем может превысить стоимость самих физических систем.

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

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

Моделирующая среда состоит из трех главных компонентов: язык параллельного моделирования Parsec(parallel simulation environment for complex systems), графического интерфейса, который называется Pave и переносной системой исполнения, реализующей алгоритмы моделирования.

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

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

Протоколы параллельного моделирования

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

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

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

Начальное время вывода(EOT). ЕОТ – нижняя граница временного интервала сообщений, которые может послать логический процесс. Если ЕОТ равен бесконечности для некоторого логического процесса s, оставшиеся логические процессы могут быть выполнены независимо от s. Процесс слива – пример такого логического процесса.
Начальное время ввода(EIT). EIT – нижняя граница временного интервала сообщений, которые может получить логический процесс. EIT логического процесса s – это начальное время, в которое он может получить сообщение от другого логического процесса. EIT процесса s равен бесконечности, если никакой другой процесс не посылает ему сообщений. Исходный процесс – пример такого процесса.
Lookahead(предсказание). Lookahead для логического процесса – это будущий интервал времени, в течении которого процесс может предсказать события, которые он сгенерирует. Lookahead используется для вычисления EOT. Например, представьте FIFO-сервер, который выполняет входящую работу за delta единиц времени. Если сервер простаивает в определенный момент времени моделирования t, его lookahead равен delta, а EOT = (t+delta).

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

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

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

Оптимистические логические процессы могут обрабатывать события с временными отметками, большими, чем EIT, однако нижележащий протокол синхронизации должен определять и корректировать нарушения ограничения причинной связи. Самый простой механизм для этого – оптимистический логический процесс, который периодически сохраняет своё состояние. Если появляется сообщение в неверном порядке, процесс может быть возвращен в сохраненное состояние, с дальнейшей обработкой событий в верном порядке. Также оптимистический алгоритм должен периодически вычислять нижнюю границу, также называемую глобальным виртуальным временем(GVT), на временной отметке самого раннего глобального события. Точки состояний, сохраненные ранее, чем GVT, могут быть восстановлены. Используя предложенную модель, для оптимистичных логических процессов достаточно сохранять хотя бы одно состояние с временем меньшим его EIT (минимум EIT всех оптимистичных логических процессов - приемлемая нижняя граница GVT модели).

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

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

В данной агрессивной, основанной на null-сообщениях, схеме, всякий раз, когда EOT логического процесса, скажем s, изменяется, EOTs посылается другим логическим процессам, используя null-сообщение. Null-сообщение может быть, конечно, вложено в регулярное сообщение, когда это возможно. При получении null-сообщения логический процесс пересчитывает свой EIT и EOT и распространяет изменения другим логическим процессам. С учетом модели без нулевых циклов задержки (все логические процессы имеют нулевой lookahead), такой алгоритм будет со временем повышать EIT (и следовательно, время) каждого процесса, независимо от того в каком режиме он выполняется – консервативном или оптимистичном. Гибридные протоколы также полезны для составления автономных симуляторов, в которых каждое моделирование может локально использовать консервативный, оптимистичный или последовательный протокол.

Разработка среды моделирования

Среда моделирования была разработана таким образом, чтобы аналитик мог исследовать полезность различных алгоритмов моделирования и параллельных архитектур для выполнения заданной модели. Среда поддерживает большое количество интерфейсов для программных моделей: язык моделирования Parces, основанный на С; библиотека Compose для С, которая может быть сопряжена с С++ кодом для выполнения параллельного моделирования, написанного на С++; Pave. Рисунок 1 иллюстрирует среду, включая поддерживаемое аппаратное обеспечение, пакеты сообщения, операционные системы, алгоритмы синхронизации и программные интерфейсы.

Parsec

Parsec адаптирует метод взаимодействия процессов к дискретно-событийному моделированию. Программа Parsec состоит из набора объектов и функций C. Каждый объект – это логический процесс, который моделирует соответствующий физический процесс; объекты могут быть созданы и уничтожены динамически. События моделируются с помощью передачи сообщений между сообщающимися объектами. Каждое сообщение содержит в себе логическую отметку времени, в которую происходит событие в физической системе. Объект также может назначать для себя специальное сообщение, которое называется timeout для специального времени в будущем. Это сообщение часто используется объект для моделирования течения времени в физической системе, и его обработка оптимизирована в системе.

...

Разработка визуальной модели

Parsec Visual Environment (Pave) облегчает визуальную разработку библиотек, связанных с компонентом моделирования, создание моделей из этих компонент в просто визуальном Фреймворке, генерацию Parsec кода для моделей и оптимизацию моделей для параллельного выполнения. Библиотека компонентов может быть создана для таких областей, как сетей с очередями или мобильных сетевых инфраструктур. В отличии от уже существующих средств визуального моделирования, Pave был разработан специально для поддержки параллельного моделирования.

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

Рисунок 2 – Модульное моделирование, разработанное в Pave и топология сети с очередями с модулем подсети

...

Примеры

Большое количество моделей в различных областях было разработано, используя модулирующие среды Maisie и Parsec: цепные модели VLSI, телекоммуникационные модели, ATM-модели, модели беспроводных сетей, параллельные архитектуры и модели систем ввода-вывода, а также модели параллельных программ. Результат эффективности выполнения параллельных моделей изображается в виде графов ускорения, где ускорение вычисляется, как:

Speedup(N,A) = Ts /Tp(N,A),

где Ts – время последовательного выполнения модели с последовательным списком глобальных событий, реализованных при помощи косого дерева, а Tp(N,A) – время выполнения на N процессорах, используя алгоритм моделирования А. (Иногда одноузловая консервативная реализация была быстрее, чем алгоритм списка глобальных событий. В таком случаем было использовано самое быстрое время для вычисления ускорения).

Эксперименты были выполнены на 32-узловой IBM SP2, на которой был запущен AIX – каждый узел оснащен процессором RS/6000, оперативной памятью 256 мБайт и частотой 66,7 мГц. Также эксперименты выполнялись на Sparc 1000 под управлением Solaris 2.5.1 с восемью процессорами SuperSparc с частотой 51 мГц и оперативной памятью 512 мБайт.

Моделирование схемы переключения уровней

Моделирование схем – слабая сторона в разработке схем VLSI, и параллельное выполнение может значительно уменьшить время моделирования для больших схем. Был разработан Mirsim – параллельный симулятор переключения уровней, который является Parsec-реализацией Irsim, существующего управляемого событиями симулятора включения линейного режима MOS-транзисторов. Используя большое разнообразие техник разделения схем на IBM SP2, была использована Parsec-реализация для моделирования большого количества схем с консервативным и оптимистичным протоколами.

В тесте участвовало несколько схем размером от 3,300 до 87,00 транзисторов. Эти схемы были первый раз промоделированы с помощью Irsim и последовательной реализацией Mirsim. Сравнительно с Irsim, среднее замедление для Mirsim было всего лишь 2,6%, с максимальным замедлением для схемы – меньше, чем 6%. Текущий набор разделяющих алгоритмов, поддерживаемый Mirsim включает итеративный разделяющий алгоритм(K-FM) и ациклический алгоритм(K-AFM), который накладывает ограничение на генерируемые части – они не должны иметь циклов. Дополнительно, графическое представление позволяет разработчику вручную разбивать схему.

Рисунок 3 – Результаты моделирования схем VLSI, показывают лучший метод разделения для каждого алгоритма синхронизации на примере набора схем

Рисунок 3 обобщает результаты моделирования для VLSI-схем, показывая для каждой схемы лучшее ускорение, полученное с помощью консервативного и оптимистичного алгоритмов и специфического алгоритма разбиения, показавшего подобный результат. Ни один из алгоритмов деления или синхронизации не доминировал, но ациклические части показали лучшую производительность. Их производительность повысилась после ликвидации циклических зависимостей в параллельной модели, что для консервативных алгоритмов значительно улучшило свойства предсказания для объектов, что дало значительное сокращение null-сообщений. Для оптимистичных алгоритмов, это уменьшило количество откатов, но уменьшение времени выполнения не настолько существенно.

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

Рисунок 3 также показывает ускорение, предсказанное ISP. Во многих случаях производительность симулятора близка к нижней границе, предсказанной ISP, что ясно показывает, что дальнейшие улучшения производительности произойдут при использовании лучших алгоритмов разделения или при более эффективной реализации IPS, но не при улучшенит самого механизма синхронизации.

Ссылки

E.A. Brewer et al., Proteus: A High Performance Parallel Architecture Simulator, Tech. Report MIT/LCS/ TR-516, Massachusetts Institute of Technology, Cambridge,Mass., 1991.
J. Misra, "Distributed Discrete-Event Simulation," ACM Computing Surveys, Mar. 1986, pp. 39-65.
D. Jefferson, "Virtual Time," ACM TOPLAS, July 1985, pp. 404-425.
V. Jha and R. Bagrodia, “A Unified Framework for Conservative and Optimistic Distributed Simulation,” Proc.1994 Workshop on Parallel and Distributed Simulation, Society for Computer Simulation, San Diego, Calif., 1994, pp. 12-19.
R. Bagrodia, “Parallel Languages for Discrete-Event Simulation Models,” IEEE Computational Science and Engineering, Apr.-June 1998, pp. 27-38.
R. Fujimoto, “Parallel Discrete Event Simulation,” Comm. ACM, Oct. 1990, pp. 30-53.
A. Alwan et al., “Adaptive Mobile Multimedia Networks,” IEEE Personal Comm., Apr. 1996, pp. 7-22.
K.M. Chandy and R. Sherman, “Space-Time and Simulation,” Proc. Distributed Simulation Conf., Society for Computer Simulation, San Diego, Calif., 1989, pp. 33-57.
R. Bagrodia, K.M. Chandy, and W.T. Liao, “A Unifying Framework for Distributed Simulation,” ACM Trans. Modeling and Computer Simulations, Oct. 1991, pp. 348-385.
R. Bagrodia, V. Jha, and M. Takai, Performance Evaluation of Conservative Algorithms in Parallel Simulation Languages, Tech. Report CSD 980026, Computer Science Dept., UCLA, 1998.
Y. Chen and R. Bagrodia, “Shared Memory Implementation of a Parallel Switch-Level Circuit Simulator,” Proc. 12th Workshop on Parallel and Distributed Simulations (PADS) 98, IEEE CS Press, Los Alamitos, Calif., 1998, pp. 134-141.