Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

STUDYING THE OPTIMAL FORM OF PARTITIONING THE DATA FOR THE MATRIX MULTIPLICATION ON THREE FULLY CONNECTED HETEROGENEOUS PROCESSORS WITH DIFFERENT BANDWIDTHS

Klyueva E.G. 1 Аdamov А.А. 2 Оspanova А.Е. 1 Snitsar L.R. 1 Кulbaeva L.N. 1
1 Karaganda State Technical University
2 Ural State Economic University
The paper presents the results of a study done to find the optimal forms of matrix element partitioning in three abstract heterogeneous processors when performing multiplication operations. An abstract processor model allows to applicate the research results in systems with different architectures. To determine the optimal partitioning form, in the work were used non-rectangular candidate forms identified by Ashley DeFlumere in her work as a result of applying the technology of redistribution of matrix elements between the processors «Push»: Square Corner, Rectangle Corner, Square Rectangle, Block Rectangle, L-Rectangle, Traditional 1D Rectangular. The optimality of forms is determined for two classes of matrix multiplication algorithms: Serial Communication with Barrier and Parallel Communication with Barrier. The Hockney model was used to evaluate the communication complexity of algorithms. Mathematical models of the algorithm execution time were introduced in the paper for each considered candidate form in both algorithms. The following conclusions were obtained: the Rectangle Corner and Traditional 1D Rectangular data partitioning forms cannot be optimal with any parameter set, the Square Corner, Square Rectangle, Block Rectangle, L-Rectangle forms can be optimal with certain parameter sets.
parallel computing
matrix multiplication
data partitioning
heterogeneous parallel systems
Hockney model
serial communication with barrier
parallel communication with barrier

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

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

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

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

Прямоугольные формы разбиения данных рассматривались в работах [1–3]. В работах [4, 5] было доказано, что при определенных соотношениях вычислительных мощностей процессоров оптимальными могут являться и непрямоугольные формы разбиения элементов матриц. Однако при этом не учитывалась разница пропускных способностей сетей передачи данных между вычислительными элементами.

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

Материалы и методы исследования

Для моделирования умножения матриц в данной работе используется абстрактная модель процессора, рассмотренная в работах [6, 7]. В работе [4] было доказано, что понятие абстрактного процессора, которое фокусируется главным образом на объеме коммуникаций и объеме вычислений, точно прогнозирует экспериментальную производительность множества процессоров и даже целых кластеров для матричных вычислений.

Для эффективного моделирования умножения матриц на трех абстрактных гетерогенных процессорах было сделано несколько допущений:

– в работе использованы квадратные исходные матрицы A, B и результирующая матрица С размером N×N элементов;

– элементы матрицы разделены между абстрактными процессорами P, R и S, пропорционально их вычислительным мощностям, которые определены отношением Pr : Rr : Sr, где P является самым мощным процессором и Sr = 1. T = Pr + Rr + Sr;

– процессоры объединены полносвязной топологией, с пропускными способностями сети передачи β1 между процессорами P и S, β2 между процессорами P и R, β3 между процессорами S и R;

– в качестве форм-кандидатов рассмотрены формы Square Corner (SC), Rectangle Corner (RC), Square Rectangle (SR), Block Rectangle (BR), L-Rectangle (LR), Traditional 1D Rectangular (TR), выявленные Эшли ДеФлумьер в работе [5, с. 77] в результате применения техники перераспределения элементов матрицы между процессорами «Push» (рис. 1):

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

klyev1.tif

Рис. 1. Формы-кандидаты, определенные как потенциально оптимальные для трехпроцессорных систем: 1) Square Corner; 2) Rectangle Corner; 3) Square Rectangle; 4) Block Rectangle; 5) L-Rectangle; 6) Traditional 1D Rectangular

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

Алгоритм последовательной коммуникации с барьером (Serial Communication with Barrier, SCB) – простой алгоритм матричного умножения, в котором все данные пересылаются процессорами последовательно, вычисления начинаются только после того, как все процессоры завершили передачу данных и выполняются параллельно (рис. 2).

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

klyev01.wmf (1)

где V – общее количество коммуникаций;

klyev02.wmf – время, необходимое процессору X для вычисления назначенной ему части матрицы С.

klyev2.tif

Рис. 2. Алгоритм последовательной коммуникации с барьером для процессоров P, R и S

Так как площадь матрицы и количество элементов, выделенных каждому процессору, пропорциональны его вычислительной мощности, параметр klyev03.wmf будет одинаков для всех рассматриваемых форм кандидатов и, соответственно, может не учитываться при сравнении времени выполнения алгоритма.

Определим время коммуникации Tcomm для каждой рассматриваемой формы согласно формуле (1).

SC: klyev04.wmf

SR: klyev05.wmf

BR: klyev06.wmf

LR: klyev07.wmf

TR: klyev08.wmf

Для формы Rectangle Corner оптимальный размер R и S будет являться комбинированной шириной N, что не может быть истиной исходя из классификации форм-кандидатов [5, с. 78]. В качестве альтернативы установим, что klyev09.wmf. Тогда

RC: klyev10.wmf

klyev11.wmf

Для облегчения анализа полученной математической модели избавимся от коэффициента β3, получив отношения пропускных способностей между вычислительными элементами klyev12.wmf. Таким образом, мы получаем четыре переменные.

Для выполнения теоретических расчетов было разработано программное обеспечение на языке программирования Java, позволяющее в текстовом виде или через web-интерфейс вводить исходные параметры klyev13.wmf и определять оптимальную форму разбиения данных (рис. 3).

klyev3a.tif

klyev3b.tif

Рис. 3. Пример программных расчетов при значениях Pr = 3, Rr = 2, klyev14.wmf, klyev15.wmf

Исходя из проведенного анализа полученных данных были сделаны следующие выводы. Для алгоритма SCB оптимальными могут являться формы разбиения элементов матрицы BR, LR, SC, SR. Форма LR оптимальна при значении коэффициента klyev16.wmf и примерно равных мощностях процессоров P и R, значительно превышающих мощность процессора S. Форма SR может являться оптимальной в случаях малых значений коэффициентов klyev17.wmf и мощностях процессоров P и R, значительно превышающих мощность процессора S. Во всех остальных случаях оптимальными являются формы BR и SC.

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

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

klyev4.tif

Рис. 4. Алгоритм параллельной коммуникации с барьером для процессоров P, R и S

Оценка времени выполнения алгоритма производится по формуле

klyev18.wmf (2)

где klyev19.wmf – объем данных, который должен быть передан процессором X.

Аналогично алгоритму SCB параметр klyev20.wmf может не учитываться в формулах, определение оптимальности форм будет произведено исходя из времени коммуникации Tcomm.

SC: klyev21.wmf

SR: klyev22.wmf

BR: klyev23.wmf

LR: klyev24.wmf

TR: klyev25.wmf

RC: klyev26.wmf

klyev27.wmf

По результатам, полученным с помощью разработанного програмного обеспечения, были сделаны следующие выводы. Как и в случае использования алгоритма SCB, оптимальными могут являться только формы BR, LR, SC, SR. LR оптимальна только при значениях коэффициентов klyev28.wmf = 0,1, klyev29.wmf и примерно равных мощностях процессоров P и R гораздо больших S. SR может являться оптимальной при klyev30.wmf и значениях мощностей процессоров P и R значительно превышающих мощность процессора S. В остальных случаях в зависимости от выбранных параметров оптимальными являются формы BR и SC.

Заключение

На основании полученных результатов можно сделать заключение, что, как и в случае трехпроцессорных систем с одинаковой пропускной способностью сетей, соединяющих вычислительные элементы, формы разбиения данных Rectangle Corner и Traditional 1D Rectangular не могут быть оптимальными ни при одном наборе параметров.

В отличие от результатов, полученных в работе [5, с. 85, 88], форма L-Rectangle может быть оптимальной при мощностях процессоров P и R, намного превышающих мощность процессора S и примерно равных друг другу в случае klyev31.wmf для алгоритма SCB и klyev32.wmf = 0,1 для алгоритма PCB. Однако в данных случаях нет смысла в использовании маломощного процессора S, и задача может быть решена на двух процессорах.

Форма Square Rectangle является оптимальной при малых значениях коэффициентов klyev33.wmf и мощностях процессоров P и R, значительно превышающих мощность процессора S. При таких исходных данных задача также может быть решена с использованием двух мощных процессоров.

В остальных случаях оптимальными в случае использования обоих алгоритмов в зависимости от значений коэффициентов klyev34.wmf являются формы Square Corner и Block Rectangle.

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