Коммуникационные шаблоны

Введение

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

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

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

Коммуникационные шаблоны

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

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

Приведем пример из области задач механики сплошной среды. Классическая задача теплопроводности, решаемая методом Якоби (данный цикл рассматривался и ранее):

for (i = 1; i < I - 1; i++) {
   
for (j = 1; j < J - 1; j++) {
       A_new[i][j] = ( A_old[i+
1][j] + A_old[i][j+1] + A_old[i-1][j] + A_old[i][j-1] ) / 4;
   }
}


Для такого двойного цикла коммуникационный шаблон будет следующим:
на каждом витке цикла (i,j) читаются данные массива A_old по индексам [i+1][j], [i][j+1], [i-1][j] и [i][j-1] и пишется в массив A_new (по индексу [i][j]).

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

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

Снова рассмотрим задачу теплопроводности, решаемую методом Якоби, записанную в методически правильном виде:

for (n = 0; n < N; n++) {
   
if (Grid[n].is_inner) { // если внутрення ячейка
       
A_new[n] =  ( A_old[Grid[n].north] + A_old[Grid[n].east] + A_old[Grid[n].south] + A_old[Grid[n].west] ) / 4;
   }
}


Описание шаблона будет следующим:
читаются элементы массива A_old, находящиеся на north, east, south, west относительно текущего элемента, пишется текущий элемент массива A_new.

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

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

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

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

Использование коммуникационных шаблонов

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

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

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

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

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

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

Редукции

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

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

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

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

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

Заключение

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