Householder (reflections) method for the QR decomposition, locality
Содержание
1 Ссылки
2 Локальность данных и вычислений
К сожалению, в графе, как видно по рисунку, в наличии пучки рассылок, в них неизбежно часть дуг остаются длинными, что отрицательно влияет на локальность вычислений по пространству.
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
На рис. 1 представлен профиль обращений в память для реализации вещественного варианта метода Хаусхолдера (отражений) QR-разложения квадратной матрицы. Из данного рисунка можно сделать несколько выводов. Во-первых, видно, что в среднем к каждому элементу выполняется примерно 90 обращений (отношение общего числа обращений к числу задействованных данных), что является достаточно хорошим показателем в плане повторного использования данных. Далее, явно видна итерационная структура профиля, причем на каждой следующей итерации обращения к небольшой части первых элементов перестают выполняться. Это говорит о том, что ближе к концу профиля задействовано меньше данных, что хорошо сказывается на пространственной локальности. Однако в то же время видно, что на каждой следующей итерации выполняется меньше обращений к одним и тем же локальным областям, то есть временная локальность, по всей вероятности, становится ниже. Рассмотрим подробнее первую итерацию, что более детально оценить их строение.
На рис. 2 представлена одна итерация общего профиля (выделенный зеленый фрагмент на рис. 1). Ее можно условно разбить на 5 фрагментов, каждую из которых рассмотреть отдельно. Фрагменты 2 и 5 устроены просто – элементы перебираются с большим шагом по памяти, при достижении конца данных перебор повторяется, только с небольшим сдвигом. Про такие фрагменты можно сказать, что они обладают низкой пространственной локальностью, поскольку шаг по памяти достаточно большой, и низкой временной локальностью, так как данные повторно не используются. Однако отметим, что данные фрагменты состоят из небольшого числа обращений, что означает, что они не так сильно будут снижать общую локальность профиля.
Далее, фрагмент 1 и 3 устроены практически идентично (основное отличие – два основных этапа переставлены местами), поэтому рассмотрим только один из них. На рис. 3 представлен фрагмент 3. Здесь хорошо видно, как устроены эти этапы. На первом этапе выполняется перебор элементов в обратном порядке с шагом 1, при этом к каждому элементу подряд обращаются несколько раз. Такой фрагмент обладает очень высокой пространственной локальностью и достаточно высокой временной локальностью.
На втором этапе также выполняется последовательный перебор, но уже с небольшим шагом, и к каждому элементу обращаются только по 1 разу на каждой итерации. Однако, поскольку в каждой небольшой итерации на втором этапе всего около 30 обращений, повторное обращение к каждому элементу происходит недалеко от предыдущего, что говорит о достаточно высокой временной локальности. Пространственная локальность также высока, поскольку шаг по памяти невелик.
Далее рассмотрим фрагмент 4. Чтобы лучше понять локальную структуру, детально изучим небольшую его часть (рис. 4). Из данного рисунка хорошо видно, что здесь профиль устроен очень просто и представляет собой обычный последовательный перебор с шагом 1 (с небольшими и нечастыми сдвигами, которые не влияют на локальность этого фрагмента). Такой фрагмент обладает высокой пространственной, но низкой временной локальностью.
В целом можно сказать, что одна итерация обладает высокой пространственной и средней временной локальностью, хотя она несколько снижается из-за наличия фрагментов 2, 4 и 5. При условии, что итерации подобны, выводы относительно локальности одной итерации можно перенести и на общий профиль.
2.1.2 Количественная оценка локальности
Оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
На рисунке 5 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность работы с памятью в данном примере высока. Значение daps для него находится на одном уровне с тестом Linpack и лишь немногим ниже, чем, например, самые эффективные варианты перемножения плотных матриц. Это означает, что негативное влияние фрагментов 2 и 5 оказывается достаточно слабым, вероятно (как и предполагалось ранее) из-за небольшого их размера.
