СРАВНИТЕЛЬНЫЙ АНАЛИЗ РАБОТЫ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ МАТРИЧНЫХ ОПЕРАЦИЙ ДЛЯ ПОЛНЫХ И РАЗРЕЖЕННЫХ МАТРИЦ В МНОГОЯДЕРНЫХ CPU-СИСТЕМАХ

COMPARATIVE ANALYSIS OF PARALLEL ALGORITHMS OF MATRIX OPERATIONS FOR FULL AND SPARSE MATRICES IN MULTI-CORE CPU SYSTEMS

Khamilla Khabaeva

student, Department of Information Technologies and Systems, North Caucasus Mining and Metallurgical Institute (State Technological University),

Russia, Vladikavkaz,

Alisher Kulchimaev

student, Department of Computer Modeling and Automation of Design, North Caucasus Mining and Metallurgical Institute (State Technological University),

Russia, Vladikavkaz

АННОТАЦИЯ

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

ABSTRACT

As part of the work, an analytical review of the subject area was conducted, a mathematical model was selected that minimizes the running time of parallel algorithms of matrix operations, parallel algorithms were developed that use multi-core computing systems for operation. A software package was also created that implements these parallel algorithms for operations on full and sparse matrices. A series of experiments were conducted to confirm the adequacy of the selected mathematical model and the effectiveness of the software package.

Ключевые слова: распараллеливания, умножение матриц, c++, сложение матриц, умножение матрицы на константу, транспонирование матриц, сравнительный анализ, многоядерные cpu-системы, параллельный алгоритм.

Keywords: parallelization, matrix multiplication, C++, matrix addition, matrix multiplication by a constant, matrix transposition, comparative analysis, multi-core CPU systems, parallel algorithm.

Введение

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

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

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

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

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

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

Цели экспериментов:

• Определение времени, необходимого для выполнения матричных операций;
• Нахождение коэффициентов k из уравнений;
• Проверка корректности уравнений.

Эксперименты проводились на ПК с характеристиками, представленными в Таблице 1. Основной параметр, исследуемый в работе программного комплекса, — это время его выполнения.

Для измерения времени выполнения программы использовался класс Stopwatch. Время выполнения сохраняется в Stopwatch.Elapsed.

Таблица 1

Характеристики ПК

В рамках работы была проведена серия экспериментов с целью определения двух зависимостей:

• зависимость времени выполнения матричной операции от количества используемых потоков и размера матрицы;
• зависимость времени выполнения от размера матрицы при использовании одного потока и оптимального количества потоков.

Ход эксперимента:

В ходе эксперимента для матричной операции умножения полной и разреженной матриц брались исходные матрицы размером: 2000, 3000, 4000, 5000, 6000. Количество потоков менялось от 1 до 6. Было проведено по 50 замеров для каждого размера матрицы. Полученное время записывалось в файл.

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

Таблица 2

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

Таблица 3.

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

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

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

Ниже представлена таблица, в которой записаны коэффициенты

k10, k11, k12, k13, k14, k15, k16, k17, k18, k19:

Таблица 4.

Коэффициенты k_i для билинейной интерполяции

Рисунок 2. Сумма квадратов разности (St) и средняя ошибка аппроксимации (At)

Результат:

В результате эксперимента на основе выражения (2.5) получены следующие данные:

Таблица 5

Аналитические данные времени работы

Рисунок 3. Аналитическая и экспериментальная зависимости времени счета от числа потоков при размере матрицы, равным 3000²

Рисунок 4. Зависимость времени решения функции одним потоком и оптимальным количеством потоков

Таблица 6.

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

Рисунок 5. Время выполнения операции разным числом потоков в зависимости от размера матрицы

Множественный коэффициент корреляции равен 0,943.

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

Для операции умножения разреженных матриц у меня используется математическая модель 2.4, в которой были найдены коэффициенты k₁₀, k₁₁, k₁₂, k_13, k₁₄, k₁₅, k₁₆, k_17, k_18, k₁₉ (Таблица 4.9).

Таблица 7.

Коэффициенты k_i для операции умножения разреженных матриц

Таблица 8

Сумма квадратов разности (St) и средняя ошибка ап- аппроксимации (At)

Результат:

В результате эксперимента на основе выражения (2.6) получены следующие данные:

Таблица 9

Аналитические данные времени работы

Рисунок 6. Аналитическая и экспериментальная зависимости времени счета от числа потоков при количестве элементов матрицы, равным 5000²

Проведем сравнительный анализ при параллельном и последовательном режиме. На графике 4.5. показана зависимость времени решения функции на одном потоке и на оптимальном числе потоков.

Таблица 10.

Время решения на одном и на оптимальном количестве потоков

Рисунок 7. Зависимость времени решения одним и оптимальным количеством потоков

Эксперимент показал эффективность разработанного программного комплекса, так как реализованный мною параллельный алгоритм дал значительный прирост производительности, в сравнении с последовательно работающим алгоритмом. Также показал адекватность выбранной математической модели, так как экспериментальные данные практически совпали с аналитическими.

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

Заключение

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

В ходе работы были выполнены следующие задачи:

1. Разработаны и реализованы параллельные алгоритмы для выполнения основных матричных операций, таких как сложение и умножение, для полных и разреженных матриц.
2. Проведены экспериментальные исследования производительности разработанных алгоритмов на различных типах матриц и в различных режимах параллельного выполнения.
3. Осуществлен анализ полученных результатов с точки зрения времени выполнения, использования вычислительных ресурсов и масштабируемости.

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

1. Мирошников А. С. Система управления параллельной обработки данных в локальных вычислительных сетях. Дисс… канд. техн. наук. Владикавказ, 2000.
2. Голубев В. В. "Численные методы линейной алгебры". - М.: Триумф, 2003. – 806 с.
3. Воронов В. В., Базылев П. Н. "Линейная алгебра и численные методы"- М.: Аст, Астрель, 2006. – 446 с.
4. Фаддеев Д. К., Фаддеева В. Н. "Вычислительные методы линейной алгебры" - 2009. – 576 с.
5. Пономарев А. Г. "Алгоритмы и методы оптимизации". — 2006. — С. 390. — 879
6. Преображенский Н. А. "Математические методы и алгоритмы обработки разреженных матриц" - М.: Триумф, 2009. – 396 с.
7. Ильин В. А., Ким В. П. "Методы вычислений" - 2006. – 446 с.
8. Эндрю Троелсен: Язык программирования C++. М.: Вильямс 2018 - 4-е изд. 1344 с.