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

На правах рукописи

00505»

Речистов Григорий Сергеевич Разработка методов моделирования для оценки

производительности суперкомпьютерных систем для параллельных приложений с однородным характером поведения

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание учёной степени кандидата технических наук

16 МАЙ 2013

Москва 2013

005058795

Работа выполнена в лаборатории суперкомпьютерных технологий для биомедицины, фармакологии и малоразмерных структур Московского физико-технического института (государственного университета).

Научные руководители доктор

технических

наук

Пентковский В.М.

доктор технических наук, профессор Плоткин А.Л.

Официальные оппоненты: доктор технических наук, профессор Топорков В.В.

кандидат технических наук Добров А.Д.

Ведущая организация:

Институт точной механики и вычислительной техники имени С.А. Лебедева РАН

Залцита состоится 2013 года в часов на заседа-

нии диссертационного совета Д 409.009.01 при ОАО «Институт электронных управляющих машин им. И.С. Брука» по адресу 119334, г. Москва, ул. Вавилова, д. 24, ОАО «ИНЭУМ им. И.С. Брука».

С диссертацией можно ознакомиться в библиотеке ОАО «ИНЭУМ им. И.С. Брука».

Автореферат разослан «¿Л» 2013 г.

Учёный секретарь

диссертационного совета

кандидат технических наук, профессор

Красовский В.Е.

Общая характеристика работы

Актуальность работы

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

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

Цель исследования

Целыо диссертационной работы является разработка теоретических оснований, практическая реализация, апробация и оценка симуляционного1 подхода для изучения производительности параллельных и распределённых приложений. Класс изучаемых приложений был ограничен, характеризовался однородностью проявляемого ими параллелизма и рассматривался на примере двух прикладных задач молекулярной динамики.

Научная новизна работы

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

1То есть основанного на имитационном компьютерном моделировании.

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

Результаты, выносимые на защиту

1) Практическая реализация программного комплекса для распределённой симуляции больших вычислительных систем, содержащих тысячи моделируемых ядер. При этом достигнутое на практике отношение суммарного числа моделируемых ядер к числу используемых физических ядер хозяйской системы достигло десяти. Замедление симуляции относительно реальности составляло от 100 до 1000.

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

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

Практическая ценность

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

Личный вклад автора

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

Работы были выполнены в составе группы симуляции архитектур лаборатории суперкомпьютерных технологий для биомедицины, фармакологии и малоразмерных структур факультета радиотехники и киберне-

тики Московского физико-технического института, на аппаратуре вычислительного кластера лаборатории.

Апробация

Результаты работы докладывались на следующих конференциях:

1) International Conference on Computational Science 2012, г. Омаха, шт. Небраска, США [5].

2) Международная конференция «Научный сервис в сети Интернет» в 2011 и 2012 гг., г. Новороссийск [1, 10].

3) «Разработка ПО 2011» CEE-SECR 2011 г., г. Москва [2]

4) Научная конференция МФТИ в 2010, 2011, 2012 гг., г. Москва, г. Долгопрудный [3, 4, 6, 11, 14].

Публикации

По теме диссертации опубликовано пять работ, из них три — в журналах, входящих в список ВАК.

Структура и объём работы

Диссертация состоит из четырёх глав и списка литературы. Общий объём работы 162 страницы.

Содержание работы

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

Симулятор (англ. simulator) — программа, моделирующая некоторую физическую систему через предоставление корректных интерфейсов входящих в неё подсистем и обеспечивающая правильное их функционирование, но не гарантирующая того, что их внутреннее устройство будет похоже на устройство аналогичных подсистем реальной ЭВМ. В частности, длительности отдельных операций, задержки доставки данных и т.п. в модели и реальной системе не обязаны совпадать.

Хозяин (англ. host) — физическая система, на которой исполняется

программа-эмулятор. Гость (англ. guest) — система, поведение которой должен демонстрировать симулятор и внутри которой исполняются гостевые приложения. Синонимичным является понятие «целевая система» (англ. target system).

Полноплатформенный симулятор (англ. full platform simulator) —

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

Функциональная модель (англ. functional model) — система, точность которой ограничена корректной функциональностью модели без обеспечения правильных значений длительностей сё операций. Например, в такой модели доступ к оперативной памяти возвращает правильное значение, но за один моделируемый такт времени, тогда как в реальности он занял бы от 3 до 200 тактов, в зависимости от состояния системы кэшей. Подобные модели недостаточно точны для предсказания производительности, но, как правило, достаточны для корректной работы большинства ПО, включая операционные системы.

Потактовая модель (англ. cycle precise model, performance model) — симулятор, корректно высчитывающий ход времени внутри моделируемой системы. Для этого он моделирует её внутреннее устройство более детально, чем это необходимо для функциональных моделей. Потактовые модели почти всегда во много раз медленнее функциональных.

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

ступного оборудования.

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

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

Теоретическим основанием для самой возможности моделирования ЭВМ является тезис Чёрча-Тьюринга: любая интуитивно вычислимая функция является частично вычислимой, или, иными словами, может быть вычислена некоторой машиной Тьюринга.

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

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

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

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

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

• Фиксированный размер обрабатываемых данных после выхода на рабочий режим.

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

• Приложения исполняются только на центральных процессорах, для которых в наличии имеются высокопроизводительные программные модели, и не используют ускорители и сопроцессорные платы.

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

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

Модель кэша В начале главы даётся описание созданной модели иерархии памяти, подключаемой к Simics. Оригинальный кэш Simics, представленный классом g-cache, не подходил для нужд этой работы по ряду причин:

1) g-cache предназначен для исследования систем с одним или двумя уровнями кэшей, тогда как существующие системы процессоров Intel имеют три уровня;

2) моделируются только SMP-системы с постоянной задержкой для всех доступов в память, реальные серверные и кластерные узлы имеют неоднородную организацию памяти (англ. NUMA);

3) обеспечивается поддержание когерентности памяти только с помощью общей тпггттм по протоколу MESI, тогда как в современных системах отдельные процессоры соединены с помощью линий QPI, сообщение по которым организовано иначе -— используется протокол MESIF.

Для обхода этих недостатков на основе исходного кода g-cache автором были созданы новые классы моделей: h-cache для моделирования кэшей и qpi- st aller для моделирования неоднородности памяти. Все уровни кэшей (L1-L3) моделировались как устройства класса h-cache. Модель кэшей поддерживала протокол MESIF, учитывающий возможность наличия данных в ЬЗ-кэше другого сокета, конфигурируемые длительности различных событий (промахи чтения, промахи записи, промахи с получением данных из кэша другого сокета и т.п.), политику вытеснения LRU. Модель неоднородной памяти qpi-staller позволяла задать диапазон физических адресов общей памяти, локальный для данного сокета; для него она возвращала одно значение задержки доступа, для всех остальных адресов, считавшихся дальними — второе, большее значение. Кроме того, она перенаправляла запросы о наличии данных в кэше при промахах в иерархию соседнего сокета.

Так как учёт работы иерархии памяти существенно замедляет симуляцию, эти модели подключались только в момент запуска исследуемых приложений и «прогревались» в течение 200 симулируемых секунд. Параметры конфигурации каждого уровня иерархии даны в табл. 1, организация соединений между ними соответствовала спецификациями физической системы изображена на рис. 1.

Таблица 1

Параметры системы кэшей модели

Величина Значение, тактов

Задержка промах Ы (чтение) 3

Задержка промах Ы (запись) 3

Задержка промах Ь2 (чтение) 12

Задержка промах Ь2 (запись) 10

Задержка промах ЬЗ (чт./зап.) 35

Задержка ЮЮБЛ (ближняя) 100

Задержка ББШ (дальняя) 220

Сбор трассы сетевых коммуникаций Инструмент mpi-tracer был создан под руководством автора для исследования влияния коммуникаций, осуществляемых по стандарту MPI, на производительность программ. Собираемая с его помощью история (трасса) всех вызовов MPI процедур, связанных с коммуникациями, позволяет определить характерные для конкретного приложения типы взаимодействия (наример, парные или коллективные) с их длительностями, увидеть характерные фазы в поведении

Сокет 1

Ядро 1 .... Ядро 16

♦ 4

i -

♦ t *

- i L2

»

1 - 1

qpi-staller

Сокет 2

Ядро 1 Ядро 16

♦ ♦ »

т ï

♦ ♦ »

f ... - !

i 4

1 - 1

qpi-staller

Физическая память

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

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

mpi-tracer состоит из профилирующей библиотеки, подключаемой к исследуемой программе, и модуля для Simics. Библиотека переопределяет процедуры MPI для перехвата обращения к ним. Для этого используется «магическая» инструкция моделируемого процессора1, но влияющая на исполнение программы, но вызывающая в симуляторе исполнение определённой пользователем функции (рис. 2). Она позволяет передавать ограниченный объём информации в симулятор. Инструмент mpi-tracer сохраняет порядковый номер, код возврата и аргументы функции, а также номер процесса (MPI rank). Эти данные позволяют определить, какие процессы взалмодейстовали и какой алгоритм они использовали, сколько данных было переслано каждым процессом и сколько времени для этого понадобилось.

Далее созданная трасса используется для вычисления среднего времени, проводимого каждым потоком приложения внутри обработки вызова MPI.

В архитектуре iDtel для этого выбрана CPUID.

Приложение! [проф. библиотека! 1 MPI библ. 1 I Simics I mpi-tracer I

I —Т^— I I I

I I 1 I

Магическая инструкция

Core Magicjnstruction (hapT ~_

"1

I I I I

[III ill ii

Рис. 2 Последовательность вызовов нри исполнении магической инструкции

Получение метрик производительности приложений Далее в главе приводится описание разработанной методики для определения производительности. Определения двух изучаемых метрик приложений:

• число завершившихся машинных инструкций за один такт процессора — IPC (англ. instructions per cycle); обратная ей величина — CPI (англ. cycles per instruction);

• число совершённых операций над числами с плавающей точкой за одну секунду — FLOPS (англ. floating point operations per second).

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

где

CPI — CPIcore + CP loaches + CPImemory + С PI mpi,

CP ïcaches = CPIL1 + CPIL2 + CPIL3.

(1)

(2)

В (1) CPIœre — количество тактов, затрачиваемых на исполнение непосредственно в ядре процессора, CPIcaches — суммарные задержки при обращениях в кэш-память, CPImerrtory — задержки при доступе в оперативную память, CPImpi — коммуникации с помощью интерфейса MPI.

Все члены, кроме СР1соге, могут быть раскрыты как математическое ожидание соответствующего набора событий для каждой из моделей:

CPlLk = P{cacheLh} ■ L?*hebk, где ке{ 1,2,3}, (3)

CP Imemory = £ Р{тегщ} ■ , (4)

CPImpi = £ P{MPIi} ■ Lfpl. (5)

Здесь P{cacheLki} — вероятность г-го типа события для кэша уровня к, таких как попадания и промахи при чтении и записи; bficheLk — длительности обработки событий в кэшах; P{mem,i} — вероятность i-ro типа обращения к памяти (дальней или локальной), L™crn — соответствующая им задержка; P{MPIï\ — вероятность вызова i-ой функции библиотеки MPI, LfPI — длительность передачи данных соответствующей функцией.

Нахождение С Piaars методами симуляции затруднено, так как требует наличия потактовой модели, учитывающей все особенности конвейерной обработки инструкций, знаний о деталях микроархитектуры исследуемого ЦПУ и т.п. Кроме того, такие модели обладают крайне низкой скоростью работы, и их использование усугубило бы проблему с большим временем симуляции больших систем. По этой причине эта величина вычислялась из значений архитектурных счётчиков, встроенных в процессоры Intel, с помощью Intel VTune.

Для получения значения FLOPS из CPI необходимо учесть, что не все инструкции выполняют собственно вычисления над числами с плавающей запятой, а также что современные векторные инструкции способны выполнять операции над двумя (в случае SSE) или четырьмя (для AVX) парами операндов. Вводится коэффициент а, показывающий, сколько операций с плавающей точкой приходится на одну инструкцию, значение FLOPS получается из следующего соотношения:

FLOPS-1 = G Picore/а + CPhaches + CPImemory 4- CPImpi. (6)

Проведённый в работе анализ данных, полученных с помощью VTune, позволил обнаружить следующий факт: для исследуемых приложений для измерения СР1соГе с удовлетворительной точностью достаточно рассматривать только самый «горячий» их участок, при этом в нём содержится наибольшее количество инструкций над значениями с плавающей точкой (векторных команд SSE/AVX), необходимых для вычисления а.

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

Организация распределённой симуляции Модели исследуемых систем содержали в себе большое число ядер — до тысяч — и требовали для работы сотни гигабайт памяти. Современные одиночные компьютеры не в состоянии удовлетворить этим условиям, поэтому необходимым являлось рассредоточение частей модели по многим хозяйским системам. Оригинальный Simics поддерживает распределение симуляции на несколько хозяйских систем, однако с увеличением их количества задача координирования и управления их работой сильно усложняется; кроме того, часть узлов хозяйского кластера обычно занята другими пользователями, непрерывно занимающими и освобождающими ресурсы. По этой причине в работе автором реализована интеграция запуска Simics с системой управления ресурсами кластерных систем SLURM (Simple Linux Resource Manager). Она реализована в виде скрипта simics-slurm, принимающего все обычные опции Simics, но дополнительно выполняющего следующие шаги.

1) Запросить у SLURM число узлов, достаточное для старта симуляции. Если они недоступны немедленно, то встать в очередь ожидания вместе с задачами других пользователей.

2) При успешном получении ресурсов от SLURM в переменной окружения SLURM_NODELIST хранится список выданных в данном сеансе узлов. На первом их них с помощью команды SSH запускается первая копия Simics, содержащая в себе модель master-узла. Этот шаг необходимо выполнять, чтобы освободить головной узел физического кластера, т.к. он используется многими пользователями и не рассчитан на вычислительно интенсивные задачи.

3) Дополнительные процессы Simics стартуют на оставшихся выданных узлах с помощью команды SSH. Каждый из них открывает новое соединение, используемое для нужд координации симуляции, с центральным процессом (рис. 3) и создаёт подгруппу гостевых slave-систем, которые будут исполняться параллельно.

4) После сигнализации готовности всех процессов Simics выдаётся глобальная команда начать симуляцию.

5) Последующие шаги определяются переданным simics-slurm файлом сценария, написанном на Python или языке скриптов Simics.

Использование такой схемы проведения отдельных экспериментов позволило автоматизировать процесс сбора данных для различных конфи-

SSH

gH

Головной узел

Вычислительный л Simics 1

-^—

[ Simics ] vT -- [ Simics ]

Вычислительный у »л В ы числ ите льмый узел

Вычислительны! узел

Вычислительный узея

В ычис л ите л ьный у »ел

Вычислительный узел

L

J

Занятые другими пользователями Рис. 3 Процесс распределения частей модели при использовании БИТОМ

гураций симулятора и при этом эффективно утилизировать возможности Simics и ресурсы хозяйской системы.

Общая последовательность проведения исследования изображена на рис. 4. Для получения части компонент задействованы модели кэшей, памяти и сети, построенные на основе фреймворка симулятора Wind River Simics. Для измерения CPIccrre, точное моделирование которого в условиях рассматриваемой задачи затруднено, используется Intel VTune. Смысл входящих в схему обозначений раскрываются в следующей главе.

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

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

Два приложения, моделирование которых проводилось в работе:

• Gromacs — пакет молекулярной динамики для моделирования ле-

Приложение

-О-

Эксперимент \ZTune

С

Вычисление СР1

вычисление а

=Q| Модель системы |

-CL

Эксперимент 51т1сБ

=D=_

Отчёт VTune | Моделирование кэшей, памяти Трасса MPI-вызовов |

-CL -CL

Вычисление CPI , CPI

Ctrh е memory

С

-CL

Вычисление СР/„

СР1

-CL

z>

Вычисление КОР?) Рис. 4 Общая последовательность исследования

Таблица 2

Конфигурации Geni и Gen2

Параметр Geni Gen2

Год ввода в эксплуа- 2011 2012

тацию

Число выч. узлов 16 112

Число процессоров в 2 2

одном выч. узле

Число ядер в одном 12 16

процессоре

Тип процессора Intel Xeon Х5680 Intel Xeon CPU E5-

(Westmere) 2690 (Sandy Bridge)

Частота процессоров 3,33 ГГц 2,9 ГГц

ОЗУ одного узла 24 Гбайт 48 Гбайт

Сеть Infmiband QDR 10 Infiniband QDR 10

Гбит/с Гбит/с

Полное число ядер в 384 3584

системе

карственных средств, использовалась версия 4.5.4, собранная с поддержкой MPI и двойной точностью;

• Amber — ещё один набор приложений для молекулярной динамики, использовалась версия Amber 11, собранная с поддержкой MPI,

Масштабируемость и скорость симуляции Главным фактором, жёстко ограничивающим максимальное число моделируемых машин, которое было возможно запустить на одном хозяйском узле, являлось потребление памяти гостевыми системами. Каждой копии ОС для устойчивой работы при симуляции требовалось около 1,5 Гбайт, что при объёме хозяйского ОЗУ 24 Гбайт создавало ограничение в 16 систем на узел. Однако, на практике их число было ограничено 12 по числу хозяйских ядер Geni для того, чтобы все потоки симулятора имели возможность исполняться параллельно.

Simcis имеет встроенный механизм systen-perfmeter для измерения скорости симуляции, что позволяет оценить замедление приложений по сравнению с их прямым исполнением на реальной аппаратуре. В таблице 3 приведены результаты измерения скорости симуляции Gromacs для экспериментов с 64 моделируемыми узлами и аналогичные данные для Amber, исполнявшегося на 16 моделируемых узлах, для одного процесса Simics в различных фазах экспериментов.

Таблица 3

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

Фаза Длительность, сим. с Скорость Gromacs, MIPS Скорость Amber, MIPS Комментарий

Загрузка ОС «200 4900 5500 Аппаратно ускоренная симуляция

Моделирование кэшей 200+200 52 61 Подключены иерархии кэшей и памяти с предварительным «прогревом» модели

Сбор трасс MPI 200 154 142 Подключен mpi.-tra.cer

Применение mpi-tracer На рис. 5 приведены зависимости относительных частот вызовов для различных функций MPI. связанных с точечными и коллективными взаимодействиями, от числа моделируемых узлов кластера, для приложения Gromacs, собранные с помощью mpi-tracer.

0.5 0.45 0.4 0.35 0.3 0.25 0.2 0.15

0Л -0.05 0

и .tuas. !

et-и

N = 2 N = 4 N = 6

N = 10 ZZ2Z3 N = 12 tW-VJ N = 16 rzzzn

N = 20 I-1

N = 32 gSAAI N = 48 ES228 N = 64 иашгав

Mm_

S %

N>0 N.

•л

MPI функция

Рис. 5 Профиль относительной частоты вызовов MPI для Gromacs в различных конфигурациях

Независимость CPIcore,CPIcaches от числа потоков На рис. 6 приводится сравнение точности метода нахождения СР1соге с помощью VTune — зависимость величины от числа процессов MPI для Gromacs для двух задач моделирования веществ. Сравниваются значения, полученные двумя способами: с помощью непосредственных замеров на аппаратуре и с помощью моделирования на Simics.

1,4- CPI ' 1.4- -... ______________

1,2- 1,2 ■ ■—в. -—е---■-zzz^s

-»-Актагардин экспериментальные значения -В- Лактицим экспериментальные

U.0 значения

-^-Актагардин модельные значения -❖-Лактицин модельные значения

о4_-,-,-,-,- . --—г—1 0-1-i-i-------'-1-г

о < е 12 16 го 2ч о я а 12 1& го гл

Количество MPI-задан Количество МРкгадач

Рис. 6 Сравнение модельного и измеренного СР1со ге для Сготасв Для первой симуляции (вещество актагардин) средняя погрешность мо-

дельного значения составила 8%, для второй (вещество лактицин) — 6%. Модельные результаты всех измерений оказались завышенными по сравнению с реальными. Скорее всего, это вызвано излишне пессимистичной оценкой производительности подсистемы кэшей, заложенной в модель.

Сравнение вычисленной и экспериментальной производительностей приложений На рис. 7 показаны зависимости величины FLOPS от числа узлов для обоих приложений (каждый узел содержал 16 процессов), а также значения их экспериментально измеренной производительности для аналогичных конфигураций для тех точек, для которых удалось провести измерения на реальной аппаратуре.

число узлов

Рис. 7 Зависимости предсказанной и измеренной производительности от числа узлов

Следует отметить, что в процессе выполнения работы было обнаружено, что Amber имеет ограничение на максимальное количество потоков, равное 256, что отражено в графике рис. 7, тогда как Gromacs лишён подобного недостатка.

Выводы по результатам диссертации

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

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

Следует отметить, что достигнутая в работе скорость симуляции сравнима с опубликованными для подобных исследований результатами. Однако представленное в работе решение ориентировано на системы архитектуры Intel, тогда как описанные в литературе параллельные симуля-торы в основном нацелены на менее распространённые системы или не ставят перед собой задач исследования производительности.

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

При выполнении диссертации были получены следующие основные результаты:

• Получены теоретические обоснования применимости разрабатываемого метода к различным классам прикладных приложений и выбран класс задач, на котором будет сфокусирована работа.

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

• Разработан инструмент mpi-tracer, предназначенный для исследования влияния коммуникаций MPI на производительность параллельных программ.

• Выработана теоретическая база и создана методика для определения производительности приложений через анализ встроенных в микропроцессоры Intel счётчиков производительности и инструмента Intel VTane Analyzer.

• Отдельные созданные компоненты объединены в единый комплекс на основе Wind River Simics, который был использован для симуляции приложений молекулярной динамики.

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

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

Публикации по теме диссертации

1. Моделирование и исследование архитектуры многопроцессорной системы с использованием распределённой моделирующей среды Graphite / Г.С. Речистов, A.A. Иванов, П.Л. Шишпор, В.М. Пент-ковский // Труды международной суперкомпьютерной конференции и конференции молодых учёных «Научный сервис в сети Интернет. Экзафлопсное будущее». — 2011. — 143-146. — ISBN: 978-5211-06229-0. — URL: http://agora.guru.ru/abrau2011.

2. Моделирование компьютерного кластера на распределённом симу-ляторе. Верификация моделей вычислительных узлов и сети кластера. / Г.С. Речистов, A.A. Иванов, П.Л. Шишпор, В.М. Пент-ковский // Труды конференции «Разработка ПО 2011» CEE-SECR 2011. — 2011. —URL: http://2011.secr.ru/lang/ru-ru/talks/ modeling-of-a-computer-cluster-on-a-distributed-simulator.

3. Опыт подготовки студентов в учебно-исследовательской лаборатории МФТИ-«Интел» / Речистов Г.С. [и др.] // Труды МФТИ. т. 3. — 2011. — С. 168-170.

4. Симуляционный подход для нахождения производительности параллельных MPI-приложений на вычислительном кластере / Г.С. Речистов, A.A. Иванов, П.Л. Шишпор, В.М. Пентковский // Труды 54-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе». Т. 01. — Москва-Долгопрудный-Жуковский, 2011. — 82-83. — ISBN: 978-5-7417-0396-0.

5. Simulation and Performance Study of Large Scale Computer Cluster Configuration: Combined Multi-level Approach / G.S. Rechistov, A.A. Ivanov, P.L. Shishpor, V.M. Pentkovski // Procedía Computer Science. — 2012. — T. 9. — C. 774-783. — ISSN: 1877-0509. — DOi: 10.1016/j . procs. 2012.04.083. — URL: http : //www. sciencedirect. com/science/article/pii/S1877050912002049 ; Proceedings of the International Conference on Computational Science, ICCS 2012.

6. Анализ производительности системы при выполнении программы Gromacs / H.H. Щелкунов, Д.А. Гаврилов, Г.С. Речистов, A.A. Аб-духаликов // Труды 55-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе». Т. 01. — Москва-Долгопрудный-Жуковский, 2012. — С. 14-15. — ISBN: 978-5-74170481-3.

7. Изучение производительности приложений на вычислительных кластерах с помощью компьютерного моделирования. Методология и руководство к применению / Речистов Г.С. [и др.]. — Спутник-}-, 2012. — ISBN: 978-5-7417-0469-1.

8. Моделирование компьютерного кластера на распределённом симу-ляторе. Верификация моделей вычислительных узлов и сети кластера / Г.С. Речистов, A.A. Иванов, П.Л. Шишпор, В.М. Пентков-ский // Программная инженерия. — 2012. — № 6. — С. 24-29. — ISSN: 2220-3397. — URL: http://novtex.ru/pi.html.

9. Основы программного моделирования ЭВМ. Учебное пособие / Речистов Г.С. [и др.]. — Издательство МФТИ, дек. 2012. — ISBN: 978-57417-0469-1. — URL: http://iscalare.mipt.ru/materials/course_ materials (дата обр. 10.12.2012).

10. Речистов Г. С. О верхних и нижних границах оценок производительности многомашинных многопроцессорных комплексов па научных приложениях // Труды международной суперкомпьютерной конференции и конференции молодых учёных «Научный сервис в сети Интернет. Поиск новых решений». — Издательство МГУ, 2012. — С. 671-675. — ISBN: 978-5-211-06394-5. — URL: http : / / agora . guru . ru/display . php?conf =abrau2012&page=item011 (дата обр. 26.12.2012).

11. Юлюгин E.A., Речистое Г.С., Иванов A.A. Моделирование нагрузки на сетевое оборудование // Труды 55-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе». Т.

Ol. — Москва-Долгопрудный-Жуковский, 2012. — С. 81-82. — ISBN: 978-5-7417-0481-3.

12. Реализация инструментария для исследования сетевой производительности MPI-приложений на распределённом симуляторе / Н.С. Поливанов, Г.С. Речистов, A.A. Абдухаликов, В.М. Пентковский // Информационные технологии. — 2013. — Янв. — № 1. — С. 46-50.

13. Речистов Г. С. Использование полноплатформенного имитационного моделирования суперкомпьютерной системы для определения производительности счётных приложений // Информационные технологии. — 2013. — Map. — X* 3. — С. 29-32.

14. Речистов Г.С. Венчмарк UNPACK для архитектуры Intel IA-32: существующие варианты, сравнительный анализ возможностей и демонстрируемой производительности // Труды 54-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе». Т. 01. — 71-72. — ISBN: 978-5-7417-0396-0.

Подписано в печать:

17.04.2013

Заказ № 8367 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Министерство образования и науки Российской Федерации Московский физико-технический институт (государственный университет)

На правах рукописи

04201356667

Речистов Григорий Сергеевич

Разработка методов моделирования для оценки производительности суперкомпьютерных систем для параллельных приложений с однородным характером поведения

05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

Диссертация на соискание учёной степени кандидата технических наук

Научные руководители

д.т.н.

Пентковский Владимир Мстиславович

д.т.н., проф. Плоткин Арнольд Леонидович

Москва 2013 год

Оглавление

1. Обзор технологий моделирования и изучения производительности 4

1.1. Цель диссертационной работы..............................5

1.2. Научная новизна ............................................6

1.3. Практическая ценность......................................6

1.4. Апробация....................................................6

1.5. Публикации ..................................................7

1.6. Содержание работы..........................................7

1.7. Обзор существующих подходов............................8

1.8. Обзор аналитических моделей параллельных программ 13

1.9. Симуляторы ЭВМ............................................16

1.10. Метрики производительности..............................18

1.11. Постановка задачи исследования..........................19

2. Теоретические обоснования 21

2.1. Классический критерий виртуализуемости ..............21

2.2. Ограничения применимости критерия виртуализуемости 26

2.3. Статус поддержки в современных архитектурах .... 34

2.4. Практические аспекты возможности эффективной симуляции ........................................................38

2.5. Вывод о применимости симуляции........................47

3. Компоненты модели 49

3.1. Моделирование кэшей ......................................49

3.2. Реализация модели кэшей и памяти......................67

3.3. Просмотр работы в реальном времени....................70

3.4. Анализ MPI..................................................71

3.5. Анализ составляющих CPI..................................82

3.6. Анализ с помощью Intel VTune............................84

3.7. Учёт влияния технологии Intel HyperThreading.....105

3.8. Распределённая модель...................109

4. Результаты и их внедрение 115

4.1. Последовательность проведения исследований приложений .............................115

4.2. Gromacs............................118

4.3. Amber.............................122

4.4. Масштабируемость и скорость симуляции........124

4.5. Однородность исследуемых приложений.........126

4.6. Анализ MPI.........................126

4.7. Анализ приложений с учётом HyperThreading .....128

4.8. Результаты измерения FLOPS...............134

4.9. Заключение..........................135

Литература 139

Приложение 156

1. Обзор технологий

моделирования и изучения производительности

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

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

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

1.1. Цель диссертационной работы

Целью диссертационной работы является разработка теоретических оснований, практическая реализация и апробация симуляционного1 подхода для изучения функциональности, поведения и производительности параллельных распределённых приложений. Класс изучаемых программ был ограничен, характеризовался однородностью проявляемого ими параллелизма и рассматривался на примере двух прикладных задач молекулярной динамики.

Для достижения поставленной цели в работе выполняются следующие этапы.

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

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

• Реализация комплекса для распределённой симуляции кластерных систем.

• Проведение исследования масштабируемости и производительности построенного симулятора, а также прикладных приложений.

хТо есть основанного на имитационном компьютерном моделировании.

1.2. Научная новизна

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

1.3. Практическая ценность

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

1.4. Апробация

Результаты работы докладывались на следующих конференциях и представлены в соответствующих сборниках трудов.

1) International Conference on Computational Science 2012, г. Омаха, шт. Небраска, США [73].

2) Международная конференция «Научный сервис в сети Интернет» в 2011 и 2012 гг., г. Новороссийск [100, 108].

3) «Разработка ПО 2011» CEE-SECR 2011 г., г. Москва [101]

4) Научная конференция МФТИ в 2010, 2011, 2012 гг., г. Москва, г. Долгопрудный [96, 103, 106, 109, 110].

1.5. Публикации

По теме диссертации опубликовано пять работ [98, 102, 104, 105, 107], из них три — в журналах, входящих в список ВАК.

1.6. Содержание работы

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

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

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

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

1.7. Обзор существующих подходов изучения программ

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

1.7.1. Применение моделирования ЭВМ

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

• Большое число составляющих систему устройств со сложными взаимосвязями, как явными, так и скрытыми или паразитными (возникающими помимо воли проектировщика).

• Необходимость сохранения обратной совместимости с уже существующим оборудованием, дополнительно усложняющая дизайн.

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

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

По этим причинам широко используется подход, когда разработка нового устройства сопровождается созданием его компьютерных моделей, способных с некоторой точностью проявлять себя так, как работает реальное устройство. Это становится возможным благодаря применению методики борьбы со сложностью — модульностью подсистем и их абстракцией от остального мира. Устройства, входящие в состав ЭВМ, соединяются между собой через строго определённые интерфейсы, специфицирующие лишь то, что будет передаваться через них, но не определяющие, что будет с противоположной стороны от них. Свойство это очень полезно. В частности, оно позволяет оборудованию различных производителей быть совместимым друг с другом без необходимости раскрытия внутренней документации конкурентам. Также это позволяет подставлять вместо реальных устройств их модели. Более того, по разные стороны интерфейсов мы можем размещать модели различных подсистем, таким образом строя полную модель всей ЭВМ, компоненты которой «не знают», что за границей интерфейса находится не реальное устройство, а лишь его модель.

Перечислим лишь некоторые практические способы применения программных моделей.

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

2) Написание сопутствующего аппаратуре ПО. Наличие функционирующей модели устройства позволяет использовать её для разработки драйверов, прошивок (таких как BIOS и UEFI [19]) и даже операционных систем и компиляторов параллельно с разработкой самого устройства. В наше время нередка ситуация, когда драйвера для нового оборудования готовы и отлаже-

ны ещё до официальной доступности предназначенного для них оборудования.

3) Построение и исследование экспериментальных аппаратных решений. Моделирование позволяет быстрее и дешевле изучать «пространство проектирования» {англ. design space) для определения параметров, при которых устройство или система будут иметь наилучшие характеристики. Для исследователей интерес часто представляют количественные характеристики новых систем, такие как скорость работы, степень загруженности подсистем, потребление и выделение энергии, и т.п. Иногда подобный анализ можно провести и без симуляции, используя аналитические методики, теорию массового обслуживания, экстраполяцию измерений на существующей аппаратуре и т.д. Однако моделирование даёт наибольшую гибкость.

4) Исследование качественных свойств, т.е. работает или нет новая технология в принципе, безотносительно её скоростных характеристик. В этом случае альтернатив симуляции практически не остаётся, поскольку необходимо изучить функционирование системы.

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

1.7.2. Терминология

Эмулятор — программа, моделирующая некоторую физическую систему путём имитации процессов, происходящих внутри подсистем аппаратуры.

Симулятор — программа, моделирующая некоторую физическую систему через предоставление корректных интерфейсов входящих в

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

Хозяин (англ. host) — физическая система, на которой исполняется программа-симулятор.

Гость (англ. guest) — система, поведение которой имитирует симу-лятор и внутри которой исполняются гостевые приложения. Синонимичным является понятие «целевая система» (англ. target system).

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

Полноплатформенный симулятор (англ. full platform simulator) —

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

Симулятор режима приложения (англ. application mode simulator)

— эмулятор, предназначенный для запуска «обычных» прикладных

приложений (т.е. не операционных систем, BIOS и другого системного ПО). Такие гостевые программы полагают присутствие определённой операционной системы, и потому симулятор обязан эмулировать необходимые системные вызовы для того, чтобы создать окружение, неотличимое от предоставляемого операционной системой. При этом модель получается жёстко привязанной к конкретному варианту системного ПО, так как список и формат системных вызовов и прочих интерфейсов приложений может заметно меняться между ОС (например, Windows и Linux) и даже внутри одной ОС между её версиями (например Linux 2.4 и Linux 2.6). Как правило, количество моделируемого периферийного аппаратного обеспечения при симуляции режима приложения минимально.

Функциональная модель {англ. functional model) — симулятор, точность которого ограничена корректным выполнением алгоритмов модели без обеспечения правильных значений длительностей отдельных операций. Например, в такой модели доступ к оперативной памяти возвращает правильное содержимое, но за один моделируемый такт времени, тогда как в реальности он занял бы от 3 до 200 тактов в зависимости от состояния системы кэшей. Подобные модели недостаточно точны для предсказания величин производительности, но, как правило, достаточны для корректной работы большинства ПО, включая операционные системы.

Потактовая модель (англ. cycle precise model, performance model) —

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

Гибридная модель — система, частично реализованная в программе, а частично — на специализированном оборудовании (например, на ПЛИС). Применяется в тех случаях, когда чисто программное решение недостаточно быстро.

1.8. Обзор аналитических моделей параллельных программ

Обзор большинства существующих высокоуровневых моделей, используемых для описания работы параллельных приложений, можно найти в работах [42, 48].

• Описание топологии сети, соединяющей отдельные вычислительные узлы, и процесса коммуникаций между узлами, исполняющими последовательные куски программы [31]. Данный класс моделей является низкоуровневым, требует учёта деталей аппаратной реализации, маскирующих непосредственный алгоритм работы изучаемого приложения. По этой причине были созданы модели, абстрагирующиеся от коммуникаций и вводящие некоторые упрощения на шаблоны поведения программы или диктующие мета-алгоритм её исполнения.

• PRAM (англ. parallel random access memory) [25] вводит упрощаю�