1. Влияние параметров распараллеливания на производительность
В разделе Руководства по использованию Комплекса PARALG "Автоматизация доступа к подпрограммам Комплекса" говорилось о подпрограммах, выбирающих за пользователя параметры распараллеливания задачи ( NPROW, NPCOL, NB ). Этот выбор обеспечивает некоторый приемлемый уровень производительности для матриц заданного размера и заданного числа параллельных процессов. Однако такой выбор не обязательно является наилучшим из возможных (оптимальным). Посредством более подходящего распределения частей (блоков) матриц по параллельным процессам можно добиться увеличения производительности на 10% и более.
Оптимальное распределение данных зависит от нескольких факторов:
Как уже пояснялось в п. выше для подпрограмм Комплекса PARALG параметрами распараллеливания являются: число строк ( NPROW ) и число столбцов ( NPCOL ) в решетке процессов (в которую необходимо (логически) организовать используемые параллельные процессы), а также величина блоков ( NB ), на которые разбиваются исходные матрицы с целью равномерного распределения их по параллельным процессам.
Выбор наилучших параметров решетки процессов ( NPROW, NPCOL ) зависит от алгоритмов, реализованных в базовых подпрограммах, входящих в Комплекс. Так, например, LU-, QR- и QL-разложения матриц лучше (быстрее) выполняются на решетках процессов "плоской" прямоугольной формы, где число строк в решетке меньше числа столбцов ( Pr < Pc ).
Тогда как LQ- и RQ-разложения быстрее выполняются на "высоких" ("вертикальных") решетках процессов, где число строк больше числа столбцов ( Pr > Pc ).
Квадратные или близкие к квадратным решетки ( Pr ≈ Pc ) являются более предпочтительными, например, для алгоритмов обращения матриц или операций приведения (преобразования) матриц к двухдиагональной форме, трехдиагональной форме или форме Хессенберга.
Но результаты анализа алгоритмов и советы по выбору предпочтительной формы решетки в той или иной степени могут зависеть от физических характеристик используемой сети взаимосвязи процессоров. Когда пользователю неизвестны особенности реализации пакета BLACS и свойства используемой сети для обмена данными на конкретной вычислительной системе, еще одно соображение может помочь с выбором формы решетки процессов.
На задачах малого размера на производительность б'ольшее влияние оказывает общее число обменов данными (передаваемых сообщений), тогда как для задач среднего размера определяющим фактором становится общий объем передаваемых данных. Для задач большого размера основное влияние на производительность оказывает выполнение операций с плавающей запятой.
При использовании одномерной решетки процессов ( Pr = 1, Pc = NPROC ) сокращается общее число обменов данными в сети связи, но увеличивается общий объем передаваемых сообщений. Поэтому одномерное распределение данных лучше использовать для задач малых размеров, но хуже для задач больших размеров (особенно, когда при этом используется более 8 процессоров).
Что касается выбора размера блоков ( NB ), на которые разбиваются матрицы, то выбор оптимального (с точки зрения производительности) размера является трудной задачей для конкретной вычислительной системы. Такой выбор часто делается эмпирическим путем.
Учитывая теоретические трудности определения наилучших параметров распределения матриц для достижения оптимальной производительности, решено было разработать и реализовать для Комплекса PARALG специальную подсистему подбора оптимальных параметров, состоящую из программной части и архива результатов.
Программная часть позволяет автоматизировать и упростить экспериментальный подбор оптимальных параметров распараллеливания задач. Удобная архивная система предназначена для хранения уже рассчитаных оптимальных значений параметров для разных целевых программ Комплекса, матриц разного размера и разного количества используемых при расчетах параллельных процессов.
При обеспечении общего доступа (разных заинтересованных пользователей) к результатам, хранящимся в такой системе, можно дополнительно съэкономить как затраты человеческого труда, так и значительное количество машинного времени.
Полезность такой архивной системы основана на том, что время выполнения расчетов с матрицами на конкретной вычислительной установке не зависит от конкретных значений элементов матриц, а только от порядка матрицы и вида решаемой задачи (т.е. используемых алгоритмов обработки). Очевидна выгода от указанной системы для пользователя, которому необходимо проводить неоднократные расчеты с разными матрицами одного и того же порядка (размера). А также для пользователя, проводящего аналогичные расчеты на той же вычислительной установке. Он может воспользоваться оптимальными параметрами распараллеливания, уже подобранными с помощью такой системы другим пользователем и размещенными в общедоступном системном архиве.
Далее опишем несколько подробнее новую (дополненную) версию реализованной программной части, а также разработанные правила хранения результатов - подобранных оптимальных параметров.
2. Программная часть подсистемы подбора наилучших параметров
Текущая версия (2015 г.) программной части подсистемы состоит из
головной подпрограммы BSTPAR9 ,
которая организует циклическое обращение к остальным подпрограммам,
меняя при этом параметры распараллеливания, при которых будет производиться
очередное решение одной и той же задачи.
Кроме того она определяет, при каком наборе этих параметров было получено
наилучшее (наименьшее) время решения в данном запуске и запоминает в системном
файле эти параметры вместе с наилучшим временем решения.
В текущую версию рассматриваемой подсистемы входит еще 6 служебных
подпрограмм ( с именами
CAL_GESVN,
CAL_POSVN,
CAL_GEEV1N,
CAL_SYEV1N,
CAL_SYGV1N,
CAL_GESVD1N ),
которые организуют автоматический вызов той или другой (указанной
пользователем) целевой вычислительной подпрограммы из разных
тематических подразделов Комплекса:
решение систем алгебраических уравнений с матрицами общего вида;
решение систем алгебраических уравнений с симметричными матрицами;
вычисление собственных значений в линейной проблеме для матриц
общего вида;
вычисление собственных значений в линейной и обощенной проблеме
для симметричных и эрмитовых матриц;
вычисление сингулярных чисел матриц.
Все эти 6 подпрограмм, кроме того, выполняют свою главную функцию
- определяют и запоминают время решения задачи при каждом,
использованном при решении, конкретном наборе параметров
распараллеливания.
Кроме того, они могут выдавать и/или запоминать в файлах
затребованную пользователем информацию ( входные параметры и матрицы,
полученные результаты решения численной задачи, использованную
при вычислениях память и др.).
Так, например, подпрограмма CAL_GESVN организует вызов выбранной
пользователем целевой программы Комплекса для решения систем линейных
алгебраических уравнений с матрицами общего вида (одну из PDGESV, PDGESV1,
PDGESV2, PDGESV3) и вычисляет время, затраченное на решение задачи при заданных
общих условиях: количестве используемых процессоров (NPROC) и заданном порядке
исходной матрицы (N). Кроме того, ей в качестве параметров передается
один из вариантов параметров распараллеливания: NPROW, NPCOL, NB.
Эта программа позволяет производить решение системы уравнений и
вычисление затраченного на это времени как на примере матрицы (порядка N),
задаваемой в файле самим пользователем, так и на примере некоторой
"стандартной" матрицы (того же порядка), генерируемой самой системой.
Подпрограмма BSTPAR9, посредством обращения в цикле к описанной выше подпрограмме CAL_GESVN, организует неоднократный вызов выбранной пользователем целевой программы Комплекса (для решения систем линейных алгебраических уравнений с матрицами общего вида) с разными фактическими параметрами распараллеливания ( NPROW, NPCOL, NB ). При этом остаются неизменными как сама исходная матрица (в частности ее порядок N), так и общее число используемых параллельных процессов ( NPROC ).
За один "заход", т.е. запуск BSTPAR9 в решение командой операционной системы (mpirun) можно сделать несколько экспериментальных расчетов (вызовов целевой программы), осуществляя перебор разных вариантов решеток процессов. Однако все варианты должны удовлетворять условию:
NPROW*NPCOL = NPROC ,
где NPROW - число строк в решетке процессов,
NPCOL - число столбцов в решетке процессов,
NPROC - общее число процессоров, заказанное в команде запуска (mpirun).
Это означает, что в конкретном запуске могут быть использованы в вычислениях только те варианты решеток процессов, которые включают в себя все заказанные процессоры ( NPROC ).
Что касается величины блока матрицы ( NB ), то за один запуск можно, вообще говоря, перебрать все варианты NB, удовлетворяющие условию
2 ≤ NB ≤ N/NPROC .
Однако, для больших матриц не имеет смысла перебирать все NB, удовлетворяющие указанному условию. Пользователю предоставляется возможность за один "заход" произвести расчеты, перебирая варианты NB с некоторым шагом ( DNB ) от некоторого минимального значения ( NBMIN ≥ 2 ) до некоторого максимального ( NBMAX ≤ N/NPROC ).
Количество "перебираемых" решеток процессов также можно ограничить, задав некоторое минимальное ( NPRWMIN ) и некоторое максимальное ( NPRWMAX ) число строк в решетке процессов.
Важнейшая функция подпрограммы BSTPAR9 заключается в выводе и запоминании в файлах результатов таймирования решения задачи при разных параметрах распараллеливания, а также в определении наилучшего (наименьшего) времени счета, полученного в данном запуске. Это наименьшее время запоминается в некотором системном файле и выдается пользователю вместе с набором значений параметров рапараллеливания, при которых оно было достигнуто.
Нами проводились расчеты на суперкомпьютере СКИФ с использованием описанных подпрограмм для матриц разных размеров. Рассмотрим, например, результаты таймирования, полученные при решении системы уравнений с помощью подпрограммы PDGESV с матрицей порядка N = 7000 и при использовании восьми параллельных процессоров ( NPROC = 8 ).
При этом перебирались все возможные для этого случая решетки процессов:
NPROW = 1 , NPCOL = 8
NPROW = 2 , NPCOL = 4
NPROW = 4 , NPCOL = 2
NPROW = 8 , NPCOL = 1
При этом для каждой из решеток осуществлялся перебор размеров блоков матрицы от NBMIN = 2 до NBMAX = 512 ( DNB = 4 ).
Наилучший результат был получен для решетки NPROW = 2 и NPCOL = 4
при значении NB = 14(18). Значение минимального времени счета составило
при этом t ≈ 4 сек.
Наихудший результат был получен при NPROW = 8, NPCOL = 1 и
NB = 254.
Значение максимального времени счета составило t ≈ 7,8 сек.
Это показывает, что при неправильном выборе параметров распараллеливания
производительность может ухудшиться почти в 2 раза.
Этот эксперимент показал, что для таких задач предпочтителен выбор решетки, близкой к квадратной, а NB не следует выбирать слишком большим ( NB < 32 ).
Кроме того, построенные графики зависимости времени решения ( t ) от величины блока матрицы ( NB ) для всех четырех вариантов решеток процессов показали, что начиная с NB ≈ 50 до NB = 254 наблюдается почти линейный рост времени решения t. Затем при NB = 258 во всех четырех случаях происходит резкое падение (уменьшение) времени решения на ( 0,8 сек; 1,1 сек; 1,35 сек; 1,7 сек ). При дальнейшем увеличении NB опять происходит линейное увеличение времени, однако, графики более пологие, чем в предыдущем случае.
Посмотреть общий вид указанных графиков можно здесь gf_gesv.xls. А в следующих файлах более подробно изображены начальная (graf2.xls) и средняя (graf3.xls) части этих графиков. Т.е. для построения графиков использовались возможности программной системы EXCEL.
Приведем здесь также ссылки на графики, построенные по результатам аналогичных ( в смысле цикличности ) вычислительных экспериментов с разными видами матриц для задач на решение систем линейных уравнений, на вычисление собственных значений в линейной и обобщенной проблемах и на вычисление сингулярных чисел матриц: gf_posv.xls, gf_syev1.xls, gf_sygv1.xls, gf_geev1.xls, gf_gesvd1.xls
Ниже представлена сводная таблица полученных результатов для матриц порядка N = 7000 и при использовании 8 параллельных процессов.
Имя п/п-мы | NPROW | NPCOL | NB | t_minim,сек | _________________________________________________ PDGESV | 2 | 4 | 14 | 4.01 | _________________________________________________ PDPOSV | 4 | 2 | 120 | 2.58 | _________________________________________________ PDGEEV1 | 4 | 2 | 80 | 209.0 | _________________________________________________ PDSYEV1 | 2 | 4 | 30 | 72.4 | _________________________________________________ PDSYGV1 | 2 | 4 | 30 | 90.3 | _________________________________________________ PDGESVD1 | 2 | 4 | 42 | 262.0 |
Проведенные расчеты показывают, что характер графиков различен для разных видов задач. Тем не менее, можно заметить, что для больших матриц (N = 7000) лучшее время достигается при решетке процессов, близкой к квадратной, и при выборе 10 < NB < 120
3. Архивная часть подсистемы подбора параметров
Помимо того, что подсистема позволяет пользователю выдать на печать и/или запомнить в любых, указанных им, файлах как входные данные, так и полученные результаты, она автоматически запоминает результаты таймирования в специальных системных каталогах и файлах.
Это может обеспечить общий доступ к полученным результатам таймирования другим пользователям на данной вычислительной системе (установке).
Принцип организации такого системного архива прост. Для каждой
подпрограммы Комплекса, с которой выполняется таймирование, заводится
отдельный подкаталог с именем этой подпрограммы, куда помещаются файлы с результатами
таймирования данной подпрограммы.
В результате таймирования (каждого отдельного запуска подпрограммы BSTPAR9)
строится системный файл, содержащий вычисленное наилучшее время счета,
полученное в этом запуске, а также параметры распараллеливания, при
которых оно было получено. Имя такого системного файла формируется
автоматически и строится на основании следующего правила.
Общая структура имени такова:
_N1_N2_D
где N1 - порядок исходной матрицы,
N2 - число используемых параллельных процессоров,
D - шестизначное число, обозначающее дату запуска задачи на счет
(например, 011212 - означает первое декабря 2012 года)
Начальным символом имени служит "_" (подчерк), такие же символы разделяют и указанные три части имени.
При большом количестве запусков на таймирование результатов счета, такая форма имени системных файлов позволяет легко сориентироваться при поисках необходимого результата таймирования, просто посмотрев содержимое каталога с именем выбранной целевой подпрограммы Комплекса.