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

ASA в 06:19, 14 июля 2022

2022-07-14T06:19:47Z

← Предыдущая версия		Версия от 06:19, 14 июля 2022
Строка 178:		Строка 178:
	Алгоритм прогонки является настолько простым, что, несмотря на его "дежурное" присутствие в стандартных пакетах программ решения задач линейной алгебры, большинство использующих его исследователей-прикладников часто пишут соответствующий фрагмент программы самостоятельно. Однако надо отметить, что, как правило, метод прогонки в пакетах реализуют не в его "чистом виде", а в виде пары "разложение на две двухдиагональные матрицы" и "решение СЛАУ с предварительно факторизованной трёхдиагональной матрицей". Так обстоит дело, например, в пакете SCALAPACK и его предшественниках.		Алгоритм прогонки является настолько простым, что, несмотря на его "дежурное" присутствие в стандартных пакетах программ решения задач линейной алгебры, большинство использующих его исследователей-прикладников часто пишут соответствующий фрагмент программы самостоятельно. Однако надо отметить, что, как правило, метод прогонки в пакетах реализуют не в его "чистом виде", а в виде пары "разложение на две двухдиагональные матрицы" и "решение СЛАУ с предварительно факторизованной трёхдиагональной матрицей". Так обстоит дело, например, в пакете SCALAPACK и его предшественниках.

	=== ~~Run results~~ ===		=== Результаты прогонов ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

ASA в 06:18, 14 июля 2022

2022-07-14T06:18:07Z

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

ASA: /* Масштабируемость алгоритма и его реализации */

2022-04-28T13:40:34Z

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

← Предыдущая версия		Версия от 13:40, 28 апреля 2022
Строка 241:		Строка 241:
	Малая эффективность, по-видимому, связана с избыточной локальностью, описанной в разделе о [[#Локальность данных и вычислений\|локальности данных и вычислений]].		Малая эффективность, по-видимому, связана с избыточной локальностью, описанной в разделе о [[#Локальность данных и вычислений\|локальности данных и вычислений]].

	Исследованная [~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Teplov~~/Scalability/blob/master/tridiag/tridiagonal.h реализация алгоритма].		Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/tridiag/tridiagonal.h реализация алгоритма].

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

ASA: /* Количественная оценка локальности */

2022-04-28T13:39:58Z

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

← Предыдущая версия		Версия от 13:39, 28 апреля 2022
Строка 194:		Строка 194:
	===== Количественная оценка локальности =====		===== Количественная оценка локальности =====

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

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

Frolov: /* Программная реализация алгоритма */

2016-11-30T17:07:22Z

Программная реализация алгоритма

← Предыдущая версия		Версия от 17:07, 30 ноября 2016
Строка 141:		Строка 141:
	x(i)=(x(i)-a(1,i)x(i-1))/(a(2,i)+a(1,i)a(3,i-1)) ! beta i+1		x(i)=(x(i)-a(1,i)x(i-1))/(a(2,i)+a(1,i)a(3,i-1)) ! beta i+1
	10 continue		10 continue
	~~a(2,N)=1./(a(2,N)+a(1,N)*a(2,N-1))~~
	x(N)=(x(N)-a(1,N)x(N-1))/(a(2,N)+a(1,N)a(2,N-1)) ! y N		x(N)=(x(N)-a(1,N)x(N-1))/(a(2,N)+a(1,N)a(2,N-1)) ! y N
	do 20 i=N-1,0,-1		do 20 i=N-1,0,-1
Строка 155:		Строка 154:
	subroutine progm (a,x,N)		subroutine progm (a,x,N)
	real a(3,0:N), x(0:N)		real a(3,0:N), x(0:N)
	a(2,0)=1./a(2,0)		a(2,0) = 1. /a(2,0)
	a(3,0)=-a(3,0)*a(2,0) ! alpha 1		a(3,0)=-a(3,0)*a(2,0) ! alpha 1
	x(0)=x(0)*a(2,0) ! beta 1		x(0)=x(0)*a(2,0) ! beta 1
	do 10 i=1,N-1		do 10 i=1,N-1
	a(2,i)=1./(a(2,i)+a(1,i)*a(2,i-1))		a(2,i)=1./(a(2,i)+a(1,i)*a(3,i-1))
	a(3,i)=-a(3,i)*a(2,i) ! alpha i+1		a(3,i)=-a(3,i)*a(2,i) ! alpha i+1
	x(i)=(x(i)-a(1,i)x(i-1))a(2,i) ! beta i+1		x(i)=(x(i)-a(1,i)x(i-1))a(2,i) ! beta i+1

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

2016-11-30T17:03:52Z

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

@@ Строка 130: / Строка 130: @@
 В зависимости от способа хранения матрицы СЛАУ (в виде одного массива с <math>3</math> строками или в виде <math>3</math> разных массивов) и способа хранения вычисляемых коэффициентов (на месте уже использованных элементов матрицы либо отдельно) возможны различные реализации алгоритма.
-Приведем пример подпрограммы на языке Fortran, реализующей прогонку, где все элементы матрицы хранятся в одном массиве, причём соседние элементы матричной строки размещаются рядом, а вычисляемые коэффициенты --- на месте элементов исходной матрицы.
+Приведем пример подпрограммы на языке Fortran, реализующей прогонку, где все элементы матрицы хранятся в одном массиве, причём соседние элементы матричной строки размещаются рядом, а вычисляемые коэффициенты --- на месте элементов исходной матрицы. Вариант без предварительного обращения:
 <source lang="fortran">

Frolov: /* Вычислительное ядро алгоритма */

2016-11-23T09:15:53Z

Вычислительное ядро алгоритма

← Предыдущая версия		Версия от 09:15, 23 ноября 2016
Строка 47:		Строка 47:
	Вычислительное ядро алгоритма можно считать состоящим из двух частей - прямого и обратного хода прогонки. В прямом ходе вычислительное ядро составляют последовательности операций деления, умножения и сложения/вычитания. В обратном ходе в вычислительном ядре остаются только последовательности умножения и сложения.		Вычислительное ядро алгоритма можно считать состоящим из двух частей - прямого и обратного хода прогонки. В прямом ходе вычислительное ядро составляют последовательности операций деления, умножения и сложения/вычитания. В обратном ходе в вычислительном ядре остаются только последовательности умножения и сложения.

	[[file:ProgonkaInv.png\|thumb\|left\|420px\|Рисунок 2. Детальный граф алгоритма прогонки с однократным вычислением обратных чисел при n=4 без отображения входных и выходных данных. '''inv''' - вычисление обратного числа, '''mult''' - операция перемножения чисел. ~~Серым цветом выделены операции, повторяющиеся при замене правой части СЛАУ~~]]		[[file:ProgonkaInv.png\|thumb\|left\|420px\|Рисунок 2. Детальный граф алгоритма прогонки с однократным вычислением обратных чисел при n=4 без отображения входных и выходных данных. '''inv''' - вычисление обратного числа, '''mult''' - операция перемножения чисел.]]

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===

Frolov: /* Входные и выходные данные алгоритма */

2016-07-07T08:12:51Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 08:12, 7 июля 2016
Строка 105:		Строка 105:

	'''Входные данные''': трёхдиагональная матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>b</math> (элементы <math>b_{i}</math>).		'''Входные данные''': трёхдиагональная матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>b</math> (элементы <math>b_{i}</math>).

			'''Объём входных данных''': <math>4n-2</math>.

	'''Выходные данные''': вектор <math>x</math> (элементы <math>x_{i}</math>).		'''Выходные данные''': вектор <math>x</math> (элементы <math>x_{i}</math>).

ASA в 14:40, 1 марта 2016

2016-03-01T14:40:09Z

← Предыдущая версия		Версия от 14:40, 1 марта 2016
Строка 268:		Строка 268:


	[[En:~~Elimination method~~, pointwise version]]		[[En:Thomas algorithm, pointwise version]]

Teplov: /* Динамические характеристики и эффективность реализации алгоритма */

2016-02-07T13:14:40Z

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

← Предыдущая версия		Версия от 13:14, 7 февраля 2016
Строка 229:		Строка 229:
	На рисунках показана эффективность реализации алгоритма прогонки.		На рисунках показана эффективность реализации алгоритма прогонки.

	[[file:~~Tridiag~~ CPU ~~USER~~.png\|thumb\|center\|700px\|Рисунок 9. График загрузки CPU при выполнении алгоритма погонки]]		[[file:Tridiag1 CPU user.png\|thumb\|center\|700px\|Рисунок 9. График загрузки CPU при выполнении алгоритма погонки]]

	На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 8% в среднем. Это указывает на достаточно ~~высокую~~ нагрузку выполнения последовательного алгоритма на 8-ми ядерном процессоре.		На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 4% в среднем. Это указывает на достаточно низкую нагрузку выполнения последовательного алгоритма на 8-ми ядерном процессоре.

	[[file:~~Tridiag flops~~.png\|thumb\|center\|700px\|Рисунок 10. График операций с плавающей точкой в секунду при выполнении алгоритма прогонки]]		[[file:Tridiag1 FLops.png\|thumb\|center\|700px\|Рисунок 10. График операций с плавающей точкой в секунду при выполнении алгоритма прогонки]]

	На Рисунке 11 показан график количества операций с плавающей точкой в секунду. На графике видна общая низкая производительность вычислений, достигающая в пике 2,7 млн операций в секунду.		На Рисунке 11 показан график количества операций с плавающей точкой в секунду. На графике видна общая низкая производительность вычислений, достигающая в пике 2,2 млн операций в секунду.
	[[file:~~Tridiag~~ L1.png\|thumb\|center\|700px\|Рисунок 11. График кэш-промахов L1 в секунду при работе алгоритма прогонки]]		[[file:Tridiag1 L1.png\|thumb\|center\|700px\|Рисунок 11. График кэш-промахов L1 в секунду при работе алгоритма прогонки]]

	На графике кэш-промахов первого уровня видно, что число промахов достаточно низкое даже для одного ядра и находится на уровне ~~550~~ тыс/сек. Это указывает на достаточно хорошую локальность данных.		На графике кэш-промахов первого уровня видно, что число промахов достаточно низкое даже для одного ядра и находится на уровне 500 тыс/сек. Это указывает на достаточно хорошую локальность данных.
	[[file:~~Tridiag~~ L3.png\|thumb\|center\|700px\|Рисунок 12. График кэш-промахов L3 в секунду при работе алгоритма прогонки]]		[[file:Tridiag1 L3.png\|thumb\|center\|700px\|Рисунок 12. График кэш-промахов L3 в секунду при работе алгоритма прогонки]]

	На графике кэш-промахов третьего уровня видно, что число промахов все еще достаточно низкое для небольшого числа процессов и находится на уровне ~~110~~ тыс/сек. Отношение промахов L1/L3 около 5, что выше средних показателей по типичным задачам. Это также указывает на хорошую локальность вычислений.		На графике кэш-промахов третьего уровня видно, что число промахов все еще достаточно низкое для небольшого числа процессов и находится на уровне 80 тыс/сек. Отношение промахов L1/L3 около 6, что выше средних показателей по типичным задачам. Это также указывает на хорошую локальность вычислений.
	[[file:~~Tridiag MEM LOAD~~.png\|thumb\|center\|700px\|Рисунок 13. График количества чтений из оперативной памяти при работе алгоритма прогонки]]		[[file:Tridiag1 Mem Load.png\|thumb\|center\|700px\|Рисунок 13. График количества чтений из оперативной памяти при работе алгоритма прогонки]]

	На графике чтений из памяти на наблюдается достаточно высокая активность чтения из памяти процессами. Так как активно работает только один процесс, то и активность чтения соответсвует максимальным значениям. Активность достаточно типична для приложений такого класса.		На графике чтений из памяти на наблюдается достаточно высокая активность чтения из памяти процессами. Так как активно работает только один процесс, то и активность чтения соответсвует максимальным значениям. Активность достаточно типична для приложений такого класса.
	[[file:~~Tridiag MEM STORE~~.png\|thumb\|center\|700px\|Рисунок 14. График количества записей в оперативную память при работе алгоритма прогонки]]		[[file:Tridiag1 Mem Store.png\|thumb\|center\|700px\|Рисунок 14. График количества записей в оперативную память при работе алгоритма прогонки]]

	Активность записи в память достаточно низкая, это вполне ожидаемо для такого алгоритма, и так же указывает на достаточно высокую локальность вычислений.		Активность записи в память достаточно низкая, это вполне ожидаемо для такого алгоритма, и так же указывает на достаточно высокую локальность вычислений.
	[[file:~~Tridiag LOAD AVG~~.png\|thumb\|center\|700px\|Рисунок 15. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма прогонки]]		[[file:Tridiag1 Load Avg.png\|thumb\|center\|700px\|Рисунок 15. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма прогонки]]
	На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 1. Это свидетельствует о стабильной работе программы с работающим только одним процессом.		На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 1. Это свидетельствует о стабильной работе программы с работающим только одним процессом.
	В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала не очень эффективно, но с высокой локальностью вычислений. Интенсивность использования памяти низкая, при этом локальность вычислений обеспечивает достаточно эффективное испльзование кэш-памяти.		В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала не очень эффективно, но с высокой локальностью вычислений. Интенсивность использования памяти низкая, при этом локальность вычислений обеспечивает достаточно эффективное испльзование кэш-памяти.