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

ASA в 10:24, 14 июля 2022

2022-07-14T10:24:21Z

@@ Строка 165: / Строка 165: @@
        end
 </source>
 === Возможные способы и особенности параллельной реализации алгоритма ===
@@ Строка 205: / Строка 174: @@
 [[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.]]
-=== Масштабируемость алгоритма и его реализации ===
+Алгоритм повторной встречной прогонки настолько прост, что, в тех случаях, когда он по каким-либо причинам понадобился, большинство использующих его исследователей-прикладников просто пишут соответствующий фрагмент программы самостоятельно. Поэтому встречную прогонку в пакеты программ обычно не включают.
 === Выводы для классов архитектур ===
 Повторная встречная прогонка - метод для архитектуры классического, фон-неймановского типа. Для распараллеливания решения СЛАУ с трёхдиагональной матрицей следует взять какой-либо её параллельный заменитель, например, наиболее распространённую [[Метод циклической редукции|циклическую редукцию]] или уступающий ей по критическому пути графа, но имеющий более регулярную структуру графа новый [[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками|последовательно-параллельный метод]].
 == Литература ==

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

2018-03-14T12:36:50Z

← Предыдущая версия		Версия от 12:36, 14 марта 2018
Строка 227:		Строка 227:
	[[Категория:Законченные статьи]]		[[Категория:Законченные статьи]]
	[[Категория:Алгоритмы с небольшим уровнем параллелизма]]		[[Категория:Алгоритмы с небольшим уровнем параллелизма]]

			[[en:Repeated two-sided Thomas algorithm, pointwise version]]

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

2016-12-16T10:47:52Z

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

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

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

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

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

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

	Далее рассмотрим фрагмент 2 (рис. 3). Здесь профиль устроен очень просто – параллельно выполняются возрастающий и убывающий переборы данных с небольшим шагом по памяти. Подобное поведение можно увидеть также во всех переборах, расположенных ниже фрагмента 2 на рис. 1.		Далее рассмотрим фрагмент 2 (рис. 4). Здесь профиль устроен очень просто – параллельно выполняются возрастающий и убывающий переборы данных с небольшим шагом по памяти. Подобное поведение можно увидеть также во всех переборах, расположенных ниже фрагмента 2 на рис. 2.

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

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

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

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

2016-12-16T10:32:48Z

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

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

2016-12-16T07:47:39Z

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

@@ Строка 173: / Строка 173: @@
 ===== Структура обращений в память и качественная оценка локальности =====
 ===== Количественная оценка локальности =====
 === Возможные способы и особенности параллельной реализации алгоритма ===

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

2016-12-12T08:08:29Z

Литература

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

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

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

2016-12-12T07:43:50Z

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

← Предыдущая версия		Версия от 07:43, 12 декабря 2016
Строка 179:		Строка 179:
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

	Встречная повторная прогонка задумана изначально для случая, когда нужно найти только какую-то близкую к "середине" компоненту вектора решения, а остальные не нужны (решение т.н. "частичной задачи"). При появлении параллельных компьютерных устройств оказалось, что у встречной прогонки есть небольшой ресурс параллелизма и она убыстряет счёт, если её верхнюю и нижнюю ветви раскидать на 2 процессора. Однако для получения массового параллелизма встречная прогонка непригодна из-за низкой ширины своей [[Глоссарий#Ярусно-параллельная форма графа алгоритма\|ЯПФ]] (равной 2).		Встречная повторная прогонка задумана изначально для случая, когда нужно найти только какую-то близкую к "середине" компоненту вектора решения, а остальные не нужны (решение т.н. "частичной задачи"). При появлении параллельных компьютерных устройств оказалось, что у встречной прогонки есть небольшой ресурс параллелизма и она убыстряет счёт, если её верхнюю и нижнюю ветви "раскидать" на 2 процессора. Однако для получения массового параллелизма встречная прогонка непригодна из-за низкой ширины своей [[Глоссарий#Ярусно-параллельная форма графа алгоритма\|ЯПФ]] (равной 2).

			С появлением суперскалярных процессоров оказалось, что для получения выигрыша (около 20%) перед монотонной повторной прогонкой встречную даже необязательно "раскидывать" на 2 процессора или даже на 2 ядра. Последнее показано сравнением времени исполнения монотонной повторной прогонки и встречной монотонной прогонки<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.]]

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

Frolov: /* Общее описание алгоритма */

2016-12-12T06:58:08Z

Общее описание алгоритма

← Предыдущая версия		Версия от 06:58, 12 декабря 2016
Строка 18:		Строка 18:
	{{Шаблон:Трёхдиагональная СЛАУ}}		{{Шаблон:Трёхдиагональная СЛАУ}}

	'''Встречная повторная прогонка''', как и [[Классическая монотонная прогонка, повторный вариант\|~~Повтоная~~ монотонная]], заключается в исключении из уравнений неизвестных, однако, в отличие от монотонной, в ней исключение ведут одновременно с обоих "краёв" СЛАУ (верхнего и нижнего). В принципе, её можно считать простейшим вариантом [[Метод редукции\|метода редукции]] (при m=1 и встречных направлениях монотонных прогонок).		'''Встречная повторная прогонка''', как и [[Классическая монотонная прогонка, повторный вариант\|повторная монотонная]], заключается в исключении из уравнений неизвестных, однако, в отличие от монотонной, в ней исключение ведут одновременно с обоих "краёв" СЛАУ (верхнего и нижнего). В принципе, её можно считать простейшим вариантом [[Метод редукции\|метода редукции]] (при m=1 и встречных направлениях монотонных прогонок).

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

Frolov: Frolov переименовал страницу Встречная прогонка, повторный вариант в Повторная встречная прогонка, точечный вариант без оставления пе…

2016-12-10T13:57:01Z

Frolov переименовал страницу Встречная прогонка, повторный вариант в Повторная встречная прогонка, точечный вариант без оставления пе…

← Предыдущая версия	Версия от 13:57, 10 декабря 2016
(нет различий)

Frolov: /* Особенности реализации последовательного алгоритма */

2016-11-23T11:15:29Z

Особенности реализации последовательного алгоритма

← Предыдущая версия		Версия от 11:15, 23 ноября 2016
Строка 141:		Строка 141:

	<source lang="fortran">		<source lang="fortran">
	subroutine ~~vprogm~~ (a,x,N) ! N=2m-1		subroutine vprogmr (a,x,N) ! N=2m-1
	real a(3,N), x(N)		real a(3,N), x(N)

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

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

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

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

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

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

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

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

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