Параллельные алгоритмы и программные средства для уменьшения заполнения фактора симметричных разреженных матриц тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Пирова Анна Юрьевна

• Пирова Анна Юрьевна
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Пирова Анна Юрьевна

ВВЕДЕНИЕ

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

1. 1 Процесс численного моделирования, основанный на прямых методах решения СЛАУ

1.2 Методика сравнения эффективности решения задачи переупорядочения разреженных матриц

1.3 Математическая постановка задачи переупорядочения

1.4 Методы переупорядочения разреженных матриц

1.5 Программные средства для переупорядочения разреженных матриц

1.6 Выводы

2 МНОГОУРОВНЕВЫЙ МЕТОД ВЛОЖЕННЫХ СЕЧЕНИЙ

2.1 Общее описание метода

2.2 Основные алгоритмы

2.3 Выводы

3 ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ПЕРЕУПОРЯДОЧЕНИЯ РАЗРЕЖЕННЫХ МАТРИЦ

3. 1 Возможности для распараллеливания метода вложенных сечений

3.2 Параллельный алгоритм для систем с общей памятью

3.3 Параллельный алгоритм для систем с распределенной памятью

3.4 Алгоритм, совмещающий параллелизм на общей и распределенной памяти

3.5 Выводы

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

4.1 Требования к программным библиотекам

4.2 Основные проектные решения и высокоуровневая архитектура

4.3 Использование программного комплекса

4.4 Выводы

5 АНАЛИЗ И ТЕСТИРОВАНИЕ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ПЕРЕУПОРЯДОЧЕНИЯ

5.1 Методика проведения вычислительных экспериментов

5.2 Анализ эффективности применения различных алгоритмов в рамках многоуровневого метода вложенных сечений

5.3 Сравнение со сторонними библиотеками для переупорядочения разреженных матриц

5.4 Применение перестановок для решения СЛАУ c симметричной разреженной матрицей

5.5 Примеры решения практических задач

5.6 Рекомендации по настройке параметров переупорядочивателя

5.7 Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ ^ ПАРАМЕТРЫ ПЕРЕУПОРЯДОЧИВАТЕЛЯ DMORSY

Введение

Введение диссертации (часть автореферата) на тему «Параллельные алгоритмы и программные средства для уменьшения заполнения фактора симметричных разреженных матриц»

Актуальность темы исследования.

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

Алгоритмы прямого решения СЛАУ с симметричной действительной

разреженной матрицей могут быть построены с использованием LLT или LDLT

разложения (факторизации) матрицы системы, где L - треугольная матрица

(фактор), а D - диагональная матрица. Одной из основных проблем является

существенное (на несколько порядков) увеличение числа ненулевых элементов в

процессе факторизации - заполнение фактора. Заполнение значительно повышает

требования к объему необходимой оперативной памяти и увеличивает время

5

факторизации, что ограничивает применимость прямых методов для решения систем с большим числом неизвестных. Для уменьшения заполнения перед численной факторизацией применяется симметричное переупорядочение строк и столбцов исходной матрицы. Нахождение подходящей перестановки позволяет уменьшить число ненулевых элементов в факторе и, следовательно, сэкономить память и время при решении СЛАУ на разных этапах процесса численного моделирования.

Известно, что задача нахождения оптимальной перестановки, минимизирующей размер фактора, является NP-трудной (Yannakakis, 1981). На практике применяются эвристические методы, основанные на аппарате теории графов, которые позволяют находить приемлемое решение в смысле двух ключевых критериев - времени, затраченного на поиск перестановки, и числа ненулевых элементов в факторе. Наибольшее распространение получили схемы, основанные на многоуровневом методе вложенных сечений, и гибридные схемы, комбинирующие многоуровневый метод вложенных сечений и метод минимальной степени. Заметный вклад в развитие многоуровневых методов внесли Buluç A., Hendrickson B. и Leland R., Karypis G. и Kumar V., Meyerhenke H., Pelligrini F. и Chevalier С., Safro I., Sanders P. и Schulz Ch., Walshaw C. В России исследованиями в области переупорядочения разреженных матриц и решения разреженных СЛАУ занимались Бартенев Ю.Г., Батищев Д.И., Икрамов Х.Д., Ильин В.П., Капорин И.Е., Старостин Н.В., Тыртышников E.E., Якобовский М.В. и другие ученые.

Развитие вычислительной техники, связанное с распространением параллельных вычислительных систем в 1990-х годах, привлекло внимание исследователей к разработке параллельных алгоритмов переупорядочения и разделения матриц. Широкое распространение получили пакеты с открытым исходным кодом ParMETIS (G. Karypis, V. Kumar) и PT-Scotch (F. Pelligrini). В этих пакетах реализованы модификации многоуровневого метода вложенных сечений для систем с распределенной памятью. В 2015 г. G. Karypis и D. LaScalle

представили библиотеку mt-METIS - версию библиотеки ParMETIS, ориентированную на параллельные системы с общей памятью. Отметим также разработки группы P. Sanders и Ch. Schulz для задачи разделения матриц, реализованные в библиотеке ParHIP. Данная библиотека включает параллельную реализацию алгоритмов разделения графа для систем с общей и распределенной памятью, а также последовательную реализацию алгоритма переупорядочения. В открытых и коммерческих пакетах для решения СЛАУ, как правило, встроена реализация алгоритма переупорядочения и интерфейс для интеграции со сторонними библиотеками. В частности, коммерческий решатель MKL Pardiso содержит реализации алгоритмов переупорядочения, основанные на методе вложенных сечений из библиотеки METIS. Исходный код MKL Pardiso закрыт, и встроенный переупорядочиватель может использоваться только в составе решателя.

Несмотря на значительные достижения при создании параллельных переупорядочивателей, существуют открытые проблемы в области управления данными в процессе численного моделирования, основанного на прямом решении СЛАУ. Во-первых, представляет интерес разработка и исследование новых подходов к распараллеливанию вычислений в алгоритмах переупорядочения разреженных матриц. Также как для многих алгоритмов на графах, сложность разработки эффективных алгоритмов переупорядочения лежит в природе задачи и заключается в особенностях хранения и обработки данных. Параллелизм подобных алгоритмов ограничен ввиду следующих причин: низкая арифметическая интенсивность; нерегулярный доступ к памяти; отсутствие потенциала для векторизации вычислений; зависимости по данным. Актуальной задачей является создание гибких и эффективных параллельных алгоритмов, в которых задействован потенциал современных вычислительных систем за счет регулирования числа используемых процессов и потоков, при сохранении числа ненулевых элементов в факторе на уровне лучших программных разработок. Так, на сегодняшний день не представлено открытой реализации алгоритма

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

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

Указанные выше проблемы определяют актуальность темы диссертации.

Объект исследования. Объектом исследования является процесс численного моделирования на базе прямых методов решения СЛАУ с симметричной действительной разреженной матрицей.

Предмет исследования. Предметом исследования являются алгоритмы переупорядочения симметричных разреженных матриц, предназначенные для уменьшения заполнения фактора матриц в процессе прямого решения СЛАУ, и приводящие к сокращению времени решения СЛАУ прямыми методами и сокращению необходимого объема памяти для хранения фактора матрицы.

Цель диссертационной работы. Целью диссертационной работы является повышение эффективности процесса численного моделирования на базе прямых методов решения СЛАУ с симметричной действительной разреженной матрицей за счет применения параллельных алгоритмов переупорядочения разреженных матриц, уменьшающих заполнение фактора.

Достижение указанной цели предполагает решение следующих задач:

- Исследование проблемы повышения эффективности процесса численного моделирования на базе прямых методов решения СЛАУ на высокопроизводительных вычислительных системах за счет выбора алгоритма переупорядочения, уменьшающего заполнение фактора симметричной разреженной матрицы.

- Разработка методики сравнения эффективности решения задачи переупорядочения матриц в рамках процесса численного моделирования на базе прямых методов решения СЛАУ с симметричной разреженной матрицей.

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

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

- Интеграция разработанного программного обеспечения в решатель СЛАУ с открытым исходным кодом MUMPS.

- Экспериментальные исследования влияния выбора алгоритмов переупорядочения и их параметров на эффективность прямых методов решения

СЛАУ на высокопроизводительных вычислительных системах. Выработка методических рекомендаций по выбору алгоритмов и настройке их параметров.

Методы исследований. Для решения поставленных в диссертационной

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

Соответствие паспорту специальности. Предложенная методика сравнения эффективности решения задач переупорядочения на разных этапах процесса численного моделирования, а также разработанные и реализованные в диссертации параллельные алгоритмы переупорядочения разреженных матриц, обеспечивают рациональный выбор алгоритмов подготовки исходных данных для прямых методов решения СЛАУ с симметричной разреженной матрицей и позволяют повысить эффективность всего процесса численного моделирования, что соответствует п. 3, 4, 5 паспорта специальности 05.13.01 «Системный анализ, управление и обработка информации».

Научная новизна работы состоит в следующем:

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

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

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

- Предложен и реализован параллельный алгоритм переупорядочения разреженных распределённых матриц с целью уменьшения заполнения в ходе их факторизации, в котором в отличие от аналогов согласованно используется параллелизм на уровне нескольких вычислительных узлов (используется технология MPI) и в пределах одного узла (используется технология OpenMP) (соответствует п. 4 и п. 5 паспорта специальности).

Практическая значимость и ценность работы заключается в разработке

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

Разработанное программное обеспечение находится в открытом доступе, а также интегрировано в широко распространенный решатель СЛАУ MUMPS, распространяемый в открытых кодах. Таким образом, библиотека доступна для широкого научного сообщества. Проведена апробация разработанных алгоритмов на разреженных матрицах из открытой коллекции SuiteSparse, а также коллекции матриц, сгенерированных пакетом «ЛОГОС» в ходе конечно-элементных расчетов задач прочности. Показано, что на широком классе задач разработанная библиотека дает перестановки, позволяющие сократить общие затраты времени и памяти для решения СЛАУ с разреженной матрицей.

Положения, выносимые на защиту.

1. Методика сравнения эффективности решения задачи переупорядочения матриц на разных этапах процесса численного моделирования на базе прямых методов решения СЛАУ с симметричной разреженной матрицей.

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

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

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

Достоверность научных результатов и выводов. Достоверность и

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

Апробация и внедрение работы. Исследования проводились при поддержке гранта Российского фонда фундаментальных исследований № НК 14-0131455 «Методы и высокопроизводительные программные средства для решения разреженных систем линейных уравнений с симметричной положительно определенной матрицей» (2014-2015 гг.), специальной государственной стипендии Правительства Российской Федерации (2015-2016 уч.г., Приказ Министерства образования и науки РФ № 1132 от 13 октября 2015), стипендии Правительства Российской Федерации для аспирантов, обучающихся по приоритетным направлениям модернизации и технологического развития российской экономики, (2015-2016 уч.г., приказ Министерства образования и науки РФ № 419 от 22.04.2015 г.), стипендии Президента Российской Федерации для молодых ученых

и аспирантов, осуществляющих перспективные научные исследования и разработки по приоритетным направлениям модернизации российской экономики (2018-2020 гг., приказ Министерства образования и науки РФ №2 231 от 03.04.2018), гранта Министерства науки и высшего образования (№ 0729-2020-0055).

Практические результаты диссертационного исследования использованы в ФГУП РФЯЦ-ВНИИЭФ при разработке и внедрении программ численного моделирования и внедрены в учебный процесс института Информационных технологий, математики и механики ННГУ им. Н. И. Лобачевского для использования при проведении практических занятий на кафедре Математического обеспечения и суперкомпьютерных технологий. Представлены документы, подтверждающие внедрение.

1 Проблема переупорядочения строк и столбцов разреженных матриц

В первой главе рассматривается процесс численного моделирования, основанный на прямых методах решения СЛАУ и его основные этапы (§1.1). Объясняется роль подготовки данных для решения СЛАУ в сокращении затрат памяти и времени при выполнении численного моделирования. В §1.2 предлагается методика сравнения эффективности работы алгоритмов переупорядочения, направленная на сокращение общего времени численного моделирования. В §1.3 дается математическая постановка задачи переупорядочения строк и столбцов разреженной матрицы для уменьшения заполнения фактора. В §1.4 приводится обзор методов ее решения. В §1.5 приводится обзор программных пакетов, в которых реализованы последовательные и параллельные алгоритмы переупорядочения.

1.1 Процесс численного моделирования, основанный на прямых методах решения СЛАУ

Основная часть описания подготовлена в соответствии с источниками [94,

108].

Численное моделирование повсеместно используется для решения широкого класса научных и инженерных задач, в частности, при расчете прочности и деформации конструкций, в различных задачах моделирования механики жидкостей и газов, передачи электромагнитного потенциала, моделировании технологических процессов и др. Математические модели в этих областях, как правило, описываются дифференциальными или интегральными уравнениями, для численного решения которых широко используется метод конечных элементов и его аналоги. В этом случае в результате дискретизации уравнений и расчетной области модели строится система линейных уравнений (СЛАУ), которая решается

численно с использованием высокопроизводительного программного обеспечения.

14

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

Рис. 1.1. Иллюстрация процесса численного моделирования, основанного на

прямых методах решения СЛАУ

Рассмотрим подробнее процесс численного моделирования на базе решения СЛАУ (рис. 1.1), который выполняется на многопроцессорной вычислительной системе. Выделим два этапа моделирования: подготовительный и основной.

Основная задача подготовительного этапа моделирования - сформировать

данные для численного решения (шаг 1) и настроить вычислительное окружение

(шаг 2). В начале процесса моделирования выполняется дискретизация расчетной

области и уравнений модели. Для этого физическая область задачи, двумерная или

трехмерная, делится на подобласти с помощью аппроксимирующей расчетной

сетки (шаг 1.1). Как правило, используется неравномерная вычислительная сетка,

сгущенная в области наибольшего изменения моделируемых величин. Затем

решается №-трудная задача распределения сетки по вычислительным узлам (шаг

1.2). Этот шаг необходим для уменьшения накладных расходов на коммуникацию

между вычислительными узлами на основном этапе моделирования. При

15

необходимости, алгоритмы распределения сетки также могут учитывать дополнительные требования к разделению данных, например, сохранить связность разделенных областей [91]. После дискретизации расчетной области выполняется дискретизация уравнений модели и построение СЛАУ (шаг 1.3). Для этого выбирается набор функций специального вида, которые аппроксимируют зависимые переменные модели на каждом элементе. В результате подстановки аппроксимирующих функций в уравнения модели и учета граничных условий строится СЛАУ, в которой вектор неизвестных состоит из коэффициентов аппроксимации. Матрица СЛАУ, как правило, является разреженной, и для больших задач имеет порядок несколько миллионов строк и более. Далее выполняется предобработка матрицы (шаг 1.4), которая заключается в переупорядочении ее строк и столбцов с целью уменьшения числа ненулевых элементов, возникающих в ходе прямого решения СЛАУ. Затем выполняется настройка и конфигурация вычислительного окружения, запуск основной части расчета (шаг 2).

На основном этапе моделирования (шаги 3-5) в цикле по времени выполняется многократное прямое решение СЛАУ, производится анализ решения и, при необходимости, адаптация модели. Решение СЛАУ (шаг 3.1) является ключевой процедурой процесса численного моделирования, наиболее затратной по времени и памяти. Сократить затраты этого этапа можно за счет соответствующей подготовки данных - переупорядочения строк и столбцов разреженной матрицы, выполненного на шаге 1.4. После того, как решение СЛАУ найдено, полученные значения неизвестных переносятся на вычислительную сетку (шаг 3.2). Затем выполняется анализ эффективности решения (шаг 4): оценивается ошибка решения СЛАУ, погрешности дискретизации и аппроксимации. Также оценивается общая эффективность моделирования по использованию вычислительных ресурсов (затратам памяти и времени). По результатам анализа, исследователь может модифицировать метод решения, например, применить дополнительную предобработку матрицы или выполнить итерационное уточнение решения. В

случае необходимости, расчетная сетка уточняется, а матрица системы перестраивается полностью или частично (шаги 5.1, 5.2). Если расположение ненулевых элементов матрицы системы изменяется, целесообразно снова выполнить подготовку данных для решения СЛАУ (шаг 5.3).

Остановимся подробнее на решении СЛАУ и подготовке данных для этого шага. В зависимости от задачи и свойств матрицы для решения СЛАУ могут применяться прямые или итерационные методы. Прямые методы используются, в частности, в случае, когда требуется высокая точность решения или матрица системы плохо обусловлена и итерационные методы медленно сходятся, или построение предобуславливателя имеет высокую трудоемкость. Прямые методы требуют больших затрат памяти, чем итерационные, что ограничивает их применимость для систем больших порядков. Проблемами подготовки данных для ускорения решения СЛАУ и применением итерационных методов для численного моделирования занимались Акимова Е.Н. [2, 84], Икрамов Х.Д. [26], Ильин В.П. [38, 93], Капорин И.Е. [42- 44], Коньшин И.Н. [43, 51] и др. Вопросы оптимизации параметров конструкций в ходе численного моделирования рассматривались, в частности, Болдыревым Ю.Я. [9, 10].

Для сокращения затрат времени и памяти при прямом решении СЛАУ выполняется переупорядочение строк и столбцов матрицы системы для уменьшения ее заполнения в ходе разложения (факторизации). Нахождение точной перестановки, минимизирующей размер фактора при прямом решении СЛАУ, -NP-трудная задача [89], и при выборе эвристического алгоритма для ее решения возникает несколько проблем.

1. Поскольку алгоритмы переупорядочения эвристические, время их работы и качество (заполнение фактора) не известны заранее. Данные показатели противоречивы, увеличение одного из них ведет к нелинейному изменению другого. Большинство используемых алгоритмов переупорядочения включают в себя решение нескольких вспомогательных задач, а значит,

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

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

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

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

5. Перестановка оказывает влияние не только на время решения СЛАУ, но и на возможности параллелизма этого этапа. Так, при одном и том же заполнении фактора матриц могут быть получены разные зависимости между данными. Неудачное расположение ненулевых элементов ограничивает масштабируемость численного решения СЛАУ.

Список литературы диссертационного исследования кандидат наук Пирова Анна Юрьевна, 2022 год

Использование

очереди задач

Рис. 3.12. Переупорядочение графа, хранящегося на 4 процессах, гибридным параллельным алгоритмом.

2. Найти разделитель G0->sep, используя 1 поток;

3. Найти подграфы G1, G2, ... Gk, используя 1 поток.

4. for (i = 0; i < k; i++) {

5. if (Gi > barrier)

6. #pragma omp task

7. Gi->sep = NDStepParallel(Gi, barrier);

8. else

9. Gi->sep = NDStepSequential(Gi); 10. }

11. return G0->sep;

12. }

13.

14. int* PMORSyOrdering(graph G, parameters, int nThreads) {

15. omp set num threads(nThreads);

16. #pragma omp parallel

17. #pragma omp single

18. G->Sep = NDStepParallel(G, barrier);

19. separators = Merge(разделители из дерева задач графа G);

20. return separators;

21. } 22 .

23. int* NDStepMPI(graph currGraph, parameters, int nProcs) {

24. Найти разделитель графа currGraph->Sep, используя все процессы;

25. Найти два подграфа subgraph[0], subgraph[1],

26. используя все процессы;

27. Распределить subgraph[0] по процессам 0, 2, ..., nProcs / 2;

28. Распределить subgraph[1] по процессам 1, 3, ..., nProcs / 2;

29. currGraph->subgraph = subgraph[proc id % 2];

30. return currGraph->Sep;

31. } 32 .

33. int* NestedDissectionMPI(graph G(V, E), int nProcs, int nThreads) {

34. currGraph = G;

35. while ((currGraph != NULL) && (nProcs > 1)) {

36. currGraph->Sep = NDStepMPI(currGraph, parameters, nProcs);

37. currGraph = currGraph->subgraph;

38. nProcs = nProcs / 2;

39. }

40. if (currGraph != NULL) {

41. currGraph->Sep = PMORSyOrdering(currGraph, parameters, nThreads);

42. }

43. iperm = Merge(разделители из дерева задач графа G);

44. return iperm;

45. }

Рис. 3.13. Гибридный MPI + OpenMP алгоритм переупорядочения графа.

Пусть исходный граф распределен по Р процессам. Тогда, пока текущий граф хранится на нескольких процессах, нахождение разделителей выполняется всеми Р процессами согласно алгоритму 3.1. После того, как будут обработаны logP уровней дерева задач, на каждом процессе окажется один подграф целиком. С этого момента для каждого процесса используется своя очередь задач, обрабатываемая

несколькими потоками. Псевдокод алгоритма представлен на рис. 3.13 (с. 67). Подробно алгоритм описан в работах [96, 97].

Гибридный MPI + OpenMP алгоритм совмещает в себе преимущества ранее рассмотренных параллельных алгоритмов. Так, пока граф содержит большое число вершин, параллельное вычисление разделителя позволяет значительно сократить время работы программы, а объем вычислений превышает накладные расходы на коммуникацию между процессами. Графы, попавшие на один процесс, будут иметь на порядок меньший размер, для них параллельное выполнение этапов многоуровневого метода не приведет к заметному сокращению времени работы переупорядочения. Использование параллелизма на потоках внутри одного вычислительного узла позволяет более эффективно использовать подсистему памяти, чем при использовании нескольких процессов, например, избежать ненужных копирований данных. Кроме того, гибридный алгоритм переупорядочения позволяет получить перестановки с лучшим заполнением фактора, чем базовый алгоритм для систем с распределенной памятью. Это объясняется тем, что при выполнении этапов многоуровневой схемы последовательные алгоритмы, использующиеся в многопоточной реализации, позволяют найти лучший разделитель, чем параллельные алгоритмы, которые используются в версии для систем с распределенной памятью. Указанные особенности работы гибридного MPI + OpenMP алгоритма подтверждаются результатами вычислительных экспериментов (§5.3). Так, будет показано, что при работе на 32 ядрах двух вычислительных узлов наилучшие результаты по времени переупорядочения и заполнению фактора матриц получены при использовании 16 процессов по 2 потока или 8 процессов по 4 потока на тестовых задачах. Некоторым ограничением указанного алгоритма является то, что число MPI-процессов необходимо выбирать равным степени числа 2, что в основном компенсируется возможностью использовать произвольное число ядер в рамках каждого MPI-процесса.

3.5 Выводы

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

Узлы современных вычислительных систем, как правило, составлены из многоядерных процессоров с большим числом ядер, поэтому важно создавать параллельные алгоритмы, учитывающие архитектуру такого узла. В работе предлагается параллельный алгоритм переупорядочения, в котором комбинируется алгоритм для систем с распределенной памятью из публикации [12] и собственный параллельный алгоритм для систем с общей памятью. Гибридный параллельный алгоритм позволяет пользователю задавать число процессов и потоков в зависимости от конфигурации вычислительной системы, а значит, уменьшить число обменов данными и более эффективно использовать подсистему памяти многоядерного вычислительного узла. Гибридный алгоритм переупорядочения, использованный при решении СЛАУ на современной многопроцессорной вычислительной системе, позволит сократить время нахождения перестановки и общее время решения СЛАУ.

4 Программный комплекс для переупорядочения разреженных матриц

В четвертой главе описывается архитектура разработанных библиотек PMORSy и DMORSy, а также приводится методика их использования в виде отдельного модуля и в составе решателя СЛАУ.

4.1 Требования к программным библиотекам

Программная реализация библиотеки для переупорядочения разреженных матриц должна удовлетворять следующим требованиям:

1. Работать на операционных системах семейств Windows и Linux.

2. Предоставлять пользовательский интерфейс, принятый в данной предметной области. В частности,

a. Принимать на вход разреженную матрицу в одном из общепринятых форматов (CSR / COO).

b. Возвращать найденную перестановку в виде массива.

c. Принимать на вход коммуникатор процессов для вычислений на распределенной памяти и / или число используемых потоков для вычислений на общей памяти.

d. Принимать на вход параметры алгоритмов переупорядочения.

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

4. Выдавать информацию о времени работы этапов метода вложенных сечений.

5. Использовать встроенный в компилятор генератор случайных чисел или генератор из высокопроизводительной библиотеки (например, Intel MKL).

6. Код должен компилироваться различными общепринятыми трансляторами языка C с поддержкой стандарта языка С99.

7. Параллелизм должен быть реализован с использованием широко распространенных технологий MPI и OpenMP.

4.2 Основные проектные решения и высокоуровневая архитектура

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

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

Интерфейс переупорядочения

Подсистема хранения и обработки структур данных

Модуль хранения графа

Модуль хранения разделения

одуль хранения информации для улучшения разделения

Подсистема процедуры метода вложенных сечений на общей памяти

Модуль процедуры метода

вложенных сечении

Модуль алгоритмов огрубления

Модуль алгоритмов разделения

Модуль алгоритмов развертывания

Подсистема обработки входной информации

Модуль обработки параметров

Модуль ввода-вывода

Подсистема вспомогательных функций

Модуль генерации ПСЧ

Модуль базовых алгоритмов на графах

Модуль точного сжатия графа

Модуль алгоритмов построения подграфов

Рис. 4.1. Высокоуровневая архитектура библиотеки PMORSy.

Архитектура библиотеки DMORSy построена как расширенный вариант библиотеки PMORSy (рис. 4.2., с. 79). Для DMORSy ядром реализации является подсистема метода вложенных сечений на распределенной памяти, из которой вызываются функции подсистемы метода вложенных сечений на общей памяти, реализованные в PMORSy. Кроме вспомогательных подсистем, использующихся в PMORSy, DMORSy содержит подсистему функций обработки графов, хранящихся распределенно.

4.2.1 Основные модули и их назначение

Рассмотрим состав и назначение подсистем библиотеки PMORSy.

1. Подсистема процедуры метода вложенных сечений на общей памяти выполняет переупорядочение графа входной матрицы согласно псевдокоду на рис. 3.7.

Интерфейс переупорядочения

Подсистема хранения и обработки структур данных

Модуль хранения распределенного графа

Модуль хранения разделения

■кТ| 11М г» ■ щг* ■ щ ми ; 15 К ЯЯ

информации для улучшения азделения ^

Модуль хранения информации для коммуникации между процессами

Подсистема процедуры метода вложенных сечений на распределенной памяти

Модуль процедуры метода вложенных сечений

Модуль алгоритмов огрубления для распределенного графа

Модуль алгоритмов развертывания для распределенного графа

Подсистема обработки входной информации

Модуль обработки параметров

Модуль ввода-вывода

Подсистема процедуры метода вложенных сечений на общей памяти

Модуль процедуры метода вложенных сечений

Модуль алгоритмов огрубления

Модуль алгоритмов разделения

Модуль алгоритмов развертывания

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

Модуль точного сжатия распределенного графа

Модуль перераспределения графов и подграфов по процессам

Модуль коммуникации между процессами

Подсистема вспомогательных последовательных функций

Модуль генерации ПСЧ

Модуль базовых алгоритмов на графах

Модуль точного сжатия графа

Модуль алгоритмов построения подграфов

Рис. 4.2. Высокоуровневая архитектура библиотеки DMORSy

Эта подсистема включает модули, выполняющие отдельные этапы многоуровневого метода вложенных сечений согласно алгоритмам, описанным в §2.2. Так, в модуле алгоритмов огрубления реализованы различные алгоритмы паросочетания и построения сжатого графа (алгоритмы 2.3-2.6). В модуле алгоритмов разделения реализованы алгоритм поиска в ширину из псевдопериферийной вершины, приведенный в [92], алгоритм растущего разделения, жадного растущего разделения, алгоритм разделения Кернигана— Лина, описанные в [46]. В модуле алгоритмов развертывания реализован модифицированный метод примитивных перемещений Эшкрафта-Лю (алгоритм 2.7).

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

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

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

В состав библиотеки DMORSy входят подсистемы, описанные выше, и специализированные подсистемы для обработки распределенных графов:

1. Подсистема процедуры метода вложенных сечений на распределенной памяти выполняет переупорядочение графа, согласно псевдокоду с рис. 3.13. Получение вершинных разделителей выполняет алгоритм 3.1. Огрубление графа, хранящегося распределенно, реализовано в модуле огрубления этой подсистемы (алгоритм 3.1, п. 1.1 - 1.6). Разделение графа выполняется на одном процессе с

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

2. Подсистема вспомогательных функций для распределенной памяти состоит из нескольких частей. В модуле перераспределения графов и подграфов по процессам реализовано построение ленточного графа для выполнения улучшения разделения (алгоритм 3.1, п. 3.2), алгоритм «сложения и дублирования» (алгоритм 3.1, п. 1.7), построение несвязных подграфов (алгоритм 3.1, п. 4). Подсистема также включает модуль сжатия распределенного графа и модуль коммуникации между процессами, который выполняет передачу информации о структуре графа, необходимую для работы многоуровневого метода вложенных сечений.

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

4.2.2 Структуры данных

Приведем краткое описание структур данных, использованных в реализации.

В программе граф представлен в виде набора списков смежности каждой вершины, хранящихся в формате CSR или распределенный CSR (distributed CSR), в зависимости от архитектуры вычислительной системы. Использование данных форматов стандартно для программ по обработке графов и разреженных матриц [92], не требует конвертации матрицы СЛАУ при передаче ее из решателя в переупорядочиватель.

Для представления вершинного разделения использовалось несколько массивов. В них для каждой вершины хранилась информация о части разделения, в которой находится вершина, и суммарном весе смежных с ней вершин из других частей разделения. Такой формат хранения предложен в [46]. Он позволяет в алгоритме улучшения разделения пересчитывать функцию выигрыша при перемещении вершины за 0(1) для большинства вершин.

Для хранения функции выигрыша в алгоритме улучшения разделения необходимо использовать приоритетную очередь. В работе для этого использовалась система карманов, реализованная в виде массива двусвязных списков. В [24] было показано, что применение карманов гарантирует вычислительную сложность внешней итерации алгоритма Кернигана-Лина, равную 0(т). Это утверждение также справедливо и для алгоритма Эшкрафта-Лю, основанного на аналогичном принципе перемещения вершин.

4.3 Использование программного комплекса

4.3.1 Программный интерфейс переупорядочивателя

Библиотеки PMORSy и DMORSy предоставляются пользователю в открытых исходных кодах. Для использования библиотек необходимо их скомпилировать с помощью прилагаемых Make-файлов. В результате пользователь получит файл библиотеки, который необходимо подсоединить к решателю СЛАУ или другому приложению. После подключения заголовочных файлов библиотек pmorsy.h и dmorsy.h пользователю доступен интерфейс следующих функций: переупорядочение матрицы для систем с общей памятью, переупорядочение матрицы для систем с распределенной памятью, установка параметров по умолчанию.

Алгоритм переупорядочения для систем с общей памятью, описанный в §3.2,

имеет следующий прототип:

int PMORSY_NestedDissection(int n, int* xadj, int* adjncy, int*

perm, int* iperm, int* options);

Параметры функции: n - порядок матрицы,

xadj - индекс начала ненулевых элементов каждой строки матрицы в массиве adjncy (формат CSR),

adjncy - массив номеров столбцов ненулевых элементов матрицы (формат CSR),

perm - массив перестановки, в которой i - новый номер строки, perm[i] -старый номер строки (может быть пустым),

iperm - массив перестановки, в которой iperm[i] - новый номер строки i, оptions - массив параметров переупорядочения размера morsy_num_options. На вход функция PMORSY_NestedDissection принимает портрет разреженной матрицы в формате CSR без диагональных элементов, в котором номера столбцов ненулевых элементов каждой строки упорядочены по возрастанию.

Гибридный алгоритм переупорядочения для систем с распределенной памятью, описанный в §3.4, имеет следующий прототип:

int NestedDissectionMPI(int n, int* xadj, int* adjncy, int* vertexDistribution, int* perm, int* iperm, int* options, MPI_Comm comm);

Параметры функции: n - порядок матрицы,

xadj - индекс начала ненулевых элементов каждой строки матрицы в массиве adj ncy, локальная индексация для каждого процесса,

adjncy - массив номеров столбцов ненулевых элементов матрицы, хранящихся на процессе,

vertexDistribution - массив, в котором описано распределение строк матрицы по процессам,

perm - массив перестановки, в которой i - новый номер строки, perm[i] -старый номер строки (может быть пустым),

iperm - массив перестановки, в которой iperm[i] - новый номер строки i, options - массив параметров переупорядочения размера morsy_num_options, comm - коммуникатор процессов, которые будут выполнять переупорядочение.

Функция NestedDissectionMPI принимает на вход матрицу в формате распределенный CSR. Предполагается, что матрица распределена полосами между p процессами так, что процесс с номером i хранит ненулевые элементы строк от

vertexDistribution[i] до vertexDistribution[i+1]-1 включительно. Переупорядочение корректно работает в число процессов, являющееся степенью двойки.

Параметры по умолчанию можно задать вызовом функции void MORSY_SetDefaultOptions(int* options), где options - массив параметров размера morsy_num_options. Описание параметров приведено в приложении А (с. 141), рекомендации по их выбору - в §0. Кроме того, пользователю доступны настройки переупорядочения, которые можно задать на этапе компиляции:

MORSY_PRECISION - точность чисел с плавающей запятой, MORSY_USE_MKL - использование генератора псевдослучайных числе из библиотеки Intel MKL,

MORSY_TIMERS - использование встроенных таймеров для замера этапов переупорядочения,

MORSY_PRINT - вывод дополнительной информации.

По завершении работы переупорядочиватель отображает пользователю информацию о времени выполнения разных этапов переупорядочения. Пример выдачи PMORSy приведен на рис. 4.3, DMORSy - на рис. 4.4.

PMORSy time (seconds): Compression: 0.044447 Coarsening: 1.891667

- Matching: 0.882230

- Contracting: 0.859222 Initial partitioning: 0.256654 Uncoarsening: 0.998201

- Refinement: 1.057838

- Projection: 0.290713 Splitting: 0.523644 Basic ND: 0.170590 First task: 0.867161

- Coarsening: 0.423892

- Matching: 0.224674

- Initial partitioning: 0.002080

- Uncoarsening: 0.354971

- Refinement: 0.309360 Total time: 2.178939

phc. 4.3. Btigana nepeynopagoHHBaTe.ra PMORSy Ha MaTpn^ G3_circuit

PMORSy time (min, max, average, call count) in seconds :

summary 1. 232 1. 235 1. 234 1

compression 0 . 020 0 . 021 0. 020 1

matching 0 . 041 0 . 059 0. 050 1641

contracting 0 . 049 0 . 073 0. 062 1641

coarsening 0 . 077 0 . 113 0. 098 971

init partitioning 0 . 010 0 . 014 0. 012 971

refinement 0 . 082 0 . 116 0. 102 2612

projection 0 . 013 0 . 018 0. 016 2613

uncoarsening 0 . 081 0 . 126 0. 107 971

splitting 0 . 028 0 . 041 0. 035 971

leafs 0 . 017 0 . 025 0. 021 1653

matching mpi 0 . 087 0 . 102 0. 097 24

contracting mpi 0 . 214 0 . 229 0. 220 24

folding mpi 0 . 029 0 . 031 0. 030 24

coarsening mpi 0 . 335 0 . 361 0. 347 4

init partitioning mpi 0 . 000 0 . 000 0. 000 0

refinement mpi 0 . 214 0 . 244 0. 234 24

projection mpi 0 . 138 0 . 168 0. 152 24

uncoarsening mpi 0 . 408 0 . 434 0. 422 4

splitting mpi 0 . 050 0 . 055 0. 053 4

communication mpi 0 . 028 0 . 037 0. 032 4

gather grath mpi 0 . 000 0 . 000 0. 000 0

coarsening single proc I 0 .019 0 . 021 0 . 020

init partitioning single proc | 0 001 0 001 0 001

uncoarsening single proc | 0 032 0 043 0 037

single proc 0. 052 0 . 063 0. 058 4

mpi 0. 894 0 . 945 0. 917 1

seqv | 0. 177 0. 250 0. 219 1

phc. 4.4. Btigana nepeynopagoHHBaTe^a DMORSy_hybrid Ha MaTp^e G3_circuit

4

4.3.2 Использование переупорядочивателя в составе решателей СЛАУ

Переупорядочиватель можно использовать для решения СЛАУ, создав общее с решателем приложение. Такой интеграции достаточно, поскольку большинство решателей СЛАУ допускают передачу пользовательской перестановки через параметры решателя.

Для выполнения численных экспериментов с решателями MUMPS и Intel MKL Pardiso были реализованы два приложения на языке С, в которых выполнялось следующее:

1. Задание тестовой СЛАУ.

2. Задание параметров и вызов переупорядочивателя, сохранение перестановки.

3. Задание параметров решателя СЛАУ. Перестановка указывается как пользовательская.

4. Вызов решателя СЛАУ.

5. Проверка корректности решения.

Как правило, при передаче пользовательской перестановки в решатель фаза анализа (символьная факторизация) выполняется последовательно, поскольку решателю не доступна информация о способе построения перестановки. Это ограничение можно снять, если решатель СЛАУ предоставляется в открытых исходных кодах. Тогда функцию переупорядочения можно вызывать напрямую из модулей решателя, выполняющих фазу анализа, и сохранить дополнительные данных. В частности, при построении перестановки методом вложенных сечений можно сохранить последовательность найденных разделителей в виде бинарного дерева, а затем использовать эту информацию для построения дерева исключения.

4.4 Выводы

Параллельные алгоритмы, предложенные в главе 3, реализованы в двух программных библиотеках для переупорядочения симметричных разреженных матриц. Библиотека PMORSy ориентирована на работу на одном вычислительном

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

В главе описана модульная архитектура библиотек PMORSy и DMORSy, приведена методика их использования в виде отдельного приложения и в составе решателя СЛАУ.

5 Анализ и тестирование параллельных алгоритмов переупорядочения

В пятой главе приводятся результаты вычислительных экспериментов и даются рекомендации по настройке параметров разработанных библиотек для получения разных конфигураций. Выполняется анализ эффективности применения различных алгоритмов в рамках многоуровневого метода вложенных сечений и сравнение реализации с библиотеками ParMETIS и mt-metis. Далее полученные перестановки применяются для решения СЛАУ с разреженной матрицей библиотеками MUMPS и Intel MKL Pardiso.

5.1 Методика проведения вычислительных экспериментов

5.1.1 Программно-аппаратное окружение

Вычислительные эксперименты проводились на двух тестовых системах:

1. Узлы суперкомпьютера ННГУ «Лобачевский» со следующими характеристиками: два 8-ядерных процессора Intel Sandy Bridge E5-2660, частота 2.2 GHz, память 64 GB, операционная система Linux CentOS 6.4, компилятор Intel C++ Compiler и генератор случайных чисел из библиотеки Intel MKL, входящие в пакет Intel Parallel Studio XE 2015 Cluster Edition.

2. Узлы кластера МСЦ РАН со следующими характеристиками: два 18-ядерных процессора Intel Xeon Gold 6154 (Skylake), 3.0 GHz, память 192 GB, операционная система Linux CentOS 6.4, компилятор Intel C++ Compiler и генератор случайных чисел из библиотеки Intel MKL, входящие в пакет Intel Parallel Studio XE 2017 Cluster Edition.

5.1.2 Тестовые задачи

Для анализа результатов работы алгоритмов переупорядочения

использовались два тестовых набора матриц. Предварительный набор составлен из

48 матриц из коллекции SuiteSparse [83]; были выбраны симметричные

вещественные разреженные матрицы разного размера и заполнения из разных

82

предметных областей. Порядок матриц варьировался от 2.2 *106 до 2.8* 108, с числом ненулевых элементов от 7.6 *106 до 7.6* 109. Параметры тестовых матриц приведены ниже (до 600 000 строк и столбцов - таблица 5.1, более 600 000 строк и столбцов - таблица 5.2). В таблицах для каждой матрицы указаны ее название, порядок (п), число ненулевых элементов (ш), заполнение (пг/(п*п)), тип (положительно определенная, неопределенная) и признак, говорящий о том, возможно ли точное сжатие структуры матрицы по алгоритму 2.2 (1 - да, 0 - нет). Далее будет показано, что возможность сжатия влияет на время решения задачи.

Таблица 5.1 Характеристики тестового набора 1. Матрицы порядка до 0.6 млн. строк. Обозначения: n - число строк матрицы, nz - число ненулевых элементов. Тип матриц: SPD - симметричная положительно определенная, SI - симметричная неопределенная.

Название n nz nz/(nXn) тип матрицы Сжимается?

pwtk 217 918 11 524 432 2,43E-04 SPD 1

hood 220 542 9 895 422 2,03E-04 SPD 1

CO 221 119 7 666 057 1,57E-04 SPD 0

HTC 336 9129 226 340 762 969 1,49E-05 SI 1

bmw3 2 227 362 11 288 630 2,18E-04 SI 1

Si87H76 240 369 10 661 631 1,85E-04 SPD 0

BenElechil 245 874 13 150 496 2,18E-04 SPD 1

Lin 256 000 1 766 400 2,70E-05 SPD 0

offshore 259 789 4 242 673 6,29E-05 SPD 0

Ga41As41H72 268 096 18 488 476 2,57E-04 SI 0

Fl 343 791 26 837 113 2,27E-04 SI 1

c-big 345 241 2 340 859 1,96E-05 SI 0

darcy003 389 874 2 097 566 1,38E-05 SI 1

helm2d03 392 257 2 741 935 1,78E-05 SI 0

msdoor 415 863 19 173 163 1,11E-04 SPD 1

boyd2 466 316 1 500 397 6,90E-06 SI 0

af 3 k101 503 625 17 550 675 6,92E-05 SPD 1

inline 1 503 712 36 816 170 1,45E-04 SPD 1

af shell3 504 855 17 562 051 6,89E-05 SPD 1

af shell9 504 855 17 588 845 6,90E-05 SI 1

parabolic fem 525 825 3 674 625 1,33E-05 SPD 0

gsm 106857 589 446 21 758 924 6,26E-05 SI 1

Таблица 5.2 Характеристики тестового набора 1. Матрицы порядка более 0.6 млн. строк. Обозначения: n - число строк матрицы, nz - число ненулевых элементов. Тип матриц: SPD - симметричная положительно определенная, SI - симметричная неопределенная.

название n nz nz/(n*n) тип матрицы сжимается? (1 - да, 0 -нет)

Fault 639 638 802 27 245 944 6,68E-05 SPD 1

apache2 715 176 4 817 870 9,42E-06 SPD 0

tmt sym 726 713 5 080 961 9,62E-06 SPD 0

boneS10 914 898 40 878 708 4,88E-05 SPD 1

Emilia 923 923 136 40 373 538 4,74E-05 SPD 1

audikw 1 943 695 77 651 847 8,72E-05 SPD 1

ldoor 952 203 42 493 817 4,69E-05 SPD 1

bone010 986 703 47 851 783 4,92E-05 SPD 1

ecology2 999 999 4 995 991 5,00E-06 SPD 0

ecology1 1 000 000 4 996 000 5,00E-06 SI 0

dielFilterV3real 1 062 400 28 192 672 2,50E-05 SI 1

dielFilterV2real 1 102 824 89 306 020 7,34E-05 SI 1

nlpkkt80 1 157 456 48 538 952 3,62E-05 SI 0

thermal2 1 228 045 8 580 313 5,69E-06 SPD 0

Serena 1 391 349 64 131 971 3,31E-05 SPD 1

Geo 1438 1 437 960 60 236 322 2,91E-05 SPD 1

StocF#465 1 465 137 21 005 389 9,79E-06 SPD 0

Hook 1498 1 498 023 59 374 451 2,65E-05 SPD 1

af shell 10 1 508 065 52 259 885 2,30E-05 SI 1

Flan 1565 1 564 794 114 165 372 4,66E-05 SPD 1

G3 circuit 1 585 478 7 660 826 3,05E-06 SPD 0

kkt power 2 063 494 12 771 361 3,00E-06 SI 1

nlpkkt120 3 542 400 95 117 792 7,58E-06 SI 0

nlpkkt160 8 345 600 225 422 112 3,24E-06 SI 0

nlpkkt200 16 240 000 440 225 632 1,67E-06 SI 0

nlpkkt240 27 993 600 760 648 352 9,71E-07 SI 0

Основной тестовый набор составили 27 матриц из коллекции SuiteSparse [83] порядком от 2.6х106 до 1.5х108 и 10 матриц, сгенерированных пакетом «ЛОГОС» в ходе расчетов задач прочности [90]. Параметры тестовых матриц приведены в таблица 5.3. Далее в таблицах результаты сравнения времени и заполнения фактора отображены по цветовой шкале, где лучшему значению соответствует зеленый цвет, худшему - красный цвет, желтому - промежуточные результаты.

Таблица 5.3 Характеристики тестового набора 2. Обозначения: n - число строк матрицы, nz - число ненулевых элементов. Тип матриц: SPD - симметричная положительно определенная, SI - симметричная неопределенная.

название n nz nz/(n*n) тип матрицы сжимается? (1 - да, 0 - нет)

cyclik 60 984 3 758 592 5,14E-04 SPD 1

Kamaz kollekt 135 669 4 202 267 1,18E-04 SPD 1

pwtk 217 918 11 634 424 1,25E-04 SPD 1

hood 220 542 10 768 436 1,13E-04 SPD 1

CO 221 119 7 666 057 8,07E-05 SI 0

podves 269 178 4 397 606 3,22E-05 SPD 1

lopatkal 274 104 20 467 224 1,38E-04 SPD 1

msdoor 415 863 20 240 935 5,97E-05 SPD 1

af 4 k101 503 625 17 550 675 3,56E-05 SPD 1

parabolic_fem 525 825 3 674 625 7,60E-06 SPD 0

Fault 639 638 802 28 614 564 3,58E-05 SPD 1

apache2 715 176 4 817 870 5,41E-06 SPD 0

tmt_sym 726 713 5 080 961 5,50E-06 SPD 0

PFlow 742 742 793 37 138 461 3,43E-05 SPD 1

boneS10 914 898 55 468 422 3,37E-05 SPD 1

Emilia 923 923 136 41 005 206 2,46E-05 SPD 1

audikw_1 943 695 77 651 847 4,41E-05 SPD 1

ldoor 952 203 46 522 475 2,62E-05 SPD 1

bone010 986 703 71 666 325 3,73E-05 SPD 1

ecology2 999 999 4 995 991 3,00E-06 SPD 0

ecology1 1 000 000 4 996 000 3,00E-06 SI 0

nlpkkt80 1 062 400 28 704 672 1,32E-05 SI 1

CurlCurl 3 1 219 574 13 544 618 4,96E-06 SI 0

thermal2 1 228 045 8 580 313 3,25E-06 SPD 0

Serena 1 391 349 64 531 701 1,70E-05 SPD 1

Kamaz_gusev 1 429 158 98 953 138 2,46E-05 SPD 1

Geo 1438 1 437 960 63 156 690 1,56E-05 SPD 1

StocF-1465 1 465 137 21 005 389 5,23E-06 SPD 0

Hook 1498 1 498 023 60 917 445 1,39E-05 SPD 1

af shell 10 1 508 065 52 672 325 1,19E-05 SPD 1

Flan 1565 1 564 794 117 406 044 2,43E-05 SPD 1

G3_circuit 1 585 478 7 660 826 1,84E-06 SPD 0

trubka 2 428 323 138 248 755 1,19E-05 SPD 1

Korpus 2 504 934 184 232 894 1,49E-05 SPD 1

lopatka2 2 545 314 174 001 728 1,36E-05 SPD 1

49 750 2 615 169 191 548 377 1,42E-05 SPD 1

p4_6 4 216 212 285 212 376 8,14E-06 SPD 1

5.1.3 Проведенные эксперименты

Введем наборы параметров переупорядочения, согласно предложенной в §1.2 методике сравнения эффективности решения задачи переупорядочения:

1. Параметры, дающие наилучшее заполнение фактора за приемлемое время работы («лучшее заполнение»);

2. Параметры, дающие приемлемое заполнение фактора за ограниченное время работы («ограниченное заполнение»).

3. Параметры по умолчанию.

Данные наборы параметров были использованы для сравнения реализованных алгоритмов друг с другом и с распространенными библиотеками mt-metis, ParMETIS.

В первой серии экспериментов (§5.2.1) для библиотеки PMORSy сравнивалось применение различных комбинаций алгоритмов огрубления и начального разделения по времени работы и заполнению фактора. Во второй серии экспериментов (§5.2.2) исследовалось влияние настроек алгоритма улучшения разделения на результаты работы PMORSy, для этого для каждой матрицы сравнивались перестановки, полученные с параметрами «лучшее заполнение» и «ограниченное заполнение». В результате экспериментов для каждой матрицы были сформированы указанные выше наборы параметров.

В третьей серии экспериментов (§5.3) приведены результаты сравнения производительности и качества переупорядочения библиотек PMORSy и DMORSy с аналогами - библиотеками mt-metis и ParMETIS. Сравнение производилось на одном и двух вычислительных узлах кластера, с параметрами «по умолчанию» для всех библиотек. Показано, что наилучший относительно аналогов результат показывает реализация DMORSy с гибридным алгоритмом распараллеливания. В четвертой серии экспериментов (§5.4) перестановки, полученные DMORSy, применялись для прямого решения СЛАУ в библиотеках MUMPS и Intel MKL Pardiso. Сравнение с переупорядочивателями на основе ParMETIS, встроенными в решатели MUMPS и Intel MKL Pardiso показало, что на большинстве тестовых

86

матриц DMORSy позволяет сократить время решения СЛАУ для решателя MUMPS и для трети матриц - для решателя Intel MKL Pardiso. В §0 даны рекомендации по настройке параметров переупорядочивателей PMORSy, DMORSy для их эффективного использования в решателях СЛАУ.

5.2 Анализ эффективности применения различных алгоритмов в рамках многоуровневого метода вложенных сечений

5.2.1 Анализ эффективности применения различных алгоритмов огрубления и разделения

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

В рамках реализованного многоуровневого метода вложенных сечений сравнивались следующие алгоритмы огрубления: алгоритм случайных паросочетаний (RM), паросочетания тяжелых ребер (HEM), паросочетания тяжелых клик (HCM). Для каждого из них были рассмотрены алгоритмы разделения: поиск в ширину из псевдопериферийной вершины (LS), алгоритм растущего разделения (GG), алгоритм жадного растущего разделения (GGG), алгоритм Кернигана—Лина (KL). Всего для каждой матрицы было проведено 126 экспериментов для фиксированного числа потоков, запуски производились в 16 потоков. Для каждого запуска собирались следующие данные: время работы алгоритма переупорядочения, заполнение фактора в результате перестановки, время обработки самого большого подграфа. Во всех таблицах матрицы приведены в порядке увеличения числа ненулевых элементов. Таким образом, наиболее вычислительно трудоемкие задачи сгруппированы внизу таблицы. Результаты переупорядочения, в которых качество было хуже более, чем на 60%, чем при применении других алгоритмов, не участвовали в сравнении времени, поскольку

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

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

Таблица 5.4 Параметры многоуровневого метода вложенных сечений для сравнения алгоритмов огрубления и разделения

Параметр Значение

размер минимального графа, уЫт 20, 100

максимальное число итераций алгоритма огрубления, сЫах 10, 20, 100

число повторений алгоритма разделения (для алгоритмов GG, GGG, KL), п1пи 5, 10

Алгоритм улучшения разделения коэффициент дисбаланса 0.2, максимальный дисбаланс 2.0, порог значения функции выигрыша 1/3.

Минимальный граф для очереди задач потоков 1000

Таблица 5.5, таблица 5.6 показывают заполнение фактора в результате перестановки, таблица 5.7, таблица 5.8 - время работы переупорядочения в зависимости от использованных алгоритмов. Приведем основные выводы:

1. Предварительные эксперименты показали, что для матриц с числом ненулевых элементов в пределах 25* 106 лучшее заполнение фактора получено при значении параметра «размер минимального графа» (уЫгп), равном 20, для матриц с большим числом ненулевых элементов - равным 100 вершин. Наиболее чувствительны к выбору этого параметра графы, в которых есть вершина со степенью, значительно больше средней, а также графы большого порядка. Чем меньше значение этого параметра, тем более плотные графы получаются в процессе огрубления. В дальнейшем для проведения экспериментов был выбран параметр уЫт, равный 100.

Таблица 5.5 Заполнение фактора PMORSy при использовании различных алгоритмов (млн. элементов). Один вычислительный узел, 16 ядер. Первая часть тестового набора матриц

Заполнение фактора, млн. элементов

Матрица RM LS MS HCM LS О о О § ~ R RM GGG 10 L M1 R HEM GG 10 HEM GGG 10 HEM KL 10 HCM GG 10 HCM GGG 10 HCM KL 10 RM GG 5 G G G5 M R RM KL 5 G G M5 E H HEM GGG 5 L K M5 E H G G M5 C H HCM GGG 5 L K § ю C H

HTC 336 9129 1,43 1,57 1,51 1,44 1,98 1,51 5,36 1,48 1,62 1,50 1,49 1,39 1,45 1,49 1,48 1,57 1,43 1,56 1,45 1,53 1,38

Lin 100,49 102,44 110,58 99,46 104,77 103,68 110,75 116,19 109,55 106,31 114,81 115,30 104,27 108,76 105,34 109,97 107,41 112,01 111,94 107,37 110,23

boyd2 1,26 1,26 1,26 1,26 1,26 30436,60 1,26 1,26 1,26 1,26 1,26 1,26 1,26 1,26 30436,60 1,26 1,26 1,26 1,26 1,26 1,26

darcy003 7,14 7,14 7,13 6,92 6,89 6,94 7,06 6,77 6,81 6,97 6,87 6,98 7,12 7,07 6,89 7,25 6,75 6,84 6,84 6,85 6,85

c-big 61,24 56,56 51,36 1816,45 57,01 341,76 102,94 71,31 78,98 54,00 101,15 120,98 98,03 64,09 79,92 90,83 55,42 60,56 126,05 94,82 15977,89

helm2d03 18,02 18,10 17,95 18,03 17,99 17,96 18,05 17,89 17,95 18,08 17,86 18,03 18,03 17,97 18,21 18,03 17,79 17,95 17,87 17,84 17,95

parabolic fem 25,45 25,49 25,42 25,38 25,24 25,38 25,60 25,21 25,36 25,30 25,24 25,36 25,48 25,27 25,36 25,36 25,14 25,46 25,41 25,54 25,23

CO 1388,45 1442,45 1524,92 4451,05 4451,05 4451,05 1540,86 1571,96 1630,38 1439,49 1618,67 1752,84 4451,05 4451,05 4451,05 1665,84 1655,87 1705,55 2804,76 1807,26 1703,62

offshore 95,58 107,85 101,97 107,03 99,79 98,75 105,55 99,59 94,63 91,77 117,28 95,14 107,12 968,97 98,59 103,13 99,76 96,61 115,36 113,11 97,46

apache2 129,54 121,65 132,36 136,54 135,96 123,02 117,74 134,63 131,84 133,82 136,70 138,63 118,67 128,75 132,57 133,63 121,92 121,70 128,55 128,61 131,57

ecology2 32,26 32,28 32,61 33,80 31,77 32,48 34,24 34,25 33,52 31,65 33,84 33,30 31,89 31,43 31,62 33,47 34,00 34,13 32,43 34,10 31,99

ecologyl 31,45 34,25 33,35 31,38 33,15 31,72 32,78 34,57 33,56 33,13 33,22 34,18 31,34 32,72 31,25 32,47 33,36 34,98 34,04 33,49 32,71

tmt sym 30,15 29,73 29,92 29,66 29,83 29,81 29,75 30,12 29,79 29,80 29,94 29,78 29,95 29,97 29,99 29,73 30,22 29,90 29,90 29,80 29,91

Si87H76 1659,63 1770,48 1689,68 5123,90 5123,90 5123,90 1899,43 1731,07 1845,08 1918,10 2375,10 1810,79 5123,90 5123,90 5123,90 2416,16 1859,00 1926,61 1881,11 2593,93 1860,85

hood 29,77 29,63 29,99 30,06 29,74 29,72 29,73 29,30 29,65 29,47 29,63 30,24 29,53 29,72 29,49 30,27 29,60 29,83 29,70 29,78 29,43

BenElechil 51,50 51,44 51,62 51,49 51,15 51,05 51,94 51,33 51,75 51,62 51,34 51,21 51,69 51,23 51,41 52,38 52,21 52,75 51,70 51,25 51,40

G3 circuit 98,45 97,12 97,62 101,51 96,31 94,52 96,24 96,22 98,45 95,94 95,73 97,84 100,59 100,97 103,61 97,47 96,03 94,40 93,05 92,22 95,27

thermal2 53,08 52,93 52,95 53,25 52,81 53,17 52,73 52,78 53,07 53,26 52,87 52,61 53,17 53,15 53,37 53,23 52,88 52,67 52,54 52,99 53,09

af 3 k101 96,76 95,94 95,77 95,92 96,07 96,03 95,84 96,24 95,33 96,61 95,93 96,30 95,88 95,58 96,05 95,87 96,04 95,92 96,28 96,08 96,66

bmw3 2 49,91 47,93 52,05 48,22 48,85 49,63 50,79 51,21 50,83 51,02 52,01 50,81 50,35 47,83 49,66 48,25 52,24 48,13 54,39 50,10 49,26

pwtk 47,12 48,00 48,28 47,21 47,76 47,57 47,26 46,92 48,16 47,44 47,60 47,75 47,61 47,26 47,00 47,80 49,06 47,82 47,85 47,46 47,98

kkt power 277,89 280,54 271,32 1404,58 271,50 447,60 273,89 339,98 258,33 515,92 615,46 529,91 566,01 518,56 684,38 275,78 357,66 239,29 743,89 680,56 578,50

nlpkkt80 1616,46 1621,75 1635,69 2509,31 4221,68 3520,35 1626,37 1624,17 1624,04 1623,54 1623,13 1624,37 2705,51 3674,03 3921,48 1638,72 1623,70 1626,49 1629,87 1623,92 1620,55

af shell3 90,86 90,86 91,35 91,51 91,80 91,51 90,91 90,63 90,98 90,92 91,07 91,31 91,58 91,01 90,58 91,19 91,01 91,12 91,41 91,49 90,55

af shell9 91,68 91,65 92,08 90,83 91,71 91,34 91,13 90,39 91,01 91,53 90,63 91,22 91,71 92,22 91,26 90,74 90,63 90,82 90,73 91,62 91,12

Ga41As41H72 2115,64 2172,17 2382,65 6178,37 6178,37 6178,37 2441,45 6178,37 2189,56 2400,23 6178,37 3626,17 6178,37 6178,37 6178,37 2393,47 6178,37 2439,34 3390,44 6178,37 4961,28

Таблица 5.6 Заполнение фактора PMORSy при использовании различных алгоритмов (млн. элементов). Один вычислительный узел, 16 ядер. Вторая часть тестового набора матриц

Заполнение фактора, млн. элементов

Матрица RM LS ^ И ^ HCM LS О о О § ~ а RM GGG 10 а HEM GG 10 HEM GGG 10 HEM КЪ 10 нем GG 10 нем GGG 10 нем къ 10 RM GG 5 О О О ш м а RM КЪ 5 О О м5 И н НЕМ GGG 5 м5 И н О О м5 е н нем GGG 5 § е н

msdoor 59,52 59,20 59,98 58,73 57,63 59,09 58,33 58,06 58,74 58,35 57,94 58,56 59,28 58,85 59,96 58,10 58,78 58,44 58,55 59,38 59,23

StocF-1465 1134,94 1149,94 1125,03 1088,73 5623,46 1531,93 1120,95 1128,00 1087,50 1094,03 1088,32 1131,10 1131,02 1512,71 1639,32 1118,09 1101,76 1111,59 1085,70 1126,90 1129,20

gsm 106857 159,03 155,04 157,42 156,09 153,34 149,02 155,91 161,01 155,76 158,87 155,00 152,92 155,99 151,63 155,78 153,47 161,71 152,82 153,85 158,92 160,36

F1 221,54 220,06 216,62 218,18 225,38 212,73 220,36 218,93 210,33 223,31 213,72 230,69 233,20 560,93 650,14 219,07 215,43 208,57 230,68 216,23 214,25

Fault 639 1128,50 1130,41 1124,63 1099,86 3565,98 1128,17 1126,00 1124,90 1112,45 1142,18 1139,73 1126,79 1133,81 1082,88 3754,18 1144,75 1150,88 1126,22 1121,51 1149,92 1115,45

inline 1 196,10 198,00 197,71 200,50 197,55 203,19 201,15 195,59 202,18 198,08 198,90 198,08 201,31 197,46 197,68 200,17 196,80 206,76 201,57 201,36 199,60

Emilia 923 1755,61 1830,90 1885,94 1685,78 1672,07 1760,02 1783,53 1742,47 1709,73 1836,14 1810,04 1875,00 1722,62 1735,72 1779,79 1750,79 1716,83 1807,84 1798,37 1688,05 1802,56

Ьопе810 324,18 339,81 318,94 357,12 362,47 361,94 351,24 319,99 326,08 340,03 324,19 351,31 490,10 352,29 338,49 347,46 311,66 328,20 328,92 321,03 348,35

Ыоог 161,26 165,18 161,30 158,82 163,88 165,41 163,66 165,33 163,44 164,46 160,68 159,84 161,69 168,20 161,78 161,05 164,76 160,82 165,45 163,13 162,34

Ьопе010 1107,92 1111,90 1068,33 1081,34 1259,03 2064,47 1074,88 1094,85 1089,06 1087,96 1101,44 1129,06 1081,31 1108,17 1297,85 1078,17 1072,81 1112,43 1131,93 1077,26 1088,25

dielFilterV2real 696,72 661,17 670,86 827,82 692,57 710,42 693,23 693,97 682,29 672,92 681,11 677,85 686,03 4340,18 688,98 686,45 692,68 679,07 684,85 672,39 666,55

^ shell10 345,42 345,37 347,30 346,70 346,23 343,81 349,09 347,31 346,41 350,38 346,46 348,19 348,74 348,12 345,44 345,52 346,43 344,74 348,17 345,08 349,18

Ноок 1498 1620,67 1634,96 1721,01 1943,98 1779,82 1635,85 1668,21 1597,89 1749,98 1790,73 1674,85 1692,43 1714,37 1807,47 2164,67 1613,85 1613,55 1619,06 1698,48 1703,83 1658,03

Geo 1438 2490,74 2527,27 2502,75 2497,91 2524,01 2527,56 2589,01 2553,19 2478,53 2463,31 2503,40 2471,27 2468,62 2457,96 2554,15 2499,18 2574,15 2589,32 2454,93 2491,77 2458,38

8егепа 2974,14 2872,10 2842,93 3129,92 2870,53 2849,15 3125,30 3036,94 2999,63 3110,84 3067,25 2844,02 2895,77 2981,66 2878,09 3087,30 3116,09 3062,77 2854,67 3158,28 2871,78

audikw 1 1388,65 1378,21 1350,37 1392,10 1888,22 1422,66 1360,75 1374,53 1358,92 1377,95 1362,27 1364,83 56695,33 1447,25 1751,44 1399,78 1414,98 1343,60 1340,26 1363,26 1355,94

dielFilterV3real 671,52 657,08 684,43 647,18 706,85 687,01 679,92 674,50 655,07 667,53 654,44 654,71 664,17 678,80 698,21 661,48 645,00 664,93 673,01 667,78 680,45

nlpkkt120 8694,83 8734,12 8805,56 12135,04 13649,79 12461,91 8773,77 8775,25 8751,02 8761,74 8746,45 8743,96 13384,79 12691,49 13835,10 8791,57 8752,52 8790,24 8783,25 8768,09 8742,41