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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.05.2020, 19:04
Ответы с готовыми решениями:

MPI
Всем добрый день! Извиняюсь за нахальство - у меня аж три вопроса и практически...

MPI
Здравствуйте, передо мной стоит задача распараллелить алгоритм Евклида НОК коллективными операциями...

MPI
Подскажите пожалуйста что не так то, программа не работает, только при исполнении выдаёт ошибки....

Установка MPI
Ребята помогите с установкой MPI на VS 2012, уже куча всего по устанавливал, прописал все пути в...

9
Почетный модератор
7388 / 2634 / 281
Регистрация: 29.07.2006
Сообщений: 13,696
07.05.2020, 19:19 2
Цитата Сообщение от Kertis138 Посмотреть сообщение
Как слить все воедино и записать в файл на ROOT узле, если ROOT узел не может в памяти слить все куски воедино?
Допустим, что узлов 5. Элементов 1000. Каждый сортирует свои 200.
Потом берем по 40 уже отсортированных элементов с каждого узла и отправляем на рутовую ноду, которая их мержит и записывает в файл. И так далее.
0
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
Почетный модератор
7388 / 2634 / 281
Регистрация: 29.07.2006
Сообщений: 13,696
07.05.2020, 23:01 4
Цитата Сообщение от Kertis138 Посмотреть сообщение
Может я вас не так понял,
Да, ты не так понял. Посмотри как работает merge sort, чтобы понять, о чем я говорю. В частности та его часть, которая про объединение отсортированных частей. Ты не смержил два отсортированных массива, а просто поставил один за другим.
0
6 / 6 / 1
Регистрация: 25.02.2016
Сообщений: 331
07.05.2020, 23:58  [ТС] 5
Цитата Сообщение от Vourhey Посмотреть сообщение
а просто поставил один за другим.
Если говорить про ограничения оперативки, то она позволяет держать в памяти только 5 элементов.
Так вот первая итерация возвращает 1 2 6 7. В каком бы опрядке я их не записил в файл, все равно придется их пересортировывать на второй итерации.
То есть все равно не получаеться сделать все это без временных файлов
0
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
Почетный модератор
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
693 / 303 / 99
Регистрация: 04.07.2014
Сообщений: 842
08.05.2020, 01:42 8
Цитата Сообщение от Vourhey Посмотреть сообщение
Потом берем по 40 уже отсортированных элементов с каждого узла и отправляем на рутовую ноду, которая их мержит и записывает в файл. И так далее.
И вы теряете возможность параллельной обработки на втором этапе. У вас один узел выполняет всю работу по слиянию нескольких массив с постоянным запросом новых порций от нескольких источников. Это что-то около O(N*M), где N - размер массива, M - число процессов.

Тогда как тупая пузырьковая сортировка справиться за O(2N/M * M)=O(N)
0
Почетный модератор
7388 / 2634 / 281
Регистрация: 29.07.2006
Сообщений: 13,696
08.05.2020, 03:57 9
И вы теряете возможность параллельной обработки на втором этапе
Спасибо, я в курсе.
Это что-то около O(N*M), где N - размер массива, M - число процессов
n*logn
Тогда как тупая пузырьковая сортировка справиться за O(2N/M * M)=O(N)
Квадрат потерял где-то.
0
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.05.2020, 12:21
Помогаю со студенческими работами здесь

mpi суммирование
Привет! Такой вопрос. Никак не могу додуматься до реализации такого фрагмента кода. Есть несколько...

MPI процессы
пусть n-количество процессов. процесс с номером 0 запрашивает у пользователя элементы квадратной...

C++ MPI Гиперкуб
Здравствуйте ,форумчане.Возник вопрос при решении следующей задачи:Топология процессов - «гиперкуб»...

С++ с распараллеливанием MPI
Добрый день! Мне очень нужна ваша помощь. Задали написать программу "Метод трапеций для...

MPI в проекте VS
Поставил все для MPI, использовал MPINCH2, установил все вроде правильно, в свойствах проэекта VS...

MPI программа
Подскажите пожалуйста как исправить ошибку.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru