Уровень реализации

Lanczos, C, MPI

Материал из Алговики
Версия от 18:01, 7 июля 2022; ASA (обсуждение | вклад) (Новая страница: «{{level-i}} = Ссылки = Для исследования масшабируемости алгоритма была написана реализация н...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к навигации Перейти к поиску


1 Ссылки

Для исследования масшабируемости алгоритма была написана реализация на языке C с использованием MPI.

2 Локальность данных и вычислений

2.1 Локальность реализации алгоритма

2.1.1 Структура обращений в память и качественная оценка локальности

2.1.2 Количественная оценка локальности

3 Масштабируемость алгоритма и его реализации

3.1 Масштабируемость алгоритма

3.2 Масштабируемость реализации алгоритма

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

Сборка осуществлялась со следующими параметрами:

  • gcc-5.2.0
  • openmpi-1.8.4
  • аргументы компилятора: -std=c11 -Ofast

Набор и границы значений изменяемых параметров реализации алгоритма:

  • число процессоров [32 : 256] с шагом 16;
  • размер матрицы [5000 : 200000] с шагом 5000.

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

  • минимальная эффективность реализации 1.92%;
  • максимальная эффективность реализации 59.47%.

График полученного распределения эффективности:

Рисунок 1. Параллельная реализация алгоритма Ланцоша. Распределение производительности.

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

Рисунок 2. Параллельная реализация алгоритма Ланцоша. Изменение производительности в зависимости от числа процессоров и размера матрицы.
Рисунок 3. Параллельная реализация алгоритма Ланцоша. Изменение эффективности в зависимости от числа процессоров и размера матрицы.

Средняя эффективность для матриц с размером больше 25000 составила 52.7%.

4 Динамические характеристики и эффективность реализации алгоритма

5 Результаты прогонов