Исследования › Гибридный реконфигурируемый вычислитель › Инженерная методика адаптации приложения к гибридному кластеру с ускорителями на ПЛИС.

Приложение 1. Коммуникационная библиотека VSDA.

П1.1. Мотивация и немного истории.

В «10 простых шагах к стройной прикладной программе» рассматривается модельное приложение – параллельная реализация сеточного аналога двумерной задачи Дирихле для уравнения Пуассона, для случая прямоугольной индексной сетки. Общее представление о технике параллельной реализации приводится в Шаге 4. Реализация базируется на следующих основных принципах:

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

Техника реализации параллельных программ на базе указанных принципов, конечно же, далеко не всеобъемлюща – существует масса полезных параллельных алгоритмов, которые в нее не укладываются. Однако, нельзя не отметить и того, что область применимости именно этой техники далеко не исчерпывается модельным приложением из «10 шагов». Точнее говоря, это модельное приложение было выбрано в качестве примера именно потому, что очень и очень многие реальные параллельные программы устроены в принципе точно так же, то есть могут быть естественным образом сформулированы в терминах блочно распределенных массивов с теневыми гранями. Среди потенциально гибридных программ, тяготеющих к простым структурам данных, вроде индексных четырехугольных или шестигранных сеток, процент таких приложений особенно велик.

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

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

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

В значительной степени именно на этих принципах построен, например, язык HPF (High Performance Fortran, Фортран высокой производительности). Сложность практического использования этого языка, в частности, в том, что указанные принципы в нем реализованы на слишком высоком уровне абстракции, что не дает программисту выйти за их рамки, использовать в дополнение к ним что-то еще.

Этого недостатка лишены системы, в которых указанные принципы реализованы не в виде специального языка, а в составе библиотеки. Наибольший интерес в этом качестве представляет хорошо известная библиотека PETSc. В ее составе даже есть функции для организации блочно распределенных массивов с теневыми гранями. Первоначально предполагалось рекомендовать для использования именно их. Не подвергая ни малейшему сомнению полезность и практическую пригодность библиотеки PETSc в целом, функции поддержки распределенных массивов с теневыми гранями из этой библиотеки все же пришлось забраковать. В PETSc эти возможности, с одной стороны, не очень удачно спроектированы, а с другой – реализованы как частный случай возможностей гораздо более сложных и общих, что привело к многократному снижению быстродействия по сравнению с непосредственной реализацией тех же обменов данными на MPI или shmem. К тому же, разработчики PETSc имеют болезненную склонность снова и снова менять пограммистский интерфейс этих возможностей, совершенно не заботясь о совместимости с прошлым, причем менять, по нашему мнению, как правило, не в лучшую сторону. Поэтому было решено начать реализацию собственной библиотеки работы с распределенными массивами, и реализовать, в качестве первого шага, блочно распределенные массивы с теневыми гранями. Библиотеку было решено строить на базе MPI, а внешний интерфейс ее сделать таким, чтобы ее можно было использовать совместно с PETSc, ScaLAPACK и любой другой построенной на базе MPI параллельной библиотекой. При этом не накладывается никаких ограничений на одновременное использование в той же программе MPI и/или shmem напрямую, если возможностей библиотек не хватит, или они окажутся оформленными неудобно для данной программы.

Описываемая ниже библиотека называется VSDA, что указывает на ее идейное родство (хотя и не очень близкое) с соответствующим набором функций одной из старых версий PETSc. Этот набор функций назывался SDA (Simple Distributed Arrays, Простые распределенные массивы). Соответственно, описываемая ниже библиотека – VSDA – это Very Simple Distributed Arrays, или Очень простые распределенные массивы.

П1.2. Модель программирования на базе коллективных операций.

Коммуникационная библиотека – это не столько набор конкретных имен функций и порядок передаваемых им аргументов, сколько набор выражаемых этими функциями понятий – коммуникационных примитивов. Чтобы использование библиотеки действительно облегчило жизнь программиста, примитивы должны быть достаточно высокоуровневыми, «более крупными», чем в базовых коммуникационных системах. Как конкретно могли бы выглядеть такие высокоуровневые коммуникационные примитивы? Будут ли они двусторонними, как «send» и «receive» в MPI, или односторонними, как «put» и «get» в shmem? В действительности, они не будут ни теми, ни другими. Заданию акта коммуникации по заранее подготовленному коммуникационному шаблону гораздо лучше соответствует модель коллективных операций, выполняемых логически одновременно всеми потенциально участвующими в акте коммуникации процессами. Слова «логически одновременно» здесь следует понимать в том же смысле, в каком «логически одновременно» выполняются соответствующие друг другу «send» и «receive» в MPI. Сама коллективность операции – уже элемент высокоуровневой логики: программист, не уточняя деталей, говорит, что в этом месте программы требуется обновить теневые грани некоторого распределенного массива, а библиотека уже самостоятельно, внутри себя, решает, какие именно обмены данными, и в каком именно порядке должен для этого выполнить тот или иной процесс. Иногда может оказаться, что вообще никакие, но программист об этом думать не обязан.

Основные действия, доступные программисту при использовании библиотеки VSDA, следующие:

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

Нетерпеливому читателю, уже готовому потребовать еще хотя бы 5 – 10 совершенно необходимых операций (в самом деле, как жить без операций редукции?) ответим сразу: скорее всего, в добавлении предлагаемых операций нет необходимости. Библиотека VSDA сознательно построена таким образом, чтобы с данными ее распределенных массивов удобно было работать непосредственно из MPI, shmem или любой другой библиотеки, базовой или высокоуровневой. В MPI, например, есть прекрасные коллективные операции редукции. Значит, в VSDA им просто не место.

П1.3. Описание библиотеки.

П1.3.1. Общие сведения.

Библиотека VSDA не «прикрывает» MPI полностью. Даже программист, который по существу использует только VSDA и ничего больше, вынужден знать о существовании MPI, чтобы напрямую вызвать, как минимум, MPI_Init(), MPI_Comm_size(), MPI_Comm_rank() и MPI_Finalize(). Также программист должен знать, что такое MPI – коммуникатор. При создании распределенного массива необходимо указать конкретный MPI – коммуникатор, который будет впредь использоваться для выполнения всех операций с этим массивом. Программист должен сам решить, будет ли этим коммуникатором MPI_COMM_WORLD, или же требуется создание специального коммуникатора (возможно, не одного), изолирующего внутренние коммуникации VSDA от других коммуникаций, используемых в программе. Проблема изоляции библиотечных коммуникаций в программах со сложной коммуникационной логикой известна давно, вовсе не специфична именно для библиотеки VSDA, и в настоящем документе особо не рассматривается. Если в Вашей программе имеются еще коммуникации, кроме внутренних коммуникаций VSDA, и Вы не уверены, надо ли их изолировать, то лучше перестраховаться. Создайте копию MPI_COMM_WORLD при помощи MPI_Comm_dup(), после чего указывайте эту копию при создании распределенных массивов.

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

Читатель, уже знакомый с параллельными библиотеками коллективных операций, без труда узнает в этом решении «традиционно-фортрановский» подход, принятый в ScaLAPACK. Противоположный, строго объектно-ориентированный, подход принят в PETSc. Правда, при реализации функций SDA, которые и послужили прототипом описываемой библиотеки, сами разработчики PETSc изменили себе и использовали подход ScaLAPACK.

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

Все длины, смещения и номера элементов во всех функциях VSDA имеют тип long. Тип int применяется только для признаков.

П1.3.2. Описание функций.

Для использования библиотеки VSDA программа должна включить соответствующий заголовочный файл:

#include “vsda.h”

Кроме того, к моменту первого обращения к какой-либо функции библиотеки должен быть инициализирован MPI, поскольку VSDA опирается на MPI.

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

void VSDA_Create( MPI_Comm comm, int sdatype, int globalshadows,
			long globsize, long elemsize, long shadowwidth,
			long *distribution_in, long *distribution_out, VSDA *vsda )

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

Смысл параметров функции следующий:

comm	—	коммуникатор, по процессам которого распределяется массив, и который будет впредь использоваться для всех обменов данными, генерируемыми внутри VSDA при работе с этим массивом. В простейшем случае это может быть MPI_COMM_WORLD. В реальных программах полезно бывает создать специальный коммуникатор для работы VSDA и пользоваться им для всех массивов, чтобы избежать перепутывания сообщений, циркулирующих внутри VSDA, с сообщениями, явно генерируемыми программой пользователя и/или другими библиотеками.
sdatype	—	тип распределенного массива. В настоящее время поддерживается единственный тип – VSDA_BLOCKED, что означает «массив, распределенный блочно, с теневыми гранями».
globalshadows	—	признак наличия «глобальных» теневых граней в нулевой и последней по счету локальных порциях. Если этот признак равен 1, то считается, что все локальные порции имеют одинаковую структуру, то есть у нулевой локальной порции есть никогда не участвующая в обменах «лишняя» теневая грань в начале локальной порции, а у последней по счету, соответственно, в конце. Если этот признак равен 0, то считается, что «лишних» теневых граней нет, и, тем самым, структура нулевой и последней по счету локальных порций отличается от структуры всех остальных.
globsize	—	общая длина массива в элементах, НЕ СЧИТАЯ ТЕНЕВЫЕ ГРАНИ.
elemsize	—	размер элемента в байтах. При распределении блоками любой массив считается одномерным, состоящим из элементов определенного размера, причем разбивать элемент на части, разрезая массив между процессами, запрещено. Например, если распределяется трехмерный массив размером [100][200][500] типа double, то, скорее всего, его globsize будет задан равным 100, а elemsize – 800000 (200*500*sizeof(double)). Элементом такого массива в терминах VSDA является слой размером 200 на 500.
shadowwidth	—	размер теневой грани в элементах.
distribution_in[]	—	входной массив, характеризующий распределение создаваемого массива по процессам. Если программист хочет, чтобы распределение построилось автоматически, в качестве этого параметра следует передать NULL. В противном случае следует передать массив типа long, в котором i-й элемент равен требуемому размеру локальной порции в i-м процессе. Размер задается в элементах (не в байтах), НЕ СЧИТАЯ ТЕНЕВЫЕ ГРАНИ.
distribution_out[]	—	выходной массив, характеризующий распределение создаваемого массива по процессам. Смысл его компонентов – тот же, что и у distribution_in[]. Независимо от того, был ли задан distribution_in[], в distribution_out[] будет размещена информация о получившемся в итоге распределении. Если эта информация не нужна, следует в качестве этого параметра передать NULL.
vsda	—	выходной параметр, дескриптор созданного распределенного массива. В качестве этого параметра следует передавать указатель на уже существующую переменную типа VSDA, в которую и будет помещен дескриптор созданного распределенного массива.

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

VSDA_Update_begin(  VSDA *vsda, void *rq, void *localportion )

Это полноценная коллективная операция, к этой функции должны «логически одновременно» (см. выше) обратиться все процессы коммуникатора, в котором был создан распределенный массив vsda.

Смысл параметров функции следующий:

vsda	—	дескриптор распределенного массива, полученный предшествующим обращением к VSDA_Create(),
rq[]	—	массив-жетон достаточной для данной операции длины,
localportion	—	указатель на локальный массив, который при данном обновлении значений теневых граней будет считаться локальной порцией данного распределенного массива в данном процессе. Локальная порция ВКЛЮЧАЕТ ТЕНЕВЫЕ ГРАНИ.

Замечание о массиве – жетоне. При запуске любой операции VSDA, подразумевающей коммуникации, необходимо предоставить массив, в котором библиотека формирует так называемый жетон – информацию о запущенных обменах данными. Впоследствии жетон используется для ожидания завершения запущенных обменов, после чего становится не нужен. Основное место внутри жетона занимает массив элементов типа MPI_Request, по одному элементу на каждый запущенный обмен. Поэтому в качестве жетона при обращении к VSDA_Update_begin() и подобным функциям удобно использовать массив элементов типа MPI_Request достаточной для данной функции длины. Для VSDA_Update_begin(), примененной к блочно распределенному массиву, достаточная длина равна 4.

Чтобы подождать завершения запущенной ранее коллективной операции, следует обратиться к функции:

VSDA_Update_end( void *rq )

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

Чтобы узнать диапазон номеров элементов распределенного массива, расположенных в данном процессе, следует обратиться к функции:

VSDA_Get_extent( VSDA *vsda, long *start, long *finish )

Смысл параметров функции следующий:

vsda	—	дескриптор распределенного массива, полученный предшествующим обращением к VSDA_Create(),
start	—	номер (в глобальной нумерации, от 0 до globsize-1) первого из элементов локальной порции данного процесса в распределенном массиве,
finish	—	значение, на 1 большее номера последнего из элементов.

ЭЛЕМЕНТЫ ТЕНЕВЫХ ГРАНЕЙ НЕ СЧИТАЮТСЯ.

Эта операция локальная, коммуникаций не выполняет.

Чтобы запустить копирование некоторого сплошного диапазона элементов из одного распределенного массива в другой, следует обратиться к функции:

VSDA_Copy(  VSDA *target, long targoffs, void *targarr, 
		 VSDA *source, long srcoffs, void *srcarr,
		 long count, void *rq )

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

Смысл параметров функции следующий:

target	—	дескриптор распределенного массива, в который производится копирование,
targoffs	—	глобальный номер элемента, начиная с которого размещать копируемую информацию,
targarr	—	локальная порция распределенного массива, в который производится копирование, source, srcoffs и srcarr – то же для распределенного массива, из которого производится копирование,
count	—	число копируемых элементов,
rq[]	—	массив – жетон.

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

Для ожидания конца копирования следует обратиться к VSDA_Update_end(). Теневые грани в копировании не участвуют, но указатели targarr и srcarr указывают на полные локальные порции, ВКЛЮЧАЮЩИЕ ТЕНЕВЫЕ ГРАНИ.