Poisson equation, solving with DFT, locality

Основные авторы описания: Вад.В.Воеводин (раздел 2).

1 Ссылки

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен здесь (функция Kernel).

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

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

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

Рисунок 1. Уравнение Пуассона, решение дискретным преобразованием Фурье. Общий профиль обращений в память

На рис. 1 представлен профиль обращений в память для реализации уравнения Пуассона, решение дискретным преобразованием Фурье. Данный профиль состоит из обращений к нескольким служебным массивам (фрагмент 1) и основному массиву (фрагмент 2). Видно, что профиль делится на два практически одинаковых этапа (вертикальная желтая линия). В целом можно отметить, что общее количество элементов невелико (чуть более 1000 элементов), при этом профиль составляет около 100 тысяч обращений. При этом видно, что в верхней части профиля плотность обращений выше, что говорит, вероятно, о высокой локальности вычислений; однако обращения к основному массиву достаточно разрознены. Перейдем к более детальному рассмотрению локальности.

На рис. 2 представлен фрагмент 1, на котором расположены все обращения к служебным массивам. Исходя только из данного графика, нельзя сказать, какова структура обращения внутри блоков, однако в данном случае это и не требуется. Общее число задействованных адресов мало – всего порядка 100 элементов, при этом они используются в течение всей программы. Более того, они организованы в блочную структуру, что улучшает работу с памятью. Поэтому можно с уверенностью сказать, что локальность (как пространственная, так и временная) в данном случае очень высока.

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

Перейдем к рассмотрению основного массива. На рис. 3 представлен фрагмент 2 от общего профиля, показанного на рис. 1. Можно сразу же отметить следующий факт. На графике представлено максимум несколько сотен обращений, а по оси Х стоит отметка более 35000. Это значит, что значительно больше обращений происходит вне этого фрагмента, а именно в служебных массивах. То есть в целом обращения к основному массиву происходят не так часто. Это подтверждается при рассмотрении исходного кода программы: данные из основного массива на самом деле только копируются в служебные массивы, где над ними выполняются преобразование Фурье, после чего они копируются обратно.

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

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

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

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

Условия запуска описаны здесь.

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

На рис. 4 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Здесь мы можем наблюдать несколько неожиданный результат – производительность работы с памятью достаточно низкая, несмотря на предполагаемую высокую локальность.

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

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

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

На рис. 5 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем, в общем случае, выше локальность). Можно увидеть, что, как и в случае алгоритма Кули-Тьюки, локальность оценивается как очень высокая. Поскольку в данной программе реализации этого алгоритма посвящена большая часть общего профиля, то и причины такого расхождения между локальностью и производительностью в данных случаях одинаковы (см. подробное рассмотрение алгоритма Кули-Тьюки).

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

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

[Категория:Статьи в работе]]