Из опыта обучения распараллеливанию вычислений (методические заметки)

Размещено на http://www.allbest.ru/

Санкт-Петербургский государственный университет

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

Бурова И.Г., Кальницкая М.А., Малевич А.В.,

Мирошниченко И.Д., Жилин Д.Е.

Аннотация

распараллеливание вычисление матрица приложение

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

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

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 - вещественная матрица с элементами предполагаем, что собственные числа вещественные, простые и наибольшее по модулю собственное число строго больше всех остальных: . Возьмем произвольный вектор c вещественными элементами и построим последовательность:

(1)

При отношение компонент векторов стремится к наибольшему по модулю собственному числу:

(2)

Для контроля вычислений можно вычислять при по формуле (2), при этом необходимо выполнить мультипликативных операций при последовательном умножении матрицы на вектор: . Для ускорения вычислений можно использовать возведение матрицы в степень: A^m. При этом следует напомнить суть алгоритма сдваивания. Заметим, также что если элементы матрицы одного знака, то компоненты вектора Y_k растут и в процессе вычислений приходится (периодически, через некоторое количество итераций) нормировать вектор Y_k. Для ускорения сходимости степенного метода можно использовать различные приемы, например, скалярное произведение [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 такими элементами: если . В задании можно предложить следующие упражнения: 1. Разработать и отладить программу численного вычисления наибольшего по модулю собственного числа последовательным алгоритмом. 2. Разработать и отладить программу численного вычисления наибольшего по модулю собственного числа степенным методом распараллеливая циклы. 3. Разработать и отладить программу численного вычисления наибольшего по модулю собственного числа применяя распараллеливание по секциям. 4. Вычислить ускорение. При этом следует напомнить, что ускорение вычислений находим как отношение времени выполнения последовательной программы (причем наиболее эффективной) ко времени выполнения параллельной программы.

Заключение

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

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

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 с.

Размещено на Allbest.ru