Сравнение алгоритмов умножения матриц

Учебный проект на C++ для проверки корректности и сравнения производительности двух способов умножения матриц: классического и оптимизированного блочного. Программа генерирует квадратную матрицу размером 2048 × 2048, запускает каждый алгоритм и выводит время выполнения.

Программа специально оптимизирована для процессора Intel I5 10400.

Что реализовано

• собственная структура matrix с непрерывным хранением элементов типа float;
• создание, копирование, перемещение и транспонирование матриц;
• классическое умножение матриц за O(n³);
• блочное умножение с размером блока 64 × 64;
• транспонирование второй матрицы для последовательного доступа к памяти;
• набор небольших тестов для проверки корректности алгоритмов;
• измерение времени через монотонные часы CLOCK_MONOTONIC;
• фиксация страниц процесса в оперативной памяти через mlockall, чтобы уменьшить влияние подкачки на результаты замеров.

Алгоритмы

Классическое умножение

Функция basic_multiply вычисляет каждый элемент результирующей матрицы по формуле:

C[i][j] = Σ A[i][k] × B[k][j]

Это простая эталонная реализация, с которой сравнивается оптимизированный вариант.

Блочное умножение

Функция optimised_multiply сначала транспонирует вторую матрицу, а затем обрабатывает данные блоками 64 × 64. Такой порядок улучшает локальность обращений к памяти и позволяет эффективнее использовать кеш процессора.

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

Структура проекта

Файл	Назначение
main.cpp	Генерация данных, проверка алгоритмов, замеры и вывод результатов
matrix.h	Структура матрицы, доступ к строкам, сравнение и транспонирование
basic_multiply.h	Классический алгоритм умножения
optimised.h	Оптимизированное блочное умножение
wrong_multiply.h	Заведомо неверная реализация для проверки механизма тестирования
utility.h	Тестовые примеры и вычисление разницы между отметками времени
CMakeLists.txt	Конфигурация сборки CMake

Требования

• CMake 3.10 или новее;
• компилятор с поддержкой C++23;
• Linux или WSL.

Проект использует POSIX-заголовок <sys/mman.h> и функции mlockall и clock_gettime. Для сборки в Windows через MinGW потребуется заменить или условно отключить эти вызовы.

Сборка и запуск

Для измерения производительности рекомендуется сборка Release:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build
./build/matrix_multiply_test

Сборка Debug включает AddressSanitizer, LeakSanitizer и UndefinedBehaviorSanitizer:

cmake -S . -B build-debug -DCMAKE_BUILD_TYPE=Debug
cmake --build build-debug
./build-debug/matrix_multiply_test

Формат результата

После проверки и выполнения алгоритмов программа печатает таблицу примерно такого вида:

|                        RESULTS                        |
|            optimised_multiply |   1sec  234567890nsec |
|                basic_multiply |  10sec  123456789nsec |

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

Настройка эксперимента

Размер тестовой матрицы задаётся в main.cpp:

size_t const big_r = 2048;
size_t const big_c = 2048;

Размер блока оптимизированного алгоритма задаётся в optimised.h:

constexpr size_t BLOCK_SIZE = 64;

Эти значения можно менять, чтобы сравнить производительность на разных объёмах данных и подобрать размер блока под кеш конкретного процессора.