Вычислительный центр им. А.А. Дородницына РАН    

Раздел виртуального курса
Параллельное программирование в интерфейсе MPI


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


Содержание

  1. Введение в ScaLAPACK
  2. Последовательные и параллельные математические библиотеки
  3. Как использовать функцию ScaLAPACK: шаг за шагом
  4. Создание процессорной сетки
  5. Распределение Данных в ScaLAPACK
  6. Литература


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

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

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

Следует учесть, что установленные в настоящее время на кластере ВЦ РАН параллельные математические библиотеки предусматривают вызовы только из Фортрана.

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

Темы, которые будут охвачены в данном разделе, таковы:

  1. Введение в ScaLAPACK
  2. Последовательные и параллельные математические библиотеки
  3. Как использовать подпрограмму библиотеки ScaLAPACK: шаг за шагом
  4. Создание процессорной сетки
  5. Распределение данных в ScaLAPACK

1. Особенности библиотеки ScaLAPACK

Этот параграф посвящен параллельной библиотеке ScaLAPACK ("Скалапак"). Вы увидите в последующих параграфах, что библиотека ScaLAPACK фактически построена на основе и содержит несколько других основных библиотек, предлагая пользователям доступ к более чем ста математическим подпрограммам, которые работают параллельно.

ScaLAPACK де-факто стала стандартной параллельной числовой библиотекой, прежде всего из-за его мобильности и дизайна. ScaLAPACK была успешно установлена на разнообразных платформах массовой парраллельной обработки (MPP) , включая Cray T3E, SGI Origin 2000, IBM SP2, Intel Paragon, сети рабочих станций, и недавно разработанные кластеры Beowolf Clusters. Но реальная причина для посеместного принятия ScaLAPACK больше чем просто переносимость, она в том, что эта библиотека содержит обширный набор параллельных подпрограмм для широко распространенных вычислений по линейной алгебре , которые хорошо выполняются и являются масштабируемыми. Если число процессоров, используемых подпрограммой ScaLAPACK увеличивается, время вычислений уменьшается, что является основной целью параллельной обработки. Масштабируемость библиотеки ScaLAPACK можно также рассмотреть с другой точки зрения – если размер задачи (измерения массива) возрастает при том же самом числе процессоров, а параллельная эффективность остается постоянной.

Успех ScaLAPACK может быть также приписан факту, что она сформирована на надежной, хорошо-развитой библиотеке LAPACK, которая использовалась программистами в течение многих десятилетий. Библиотека ЛАПАК содержит последовательные подпрограммы линейной алгебры, оптимизированные для разнообразных процессоров. Кроме того, ScaLAPACK включает две новых библиотеки: PBLAS и PBLACS. Как будет детализировано позже, подпрограммы PBLAS выполняют оптимизированные, параллельные задачи линейной алгебры нижнего уровня. Пользователи ограждены от специфических машинных характеристик, которые подпрограммы PBLAS используют для оптимизации. Подпрограммы PBLACS ответственны за коммуникацию между процессорами, заменяя кодирование на MPI, которое Вам пришлось бы делать в противном случае.

Разработчики ScaLAPACK приняли полезное решение, разработав синтаксис фактических вызовов ScaLAPACK. Эта "дружественая пользователю" идея заключалась в том, чтобы параллельная версия последовательной подпрограммы LAPACK имела то же самое название, только предваренное буквой 'P'. Кроме того, названия и значения параметров подпрограмм ScaLAPACK были сделаны подобными настолько, насколько это возможно, соотвествующим параметрам подпрограмм LAPACK.

Конечное, и безусловно самое желаемое, свойство ScaLAPACK состоит в том, что при использовании ее подпрограмм Вы не должны писать ваш собственный параллельный код обработки не должны разрабатывать или исследовать хороший параллельный алгоритм для выполнения специфической задачи линейной алгебры. (Последнее часто является трудным процессом и темой текущих исследований в журналах CIS - Computing and Information Systems.) Строго говоря, Вам не требуется какое-либо знания MPI или любых других библиотек передачи сообщений. Однако, небольшой опыт в использовании передачи сообщений полезен как подготовка к пониманию подпрограмм PBLACS, предназначенных для отправки целых массивов (или подсекций) от одного процессора к другому.

Документация ScaLAPACK

Вся информация, которую необходимо знать о ScaLAPACK и ее библиотеках имеется в документации, доступной в репозитарии Netlib.

Репозитарий (= хранилище = архив) Netlib содержит не только ОТКРЫТЫЙ исходный код множества математических библиотек, но также и документацию во многих формах: описания подпрограмм, руководства, man-страницы, публикации кратких справок, и т.д.
Специфические рукописи, которые были бы полезны для этого раздела:

2. Последовательные и параллельные математические библиотеки

Акронимы (звуковые аббревиатуры)

Для начала определим некоторые акронимы:

Иерархия математических библиотек

Рис. 1. Иерархия математических библиотек

На вышеприведенном рисунке, библиотеки, лежащие ниже ключевого слова "Local" - это последовательные библиотеки. Заметим, что LAPACK содержит и основывается на BLAS. Каждый поставщик оптимизирует и работает только на системе с единственным процессором : векторные суперкомпьютеры, рабочие станции, или один процессор системы MPP. Как правило, оптимизация выполнена через блокирующие алгоритмы, спроектированные, чтобы сохранить и многократно использовать критические данные на самых низких уровнях иерархии памяти: регистры -> первичный кэш -> вторичный кэш -> локальная память.

Библиотеки, лежащие выше ключевого слова "Global", - это новые параллельные библиотеки. Аналогичным образом как и у последовательных библиотек, ScaLAPACK содержит и основывается на PBLAS. Это библиотеки, которые будут обсуждаться и будут использоваться в этом разделе, поскольку они используются на системах MPP для выполнения параллельных вычислений линейной алгебры.

Этот рисунок также показывает, что ScaLAPACK основан на BLACS, и это должно быть так, поскольку подпрограммы BLACS передают локальные данные из памяти одного процессора к другому. В действительности, подпрограммы BLACS являются подпрограммами окружения (обертки), которые называют библиотекой передачи сообщений низшего уровня. Типично - это непосредственно MPI! (Рисунок выше является немного запутывающим в этом пункте, поскольку BLACS и MPI - параллельные библиотеки. Они изображены в более низком разделе, чтобы проиллюстрировать то, что параллельные библиотеки сформированы над ними).

BLAS/PBLAS

Эти библиотеки содержат последовательные и параллельные версии основных процедур линейной алгебры. Каждая содержит подпрограммы, которые распадаются на три уровня:

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

LAPACK/ScaLAPACK

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

Как и с основными библиотеками поддерживается много типов матриц, так же включены различные алгоритмы по разложению матриц на множители. Эти разложения на множители включают LU (L - нижняя треугольная, U - верхняя треугольная), Cholesky, QR, LQ, Orthogonal, и т.д.

BLACS

Как ранее упоминалось, подпрограммыBLACS используют в первую очередь, чтобы передать данные между процессорами. Более точно говоря, подпрограммы BLACS включают двухточечную коммуникацию, подпрограммы передачи, и "комбинационные" подпрограммы для осуществления "глобальных" вычислений - суммирования, нахождения максимума и минимума - с данными, размещенными на различных процессорах. Привлекательная особенность подпрограмм коммуникации BLACS состоит в том, что они основаны на массиве: данные, которые передаются - всегда массив целиком или подмассив.

Библиотека BLACS также содержит важные подпрограммы для создания и исследования сетки процессора, которая ожидается и используется всеми подпрограммами PBLAS и ScaLAPACK. Процессорная сетка является 2-мерной с ее размером и формой, которыми управляет пользователь. Процессор идентифицирован не его традиционным рангом MPI, а скорее его строкой и числом столбца в процессорной сетке.

Как можно заметить на диаграмме процессорной сетки ниже (рис. 2), 8 процессоров, используемых программой были упорядочены в сетку 2x4. Содержащийся в пределах каждого элемента сетки номер является рангом MPI для процессора. Например, процессор с рангом 6 имеет координаты сетки ( p, q ) = (1,2). Обратите внимание, что нумерации и строк и столбцов начинаются с нуля. Для примера мы выбрали вставку процессоров по "строке". Эта сетка была создана вызовом простую подпрограмму BLACS, которая будет подробно описана позже.

Рис. 2. Сетка, созданная посредством простой подпрограммы BLACS.

 


3. Как использовать подпрограмму библиотеки ScaLAPACK: шаг за шагом

Этот параграф может быть самым коротким, но в каком-то смысле он является самым важным. Если Вы выполните правильно каждый шаг, то ваша подпрограмма ScaLAPACK должна работать!

Порядок выполнения ScaLAPACK (контрольный список):

  1. Напишите пропорционально уменьшенную программу, используя эквивалентную последовательную подпрограмму LAPACK

    • Рекомендуется, не требуется

    • Выполните, используя только один процессор

    • Хорошо для ознакомления пользователя с подходящими названиями подпрограмм и их параметров. Названия и аргументы параллельных подпрограмм будут аналогичными.

    • Хорошо для синтаксиса и логической отладки

  2. Инициализируйте библиотеку BLACS для ее использования в программе

  3. Создайте и используйте процессорную сетку BLACS

  4. Распределите части каждого глобального массива по процессорам в сетке

    • Пользователь делает это, создавая вектор описателя массива для каждого глобального массива

    • Глобальные элементы массива отображены блокированно-циклическим способом в 2-мерный массив на процессорной сетке

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

  6. Вызовите подпрограмму ScaLAPACK!

  7. Подтвердите/используйте вывод подпрограммы ScaLAPACK

  8. Освободите процессорную сетку и выйдите из библиотеки BLACS


4. Создание процессорной сетки

Подпрограммы инициализации BLACS

Две подпрограммы, описанные в этом разделе инициализируют библиотеку BLACS, устанавливая контекст, в пределах которого данные будут переданы. Это - шаг 2 контрольного списка порядка выполнения, выделенный в пункте 3. Следующее соглашение будет использоваться для всех подпрограмм в этом разделе: если параметр подчеркнут, значение для него возвращено подпрограммой; все другие - ввод в подпрограмму. Кроме того, все функции - подпрограммы, если только их синтаксис не указывает возвращаемый тип.

   BLACS_PINFO(rank,nprocs)

Подпрограммы сетки BLACS

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

   BLACS_GRIDINIT(icontxt,order,nprow,npcol)

Например, сетка, показанная на диаграмме в конце параграфа 2 была сделана посредством такого вызова:

   CALL BLACS_GRIDINIT(icontxt,'R',2,4) 

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

   BLACS_GRIDINFO(icontxt,nprow,npcol,myrow,mycol)


5. Распределение данных в ScaLAPACK

Метод распределения данных

ScaLAPACK использует двумерную блочно-циклическую дистрибутивную методику, чтобы анализировать отображение глобальных элементов массива на сетку процессора. Блочно-циклическая методика была выбрана, потому что она дает лучший баланс загрузки и максимального разброса (местоположения) данных для большинства алгоритмов ScaLAPACK. (См "Руководство пользователя ScaLAPACK" для подробной проверки этого выбора и сравнения с другими методами распределения.)

Двумерное блочно-циклическое распределение достигается благодаря следующим шагам:

  1. Разделите глобальный массив на блоки с mb строками и nb столбцами. С этого времени, представляйте себе глобальный массив, как массив, составленный только из этих блоков.

  2. Выделите первую строку блоков массива поперек первой строки сетки процессора по-порядку. Если Вы исчерпываете столбцы процессорной сетки, сделайте переход на цикл назад к первому столбцу.

  3. Повторите со второй строкой блоков массива, со второй строкой процессорной сетки.

  4. Продолжите для оставшихся строк блоков массива.

  5. Если Вы исчерпываете строки процессорной сетки, сделайте цикл назад к первой строке процессора и повторите.

Диаграмма ниже иллюстрирует двумерное блочно-циклическое распределение глобального массива размерности 9x9 блоками массива 2x2 по процессорной сетке 2x3. (Цвета представляют ранги 6 различных процессоров.)

Рис. 3. 2-мерное блочно-циклическое распределение глобального массива размерности 9x9 блоками массива 2x2 по процессорной сетке 2x3

Обратите внимание, что каждый процессор имеет различной размерности локальный массив, который он должен заполнить правильными глобальными элементами (Шаг 5 в контрольном списке порядка выполнения).

  Процессор (0,0): локальный массив размерности 5x4
  Процессор (0,1): локальный массив размерности 5x3
  Процессор (0,2): локальный массив размерности 5x2
  Процессор (1,0): локальный массив размерности 4x4
  Процессор (1,1): локальный массив размерности 4x3
  Процессор (1,2): локальный массив размерности 4x2

Вектор Описателя Массива

Вектор описателя массива содержит информацию, в которой каждая подпрограмма ScaLAPACK определяет распределение глобальных элементов массива в локальные массивы, принадлежащие каждому процессору. Ниже описан каждый из 9 элементов этого вектора. Два соглашения используются в этом описании. Во-первых, для глобального массива A, традиционно назвать вектор описателя массива DESCA. Во вторых, "_A" читается как "распределенный глобальный массив A". Символические названия и определения элементов DESCA даны в следующей таблице.

Символьное имя

Описание

DESCA(1)=dtype_A

тип распределяемой матрицы (1 для плотной, обычной матрицы)

DESCA(2)=icontxt

BLACS context

DESCA(3)=m_A

число строк в глобальном массиве A

DESCA(4)=n_A

число столбцов в глобальном массиве A

DESCA(5)=mb_A

число строк в блоке A

DESCA(6)=nb_A

число столбцов в блоке A

DESCA(7)=rsrc_A

строка процессорной сетки, которая имеет первый блок (типично 0)

DESCA(8)=csrc_A

столбец процессорной сетки, который имеет первый блок (типично 0)

DESCA(9)=lld

число строк в локальном массиве, которые содержат блоки A (локальная/l/ лидирующая/l/ размерность/d/). Этот элемент является процессорно-зависимым

Итак, для процессора (0,2) в представленном примере, DESCA=(1,icontxt,9,9,2,2,0,0,5).

Пользовательская подпрограмма DESCINIT

К счастью, Вы никогда не должны явно заполнять каждый элемент DESCA. ScaLAPACK обеспечен инструментальной подпрограммой DESCINIT, которая будет использовать свои параметры, чтобы создать вектор описателя массива DESCA для Вас. Как только DESCINIT вызвана (каждым процессором), шаг 4 контрольного списка последовательности выполнения завершен.

   DESCINIT(desc, m, n, mb, nb, rsrc, csrc, icontxt, lld, info)


6. Литература

  1. Руководство пользователя ScaLAPACK
  2. Parallel Basic Linear Algebra Subprograms (PBLAS)
  3. Руководство пользователя BLACS


© 2004 Вычислительный центр им. А.А.Дородницына Все права защищены.
Прочтите наше Copyright руководство.