ASA в 09:45, 7 июля 2022

2022-07-07T09:45:30Z

← Предыдущая версия		Версия от 09:45, 7 июля 2022
Строка 5:		Строка 5:
	= Ссылки =		= Ссылки =

	Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/benchmarks/holecky/holecky.h здесь] (функция Kernel)~~. Условия запуска описаны [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/README.md здесь]~~.		Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/benchmarks/holecky/holecky.h здесь] (функция Kernel).

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

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

			Условия запуска описаны [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/README.md здесь].

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

ASA в 06:13, 3 июля 2022

2022-07-03T06:13:19Z

← Предыдущая версия		Версия от 06:13, 3 июля 2022
Строка 61:		Строка 61:
	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

	[[En:~~The computational core of the Graph500 benchmark on MPI~~]]		[[En:Cholesky decomposition, locality]]

ASA: Новая страница: «{{level-i}} Основные авторы описания: Вад.В.Воеводин (#Описание локальности...»

2022-07-03T06:12:34Z

Новая страница: «{{level-i}} Основные авторы описания: Вад.В.Воеводин (#Описание локальности...»

Новая страница

{{level-i}}

Основные авторы описания: [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2]])

= Ссылки =

Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/benchmarks/holecky/holecky.h здесь] (функция Kernel). Условия запуска описаны [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/README.md здесь].

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

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

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

[[file:Cholesky_locality1.jpg|thumb|center|700px|Рисунок 1. Реализация метода Холецкого. Общий профиль обращений в память]]

На рис.1 представлен профиль обращений в память<ref>Воеводин Вад. В. Визуализация и анализ профиля обращений в память // Вестник Южно-Уральского государственного университета. Серия Математическое моделирование и про-граммирование. — 2011. — Т. 17, № 234. — С. 76–84.</ref><ref>Воеводин Вл. В., Воеводин Вад. В. Спасительная локальность суперкомпьютеров // Открытые системы. — 2013. — № 9. — С. 12–15.</ref> для реализации метода Холецкого. В программе задействован только один массив, поэтому в данном случае обращения в профиле происходят только к элементам этого массива. Программа состоит из одного основного этапа, который, в свою очередь, состоит из последовательности подобных итераций. Пример одной итерации выделен зеленым цветом.

Видно, что на каждой <math>i</math>-й итерации используются все адреса, начиная с некоторого, при этом адрес первого обрабатываемого элемента увеличивается. Также можно заметить, что число обращений в память на каждой итерации растет примерно до середины работы программы, после чего уменьшается вплоть до завершения работы. Это позволяет говорить о том, что данные в программе используются неравномерно, при этом многие итерации, особенно в начале выполнения программы, задействуют большой объем данных, что приводит к ухудшению локальности.

Однако в данном случае основным фактором, влияющим на локальность работы с памятью, является строение итерации. Рассмотрим фрагмент профиля, соответствующий нескольким первым итерациям.

[[file:Cholesky_locality2.jpg|thumb|center|700px|Рисунок 2. Реализация метода Холецкого. Фрагмент профиля (несколько первых итераций)]]

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

Фрагмент 2 устроен гораздо лучше с точки зрения локальности. В рамках этого фрагмента выполняется большое число обращений подряд к одним и тем же данным, что обеспечивает гораздо более высокую степень как пространственной, так и временно́й локальности по сравнению с фрагментом 1.

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

[[file:Cholesky_locality3.jpg|thumb|center|700px|Рисунок 3. Реализация метода Холецкого. Фрагмент профиля (часть одной итерации)]]

Рис.3, на котором представлена часть одной итерации общего профиля (см. рис.1), позволяет отметить достаточно интересный факт: строение каждого из фрагментов на самом деле заметно сложнее, чем это выглядит на рис.2. В частности, каждый шаг фрагмента 1 состоит из нескольких обращений к соседним адресам, причем выполняется не последовательный перебор. Также можно увидеть, что фрагмент 2 на самом деле в свою очередь состоит из повторяющихся итераций, при этом видно, что каждый шаг фрагмента 1 соответствует одной итерации фрагмента 2 (выделено зеленым на рис.3). Это лишний раз говорит о том, что для точного понимания локальной структуры профиля необходимо его рассмотреть на уровне отдельных обращений.

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

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

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

[[file:Cholesky_locality4.jpg|thumb|center|700px|Рисунок 4. Сравнение значений оценки daps]]

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

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

[[file:Cholesky_locality5.jpg|thumb|center|700px|Рисунок 5. Сравнение значений оценки cvg]]

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

= Масштабируемость алгоритма и его реализации =
== Масштабируемость алгоритма ==
== Масштабируемость реализации алгоритма ==
= Динамические характеристики и эффективность реализации алгоритма =
= Результаты прогонов =

= Литература =

<references />

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

[[En:The computational core of the Graph500 benchmark on MPI]]

Cholesky decomposition, locality - История изменений

ASA в 09:45, 7 июля 2022

ASA в 06:13, 3 июля 2022

ASA: Новая страница: «{{level-i}} Основные авторы описания: Вад.В.Воеводин (#Описание локальности...»