ASA в 09:00, 14 июля 2022

2022-07-14T09:00:17Z

← Предыдущая версия		Версия от 09:00, 14 июля 2022
Строка 79:		Строка 79:
	= Результаты прогонов =		= Результаты прогонов =

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

	<references />		<references />

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

2022-07-08T07:06:03Z

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

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

{{level-i}}

Основные авторы описания: [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2]]), [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|3]])

= Ссылки =

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

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

Как видно по графу алгоритма, локальность данных по пространству хорошая - все перевычисляемые аргументы, что нужны операциям, вычисляются "рядом".
При этом, однако, схема Горнера относится к таким последовательным алгоритмам, в которых локальность вычислений настолько велика, что будет излишней. Из-за того, что данные, нужные для вычислений основных операций алгоритма, вычисляются в его процессе операциями, непосредственно предшествующими им, возможности вычислительных ядер процессоров по использованию своей суперскалярности практически сводятся на нет, что резко ухудшает эффективность исполнения схемы даже на современных однопроцессорных и одноядерных системах.

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

[[file:Gorner_1.png|thumb|center|500px|Рисунок 1. Реализация схемы Горнера. Общий профиль обращений в память]]

На рис.2 представлен профиль обращений в память последовательной вещественной реализации схемы Горнера. Исходя из рисунка 1, данный профиль устроен очень просто и состоит из двух последовательных переборов элементов, выполняемых параллельно для двух массивов.

Однако даже в таком простом примере для полного понимания структуры обращений в память нужен более детальный анализ на уровне отдельных обращений. На рис.2 рассмотрим подробнее фрагмент 1, выделенный на рис.1 зеленым. Можно увидеть, что верхний последовательный перебор несколько отличается от нижнего – в первом случае к каждому элементу выполняется по два обращения подряд. Отметим, однако, что данное уточнение строения профиля слабо сказывается на локальности всего профиля.

В целом, общий профиль обладает высокой пространственной локальностью, поскольку перебор элементов массивов осуществляется последовательно, однако очень низкой временно́й локальностью – в одном из массивов к каждому элементу выполняется обращение только дважды, во втором массиве повторные обращения вообще отсутствуют.

[[file:Gorner_2.jpg|thumb|center|500px|Рисунок 2. Фрагмент 1 (первые 100 обращений общего профиля)]]

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

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

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

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

Причина такого поведения связана с особенностями строения подсистемы памяти. В реализации схемы Горнера, как было отмечено выше, к элементам одного из массивов выполняется по два обращения подряд. Однако если посмотреть исходный код реализации, можно увидеть, что на самом деле второе обращение выполняется на следующей итерации – это обращение к предыдущему элементу:
<source lang="c">
for (int i = 1; i < size; i++) {
c[i] = a[i] + c[i - 1] * x;
}
</source>
В результате из-за зависимости итераций аппаратный префетчер гораздо хуже справляется с подтягиванием требуемых кэш-строк, что приводит к заметному замедлению выполнения программы по сравнению с другими реализациями, основанными на последовательном переборе (например, тесты STREAM).

Подобный пример лишний раз показывает, насколько сложно утроена подсистема памяти – совсем небольшое изменение строения тела цикла приводит к достаточно неожиданному серьезному замедлению программы.

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

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

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

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

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

= Масштабируемость алгоритма и его реализации =
== Масштабируемость алгоритма ==
== Масштабируемость реализации алгоритма ==

Понятие масштабируемости неприменимо, поскольку описываемый алгоритм не предполагает параллельной реализации.
Проведём исследование масштабируемости вширь реализации алгоритма согласно [[Scalability methodology|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].
Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:

* число процессоров 1;
* размер области [10240 : 1024000] с шагом 10240.

В результате проведённых экспериментов был получен следующий диапазон [[Глоссарий#Эффективность реализации|эффективности реализации]] алгоритма:

* минимальная эффективность реализации 0.0324%;
* максимальная эффективность реализации 0.0331%.

На следующих рисунках приведены графики [[Глоссарий#Производительность|производительности]] и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.

[[file:Gorner perf.png|thumb|center|700px|Рисунок 5. Реализация алгоритма. Изменение производительности в зависимости от размера вектора.]]
[[file:Gorner eff.png|thumb|center|700px|Рисунок 6. Реализация алгоритма. Изменение эффективности в зависимости от размера вектора.]]

Мизерная эффективность, по-видимому, связана с избыточной локальностью, описанной в разделе о [[#Локальность данных и вычислений|локальности данных и вычислений]].

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

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

<references />

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

[[En:Horners, locality]]

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

ASA в 09:00, 14 июля 2022

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