Linpack benchmark - История изменений

ASA в 13:13, 12 июля 2022

2022-07-12T13:13:46Z

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

2022-04-28T11:50:29Z

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

← Предыдущая версия		Версия от 11:50, 28 апреля 2022
Строка 149:		Строка 149:
	* По двум направлениям: 0.0000284 При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности не очень большая.		* По двум направлениям: 0.0000284 При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности не очень большая.

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

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

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

2022-04-28T11:49:33Z

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

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

	Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Voevodin~~/locality/blob/master/benchmarks/linpack/linpack_np.cpp здесь] (оригинал исходного кода взят [http://people.sc.fsu.edu/~%20jburkardt/cpp_src/linpack_bench/linpack_bench_s.cpp отсюда]). Условия запуска описаны [~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Voevodin~~/locality/blob/master/README.md здесь].		Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/benchmarks/linpack/linpack_np.cpp здесь] (оригинал исходного кода взят [http://people.sc.fsu.edu/~%20jburkardt/cpp_src/linpack_bench/linpack_bench_s.cpp отсюда]). Условия запуска описаны [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/README.md здесь].

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

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

2017-10-31T16:09:29Z

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

← Предыдущая версия		Версия от 16:09, 31 октября 2017
Строка 142:		Строка 142:

	[[file:Масштабируемость Linpack performance.png\|thumb\|center\|700px\|Рисунок 12. Тест HPL. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]		[[file:Масштабируемость Linpack performance.png\|thumb\|center\|700px\|Рисунок 12. Тест HPL. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
	[[file:Linpack масштабируемость эффективность.png\|thumb\|center\|700px\|Рисунок 13. Тест HPL. Изменение ~~производительности~~ в зависимости от числа процессоров и размера матрицы.]]		[[file:Linpack масштабируемость эффективность.png\|thumb\|center\|700px\|Рисунок 13. Тест HPL. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

	Построим оценки масштабируемости теста Linpack:		Построим оценки масштабируемости теста Linpack:

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

2017-10-31T13:11:55Z

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

← Предыдущая версия		Версия от 13:11, 31 октября 2017
Строка 95:		Строка 95:
	[[file:linpack 3.PNG\|thumb\|center\|400px\|Рисунок 7. Фрагмент 2 (профиль обращений к второму массиву)]]		[[file:linpack 3.PNG\|thumb\|center\|400px\|Рисунок 7. Фрагмент 2 (профиль обращений к второму массиву)]]

	На рис.8 представлен фрагмент 3, выделенный на рис.5, соответствующий одной итерации цикла, в котором выполняются обращения к данному массиву. Из данного рисунка хорошо видно, что итерация состоит из двух частей, соответствующих двум внутренним циклам. В обоих случаях число обращений на любой итерации внутреннего цикла примерно ~~равно~~, однако в первом внутреннем цикле на следующей итерации перебирается следующая часть элементов массива, в то время как во втором цикле перебираются одни и те же элементы.		На рис.8 представлен фрагмент 3, выделенный на рис.5, соответствующий одной итерации цикла, в котором выполняются обращения к данному массиву. Из данного рисунка хорошо видно, что итерация состоит из двух частей, соответствующих двум внутренним циклам. В обоих случаях число обращений на любой итерации внутреннего цикла примерно одинаково, однако в первом внутреннем цикле на следующей итерации перебирается следующая часть элементов массива, в то время как во втором цикле перебираются одни и те же элементы.

	[[file:linpack 4.PNG\|thumb\|center\|700px\|Рисунок 8. Фрагмент 3 (профиль обращений к третьему массиву, одна итерация)]]		[[file:linpack 4.PNG\|thumb\|center\|700px\|Рисунок 8. Фрагмент 3 (профиль обращений к третьему массиву, одна итерация)]]

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

2017-10-31T11:12:40Z

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

← Предыдущая версия		Версия от 11:12, 31 октября 2017
Строка 89:		Строка 89:
	[[file:linpack 2.PNG\|thumb\|center\|400px\|Рисунок 6. Фрагмент 1 (профиль обращений к первому массиву)]]		[[file:linpack 2.PNG\|thumb\|center\|400px\|Рисунок 6. Фрагмент 1 (профиль обращений к первому массиву)]]

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

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

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

2017-10-31T11:07:33Z

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

← Предыдущая версия		Версия от 11:07, 31 октября 2017
Строка 85:		Строка 85:
	На рис.5 представлен общий профиль обращений в память для теста Linpack. В данном тесте задействовано 3 массива. Обращения к первым двум выделены на рис.5 зеленым цветом (фрагменты 1 и 2), остальные обращения выполняются к элементам третьего массива – матрицы, содержащей коэффициенты СЛАУ. Данный тест состоит из двух этапов – факторизации матрицы и собственно решения СЛАУ. Разделение между этапами отмечено на рисунке оранжевой линией. Видно, что первый этап обладает итерационной структурой, при этом на каждой следующей итерации отбрасываются из рассмотрения несколько элементов матрицы с наименьшими индексами. Также можно заметить, что на втором этапе выполняется два прохода по элементам матрицы с возрастающим шагом, сначала последовательный, затем обратный. Однако в целом профиль устроен достаточно сложно, и для понимания свойств локальности необходимо детальное рассмотрение.		На рис.5 представлен общий профиль обращений в память для теста Linpack. В данном тесте задействовано 3 массива. Обращения к первым двум выделены на рис.5 зеленым цветом (фрагменты 1 и 2), остальные обращения выполняются к элементам третьего массива – матрицы, содержащей коэффициенты СЛАУ. Данный тест состоит из двух этапов – факторизации матрицы и собственно решения СЛАУ. Разделение между этапами отмечено на рисунке оранжевой линией. Видно, что первый этап обладает итерационной структурой, при этом на каждой следующей итерации отбрасываются из рассмотрения несколько элементов матрицы с наименьшими индексами. Также можно заметить, что на втором этапе выполняется два прохода по элементам матрицы с возрастающим шагом, сначала последовательный, затем обратный. Однако в целом профиль устроен достаточно сложно, и для понимания свойств локальности необходимо детальное рассмотрение.

	Фрагмент 1 показан отдельно на рис.6. При подобном приближении хорошо видно, что данный фрагмент состоит из двух последовательных переборов всех элементов массива, при этом размер ~~фрагмент~~ очень мал по сравнению с общим профилем. Такой последовательный перебор характеризуется высокой пространственной и достаточно низкой временной локальностью, поскольку к каждому элементу обращение выполняется всего дважды.		Фрагмент 1 показан отдельно на рис.6. При подобном приближении хорошо видно, что данный фрагмент состоит из двух последовательных переборов всех элементов массива, при этом размер фрагмента очень мал по сравнению с общим профилем. Такой последовательный перебор характеризуется высокой пространственной и достаточно низкой временной локальностью, поскольку к каждому элементу обращение выполняется всего дважды.

	[[file:linpack 2.PNG\|thumb\|center\|400px\|Рисунок 6. Фрагмент 1 (профиль обращений к первому массиву)]]		[[file:linpack 2.PNG\|thumb\|center\|400px\|Рисунок 6. Фрагмент 1 (профиль обращений к первому массиву)]]

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

2017-10-31T08:14:14Z

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

← Предыдущая версия		Версия от 08:14, 31 октября 2017
Строка 75:		Строка 75:
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===

	Строго говоря, при реализации теста испытывающий компьютерную систему испытывает и версии Линпака или другого пакета, откуда он должен вставлять вызовы треугольного разложения матрицы и решения СЛАУ с помощью полученного разложения. Поэтому находящиеся в сети версии теста не являются догмой, поскольку с их помощью можно тестировать и другие версии реализации метода Гаусса. Как уже отмечено выше, из-за того, что треугольное разложение ~~Гаусса~~ вычисляется на месте исходной матрицы, а также из-за того, что при прямом и обратном ходе решение занимает место правой части, после вычисления решения приходится заново перевычислять как матрицу системы, так и правую часть — для последующего вычисления невязки. Это решение вполне можно поменять с целью оптимизации теста.		Строго говоря, при реализации теста испытывающий компьютерную систему испытывает и версии Линпака или другого пакета, откуда он должен вставлять вызовы треугольного разложения матрицы и решения СЛАУ с помощью полученного разложения. Поэтому находящиеся в сети версии теста не являются догмой, поскольку с их помощью можно тестировать и другие версии реализации метода Гаусса. Как уже отмечено выше, из-за того, что треугольное разложение вычисляется на месте исходной матрицы, а также из-за того, что при прямом и обратном ходе решение занимает место правой части, после вычисления решения приходится заново перевычислять как матрицу системы, так и правую часть — для последующего вычисления невязки. Это решение вполне можно поменять с целью оптимизации теста.

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

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

2017-10-31T07:56:42Z

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

← Предыдущая версия		Версия от 07:56, 31 октября 2017
Строка 75:		Строка 75:
	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===

	Строго говоря, при реализации теста испытывающий компьютерную систему испытывает и версии Линпака или другого пакета, откуда он должен вставлять вызовы разложения ~~Гаусса~~ и решения СЛАУ с помощью полученного разложения. Поэтому находящиеся в сети версии теста не являются догмой, поскольку с их помощью можно тестировать и другие версии реализации метода Гаусса. Как уже отмечено выше, из-за того, что разложение Гаусса вычисляется на месте исходной матрицы, а также из-за того, что при прямом~~-обратном~~ и обратном ходе решение занимает место правой части, после вычисления решения приходится заново перевычислять как матрицу системы, так и правую часть — для последующего вычисления невязки. Это решение вполне можно поменять с целью оптимизации теста.		Строго говоря, при реализации теста испытывающий компьютерную систему испытывает и версии Линпака или другого пакета, откуда он должен вставлять вызовы треугольного разложения матрицы и решения СЛАУ с помощью полученного разложения. Поэтому находящиеся в сети версии теста не являются догмой, поскольку с их помощью можно тестировать и другие версии реализации метода Гаусса. Как уже отмечено выше, из-за того, что треугольное разложение Гаусса вычисляется на месте исходной матрицы, а также из-за того, что при прямом и обратном ходе решение занимает место правой части, после вычисления решения приходится заново перевычислять как матрицу системы, так и правую часть — для последующего вычисления невязки. Это решение вполне можно поменять с целью оптимизации теста.

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

Ikramov: /* Ресурс параллелизма алгоритма */

2017-10-30T19:48:46Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 19:48, 30 октября 2017
Строка 61:		Строка 61:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	При изучении ресурса параллелизма теста видно, что основная сложность (''квадратичная'') будет у разложения Гаусса с выбором ведущего элемента по столбцу (именно из-за наличия выбора элемента по столбцу). Остальные части алгоритма имеют не более линейной сложности. Поэтому для оптимизации вычислений возможному исследователю нужно заняться именно оптимизацией разложения Гаусса с выбором ведущего элемента по столбцу. Кроме этого, первый кусок второй части (решение первой из треугольных СЛАУ) может быть пристыкован к первой части исполнен почти полностью «на её фоне», ибо направление перевычисления данных у них совпадают. Однако второй кусок второй части, несмотря на его схожесть с первым, может быть вычислен не ранее, чем будет выполнен весь первый кусок, поскольку у них направления перевычисления данных противоположны.		При изучении ресурса параллелизма теста видно, что основная сложность (''квадратичная'') будет у разложения Гаусса с выбором ведущего элемента по столбцу (именно из-за наличия выбора элемента по столбцу). Остальные части алгоритма имеют не более линейной сложности. Поэтому для оптимизации вычислений возможному исследователю нужно заняться именно оптимизацией разложения Гаусса с выбором ведущего элемента по столбцу. Кроме этого, первый кусок второй части (решение первой из треугольных СЛАУ) может быть пристыкован к первой части и исполнен почти полностью «на её фоне», ибо направление перевычисления данных у них совпадают. Однако второй кусок второй части, несмотря на его схожесть с первым, может быть вычислен не ранее, чем будет выполнен весь первый кусок, поскольку у них направления перевычисления данных противоположны.

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