Полный метод циклической редукции - История изменений

ASA: /* Свойства и структура алгоритма */

2022-07-14T11:10:58Z

Свойства и структура алгоритма

← Предыдущая версия		Версия от 11:10, 14 июля 2022
Строка 18:		Строка 18:
	{{Шаблон:Трёхдиагональная СЛАУ2}}		{{Шаблон:Трёхдиагональная СЛАУ2}}

	'''Циклическая редукция''', как и все варианты прогонки, заключается <ref name="IK3d">Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г., 208 с.</~~ref~~><ref name="FAVT-2016">Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (г. Архангельск, 28 марта – 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.</ref> в исключении из уравнений неизвестных, однако, в отличие от них, в ней исключение ведут одновременно по всей СЛАУ. В принципе, её можно считать вариантом [[Метод редукции\|метода редукции]], выполняемого максимально возможное для данной СЛАУ число раз.		'''Циклическая редукция''', как и все варианты прогонки, заключается <ref name="IK3d" /><ref name="FAVT-2016">Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (г. Архангельск, 28 марта – 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.</ref> в исключении из уравнений неизвестных, однако, в отличие от них, в ней исключение ведут одновременно по всей СЛАУ. В принципе, её можно считать вариантом [[Метод редукции\|метода редукции]], выполняемого максимально возможное для данной СЛАУ число раз.

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===

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

2022-07-14T11:00:41Z

Внесённые изменения

ASA в 12:38, 14 марта 2018

2018-03-14T12:38:34Z

← Предыдущая версия		Версия от 12:38, 14 марта 2018
Строка 407:		Строка 407:
	{{algorithm}}		{{algorithm}}
	[[Категория:Алгоритмы с избыточными вычислениями]]		[[Категория:Алгоритмы с избыточными вычислениями]]

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

			[[en:Complete cyclic reduction]]

VadimVV: /* Локальность реализации алгоритма */

2016-12-16T10:46:58Z

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

← Предыдущая версия		Версия от 10:46, 16 декабря 2016
Строка 338:		Строка 338:
	[[file:cyclic_reduction_3.png\|thumb\|center\|500px\|Рисунок 9. Профиль обращений, фрагмент 2]]		[[file:cyclic_reduction_3.png\|thumb\|center\|500px\|Рисунок 9. Профиль обращений, фрагмент 2]]

	Рассмотрим еще более детально небольшие части данных фрагментов, чтобы дальше проанализировать структуру представленных переборов. На рис. 10 представлены небольшие локальные области, выделенные зеленым на рис. 2 и 3. Можно увидеть, что локальная структура обращений в целом отличается. В частности, в области, выделенной на рис. 9, шаг по памяти больше, а также выполняется меньше повторных обращений, что говорит о более низкой пространственной локальности.		Рассмотрим еще более детально небольшие части данных фрагментов, чтобы дальше проанализировать структуру представленных переборов. На рис. 10 представлены небольшие локальные области, выделенные зеленым на рис. 8 и 9. Можно увидеть, что локальная структура обращений в целом отличается. В частности, в области, выделенной на рис. 9, шаг по памяти больше, а также выполняется меньше повторных обращений, что говорит о более низкой пространственной локальности.

	[[file:cyclic_reduction_4.png\|thumb\|center\|700px\|Рисунок 10. Локальная структура фрагментов 2 и 3]]		[[file:cyclic_reduction_4.png\|thumb\|center\|700px\|Рисунок 10. Локальная структура фрагментов 2 и 3]]

VadimVV: /* Локальность реализации алгоритма */

2016-12-16T10:46:28Z

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

VadimVV: /* Локальность реализации алгоритма */

2016-12-16T10:33:27Z

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

VadimVV: /* Локальность данных и вычислений */

2016-12-16T08:14:34Z

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

← Предыдущая версия		Версия от 08:14, 16 декабря 2016
Строка 319:		Строка 319:

	[[File:I3-cyc.png\|thumb\|center\|1000px\|Рисунок 6. Отношение времени исполнения циклической редукции и монотонных прогонок на ПК. По оси асбсцисс отложено <math>m</math> (порядок СЛАУ равен <math>2^m - 1</math>), по оси ординат - отношение времени, затраченного на исполнение циклической редукции, к времени, затраченному на выполнение монотонной повторной прогонки. Система Core i3 + Windows 8, сборка кода компилятором GNU Fortran. На других системах получена качественно примерно такая же картина, с различием по выходу за границы кэша. Между синей и красной линиями - примерная область взаимной компенсации неарифметических факторов. При малых размерах сказывается неиспользование прогонками суперскалярности процессора.]]		[[File:I3-cyc.png\|thumb\|center\|1000px\|Рисунок 6. Отношение времени исполнения циклической редукции и монотонных прогонок на ПК. По оси асбсцисс отложено <math>m</math> (порядок СЛАУ равен <math>2^m - 1</math>), по оси ординат - отношение времени, затраченного на исполнение циклической редукции, к времени, затраченному на выполнение монотонной повторной прогонки. Система Core i3 + Windows 8, сборка кода компилятором GNU Fortran. На других системах получена качественно примерно такая же картина, с различием по выходу за границы кэша. Между синей и красной линиями - примерная область взаимной компенсации неарифметических факторов. При малых размерах сказывается неиспользование прогонками суперскалярности процессора.]]



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

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

			[[file:cyclic_reduction_1.png\|thumb\|center\|700px\|Рисунок 1. Полный метод циклической редукции. Общий профиль обращений в память]]

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

			На первом этапе явно видны отдельные итерации (первые 3 итерации разделены желтыми линиями), каждая из которых состоит из 4 параллельно выполняемых переборов данных. Отметим, что на каждой итерации в рамках каждого перебора задействованы данные из одного и того же диапазона. Число обращений в память в каждой итерации различается, и это позволяет предположить, что характер переборов также может отличаться.

			Рассмотрим фрагменты двух итераций более детально. На рис. 2 и 3 соответственно представлены фрагменты 1 и 2, обозначенные на рис. 1 зеленым. Данные фрагменты содержат по 1000 обращений. Можно увидеть, что в целом все переборы в двух фрагментах выполняются с регулярным и достаточно небольшим шагом по памяти, однако интенсивность обращений в каждом случае разная. Причем при смене итерации меняется и интенсивность обращений к одному и тому диапазону данных.

			[[file:cyclic_reduction_2.png\|thumb\|center\|500px\|Рисунок 2. Профиль обращений, фрагмент 1]]

			[[file:cyclic_reduction_3.png\|thumb\|center\|500px\|Рисунок 3. Профиль обращений, фрагмент 2]]

			Рассмотрим еще более детально небольшие части данных фрагментов, чтобы дальше проанализировать структуру представленных переборов. На рис. 4 представлены небольшие локальные области, выделенные зеленым на рис. 2 и 3. Можно увидеть, что локальная структура обращений в целом отличается. В частности, в области, выделенной на рис. 3, шаг по памяти больше, а также выполняется меньше повторных обращений, что говорит о более низкой пространственной локальности.

			[[file:cyclic_reduction_4.png\|thumb\|center\|700px\|Рисунок 4. Локальная структура фрагментов 2 и 3]]

			В целом можно сказать, что структура итераций похожа, однако локальность несколько отличается в силу указанных выше причин. Если же говорить в среднем, такое строение итераций характеризуется от средней до высокой (в зависимости от локальной структуры) пространственной локальностью и низкой временной локальностью, поскольку данные перебираются подряд (обычно с небольшим шагом по памяти), но при этом повторно почти не используются. Отметим, что размер итераций достаточно велик, так что повторное обращение к данным на следующей итерации не приводит к улучшению локальности.

			Отдельно рассмотрим самый конец первого этапа (фрагмент 3 на рис. 1), который показан на рис. 5. Здесь локальность обращений в память самая низкая, поскольку шаг по памяти в переборах становится наибольшим. В центре рисунка можно заметить область особенно низкой локальности (наиболее разрозненные обращения). Хотя данный фрагмент небольшого размера, он может серьезно снижать общую производительность взаимодействия с памятью.

			[[file:cyclic_reduction_5.png\|thumb\|center\|500px\|Рисунок 5. Профиль обращений, фрагмент 3]]

			Второй этап также имеет регулярную структуру. Рассмотрим на рис. 6 небольшую область более детально (фрагмент 4 на рис. 1). Из данного рисунка видно, что здесь также выполняются последовательные переборы, локальная структура которых может отличаться. Как и в рассмотренном на первом этапе случае, это приводит к различиям по пространственной и временной локальности. Стоит отметить, что угол наклона переборов на втором этапе в целом больше, чем на первом этапе (см. рис 1), что говорит о большем шаге по памяти, и, как следствие, более низкой пространственной локальности, однако это различие может нивелироваться различиями в локальной структуре.

			[[file:cyclic_reduction_6.png\|thumb\|center\|500px\|Рисунок 6. Профиль обращений, фрагмент 4]]

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

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

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

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


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

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

Frolov: /* Возможные способы и особенности параллельной реализации алгоритма */

2016-12-13T14:56:05Z

Возможные способы и особенности параллельной реализации алгоритма

← Предыдущая версия		Версия от 14:56, 13 декабря 2016
Строка 321:		Строка 321:

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

			Исходя из таких свойств алгоритма циклической редукции, как плохая локальность и наличие избыточности, логично было бы использовать его не в "чистом виде", а, проведя несколько этапов редукции, решать оставшуюся СЛАУ более простым методом вроде прогонки.

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

Frolov: /* Существующие реализации алгоритма */

2016-12-13T14:51:59Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 14:51, 13 декабря 2016
Строка 352:		Строка 352:

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

			Обычно циклическую редукцию как в блочном, так и в точечном варианте реализуют матфизики, решающие задачи с задачами, содержащими, например, дискретизацию оператора Лапласа. Её, несмотря на популярность, редко включают в пакеты программ. В основном это связано с тем, что простота схемы циклической редукции остаётся только для определённых размерностей задач, а универсальные решатели на её основе никто не делает. Для других размерностей могут быть придуманы разные, в том числе и более быстрые варианты циклической редукции<ref>А.В.Фролов "О коэффициенте при логарифме в критическом пути графа циклической редукции" // Суперкомпьютерные дни в России: Труды международной конференции (26-27 сентября 2016 г., г. Москва). – М.: Изд-во МГУ, 2016. с. 307-313.</ref>, но у них очень сложная схема, и каждый раз нужно выполнять анализ на устойчивость.

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

Frolov: /* Локальность данных и вычислений */

2016-12-12T10:25:58Z

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

← Предыдущая версия		Версия от 10:25, 12 декабря 2016
Строка 316:		Строка 316:
	=== Локальность данных и вычислений ===		=== Локальность данных и вычислений ===

	По графу видно, что, хотя и налицо "местная" локальность по вычислениям, но от яруса к ярусу расстояние между запрашиваемыми данными растёт от первых и последних ярусов алгоритма к его середине, являющимся не только узким местом алгоритма, но и имеющим наибольшую длину передачи данных между устройствами. Поэтому, хотя в циклической редукции нет той избыточной локальности, которая притормаживает работу прогонки, это преимущество, как показали замеры<ref>Фролов Н.А., Фролов А.В. Экспериментальные исследования влияния степени локальности алгоритмов на их быстродействие на примере решения трёхдиагональных СЛАУ // Труды 59й научной конференции МФТИ (21–26 ноября 2016 г., гг. Москва-Долгопрудный).</ref> (см. Рисунок 3), не способно компенсировать недостатки общей локальности графа циклической редукции.		По графу видно, что, хотя и налицо "местная" локальность по вычислениям, но от яруса к ярусу расстояние между запрашиваемыми данными растёт от первых и последних ярусов алгоритма к его середине, являющимся не только узким местом алгоритма, но и имеющим наибольшую длину передачи данных между устройствами. Поэтому, хотя в циклической редукции нет той избыточной локальности, которая притормаживает работу прогонки, это преимущество, как показали замеры<ref>Фролов Н.А., Фролов А.В. Экспериментальные исследования влияния степени локальности алгоритмов на их быстродействие на примере решения трёхдиагональных СЛАУ // Труды 59й научной конференции МФТИ (21–26 ноября 2016 г., гг. Москва-Долгопрудный).</ref> (см. Рисунок 6), не способно компенсировать недостатки общей локальности графа циклической редукции.

	[[File:I3-cyc.png\|thumb\|center\|~~800px~~\|Рисунок 3. Отношение времени исполнения циклической редукции и монотонных прогонок на ПК. По оси асбсцисс отложено <math>m</math> (порядок СЛАУ равен <math>2^m - 1</math>), по оси ординат - отношение времени, затраченного на исполнение циклической редукции, к времени, затраченному на выполнение монотонной повторной прогонки. Система Core i3 + Windows 8, сборка кода компилятором GNU Fortran. На других системах получена качественно примерно такая же картина, с различием по выходу за границы кэша. Между синей и красной линиями - примерная область взаимной компенсации неарифметических факторов. При малых размерах сказывается неиспользование прогонками суперскалярности процессора.]]		[[File:I3-cyc.png\|thumb\|center\|1000px\|Рисунок 6. Отношение времени исполнения циклической редукции и монотонных прогонок на ПК. По оси асбсцисс отложено <math>m</math> (порядок СЛАУ равен <math>2^m - 1</math>), по оси ординат - отношение времени, затраченного на исполнение циклической редукции, к времени, затраченному на выполнение монотонной повторной прогонки. Система Core i3 + Windows 8, сборка кода компилятором GNU Fortran. На других системах получена качественно примерно такая же картина, с различием по выходу за границы кэша. Между синей и красной линиями - примерная область взаимной компенсации неарифметических факторов. При малых размерах сказывается неиспользование прогонками суперскалярности процессора.]]

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

← Предыдущая версия		Версия от 10:46, 16 декабря 2016
Строка 328:		Строка 328:
	[[file:cyclic_reduction_1.png\|thumb\|center\|700px\|Рисунок 7. Полный метод циклической редукции. Общий профиль обращений в память]]		[[file:cyclic_reduction_1.png\|thumb\|center\|700px\|Рисунок 7. Полный метод циклической редукции. Общий профиль обращений в память]]

	На рис. 1 представлен профиль обращений в память для реализации полного метода циклической редукции. Данный профиль достаточно интересно. Как нам известно из описания самого алгоритма, он состоит из двух частей – прямого и обратного хода. На общем профиле синяя вертикальная черта отделяет эти два этапа. Рассмотрим их в отдельности.		На рис. 7 представлен профиль обращений в память для реализации полного метода циклической редукции. Данный профиль достаточно интересно. Как нам известно из описания самого алгоритма, он состоит из двух частей – прямого и обратного хода. На общем профиле синяя вертикальная черта отделяет эти два этапа. Рассмотрим их в отдельности.

	На первом этапе явно видны отдельные итерации (первые 3 итерации разделены желтыми линиями), каждая из которых состоит из 4 параллельно выполняемых переборов данных. Отметим, что на каждой итерации в рамках каждого перебора задействованы данные из одного и того же диапазона. Число обращений в память в каждой итерации различается, и это позволяет предположить, что характер переборов также может отличаться.		На первом этапе явно видны отдельные итерации (первые 3 итерации разделены желтыми линиями), каждая из которых состоит из 4 параллельно выполняемых переборов данных. Отметим, что на каждой итерации в рамках каждого перебора задействованы данные из одного и того же диапазона. Число обращений в память в каждой итерации различается, и это позволяет предположить, что характер переборов также может отличаться.

	Рассмотрим фрагменты двух итераций более детально. На рис. 2 и 3 соответственно представлены фрагменты 1 и 2, обозначенные на рис. 1 зеленым. Данные фрагменты содержат по 1000 обращений. Можно увидеть, что в целом все переборы в двух фрагментах выполняются с регулярным и достаточно небольшим шагом по памяти, однако интенсивность обращений в каждом случае разная. Причем при смене итерации меняется и интенсивность обращений к одному и тому диапазону данных.		Рассмотрим фрагменты двух итераций более детально. На рис. 8 и 9 соответственно представлены фрагменты 1 и 2, обозначенные на рис. 7 зеленым. Данные фрагменты содержат по 1000 обращений. Можно увидеть, что в целом все переборы в двух фрагментах выполняются с регулярным и достаточно небольшим шагом по памяти, однако интенсивность обращений в каждом случае разная. Причем при смене итерации меняется и интенсивность обращений к одному и тому диапазону данных.

	[[file:cyclic_reduction_2.png\|thumb\|center\|500px\|Рисунок 8. Профиль обращений, фрагмент 1]]		[[file:cyclic_reduction_2.png\|thumb\|center\|500px\|Рисунок 8. Профиль обращений, фрагмент 1]]
Строка 338:		Строка 338:
	[[file:cyclic_reduction_3.png\|thumb\|center\|500px\|Рисунок 9. Профиль обращений, фрагмент 2]]		[[file:cyclic_reduction_3.png\|thumb\|center\|500px\|Рисунок 9. Профиль обращений, фрагмент 2]]

	Рассмотрим еще более детально небольшие части данных фрагментов, чтобы дальше проанализировать структуру представленных переборов. На рис. 4 представлены небольшие локальные области, выделенные зеленым на рис. 2 и 3. Можно увидеть, что локальная структура обращений в целом отличается. В частности, в области, выделенной на рис. 3, шаг по памяти больше, а также выполняется меньше повторных обращений, что говорит о более низкой пространственной локальности.		Рассмотрим еще более детально небольшие части данных фрагментов, чтобы дальше проанализировать структуру представленных переборов. На рис. 10 представлены небольшие локальные области, выделенные зеленым на рис. 2 и 3. Можно увидеть, что локальная структура обращений в целом отличается. В частности, в области, выделенной на рис. 9, шаг по памяти больше, а также выполняется меньше повторных обращений, что говорит о более низкой пространственной локальности.

	[[file:cyclic_reduction_4.png\|thumb\|center\|700px\|Рисунок 10. Локальная структура фрагментов 2 и 3]]		[[file:cyclic_reduction_4.png\|thumb\|center\|700px\|Рисунок 10. Локальная структура фрагментов 2 и 3]]
Строка 344:		Строка 344:
	В целом можно сказать, что структура итераций похожа, однако локальность несколько отличается в силу указанных выше причин. Если же говорить в среднем, такое строение итераций характеризуется от средней до высокой (в зависимости от локальной структуры) пространственной локальностью и низкой временной локальностью, поскольку данные перебираются подряд (обычно с небольшим шагом по памяти), но при этом повторно почти не используются. Отметим, что размер итераций достаточно велик, так что повторное обращение к данным на следующей итерации не приводит к улучшению локальности.		В целом можно сказать, что структура итераций похожа, однако локальность несколько отличается в силу указанных выше причин. Если же говорить в среднем, такое строение итераций характеризуется от средней до высокой (в зависимости от локальной структуры) пространственной локальностью и низкой временной локальностью, поскольку данные перебираются подряд (обычно с небольшим шагом по памяти), но при этом повторно почти не используются. Отметим, что размер итераций достаточно велик, так что повторное обращение к данным на следующей итерации не приводит к улучшению локальности.

	Отдельно рассмотрим самый конец первого этапа (фрагмент 3 на рис. 1), который показан на рис. 5. Здесь локальность обращений в память самая низкая, поскольку шаг по памяти в переборах становится наибольшим. В центре рисунка можно заметить область особенно низкой локальности (наиболее разрозненные обращения). Хотя данный фрагмент небольшого размера, он может серьезно снижать общую производительность взаимодействия с памятью.		Отдельно рассмотрим самый конец первого этапа (фрагмент 3 на рис. 7), который показан на рис. 11. Здесь локальность обращений в память самая низкая, поскольку шаг по памяти в переборах становится наибольшим. В центре рисунка можно заметить область особенно низкой локальности (наиболее разрозненные обращения). Хотя данный фрагмент небольшого размера, он может серьезно снижать общую производительность взаимодействия с памятью.

	[[file:cyclic_reduction_5.png\|thumb\|center\|500px\|Рисунок 11. Профиль обращений, фрагмент 3]]		[[file:cyclic_reduction_5.png\|thumb\|center\|500px\|Рисунок 11. Профиль обращений, фрагмент 3]]

	Второй этап также имеет регулярную структуру. Рассмотрим на рис. 6 небольшую область более детально (фрагмент 4 на рис. 1). Из данного рисунка видно, что здесь также выполняются последовательные переборы, локальная структура которых может отличаться. Как и в рассмотренном на первом этапе случае, это приводит к различиям по пространственной и временной локальности. Стоит отметить, что угол наклона переборов на втором этапе в целом больше, чем на первом этапе (см. рис 1), что говорит о большем шаге по памяти, и, как следствие, более низкой пространственной локальности, однако это различие может нивелироваться различиями в локальной структуре.		Второй этап также имеет регулярную структуру. Рассмотрим на рис. 12 небольшую область более детально (фрагмент 4 на рис. 7). Из данного рисунка видно, что здесь также выполняются последовательные переборы, локальная структура которых может отличаться. Как и в рассмотренном на первом этапе случае, это приводит к различиям по пространственной и временной локальности. Стоит отметить, что угол наклона переборов на втором этапе в целом больше, чем на первом этапе (см. рис 7), что говорит о большем шаге по памяти, и, как следствие, более низкой пространственной локальности, однако это различие может нивелироваться различиями в локальной структуре.

	[[file:cyclic_reduction_6.png\|thumb\|center\|500px\|Рисунок 12. Профиль обращений, фрагмент 4]]		[[file:cyclic_reduction_6.png\|thumb\|center\|500px\|Рисунок 12. Профиль обращений, фрагмент 4]]
Строка 358:		Строка 358:
	Оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.		Оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

	На рисунке 7 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность работы с памятью в данном случае низка и лишь чуть выше значения daps для такой неэффективной с точки зрения работы с памятью программы как тест RandomAccess (rand). В целом это соотносится с выводами, которые были сделаны нами ранее		На рисунке 13 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность работы с памятью в данном случае низка и лишь чуть выше значения daps для такой неэффективной с точки зрения работы с памятью программы как тест RandomAccess (rand). В целом это соотносится с выводами, которые были сделаны нами ранее

← Предыдущая версия		Версия от 10:33, 16 декабря 2016
Строка 326:		Строка 326:
	===== Структура обращений в память и качественная оценка локальности =====		===== Структура обращений в память и качественная оценка локальности =====

	[[file:cyclic_reduction_1.png\|thumb\|center\|700px\|Рисунок 1. Полный метод циклической редукции. Общий профиль обращений в память]]		[[file:cyclic_reduction_1.png\|thumb\|center\|700px\|Рисунок 7. Полный метод циклической редукции. Общий профиль обращений в память]]

	На рис. 1 представлен профиль обращений в память для реализации полного метода циклической редукции. Данный профиль достаточно интересно. Как нам известно из описания самого алгоритма, он состоит из двух частей – прямого и обратного хода. На общем профиле синяя вертикальная черта отделяет эти два этапа. Рассмотрим их в отдельности.		На рис. 1 представлен профиль обращений в память для реализации полного метода циклической редукции. Данный профиль достаточно интересно. Как нам известно из описания самого алгоритма, он состоит из двух частей – прямого и обратного хода. На общем профиле синяя вертикальная черта отделяет эти два этапа. Рассмотрим их в отдельности.
Строка 334:		Строка 334:
	Рассмотрим фрагменты двух итераций более детально. На рис. 2 и 3 соответственно представлены фрагменты 1 и 2, обозначенные на рис. 1 зеленым. Данные фрагменты содержат по 1000 обращений. Можно увидеть, что в целом все переборы в двух фрагментах выполняются с регулярным и достаточно небольшим шагом по памяти, однако интенсивность обращений в каждом случае разная. Причем при смене итерации меняется и интенсивность обращений к одному и тому диапазону данных.		Рассмотрим фрагменты двух итераций более детально. На рис. 2 и 3 соответственно представлены фрагменты 1 и 2, обозначенные на рис. 1 зеленым. Данные фрагменты содержат по 1000 обращений. Можно увидеть, что в целом все переборы в двух фрагментах выполняются с регулярным и достаточно небольшим шагом по памяти, однако интенсивность обращений в каждом случае разная. Причем при смене итерации меняется и интенсивность обращений к одному и тому диапазону данных.

	[[file:cyclic_reduction_2.png\|thumb\|center\|500px\|Рисунок 2. Профиль обращений, фрагмент 1]]		[[file:cyclic_reduction_2.png\|thumb\|center\|500px\|Рисунок 8. Профиль обращений, фрагмент 1]]

	[[file:cyclic_reduction_3.png\|thumb\|center\|500px\|Рисунок 3. Профиль обращений, фрагмент 2]]		[[file:cyclic_reduction_3.png\|thumb\|center\|500px\|Рисунок 9. Профиль обращений, фрагмент 2]]

	Рассмотрим еще более детально небольшие части данных фрагментов, чтобы дальше проанализировать структуру представленных переборов. На рис. 4 представлены небольшие локальные области, выделенные зеленым на рис. 2 и 3. Можно увидеть, что локальная структура обращений в целом отличается. В частности, в области, выделенной на рис. 3, шаг по памяти больше, а также выполняется меньше повторных обращений, что говорит о более низкой пространственной локальности.		Рассмотрим еще более детально небольшие части данных фрагментов, чтобы дальше проанализировать структуру представленных переборов. На рис. 4 представлены небольшие локальные области, выделенные зеленым на рис. 2 и 3. Можно увидеть, что локальная структура обращений в целом отличается. В частности, в области, выделенной на рис. 3, шаг по памяти больше, а также выполняется меньше повторных обращений, что говорит о более низкой пространственной локальности.

	[[file:cyclic_reduction_4.png\|thumb\|center\|700px\|Рисунок 4. Локальная структура фрагментов 2 и 3]]		[[file:cyclic_reduction_4.png\|thumb\|center\|700px\|Рисунок 10. Локальная структура фрагментов 2 и 3]]

	В целом можно сказать, что структура итераций похожа, однако локальность несколько отличается в силу указанных выше причин. Если же говорить в среднем, такое строение итераций характеризуется от средней до высокой (в зависимости от локальной структуры) пространственной локальностью и низкой временной локальностью, поскольку данные перебираются подряд (обычно с небольшим шагом по памяти), но при этом повторно почти не используются. Отметим, что размер итераций достаточно велик, так что повторное обращение к данным на следующей итерации не приводит к улучшению локальности.		В целом можно сказать, что структура итераций похожа, однако локальность несколько отличается в силу указанных выше причин. Если же говорить в среднем, такое строение итераций характеризуется от средней до высокой (в зависимости от локальной структуры) пространственной локальностью и низкой временной локальностью, поскольку данные перебираются подряд (обычно с небольшим шагом по памяти), но при этом повторно почти не используются. Отметим, что размер итераций достаточно велик, так что повторное обращение к данным на следующей итерации не приводит к улучшению локальности.
Строка 346:		Строка 346:
	Отдельно рассмотрим самый конец первого этапа (фрагмент 3 на рис. 1), который показан на рис. 5. Здесь локальность обращений в память самая низкая, поскольку шаг по памяти в переборах становится наибольшим. В центре рисунка можно заметить область особенно низкой локальности (наиболее разрозненные обращения). Хотя данный фрагмент небольшого размера, он может серьезно снижать общую производительность взаимодействия с памятью.		Отдельно рассмотрим самый конец первого этапа (фрагмент 3 на рис. 1), который показан на рис. 5. Здесь локальность обращений в память самая низкая, поскольку шаг по памяти в переборах становится наибольшим. В центре рисунка можно заметить область особенно низкой локальности (наиболее разрозненные обращения). Хотя данный фрагмент небольшого размера, он может серьезно снижать общую производительность взаимодействия с памятью.

	[[file:cyclic_reduction_5.png\|thumb\|center\|500px\|Рисунок 5. Профиль обращений, фрагмент 3]]		[[file:cyclic_reduction_5.png\|thumb\|center\|500px\|Рисунок 11. Профиль обращений, фрагмент 3]]

	Второй этап также имеет регулярную структуру. Рассмотрим на рис. 6 небольшую область более детально (фрагмент 4 на рис. 1). Из данного рисунка видно, что здесь также выполняются последовательные переборы, локальная структура которых может отличаться. Как и в рассмотренном на первом этапе случае, это приводит к различиям по пространственной и временной локальности. Стоит отметить, что угол наклона переборов на втором этапе в целом больше, чем на первом этапе (см. рис 1), что говорит о большем шаге по памяти, и, как следствие, более низкой пространственной локальности, однако это различие может нивелироваться различиями в локальной структуре.		Второй этап также имеет регулярную структуру. Рассмотрим на рис. 6 небольшую область более детально (фрагмент 4 на рис. 1). Из данного рисунка видно, что здесь также выполняются последовательные переборы, локальная структура которых может отличаться. Как и в рассмотренном на первом этапе случае, это приводит к различиям по пространственной и временной локальности. Стоит отметить, что угол наклона переборов на втором этапе в целом больше, чем на первом этапе (см. рис 1), что говорит о большем шаге по памяти, и, как следствие, более низкой пространственной локальности, однако это различие может нивелироваться различиями в локальной структуре.

	[[file:cyclic_reduction_6.png\|thumb\|center\|500px\|Рисунок 6. Профиль обращений, фрагмент 4]]		[[file:cyclic_reduction_6.png\|thumb\|center\|500px\|Рисунок 12. Профиль обращений, фрагмент 4]]

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


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

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===