Участник:ADovganich/Нечеткий алгоритм С средних - История изменений

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

2016-12-19T23:52:20Z

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

← Предыдущая версия		Версия от 23:52, 19 декабря 2016
Строка 150:		Строка 150:
	Сложность ее вычисления на первом шаге (вычисление центров кластеров) при параллельной реализации составляет <math>O(\log_{2}NC)</math>. Для каждого элемента из набора входных данных(<math> K N </math>). Здесь возможен независимый расчет(координатный параллелизм).		Сложность ее вычисления на первом шаге (вычисление центров кластеров) при параллельной реализации составляет <math>O(\log_{2}NC)</math>. Для каждого элемента из набора входных данных(<math> K N </math>). Здесь возможен независимый расчет(координатный параллелизм).

	На втором шаге(вычисление решающей функции) так же основной сложностью, исходя из начального предположения, является суммирование. Её сложность будет <math>O(\log_{2} {NCK})</math>, потому что здесь необходимо сложение всех элементов.		На втором шаге (вычисление решающей функции) так же основной сложностью, исходя из начального предположения, является суммирование. Её сложность будет <math>O(\log_{2} {NCK})</math>, потому что здесь необходимо сложение всех элементов.

	На третьем шаге имеем сложность <math>O(\log_{2} NKC^2)</math>. Что видно из последовательной реализации в п.1.5.		На третьем шаге имеем сложность <math>O(\log_{2} NKC^2)</math>. Что видно из последовательной реализации в п.1.5.

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

2016-12-19T23:51:58Z

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

← Предыдущая версия		Версия от 23:51, 19 декабря 2016
Строка 146:		Строка 146:

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	На каждом шаге алгоритма необходимо вычислять сумму элементов массивов. Будем считать, что количество процессоров у нас стремится к бесконечности. Поэтому каждую операцию умножения и деления на данном шаге можно выполнять отдельно, сложность будет составлять только суммирование, полученных результатов. Для суммирования применим каскадную схему.		На каждом шаге алгоритма необходимо вычислять сумму элементов массивов. Будем считать, что количество процессоров у нас стремится к бесконечности. Поэтому каждую операцию умножения и деления на данном шаге можно выполнять отдельно, сложность будет составлять только суммирование полученных результатов. Для суммирования применим каскадную схему.

	Сложность ее вычисления на первом шаге (вычисление центров кластеров) при параллельной реализации составляет <math>O(\log_{2}NC)</math>. Для каждого элемента из набора входных данных(<math> K N </math>). Здесь возможен независимый расчет(координатный параллелизм).		Сложность ее вычисления на первом шаге (вычисление центров кластеров) при параллельной реализации составляет <math>O(\log_{2}NC)</math>. Для каждого элемента из набора входных данных(<math> K N </math>). Здесь возможен независимый расчет(координатный параллелизм).

ADovganich в 23:51, 19 декабря 2016

2016-12-19T23:51:03Z

← Предыдущая версия		Версия от 23:51, 19 декабря 2016
Строка 3:		Строка 3:
	{{algorithm		{{algorithm
	\| name = Нечеткий алгоритм C средних		\| name = Нечеткий алгоритм C средних
	\| serial_complexity = <math>O(CCK*I)</math>., где <math>I</math> - количество итераций		\| serial_complexity = <math>O(CCKNI)</math>., где <math>I</math> - количество итераций
	\| input_data = <math>KN</math>, [количество векторов размерность]		\| input_data = <math>KN</math>, [количество векторов размерность]
	\| output_data = <math>C*K</math>, [элементы матрицы принадлежности]		\| output_data = <math>C*K</math>, [элементы матрицы принадлежности]

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

2016-12-19T23:49:34Z

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

← Предыдущая версия		Версия от 23:49, 19 декабря 2016
Строка 146:		Строка 146:

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	На каждом шаге алгоритма необходимо вычислять сумму элементов массивов. Сложность ее вычисления на первом шаге (вычисление центров кластеров) при параллельной реализации составляет <math>O(\log_{2} C)</math>. Для каждого элемента из набора входных данных(<math> K * N </math>)~~, но здесь~~ возможен независимый расчет(координатный параллелизм). На втором шаге(вычисление решающей функции) сложность будет <math>O(\log_{2} {CKN})</math>, потому что здесь необходимо сложение всех элементов. На третьем шаге имеем сложность <math>O(\log_{2} C^2)</math>. Итого суммарная сложность итерации: <math>O(\log_{2} {CKN} + \log_{2} C^3)</math>. Воспользовавшись свойствами логарифма произведения получаем: <math>O(\log_{2} {K*N} + \log_{2} C^4)</math>.		На каждом шаге алгоритма необходимо вычислять сумму элементов массивов. Будем считать, что количество процессоров у нас стремится к бесконечности. Поэтому каждую операцию умножения и деления на данном шаге можно выполнять отдельно, сложность будет составлять только суммирование, полученных результатов. Для суммирования применим каскадную схему.

			Сложность ее вычисления на первом шаге (вычисление центров кластеров) при параллельной реализации составляет <math>O(\log_{2}NC)</math>. Для каждого элемента из набора входных данных(<math> K N </math>). Здесь возможен независимый расчет(координатный параллелизм).

			На втором шаге(вычисление решающей функции) так же основной сложностью, исходя из начального предположения, является суммирование. Её сложность будет <math>O(\log_{2} {NCK})</math>, потому что здесь необходимо сложение всех элементов.

			На третьем шаге имеем сложность <math>O(\log_{2} NKC^2)</math>. Что видно из последовательной реализации в п.1.5.

			Итого суммарная сложность итерации: <math>O(\log_{2} {CKN} + \log_{2} K^2N^2C^3)</math>. Воспользовавшись свойствами логарифма произведения получаем: <math>O(\log_{2} {K^3N^3} + \log_{2} C^4)</math>.

	Скошенного параллелизма в алгоритме нет.		Скошенного параллелизма в алгоритме нет.

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

2016-12-19T23:05:03Z

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

← Предыдущая версия		Версия от 23:05, 19 декабря 2016
Строка 189:		Строка 189:
	* максимальная эффективность реализации 2,56%.		* максимальная эффективность реализации 2,56%.

	В параллельной реализации использовалась технология OpenMP. Компилятор GNU(gcc) с флагом -fopenmp. Версия компилятора: gcc version 4.4.7 20120313 (Red Hat 4.4.7-4) (GCC).		В параллельной реализации использовалась технология OpenMP, для передачи данных данных между потоками использовалась технология MPI. Компилятор GNU(gcc) с флагом -fopenmp. Версия компилятора: gcc version 4.4.7 20120313 (Red Hat 4.4.7-4) (GCC).

	На следующих рисунках приведены графики [[Глоссарий#Производительность\|производительности]] и [[Глоссарий#Эффективность реализации\|эффективности]] выбранной реализации в зависимости от изменяемых параметров запуска.		На следующих рисунках приведены графики [[Глоссарий#Производительность\|производительности]] и [[Глоссарий#Эффективность реализации\|эффективности]] выбранной реализации в зависимости от изменяемых параметров запуска.

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

2016-12-19T22:52:09Z

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

← Предыдущая версия		Версия от 22:52, 19 декабря 2016
Строка 146:		Строка 146:

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	На каждом шаге алгоритма необходимо вычислять сумму элементов массивов. Сложность ее вычисления на первом шаге (вычисление центров кластеров) при параллельной реализации составляет <math>O(\log_{2} C)</math>. Для каждого элемента из набора входных данных(<math> K </math>), но здесь возможен независимый расчет(координатный параллелизм). На втором шаге(вычисление решающей функции) сложность будет <math>O(\log_{2} {CK})</math>, потому что здесь необходимо сложение всех элементов. На третьем шаге имеем сложность <math>O(\log_{2} C^2)</math>. Итого суммарная сложность итерации: <math>O(\log_{2} {CK} + \log_{2} C^3)</math>. Воспользовавшись свойствами логарифма произведения получаем: <math>O(\log_{2} {K} + \log_{2} C^4)</math>.		На каждом шаге алгоритма необходимо вычислять сумму элементов массивов. Сложность ее вычисления на первом шаге (вычисление центров кластеров) при параллельной реализации составляет <math>O(\log_{2} C)</math>. Для каждого элемента из набора входных данных(<math> K * N </math>), но здесь возможен независимый расчет(координатный параллелизм). На втором шаге(вычисление решающей функции) сложность будет <math>O(\log_{2} {CKN})</math>, потому что здесь необходимо сложение всех элементов. На третьем шаге имеем сложность <math>O(\log_{2} C^2)</math>. Итого суммарная сложность итерации: <math>O(\log_{2} {CKN} + \log_{2} C^3)</math>. Воспользовавшись свойствами логарифма произведения получаем: <math>O(\log_{2} {K*N} + \log_{2} C^4)</math>.

	Скошенного параллелизма в алгоритме нет.		Скошенного параллелизма в алгоритме нет.

ASA в 10:34, 30 ноября 2016

2016-11-30T10:34:33Z

← Предыдущая версия		Версия от 10:34, 30 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|ASA}}

	{{algorithm		{{algorithm

Protsenko в 10:26, 30 ноября 2016

2016-11-30T10:26:35Z

← Предыдущая версия		Версия от 10:26, 30 ноября 2016
Строка 1:		Строка 1:
			{{Assignment}}

	{{algorithm		{{algorithm
	\| name = Нечеткий алгоритм C средних		\| name = Нечеткий алгоритм C средних

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

2016-11-29T19:24:04Z

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

← Предыдущая версия		Версия от 19:24, 29 ноября 2016
Строка 191:		Строка 191:
	На следующих рисунках приведены графики [[Глоссарий#Производительность\|производительности]] и [[Глоссарий#Эффективность реализации\|эффективности]] выбранной реализации в зависимости от изменяемых параметров запуска.		На следующих рисунках приведены графики [[Глоссарий#Производительность\|производительности]] и [[Глоссарий#Эффективность реализации\|эффективности]] выбранной реализации в зависимости от изменяемых параметров запуска.

	[[file: FCM произв.jpg \|thumb\|center\|800px\|Изменение производительности.]]		[[file: FCM произв.jpg \|thumb\|center\|800px\|Рисунок 2 Изменение производительности.]]

	[[file: FCM эф.jpg \|thumb\|center\|800px\|Изменение эффективности.]]		[[file: FCM эф.jpg \|thumb\|center\|800px\|Рисунок 3 Изменение эффективности.]]

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

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

2016-11-29T19:23:46Z

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

← Предыдущая версия		Версия от 19:23, 29 ноября 2016
Строка 141:		Строка 141:
	'''Третий ярус''' включает <math>C*K</math> параллельных операций, каждая из которых состоит из <math>C</math> параллельных операций, и одной, которая выполняется с использованием результата предыдущих.		'''Третий ярус''' включает <math>C*K</math> параллельных операций, каждая из которых состоит из <math>C</math> параллельных операций, и одной, которая выполняется с использованием результата предыдущих.

	[[Файл:Суперпрак.png\|1200px\|thumb\|center\|Информационный граф алгоритма. Салатовым цветом обозначены вершины графа-операции. Дугами обозначена передача информации, передаваемые данные надписаны сверху.]]		[[Файл:Суперпрак.png\|1200px\|thumb\|center\|Рисунок 1 Информационный граф алгоритма. Салатовым цветом обозначены вершины графа-операции. Дугами обозначена передача информации, передаваемые данные надписаны сверху.]]

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

← Предыдущая версия		Версия от 23:52, 19 декабря 2016
Строка 150:		Строка 150:
	Сложность ее вычисления на первом шаге (вычисление центров кластеров) при параллельной реализации составляет <math>O(\log_{2}NC)</math>. Для каждого элемента из набора входных данных(<math> K N </math>). Здесь возможен независимый расчет(координатный параллелизм).		Сложность ее вычисления на первом шаге (вычисление центров кластеров) при параллельной реализации составляет <math>O(\log_{2}NC)</math>. Для каждого элемента из набора входных данных(<math> K N </math>). Здесь возможен независимый расчет(координатный параллелизм).

	На втором шаге(вычисление решающей функции) так же основной сложностью, исходя из начального предположения, является суммирование. Её сложность будет <math>O(\log_{2} {NCK})</math>, потому что здесь необходимо сложение всех элементов.		На втором шаге (вычисление решающей функции) так же основной сложностью, исходя из начального предположения, является суммирование. Её сложность будет <math>O(\log_{2} {NCK})</math>, потому что здесь необходимо сложение всех элементов.

	На третьем шаге имеем сложность <math>O(\log_{2} NKC^2)</math>. Что видно из последовательной реализации в п.1.5.		На третьем шаге имеем сложность <math>O(\log_{2} NKC^2)</math>. Что видно из последовательной реализации в п.1.5.