Наши журналы
Опубликовать статью Вход и регистрация
Расширенный поиск
Разделы статьи

ИЗ ОПЫТА ОБУЧЕНИЯ РАСПАРАЛЛЕЛИВАНИЮ ВЫЧИСЛЕНИЙ (МЕТОДИЧЕСКИЕ ЗАМЕТКИ)

Научная статья
Бурова И.Г.
Кальницкая М.А.
Малевич А.В.
Мирошниченко И.Д.
Жилин Д.Е.
DOI:
https://doi.org/10.23670/IRJ.2018.73.7.028
Выпуск: № 7 (73), 2018
Опубликована:
2018/07/18
PDF

ИЗ ОПЫТА ОБУЧЕНИЯ РАСПАРАЛЛЕЛИВАНИЮ ВЫЧИСЛЕНИЙ (МЕТОДИЧЕСКИЕ ЗАМЕТКИ)

Научная статья

Бурова И.Г.1, *, Кальницкая М.А.2, Малевич А.В.3, Мирошниченко И.Д.4, Жилин Д.Е.5

1 ORCID: 0000-0002-8743-1377;

 2 ORCID: 0000-0001-5671-5070;

3 ORCID: 0000-0003-0753-4621;

4 ORCID: 0000-0001-6479-1428;

5 ORCID: 0000-0002-8420-1023,

1, 2, 3, 4, 5 Санкт-Петербургский государственный университет, Санкт-Петербург, Россия

* Корреспондирующий автор (i.g.burova[at]spbu.ru)

Аннотация

Обсуждаются основные моменты по обучению практическому распараллеливанию вычислений на примере вычисления наибольшего по модулю собственного числа вещественной матрицы. Приводится краткое изложение степенного метода. Распараллеливание вычислений предполагается проводить с применением технологии OpenMP. Приложения предполагается разрабатывать в среде Visual Studio (используя Visual C++) для Windows. Приведены фрагменты программ и вариант задания для самостоятельной работы. Обсуждаются вопросы контроля правильности результата.

Ключевые слова: распараллеливание вычислений, OpenMP, степенной метод. 

FROM EXPERIENCE OF TRAINING IN CALCULATIONS PARALLELING (METHODOLOGICAL NOTES)

Research article

Burova I.G.1, *, Kal’nitskaya M.A.2, Malevich A.V.3, Miroshnichenko I.D.4, Zhilin D.E.5

1 ORCID: 0000-0002-8743-1377;

2ORCID: 0000-0001-5671-5070;

3 ORCID: 0000-0003-0753-4621;

4 ORCID: 0000-0001-6479-1428;

5 ORCID: 0000-0002-8420-1023,

1, 2, 3, 4, 5 Saint-Petersburg State University, St. Petersburg, Russia

* Corresponding author (i.g.burova[at]spbu.ru)

Abstract

The main issues on learning practical calculation paralleling on the example of computing the largest eigenvalue of a real matrix by modulus are discussed in the paper. A brief description of the power method is also given. Calculation paralleling is supposed to be carried out with the use of OpenMP technology. Applications are supposed to be developed in the Visual Studio environment (using Visual C++) for Windows OS. The fragments of the programs and the options of the task for independent work are given. The issues of control over the correctness of the result are discussed.

Keywords: computations paralleling, OpenMP, power method.

Введение

Текущие результаты и перспективы развития суперкомпьютерного образования в России изложены в работе [1]. Современное суперкомпьютерное образование невозможно без освоения обучающимися основ параллельного программирования [2]. Более того, через несколько лет программист, не владеющий техникой распараллеливания, может считаться компьютерно неграмотным. В настоящее время существует большое количество книг и статей, посвященных распараллеливанию вычислений. Одним из современных направлений распараллеливания является распараллеливание на гибридных системах [18], [19], что предполагает дополнительное распараллеливание в OpenMP.

С точки зрения обучения технологии распараллеливания OpenMP является наиболее простой и доступной средой. Среди книг по технологии OpenMP наиболее привлекательной по количеству примеров использования директив OpenMP следует отметить книгу [20]. Важное место в процессе обучения имеет достаточное количество заданий по распараллеливанию. В данной статье хочется поделиться особенностями проведения практического занятия по распараллеливанию в OpenMP на примере вычисления наибольшего по модулю собственного числа матрицы при помощи последовательных итераций (другое название - степенной метод). В следующих разделах будут приведены основные теоретические сведения по вычислению наибольшего собственного числа матрицы степенным методом и особенности распараллеливания алгоритма. Предполагается, что обучающиеся владеют навыками программирования в С++. Приложения удобно  разрабатывать в среде Visual Studio (используя Visual C++) для Windows.

Вычисление наибольшего собственного числа матрицы степенным методом

Наибольшее по модулю собственное число матрицы  может быть вычислено различными методами, в том числе, итерационными. Одним из наиболее простых и легко алгоритмически реализуемых методов является степенной метод [21]. Пусть A – вещественная матрица с элементами 24-07-2018 11-38-37 предполагаем, что собственные числа вещественные, простые и наибольшее по модулю собственное число 24-07-2018 11-39-39  строго больше всех остальных: 24-07-2018 11-39-52. Возьмем произвольный вектор 24-07-2018 11-40-46 c  вещественными элементами и построим последовательность:

24-07-2018 11-41-27   (1)

При 24-07-2018 11-42-20 отношение компонент векторов 24-07-2018 11-43-03 стремится к наибольшему по модулю собственному числу:

24-07-2018 11-43-53   (2)

Для контроля вычислений можно вычислять 24-07-2018 11-39-39 при 24-07-2018 11-45-08 по формуле (2), при этом необходимо выполнить 24-07-2018 11-45-43  мультипликативных операций при последовательном умножении матрицы на вектор: 24-07-2018 11-45-55. Для ускорения вычислений можно использовать возведение матрицы в степень: Am. При этом следует напомнить суть алгоритма сдваивания. Заметим, также что если элементы матрицы одного знака, то компоненты вектора Yk растут и в процессе вычислений приходится  (периодически, через некоторое количество итераций) нормировать вектор Yk. Для ускорения сходимости степенного метода можно использовать различные приемы, например, скалярное произведение [21].

Отметим, что важным моментом в обучении является мотивация. Степенной метод обычно изучают в курсе численных методов на младших курсах бакалавриата. Ко времени изучения основ распараллеливания некоторые студенты могут забыть для решения каких задач необходимо знать величину наибольшего по модулю собственного числа. Поэтому следует напомнить, что при решении систем линейных алгебраических уравнений методом простой итерации нужно быть уверенным, что модуль наибольшего собственного числа матрицы меньше единицы. Наибольшее собственное число матрицы часто используется при вычислении числа обусловленности. Нужно также напомнить о применяемых нормах. А именно, матричная норма должна быть согласована и подчинена некоторой векторной норме (см. [21]). Для контроля правильности вычисления наибольшего собственного числа можно использовать теорему Гершгорина или теорему об оценке спектрального радиуса матрицы через норму матрицы [21].

О распараллеливании вычислений

Для распараллеливания в OpenMP важно уметь распараллеливать циклы и работать с секциями. Для вычислений по формуле (1) необходимо уметь распараллеливать умножение матрицы на вектор. Как известно, распараллеливание на несколько потоков требует существенных временных затрат, что можно сравнить по длительности с выполнением 2000 мультипликативных операций. Поэтому умножение матрицы на вектор будет эффективно при достаточно большом n. Рекомендуется разработать последовательный алгоритм умножения матрицы на вектор. Для разработки параллельного алгоритма лучше всего использовать информацию из книг Антонова А.С. [17], [20]. При небольшом значении n, например, n=4 следует сравнить результаты вычислений, полученные при последовательном и параллельном вычислении. Первым упражнением по распараллеливанию следует сделать теоретическое определение минимального n, для которого распараллеливание дает ускорение, далее следует выполнить эксперимент по распараллеливанию и сравнить теоретические и практические результаты. После этого можно разработать программу численного вычисления наибольшего по модулю собственного числа матрицы. Далее следует построить таблицу, в которой первая строка – размер матрицы, вторая строка – ускорение.

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

Наиболее интересные программы были предложены студентами СПбГУ Зиминым Г.А. (Листинг 1) и Малькевичем С.В. (Листинг 2). Ниже приведем фрагменты программ.

#pragma omp parallel num_threads (4) shared(matrix, result, vector)

if (n > 200) { int i, j;   double sum; #pragma omp for schedule(static)  private(i, j, sum) for (i = 0; i < n; ++i) { sum = 0.0; for (j = 0; j < n; ++j) {sum += matrix[i][j] * vector[j]; } result[i] = sum; }

Листинг 1 – Умножение матрицы на вектор (#pragma omp for)

 

Студент Малькевич С. В. для параллельного умножения матрицы на вектор использует директиву sections.

#pragma omp parallel sections { #pragma omp section { for (int i = 0; i < 500; i++) { A_y[i] = 0; for (int j = 0; j < 1000; j++) { A_y[i] = A_y[i] + A[i][j] * y[j]; } } } #pragma omp section { for (int i = 500; i < 1000; i++) { A_y[i] = 0; for (int j = 0; j < 1000; j++) { A_y[i] = A_y[i] + A[i][j] * y[j]; } } }

Листинг 2 – Умножение матрицы на вектор (#pragma omp parallel sections)

Для самостоятельной работы студентам нужно выдать задания, где указан алгоритм построения матрицы с вещественными элементами, у которой собственные числа вещественные и простые. Для этого можно использовать  симметричные матрицы с диагональным преобладанием, например, c такими элементами: 24-07-2018 11-53-30 если 24-07-2018 11-54-11. В задании можно предложить следующие упражнения: 1. Разработать и отладить программу численного вычисления наибольшего по модулю собственного числа последовательным алгоритмом. 2. Разработать и отладить программу численного вычисления наибольшего по модулю собственного числа степенным методом распараллеливая  циклы. 3. Разработать и отладить программу численного вычисления наибольшего по модулю собственного числа применяя распараллеливание по секциям. 4. Вычислить ускорение. При этом следует напомнить, что ускорение вычислений находим как отношение времени выполнения последовательной программы (причем наиболее эффективной)  ко времени выполнения параллельной программы.

Заключение

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

Конфликт интересов Не указан. Conflict of Interest None declared.

Список литературы / References

  1. Воеводин Вл. В. Развитие системы суперкомпьютерного образования в России: текущие результаты и перспективы / Вл. В. Воеводин, В. П. Гергель, Л. Б. Соколинский и др. // Вестник Нижегородского университета. – 2012. – № 4. – С.203–
  2. Воеводин В. В. Параллельные вычисления. / В. В. Воеводин, Вл. В. Воеводин. – СПб. : БХВ-Петербург, 2002. – 608 с.
  3. Бахтин В. А. Автоматическое распараллеливание последовательных программ для многоядерных кластеров / В. А. Бахтин, М. С. Клинов, В. А. Крюков и др. // Труды Международной научной конференции «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи» (20-25 сентября 2010 г., г. Новороссийск). – М. : Издательство Московского университета, 2010. – С. 12–15.
  4. Воеводин Вл. В. Решение больших задач в распределенных вычислительных средах. / Вл. В. Воеводин // Автоматика и Телемеханика. – 2007. №5. – С. 32–45.
  5. Старченко А. В. Практикум по методам параллельных вычислений / А. В. Старченко, Е. А. Данилкин, В. И. Лаева и др. // М. : Издательство МГУ, серия «Суперкомпьютерное образование», 2010. – 200 с.
  6. Гурьева Я. Л. О некоторых параллельных методах и технологиях декомпозиции областей / Я. Л. Гурьева, В. П Ильин // Записки научных семинаров Санкт-Петербургского отделения математического института им. В.А. Стеклова РАН. – – Т. 428. – № 27. – С. 89–106.
  7. Голубева Я. В. Разработка и исследование алгоритмов балансировки нагрузки в параллельной реализации метода ветвей и границ / Я. В. Голубева // Современные информационные технологии и ИТ-образование. – – Т. 2. – № 11. – С. 423–429.
  8. Бененсон М. З. Использование методов параллельного программирования для решения систем линейных алгебраических уравнений / М. З. Бененсон // Вопросы радиоэлектроники. – – № 7. – С. 100–102.
  9. Зонов А. В. Особенности метода конечных элементов при реализации параллельной вычислительной схемы для расчета строительных конструкций / А. В. Зонов, А. С. Кропачева // Сборник «ОБЩЕСТВО, НАУКА, ИННОВАЦИИ (НПК-2016)» Сборник статей 2-е издание, исправленное и дополненное. – Вятский государственный университет. – – С. 557–561.
  10. Lamas Daviña A. MPI-CUDA parallel linear solvers for block-tridiagonal matrices in the context of SLEPc's eigensolvers / A. Lamas Daviña, J. E. Roman // Parallel Computing 74. – – P. 118–135.
  11. Mahfoudhi R. High performance recursive LU factorization for multicore systems / R. Mahfoudhi // Proceedings of IEEE/ACS International Conference on Computer Systems and Applications, AICCSA – 2017-October. – – P. 668–674.
  12. Nebot-Gil I. Diagonalization of large matrices: A new parallel algorithm / I. Nebot-Gil // Journal of Chemical Theory and Computation 11(2). – – P. 472–483.
  13. Ekström S.-E. A matrix-less and parallel interpolation–extrapolation algorithm for computing the eigenvalues of preconditioned banded symmetric / S.-E. Ekström, C. Garoni // Toeplitz matrices Numerical Algorithms. – – P. 1–30.
  14. Myllykoski M. A task-based algorithm for reordering the eigenvalues of a matrix in real schur form / M. Myllykoski // Lecture Notes in Computer Science //including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics 10777 LNCS. – – P. 207–216.
  15. Rusu I. A performance analysis of parallel eigensolvers for large dense symmetric matrices / I. Rusu, S.-G. Pentiuc, C. Turcu and others // 18th International Conference on System Theory, Control and Computing, ICSTCC 2014 6982488. – – P. 633–638.
  16. Tang P. T. P. A new highly parallel non-Hermitian eigensolver / P. T. P. Tang, J. Kestyn, E. Polizzi // Simulation Series 46(5). – – P. 1–9.
  17. Антонов А. С. Технологии параллельного программирования MPI и OpenMP: учеб. пособие. Предисл.: В. А. Садовничий. / А. С. Антонов ; МГУ – М. : Издательство Московского университета, 2012. – 344 с.
  18. Бахтин В. А. Использование языка Fortran DVMH для решения задач гидродинамики на высокопроизводительных гибридных вычислительных системах / В. А. Бахтин, М. С. Клинов, В. А. Крюков и др. // Вестник Южно-Уральского государственного университета. Серия «Вычислительная математика и информатика». – 2013. – Т. 2. – № – С. 106–120.
  19. Бахтин В. А. Использование языка Fortran DVMH для решения задач гидродинамики на высокопроизводительных гибридных вычислительных системах / В. А. Бахтин, М. С. Клинов, В. А. Крюков и др. // Труды международной научной конференции Параллельные вычислительные технологии (ПаВТ'2013) // Челябинск : Издательский центр ЮУрГУ, 2013. – С.58–
  20. Антонов А. С. Параллельное программирование с использованием технологии OpenMP: учебное пособие. / А. С. Антонов // М. : Издательство МГУ, 2009. – 77с.
  21. Фаддеев Д.К. Вычислительные методы линейной алгебры. / Д. К. Фаддеев, В. Н. Фаддеева // М. : Физматгиз, 1960. – 656с.

Список литературы на английском языке / References in English

  1. Voevodin Vl. V. Razvitie sistemy` superkomp`yuternogo obrazovaniya v Rossii: tekushhie rezul`taty` i perspektivy` [Development of the system of supercomputer education in Russia: current results and prospects] / Vl. V. Voevodin, V. P. Gergel`, L. B. Sokolinskij and others // Vestnik Nizhegorodskogo universiteta [Bulletin of the University of Nizhny Novgorod]. – 2012. – № 4. – P. 203–209. [in Russian]
  2. Voevodin V. V. Parallel`ny`e vy`chisleniya [Parallel computing]. / V. V. Voevodin, Vl. V. Voevodin – SPb. : BXV-Peterburg, 2002. – 608 p. [in Russian]
  3. Baxtin V. A. Avtomaticheskoe rasparallelivanie posledovatel`ny`x programm dlya mnogoyaderny`x klasterov [Automatic parallelization of sequential programs for multi-core clusters] / V. A. Baxtin, M. S. Klinov, V. A. Kryukov and others // Trudy` Mezhdunarodnoj nauchnoj konferencii «Nauchny`j servis v seti Internet: superkomp`yuterny`e centry` i zadachi» (20-25 sentyabrya 2010 g., g. Novorossijsk) [Proceedings of the International Scientific Conference "Scientific Service in the Internet: Supercomputer Centers and Tasks" (September 20-25, 2010, Novorossiysk)]. – M. : Izdatel`stvo Moskovskogo universiteta, 2010. – P. 12–15. [in Russian]
  4. Voevodin Vl. V. Reshenie bol`shix zadach v raspredelenny`x vy`chislitel`ny`x sredax [Solving large problems in distributed computing environments] / Vl. V. Voevodin // Avtomatika i Telemexanika [Automation and Telemechanics]. – 2007. – №5. – P. 32–45. [in Russian]
  5. Starchenko A. V. Praktikum po metodam parallel`ny`x vy`chislenij [Practice on methods of parallel computing] / A. V. Starchenko, E. A. Danilkin, V. I. Laeva and others // M. : Izdatel`stvo MGU, seriya «Superkomp`yuternoe obrazovanie» [series "Supercomputer Education"], 2010. – 200 p. [in Russian]
  6. Gur`eva Ya. L. O nekotory`x parallel`ny`x metodax i texnologiyax dekompozicii oblastej [About some parallel methods and technologies of domain decomposition] / Ya. L. Gur`eva, V. P Il`in // Zapiski nauchny`x seminarov Sankt-Peterburgskogo otdeleniya matematicheskogo instituta im. V.A. Steklova RAN [Notes of scientific seminars of the St. Petersburg Department of the Math. V.A. Of the Russian Academy of Sciences]. – 2014. – V. 428. – № 27. – P. 89–106. [in Russian]
  7. Golubeva Ya. V. Razrabotka i issledovanie algoritmov balansirovki nagruzki v parallel`noj realizacii metoda vetvej i granicz [Development and study of load balancing algorithms in the parallel implementation of the branch and boundary method] / Ya. V. Golubeva // Sovremenny`e informacionny`e texnologii i IT-obrazovanie [Modern Information Technologies and IT Education]. – 2015. – V. 2. – № 11. – P. 423–429. [in Russian]
  8. Benenson M. Z. Ispol`zovanie metodov parallel`nogo programmirovaniya dlya resheniya sistem linejny`x algebraicheskix uravnenij [The use of parallel programming methods for solving systems of linear algebraic equations] / M. Z. Benenson // Voprosy` radioe`lektroniki [Questions of radio electronics]. – 2016. – № 7. – P. 100–102. [in Russian]
  9. Zonov A. V. Osobennosti metoda konechny`x e`lementov pri realizacii parallel`noj vy`chislitel`noj sxemy` dlya rascheta stroitel`ny`x konstrukcij [Features of the finite element method for implementing a parallel computing scheme for the calculation of building structures] / A. V. Zonov, A. S. Kropacheva // Sbornik «OBShhESTVO, NAUKA, INNOVACII (NPK-2016)» Sbornik statej 2-e izdanie, ispravlennoe i dopolnennoe [Collection "SOCIETY, SCIENCE, INNOVATION (NPK-2016)" Collection of articles 2nd edition, revised and enlarged.]. – Vyatskij gosudarstvenny`j universitet [Vyatka State University]. – 2016. – P. 557–561. [in Russian]
  10. Lamas Daviña A. MPI-CUDA parallel linear solvers for block-tridiagonal matrices in the context of SLEPc's eigensolvers / A. Lamas Daviña, J. E. Roman // Parallel Computing 74. – 2018. – P. 118–135.
  11. Mahfoudhi R. High performance recursive LU factorization for multicore systems / R. Mahfoudhi // Proceedings of IEEE/ACS International Conference on Computer Systems and Applications, AICCSA – 2017-October. – 2018. – P. 668–674.
  12. Nebot-Gil I. Diagonalization of large matrices: A new parallel algorithm / I. Nebot-Gil // Journal of Chemical Theory and Computation 11(2). – 2015. – P. 472–483.
  13. Ekström, S.-E. A matrix-less and parallel interpolation–extrapolation algorithm for computing the eigenvalues of preconditioned banded symmetric / S.-E. Ekström, C. Garoni // Toeplitz matrices Numerical Algorithms. – 2018. – P. 1–30.
  14. Myllykoski M. A task-based algorithm for reordering the eigenvalues of a matrix in real schur form / M. Myllykoski // Lecture Notes in Computer Science //including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics 10777 LNCS. – 2018. – P. 207–216.
  15. Rusu I. A performance analysis of parallel eigensolvers for large dense symmetric matrices / I. Rusu, S.-G. Pentiuc, C. Turcu and others // 18th International Conference on System Theory, Control and Computing, ICSTCC 2014 6982488. – 2014. – P. 633–638.
  16. Tang P. T. P. A new highly parallel non-Hermitian eigensolver / P. T. P. Tang, J. Kestyn, E. Polizzi // Simulation Series 46(5). – 2014. – P. 1–9.
  17. Antonov A. S. Texnologii parallel`nogo programmirovaniya MPI i OpenMP: ucheb. posobie. Predisl.: V. A. Sadovnichij. [Parallel Programming Technologies MPI and OpenMP: Proc. allowance] / A. S. Antonov; MGU – M. : Izdatel`stvo Moskovskogo universiteta [Publishing house of Moscow University], 2012. – 344 p. [in Russian]
  18. Baxtin V. A. Ispol`zovanie yazy`ka Fortran DVMH dlya resheniya zadach gidrodinamiki na vy`sokoproizvoditel`ny`x gibridny`x vy`chislitel`ny`x sistemax [Using the Fortran DVMH language to solve hydrodynamic problems on high-performance hybrid computing systems] / V. A. Baxtin, M. S. Klinov, V. A. Kryukov and others // Vestnik Yuzhno-Ural`skogo gosudarstvennogo universiteta. Seriya «Vy`chislitel`naya matematika i informatika» [Bulletin of the South Ural State University. Series "Computational Mathematics and Computer Science"]. – 2013. – V. 2. – № 3. – P. 106–120. [in Russian]
  19. Baxtin V. A. Ispol`zovanie yazy`ka Fortran DVMH dlya resheniya zadach gidrodinamiki na vy`sokoproizvoditel`ny`x gibridny`x vy`chislitel`ny`x sistemax [Using the Fortran DVMH language to solve hydrodynamic problems on high-performance hybrid computing systems] / V. A. Baxtin, M. S. Klinov, V. A. Kryukov and others // Trudy` mezhdunarodnoj nauchnoj konferencii Parallel`ny`e vy`chislitel`ny`e texnologii (PaVT'2013) [Proceedings of the International Scientific Conference Parallel Computing Technologies (PaCT'2013)] // Chelyabinsk : Izdatel`skij centr YuUrGU [Publishing Center of South Ural State University], 2013. – P. 58–67. [in Russian]
  20. Antonov A. S. Parallel`noe programmirovanie s ispol`zovaniem texnologii OpenMP: uchebnoe posobie [Parallel Programming Using OpenMP Technology: A Tutorial / A. S. Antonov // M. : Izdatel`stvo MGU [Publishing house of Moscow State University], 2009. – 77 p. [in Russian]
  21. Faddeev D.K. Vy`chislitel`ny`e metody` linejnoj algebry` [Computational methods of linear algebra] / D. K. Faddeev, V. N. Faddeeva // M. : Fizmatgiz, 1960. – 656 p. [in Russian]