Участник:One/Алгоритм распределения булевых функций на гиперсфере - История изменений

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

2020-12-04T07:27:55Z

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

← Предыдущая версия		Версия от 07:27, 4 декабря 2020
Строка 115:		Строка 115:
	Для наглядной масштабируемости алгоритма представлен график (Рисунок 2) зависимости времени выполнения от количества переменных в булевой функции и от количества используемых процессоров.		Для наглядной масштабируемости алгоритма представлен график (Рисунок 2) зависимости времени выполнения от количества переменных в булевой функции и от количества используемых процессоров.

	[[file:BoolFunc_Chart.jpg\|thumb\|center\|700px\|Рисунок 2. График зависимости времени он количества входных переменных и степени распараллеливания.]]		[[file:BoolFunc_Chart.jpg\|thumb\|center\|700px\|Рисунок 2. График зависимости времени от количества входных переменных и степени распараллеливания.]]

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

2020-12-04T07:27:18Z

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

← Предыдущая версия		Версия от 07:27, 4 декабря 2020
Строка 115:		Строка 115:
	Для наглядной масштабируемости алгоритма представлен график (Рисунок 2) зависимости времени выполнения от количества переменных в булевой функции и от количества используемых процессоров.		Для наглядной масштабируемости алгоритма представлен график (Рисунок 2) зависимости времени выполнения от количества переменных в булевой функции и от количества используемых процессоров.

	[[file:BoolFunc_Chart.~~png~~\|thumb\|center\|700px\|Рисунок 2. График зависимости времени он количества входных переменных и степени распараллеливания.]]		[[file:BoolFunc_Chart.jpg\|thumb\|center\|700px\|Рисунок 2. График зависимости времени он количества входных переменных и степени распараллеливания.]]

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

2020-12-03T18:17:43Z

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

← Предыдущая версия		Версия от 18:17, 3 декабря 2020
Строка 118:		Строка 118:


	Наглядно видно, что время при увеличении количества переменных увеличивается экспоненциально. Однако увеличение количества используемых процессоров немного улучшает ситуацию. Тем не менее, нельзя просто при любом количестве переменных брать максимально доступное число процессоров, ибо как видно при [math]n = 3[/math] такой выбор лишь усугубляет ситуацию - очень много времени уходит на сбор информации со всех процессоров, что в несколько раз увеличивает время работы алгоритма. Однако при увеличении [math]n[\math] увеличение количества используемых процессоров немного улучшает ситуацию со временем, но это далеко не панацея.		Наглядно видно, что время при увеличении количества переменных увеличивается экспоненциально. Однако увеличение количества используемых процессоров немного улучшает ситуацию. Тем не менее, нельзя просто при любом количестве переменных брать максимально доступное число процессоров, ибо как видно при [math]n = 3[/math] такой выбор лишь усугубляет ситуацию - очень много времени уходит на сбор информации со всех процессоров, что в несколько раз увеличивает время работы алгоритма. Однако при увеличении [math]n[/math] увеличение количества используемых процессоров немного улучшает ситуацию со временем, но это далеко не панацея.

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

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

2020-12-03T17:52:35Z

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

← Предыдущая версия		Версия от 17:52, 3 декабря 2020
Строка 118:		Строка 118:


	Наглядно видно, что время при увеличении количества переменных увеличивается экспоненциально. Однако увеличение количества используемых процессоров немного улучшает ситуацию. Тем не менее, нельзя просто при любом количестве переменных брать максимально доступное число процессоров, ибо как видно при n = 3 такой выбор лишь усугубляет ситуацию - очень много времени уходит на сбор информации со всех процессоров, что в несколько раз увеличивает время работы алгоритма. Однако при увеличении n увеличение количества используемых процессоров немного улучшает ситуацию со временем, но это далеко не панацея.		Наглядно видно, что время при увеличении количества переменных увеличивается экспоненциально. Однако увеличение количества используемых процессоров немного улучшает ситуацию. Тем не менее, нельзя просто при любом количестве переменных брать максимально доступное число процессоров, ибо как видно при [math]n = 3[/math] такой выбор лишь усугубляет ситуацию - очень много времени уходит на сбор информации со всех процессоров, что в несколько раз увеличивает время работы алгоритма. Однако при увеличении [math]n[\math] увеличение количества используемых процессоров немного улучшает ситуацию со временем, но это далеко не панацея.

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

One: /* Информационный граф */

2020-12-03T17:23:03Z

Информационный граф

← Предыдущая версия		Версия от 17:23, 3 декабря 2020
Строка 81:		Строка 81:
	[F-N S] - генерация вектора значений функции-номера секции на основе спектра Уолша.		[F-N S] - генерация вектора значений функции-номера секции на основе спектра Уолша.

	[[file:IG.png\|thumb\|center\|500px\|Рисунок 1. Подграф информационного графа алгоритма распределения булевых функций на гиперсфере.]]		[[file:BoolFunc_IG.png\|thumb\|center\|500px\|Рисунок 1. Подграф информационного графа алгоритма распределения булевых функций на гиперсфере.]]

	Действительно, очевидно, что данный подграф отображает лишь одну итерацию всего цикла, т.е. весь информационный граф этого цикла будет состоять из [math]2^{2^n}[/math] одинаковых несвязных подграфов вида как на рисунке 1.		Действительно, очевидно, что данный подграф отображает лишь одну итерацию всего цикла, т.е. весь информационный граф этого цикла будет состоять из [math]2^{2^n}[/math] одинаковых несвязных подграфов вида как на рисунке 1.

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

2020-12-03T17:22:26Z

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

← Предыдущая версия		Версия от 17:22, 3 декабря 2020
Строка 112:		Строка 112:

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

			Для наглядной масштабируемости алгоритма представлен график (Рисунок 2) зависимости времени выполнения от количества переменных в булевой функции и от количества используемых процессоров.

			[[file:BoolFunc_Chart.png\|thumb\|center\|700px\|Рисунок 2. График зависимости времени он количества входных переменных и степени распараллеливания.]]


			Наглядно видно, что время при увеличении количества переменных увеличивается экспоненциально. Однако увеличение количества используемых процессоров немного улучшает ситуацию. Тем не менее, нельзя просто при любом количестве переменных брать максимально доступное число процессоров, ибо как видно при n = 3 такой выбор лишь усугубляет ситуацию - очень много времени уходит на сбор информации со всех процессоров, что в несколько раз увеличивает время работы алгоритма. Однако при увеличении n увеличение количества используемых процессоров немного улучшает ситуацию со временем, но это далеко не панацея.

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

One: /* Информационный граф */

2020-12-03T11:42:31Z

Информационный граф

← Предыдущая версия		Версия от 11:42, 3 декабря 2020
Строка 85:		Строка 85:
	Действительно, очевидно, что данный подграф отображает лишь одну итерацию всего цикла, т.е. весь информационный граф этого цикла будет состоять из [math]2^{2^n}[/math] одинаковых несвязных подграфов вида как на рисунке 1.		Действительно, очевидно, что данный подграф отображает лишь одну итерацию всего цикла, т.е. весь информационный граф этого цикла будет состоять из [math]2^{2^n}[/math] одинаковых несвязных подграфов вида как на рисунке 1.
	Из вида информационного графа сразу понятен ресурс параллелизма данного алгоритма - блочное (или циклическое) распределение итерация цикла между процессорами.		Из вида информационного графа сразу понятен ресурс параллелизма данного алгоритма - блочное (или циклическое) распределение итерация цикла между процессорами.

			Обоснование, почему операцию нахождения спектра Уолша можно считать за работу оператора: в данной реализации алгоритма вычисление спектра Уолша производилось прямо по определению, однако в теории криптографии существует быстрое преобразование Адамара. Оно заключается в том, что существуют [https://ru.wikipedia.org/wiki/Матрица_Адамара матрицы Адамара] специального вида, обозначаемые [math]H_{2^n}[/math], которые используются для вычисления спектра Уолша по формуле: [math]WS = (-1)^f * H_{2^n}[/math], где [math](-1)^f[/math] - вектор вида [math]((-1)^{f(0)}, ..., (-1)^{f(1^n)})[/math].

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

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

2020-12-03T11:35:08Z

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

← Предыдущая версия		Версия от 11:35, 3 декабря 2020
Строка 95:		Строка 95:
	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

	'''Входные данные:''' Количество переменных, от которых зависят булевы функции. Предпочтительно задавать нечетные значения, значения [math]\ge 3[/math], но [math]\le 11[/math]. (т.к. именно для значений [math]n \le 11[/math] существуют [https://dspace.spbu.ru/bitstream/11701/4477/1/VKR_Anoxin_I_A_.pdf оценки максимальной нелинейности булевой функции.] , которые можно использовать для хотя бы частичной проверки корректности работы алгоритма.		'''Входные данные:''' Количество переменных, от которых зависят булевы функции. Предпочтительно задавать нечетные значения, значения [math]\ge 3[/math], но [math]\le 11[/math]. (т.к. именно для значений [math]n \le 11[/math] существуют [https://dspace.spbu.ru/bitstream/11701/4477/1/VKR_Anoxin_I_A_.pdf оценки максимальной нелинейности булевой функции.] , которые можно использовать для хотя бы частичной проверки корректности работы алгоритма)

	'''Выходные данные:''' Словарь (в понятии языка Python), где ключу будет соответствовать вектор значений функции-номера секции, а значению соответствует количество функций в данной секции.		'''Выходные данные:''' Словарь (в понятии языка Python), где ключу будет соответствовать вектор значений функции-номера секции, а значению соответствует количество функций в данной секции.

One: /* Информационный граф */

2020-12-03T11:25:09Z

Информационный граф

← Предыдущая версия		Версия от 11:25, 3 декабря 2020
Строка 71:		Строка 71:

	=== Информационный граф ===		=== Информационный граф ===
			Так как весь алгоритм 'сосредоточен' в главном цикле перебора всех возможных чисел, то именно для этого фрагмента реализации алгоритма построим информационный граф.

			Подграф желаемого графа указан на рисунке 1, где:

			[VV] - преобразование числа в вектор значение булевой функции, т.е. фактически перевод десятичного числа в двоичную систему счисления.

			[WS] - нахождение спектра Уолша на основе вектора значений.

			[F-N S] - генерация вектора значений функции-номера секции на основе спектра Уолша.

			[[file:IG.png\|thumb\|center\|500px\|Рисунок 1. Подграф информационного графа алгоритма распределения булевых функций на гиперсфере.]]

			Действительно, очевидно, что данный подграф отображает лишь одну итерацию всего цикла, т.е. весь информационный граф этого цикла будет состоять из [math]2^{2^n}[/math] одинаковых несвязных подграфов вида как на рисунке 1.
			Из вида информационного графа сразу понятен ресурс параллелизма данного алгоритма - блочное (или циклическое) распределение итерация цикла между процессорами.

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

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

2020-12-03T11:03:46Z

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

← Предыдущая версия		Версия от 11:03, 3 декабря 2020
Строка 81:		Строка 81:
	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

	'''Входные данные:''' Количество переменных, от которых зависят булевы функции. Предпочтительно задавать нечетные значения, значения [math]\ge 3[/math], но [math]\le 11[/math]. (т.к. именно для значений [math]n \le 11[/math] существуют оценки максимальной нелинейности, ~~которую~~ можно использовать для хотя бы частичной проверки корректности работы алгоритма.		'''Входные данные:''' Количество переменных, от которых зависят булевы функции. Предпочтительно задавать нечетные значения, значения [math]\ge 3[/math], но [math]\le 11[/math]. (т.к. именно для значений [math]n \le 11[/math] существуют [https://dspace.spbu.ru/bitstream/11701/4477/1/VKR_Anoxin_I_A_.pdf оценки максимальной нелинейности булевой функции.] , которые можно использовать для хотя бы частичной проверки корректности работы алгоритма.

	'''Выходные данные:''' Словарь (в понятии языка Python), где ключу будет соответствовать вектор значений функции-номера секции, а значению соответствует количество функций в данной секции.		'''Выходные данные:''' Словарь (в понятии языка Python), где ключу будет соответствовать вектор значений функции-номера секции, а значению соответствует количество функций в данной секции.