Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 1,021

ИССЛЕДОВАНИЕ ОПТИМАЛЬНОЙ ФОРМЫ РАЗБИЕНИЯ ДАННЫХ ДЛЯ УМНОЖЕНИЯ МАТРИЦ НА ТРЕХ ГЕТЕРОГЕННЫХ ПРОЦЕССОРАХ С ПОЛНОСВЯЗНОЙ ТОПОЛОГИЕЙ И РАЗЛИЧНЫМИ ПРОПУСКНЫМИ СПОСОБНОСТЯМИ

Клюева Е.Г. 1 Адамов А.А. 2 Оспанова А.Е. 1 Сницарь Л.Р. 1 Кулбаева Л.Н. 1
1 Карагандинский государственный технический университет
2 Евразийский национальный университет имени Л.Н. Гумилева
Данная статья посвящена исследованию оптимальной формы разбиения элементов матрицы между тремя абстрактными гетерогенными процессорами при выполнении операции умножения. Использование в исследовании абстрактной модели процессора позволяет применять результаты исследования для систем с различной архитектурой. Для определения оптимальной формы разбиения в работе используются непрямоугольные формы-кандидаты, выявленные в работе Эшли Дэ Флюмьер в результате применения техники перераспределения элементов матрицы между процессорами «Push»: Square Corner, Rectangle Corner, Square Rectangle, Block Rectangle, L-Rectangle, Traditional 1D Rectangular. Оптимальность форм определяется для двух классов алгоритмов матричного умножения: последовательной коммуникации с барьером и параллельной коммуникации с барьером. Для оценки коммуникационной трудоемкости алгоритмов используется модель Хокни. В статье построены математические модели времени выполнения алгоритма для каждой рассматриваемой формы-кандидата в обоих используемых алгоритмах. Сделаны выводы о том, что формы разбиения данных Rectangle Corner и Traditional 1D Rectangular не могут быть оптимальными ни при одном наборе параметров, формы Square Corner, Square Rectangle, Block Rectangle, L-Rectangle могут быть оптимальными при определенных наборах параметров.
параллельные вычисления
умножение матриц
разбиение данных
гетерогенные параллельные системы
модель Хокни
алгоритмы последовательной коммуникации с барьером
алгоритмы параллельной коммуникации с барьером
1. Beaumont O., Boudet V., Legrand A., Rastello F., Robert Y. Heterogeneous matrix-matrix multiplication or partitioning a square into rectangles: Np-completeness and approximation algorithms. Parallel and Distributed Processing, 2001. Proceedings. Ninth Euromicro Workshop, IEEE. 2001. Р. 298–305.
2. Lastovetsky A.L. On grid-based matrix partitioning for heterogeneous processors. ISPDC. 2007. Р. 383–390.
3. Clarke D., Lastovetsky A., Rychkov V. Column-based matrix partitioning for parallel matrix multiplication on heterogeneous processors based on functional performance models. Euro-Par 2011: Parallel Processing Workshops, Springer. 2012. Р. 450–459.
4. DeFlumere A., Lastovetsky A. Optimal data partitioning shape for matrix multiplication on three fully connected heterogeneous processors, Euro-Par 2014WS, HeteroPar 2014 – Twelfth International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms. 2014. Р. 201–214.
5. DeFlumere A. Optimal Partitioning for Parallel Matrix Computation on a Small Number of Abstract Heterogeneous Processors. PhD thesis, University College Dublin. 2014. 161 р.
6. Zhong Z., Rychkov V., Lastovetsky A. Data partitioning on heterogeneous multicore platforms. Cluster Computing (CLUSTER), 2011 IEEE International Conference, IEEE. 2011. Р. 580–584.
7. Zhong Z., Rychkov V., Lastovetsky, A. Data partitioning on heterogeneous multicore and multi-gpu systems using functional performance models of data-parallel applications. Cluster Computing (CLUSTER), 2012 IEEE International Conference, IEEE. 2012. Р. 191–199.

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

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

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

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

Прямоугольные формы разбиения данных рассматривались в работах [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.

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


Библиографическая ссылка

Клюева Е.Г., Адамов А.А., Оспанова А.Е., Сницарь Л.Р., Кулбаева Л.Н. ИССЛЕДОВАНИЕ ОПТИМАЛЬНОЙ ФОРМЫ РАЗБИЕНИЯ ДАННЫХ ДЛЯ УМНОЖЕНИЯ МАТРИЦ НА ТРЕХ ГЕТЕРОГЕННЫХ ПРОЦЕССОРАХ С ПОЛНОСВЯЗНОЙ ТОПОЛОГИЕЙ И РАЗЛИЧНЫМИ ПРОПУСКНЫМИ СПОСОБНОСТЯМИ // Современные наукоемкие технологии. – 2019. – № 2. – С. 83-88;
URL: http://top-technologies.ru/ru/article/view?id=37413 (дата обращения: 30.11.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074