ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2013, № 5, с. 166-171
МИКРОПРОЦЕССОРЫ ^^^^^^^^^^ И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА
УДК 62-50
МАСШТАБИРУЕМАЯ МОДЕЛЬ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ДЛЯ ЗАДАЧ С ИНТЕНСИВНЫМ ВВОДОМ-ВЫВОДОМ
© 2013 г. Д. Ю. Андреев
Москва, ВЦ РАН Поступила в редакцию 07.05.13 г., после доработки 30.05.13 г.
Представлена модель организации вычислений на массивно-параллельных вычислительных системах для задач с преобладанием ввода-вывода. Модель построена на основе выделения паттернов ввода-вывода, перераспределения данных и обработки в задачах обработки данных. Предложена стратегия разделения ролей вычислительных узлов суперкомпьютера. Рассмотрены особенности реализации модели для систем с топологией жирное дерево и топологией трехмерный тор.
Б01: 10.7868/80002338813050028
Введение. Множество современных массивно-параллельных вычислительных систем (суперкомпьютеров) содержат тысячи вычислительных узлов. Вычислительные узлы объединены коммуникационной средой и имеют доступ к внешней системе хранения данных. Каждый вычислительный узел имеет собственное оперативное запоминающее устройство (вычислительная система с распределенной оперативной памятю). Данные из оперативной памяти одного вычислительного узла могут быть переданы через коммуникационную среду другому вычислительному узлу. Архитектурные особенности внешней системы хранения данных и коммуникационной среды влияют на время выполнения вычислительных приложений. Для многих прикладных задач узким местом является ввод-вывод больших объемов данных и передачи данных между вычислительными узлами.
Существует ряд средств и алгоритмов обработки данных, которые предполагают предварительное подготовку данных и независимую обработку [1], они используются на стандартных кластерных системах и не предназначены для современных суперкомпьютерных систем с тысячами процессоров. В данной работе предлагается новая модель вычислений на массивно-параллельной системе для задач обработки данных. Предложенная модель выделяет в процессе решения вычислительной задачи следующие шаблоны поведения: загрузка данных из внешней системы хранения в оперативную память вычислительных узлов, перераспределения данных между узлами вычислительной системы, выполнение вычислительной части алгоритма обработки данных, которые в дальнейшем имеуются паттернами поведения. На основе построенной модели предлагаются стратегии оптимизации работы такой модели на вычислительных системах Ломоносов [2] и Б1иеОепе/Р [3] суперкомпьютерного комплекса МГУ им. М.В. Ломоносова.
1. Терминология модели. Не существует единого принципа построения программ для массивно-параллельных вычислительных систем, который учитывает все множество архитектурных особенностей вычислительной системы. Важный этап обработки данных — ввод-вывод. Для современных вычислительных систем свойственна плохая масштабируемость задачи ввода-вывода. Достаточно малого числа одновременно читающих процессов для достижения максимальной производительности систем хранения данных (СХД). На скорость чтения и записи данных влияет локальность запросов к СХД [4], при случайном доступе скорость снижается. Для увеличения локальности запросов к системе применяется метод двухфазового ввода-вывода [5], при котором запросы к СХД предварительно упорядочиваются.
В предлагаемой модели выделяются несколько паттернов поведения программы, на каждый из которых влияет определенное подмножество архитектурных особенностей. Для описания паттернов поведения введем следующие абстрактные понятия: источник данных — совокупность данных, формата хранения во внешней системе хранения и процедуры чтения/записи; внутреннее представление данных — формат хранения данных в оперативной памяти массивно-парал-
лельной вычислительной системы; подпрограмма обработки данных — процедура обработки внутренних данных, результатом которой могут являться некоторые внутренние данные.
Источник данных включает процедуры чтения/записи данных. Как уже указывалось ранее, массивно-параллельные вычислительные системы позволяют получать доступ к внешнему хранилищу с каждого вычислительного узла одновременно. Подмножество вычислительных узлов, которые во время работы программы используют источник данных, будем называть узлы ввода-вывода или сокращенно узлы В/В.
Подпрограмма обработки данных является вычислительной частью программы. Подпрограмма исполняется на вычислительных узлах, в память которых предварительно загружены данные. Вычислительные узлы, которые используются для выполнения указанной подпрограммы обработки данных, будем называть узлы обработки данных (сокращенно узлы О/Д) указанной подпрограммы.
Для параллельной обработки загружаемые данные распределяются по оперативной памяти узлов О/Д. Будем говорить, что узлы О/Д содержат указанные внутренние данные или что внутренние данные расположены на узлах О/Д, если внутренние данные полностью содержатся в памяти узлов О/Д.
Вычислительную программу можно разделить на следующие паттерны поведения: загрузка/выгрузка данных из источника данных, перераспределение внутренних данных и выполнение подпрограммы. Рассмотрим примеры применения паттернов в задачах обработки.
Модели простой обработки:
1) программа загружает и обрабатывает данные;
2) программа в результате работы создает внутренние данные, которые выгружаются;
3) программа загружает новые данные, обрабатывает их и выводит полученные данные.
Модели с повторным использованием данных уровня:
1) программа загружает данные и обрабатывает их более чем один раз;
2) в результате работы более чем одной подпрограммы создаются внутренние данные, которые выгружаются;
3) программа загружает новые данные, они обрабатываются более чем один раз и создаются внутренние данные, которые в результате выводятся.
Модели с конвеерной обработкой данных:
1) программе необходимо обрабатывать последовательно загружаемые единицы данных с использованием одной или нескольких подпрограмм обработки;
2) во время работы программы одна или несколько подпрограмм вызываются последовательно некоторое количество раз, каждый запуск оканчивается выгрузкой данных.
2. Параметры модели. Системы планирования выполнения на современных массивно-параллельных вычислительных системах предполагают статическое задание количества узлов, на которых будет выполняться задача. В зависимости от используемого алгоритма подпрограммы обработки данных необходимо, чтобы данные располагались определенным образом в памяти перед началом выполнения обработки.Таким образом пользователем для каждой модели могут быть заданы такие параметры: N — количество вычислительных узлов задачи, F — распределение данных в памяти, которое задается отображением P ^ D(data), где P — множество процессоров, data — данные, которые обрабатывает программа, а D (data) — множество подмножеств данных. А также формат хранения данных DF, который используется в "источнике данных".
Вычислительная система состоит из множества вычислительных узлов и коммуникационной среды. Коммуникационная среда состоит из каналов связи и устройств коммутации: ^выч = (К,£выч, Евыч) — граф коммуникационной среды, V — множество вычислительных узлов суперкомпьютера, £выч — множество коммутационных устройств вычислительной системы, Eвыч — каналы связи суперкомпьютера, W : Евыч^ Ш — отношение, задающее пропускную способность каналов. Граф Свыч соответствует топологии коммуникационной среды. Наиболее часто используемые в современных системах топологии: жирное дерево, тор (часто трехмерный).
СХД доступна с каждого вычислительного узла через каналы связи, которые могут являться частью коммуникационной среды вычислительной системы или отдельно соединять вычислительные узлы с системой хранения. Граф Свыч = (V, ^С^ЕСвд) — граф коммуникационной среды доступа вычислительных узлов к СХД. Архитектура СХД представляет из себя сложную систему, но обычно пользовательскому приложению доступен стандартный интерфейс работы с файлами.
Скорость чтения/записи зависит от загруженности системы хранения, каналов связи и от особенностей формата хранения. Для каждого формата данных DF, или в терминах модели — источника данных, и для данной вычислительной системы существует отображение TDF:D (data) ^ t, которое задает время извлечения подмножества данных из хранилища без учета передачи через коммуникационную среду.
Вышеперечисленные параметры строго определены для каждого запуска задачи описанной моделью. Но на данном этапе не устанавливается, на каких именно узлах происходит выполнение, поскольку для модели не важен порядок выбранных узлов, однако на скорость выполнения передач данных влияют Свыч и ОСХд , в которых указаны конкретные графы коммуникаций. Также на время работы загрузки данных влияет не только выбор узлов, но и подмножество данных, которое загружается на конкретный узел, из-за указанных выше ОСХд и TDF.
Паттерн загрузки данных. Первый этап выполнения обработки данных — загрузка данных. Узлы В/В параллельно запрашивают подмножества данных, которые в результате будут переданы в локальную память узлов. СХД предоставляет доступ в виде стандартного интерфейса к файлам. Данные могут храниться в виде одного или нескольких файлов, каждый файл может хранить данные в каком-то специальном формате (таком, как текстовый, простой бинарный или особые — netCDF, HDF5). Свойства СХД и формат данных определяют, какая будет задержка при извлечении определенной порции данных.
Паттерн перераспределения данных. После того как данные загружены на узлы В/В, их необходимо передать на узлы О/Д. Другими словами нужно совершить переход от одного внутреннего представления данных (ВП) к другому, такую операцию будем называть перераспределение данных.
Задача перехода от ВП1 к ВП2 схожа с задачей организации потоков многих веществ к многим исходам со следующими передачами данных: пусть для Свыч последовательность взаимно непересекающихся подмножеств данных {d1;} описывает ВП1, а последовательность подмножества данных {d2;} описывает ВП2, тогда задача перераспределения состоит из следующих передач данных: для любых vt, от vt к пер
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.