Часть I.

Организация и структура Комплекса,
общие правила построения и документирования программ.

Содержание

• 1. Введение.
• 2. Общее описание организации и структуры комплекса.
• 3. Использование пакета BLACS для организации параллельных процессов при решении задач линейной алгебры.
• 4. Общие правила программирования при использовании целевых программ Комплекса.
• 5. Специфика задания параметров при обращении к целевым программам Комплекса.
• 5.1. Глобальные и локальные объекты и параметры программ Комплекса.
• 5.2. Дескрипторы глобальных массивов.
• 5.3. Описания параметров подпрограмм, связанных с глобальными массивами.
• 6. Алгоритмы и реализация распределения плотных матриц по решетке процессов.
• 6.1. Блочно-циклическое отображение плотных матриц в локальную память параллельных процессов.
• 6.2. Пример блочно-циклического распределения плотной матрицы по решетке процессов.
• 6.3. Программирование блочно-циклического распределения плотных матриц.
• 7. Автоматизация доступа к целевым программам Комплекса.
• 8. Некоторые особенности документирования программ.
• 8.1. Правила наименований подпрограмм
• 8.2. Описания программ Комплекса и примеры их использования.
• 8.3. Обозначения и упрощения в примерах по использованию подпрограмм Комплекса.
• ЛИТЕРАТУРА
• Приложение 1_1. Дескрипторы ленточных и трехдиагональных матриц.
• Приложение 1_2. Описания глобальных параметров подпрограмм при обработке ленточных и трехдиагональных матриц.
• Приложение 1_3. Порядок действий при решении задач линейной алгебры с помощью программ автоматизации доступа к целевым программам Комплекса PARALG.

1.Введение.

При реализации Комплекса параллельных программ, рассматриваемого в настоящем пособии, использовались ресурсы суперкомпьютера СКИФ МГУ "ЧЕБЫШЕВ", работающего в Научно-исследовательском Вычислительном Центре МГУ.

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

Указанный Комплекс целевых параллельных фортранных программ (PARALG, см. http://www.srcc.msu.su/num.anal/) был реализован в НИВЦ МГУ на основе использования базовых и вспомогательных подпрограмм пакета ScaLAPACK [13, 14], а также пакетов BLAS [26, 27] и BLACS[18, 19], использующих высокоэффективные алгоритмы решения задач линейной алгебры на распределенной памяти. Он ориентирован на параллельные компьютеры с распределенной памятью и на обмен информацией между параллельными процессами посредством передачи сообщений с помощью примитивов MPI (Massage Passing Interface) [1, 2, 8, 9, 10, 11].

При этом в целевых программах Комплекса взаимодействие параллельных процессов описывается посредством обращений к подпрограммам указанного выше пакета BLACS, который специально разработан как надстройка над примитивами MPI, упрощающая описание такого взаимодействия именно при программировании задач линейной алгебры. Этот пакет тесно связан с представлением о виртуальной "решетке процессов"(см.п.3), в которую организуются выделенные для задачи параллельные процессы, что позволяет использовать эффективные алгоритмы.

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

Такому автоматизированному доступу посвящен материал в п.7 и Приложении 1_3.

2.Общее описание организации и структуры Комплекса.

Рассматриваемый Комплекс программ относится к разряду "параллельных предметных библиотек", при обращении к которым пользователю не приходится явно применять какие - либо конструкции специальных языков параллельного программирования или интерфейсов, поддерживающих взаимодействие параллельных процессов. Все необходимые действия по "распараллеливанию" выполняются подпрограммами из специально разработанных для этих целей пакетов с именами PBLAS [15, 16] (являющегося составной частью пакета ScaLAPACK) и BLACS (Basic Linear Algebra Communication Subprogramms).

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

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

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

Другим пакетом, к которому обращаются программы комплекса, является пакет PBLAS (Parallel Basic Linear Subprogramms), содержащий версии для распределенной памяти подпрограмм (первого, второго и третьего уровней) хорошо известного пакета BLAS (Basic Linear Algebra Subprogram). В BLAS'е содержатся версии подпрограмм, реализующих базовые операции линейной алгебры (такие как действия над векторами и скалярами, умножение матрицы на вектор или перемножение двух матриц), которые могут использоваться на векторных суперкомпьютерах и параллельных компьютерах с разделяемой памятью.

Разработчики пакета PBLAS реализовали его таким образом, чтобы интерфейс его подпрограмм был максимально похожим на интерфейс подпрограмм пакета BLAS.

Таким образом целевые программы описываемого Комплекса (т.е. программы, которые имеют самостоятельное значение при решении прикладных задач) могут содержать обращения к подпрограммам указанных выше пакетов BLACS, PBLAS и BLAS, а также к базовым и вспомогательным подпрограммам пакета ScaLAPACK.

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

К вспомогательным подпрограммам пакета ScaLAPACK относятся подпрограммы, называемые авторами ScaLAPACK'а tools routines. Подпрограммы TOOLS - библиотеки выполняют различные вспомогательные функции, например:

• выдача параметров машинной арифметики конкретной ЭВМ;
• выдача диагностических сообщений в стандартной форме;
• подсчет количества строк или столбцов распределенной по параллельным процессам матрицы, расположенных на одном из этих процессов и т.п.

Верхний уровень программ рассматриваемого Комплекса составляют в настоящее время целевые программы, решающие задачи из разделов линейной алгебры: решение систем линейных алгебраических уравнений, решение проблемы собственных значений (линейной и обобщенной) и сингулярное разложение матриц. Решение систем линейных уравнений рассматривается в Части II настоящего пособия, решение проблемы собственных значений и сингулярное разложение матриц - в Части III.

3.Использование пакета BLACS для организации параллельных процессов
при решении задач линейной алгебры.

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

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

В принятой в BLACS'е логической структуре параллельных процессов каждый процесс идентифицируется с помощью пары чисел - координат процесса в решетке процессов.

На рисунке ниже изображена решетка из 8 процессов, состоящая из двух строк и четырех столбцов ( 2 * 4 ).

                  0      1       2       3
              ------------------------
         0   |        |        |        |        |
              ------------------------
         1   |        |        |        |        |
              ------------------------

Обозначаются эти процессы как:

  ( 0,0 ), ( 0,1 ), ( 0,2 ), ( 0,3 ), ( 1,0 ), ( 1,1 ), ( 1,2 ), ( 1,3 )

Т.е., в общем виде, если в решетке процессов R строк и C столбцов, любой процесс в решетке обозначается парой ( i, j ), где 0 ? i < R,  0 ? j < C. Общее число процессов равно R * C.

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

BLACS, предназначенный для таких компьютеров, опирается на использование широко известных и распространненых интерфейсов обмена сообщениями MPI (Massage Passing Interface) или PVM (Parallel Virtual Machine). Они содержат не только операции обмена между одним посылающим и одним принимающим сообщение процессом, но также и массовые операции обмена, когда, например, один процесс может рассылать сообщение сразу всем другим параллельным процессам, и, наоборот, один из процессов может получать сообщения от всех других.

В BLACS'е такие операции называются контекстными операциями (scope operations), а про процессы, принимающие в них участие, говорят, что они находятся внутри операционного контекста (operation's scope). Организация процессов в виде логической решетки, позволяет BLACS'у естественным образом расширить виды контекстов, а именно, объявлять (задавать) в качестве контекста, т.е. области действия массовых операций обмена сообщениями, не только все параллельные процессы, но также и все процессы, принадлежащие только некоторой строке решетки процессов или некоторому ее столбцу.

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

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

В большинстве современных суперкомпьютеров это условие выполнено, но при использовании сети Ethernet такое преимущество недостижимо (невозможно).

4.Общие правила программирования при использовании целевых программ Комплекса.

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

                              NPROW - число строк решетки процессов,
                               NPCOL - число столбцов решетки процессов,
      NP = NPROW*NPCOL - общее число процессов решетки.

Для идентификации каждого процесса используется пара (MYROW, MYCOL):

                  MYROW - номер строки процесса в решетке,
                   MYCOL - номер столбца процесса в решетке.

При этом  
                    0 ? MYROW < NPROW,
                    0 ? MYCOL  < NPCOL.

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

Это необходимо проделать по той причине, что программы ориентированы на более эффективную блочную реализацию операций с матрицами. Поэтому при обращении к подпрограммам Комплекса необходимо задавать, в частности, величину указанных блоков, т.е.:

        MB - число строк матрицы в блоке;
        NB - число столбцов матрицы в блоке.

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

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

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

Ниже подробнее описываются общие обязательные действия программиста при обращении к любой целевой программе Комплекса.

4.1. Инициализация решетки процессов.

После присвоения конкретных значений параметрам решетки NPROW и NPCOL инициализация решетки процессов проще всего производится посредством обращения к подпрограмме SL_INIT из разряда служебных ( tool - routines). Она состоит из обращений к необходимым подпрограммам пакета BLACS. Ее короткий текст в файле SL_INIT.f ).

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

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

Обращение к подпрограмме SL_INIT выглядит так:

       CALL SL_INIT ( ICTXT, NPROW, NPCOL) ,

    где  
         
           ICTXT - специфицирует контекст BLACS'а (глобальный выходной
                          параметр, тип: целый);
         NPROW - число строк, в создаваемой решетке процессов
                           (глобальный входной параметр, тип: целый);
         NPCOL  - число столбцов, в создаваемой решетке процессов
                           (глобальный входной параметр, тип: целый).

Программы Комплекса написаны с расчетом на использование в стиле SPMD (Single Program Multiple Data). Это означает, что одна и та же программа пользователя будет загружена и одновременно выполняться всеми процессами решетки. Поэтому при необходимости выполнения некоторых действий только на некоторых из этих процессов, требуется определить (узнать) координаты процесса, на котором выполняется данный экземпляр программы. Как уже указывалось они обычно обозначаются идентификаторами (MYROW, MYCOL). Например, необходимо произвести распечатку входных параметров, одинаковых для всех процессов. Чаще всего это делают с процесса с координатами (0, 0).

Для определения координат процесса используют подпрограмму пакета BLACS  BLACS_GRIDINFO.

      CALL BLACS_GRIDINFO ( ICTXT, NPROW, NPCOL, MYROW, MYCOL) ,

где 
         MYROW - номер строки данного процесса в решетке процессов,
                            0 ? MYROW < NPROW (глобальный выходной параметр);
         MYCOL  - номер столбца данного процесса в решетке процессов,
                            0 ? MYCOL < NPCOL (глобальный выходной параметр).

а три первых параметра описаны выше, с той только разницей, что в данном случае
параметр ICTXT - входной.

4.2. Распределение матриц по решетке процессов.

Поскольку каждый процесс производит операции над своей частью исходной глобальной матрицы, до обращения к программам Комплекса необходимо распределить (по определенным правилам) матрицу(ы) A по решетке процессов. Это является обязанностью пользователя (подробности этого процесса описаны в п.6, а также во второй части пособия в пп. 5, 6).

При этом каждой глобальной матрице, распределенной по решетке процессов, должен быть приписан дескриптор, содержащий информацию о том, как именно было произведено это распределение. Дескриптор представляет из себя одномерный массив из 9 или 7 элементов целого типа. Подробное описание дескрипторов можно найти в п.5.2. Здесь мы покажем лишь как инициализировать дескриптор глобальной матрицы A (DESCA).

Если матрица A - плотная, то проще всего инициализировать дескриптор посредством обращения к служебной подпрограмме DESCINIT.

Ниже приводится обращение к этой подпрограмме при инициализации дескриптора DESCA. Подобные обращения можно найти, например, в текстах тестовых примеров к программам решения системы уравнений с плотными матрицами ( TPDGESV.f, TPDPOSV.f ).

     CALL DESCINIT(DESCA, M, N, MB, NB, RSRC, CSRC,
                                    ICTXT, MXLLDA, INFO)

Этот вызов подрограммы DESCINIT эквивалентен следующим операторам присваивания:

        DESCA(1) = 1
        DESCA(2) = ICTXT
        DESCA(3) = M
        DESCA(4) = N
        DESCA(5) = MB
        DESCA(6) = NB
        DESCA(7) = RSRC
        DESCA(8) = CSRC
        DESCA(9) = MXLLDA

Здесь первый элемент обозначает тип дескриптора для плотной матрицы, второй - обсуждавшийся выше служебный параметр подпрограмм BLACS'а (контекст).

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

4.3. Освобождение решетки процессов.

После того как необходимые вычисления на решетке процессов были завершены требуется освободить решетку процессов посредством вызова подпрограммы BLACS_GRIDEXIT. Когда завершены все вычисления, выход из системы BLACS'а должен быть осуществлен посредством обращения к подпрограмме BLACS_EXIT.

Типичный пример фрагмента программы, включающий эти действия:

          CALL BLACS_GRIDEXIT(ICTXT)

          CALL BLACS_EXIT(0)