Вычислительный центр им. А.А. Дородницына РАНРаздел виртуального курса
|
|
---|
Параллельные математические библиотеки
В данном разделе общий ход изложения изменен. Из предыдущих разделов Вы узнали полезные функции MPI, что дает Вам возможность писать ваши собственные функции с помощью MPI для параллельного выполнения математических и научных задач. В этом разделе Вы узнаете о существующих (и, кроме того, популярных и свободных) математических библиотеках, которые осуществят для Вас параллельно общие алгоритмы линейной алгебры.
Вам не потребуется писать собственный код в MPI, чтобы выполнять задачи линейной алгебры параллельно; вместо этого Вам достаточно вызвать подпрограмму.
Следует учесть, что установленные в настоящее время на кластере ВЦ РАН параллельные математические библиотеки предусматривают вызовы только из Фортрана.
Помимо очевидной простоты в использовании только вызова из библиотеки, это также предохранит Вас от "изобретения велосипеда." Вы увидите, что эти библиотеки являются полными, хорошо написанными, хорошо оптимизированными (как с последовательной, так и с параллельной точек зрения), и спроектированными на основе превосходных параллельных алгоритмов.
Темы, которые будут охвачены в данном разделе, таковы:
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 и ее библиотеках имеется в документации, доступной в репозитарии Netlib.
Репозитарий (= хранилище = архив) Netlib содержит не только ОТКРЫТЫЙ исходный код
множества математических библиотек, но также и документацию во многих формах: описания подпрограмм,
руководства, man-страницы, публикации кратких справок, и т.д.
Специфические рукописи, которые были бы полезны для этого раздела:
2. Последовательные и параллельные математические библиотеки
Рис. 1. Иерархия математических библиотек |
На вышеприведенном рисунке, библиотеки, лежащие ниже ключевого слова "Local" - это последовательные библиотеки. Заметим, что LAPACK содержит и основывается на BLAS. Каждый поставщик оптимизирует и работает только на системе с единственным процессором : векторные суперкомпьютеры, рабочие станции, или один процессор системы MPP. Как правило, оптимизация выполнена через блокирующие алгоритмы, спроектированные, чтобы сохранить и многократно использовать критические данные на самых низких уровнях иерархии памяти: регистры -> первичный кэш -> вторичный кэш -> локальная память.
Библиотеки, лежащие выше ключевого слова "Global", - это новые параллельные библиотеки. Аналогичным образом как и у последовательных библиотек, ScaLAPACK содержит и основывается на PBLAS. Это библиотеки, которые будут обсуждаться и будут использоваться в этом разделе, поскольку они используются на системах MPP для выполнения параллельных вычислений линейной алгебры.
Этот рисунок также показывает, что ScaLAPACK основан на BLACS, и это должно быть так, поскольку подпрограммы BLACS передают локальные данные из памяти одного процессора к другому. В действительности, подпрограммы BLACS являются подпрограммами окружения (обертки), которые называют библиотекой передачи сообщений низшего уровня. Типично - это непосредственно MPI! (Рисунок выше является немного запутывающим в этом пункте, поскольку BLACS и MPI - параллельные библиотеки. Они изображены в более низком разделе, чтобы проиллюстрировать то, что параллельные библиотеки сформированы над ними).
Эти библиотеки содержат последовательные и параллельные версии основных процедур линейной алгебры. Каждая содержит подпрограммы, которые распадаются на три уровня:
Все эти уровни подпрограмм спроектированы для работы с разнообразием матричных типов, таких как общие, симметричные, сложные, Эрмитовы и треугольные матрицы. Заметим, что разреженные матрицы не поддерживаются.
Эти библиотеки содержат подпрограммы для более сложных вычислений линейной алгебры. Есть три типа продвинутых задач, которые эти библиотеки решают:
Решение ряда систем линейных уравнений
Задачи на собственное значение / собственный вектор
Линейная подгонка по методу наименьших квадратов
Как и с основными библиотеками поддерживается много типов матриц, так же включены различные алгоритмы по разложению матриц на множители. Эти разложения на множители включают LU (L - нижняя треугольная, U - верхняя треугольная), Cholesky, QR, LQ, Orthogonal, и т.д.
Как ранее упоминалось, подпрограммыBLACS используют в первую очередь, чтобы передать данные между процессорами. Более точно говоря, подпрограммы BLACS включают двухточечную коммуникацию, подпрограммы передачи, и "комбинационные" подпрограммы для осуществления "глобальных" вычислений - суммирования, нахождения максимума и минимума - с данными, размещенными на различных процессорах. Привлекательная особенность подпрограмм коммуникации BLACS состоит в том, что они основаны на массиве: данные, которые передаются - всегда массив целиком или подмассив.
Библиотека BLACS также содержит важные подпрограммы для создания и исследования сетки процессора, которая ожидается и используется всеми подпрограммами PBLAS и ScaLAPACK. Процессорная сетка является 2-мерной с ее размером и формой, которыми управляет пользователь. Процессор идентифицирован не его традиционным рангом MPI, а скорее его строкой и числом столбца в процессорной сетке.
Как можно заметить на диаграмме процессорной сетки ниже (рис. 2), 8 процессоров, используемых программой были упорядочены в сетку 2x4. Содержащийся в пределах каждого элемента сетки номер является рангом MPI для процессора. Например, процессор с рангом 6 имеет координаты сетки ( p, q ) = (1,2). Обратите внимание, что нумерации и строк и столбцов начинаются с нуля. Для примера мы выбрали вставку процессоров по "строке". Эта сетка была создана вызовом простую подпрограмму BLACS, которая будет подробно описана позже.
Рис. 2. Сетка, созданная посредством простой подпрограммы BLACS. |
3. Как использовать подпрограмму библиотеки ScaLAPACK: шаг за шагом
Этот параграф может быть самым коротким, но в каком-то смысле он является самым важным. Если Вы выполните правильно каждый шаг, то ваша подпрограмма ScaLAPACK должна работать!
Порядок выполнения ScaLAPACK (контрольный список):
Напишите пропорционально уменьшенную программу, используя эквивалентную последовательную подпрограмму LAPACK
Рекомендуется, не требуется
Выполните, используя только один процессор
Хорошо для ознакомления пользователя с подходящими названиями подпрограмм и их параметров. Названия и аргументы параллельных подпрограмм будут аналогичными.
Хорошо для синтаксиса и логической отладки
Инициализируйте библиотеку BLACS для ее использования в программе
Создайте и используйте процессорную сетку BLACS
Распределите части каждого глобального массива по процессорам в сетке
Пользователь делает это, создавая вектор описателя массива для каждого глобального массива
Глобальные элементы массива отображены блокированно-циклическим способом в 2-мерный массив на процессорной сетке
Пусть каждый процессор инициализирует его локальный массив правильными значениями кусочков глобального массива, которыми он владеет.
Вызовите подпрограмму ScaLAPACK!
Подтвердите/используйте вывод подпрограммы ScaLAPACK
Освободите процессорную сетку и выйдите из библиотеки BLACS
Две подпрограммы, описанные в этом разделе инициализируют библиотеку BLACS, устанавливая контекст, в пределах которого данные будут переданы. Это - шаг 2 контрольного списка порядка выполнения, выделенный в пункте 3. Следующее соглашение будет использоваться для всех подпрограмм в этом разделе: если параметр подчеркнут, значение для него возвращено подпрограммой; все другие - ввод в подпрограмму. Кроме того, все функции - подпрограммы, если только их синтаксис не указывает возвращаемый тип.
|
Основная цель вызова этой подпрограммы состоит в том, чтобы получить число процессоров, которые программа будет использовать (как определено в командной строке, когда программа запускается).
Ранг параметра содержит нормальный ранг MPI (Структура программы MPI) процессора, который вызван подпрограммой.
Параметр nprocs содержит общее количество используемых процессоров.
|
BLACS_GET является фактически универсальной, сервисной подпрограммой, которая восстановит значения для ряда внутренних параметров BLACS.
С параметрами, показанными выше, вызов BLACS_GET получит контекст (параметр icontxt) для использования ScaLAPACK. (Примечание: первый параметр игнорируется в этой форме вызова).
Контекст параллельной библиотеки передачи данных уникально идентифицирует все передачи данных BLACS, как подключаемые со специфической подпрограммой ScaLAPACK. Никакие другие подпрограммы передачи сообщений в программе не могут столкнуться с коммуникацией BLACS. Контекст полностью эквивалентен значению Коммуникатора MPI, объясненному ранее в этом курсе.
Первая из этих двух подпрограмм BLACS фактически создает процессорную сетку к спецификациям. Вторая является инструментальной подпрограммой, которая подтверждает, что сетка была создана успешно. Вместе, вызовы этих подпрограмм составляют шаг 3 нашего контрольного списка порядка выполнения.
|
Эта подпрограмма создает виртуальную процессорную сетку согласно значениям, в которые установлены параметры.
icontxt = контекст BLACS для его передачи сообщений (первый параметр почти каждой подпрограммы BLACS).
order= определяет, как ранги процессора отображены на сетке. Если этот параметр есть 'R', то отображение сделано по строкам; если он есть 'C', то отображение сделано по столбцам.
nprow= устанавливает число строк в процессорной сетке.
npcol= устанавливает число столбцов в процессорной сетке.
Например, сетка, показанная на диаграмме в конце параграфа 2 была сделана посредством такого вызова:
|
Эта типовая процессорная сетка была бы приемлемой для программы, использующей 8 (2x4) процессоров. Вы можете экспериментировать с размером и формой процессорной сетки, созданной, чтобы максимизировать эффективность работы программы.
|
Основное использование этой пользовательской подпрограммы состоит в том, чтобы подтвердить форму процессорной сетки и, что еще более важно, получить для каждого процессора его координаты (myrow, mycol) в процессорной сетке. ВОЗЬМИТЕ В ПРИВЫЧКУ ИСПОЛЬЗОВАТЬ КООРДИНАТЫ СЕТКИ, ЧТОБЫ ИДЕНТИФИЦИРОВАТЬ ПРОЦЕССОР!
Отметим, что nprow и npcol возвращаются, чтобы удостовериться, что форма сетки такова, которую хотелось.
myrow = вызываемый номер строки процессора в процессорной сетке.
mycol = вызываемый номер столбца процессора в процессорной сетке.
Двумерное блочно-циклическое распределение достигается благодаря следующим шагам:
Разделите глобальный массив на блоки с mb строками и nb столбцами. С этого времени, представляйте себе глобальный массив, как массив, составленный только из этих блоков.
Выделите первую строку блоков массива поперек первой строки сетки процессора по-порядку. Если Вы исчерпываете столбцы процессорной сетки, сделайте переход на цикл назад к первому столбцу.
Повторите со второй строкой блоков массива, со второй строкой процессорной сетки.
Продолжите для оставшихся строк блоков массива.
Если Вы исчерпываете строки процессорной сетки, сделайте цикл назад к первой строке процессора и повторите.
Диаграмма ниже иллюстрирует двумерное блочно-циклическое распределение
глобального массива размерности 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).
К счастью, Вы никогда не должны явно заполнять каждый элемент DESCA. ScaLAPACK обеспечен инструментальной подпрограммой DESCINIT, которая будет использовать свои параметры, чтобы создать вектор описателя массива DESCA для Вас. Как только DESCINIT вызвана (каждым процессором), шаг 4 контрольного списка последовательности выполнения завершен.
DESCINIT(desc, m, n, mb, nb, rsrc, csrc, icontxt, lld, info) |
desc = "заполняемый" вектор описания, возвращаемый подпрограммой.
аргументы 2-9 = значения для элементов 2-9 вектора описания (в другом порядке).
info = значения состояния (статуса), возвращаемое, чтобы показать работает ли DESCINIT корректно. Если info = 0, вызов подпрограммы успешен. Если info = -i, i-ый аргумент имеет неверное значение.
© 2004
Вычислительный центр им. А.А.Дородницына
Все права защищены. |
|