Сортировка MPI

@Kertis138 · Регистрация: 25.02.2016

Здравствуйте!

Есть K узлов, на которых нужно отсортировать массив целых чисел.
Единственная проблема - размер массима столь велик, что ни один узел не может загрузить его полность.

Я делю массив на K частей и на каждом узле сортирую свой кусок - здесь проблем не возникло. А вот, что делать далее я не могу понять.
Я не могу слить воедино все куски, так как ни один узел не может удержать в памяти все куски.
Как это можно сделать? Может через внешний файл как нибудь?

1) Поделить массив на K кусков
2) Отосртирвать каждый кусок на отдельном узле
3) Как слить все воедино и записать в файл на ROOT узле, если ROOT узел не может в памяти слить все куски воедино?

Vourhey · 07.05.2020, 19:19

Сообщение от Kertis138

Как слить все воедино и записать в файл на ROOT узле, если ROOT узел не может в памяти слить все куски воедино?

Допустим, что узлов 5. Элементов 1000. Каждый сортирует свои 200.
Потом берем по 40 уже отсортированных элементов с каждого узла и отправляем на рутовую ноду, которая их мержит и записывает в файл. И так далее.

@Kertis138 · 07.05.2020, 22:21 **[ТС]**

Сообщение от Vourhey

Потом берем по 40 уже отсортированных элементов с каждого узла и отправляем на рутовую ноду, которая их мержит и записывает в файл. И так далее.

Может я вас не так понял, но это не работает.
Пример:

10 9 8 7 6 5 4 3 2 1

Делятся на 2 узла и сортируются:
1) 1 2 3 4 5
2) 6 7 8 9 10

Далее берутся по 2 элемента из каждого узла и отправляются на ROOT:
1) 1 2 6 7
2) 3 4 8 9
3) 5 10

В итоге у меня в файле:
1 2 6 7 3 4 8 9 10

Vourhey · 07.05.2020, 23:01

Сообщение от Kertis138

Может я вас не так понял,

Да, ты не так понял. Посмотри как работает merge sort, чтобы понять, о чем я говорю. В частности та его часть, которая про объединение отсортированных частей. Ты не смержил два отсортированных массива, а просто поставил один за другим.

@Kertis138 · 07.05.2020, 23:58 **[ТС]**

Сообщение от Vourhey

а просто поставил один за другим.

Если говорить про ограничения оперативки, то она позволяет держать в памяти только 5 элементов.
Так вот первая итерация возвращает 1 2 6 7. В каком бы опрядке я их не записил в файл, все равно придется их пересортировывать на второй итерации.
То есть все равно не получаеться сделать все это без временных файлов

@AlexVRud · 08.05.2020, 00:31

Самое простое применить параллельный вариант сортировки "пузырьком" (чёт-нечет) для узлов.
т.е. делаем слияние для пар:

* 0-1, 2-3, 4-5, 6-7, ...
* 1-2, 3-4, 5-6, 7-8, ...
* 0-1, 2-3, 4-5, 6-7, ...
* 1-2, 3-4, 5-6, 7-8, ...
...

Vourhey · 08.05.2020, 01:22

Сообщение от Kertis138

Так вот первая итерация возвращает 1 2 6 7. В каком бы опрядке я их не записил в файл, все равно придется их пересортировывать на второй итерации.

После того, как записана польностью первая порция данных (1 и 2), новая должна браться и так же проверяться (3 4 сравниваться с 6). Когда буфер одного из узлов полностью записан, она снова заполняется. Сравнение для множественных массивов делается через min-heap.

@AlexVRud · 08.05.2020, 01:42

Сообщение от Vourhey

Потом берем по 40 уже отсортированных элементов с каждого узла и отправляем на рутовую ноду, которая их мержит и записывает в файл. И так далее.

И вы теряете возможность параллельной обработки на втором этапе. У вас один узел выполняет всю работу по слиянию нескольких массив с постоянным запросом новых порций от нескольких источников. Это что-то около O(N*M), где N - размер массива, M - число процессов.

Тогда как тупая пузырьковая сортировка справиться за O(2N/M * M)=O(N)

Vourhey · 08.05.2020, 03:57

И вы теряете возможность параллельной обработки на втором этапе

Спасибо, я в курсе.

Это что-то около O(N*M), где N - размер массива, M - число процессов

n*logn

Тогда как тупая пузырьковая сортировка справиться за O(2N/M * M)=O(N)

Квадрат потерял где-то.

@AlexVRud · 08.05.2020, 12:21

Сообщение от Vourhey

Квадрат потерял где-то.

Неа. Т.к. M действий выполняется параллельно, то M^2 становиться M.

Ещё раз. У нас есть M отсортированных массивов на M узлах.

1. на узлах 0 и 1 делаем слияние их массивов так, чтобы на 0-м узле остались только младшие, а на 1-м только старшие значения. (аля сравнили и переставили в пузырьковой сортировке) (Пример: было [3,5,8] и [1,4,9], стало [1,3,4] и [5,8,9]) Трудоёмкость O(N/M). Это же делаем ОДНОВРЕМЕННО на узлах 2 и 3, 4 и 5, и т.д.
2. Выполняем аналогичную работу но для пар 1-2, 3-4, 5-6, ...
3. Поочерёдно выполняем пункты 1 и 2 M раз.

Итого O(N/M*M)

В результате на M узлах хранится отсортированный массив. И нам не нужен файл. Для его хранения.

@Kertis138 6 / 6 / 1 Регистрация: 25.02.2016 Сообщений: 331
		1
	Сортировка MPI 07.05.2020, 19:04. Показов 4167. Ответов 9 Метки нет (Все метки) Здравствуйте! Есть K узлов, на которых нужно отсортировать массив целых чисел. Единственная проблема - размер массима столь велик, что ни один узел не может загрузить его полность. Я делю массив на K частей и на каждом узле сортирую свой кусок - здесь проблем не возникло. А вот, что делать далее я не могу понять. Я не могу слить воедино все куски, так как ни один узел не может удержать в памяти все куски. Как это можно сделать? Может через внешний файл как нибудь? 1) Поделить массив на K кусков 2) Отосртирвать каждый кусок на отдельном узле 3) Как слить все воедино и записать в файл на ROOT узле, если ROOT узел не может в памяти слить все куски воедино? __________________ Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь 0

Vourhey Почетный модератор 7388 / 2634 / 281 Регистрация: 29.07.2006 Сообщений: 13,696
	07.05.2020, 19:19	2
	Сообщение от Kertis138 Как слить все воедино и записать в файл на ROOT узле, если ROOT узел не может в памяти слить все куски воедино? Допустим, что узлов 5. Элементов 1000. Каждый сортирует свои 200. Потом берем по 40 уже отсортированных элементов с каждого узла и отправляем на рутовую ноду, которая их мержит и записывает в файл. И так далее. 0

@Kertis138 6 / 6 / 1 Регистрация: 25.02.2016 Сообщений: 331
	07.05.2020, 22:21 [ТС]	3
	Сообщение от Vourhey Потом берем по 40 уже отсортированных элементов с каждого узла и отправляем на рутовую ноду, которая их мержит и записывает в файл. И так далее. Может я вас не так понял, но это не работает. Пример: 10 9 8 7 6 5 4 3 2 1 Делятся на 2 узла и сортируются: 1) 1 2 3 4 5 2) 6 7 8 9 10 Далее берутся по 2 элемента из каждого узла и отправляются на ROOT: 1) 1 2 6 7 2) 3 4 8 9 3) 5 10 В итоге у меня в файле: 1 2 6 7 3 4 8 9 10 0

Vourhey Почетный модератор 7388 / 2634 / 281 Регистрация: 29.07.2006 Сообщений: 13,696
	07.05.2020, 23:01	4
	Сообщение от Kertis138 Может я вас не так понял, Да, ты не так понял. Посмотри как работает merge sort, чтобы понять, о чем я говорю. В частности та его часть, которая про объединение отсортированных частей. Ты не смержил два отсортированных массива, а просто поставил один за другим. 0

@Kertis138 6 / 6 / 1 Регистрация: 25.02.2016 Сообщений: 331
	07.05.2020, 23:58 [ТС]	5
	Сообщение от Vourhey а просто поставил один за другим. Если говорить про ограничения оперативки, то она позволяет держать в памяти только 5 элементов. Так вот первая итерация возвращает 1 2 6 7. В каком бы опрядке я их не записил в файл, все равно придется их пересортировывать на второй итерации. То есть все равно не получаеться сделать все это без временных файлов 0

@AlexVRud 693 / 303 / 99 Регистрация: 04.07.2014 Сообщений: 842
	08.05.2020, 00:31	6
	Самое простое применить параллельный вариант сортировки "пузырьком" (чёт-нечет) для узлов. т.е. делаем слияние для пар: * 0-1, 2-3, 4-5, 6-7, ... * 1-2, 3-4, 5-6, 7-8, ... * 0-1, 2-3, 4-5, 6-7, ... * 1-2, 3-4, 5-6, 7-8, ... ... 0

Vourhey Почетный модератор 7388 / 2634 / 281 Регистрация: 29.07.2006 Сообщений: 13,696
	08.05.2020, 01:22	7
	Сообщение от Kertis138 Так вот первая итерация возвращает 1 2 6 7. В каком бы опрядке я их не записил в файл, все равно придется их пересортировывать на второй итерации. После того, как записана польностью первая порция данных (1 и 2), новая должна браться и так же проверяться (3 4 сравниваться с 6). Когда буфер одного из узлов полностью записан, она снова заполняется. Сравнение для множественных массивов делается через min-heap. 1

@AlexVRud 693 / 303 / 99 Регистрация: 04.07.2014 Сообщений: 842
	08.05.2020, 01:42	8
	Сообщение от Vourhey Потом берем по 40 уже отсортированных элементов с каждого узла и отправляем на рутовую ноду, которая их мержит и записывает в файл. И так далее. И вы теряете возможность параллельной обработки на втором этапе. У вас один узел выполняет всю работу по слиянию нескольких массив с постоянным запросом новых порций от нескольких источников. Это что-то около O(NM), где N - размер массива, M - число процессов. Тогда как тупая пузырьковая сортировка справиться за O(2N/M M)=O(N) 0

Vourhey Почетный модератор 7388 / 2634 / 281 Регистрация: 29.07.2006 Сообщений: 13,696
	08.05.2020, 03:57	9
	И вы теряете возможность параллельной обработки на втором этапе Спасибо, я в курсе. Это что-то около O(NM), где N - размер массива, M - число процессов nlogn Тогда как тупая пузырьковая сортировка справиться за O(2N/M * M)=O(N) Квадрат потерял где-то. 0

@AlexVRud 693 / 303 / 99 Регистрация: 04.07.2014 Сообщений: 842
	08.05.2020, 12:21	10
	Сообщение от Vourhey Квадрат потерял где-то. Неа. Т.к. M действий выполняется параллельно, то M^2 становиться M. Ещё раз. У нас есть M отсортированных массивов на M узлах. 1. на узлах 0 и 1 делаем слияние их массивов так, чтобы на 0-м узле остались только младшие, а на 1-м только старшие значения. (аля сравнили и переставили в пузырьковой сортировке) (Пример: было [3,5,8] и [1,4,9], стало [1,3,4] и [5,8,9]) Трудоёмкость O(N/M). Это же делаем ОДНОВРЕМЕННО на узлах 2 и 3, 4 и 5, и т.д. 2. Выполняем аналогичную работу но для пар 1-2, 3-4, 5-6, ... 3. Поочерёдно выполняем пункты 1 и 2 M раз. Итого O(N/M*M) В результате на M узлах хранится отсортированный массив. И нам не нужен файл. Для его хранения. 1

Опции темы