Участник:Бугаков Юрий/Построение матрицы Адамара произвольного размера - История изменений

Lineprinter: Lineprinter переименовал страницу Обсуждение:Участники: Бугаков Юрий, Кужамалиев Ернур/Построение матрицы Адамара произвольного размера в…

2016-10-28T13:42:40Z

Lineprinter переименовал страницу Обсуждение:Участники: Бугаков Юрий, Кужамалиев Ернур/Построение матрицы Адамара произвольного размера в…

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

Бугаков Юрий: Бугаков Юрий переименовал страницу Участника: Бугаков Юрий, Кужамалиев Ернур/Построение матрицы Адамара произвольного размера в [[Обс…

2016-10-15T19:40:04Z

Бугаков Юрий переименовал страницу Участника: Бугаков Юрий, Кужамалиев Ернур/Построение матрицы Адамара произвольного размера в [[Обс…

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

Бугаков Юрий: Бугаков Юрий переименовал страницу Построение матрицы Адамара произвольного размера в [[Участника: Бугаков Юрий, Кужамалиев Ернур/Пос…

2016-10-15T19:37:40Z

Бугаков Юрий переименовал страницу Построение матрицы Адамара произвольного размера в [[Участника: Бугаков Юрий, Кужамалиев Ернур/Пос…

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

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

2016-10-15T19:33:14Z

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

← Предыдущая версия		Версия от 19:33, 15 октября 2016
Строка 156:		Строка 156:
	Одним из трудных мест параллельной реализации является правильный выбор количества процессов. Рассматривается некоторое фиксированное число процессов <math>P\in \mathbb{N}</math>. Считается, что каждый процесс ''P'' обрабатывает не более чем <math>\left[\frac{2^{2n}}{P}\right]\geq 1</math> элементов. Тогда качественная формула может быть записана таким образом:		Одним из трудных мест параллельной реализации является правильный выбор количества процессов. Рассматривается некоторое фиксированное число процессов <math>P\in \mathbb{N}</math>. Считается, что каждый процесс ''P'' обрабатывает не более чем <math>\left[\frac{2^{2n}}{P}\right]\geq 1</math> элементов. Тогда качественная формула может быть записана таким образом:

	:<math>T(n,p)=2\,(1+\left[ \frac{n}{4} \right])\,\frac{2^{2n}}{P}</math>.		:<math>T(n,P)=2\,(1+\left[ \frac{n}{4} \right])\,\frac{2^{2n}}{P}</math>.

	Неравенство <math>\left[\frac{2^{2n}}{P}\right]\geq 1</math> можно переписать, как <math>log_2\,\sqrt{P}\leq n</math>.		Неравенство <math>\left[\frac{2^{2n}}{P}\right]\geq 1</math> можно переписать, как <math>log_2\,\sqrt{P}\leq n</math>.

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

2016-10-15T19:32:12Z

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

← Предыдущая версия		Версия от 19:32, 15 октября 2016
Строка 162:		Строка 162:
	Легко увидеть, что минимум функции ''T(n,P)'' будет при максимально возможном ''P'' : <math>log_2\,\sqrt{P}\leq n</math>. Такое ''P'' будет оптимальным числом процессов для алгоритма. В частности, для <math>P=2^p,\,p\in\mathbb{N}</math> оптимальное <math>P = 2^{2n}</math>.		Легко увидеть, что минимум функции ''T(n,P)'' будет при максимально возможном ''P'' : <math>log_2\,\sqrt{P}\leq n</math>. Такое ''P'' будет оптимальным числом процессов для алгоритма. В частности, для <math>P=2^p,\,p\in\mathbb{N}</math> оптимальное <math>P = 2^{2n}</math>.
	:<math>\frac{T(n)}{T(n,p)}=P</math>.		:<math>\frac{T(n)}{T(n,p)}=P</math>.
	то есть, отношение последовательной и параллельной сложности будет ''линейно'' зависеть от <math>P</math>.		то есть, отношение последовательной и параллельной сложности будет ''линейно'' зависеть от <math>P</math>;

	* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:		* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:

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

2016-10-15T19:30:59Z

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

← Предыдущая версия		Версия от 19:30, 15 октября 2016
Строка 162:		Строка 162:
	Легко увидеть, что минимум функции ''T(n,P)'' будет при максимально возможном ''P'' : <math>log_2\,\sqrt{P}\leq n</math>. Такое ''P'' будет оптимальным числом процессов для алгоритма. В частности, для <math>P=2^p,\,p\in\mathbb{N}</math> оптимальное <math>P = 2^{2n}</math>.		Легко увидеть, что минимум функции ''T(n,P)'' будет при максимально возможном ''P'' : <math>log_2\,\sqrt{P}\leq n</math>. Такое ''P'' будет оптимальным числом процессов для алгоритма. В частности, для <math>P=2^p,\,p\in\mathbb{N}</math> оптимальное <math>P = 2^{2n}</math>.
	:<math>\frac{T(n)}{T(n,p)}=P</math>.		:<math>\frac{T(n)}{T(n,p)}=P</math>.
	то есть, отношение последовательной и параллельной сложности будет ''линейно'' зависеть от <math>P</math>~~, а при фиксированном <math>P</math> отношение будет ''константным''~~.		то есть, отношение последовательной и параллельной сложности будет ''линейно'' зависеть от <math>P</math>.

	* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:		* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:

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

2016-10-15T19:28:29Z

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

← Предыдущая версия		Версия от 19:28, 15 октября 2016
Строка 154:		Строка 154:

	* Соотношение последовательной и параллельной сложности:		* Соотношение последовательной и параллельной сложности:
	Одним из трудных мест параллельной реализации является правильный выбор количества процессов. ~~Для удобства анализа рассматривается~~ число ~~процессоров~~ <math> P ~~= 2^p~~ </math>, ~~где~~ <math> p \in \~~mathbb~~ {N} </math>. Ясно, что такое допущение не повлияет на качество анализа, так как другое число процессоров лишь приведет к незначительным накладным расходам, сложность которых асимптотически стремится к нулю.. Тогда ~~приближенная~~ качественная формула может быть записана таким образом:		Одним из трудных мест параллельной реализации является правильный выбор количества процессов. Рассматривается некоторое фиксированное число процессов <math>P\in \mathbb{N}</math>. Считается, что каждый процесс ''P'' обрабатывает не более чем <math>\left[\frac{2^{2n}}{P}\right]\geq 1</math> элементов. Тогда качественная формула может быть записана таким образом:

	:<math>T(n,p)=2\,(1+\left[ \frac{n}{4} \right])\,2^{2n-p}~~,\,2n-p\geq 0~~</math>,		:<math>T(n,p)=2\,(1+\left[ \frac{n}{4} \right])\,\frac{2^{2n}}{P}</math>.

	Легко увидеть, что минимум будет при <math>p=2\,n\,</math> - оптимальное ~~число процессов~~.		Неравенство <math>\left[\frac{2^{2n}}{P}\right]\geq 1</math> можно переписать, как <math>log_2\,\sqrt{P}\leq n</math>.
	:<math>\frac{T(n)}{T(n,p)}~~=2^p~~=P</math>.
			Легко увидеть, что минимум функции ''T(n,P)'' будет при максимально возможном ''P'' : <math>log_2\,\sqrt{P}\leq n</math>. Такое ''P'' будет оптимальным числом процессов для алгоритма. В частности, для <math>P=2^p,\,p\in\mathbb{N}</math> оптимальное <math>P = 2^{2n}</math>.
			:<math>\frac{T(n)}{T(n,p)}=P</math>.
	то есть, отношение последовательной и параллельной сложности будет ''линейно'' зависеть от <math>P</math>, а при фиксированном <math>P</math> отношение будет ''константным''.		то есть, отношение последовательной и параллельной сложности будет ''линейно'' зависеть от <math>P</math>, а при фиксированном <math>P</math> отношение будет ''константным''.

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

2016-10-15T18:04:22Z

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

← Предыдущая версия		Версия от 18:04, 15 октября 2016
Строка 160:		Строка 160:
	Легко увидеть, что минимум будет при <math>p=2\,n\,</math> - оптимальное число процессов.		Легко увидеть, что минимум будет при <math>p=2\,n\,</math> - оптимальное число процессов.
	:<math>\frac{T(n)}{T(n,p)}=2^p=P</math>.		:<math>\frac{T(n)}{T(n,p)}=2^p=P</math>.
	то есть, отношение последовательной и параллельной сложности будет ''~~линейным~~'' от <math>P</math>.		то есть, отношение последовательной и параллельной сложности будет ''линейно'' зависеть от <math>P</math>, а при фиксированном <math>P</math> отношение будет ''константным''.

	* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:		* ''Вычислительная мощность'' алгоритма построения матрицы Адамара, как отношение числа операций к суммарному объему входных и выходных данных:

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

2016-10-15T18:02:01Z

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

← Предыдущая версия		Версия от 18:02, 15 октября 2016
Строка 159:		Строка 159:

	Легко увидеть, что минимум будет при <math>p=2\,n\,</math> - оптимальное число процессов.		Легко увидеть, что минимум будет при <math>p=2\,n\,</math> - оптимальное число процессов.
	:<math>\frac{T(n)}{T(n,p)}=2^p=P</math>,		:<math>\frac{T(n)}{T(n,p)}=2^p=P</math>.
	то есть, отношение последовательной и параллельной сложности будет ''линейным'' от <math>P</math>.		то есть, отношение последовательной и параллельной сложности будет ''линейным'' от <math>P</math>.

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

2016-10-15T18:01:38Z

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

← Предыдущая версия		Версия от 18:01, 15 октября 2016
Строка 154:		Строка 154:

	* Соотношение последовательной и параллельной сложности:		* Соотношение последовательной и параллельной сложности:
	Одним из трудных мест параллельной реализации является правильный выбор количества процессов. Для удобства анализа рассматривается число процессоров <math> P = 2^p </math>, где <math> p \in \mathbb {N} </math>. Ясно, что такое допущение не повлияет на качество анализа, так как другое число процессоров лишь приведет к незначительным накладным расходам. Тогда приближенная качественная формула может быть записана таким образом:		Одним из трудных мест параллельной реализации является правильный выбор количества процессов. Для удобства анализа рассматривается число процессоров <math> P = 2^p </math>, где <math> p \in \mathbb {N} </math>. Ясно, что такое допущение не повлияет на качество анализа, так как другое число процессоров лишь приведет к незначительным накладным расходам, сложность которых асимптотически стремится к нулю.. Тогда приближенная качественная формула может быть записана таким образом:

	:<math>T(n,p)=2\,(1+\left[ \frac{n}{4} \right])\,2^{2n-p},\,2n-p\geq 0</math>,		:<math>T(n,p)=2\,(1+\left[ \frac{n}{4} \right])\,2^{2n-p},\,2n-p\geq 0</math>,