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

00553*«»«-

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

Корж Антон Александрович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ ДОСТИЖЕНИЯ ВЫСОКОЙ СТЕПЕНИ МАСШТАБИРУЕМОСТИ СУПЕРКОМПЬЮТЕРНЫХ ПРИЛОЖЕНИЙ

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

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

1 г СЕН 2Щ

Москва-2013

005532866

Работа выполнена в лаборатории параллельных информационных технологий Научно-исследовательского вычислительного центра Московского государственного университета имени М.В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

чл.-корр. РАН, профессор Воеводин Владимир Валентинович

Официальные оппоненты: доктор физико-математических наук,

Лацис Алексей Оттович, ИПМ им. М.В. Келдыша РАН, заведующий сектором

кандидат технических наук, Аладышев Олег Сергеевич, Межведомственный суперкомпьютерный центр РАН, заведующий отделом

Ведущая организация: Вычислительный центр

им. А. А. Дородницына РАН

Защита состоится 4 октября 2013 года в 15 часов 00 минут на заседании диссертационного совета Д 501.002.09 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, г. Москва, Ленинские горы, д.1, стр. 4, НИВЦ МГУ, конференц-зал.

С диссертацией можно ознакомиться в Научной библиотеке МГУ имени М.В. Ломоносова (Ломоносовский проспект, 27).

Автореферат разослан^'-? августа 2013 года.

Учёный секретарь диссертационного совета ............Суворов В.В.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание и результаты работы соответствуют паспорту специальности 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-и научных публикациях [118], из них 10 в журналах из списка ВАК.

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

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

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

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

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

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

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

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

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

В разделе 2.1 проведена оценка баланса между пропускной способностью канала, соединяющего адаптер среды коммутации и процессорный элемент, и канала самой среды коммутации для различных топологий [9]. Для разных задач с разным коммуникационным шаблоном данные каналы будут задействоваться в разной степени, поэтому для получения соотношений был введено понятие коммуникационного диаметра задачи Н. Коммуникационный диаметр приложения Н определяется, как среднее расстояние, которое должны пройти пакеты, генерируемые данным приложением, положенным на заданную топологию коммутационной среды. Единицей измерения является число хопов, которое нужно преодолеть, прежде чем пакет будет доставлен до узла назначения. Минимальным и максимальными значениями в данном случае будет единица и максимальный диаметр сети. В приложениях класса 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 [8,12].

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

О -——........—'——»--—1—1— 1 1 1 1 1 '

О 500 10D0 1500 2000 2500 3000 3500 4000 4500 5000 5500 6000 6500 7000 7500 8000 8500 9000 9500 10000 10500 11000

Число уялов

Тор АхА ——Тор АхАхА -■—Тор АхАхАхА -----Тор АхАхАхАхА

-с--'Top АХ2АХ2А —о—Сочъ Коли Ах2Ах2А -о— Сеть К,ЛИ Ах2Ах2Ах2А Сеть Клоеа (64 портв)

Рис.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 pe, int isjequest), где hndl - это номер обработчика активного сообщения, предварительно зарегистрированный с помощью функции shmem registerjiandler. При этом также гарантируется выполнения всех обработчиков на удаленном узле после следующего вызова shmemj>arrier_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.

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

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

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

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

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

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

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

0.001 0.005 0.01

К:временная 0.05 локальность

0.1

0.5

1

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 L: пространственная локальность

а 6-8 □ 4-6

0 2-4 В 0-2

Рис.2 Отношение APEX-DISLIB к APEX-MPI для 128 узлов BlueGene/P

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

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

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

sum = 1; *nvisited = 0;

shmem barrier all ();

while ( sum ! = 0 ) { *nvisited += sum; for(i =0; i < qc; i++) for(j = g->rowsts[ql[i]]; j<g->rowsts[ql[i]+1]; j++) send vertex( getcolumn(g->column, j), ql[i]) ; shmem barrier all ();

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

shmem long allsum(Ssum);

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

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

Заключение

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

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

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

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

Выводы и рекомендации.

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

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

Публикации в журналах из перечня ВАК

1. Турсин Д.Ф., Корж А.А Применение Infmiband в инфраструктуре хранения данных // Вестник компьютерных и информационных технологий 2013, №5, С. 3-7

2. Корж О.В., Андреев Д.Ю., Корж A.A., Коробков C.B., Чернявский А.Ю. Моделирование работы идеального квантового компьютера на суперкомпьютере Ломоносов // Вычислительные методы и программирование, 2013, т. 14, С. 24-34

3. Корж A.A. Мифология суперкомпьютинга // Открытые системы. 2011, №7, С. 44-45

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

14

31-42

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

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

7. Dzhosan O.V., Popova N.N., Korzh А.А. Hierarchical Visualisation System for High Performance Computing // Advances in Parallel Computing, 2010, № 19, P. 177-184

8. Корж A.A., Макагон Д.В., Бородин A.A., Жабин И.А., Куштанов Е.Р., Сыромятников Е.Л., Черемушкина Е.В. Отечественная коммуникационная сеть ЗБ-тор с поддержкой глобально адресуемой памяти // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 2010. № 35 (211). С. 41-53.

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

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

Публикации в других научных изданиях:

11. Корж А.А. Масштабирование Data-Intensive приложений с помощью библиотеки DISLIB на суперкомпьютерах Blue Gene/P и "Ломоносов" // Труды конференции "Научный сервис в сети Интернет-2011"., 2011, С. 126-131.

12.Корж А.А., Макагон Д.В., Бородин А.А., Жабин И.А., Куштанов Е.Р., Сыромятников Е.Л., Черемушкина Е.В. Отечественная коммуникационная сеть ЗБ-тор с поддержкой глобально адресуемой памяти для суперкомпьютеров транспетафлопсного уровня производительности // Параллельные вычислительные технологии (ПаВТ'2010): Труды международной научной конференции (Уфа, 29 марта — 2 апреля 2010 г.): 2010, С. 227—237

13.Korzh A.A., Dzhosan O.V. Scaling the Unscalable: NPB UA Benchmark Scaling to Thousands of Blue Gene /Р Cores Using PGASlike OpenMP Extention // Proc. Conf. ISC2010, Germany, Hamburg, 2010, P. 34

14. Korzh A.A., Dzhosan O.V. Early Evaluation of NPB UA Benchmark Scaling

to Thousands of Blue Gene /Р Cores Using PGASlike OpenMP Extention // Proc. Conf. Information Systems & GRID Technologies Fourth International Conférence, Sofia, Bulgaria, 2010 P. 58-69

15. Dzhosan O.V., Popova N.N., Korzh A.A. Hierarchical Visualization System for High Performance Computing // proc. conf. ParCo 2009, France, Lyon, 2009, P. 79-88

16. Корж A.A. Распараллеливание задачи умножения разреженной матрицы на вектор на вычислительных кластерах с минимальной аппаратной поддержкой PGAS // Параллельные вычислительные технологии (ПаВТ 2009): Труды международной научной конференции (Нижний Новгород, 30 марта — 3 апреля)., 2009. - С. 813.

17. Корж А .А. Исследование производительности многоядерных процессоров на тестах с нерегулярным доступом к памяти // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: Труды Всероссийской суперкомпьютерной конференции (21-26 сентября 2009г., г. Новороссийск), 2009, С. 168-172

18. Корж А.А. Распараллеливание метода ветвей и границ в модели вычислений Message-driven // Научный сервис в сети Интернет: технологии распределённых вычислений: Труды Всероссийской суперкомпьютерной конференции (19-24 сентября 2005г., г. Новороссийск)., 2005, С. 244-246

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано в печать 26.08.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 256. Тел./факс: 8 (495) 939-3890, 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к.

Московский государственный университет имени М.В. Ломоносова Научно-исследовательский вычислительный центр

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

Корж Антон Александрович

04201361033

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ ДОСТИЖЕНИЯ ВЫСОКОЙ СТЕПЕНИ МАСШТАБИРУЕМОСТИ СУПЕРКОМПЬЮТЕРНЫХ ПРИЛОЖЕНИЙ

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

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук Воеводин Владимир Валентинович

Москва 2013

Содержание

Содержание..........................................................................................................2

Введение...............................................................................................................4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Intensive...............................................................................................................95

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

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

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

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

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

Заключение.......................................................................................................133

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

Введение

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

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

В современных высокопроизводительных системах применяется принцип параллельной обработки данных на тысячах вычислительных узлов. Каждый такой узел содержит несколько процессоров с локальной памятью. Для обмена информацией и синхронизации работы узлы соединяются между собой коммуникационной сетью. Для решения многих современных задач требуется не только большая производительность суперкомпьютеров на арифметико-логических операциях, но и возможность эффективной работы с памятью большого объема, оцениваемой в десятки и сотни терабайт. Память такого объема обычно представляет собой десятки тысяч модулей, доступных через коммуникационную сеть. При больших объемах обрабатываемой информации для производительности суперкомпьютера становится крайне важна не только скорость вычислительных устройств, но и пропускная способность памяти, которая в свою очередь для систем с распределенной общей памятью (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 приведен разработанный метод высокоскоростной инжекции пакетов в сеть. Основная идея этого метода заключается в оптимизации использования узкого места - шины инжекции пакетов в сетевой а�