Householder (reflections) reduction of a matrix to bidiagonal form, locality
Содержание
1 Ссылки
2 Локальность данных и вычислений
К сожалению, в графе в наличии пучки рассылок, в них неизбежно часть дуг остаются длинными, что отрицательно влияет на локальность вычислений по пространству.
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
На рис. 1 представлен профиль обращений в память для реализации метода Хаусхолдера (отражений) приведения матрицы к двухдиагональной форме. Данный профиль обладает явной итерационной структурой, причем видно, что на каждой следующей итерации из рассмотрения отбрасывается небольшая часть элементов из начала массива данных. Также можно заметить, что основная часть данных используется достаточно равномерно в рамках одной итерации, однако в нижней и верхней частях итерации видны небольшие блоки с очень высокой локальностью обращений. Итерации явно устроены по одному принципу, поэтому стоит рассмотреть одну из них более детально.
На рис. 2 показаны обращения в рамках первой итерации общего профиля (выделена на рис. 1 зеленым). Эти обращения можно условно разбить на несколько фрагментов. Фрагменты 1, 2 и 6 практически идентичны (различие заключается только в перестановке местами двух частей этих фрагментов), рассмотрим один из них.
На рис. 3 показан отдельно фрагмент 6, выделенный на рис. 2. Теперь можно определить структуру каждой из двух частей более точно. Первая часть представляет собой последовательный перебор элементов в обратном порядке, причем к каждому элементу выполняется несколько обращений подряд. Во второй части также наблюдается последовательный перебор, однако с другими свойствами: элементы перебираются в прямом порядке, к каждому элементу выполняется только 1 обращение, однако данный перебор повторяется несколько раз подряд, причем каждый раз задействованы одни и те же элементы. Все это позволяет говорить о высокой пространственной локальности фрагмента (поскольку шаг по памяти каждый раз небольшой) и достаточно высокой временной локальности (поскольку данные часто используются повторно).
Свойства локальности во фрагментах 3 и 5 можно оценить и без более детального рассмотрения. Данные в обоих фрагментах перебираются с достаточно большим шагом по памяти, при этом повторно они почти не используются, что говорит о низкой локальности в обоих случаях (хотя надо отметить, что локальность фрагмента 5 немного выше из-за более высокой пространственной локальности).
Теперь перейдем к рассмотрению фрагмента 4, расположенного в центре рис. 2. Поскольку он обладает регулярной структурой, достаточно более детально изучить небольшой фрагмент (представлен на рис. 4, выделен на рис. 3 зеленым). Здесь можно увидеть, что первая часть фрагмента представляет собой практически стандартный последовательный перебор (с небольшими нечастыми сдвигами, которые не влияют на локальность). Такой набор обращений обладает высокой пространственной и низкой временной локальностью. Вторая часть данного фрагмента устроена несколько сложнее – она состоит из L-образных наборов обращений. Одна его область (часть 1 на рис. 4) по строению очень похожа на первую часть; вторая (часть 2 на рис. 4) представляет собой набор обращений к одному и тому же элементу, что достаточно сильно повышает локальность данного фрагмента. Из этого можно сделать вывод, что фрагмент 4 обладает высокой пространственной и средней временной локальностью.
Суммируя выше сказанное, можно сказать, что фрагменты 1, 2 и 6 обладают высокой локальностью; фрагменты 3 и 5 – низкой локальностью; фрагмент 4 – высокой пространственной и средней временной локальностью. Можно предположить, что в итоге локальность общего профиля будет не очень высокой, в основном из-за более низкой временной локальности. Однако такое достаточно сложное строение общего профиля затрудняет оценку локальности общего профиля на основе визуального анализа.
2.1.2 Количественная оценка локальности
Оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
На рисунке 5 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что оценка производительности в данном случае не очень высока, что подтверждает сделанные ранее выводы. В частности, значение daps для этого примера показывает более низкую производительность по сравнению с реализациями других методов Хаусхолдера (householder_qr householder_qtq) и находится примерно на уровне оценки для реализации метода Холецкого.
