Householder (reflections) method for reducing a symmetric matrix to tridiagonal form, locality
Содержание
1 Ссылки
Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен здесь).
2 Локальность данных и вычислений
К сожалению, в графе, как видно по рисунку, в наличии пучки рассылок, в них неизбежно часть дуг остаются длинными, что отрицательно влияет на локальность вычислений по пространству.
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
На рис. 1 представлен профиль обращений в память для реализации метода Хаусхолдера (отражений) для приведения симметричных матриц к трёхдиагональному виду. Данный профиль обладает явной итерационной структурой, при этом видно, что итерации очень похожи. Основное их отличие заключается в наборе используемых данных – на каждой следующей итерации несколько первых элементов отбрасываются их рассмотрения, то есть чем позже итерация, тем меньше данных в ней задействовано. Также можно отметить, что число обращений в каждой последующей итерации немного уменьшается. Для того чтобы проанализировать общий профиль, в таком случае чаще всего достаточно изучить одну итерацию. Рассмотрим самую первую из них более детально.
На рис. 2 показан набор обращений в рамках первой итерации (выделен на рис. 1 зеленым). Его можно разбить на несколько фрагментов и рассмотреть их отдельно. Строение фрагментов 2-5 можно оценить по общему графику для итерации. Фрагмент 2 представляет собой набор последовательных переборов в обратном порядке с небольшим шагом, причем число элементов в переборе постепенно уменьшается. Такое строение характеризуется достаточно высокой пространственной локальностью, поскольку часто происходит обращений к близко расположенным данным, однако низкой временной, поскольку данные повторно не используются. То же самое верно и для фрагмента 4, основное отличие которого заключается в том, что переборы выполняются в прямом порядке. Отметим, что некоторое искривление данного фрагмента связано не со строением самого фрагмента, а с разным числом параллельно выполняющихся обращений (см., например, правую область фрагмента 6), чего не наблюдается при выполнении фрагмента 2.
Далее, фрагменты 3 и 5 состоят из небольшого числа обращений к данным, расположенным далеко друг от друга. Такие фрагменты характеризуются низкой пространственной и временной локальностью.
Оставшиеся фрагменты требуют более детального рассмотрения. Перейдем к изучению фрагмента 1, который целиком представлен на рис. 3. Здесь мы можем видеть несколько этапов, каждый из которых представляет собой последовательный перебор элементов с шагом по памяти 1, причем в некоторых случаях данные много раз используются повторно (особенно это заметно в правой нижней области рисунка, где выполняется множество обращений к одному и тому же элементу). При условии, что в данном фрагменте задействовано всего около 40 элементов, можно говорить, что данный набор обращений обладает высокой пространственной и временной локальностью.
Далее рассмотрим детально фрагмент 6 (рис. 4). Здесь можно увидеть, что повторные обращения к данным выполняются не подряд, а через некоторые промежутки, однако число задействованных элементов также очень невелико, так что и в этом случае локальность (и пространственная, и временная) будет высокой.
В целом можно сказать, что рассматриваемая итерация обладает достаточно высокой пространственной и временной локальностью. Поскольку остальные итерации устроены подобным образом, данные вывод можно перенести и на общий профиль обращений.
2.1.2 Количественная оценка локальности
Оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
На рисунке 5 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность работы с памятью в данном случае достаточно высока – значение daps лишь немногим уступает тесту Linpack, который обладает высокой эффективностью работы с памятью, и немного превосходит, например, реализацию метода Якоби или метода Гаусса.
