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

• Корж, Антон Александрович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Корж, Антон Александрович

Содержание

Содержание

Введение

Глава 1. Обзор существующих коммуникационных сред

1.1 Коммуникационные среды фирмы Cray

1.2 Система BlueGene фирмы IBM

1.3 Сети семейства InfiniBand

1.4 Базовые понятия и принципы маршрутизации

1.5 Проблема выбора и использования модели программирования

1.6 Выводы по главе

Глава 2. Исследования и разработка методов построения масштабируемых

—систем коммутацииТ^^...Т.Т^7.Т..~^^ТТТТ77.~".Т^

2.1 Зависимость производительности суперкомпьютера от агрегатной пропускной способности коммуникационной сети

2.2 Высокоскоростной метод инжекции пакетов в коммуникационную среду процессором со стандартной архитектурой

2.3 Параметризованная архитектура маршрутизатора с топологией kD-тор

2.4 Параллельная имитационная модель коммутационной среды

2.5 Результаты моделирования коммуникационной сети

2.6 Выводы по главе

Глава 3. Система программирования для разработки масштабируемых суперкомпьютерных приложений

3.1 Модель программирования SHMEM с абстракцией общей памяти

3.2 Расширенная библиотека DISLIB

3.3 Реализация DISLIB для суперкомпьютеров IBM Blue Gene /Р и для кластеров с сетью Infiniband с агрегацией сообщений

3.4 Выводы по главе

Глава 4. Экспериментальное исследование применения Б18ЫВ для достижения высокой степени масштабируемости приложений класса

Intensive

4.1 Описание используемых программно-аппаратных сред

4.2 Сравнение моделей программирования на тесте АРЕХ-МАР

4.3. Масштабирование бенчмарка NPB UA на тысячи ядер с помощью DISLIB

4.4 Распараллеливание бенчмарка Graph500 с помощью библиотеки DISLIB

4.5 Выводы по главе

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Разработка и исследование методов достижения высокой степени масштабируемости суперкомпьютерных приложений»

Введение

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

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

В современных высокопроизводительных системах применяется принцип параллельной обработки данных на тысячах вычислительных узлов. Каждый такой узел содержит несколько процессоров с локальной памятью. Для обмена информацией и синхронизации работы узлы соединяются между собой коммуникационной сетью. Для решения многих современных задач требуется не только большая производительность суперкомпьютеров на арифметико-логических операциях, но и возможность эффективной работы с памятью большого объема, оцениваемой в десятки и сотни терабайт. Память такого объема обычно представляет собой десятки тысяч модулей, доступных через коммуникационную сеть. При больших объемах обрабатываемой информации для производительности суперкомпьютера становится крайне важна не только скорость вычислительных устройств, но и пропускная способность памяти, которая в свою очередь для систем с распределенной общей памятью (DSM) зависит от пропускной способности сети. В настоящее время самым мощным суперкомпьютером в России является суперкомпьютер «Ломоносов», имеющий пиковую производительность более 1.7 петафлопс. «Ломоносов» имеет в своем составе более 52 тысяч ядер х86 и более 480 тысяч ядер GPU. Производительность ведущих мировых суперкомпьютеров составляет десятки петафлопс. Для эффективного использования такого количества ядер требуется написание программ с высокой степенью масштабируемости. [3,4,10]

Суперкомпьютерные приложения, работающие на многих тысячах узлов разделяются на два класса: вычислительно интенсивные и коммуникационно интенсивные (Data-Intensive или DIS-класс). В настоящее время все больший интерес начинают привлекать приложения второго класса, которые часто относят к области высокопроизводительных вычислений, называемой Big Data. В приложениях первого класса накладные расходы на коммуникации ничтожно малы по сравнению с временем вычислений, в связи с чем, такие задачи достаточно хорошо масштабируются на современных суперкомпьютерах. При выполнении приложений класса Data-Intensive, накладные расходы на коммуникации составляют значительную часть общего времени работы задачи, мешая — достижению -высокой—степени масштабируемости таких- приложений—В связи с этим рассмотрение проблем достижения высокой степени масштабируемости задач класса Data-Intensive является актуальным [2,16,18].

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

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

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

Цель и задачи диссертации

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

1. Исследовать влияние коммутационной среды суперкомпьютера на степень масштабируемости приложений.

2. Исследовать подходы к созданию и разработать средства параллельного программирования для достижения высокой степени масштабируемости суперкомпьютерных приложений класса Data-Intensive на современных вычислительных комплексах.

3. Провести исследования эффективности разработанных программных средств на приложениях класса Data-Intensive.

Положения, выносимые на защиту

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

неулучшаемость полученной оценки показана эмпирически.

2. Разработана и реализована на вычислительных комплексах IBM BlueGene/P и суперкомпьютер «Ломоносов» система параллельного программирования DISLIB, являющаяся расширением модели параллельного программирования с абстракцией общей памяти, существенно повышающая степень масштабируемости приложений. Доказаны свойства бездедлоковости для предложенной реализации системы программирования DISLIB.

3. Разработанная система программирования DISLIB успешно прошла апробацию на параметрическом тесте АРЕХ-МАР, на известных бенчмарках Graph500 и NASA Parallel Benchmark Unstructured Adaptive. Были показаны высокие степени масштабируемости (8 тысяч ядер IBM BlueGene/P и 32 тысяч ядер суперкомпьютера «Ломоносов») и высокая продуктивность параллельного программирования в разработанной модели DISLIB.

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

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

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

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

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

Практическая значимость результатов работы

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

Разработанные средства параллельного программирования могут быть использованы для эффективного распараллеливания приложений в различных областях: для задач обработки графов, для расчетов на нерегулярных и адаптивных сетках. В настоящее время реализованная система доступна и используется прикладными пользователями СК «Ломоносов». Пользователи, успешно применяющие эти библиотеки в своих прикладных задачах, сообщают о повышении продуктивности и о достижении хороших уровней масштабируемости своих приложений на тысячах и более ядрах суперкомпьютера «Ломоносов» [9].

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

Разработанный метод высокоскоростной инжекции пакетов в сеть реализован в макетах коммуникационной сети, изготовленных ОАО «НИЦЭВТ», которые используются пользователями для решения прикладных задач.

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

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

Соответствие диссертации паспорту научной специальности

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

Апробация работы и публикации

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

• 25-я, 26-я Международные конференции International Supercomputing 2010, 2011 (ISC), Германия, Гамбург, 2010, 2011

•23-я Международная конференция Supercomputing 2011, Graph500 BoF, США, Сиэттл 2011

• 27-я Международная конференция по параллельным вычислениям РагСо 2009, Франция, Лион, 2009

• 3-я и 4-я Международные конференции «Параллельные вычислительные технологии» (ПАВТ 2009 и 2010), Россия, Н. Новгород 2009, Уфа 2010 •7-я, 10-я, 11-я, 12-я и 13-я Всероссийские суперкомпьютерные конференции серии «Научный сервис в сети Интернет», Россия, Новороссийск, 2005, 2008, 2009, 2010, 2011;

• Семинар ОАО "НИЦЭВТ" под руководством Л.К.Эйсымонта

• Семинар parallel.ru под руководством В.В.Воеводина

Основные результаты работы изложены в 18-и научных публикациях [1-18], из них 10 в журналах из списка ВАК.

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

Во Введении приведено обоснование актуальности данной работы и

ее научной новизны. Сформулированы цели и задачи диссертации.

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

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

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

В заключении приводятся выводы по главе.

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

суперкомпьютерных приложений.

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

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

Теорема. Для коммутационных сред с топологией kD-тор при равномерно случайном траффике пропускная способность инжекции в каждый маршрутизатор будет ограничена 8*L/k, где L — пропускная способность межроутерного канала, а к — длина максимального измерения тора.

На практике это означает, сторона тора, равная 8, обеспечивает равномерную загрузку межроутерных и инжекционных каналов.

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

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

накладные расходы на синхронизацию моделируемых объектов и увеличить быстродействие и масштабируемость модели.

В разделе 2.3 приведен разработанный метод высокоскоростной инжекции пакетов в сеть. Основная идея этого метода заключается в оптимизации использования узкого места - шины инжекции пакетов в сетевой адаптер PCI-express. Сети, такие как RDMA Infiniband, для посылки одного пакета требуют нескольких (обычно от 2х до 4х) транзакций по шине. Методы передачи данных, такие как PUT with immediate или метод передачи, используемый в сети EXTOLL, требуют одной транзакции на передачу одного небольшого пакета. Предлагаемый в работе метод требует всего лишь четверть транзакции для передачи одного пакета. Достигается это использованием режима записи write-combining и использованием при записи кольцевого буфера, в который последовательно записываются команды содержащие тип операции, адрес и сами данные переменного размера. Таким образом обеспечивается аппаратная агрегация нескольких небольших записей в одну транзакцию PCI-Express (64 байта). В результате на аппаратной реализации МЗ на ПЛИС удалось достигнуть скорости инжекции в 32 миллиона пакетов в секунду с одного процесса против известных ранее 3-4 миллионов для сети Infiniband. Платой за повышенную пропускную способность является задержка "последнего" пакета. Данный недостаток преодолевается выдачей инструкции sfence, которая сбрасывает все аппаратные write-буферы процессора, включая буферы write-combining.

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

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

Третья глава посвящена описанию разработанной в рамках данной работы модели параллельного программирования DISLIB. При разработке за основу была взята описанная в разделе 3.1 модель программирования SHMEM, разработанная еще в 1993 году для машины Cray ТЗЕ. Основными характеристиками модели программирования с абстракцией общей памяти SHMEM являются: стиль программирования SPMD (одна программа и множество данных), использование модели односторонних коммуникаций (PUT и GET), использование глобальных барьеров для разделения фаз коммуникаций и вычислений.

В разделе 3.2 приведены ключевые особенности расширения DISLIB: 1) наличие расширенных операций PUT (односторонние активные сообщения), 2) наличие расширенных операций GET (двухсторонние активные сообщения). Как будет показано в главе 4, эти особенности позволяют значительно повысить продуктивность программирования на ряде задач, относящихся к классу Data-Intensive.

Расширенные операции PUT в модели программирования DISLIB выполняются с помощью функции shmem_send(int hndl,void * data, int size, int ре, int is_request), где hndl - это номер обработчика активного сообщения, предварительно зарегистрированный с помощью функции shmem_register_handler. При этом также гарантируется выполнения всех обработчиков на удаленном узле после следующего вызова shmem_barrier_all. Кроме того, не гарантируется порядок выполнения обработчиков, однако, в отличие от операций PUT, гарантируется атомарность выполнения обработчиков. Прототип функции обработчика следующий: void handler (void *data, int size, int from).

Расширенная операция GET является двухсторонним аналогом расширенной операции PUT. На практике для удобства пользователя ему позволяется вызывать из обработчиков функцию shmem_send и отвечать на активный GET посылкой активного PUT. Пользователь в данном случае не ограничен в глубине вложенности операций GET, однако разработанная реализация гарантирует отсутствие дедлоков только для вложенности не более 1. Это объясняется использованием двух виртуальных каналов и коммуникаторов для запросов (расширенных GET) и ответов (расширенных PUT).

Особенностями реализаций библиотеки DISLIB, описанными в разделе 3.3, являются: 1) эффективная и прозрачная реализация агрегации сообщений, как операций PUT, так и операций GET, 2) многоступенчатая реализация передачи сообщений в многоядерных системах.

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

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

Приведено описание алгоритма эффективной программной агрегации сообщений. Ключевой частью алгоритма является выполнение барьерной синхронизации shmemjbarrier_all. Разработанный алгоритм выполнения барьерной синхронизации использует функцию неблокируемого барьера (введенную в стандарт MPI-3, но доступную и ранее через библиотеку libNBC или GASNET). При этом алгоритм предлагает отправку

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

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

Алгоритм барьерной синхронизации выглядит следующим образом: 1) отправка всех неотправленных буферов агрегации; 2) ожидание подтверждения доставки всех отправленных буферов агрегации, во время которого мы принимаем пришедшие пакеты и посылаем на них подтверждения; 3) после получения всех подтверждений выполняем первую фазу неблокирующего синхронизационного барьера (notify); 4) пока не получено уведомление о выполнении фазы 2 неблокирующего барьера (wait), продолжаем принимать сообщения и отправлять подтверждения.

Преимущества разработанного алгоритма следующие: 1) гарантирует доставку и исполнение на удаленных узлах всех сообщений отправленных до барьера; 2) в случае нулевого количества коммуникаций до барьера, сам барьер работает со скоростью синхронизационного барьера и не влечет дополнительных накладных расходов; 3) в случае отправки любого числа сообщений также не добавляет значительных накладных расходов. Доказана следующая теорема о корректности и бездедлоковости предложенных алгоритмов.

Теорема. При использовании как односторонних активных сообщений PUT, так и двухсторонних расширенных операций GET

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

В разделе 3.4 приводятся выводы по главе.

В четвертой главе приводятся результаты экспериментов с разработанными реализациями модели программирования DISLIB.

В разделе 4.1 описывается архитектура и устройство используемых для экспериментов вычислительных комплексов.

В разделе 4.2 описывается сравнение моделей программирования на тесте АРЕХ-МАР. Сравнивается оригинальная программа АРЕХ-МАР, написанная Erich Strohmaier et al. в модели программирования MPI, и версия, реализованная в рамках данной работы в модели программирования SHMEM с использованием библиотеки DISLIB для суперкомпьютера BlueGene/P. Мы видим, что ускорение DISLIB относительно MPI достигает 8 раз для небольших сообщений.

В разделе 4.3 описывается бенчмарк NASA NPB UA (Unstructured Adaptive), который был написан в NASA для оценки работы высокопроизводительных систем на задачах с нерегулярным доступом в память. Из-за высокой сложности авторы смогли реализовать этот бенчмарк только для систем с общей памятью (ОрепМР). Версия, использующая MPI, написана так и не была, хотя это было заявлено в планах. В рамках данной работы код NPB UA (около 8000 строк кода без комментариев в 15 файлах на фортране 77) был отредактирован таким образом, что ОрепМР версия была превращена в DISLIB+OpenMP версию. Результаты, полученные для классов С (33 тысяч элементов сетки, 1720 Mop/s, см Рис. 1а) и D (515 тысяч элементов сетки, 4910 Mop/s), масштабируются на суперкомпьютерах BlueGene/P и «Ломоносов» до нескольких тысяч ядер, при этом абсолютные результаты в 22.4 раза превосходят все ранее известные результаты для этого бенчмарка (219 Mop/s).

В разделе 4.4 описывается имплементация бенчмарка Graph500 Kernel 1: поиск вширь с помощью библиотеки DISLIB. Текст основного цикла программы занимает не более 10 строк кода (см. Листинг 1), в то время как референсная версия на MPI-1 и MPI-2 занимает более сотни строк кода. При этом DISLIB-версия показывает масштабируемость вплоть до 32 тысяч ядер суперкомпьютера «Ломоносов» (Рис.1 в) (и 8192 ядер суперкомпьютера IBM BlueGene/P (Рис. 16)). Полученные результаты позволили суперкомпьютеру Ломоносов занять 1-е место по производительности (3-е итоговое) во 2-й редакции списка Graph500 (июнь 2011) и 3-е место (по производительности и итоговое) в 3-й редакции списка Graph500 (ноябрь 2011).

В заключении сформулированы основные результаты работы.

—Ломоносов DISLIB IBM BlueGeneG/P DISLIB Altix 3700 OpenMP ^^-AlUx UV OpenMP -O IBM BlueGene/P SHMEM

/

у

2 4 в 16 32 Ы 128 ги 512 1024 2046 4066 8182

часло «д»р

■тело »иж с к Помояесо*

б) в)

Рис.1 а) Сравнение DISLIB,SHMEM и ОрепМР версий на суперкомпьютерах IBM BlueGene/P и Ломоносов для задачи NPB UA class С; б) Масштабирование Graph500 версий DISLIB и MPI-1 на суперкомпьютере IBM BlueGene/P; в) Масштабирование Graph500 версий DISLIB и MPI-1 на суперкомпьютере Ломоносов

Листинг 1. Ядро бенчмарка Graph500 в модели DISLIB

sum = 1; *nvisited = 0; shmembarrier allQ; while(sum != 0) { *nvisited += sum; for(i = 0; i < qc; i++)

for(j = g->rowsts[ql[i]]; j<g->rowsts[ql[i]+l]; j++) send vertexj getcolumn(g->column, j), ql[i]); shmem barrier allQ;

qc=q2c;q2c=0;int *tmp=ql;ql=q2;q2=tmp; sum = qc;

shmem Ions allsum(&sum); }

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Корж, Антон Александрович

3.4 Выводы по главе

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

Описаны алгоритмы агрегации сообщений, а также, дополнительной маршрутизации для многоядерных систем, снижающей потребление памяти буферами агрегации, использованные при реализации библиотеки DISLIB на суперкомпьютерах IBM BlueGene/P и Ломоносов.

Доказано две теоремы о бездедлоковости представленной реализации. Получено следствие о необходимом условии эффективности агрегации сообщений.

Глава 4. Экспериментальное исследование применения DISLIB для достижения высокой степени масштабируемости приложений класса Data-Intensive.

4.1 Описание используемых программно-аппаратных сред

Для проведения экспериментов использовались суперкомпьютерные комплексы IBM BlueGene/P и CK Ломоносов установленные в МГУ им М.В. Ломоносова.

IBM BlueGene/P установленный в МГУ имеет 2048 узла, на каждом из которых имеется 4 ядра и 2 гигабайта оперативной памяти. Максимальный эксперимент использовал все 8192 ядра установленных в данном суперкомпьютере. Данные ядра имеют архитектуру PowerPC и частоту 850 Мгц.

Суперкомпьютер Ломоносов, установленный в МГУ имеет несколько типов вычислительных узлов. Узлы с ускорителями GPU (более 1000 шт.) в данной работе не использовались. Узлов с двумя процессорами со стандартной архитектурой х86 в CK Ломоносов имеется 5100 штук. Вычислительные узлы имеют от 8 до 12 ядер и от 12 до 48 гигабайт оперативной памяти. Для проведения экспериментов использовалось 4096 узлов с 8-ю ядрами и 12 гигабайтами оперативной памяти. Таким образом, максимально использовалось 32768 процессорных ядер с архитектурой х86 и частотой 2.93 Ггц.

4.2 Сравнение моделей программирования на тесте ЛРЕХ-МЛР

Преимущество SHMEM относительно MPI с точки зрения производительности сказывается особенно сильно в области задач работающих с небольшими блоками данных, хаотично разбросанными по 6-8

4-6 ■ 2-4

0-2

Blue Gene /Р, SHMEM/MPI г0,001 [о,005

0,01 к: temporal Г0,05 locality kl \0,5 И со •ч- со ю CNI О) 00 см о о 00 со

L:spatial locality

Рисунок 17. Отношение SHMEM версии АРЕХ-поверхности относительно MPI версии для 128 узлов IBM Blue Gene /Р в зависимости от параметров временной и пространственной локализации к и L.

4.3. Масштабирование бенчмарка NPB VA на тысячи ядер с помощью DISLIB

В главе рассмотрено распараллеливание бенчмарка Unstructured Adaptive из пакета NAS Parallel Benchmarks в парадигме PGAS, дополняющей парадигму ОрепМР, для машин с распределенной памятью. Рассматривается реализация данной парадигмы на суперкомпьютере IBM BlueGene /Р. Приводятся результаты исследования производительности рассмотренного бенчмарка. На 8192 ядрах системы BlueGene /Р, установленной в Московском Государственном Университете получены результаты, превосходящие ранее известные результаты для ОрепМР-версии на машинах с общей памятью.

Будущая серия машин Cray Baker, ожидаемая во втором квартале 2010 года, оставаясь в рамках традиционной МРР-архитектуры (десятки тысяч узлов, в каждом из которых по два процессора AMD Opteron, узлы соединены коммуникационной сетью с топологией 3D-TOp) будет иметь принципиально новую коммуникационную сеть с кодовым названием Gemini. Одним из существенных отличий Gemini от интерконнекта Seastar2+ машин серии Cray XT будет являться значительно более высокий темп передачи коротких сообщений (Message Rate) и аппаратная поддержка парадигмы PGAS — все это значит эффективную передачу десятков миллионов сообщений в секунду. Второй проект, также разрабатываемый в рамках военной программы DARPA HPCS, IBM PERCS, также будет использовать процессоры со стандартной суперскалярной архитектурой POWER7, соединенные между собой коммуникационной сетью с пропускной способностью 400 Гбит/с на узел. Среди новшеств также значится аппаратная поддержка парадигмы общей памяти PGAS. Это говорит о необходимости переходить к программированию в рамках парадигмы PGAS.

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

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

Вопрос стоит в том, на каких задачах использование парадигмы PGAS сможет дать значительные преимущества относительно используемых стандартных MPI/OpenMP. Предположительно такими задачами окажутся задачи имеющие нерегулярный шаблон доступа к данным, а именно: мелкую гранулярность обращений, низкую пространственную и временную локализацию обращений к памяти. В частности, расчеты на нерегулярных адаптивных сетках относятся к данному классу. По этой причине была выбрана модельная задача UA (Unstructured Adaptive) из известного пакета бенчмарков NASA - NAS Parallel Benchmark.

4.3.1 Описание бенчмарка UA из пакета NAS Parallel Benchmarks

Впервые бенчмарк NPB UA был добавлен лишь в версию 3.1 пакета

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

В бенчмарке решается задача Дирихле уравнения теплопереноса в трехмерной кубической области на нерегулярной декартовой сетке. Источник тепла представляет собой шар движущийся с постоянной скоростью. Самым существенным с точки зрения шаблона доступа к памяти является тот факт, что для решения применяется нерегулярная сетка, причем каждые несколько шагов происходит ее адаптация: на областях с большим градиентом температуры сетка измельчается, с малым — укрупняется. Для решения применяется спектральный метод конечных элементов (SEM) с применением метода конечных мортаров. Более подробно описание применяемого численного метода и его преимуществ можно прочесть у авторов бенчмарка в [35].

До сих пор существуют лишь две известные реализации данного бенчмарка — последовательная версия и ОрепМР-версия. MPI-версии, так никому и не удалось представить. В связи с этим, разработанная автором версия, которая может работать на суперкомпьютерах без аппаратной поддержки общей памяти может представлять существенный интерес. С другой стороны, бенчмарк представляет собой реальную программу на фортране 77, объем кода составляет почти 300 КБ. Поэтому, тот факт, что на распараллеливание было потрачено около трех недель, доказывает крайне высокую продуктивность программирования с помощью библиотеки DISLIB.

4.3.2 DISLIB реализация задачи NPB UA

С программистской точки зрения один временной шаг бенчмарка

NPB UA состоит из следующих этапов: 1) продвижение конвекционной части уравнения явным методом Рунге-Кутта 4-го порядка 2) продвижение диффузионной части уравнения 3) изменение сетки, если прошло заданное число шагов. Основным по трудоемкости является продвижение диффузионной части, так как оно включает решение систем линейных уравнений с помощью метода сопряженных градиентов с предобуславливанием. Например, на процессоре PowerPC 450, используемом в узле суперкомпьютера BlueGene /Р, время счета на последовательной версии на задаче класса С распределяется следующим образом:

Список литературы диссертационного исследования кандидат физико-математических наук Корж, Антон Александрович, 2013 год

Список литературы

1. Корж А.А. Результаты масштабирования бенчмарка NPB UA на тысячи ядер суперкомпьютера Blue Gene/P с помощью PGAS-расширения ОрепМР // Вычислительные методы и программирование, т. 11, 2010, С .31-42

2. Корж А.А. Распараллеливание задач с нерегулярным доступом к памяти с помощью расширенной библиотеки SHMEM+ на суперкомпьютерах BLUEGENE /Р и "Ломоносов" // Вычислительные методы и программирование, т. 11, 2010, С .123-129

3. Фролов А.С., Семенов А.С., Корж А.А., Эйсымонт Л.К. Программа создания перспективных суперкомпьютеров // Открытые системы, №9, 2007, С. 21-29

4. Корж А.А. Мифология суперкомпьютинга // Открытые системы. -№7, 2011, С. 25-27

5. Корж А.А., Макагон Д.В. Оценка минимальных требований к аппаратуре и топологии при построении высокоскоростных коммуникационных сетей для суперкомпьютеров с общей памятью // Вычислительные методы и программирование: новые вычислительные технологии, т.9, 2008, С.26-31

6. Корж А.А., Джосан О.В. Организация коммуникационной сети для транспетафлопсных суперкомпьютеров // Труды Института системного анализа Российской академии наук, т.32, №3, 2008, сс.267-274

7. Dzhosan O.V., Popova N.N., Korzh А.А. Hierarchical Visualisation System for High Performance Computing // Advances in Parallel Computing, Volume 19, 2010, IOS Press, pp.177- 184, ISBN 978-160750-529-7, DOI: 10.3233/978-1-60750-530-3-177

8. Корж A.A., Макагон Д.В., Бородин A.A., Жабин И.А., Куштанов Е.Р., Сыромятников Е.Л., Черемушкина Е.В. Отечественная

21. Коммуникационная сеть МВС-Экспресс http://www.kiam.ru/MVS/research/mvs_express.html

22.N. R. Adiga et al. BlueGene/L torus interconnection network. IBM J. Res & DEV., VOL. 49, NO. 2/3, March/May 2005, pp. 265-276.

23.Duato J., Yalamanchili S., Ni L. Interconnection networks: an engineering approach. Morgan Kaufmann Publishers, San Francisco, CA, 2003, 625 pp.

24.Корнеев B.B. Архитектура вычислительных систем с программируемой структурой. Новосибирск: Наука, 1985.

25.Р. R. Hafner. Large Cayley graphs and digraphs with small degree and diameter. University of Auckland, 1995.

26. Aaron Harwood. High Performance Interconnection Networks. July 2005.

27.N. R. Adiga et al. An overview of the BlueGene/L Supercomputer. Proceedings of ACM/IEEE Conference on Supercomputing (SC'2002), November, IBM and Lawrence Livermore National Lab., 2002, pp. 1-22.

28.William J. Dally. Performance analysis of k-ary n-cube interconnection networks. IEEE Transactions on Computers, Vol. 39, No. 6, June 1990.

29.V. Puente, C. Izuy, R. Beivide, J.A. Gregorio, F. Vallejo, J.M. Prellezo. The Adaptive Bubble Router. 2000, 27 pp.

30.Steven L. Scott, Gregory M. Thorson. The Cray T3E Network: Adaptive Routing in a High Performance 3D Torus. HOT Interconnects IV, Stanford University, August 15-16, 1996, 10 pp.

31. Axel Jantsch. Communication Performance in Network-on-Chips. Stockholm, 2004.

32.C. Katsinis, B. Nabet. A scalable interconnection network architecture for petaflops computing. Drexel Univ., 2002.

33. J. S. Turner, R. Melen. Multirate Clos Network. IEEEC Mag., 2003.

34. John Kim, William J. Dally, Microarchitecture of a High-Radix Router. Stanford Univ., 2004.

35.S. Scott, D. Abts, J. Kim, W. Dally, The BlackWidow High-Radix Clos Network. Stanford Univ., 2006.

36.Timothy M. Pinkston, Aurelio Bermudez, Jose Duato, Deadlock-free dynamic reconfiguration over InfiniBand networks. PAA Mag., 2004

37. US Department of Defense. High performance computing modernization program. DoD, 2002.

38. Yogesh A. Mehta. Low diameter regular graph as a network topology in direct and hybrid interconnection networks. Urbana, Illinois, 2003.

39.John Kim, William J. Dally, Dennis Abts. Adaptive routing in high-radix Clos network. Stanford Univ., Cray Inc., Nov. 2006.

40.F. Petrini et al. The Quadrics Network: high-performance clustering technology. IEEE Micro, vol. 22, no. 1, Jan.-Feb. 2002, pp. 46-57.

41.F. Petrini et al. QsNetll: Defining high-performance network design. IEEE Press, 2005.

42. K.T. Pedretti and T. Hudson. Developing custom firmware for the Red Storm SeaStar network interface. Proc. 47th Cray User Group Ann. Tech. Conf., Sandia Lab, 2005.

43.R. Brightwell et al. Implementation and performance of Portals 5.3 on the Cray XT3. Proc. 2005 IEEE Int'l Conf. Cluster Computing (Cluster 2005), IEEE Press, Sandia Lab, 2005.

44. R. Brightwell et al. SeaStar Interconnect: balanced bandwidth for scalable performance. IEEE Press, Sandia Lab, 2006.

45. Infiniband Architecture Specification Volume 1, Release 1.2 October 2004.

46. D. W. Doerfler. An analysis of the Pathscale Inc. InfiniBand host channel adapter, InfiniPath. Sandia Lab.

47.T. Dunigan, J. Vetter, J. White III, P. Worley, "Performance evaluation of the Cray XI distributed shared-memory architecture", Micro, IEEE Volume 25, Issue 1, Jan.-Feb. 2005, P. 30 - 40.

48.Dally, W. J., Labonte, F., Das, A., Hanrahan, P., Ahn, J., Gummaraju, J., Erez, M., Jayasena, N., Buck, I., Knight, T. J., and Kapasi, U. J. 2003. Merrimac: Supercomputing with Streams. In Proceedings of the 2003 ACM/IEEE Conference on Supercomputing (November 15 - 21, 2003). Conference on High Performance Networking and Computing. IEEE Computer Society, Washington, DC, P. 35.-45

49.Scott, S., Abts, D., Kim, J., and Dally, W. J. 2006. The BlackWidow HighRadix Clos Network. In Proceedings of the 33rd Annual international Symposium on Computer Architecture (June 17 - 21, 2006). International Conference on Computer Architecture. IEEE Computer Society, Washington, DC, 16-28.

50.M. Blumrich et al. Design and Analysis of the BlueGene/L Torus Interconnection Network. IBM Research Report, December 3, 2003, 9 pp._

51.S.L. Scott, G.M. Thorson, The Cray T3E Network: Adaptive Routing in High Performance 3D Torus. HOT Interconnects IV, Stanford University, August 15-16, 1996, P. 10-20

52.V. Puente, C. Izu, R. Beivide, J.A. Gregorio, F. Vallejo and J.M. Prellezo, The Adaptative Bubble Router, Journal of Parallel and Distributed Computing. Vol 61 - n° 9, September 2001. P.

53.Sterling T. Critical Factors and Directions for Petaflops-scale Supercomputers // Presentation on IFIP WG10.3 e-Seminar Series. California Institute of Technology, 2005. P. 2-47.

54.Scott S., Abts D., Kim J., Dally W.J. The BlackWidow High-Radix Clos Network // International Symposium on Computer Architecture (ISCA), Boston, MA, USA, June 2006. Proceedings. P. 16-28.

55.Kim J., Dally W.J., Towles B., Gupta A.K. Microarchitecture of a HighRadix Router // International Symposium on Computer Architecture (ISCA), Madison, WI, USA, June 2005. Proceedings. P. 420-431.

56.Clos C. A Study of Non-Blocking Switching Networks // The Bell System technical Journal. March 1953. 42, №2. P. 406^124.

57.Dally W.J. Performance Analysis of k-ary n-cube Interconnection Networks // IEEE Transactions on Computers, 1990. 39, №6. P. 775-785.