Bellman-Ford, locality

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

1 Ссылки

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

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

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

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

Рисунок 1. Алгоритм Беллмана-Форда. Общий профиль обращений в память

На рис. 1 представлен профиль обращений в память для реализации алгоритма Беллмана-Форда. Первое, что сразу стоит отметить – число обращений в память гораздо больше числа задействованных данных. Это говорит о частом повторном использовании одних и тех же данных, что обычно приводит к высокой временной локальности. Далее, видна явная регулярная структура производимых обращений в память, видны повторяющиеся итерации работы алгоритма. Практически все обращения образуют фрагменты, похожие на последовательный перебор, кроме самой верхней части, где наблюдается более сложная структура.

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

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

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

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

Чтобы понять структуру обращений в память в верхней части, можно рассмотреть ее еще подробнее. Приведем визуализацию небольшой области фрагмента 2, выделенной на рис. 3 зеленым. Однако в данном случае дальнейшее приближение (рис. 4) не привносит большей ясности: видна нерегулярная структура внутри итерации, характер которой достаточно сложно описать. Но в данном случае этого и не требуется – можно заметить, что по вертикали отложено всего 15 элементов, при этом обращений к ним выполняется гораздо больше. Независимо от структуры обращений, такой профиль обладает очень высокой как пространственной, так и временной локальностью.

Рисунок 4. Небольшая часть фрагмента 2

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

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

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

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

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