Участник:RS42/Quickhull - История изменений

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

2017-11-30T23:25:04Z

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

← Предыдущая версия		Версия от 23:25, 30 ноября 2017
Строка 125:		Строка 125:

	Далее для наглядности представлены графики времени выполнения алгоритма как в логарифмическом масштабе времени, так и в линейном. Хотя графики с линейным масштабом по времени только для того, чтобы быстро взглянуть и не задумываясь убедиться в том, что действительно есть какое-то ускорение.		Далее для наглядности представлены графики времени выполнения алгоритма как в логарифмическом масштабе времени, так и в линейном. Хотя графики с линейным масштабом по времени только для того, чтобы быстро взглянуть и не задумываясь убедиться в том, что действительно есть какое-то ускорение.


	Из описаний в пунктах 1.3 и 1.8 можно сделать предположения о работе алгоритма:		Из описаний в пунктах 1.3 и 1.8 можно сделать предположения о работе алгоритма:

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

2017-11-30T23:20:13Z

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

← Предыдущая версия		Версия от 23:20, 30 ноября 2017
Строка 140:		Строка 140:
	На Рис. 1 и Рис. 3 можно отметить аномалии при 4096 точках во входных данных, что объясняется превышением времени на рассылки данных с помощью MPI_Bcast() по отношению как к операции построения новых граней, так и операции распределения точек.		На Рис. 1 и Рис. 3 можно отметить аномалии при 4096 точках во входных данных, что объясняется превышением времени на рассылки данных с помощью MPI_Bcast() по отношению как к операции построения новых граней, так и операции распределения точек.

	Из сделанных предположений следует, что сильную масштабируемость для данной реализации мы можем наблюдать в том случае, если доля вычислений распределения точек составляет основную часть вычислений. На графиках видно, как при <math>2^{24}, 2^{23}, 2^{22}</math> входных точках время работы обратно пропорционально числу процессов до определенного момента (64 узла для размерности 2, 4 узла для ~~размерностей~~ 3 и 4), когда время работы упирается во время последовательной части программы (см. закон Амдала), и дальнейшим ростом числа вычислительных узлов никак не помочь. И чем меньше входных точек, тем слабее проявляется сильная масштабируемость.		Из сделанных предположений следует, что сильную масштабируемость для данной реализации мы можем наблюдать в том случае, если доля вычислений распределения точек составляет основную часть вычислений. На графиках видно, как при <math>2^{24}, 2^{23}, 2^{22}</math> входных точках время работы обратно пропорционально числу процессов до определенного момента (64 узла для размерности 2 для <math>2^{24}</math> точек, 4 узла для размерности 3 для <math>2^{24}</math> и для размерности 4 с <math>2^{22}</math> точек), когда время работы упирается во время последовательной части программы (см. закон Амдала), и дальнейшим ростом числа вычислительных узлов никак не помочь. И чем меньше входных точек, тем слабее проявляется сильная масштабируемость.
	С увеличением размерности задачи ситуация только ухудшается в силу возрастающей сложности операции построения новых граней.		С увеличением размерности задачи ситуация только ухудшается в силу возрастающей сложности операции построения новых граней.

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

2017-11-30T23:16:37Z

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

← Предыдущая версия		Версия от 23:16, 30 ноября 2017
Строка 140:		Строка 140:
	На Рис. 1 и Рис. 3 можно отметить аномалии при 4096 точках во входных данных, что объясняется превышением времени на рассылки данных с помощью MPI_Bcast() по отношению как к операции построения новых граней, так и операции распределения точек.		На Рис. 1 и Рис. 3 можно отметить аномалии при 4096 точках во входных данных, что объясняется превышением времени на рассылки данных с помощью MPI_Bcast() по отношению как к операции построения новых граней, так и операции распределения точек.

	Из сделанных предположений следует, что сильную масштабируемость для данной реализации мы можем наблюдать в том случае, если доля вычислений распределения точек составляет основную часть вычислений. На графиках видно, как при <math>2^{24}, 2^{23}, 2^{22}</math> входных точках время работы обратно пропорционально числу процессов до определенного момента (64 узла для размерности 2, ~~8 —~~ для 3~~, 4 — для~~ 4), когда время работы упирается во время последовательной части программы (см. закон Амдала), и дальнейшим ростом числа вычислительных узлов никак не помочь. И чем меньше входных точек, тем слабее проявляется сильная масштабируемость.		Из сделанных предположений следует, что сильную масштабируемость для данной реализации мы можем наблюдать в том случае, если доля вычислений распределения точек составляет основную часть вычислений. На графиках видно, как при <math>2^{24}, 2^{23}, 2^{22}</math> входных точках время работы обратно пропорционально числу процессов до определенного момента (64 узла для размерности 2, 4 узла для размерностей 3 и 4), когда время работы упирается во время последовательной части программы (см. закон Амдала), и дальнейшим ростом числа вычислительных узлов никак не помочь. И чем меньше входных точек, тем слабее проявляется сильная масштабируемость.
	С увеличением размерности задачи ситуация только ухудшается в силу возрастающей сложности операции построения новых граней.		С увеличением размерности задачи ситуация только ухудшается в силу возрастающей сложности операции построения новых граней.

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

2017-11-30T23:13:31Z

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

← Предыдущая версия		Версия от 23:13, 30 ноября 2017
Строка 140:		Строка 140:
	На Рис. 1 и Рис. 3 можно отметить аномалии при 4096 точках во входных данных, что объясняется превышением времени на рассылки данных с помощью MPI_Bcast() по отношению как к операции построения новых граней, так и операции распределения точек.		На Рис. 1 и Рис. 3 можно отметить аномалии при 4096 точках во входных данных, что объясняется превышением времени на рассылки данных с помощью MPI_Bcast() по отношению как к операции построения новых граней, так и операции распределения точек.

	Из сделанных предположений следует, что сильную масштабируемость для данной реализации мы можем наблюдать в том случае, если доля вычислений распределения точек составляет основную часть вычислений. На графиках видно, как при <math>2^{24}, 2^{23}, 2^{22}</math> входных точках время работы обратно пропорционально числу процессов до определенного момента, когда время работы упирается во время последовательной части программы (см. закон Амдала), и дальнейшим ростом числа вычислительных узлов никак не помочь. И чем меньше входных точек, тем слабее проявляется сильная масштабируемость.		Из сделанных предположений следует, что сильную масштабируемость для данной реализации мы можем наблюдать в том случае, если доля вычислений распределения точек составляет основную часть вычислений. На графиках видно, как при <math>2^{24}, 2^{23}, 2^{22}</math> входных точках время работы обратно пропорционально числу процессов до определенного момента (64 узла для размерности 2, 8 — для 3, 4 — для 4), когда время работы упирается во время последовательной части программы (см. закон Амдала), и дальнейшим ростом числа вычислительных узлов никак не помочь. И чем меньше входных точек, тем слабее проявляется сильная масштабируемость.
	С увеличением размерности задачи ситуация только ухудшается в силу возрастающей сложности операции построения новых граней.		С увеличением размерности задачи ситуация только ухудшается в силу возрастающей сложности операции построения новых граней.

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

2017-11-30T23:07:44Z

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

← Предыдущая версия		Версия от 23:07, 30 ноября 2017
Строка 116:		Строка 116:
	== Масштабируемость алгоритма и его реализации ==		== Масштабируемость алгоритма и его реализации ==
	Характеристики вычислительной среды:		Характеристики вычислительной среды:
	суперкомпьютер Ломоносов, intel mpi 5.0.1, intel icc 15.0.0, ключи: -std=c++11, -O3.		суперкомпьютер Ломоносов, версия MPI: intel mpi 5.0.1, компилятор: intel icc 15.0.0, ключи: -std=c++11, -O3.

	Тестирование проводилось на множестве исходных точек, равномерно распределенных в единичном <math>d</math>-мерном шаре. Для генерации входных данных использовался пакет Geometric Object Generators из библиотеки CGAL 4.8.2. Все тесты проводились для чисел процессов <math>2^k, k = 0,..,9</math> и количества точек во входных данных <math>2^k, k = 12,..,24, d = 2, 3 </math> и		Тестирование проводилось на множестве исходных точек, равномерно распределенных в единичном <math>d</math>-мерном шаре. Для генерации входных данных использовался пакет Geometric Object Generators из библиотеки CGAL 4.8.2. Все тесты проводились для чисел процессов <math>2^k, k = 0,..,9</math> и количества точек во входных данных <math>2^k, k = 12,..,24, d = 2, 3 </math> и

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

2017-11-30T22:52:12Z

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

← Предыдущая версия		Версия от 22:52, 30 ноября 2017
Строка 124:		Строка 124:
	Операции обмена совершались только для передачи всем процессам вершины для построения новых граней и в самом начале работы алгоритма, когда один процесс производит рассылку выбранного им стартового симплекса.		Операции обмена совершались только для передачи всем процессам вершины для построения новых граней и в самом начале работы алгоритма, когда один процесс производит рассылку выбранного им стартового симплекса.

	Далее для наглядности представлены графики времени выполнения алгоритма как в логарифмическом масштабе времени, так и в линейном.		Далее для наглядности представлены графики времени выполнения алгоритма как в логарифмическом масштабе времени, так и в линейном. Хотя графики с линейным масштабом по времени только для того, чтобы быстро взглянуть и не задумываясь убедиться в том, что действительно есть какое-то ускорение.

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

2017-11-30T22:47:37Z

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

← Предыдущая версия		Версия от 22:47, 30 ноября 2017
Строка 127:		Строка 127:


	Из описаний в ~~пункте~~ 1.3 можно сделать предположения о работе алгоритма:		Из описаний в пунктах 1.3 и 1.8 можно сделать предположения о работе алгоритма:

	1. С ростом числа исходных точек растет время как операции распределения точек, так и операции построения новых граней.		1. С ростом числа исходных точек растет время как операции распределения точек, так и операции построения новых граней.

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

2017-11-30T22:46:10Z

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

← Предыдущая версия		Версия от 22:46, 30 ноября 2017
Строка 140:		Строка 140:
	На Рис. 1 и Рис. 3 можно отметить аномалии при 4096 точках во входных данных, что объясняется превышением времени на рассылки данных с помощью MPI_Bcast() по отношению как к операции построения новых граней, так и операции распределения точек.		На Рис. 1 и Рис. 3 можно отметить аномалии при 4096 точках во входных данных, что объясняется превышением времени на рассылки данных с помощью MPI_Bcast() по отношению как к операции построения новых граней, так и операции распределения точек.

	Из сделанных предположений следует, что сильную масштабируемость для данной реализации мы можем наблюдать в том случае, если доля вычислений распределения точек составляет основную часть вычислений. На графиках видно, как при <math>2^{24}</math> входных точках время работы обратно пропорционально числу процессов до определенного момента, когда время работы упирается во время последовательной части программы (см. закон Амдала), и дальнейшим ростом числа вычислительных узлов никак не помочь. И чем меньше входных точек, тем слабее проявляется сильная масштабируемость.		Из сделанных предположений следует, что сильную масштабируемость для данной реализации мы можем наблюдать в том случае, если доля вычислений распределения точек составляет основную часть вычислений. На графиках видно, как при <math>2^{24}, 2^{23}, 2^{22}</math> входных точках время работы обратно пропорционально числу процессов до определенного момента, когда время работы упирается во время последовательной части программы (см. закон Амдала), и дальнейшим ростом числа вычислительных узлов никак не помочь. И чем меньше входных точек, тем слабее проявляется сильная масштабируемость.
	С увеличением размерности задачи ситуация только ухудшается в силу возрастающей сложности операции построения новых граней.		С увеличением размерности задачи ситуация только ухудшается в силу возрастающей сложности операции построения новых граней.

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

2017-11-30T22:44:22Z

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

← Предыдущая версия		Версия от 22:44, 30 ноября 2017
Строка 131:		Строка 131:
	1. С ростом числа исходных точек растет время как операции распределения точек, так и операции построения новых граней.		1. С ростом числа исходных точек растет время как операции распределения точек, так и операции построения новых граней.
	В силу того, что тестирование проводилось на точках, распределенных в шаре, доля времени операции распределения точек от общего времени будет только		В силу того, что тестирование проводилось на точках, распределенных в шаре, доля времени операции распределения точек от общего времени будет только
	увеличиваться, и в итоге сложность всего алгоритма растет линейно на данных тестах. Если проводить тестирование на точках, лежащих на сфере, то с увеличением		увеличиваться, и в итоге сложность всего алгоритма растет линейно на данных тестах. Это заметно на графиках, если зафиксировать число процессов. Если проводить тестирование на точках, лежащих на сфере, то с увеличением
	числа точек доля времени, ушедшего на построение новых граней, будет практически полностью составлять время работы всей программы.		числа точек доля времени, ушедшего на построение новых граней, будет практически полностью составлять время работы всей программы.

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

2017-11-30T22:41:44Z

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

← Предыдущая версия		Версия от 22:41, 30 ноября 2017
Строка 140:		Строка 140:
	На Рис. 1 и Рис. 3 можно отметить аномалии при 4096 точках во входных данных, что объясняется превышением времени на рассылки данных с помощью MPI_Bcast() по отношению как к операции построения новых граней, так и операции распределения точек.		На Рис. 1 и Рис. 3 можно отметить аномалии при 4096 точках во входных данных, что объясняется превышением времени на рассылки данных с помощью MPI_Bcast() по отношению как к операции построения новых граней, так и операции распределения точек.

	Из сделанных предположений следует, что сильную масштабируемость для данной реализации мы можем наблюдать в том случае, если доля вычислений распределения точек составляет основную часть вычислений. На графиках видно, как при <math>2^24</math> входных точках время работы обратно пропорционально числу процессов до определенного момента, когда время работы упирается во время последовательной части программы (см. закон Амдала), и дальнейшим ростом числа вычислительных узлов никак не помочь. И чем меньше входных точек, тем слабее проявляется сильная масштабируемость.		Из сделанных предположений следует, что сильную масштабируемость для данной реализации мы можем наблюдать в том случае, если доля вычислений распределения точек составляет основную часть вычислений. На графиках видно, как при <math>2^{24}</math> входных точках время работы обратно пропорционально числу процессов до определенного момента, когда время работы упирается во время последовательной части программы (см. закон Амдала), и дальнейшим ростом числа вычислительных узлов никак не помочь. И чем меньше входных точек, тем слабее проявляется сильная масштабируемость.
	С увеличением размерности задачи ситуация только ухудшается в силу возрастающей сложности операции построения новых граней.		С увеличением размерности задачи ситуация только ухудшается в силу возрастающей сложности операции построения новых граней.