Разработка модуля расчета моделируемой схемы с разреженными матрицами

Рисунок 36 - Сравнение теоретичесого и расчётного ускорения автоматического распараллеливания

Рисунок 37 - Реализация умножения с использованием автоматического распараллеливания

Сравнение автоматического распараллеливания, OpenMP, MPI

Вычисления были произведены на суперкомпьютерном комплексе НИУ ВШЭ.

Характеристики суперкомпьютерного комплекса НИУ ВШЭ:

1. Состоит из 26 узлов, разделенных на две группы (10 и 16 узлов отличающихся количеством оперативной памяти).

2. Сеть суперкомпьютера построена на Infiniband EDR с топологией Fat Tree.

3. Файловая система - Lustre.

Характеристики узлов:

1. Узлы тип 1: 16 (2xXeon Gold 6152 [Acc: 4xTesla V100 32GB] 2.1 GHz 768GB RAM)

2. Узлы тип 2: 10 (2xXeon Gold 6152 [Acc: 4xTesla V100 32GB] 2.1 GHz 1.5TB RAM)

Объем полезного дискового пространства 840Tb.

На следующем графике показаны расчётные ускорения технологий MPI, OpenMP и автоматического распараллеливания.

Рисунок 38 - Сравнение расчётных ускорений OpenMP, MPI, автоматического распараллеливания

Видно, что при данном размере задачи, пересылка сообщений, используемая в технологии MPI с распределённой памятью, оказывается менее затратной операцией по сравнению с конкурирующим доступом к памяти, для технологии OpenMP с разделяемой памятью, и сборкой пакетов векторных вычислений при векторизации с использованием инструкций SSE2 и AVX2. Автоматическое распараллеливание при этом значительно уступает первым двум по ускорению, что вполне ожидаемо ввиду отсутствия значительных затрат на параллелизацию программы. Ясно, что при увеличении числа процессоров технология MPI будет показывать лучшее ускорение по сравнению с технологией OpenMP, поскольку вторая окажется менее эффективной из-за роста издержек на доступ к памяти. Для увеличения ускорения автоматического распараллеливания требуются новые инструкции векторных операций и, соответственно, наличие в процессоре больших размеров специальных регистров.

CUDA

OpenMP, MPI и автоматическое распараллеливание - это классический подход к параллельным вычислениям главной сутью которого является разбиение решаемой задачи на максимально независимые участки.

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

Совершенно иным подходом в реализации параллельных алгоритмов является CUDA - это созданная компанией NVIDIA архитектура параллельных вычислений, основным принципом которой является использование графического процессора (GPU) [31], что даёт более высокую вычислительную производительность, чем классические методы. Из-за работы с общей памятью и низкой стоимости создания потока подход к параллелизму CUDA значительно отличается от классических. Здесь число потоков обычно в разы превосходит количество вычислительных ядер.

Рассмотрим, как происходит запуск программы на графическом процессоре:

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

Хост копирует данные из своей памяти в память устройства

Хост запускает ядро на устройстве

Устройство исполняет это ядро

Хост копирует результаты из памяти устройства в свою память

На рисунке 39 изображены все перечисленные шаги запуска программы, кроме первого.



Рисунок 39 - Шаги запуска CUDA программы

Рисунок 40 - Взаимодействие CPU и GPU

Как видно из рисунка 40, центральный процессор взаимодействует с графическим через CUDA Runtime API, CUDA Driver API и CUDA Libraries. Runtime и Driver API отличаются уровнем абстракции. Первый вариант более высокого уровня в плане программирования, более абстрактный, а второй - напротив, более низкого (уровень драйвера).

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



Рисунок 41 - Архитектура CPU и GPU

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

GPU ориентирован на выполнение программ с большим объемом данных и расчетов, поэтому спроектирован как streaming processor array, то есть набор (массив) процессоров потокового типа, которые хранят в себе кластеры процессоров текстурного типа (Texture Processor Clusters, TPC). Вдобавок озвученный кластер имеет в своей структуре перечень мультипроцессоров (SM - Streaming Multi-processor, рис. 39). Во всех этих процессорах в свою очередь есть несколько процессоров потокового типа (SP - Streaming Processors) или ядер (в процессорах текущих поколений число ядер может быть больше 1024).

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



Рисунок 42 - Мультипроцессоры, SM

В конце концов GPU стал устройством, которое в прямом смысле способно реализовать модель вычислений потокового типа (stream computing model). В данной модели присутствуют потоки как данных, которые входят, так и исходят. Все эти данные состоят из одинаковых частей, которые могут быть обработаны раздельно (рис. 43).

Рисунок 43 - Потоковая вычислительная модель

CUDA использует большое количество отдельных потоков для расчетов, которые формируются в иерархию - grid / block / thread (рис. 44).



Рисунок 44 - Структура блоков

Уровень grid ответственен за отправку ответа ядру, а также за объединение каждого из потоков, что выполняются на этом ядре. Grid представляет собой одномерный или двумерный массив блоков (block). Все эти блоки являются независимым перечнем согласованных между собой потоков. Также стоит отметить, что у потоков, которые принадлежат различным блокам отсутствует возможность работать друг с другом.

Отличие от SIMD-архитектуры: существует понятие warp - группа из 32 потоков (в зависимости от архитектуры GPU, но почти всегда 32). Только потоки в рамках одной группы (warp) могут физически выполняться одновременно. Потоки из разных групп могут находиться на разных стадиях выполнения программы. Такой метод обработки данных обозначается термином SIMT (Single Instruction - Multiple Theads). Режим работы wrap управляется на аппаратном уровне.

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

Программно-аппаратная часть, используемая для вычислений на GPU, разработана Nvidia, и ее отличие от предшествующих поколений GPGPU состоит в том, что современная версия дает возможность писать для GPU программы, используя настоящий язык Си, имеющий стандартный синтаксис, указатели и с минимальным использованием расширений, обеспечивающих доступ к имеющимся у видеочипов вычислительным ресурсам [32]. Зависимость CUDA от API графического типа отсутствует, а наличие ряда особенностей, направленных на использование при вычислениях общего назначения, делает его особенно привлекательным для практического применения.

К числу преимуществ CUDA перед стандартным подходом к GPGPU можно отнести:

использование стандартного языка программирования Си с комплексом расширений;

наличие доступа к разбиваемой на потоки памяти, объем которой на мультипроцессор составляет 16 Кб. Она может быть задействована в качестве кэш-памяти с широкой пропускной способностью;

отсутствие требования по использованию графических API;

повышенная эффективность передачи информации между системной памятью и видеопамятью;

линейная адресация памяти;

аппаратная поддержка операций целочисленного и битового типа.

CUDA имеет несколько минусов:

рекурсия для реализуемых функций не поддерживается;

блок должен иметь ширину не менее 32 потоков;

архитектура закрытого типа.

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

CUDA имеет крайне удобный доступ к памяти. Так, в стандартных API, принадлежащих к графическому типу, программный код осуществляет ввод данных в формате набора из 32 вариаций с перемещающейся точкой одинарной точности в заблаговременно обозначенные области, в то время как CUDA может осуществлять безграничное число записей по всему многообразию адресов. Благодаря данной особенности открываются возможности реализации на GPU определенных алгоритмов, эффективное воплощение которых за счет базирующихся на графических API GPGPU не представляется возможным.

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

Ниже приведена программная реализация умножения матриц с использованием CUDA:



Рисунок 45 - Реализация умножения с использованием CUDA

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



6. Сравнение алгоритмов умножения разреженных матриц

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

Так как нам заранее неизвестна целевая архитектура, для распараллеливания были выбраны OpenMP, MPI и гибридизация MPI+OpenMP [33], так как при экспериментальном сравнении эти два метода показали практически идентичные результаты в ускорении, а их совместная работа позволит избегать накладных расходов на MPI-коммуникации внутри узла, получать передачу сообщений большего размера за меньшее время и динамическую балансировку загрузки, а также потенциально можно получить большее ускорение, чем при применении MPI или OpenMP в чистом виде, но только при запуске программы на кластере, так как MPI показывает свою пользу именно на системах с распределённой памятью.
Было принято решение не использовать CUDA, так как она работает только на графических процессорах, которые не всегда могут себе позволить исследовательские лаборатории, а для максимальной доступности разработанного модуля расчета моделируемой схемы с разреженными матрицами необходимо использовать общедоступные методы.

Работу итогового программного решения можно представить в виде UML - диаграммы использования (use-case).

Чтобы наглядно продемонстрировать эффективность работы разработанного модуля расчета, составим сравнительную таблицу времени выполнения алгоритма, где будет отображено время работы программы, используемой на данный момент в ПО “Satellite-MIEM”. В ускорение указано отношение времени выполнения параллельного алгоритма к последовательному.



Рисунок 46 - Диаграмма вариантов использования

Таблица 4 - Таблица сравнения времени выполнения вычислений в ПО “Satellite -MIEM”, последовательным и параллельным методами

Размерность разреженной матрицы	Время выполнения программ (мс)
	ПО “Satellite -MIEM”	Последовательный метод	Параллельные методы
			Open MP	Ускорение	MPI	Ускорение	OpenMP+MPI	Ускорение
50х50	3.2	0.2	0.4	0.5	0.4	0.5	0.4	0.50
100х100	26.2	0.4	0.7	0.57	0.8	0.5	0.8	0.50
500х500	1 336.3	7.1	6.4	1.09	7.1	1.1	6.9	1.03
1000х1000	17 054.5	45.2	31.83	1.42	40.36	1.12	35.7	1.27
2000х2000	133 405.9	291	188.96	1.54	303.13	0.96	226.2	1.29
5000х5000	2 584 362	3 465.5	2325.84	1.49	3208.80	1.08	2732.8	1.27
15000х15000	-	89 044.1	58581.64	1.52	91798.04	0.97	62945.1	1.41
20000х20000	-	195 509.6	132101	1.48	184443	1.06	139732.4	1.40



Рисунок 47- Сравнение отношений времени выполнения алгоритмов в зависимости от размера матриц

Рисунок 48 - Зависимость поэтапного (в зависимости от размера) увеличения времени выполнения алгоритма

Исходя из полученных данных, мы видим, что время выполнения последовательного алгоритма уменьшается экспоненциально и уже на размерах матрицы 5000х5000 достигло значения в 745 раз.

Все вычисления производились на системе с общей памятью, поэтому алгоритм с использованием OpenMP показывает наибольшее, по сравнению с MPI или OpenMP+MPI, ускорение в сравнении с последовательным алгоритмом. В случае гибридизации OpenMP+MPI это вызвано тем, что много времени расходуется на инициализацию MPI, а также на ожидание окончания вычислений на ядрах, а также процессов, которые выполняют пустую работу, к примеру, отправку процессорных сообщений «в пустоту». Упростить программирование с помощью данного подхода можно при наличии двух уровней параллелизма - параллелизма между подзадачами и параллелизма внутри подзадач. Организация взаимодействия подзадач не является сложной, так как сводится к обмену между ними граничными значениями.

Изучив специфику работы отдельно MPI (используя 2 процессора) и гибридизации OpenMP+MPI (используя 2 процессора по 2 ядра) допустимо предполагать, что на системах с распределенной памятью алгоритм может выполнять вычисления быстрее примерно на 40% «чистого» OpenMP.

Таким образом, мы видим, что разработанного программное решение позволяет в зависимости от размеров исходных матриц уменьшить время выполнения вычислений в сотни раз. Такие результаты позволяют эффективно интегрировать в ПО «Satellite-MIEM» разработанное программное решение для успешных исследований влияния электризации космических аппаратов.



7. Тестирование программного обеспечения на основании разработанных методик испытаний

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

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

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

Общесистемное тестирование. Основной сценарий работы программного модуля соответствует ожидаемому. Производится умножение матриц. Текст отображается корректно.

Рисунок 49 - Тестирование функции умножения

Модульное тестирование. Было проведено тестирование каждой функции в отдельности. Например, на рисунке 49 сверяется размер CRS векторовов функции умножения посредством сравнения с CRS векторами проверки. Также происходит вывод данных на экран для дополнительной визуальной проверки

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



Заключение

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

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

В результате проведенной работы был создан модуль расчета моделируемой схемы с разреженными матрицами, базирующийся на озвученных выше подходах. Исходя из результатов практических экспериментов можно утверждать, что разработанный модуль удовлетворяет поставленным требованиям и успешно справляется с проблемой вычисления разреженных матриц за время, приемлемое в рамках нашей задачи. Таким образом, поставленная цель достигнута с ускорением вычислений в сотни раз по отношению к результатам программы, используемой в ПО “Satellite-MIEM”.

Следующим направлением работ по развитию ПО “Satellite-MIEM” являются интеграция разработанного программного решения и перенос вычислительной задачи на суперкомпьютерный комплекс НИУ ВШЭ, который позиционируется как актуальный способ совершенствования вычислений для исследований в учебно-исследовательской лаборатории функциональной безопасности космических аппаратов и систем в области электризации космических аппаратов.

Данная разработка является актуальной на сегодняшний день и помимо того, что она может быть интегрирована в программное обеспечение “Satellite-MIEM”, она также может быть использована предприятиями, конструирующими космические аппараты и исследовательскими лабораториями, занимающимися изучением локальных геомагнитных возмущений.



Список сокращений

КА Космический аппарат

БРЭА Бортовая радиоэлектронная аппаратура

ЭСР Электростатический разряд

ПО Программное обеспечение

СЭМ Структурная электрофизическая модель

БКС Бортовая кабельная сеть

ЭЭС Эквиваленты электросхем

ОЗУ Оперативное запоминающее устройство

ОДУ Обыкновенное дифференциальное уравнение



Список использованных источников

[1] Востриков А. В., Абрамешин А. Е. Вычислительная схема ускоренного метода расчета наводок в бортовой кабельной сети космических аппаратов// Технологии электромагнитной совместимости. 2012. № 3. С. 22-28.

[2] Пожидаев Е.Д. и др. Повышение стойкости космических аппаратов к воздействию поражающих факторов. // «Космонавтика и ракетостроение», 2003, № 1 (30). - С. 32-35.

[3] Новиков Л.C., Бабкин Г.В., Морозов Е.П., Колосов С.А., Крупников К.К., Милеев B.Н., Саенко B.C. Комплексная методология определения параметров электростатической зарядки, электрических полей и пробоев на космических аппаратах в условиях их радиационной электризации. Руководство для конструкторов. ЦНИИМАШ, Королев 1995.

[4] D. Hastings, H. Garrett. Spacecraft-Environment Interactions. United Kingdom, Cambridge, Trumpington Street, The Pitt Building: The Press Syndicate of the University of Cambridge, 1996, pp. 1-14.

[5] M. Dhamodaran,“Capacitance Computation of Arbitrarily Shaped Conducting Bodies by Spacecraft Surface Charging Analysis,” 2016 International Conference on Communication Control and Computing Technologies (ICACCCT), Ramanathapuram, 2016, pp. 57-61.

[6] Frederickson A. Electric Discharge Pulses in Irradiated Solid Dielectrics in Space // IEEE Transactions on Electrical Insulation. 1983. Vol. EI-18. No. 3. P. 337-349.

[7] R. H. Alad, H. Shah, S. B. Chakrabarty, and D. Shah, "Effect of Solar Illumination on ESD for Structure Used in Spacecraft," Progress In Electromagnetics Research M, Vol. 55, pp. 25- 36, 2017.

[8] R. Hoffmann, et al., “Low-Fluence Electron Yields of Highly Insulating Materials,” IEEE Trans. on Plasma Science, Vol 36, No 5 (2008).

[9] Милеев В.Н., Новиков Л.С. Физико-математическая модель электризации ИСЗ на геостационарной и высокоэллиптических орбитах // Исследования по геомагнетизму, аэрономии и физике Солнца. - М.: Наука, 1989. С. 64-98.

[10] J. A. Roth. “Electrostatic Discharge in Spacecraft Materials.” Honors in University Studies with Departmental Honors thesis, Utah State University, Logan, 2009.

[11] P. K. Katsivelis et al., “Electrostatic Discharge Current Linear Approach and Circuit Design Method.” Energies vol. 3, pp.1728-1740, Nov. 2010.

[12] G. P. Fotis, I. F. Gonos, D. P. Iracleous and I. A. Stathopulos, "Mathematical analysis and simulation for the electrostatic discharge (ESD) according to the EN 61000-4-2," 39th International Universities Power Engineering Conference, 2004. UPEC 2004., Bristol, UK, 2004, pp. 228-232.

[13] Абрамешин А.Е. Компьютерное моделирование радиационного заряжения слабопроводящих диэлектриков / Абрамешин А.Е., Азаров М.Д., Пожидаева А.Е. // «Системный администратор», 2015, № 4. - С. 91-95.

[14] Barth, J. Measurements of real ESD threats that have been ignored too long. IEEE Instrum. Meas. Mag. 2005, 8, 61-63.

[15] Fotis, G.P.; Gonos, I.F.; Stathopulos, I.A. Determination of the discharge current equation parameters of ESD using genetic algorithms. IEE-Electron. Lett. 2006, 42, 797-799.

[16] Востриков А. В., Абрамешин А. Е., Борисов Н. И. Расчет наводок в бортовой кабельной сети космических аппаратов с помощью макромоделирования на основе методов Эйлера// Технологии электромагнитной совместимости. 2012. № 1 (40). С. 19-24.

[17] Математика и Математическое моделирование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2016. № 01. С. 1-27.

[18] Востриков А. В., Жадов А. Д., Борисов Н. И., Клышинский Э. С. Разработка и анализ редуцированной вычислительной схемы// Системный администратор. 2014. № 12. С. 90-95.

[19] Rizwan H. Alad, S. B. Chakrabarty, “Computation of Capacitance Matrix of Orbiting Spacecraft Bodies,” IETE Journal of Research, Vol.63, pp. 3-10, 2017.

[20] Farzaneh, A., H. Kheiri and M.A. Shahmersi, 2009. An efficient storage format for large sparse matrices. Commun. Fac. Sci. Univ., Ank. Series A1, 58(2): 1-10.

[21] Stanimiroviж, I.P. and M.B. Tasiж, 2009. Performance comparison of storage formats for sparse matrices. Facta Univ., (NIS) Ser. Math. Inform., 24: 39-51.

[22] A. M. Alabaichi, A. Alhusiny, E. M. Thabit. “A Novel Compressing a Sparse Matrix using Folding Technique”, Research Journal of Applied Sciences, Engineering and Technology, vol. 14, pp. 310-319, Aug. 2017.

[23] Мееров И.Б., Сысоев А.В. Разреженное матричное умножение. Учебное пособие. - М.: Нижний Новгород, 2011. - 81 с.

[24] R.Yuster, U. Zwick. “Fast Sparse Matrix Multiplication,” in Proc. European Symposium on Algorithms, 2004, pp. 604-615.

[25] Гергель В.П. Теория и практика параллельных вычислений. Учебное пособие. - ИНТУИТ, Бином. Лаборатория знаний, 2007. - 40 с.

[26] Антонов, А. С. Технологии параллельного программирования MPI и OpenMP / А.С. Антонов. - Москва: СПб. [и др.] : Питер, 2012. - 344 c.

[27] Gropp, W., Hoe?er, T., Thakur, R., Lusk, E.: Using Advanced MPI: Modern Features of the Message-Passing Interface. MIT Press (2014).

[28] Sheela Kathavate, N.K.Srikanth, "Efficient of Parallel Algorithms on Multi Core Systems Using OpenMP”, International Journal of Advanced Research in Computer and Communication Engineering, Vol. 3, Issue 10, October 2014.

[29] Плещинский Н.Б. Многопроцессорные вычислительные комплексы. Технологии параллельного программирования: Учебное пособие / Н.Б. Плещинский, И.Н. Плещинский. - Казанский федеральный университет, 2018. - 80 с.

[30] Буза, М.К. Проектирование программ для многоядерных процессоров. / М.К.Буза, О.М.Кондратьева. - Минск: БГУ, 2013. - 48 с.

[31] Боресков А.В., Харламов А.А. Параллельные вычисления на GPU. Архитектура и программная модель CUDA. Учебное пособие. - Издательство Московского университета, 2012 - 54 с.

[32] Miguel Cґardenas-Montes,” Accelerating Particle Swarm Algorithm with GPGPU,” 19th International Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2011.

[33] Rabenseifner R., Hager G., Jost G. Hybrid MPI/OpenMP Parallel Programming on Clusters of Multi-Core SMP Nodes // Proceedings of the 2009 17th Euromicro International Conference on Parallel, Distributed and Network-based Processing. 427-436 (2009).



Приложение

Таблица с результатами экспериментов произведенных способом, используемым в ПО “Satellite-MIEM”

Размер разреженной матрицы	Результаты экспериментов по номерам (мс)
	№1	№2	№3	№4	№5	№6	№7	№8	№9	№10
50х50	3	3	3	3	3	3	4	3	3	4
100х100	28	23	27	28	27	29	24	26	28	22
500х500	1415	1183	1308	1280	1404	1357	1328	1351	1369	1368
1000х1000	15663	17060	18357	16843	16955	16767	16941	18244	16885	16830
2000х2000	133530	133591	132894	132865	132659	133433	134512	132767	134630	133178
5000х5000	2385505	2653817	2341598	2876923	2715388	2453125	2398654	2561984	2674879	2781749
15000х15000	too long	too long	too long	too long	too long	too long	too long	too long	too long	too long
20000х20000	too long	too long	too long	too long	too long	too long	too long	too long	too long	too long

Таблица с результатами экспериментов произведенных с использованием CRS формата последовательным методом

Размер разреженной матрицы	Результаты экспериментов по номерам (мс)
	№1	№2	№3	№4	№5	№6	№7	№8	№9	№10
50х50	0	1	0	0	1	0	0	0	0	0
100х100	1	0	0	1	0	0	0	0	1	1
500х500	7	7	7	8	7	7	7	7	7	7
1000х1000	45	45	47	44	45	45	45	46	45	45
2000х2000	289	291	294	293	292	288	289	288	294	292
5000х5000	3453	3466	3460	3432	3454	3532	3466	3455	3456	3481
15000х15000	95479	83852	93263	83458	83714	93108	92112	93504	85716	86235
20000х20000	195789	195084	195190	195440	196715	195381	195154	195318	194901	196124

Таблица с результатами экспериментов произведенных с использованием CRS формата и Open MP

Размер разреженной матрицы	Результаты экспериментов по номерам (мс)
	№1	№2	№3	№4	№5	№6	№7	№8	№9	№10
50х50	0.41	0.54	0.27	0.31	0.53	0.32	0.59	0.49	0.30	0.58
100х100	0.75	0.93	0.83	0.53	0.57	0.38	0.74	0.93	0.85	0.83
500х500	3.45	2.93	3.48	3.49	3.29	3.54	2.91	2.85	3.93	3.86
1000х1000	23.7	24.1	25.7	27.7	27.1	27.2	25.2	24.3	26.8	24.9
2000х2000	162.05	159.43	160.15	163.02	163.01	162.33	160.13	163.12	158.91	160.09
5000х5000	1953.93	1881.64	1885.01	1946	1896	1962.4	1957.2	1921.4	1941.95	1913.22
15000х15000	49146.2	48937.2	48519.5	50124.	49617.	50231.	49112.	48435.	49917.9	48330.1
20000х20000	112217	109271	105251	101507	115833	107112	112607	111337	105381	105881

Таблица с результатами экспериментов произведенных с использованием CRS формата и MPI

Размер разреженной матрицы	Результаты экспериментов по номерам (мс)
	№1	№2	№3	№4	№5	№6	№7	№8	№9	№10
50х50	0.3	0.4	0.4	0.3	0.5	0.4	0.4	0.3	0.4	0.4
100х100	0.8	0.8	0.8	0.8	0.8	0.8	0.8	0.8	0.8	0.8
500х500	6.5	7.1	7.6	7.1	7.1	7.3	7.5	7.2	6.9	7
1000х1000	42.16	39.78	40.08	40.92	43.16	39.14	40.02	39.51	40.27	39.30
2000х2000	302.74	295.13	304.17	307.92	301.55	302.13	305.86	301.29	306.50	304.02
5000х5000	3215.80	3918.80	2968.30	2978.24	3216.30	3391.20	3238.74	2896.91	2968.78	3301.80
15000х15000	93719.32	91195.12	94198.71	89128.20	89591.5	92718.14	91003.9	94859.5	90496.6	91058.04
20000х20000	188158.46	181113.5	190893.9	189562.8	183910	178318.2	184448	187514	182122	182212

Таблица с результатами экспериментов произведенных с использованием CRS формата и гибридизации OpenMP+MPI

Размер разреженной матрицы	Результаты экспериментов по номерам (мс)
	№1	№2	№3	№4	№5	№6	№7	№8	№9	№10
50х50	0.3	0.4	0.4	0.3	0.5	0.4	0.4	0.3	0.4	0.4
100х100	0.8	0.8	0.8	0.8	0.8	0.8	0.8	0.8	0.8	0.8
500х500	6.5	7.1	7.6	6.6	7.1	5.9	7.5	7.2	6.1	7
1000х1000	37.16	26.43	38.08	39.92	33.16	39.14	45.02	29.51	28.27	39.30
2000х2000	216.74	195.13	254.17	219.92	261.55	219.13	235.86	201.29	186.50	259.02
5000х5000	2918.80	3191.80	3218.30	2818.24	2591.3	2499.2	2238.7	2721.9	2758.78	2601.80
15000х15000	67549.32	62815.12	54198.71	70198.2	59591	59718	65003	65129	62496.64	62758.04
20000х20000	135158.46	138113.59	134893.92	141562	145910	139318	139448	140514	139122.62	137212

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

...