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

One step of the dqds, LAPACK

Материал из Алговики
Перейти к навигации Перейти к поиску


Основные авторы описания: И.В.Афанасьев

1 Ссылки

Исследованная параллельная реализация на языке C.

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

Легко видеть, что локальность данных высока. Её легко повысить, размещая рядом соответствующие элементы массивов e и q, однако, это не оказывает существенного влияния на производительность в силу константного количества операций относительно объема обрабатываемых данных.

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

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

Рисунок 1. Итерация алгоритма dqds. Общий профиль обращений в память

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

Рассмотрим более детально строение одного из переборов (второй устроен практически идентично). На рис. 2 показан выделенный на рис. 1 небольшой фрагмент 1. Видно, что на каждом шаге в данном переборе выполняется три обращения в память; подобное строение говорит о высокой пространственной локальности, однако низкой временной, поскольку данные повторно используются только по 3 раза.

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

Рисунок 2. Профиль обращений, фрагмент 1

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

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

На рисунке 3 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Результат получен достаточно неожиданный – производительность работы с памятью очень невелика. Оценка daps для данного профиля сравнима с реализациями самых неэффективных алгоритмов в части работы с памятью – тестов RandomAccess и неэффективных вариантов обычного перемножения матриц. Отчасти это может объясняться низкой временной локальностью. Однако в данном случае причина может также заключаться в том, что в данной реализации объем вычислений на одно обращение в память достаточно велик, что может приводить к недостаточной загруженности подсистемы памяти. В таком случае, несмотря на в целом неплохую эффективность работы с памятью, производительность будет достаточно низка.

Рисунок 3. Сравнение значений оценки daps

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

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

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

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

Проведём исследование масштабируемости вширь реализации согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов-2" Суперкомпьютерного комплекса Московского университета.

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

  • число процессоров 1;
  • размер матрицы [1000 : 260000] с шагом 500.

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

  • минимальная эффективность реализации 2.559e-06%;
  • максимальная эффективность реализации 2.492e-08%.

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

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

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

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