Участник:Obirvalger/Метод рекурсивной координатной бисекции - История изменений

Dan в 08:39, 29 ноября 2016

2016-11-29T08:39:29Z

← Предыдущая версия		Версия от 08:39, 29 ноября 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|Dan}}

	{{algorithm		{{algorithm
	\| name = Рекурсивная координатная бисекция		\| name = Рекурсивная координатная бисекция

KolmakovEA в 22:07, 28 ноября 2016

2016-11-28T22:07:17Z

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

	{{algorithm		{{algorithm
	\| name = Рекурсивная координатная бисекция		\| name = Рекурсивная координатная бисекция

KolmakovEA в 22:06, 28 ноября 2016

2016-11-28T22:06:39Z

← Предыдущая версия		Версия от 22:06, 28 ноября 2016
Строка 8:		Строка 8:
	}}		}}

	Авторы: [[Участник:Obirvalger\|Гордеев Михаил]] (разделы 1.4, 1.6, 1.8, 1.10), [[Участник:KolmakovEA\|Колмаков Евгений]] (разделы 1.1, 1.2, 1.3, 1.5, 1.7, 1.9, 2.7).		Авторы: [[Участник:Obirvalger\|Гордеев Михаил]] (разделы 1.4, 1.6, 1.8, 1.10, 2.1, 2.4), [[Участник:KolmakovEA\|Колмаков Евгений]] (разделы 1.1, 1.2, 1.3, 1.5, 1.7, 1.9, 2.1, 2.4, 2.7).

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

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

2016-11-28T22:05:57Z

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

← Предыдущая версия		Версия от 22:05, 28 ноября 2016
Строка 216:		Строка 216:
	using namespace std;		using namespace std;

	vector<vector<double> > points_matrix;		#define N 5
			#define M 5
			#define STEP 0.01

			#define N_DIMS 2
			#define N_DOMAINS 6

			vector<vector<double> > points_matrix(N_DIMS, vector<double>(N * M));
	vector<vector<int> > graph_partition;		vector<vector<int> > graph_partition;

	double span(vector<double> &x, vector<int> &idx)		double span(vector<double> x, vector<int> idx)
	{		{
	double max_value = x[idx[0]];		double max_value = x[idx[0]];
Строка 232:		Строка 239:
	}		}

	vector<int> bisect(vector<int> &idx)		vector<int> bisect(vector<int> idx)
	{		{
	double max_span = 0;		double max_span = 0;
Строка 247:		Строка 254:

	// sorting vertices along this coordinate		// sorting vertices along this coordinate
	~~vector<int> sorted_idx = idx;~~		sort(idx.begin(), idx.end(), [&](const int& a, const int& b) {
			return points_matrix[max_ind][a] < points_matrix[max_ind][b];
	sort(~~sorted_idx~~.begin(), ~~sorted_idx~~.end(),
	[&](const int& a, const int& b) {
	return points_matrix[max_ind]~~[idx~~[a]] < points_matrix[max_ind]~~[idx~~[b]];
	});		});

	return ~~sorted_idx~~;		return idx;
	}		}

	void recursive_bisection(vector<int> &idx, int k)		void recursive_bisection(vector<int> idx, int k)
	{		{
	// adding current domain to partition		// adding current domain to partition
Строка 280:		Строка 284:
	int main()		int main()
	{		{
	// example: ~~2x4~~-mesh		// example: uniform MxN-mesh
	~~points_matrix~~ = {{0.0~~, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0},~~ {0~~.0,~~ 1~~.0, 2.0, 3.0, 0.0, 1.0, 2.0, 3.0~~}};		for(size_t i = 0; i < N; ++i)
	vector<int> idx ~~= {0, 1, 2, 3, 4, 5, 6, 7}~~;		for(size_t j = 0; j < M; ++j) {
	~~int k = 4~~;		points_matrix[0][M * i + j] = i * STEP;
			points_matrix[1][M * i + j] = j * STEP;
			}

			vector<int> idx(M * N);
			iota(idx.begin(), idx.end(), 0);

	recursive_bisection(idx, k);		recursive_bisection(idx, K);

			// partitioning results
	for(size_t i = 0; i < graph_partition.size(); ++i) {		for(size_t i = 0; i < graph_partition.size(); ++i) {
	for(size_t j = 0; j < graph_partition[i].size(); ++j)		for(size_t j = 0; j < graph_partition[i].size(); ++j)

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

2016-11-28T13:52:43Z

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

← Предыдущая версия		Версия от 13:52, 28 ноября 2016
Строка 342:		Строка 342:
	</center>		</center>

			[http://pastebin.com/hCqz7vBU Параллельная реализация алгоритма на языке C++]

	В статье <ref>http://glaros.dtc.umn.edu/gkhome/node/112</ref> приводятся результаты работы алгоритма декомпозиции графов из пакета ParMETIS. В таблице ниже приведено время работы алгоритма в зависимости от числа вершин в графе и используемого числа процессоров. Рассмотравились следующие графы:		В статье <ref>http://glaros.dtc.umn.edu/gkhome/node/112</ref> приводятся результаты работы алгоритма декомпозиции графов из пакета ParMETIS. В таблице ниже приведено время работы алгоритма в зависимости от числа вершин в графе и используемого числа процессоров. Рассмотравились следующие графы:

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

2016-11-28T13:46:18Z

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

@@ Строка 300: / Строка 300: @@
 == Масштабируемость алгоритма и его реализации ==
 В статье <ref>http://glaros.dtc.umn.edu/gkhome/node/112</ref> приводятся результаты работы алгоритма декомпозиции графов из пакета ParMETIS. В таблице ниже приведено время работы алгоритма в зависимости от числа вершин в графе и используемого числа процессоров. Рассмотравились следующие графы:
 граф mrng2 с 1 миллионом вершин, mrng3 с 4 миллионами и граф mrgn4 с 7.5 миллионами вершин.

Dan в 11:14, 17 ноября 2016

2016-11-17T11:14:31Z

← Предыдущая версия		Версия от 11:14, 17 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment\|Dan}}~~

	{{algorithm		{{algorithm
	\| name = Рекурсивная координатная бисекция		\| name = Рекурсивная координатная бисекция

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

2016-11-15T19:21:16Z

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

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

	vector<int> bisect(vector<int> idx)		vector<int> bisect(vector<int> &idx)
	{		{
	double max_span = 0;		double max_span = 0;
Строка 259:		Строка 259:
	}		}

	void recursive_bisection(vector<int> idx, int k)		void recursive_bisection(vector<int> &idx, int k)
	{		{
	// adding current domain to partition		// adding current domain to partition
Строка 284:		Строка 284:
	// example: 2x4-mesh		// example: 2x4-mesh
	points_matrix = {{0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0}, {0.0, 1.0, 2.0, 3.0, 0.0, 1.0, 2.0, 3.0}};		points_matrix = {{0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0}, {0.0, 1.0, 2.0, 3.0, 0.0, 1.0, 2.0, 3.0}};
			vector<int> idx = {0, 1, 2, 3, 4, 5, 6, 7};
	~~recursive_bisection(~~{0, 1, 2, 3, 4, 5, 6, 7}, 4);		int k = 4;

			recursive_bisection(idx, k);

	for(size_t i = 0; i < graph_partition.size(); ++i) {		for(size_t i = 0; i < graph_partition.size(); ++i) {

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

2016-11-15T19:13:20Z

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

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

	== Масштабируемость алгоритма и его реализации ==		== Масштабируемость алгоритма и его реализации ==
	В статье <ref>http://glaros.dtc.umn.edu/gkhome/node/112</ref> ~~были рассмотрены~~ следующие графы:		В статье <ref>http://glaros.dtc.umn.edu/gkhome/node/112</ref> приводятся результаты работы алгоритма декомпозиции графов из пакета ParMETIS. В таблице ниже приведено время работы алгоритма в зависимости от числа вершин в графе и используемого числа процессоров. Рассмотравились следующие графы:
	граф mrng2 с 1 миллионом вершин, mrng3 с 4 ~~миллиона~~ и граф mrgn4 с 7.5 миллионами вершин.		граф mrng2 с 1 миллионом вершин, mrng3 с 4 миллионами и граф mrgn4 с 7.5 миллионами вершин.

	{\| class="wikitable"		{\| class="wikitable"

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

2016-11-15T19:07:01Z

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

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

	~~Пример~~ реализации последовательного алгоритма на языке C++:		Ниже приведен пример реализации последовательного алгоритма на языке C++. Следует отметить, что исходный массив вершин не изменяется, вся работа осуществляется с индексами.
	<source lang = "c++">		<source lang = "c++">
	#include <algorithm>		#include <algorithm>
Строка 270:		Строка 270:
	int k2 = k - k1;		int k2 = k - k1;

	// bisecting current ~~domain~~		// bisecting current graph
	vector<int> sorted_idx1 = bisect(idx);		vector<int> sorted_idx1 = bisect(idx);
	vector<int> sorted_idx2(make_move_iterator(sorted_idx1.begin() + k1 * sorted_idx1.size() / k),		vector<int> sorted_idx2(make_move_iterator(sorted_idx1.begin() + k1 * sorted_idx1.size() / k),
Строка 294:		Строка 294:
	}		}
	</source>		</source>

	~~Следует отметить, что исходный массив вершин не изменяется, вся работа осуществляется с индексами.~~

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