item | Сибирский аэрокосмический журнал ISSN 2712-8970

UDK 004.021 Doi: 10.31772/2587-6066-2020-21-1-28-33

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

Романова Д. С.

Сибирский федеральный университет, Российская Федерация, 660041, г. Красноярск, просп. Свободный, 79. E-mail: daryaooo@mail.ru

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

Ключевые слова: неограниченный параллелизм, матричное умножение, параллельное программирование.

References

1. Легалов А. И. Современные проблемы информатики и вычислительной техники:
учебное пособие. Сибирский федеральный университет. Томск : СПБ Графикс, 2012. 216 с.
2. Легалов А. И. Методы сортировки, полученные из анализа максимально параллельной
программы. Распределенные и кластерные вычисления // Избр. мат. 3 шк.-семинара. Ин-т
вычислит. моделир. СО РАН. Красноярск, 2004. С. 119–134.
3. Легалов А. И. Об управлении вычислениями в параллельных системах и языках
программирования // Научный вестник НГТУ. 2004. № 3 (18). С. 63–72.
4. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПб. : БХВ Петербург,
2002. 608 с.
5. Solomonik E., Demmel J. Communication-optimal parallel 2.5D matrix multiplication and
LU factorization algorithms. Department, University of California, Berkeley (February 2011)
[Электронный ресурс]. URL: http://www.eecs.berkeley.edu/Pubs/TechRpts/2011/EECS-2011-
10.html (дата обращения: 01.12.2019).
6. Dongarra J. J., Duff L. S., Sorensen D. C., Vorst H. A. V. Numerical Linear Algebra for
High Performance Computers (Software, Environments, Tools). Soc for Industrial & Applied.
1999. P. 120–125.
7. Гергель В. П., Фурсов В. А. Лекции по параллельным вычислениям. Самара : Изд-во
Самар. гос. аэрокосм. ун-та, 2009. 164 с.
8. Модель функционально-потоковых параллельных вычислений и язык
программирования «Пифагор». Распределенные и кластерные вычисления / А. И. Легалов, Ф.
А. Казаков, Д. А. Кузьмин, Д. В. Привалихин // Избранные материалы второй Школы
семинара. Институт вычислительного моделирования СО РАН. Красноярск, 2002. С. 101–
120.
9. Легалов А. И. Методы сортировки, полученные из анализа максимально параллельной
программы. Распределенные и кластерные вычисления. Избр. мат. 3 шк.-семинара. Ин-т
вычислит. моделир. СО РАН. Красноярск, 2004. С. 119–134.
10. Вирт Н. Алгоритмы и структуры данных. М. : Мир, 1989. 360 с.
11. Федотов И. Е. Модели параллельного программирования. М. : СОЛОН-ПРЕСС.
Москва, 2012. 384 с.
12. Legalov A. I., Nepomnyaschy O. V., Matkovsky I. V., Kropacheva M. S. Tail Recursion
Transformation in Functional Dataflow Parallel Programs // Automatic Control and Computer
Sciences. 2013. Vol. 47, No. 7. P. 366–372.
13. Миллер Р., Боксер Л. Последовательные и параллельные алгоритмы: Общий подход.
М. : БИНОМ. Лаборатория знаний, 2006. 406 с.
14. Лупин С. А., Посыпкин М. А. Технологии параллельного программирования. Серия:
Высшее образование. М. : Форум ; Инфра-М, 2008. 208 с.
15. Herlihy M. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc.,
San Francisco, CA, USA. 2008. 508 р.

Романова Дарья Сергеевна – аспирант, Сибирский федеральный университет.
daryaooo@mail.ru.

Сибирский государственный университет
науки и технологий имени академика М.Ф. Решетнева

Контакты

Контакты

Сибирский АЭРОКОСМИЧЕСКИЙ журнал

ISSN 2712-8970

Социальные сети