Классическая монотонная прогонка, повторный вариант - История изменений

ASA в 08:05, 14 июля 2022

2022-07-14T08:05:19Z

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

2018-03-14T12:27:04Z

← Предыдущая версия		Версия от 12:27, 14 марта 2018
Строка 196:		Строка 196:
	<references />		<references />

	[[En:~~Two-sided elimination method~~, pointwise version]]		[[En:Repeated Thomas algorithm, pointwise version]]
	[[Категория:Алгоритмы с низким уровнем параллелизма]]		[[Категория:Алгоритмы с низким уровнем параллелизма]]
	[[Категория:Законченные статьи]]		[[Категория:Законченные статьи]]

Frolov в 12:08, 26 апреля 2017

2017-04-26T12:08:44Z

← Предыдущая версия		Версия от 12:08, 26 апреля 2017
Строка 1:		Строка 1:
			{{level-a}}

	{{algorithm		{{algorithm
	\| name = Повторная прогонка для трёхдиагональной матрицы,<br /> точечный вариант		\| name = Повторная прогонка для трёхдиагональной матрицы,<br /> точечный вариант

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

2016-12-16T10:49:47Z

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

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

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

	На рис. 2 представлен фрагмент 1 (выделен на рис. 1 зеленым). В данном фрагменте происходит смена двух этапов, а также входят обращения ко всем массивам. Из рис. 2 видно, что перебор 4 массивов в нижней части рисунка состоит из единичных обращений; в данном случае фрагменты представляют собой обычный последовательный перебор элементов массива, возможно с некоторым небольшим шагом по памяти. Однако самая верхняя часть фрагмента отличается от остальных, более того, можно увидеть, что характер обращений на разных этапах отличается. Рассмотрим данную часть более детально.		На рис. 5 представлен фрагмент 1 (выделен на рис. 4 зеленым). В данном фрагменте происходит смена двух этапов, а также входят обращения ко всем массивам. Из рис. 5 видно, что перебор 4 массивов в нижней части рисунка состоит из единичных обращений; в данном случае фрагменты представляют собой обычный последовательный перебор элементов массива, возможно с некоторым небольшим шагом по памяти. Однако самая верхняя часть фрагмента отличается от остальных, более того, можно увидеть, что характер обращений на разных этапах отличается. Рассмотрим данную часть более детально.

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

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

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

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

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

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

2016-12-16T10:31:54Z

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

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

2016-12-16T08:19:06Z

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

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

	[[File:Repvstrprog.png\|thumb\|center\|800px\|Рисунок 2. Отношение времени исполнения повторной встречной и монотонных прогонок. По оси асбсцисс отложено <math>m</math> (порядок СЛАУ равен <math>2^m - 1</math>), по оси ординат - отношение времени, затраченного на исполнение встречной повторной прогонки, к времени, затраченному на выполнение монотонной повторной прогонки. Цветами выделены графики для разных систем (Pentium D + Windows XP, Core i5 + Windows 8, Core i7 + Windows 7), на всех их использована одна и та же сборка кода компилятором GNU Fortran.]]		[[File:Repvstrprog.png\|thumb\|center\|800px\|Рисунок 2. Отношение времени исполнения повторной встречной и монотонных прогонок. По оси асбсцисс отложено <math>m</math> (порядок СЛАУ равен <math>2^m - 1</math>), по оси ординат - отношение времени, затраченного на исполнение встречной повторной прогонки, к времени, затраченному на выполнение монотонной повторной прогонки. Цветами выделены графики для разных систем (Pentium D + Windows XP, Core i5 + Windows 8, Core i7 + Windows 7), на всех их использована одна и та же сборка кода компилятором GNU Fortran.]]


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

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

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

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

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

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

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

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

			[[file:monosweep_repeated_3.png\|thumb\|center\|500px\|Рисунок 3. Фрагмент 1, верхняя часть]]

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

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

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

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

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

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

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

Frolov: /* Литература */

2016-12-12T07:58:29Z

Литература

← Предыдущая версия		Версия от 07:58, 12 декабря 2016
Строка 163:		Строка 163:
	<references />		<references />

			[[En:Two-sided elimination method, pointwise version]]
	[[Категория:Алгоритмы с низким уровнем параллелизма]]		[[Категория:Алгоритмы с низким уровнем параллелизма]]
	[[Категория:Законченные статьи]]		[[Категория:Законченные статьи]]

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

2016-12-12T07:55:40Z

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

← Предыдущая версия		Версия от 07:55, 12 декабря 2016
Строка 11:		Строка 11:

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
			[[file:ProgonkaRep.png\|thumb\|right\|200px\|Рисунок 1. Граф алгоритма повторной прогонки при n=7 без отображения входных и выходных данных. '''/''' - деление, '''''f''''' - операция '''''a+bc'''''.]]

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
Строка 17:		Строка 18:

	{{Шаблон:Трёхдиагональная СЛАУ}}		{{Шаблон:Трёхдиагональная СЛАУ}}


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

	[[file:~~ProgonkaInv~~.png\|thumb\|left\|~~420px~~\|Рисунок 1. ~~Детальный граф~~ алгоритма ~~предварительной~~ прогонки с ~~однократным вычислением~~ обратных чисел при n=4 без отображения входных и выходных данных. '''~~inv~~''' - ~~вычисление обратного числа~~, '''~~mult~~''' - операция ~~перемножения чисел. Самая левая ветвь не выполняется при повторной прогонке~~.]]		[[file:ProgonkaRepMul.png\|thumb\|left\|200px\|Рисунок 2. Граф алгоритма повторной прогонки с заранее выполненным предвычислением обратных чисел при n=7 без отображения входных и выходных данных. '''m''' - умножение на предвычисленное обратное число, '''''f''''' - операция '''''a+bc'''''.]]

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
Строка 77:		Строка 77:
	=== Информационный граф ===		=== Информационный граф ===

	Информационный граф повторной прогонки ~~представлен вместе с графом~~ первой прогонки на рис.1. ~~В отличие от предварительной,~~ в ~~графе повторной~~ прогонки ~~полностью вычёркивается самая левая ветвь вычислений~~. Как следует из анализа графа, он является полностью последовательным. Из рисунка видно, что не только математическая суть обработки элементов векторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названиям "прямой и обратный ход".		Информационный граф повторной прогонки в случае первой прогонки без предвычислений обратных чисел на рис.1. Информационный граф повторной прогонки в случае первой прогонки с предвычислениями обратных чисел - на рис.2. Как следует из анализа графа, он является полностью последовательным. Из рисунка видно, что не только математическая суть обработки элементов векторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названиям "прямой и обратный ход".

	=== Описание ресурса параллелизма алгоритма ===		=== Описание ресурса параллелизма алгоритма ===

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

2016-12-12T07:24:37Z

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

← Предыдущая версия		Версия от 07:24, 12 декабря 2016
Строка 137:		Строка 137:
	При этом, однако, повторная прогонка относится к таким последовательным алгоритмам, в которых локальность вычислений настолько велика, что является даже излишней<ref>Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.</ref>. Из-за того, что данные, необходимые для выполнения основных операций прогонки, вычисляются в непосредственно предшествующим им операциях, возможность использования суперскалярности вычислительных ядер процессоров практически сводится на нет, что ухудшает эффективность выполнения прогонки даже на современных однопроцессорных и одноядерных системах. Последнее показано сравнением времени исполнения монотонной повторной прогонки и встречной монотонной прогонки<ref>Фролов Н.А., Фролов А.В. Экспериментальные исследования влияния степени локальности алгоритмов на их быстродействие на примере решения трёхдиагональных СЛАУ // Труды 59й научной конференции МФТИ (21–26 ноября 2016 г., гг. Москва-Долгопрудный).</ref>, которая благодаря наличию двух ветвей вычислений даёт выигрыш по времени около 20% в сравнении с первой даже на персональных компьютерах (см. Рисунок 2).		При этом, однако, повторная прогонка относится к таким последовательным алгоритмам, в которых локальность вычислений настолько велика, что является даже излишней<ref>Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.</ref>. Из-за того, что данные, необходимые для выполнения основных операций прогонки, вычисляются в непосредственно предшествующим им операциях, возможность использования суперскалярности вычислительных ядер процессоров практически сводится на нет, что ухудшает эффективность выполнения прогонки даже на современных однопроцессорных и одноядерных системах. Последнее показано сравнением времени исполнения монотонной повторной прогонки и встречной монотонной прогонки<ref>Фролов Н.А., Фролов А.В. Экспериментальные исследования влияния степени локальности алгоритмов на их быстродействие на примере решения трёхдиагональных СЛАУ // Труды 59й научной конференции МФТИ (21–26 ноября 2016 г., гг. Москва-Долгопрудный).</ref>, которая благодаря наличию двух ветвей вычислений даёт выигрыш по времени около 20% в сравнении с первой даже на персональных компьютерах (см. Рисунок 2).

	[[File:Repvstrprog.png\|thumb\|center\|800px\|Рисунок 2. Отношение времени исполнения повторной встречной и монотонных прогонок. По оси асбсцисс отложено <math>m</math> (порядок СЛАУ равен <math>2^m - 1</math>), по оси ординат - отношение времени, затраченного на исполнение встречной повторной прогонки, к времени, затраченному на выполнение монотонной повторной прогонки. Цветами выделены графики для разных систем (Pentium D + Windows XP, Core i5 + Windows 8, Core i7 + Windows 7, ~~использован компилятор~~ GNU Fortran.]]		[[File:Repvstrprog.png\|thumb\|center\|800px\|Рисунок 2. Отношение времени исполнения повторной встречной и монотонных прогонок. По оси асбсцисс отложено <math>m</math> (порядок СЛАУ равен <math>2^m - 1</math>), по оси ординат - отношение времени, затраченного на исполнение встречной повторной прогонки, к времени, затраченному на выполнение монотонной повторной прогонки. Цветами выделены графики для разных систем (Pentium D + Windows XP, Core i5 + Windows 8, Core i7 + Windows 7), на всех их использована одна и та же сборка кода компилятором GNU Fortran.]]

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

Frolov: /* Литература */

2016-12-12T07:22:57Z

Литература

← Предыдущая версия		Версия от 07:22, 12 декабря 2016
Строка 164:		Строка 164:

	[[Категория:Алгоритмы с низким уровнем параллелизма]]		[[Категория:Алгоритмы с низким уровнем параллелизма]]
			[[Категория:Законченные статьи]]

← Предыдущая версия		Версия от 10:31, 16 декабря 2016
Строка 137:		Строка 137:
	При этом, однако, повторная прогонка относится к таким последовательным алгоритмам, в которых локальность вычислений настолько велика, что является даже излишней<ref>Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.</ref>. Из-за того, что данные, необходимые для выполнения основных операций прогонки, вычисляются в непосредственно предшествующим им операциях, возможность использования суперскалярности вычислительных ядер процессоров практически сводится на нет, что ухудшает эффективность выполнения прогонки даже на современных однопроцессорных и одноядерных системах. Последнее показано сравнением времени исполнения монотонной повторной прогонки и встречной монотонной прогонки<ref>Фролов Н.А., Фролов А.В. Экспериментальные исследования влияния степени локальности алгоритмов на их быстродействие на примере решения трёхдиагональных СЛАУ // Труды 59й научной конференции МФТИ (21–26 ноября 2016 г., гг. Москва-Долгопрудный).</ref>, которая благодаря наличию двух ветвей вычислений даёт выигрыш по времени около 20% в сравнении с первой даже на персональных компьютерах (см. Рисунок 2).		При этом, однако, повторная прогонка относится к таким последовательным алгоритмам, в которых локальность вычислений настолько велика, что является даже излишней<ref>Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.</ref>. Из-за того, что данные, необходимые для выполнения основных операций прогонки, вычисляются в непосредственно предшествующим им операциях, возможность использования суперскалярности вычислительных ядер процессоров практически сводится на нет, что ухудшает эффективность выполнения прогонки даже на современных однопроцессорных и одноядерных системах. Последнее показано сравнением времени исполнения монотонной повторной прогонки и встречной монотонной прогонки<ref>Фролов Н.А., Фролов А.В. Экспериментальные исследования влияния степени локальности алгоритмов на их быстродействие на примере решения трёхдиагональных СЛАУ // Труды 59й научной конференции МФТИ (21–26 ноября 2016 г., гг. Москва-Долгопрудный).</ref>, которая благодаря наличию двух ветвей вычислений даёт выигрыш по времени около 20% в сравнении с первой даже на персональных компьютерах (см. Рисунок 2).

	[[File:Repvstrprog.png\|thumb\|center\|800px\|Рисунок 2. Отношение времени исполнения повторной встречной и монотонных прогонок. По оси асбсцисс отложено <math>m</math> (порядок СЛАУ равен <math>2^m - 1</math>), по оси ординат - отношение времени, затраченного на исполнение встречной повторной прогонки, к времени, затраченному на выполнение монотонной повторной прогонки. Цветами выделены графики для разных систем (Pentium D + Windows XP, Core i5 + Windows 8, Core i7 + Windows 7), на всех их использована одна и та же сборка кода компилятором GNU Fortran.]]		[[File:Repvstrprog.png\|thumb\|center\|800px\|Рисунок 3. Отношение времени исполнения повторной встречной и монотонных прогонок. По оси асбсцисс отложено <math>m</math> (порядок СЛАУ равен <math>2^m - 1</math>), по оси ординат - отношение времени, затраченного на исполнение встречной повторной прогонки, к времени, затраченному на выполнение монотонной повторной прогонки. Цветами выделены графики для разных систем (Pentium D + Windows XP, Core i5 + Windows 8, Core i7 + Windows 7), на всех их использована одна и та же сборка кода компилятором GNU Fortran.]]


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

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

	На рис. 1 представлен общий профиль обращений в память для реализации повторного варианта классической монотонной прогонки. Явно видно два этапа в работе программы – на первом этапе выполняется перебор 4 массивов в прямой последовательности, а на втором этапе 2 массива перебираются в обратной последовательности. Профиль состоит из фрагментов, каждый из которых очень похож на обычный последовательный перебор, который обладает высокой пространственной и низкой временной локальностями. Однако необходимо более детальное рассмотрение профиля, чтобы понять, как именно этот перебор устроен.		На рис. 1 представлен общий профиль обращений в память для реализации повторного варианта классической монотонной прогонки. Явно видно два этапа в работе программы – на первом этапе выполняется перебор 4 массивов в прямой последовательности, а на втором этапе 2 массива перебираются в обратной последовательности. Профиль состоит из фрагментов, каждый из которых очень похож на обычный последовательный перебор, который обладает высокой пространственной и низкой временной локальностями. Однако необходимо более детальное рассмотрение профиля, чтобы понять, как именно этот перебор устроен.
Строка 150:		Строка 150:
	На рис. 2 представлен фрагмент 1 (выделен на рис. 1 зеленым). В данном фрагменте происходит смена двух этапов, а также входят обращения ко всем массивам. Из рис. 2 видно, что перебор 4 массивов в нижней части рисунка состоит из единичных обращений; в данном случае фрагменты представляют собой обычный последовательный перебор элементов массива, возможно с некоторым небольшим шагом по памяти. Однако самая верхняя часть фрагмента отличается от остальных, более того, можно увидеть, что характер обращений на разных этапах отличается. Рассмотрим данную часть более детально.		На рис. 2 представлен фрагмент 1 (выделен на рис. 1 зеленым). В данном фрагменте происходит смена двух этапов, а также входят обращения ко всем массивам. Из рис. 2 видно, что перебор 4 массивов в нижней части рисунка состоит из единичных обращений; в данном случае фрагменты представляют собой обычный последовательный перебор элементов массива, возможно с некоторым небольшим шагом по памяти. Однако самая верхняя часть фрагмента отличается от остальных, более того, можно увидеть, что характер обращений на разных этапах отличается. Рассмотрим данную часть более детально.

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

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

	[[file:monosweep_repeated_3.png\|thumb\|center\|500px\|Рисунок 3. Фрагмент 1, верхняя часть]]		[[file:monosweep_repeated_3.png\|thumb\|center\|500px\|Рисунок 6. Фрагмент 1, верхняя часть]]

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

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

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