Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 19.05.2010, 06:17
гость

 
Сообщений: n/a

распараллеливание алгоритмов сортировки на кластерах
собственно, может кто знает хорошие ссылки на эту тему?
интересна сама теория такого распараллеливания сортировок, какие части, методы, почему могут быть распараллелены. а также хотелось бы взглянуть на сами коды реализации (если вдруг есть). материалы можно разные, лучше с уклоном в распараллеливание на нитях.

плюс, хотелось бы узнать - какие алгоритмы сортировки по-вашему вообще следует распараллеливать. как я понял, хорошо поддается лишь сортировка слиянием. для всех остальных это уже не явно делается.
в-общем, кто что знает или может уже делал подобное.
  #2  
Старый 19.05.2010, 14:26
гость

 
Сообщений: n/a

А зачем вам вообще надо распределённо что-то сортировать? Там гораздо больше геморроя будет с организацией ввода/вывода, балансировкой данных,обеспечением отказоустойчивости и т.д., чем с собственно алгоритмом сортировки.

Скорее всего можно и без сортировки обойтись. Вы какую задачу пытаетесь таким образом решить?

Может быть вам подойдет MapReduce (см http://hadoop.apache.org/)? Он делает "почти" сортировку, в том смысле что из n неотсортированных входных файлов вы получаете m выходных файлов (чем меньше m тем сильно дольше будет работать однако), каждый из которых отсортирован, и вам остаётся их слить.

Цитата:
распараллеливание алгоритмов сортировки на кластерах
распараллеливание на нитях
так я не понял, вам распараллеливание нужно на кластере или просто многопроцессорной машине?
  #3  
Старый 20.05.2010, 01:39
гость

 
Сообщений: n/a

да кстати, правильное замечание/ скорее всего на многопроцессорных компьютерах.

основная цель - посмотреть параллельную сортировку на многопроцессорных компьютерах, и переделать алгоритмы сортировки в нитевые программы для них.

позже это все дело будет пускаться на кластер [один узел это несколько многопроцессорных машин] //ограничиваюсь пока внутренней сортировкой, не заморачиваюсь, а глобальные проблемы отказов, вв/выв, сортировки файлов не сильно важны (пока).

набираюсь уму-разуму.
  #4  
Старый 20.05.2010, 02:31
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
основная цель - посмотреть параллельную сортировку на многопроцессорных компьютерах, и переделать алгоритмы сортировки в нитевые программы для них.
Как пример как можно сделать: делишь вход поровну на n частей (где n число процессоров), каждый процессор сортирует свой вход самым быстрым непараллельным алгоритмом (быстрая сортировка), затем синхронизационный барьер, и сливаешь в один поток получившиеся подмассивы сортировкой слиянием.

Цитата:
позже это все дело будет пускаться на кластер
не выйдет. кластер слишком иная система чтобы так просто плавно к ней перейти. с нуля придется переписывать
  #5  
Старый 20.05.2010, 03:44
гость

 
Сообщений: n/a

да, я уже думал по поводу разделения на равное количество частей с дальнейшим их слиянием. но также думал о выделении в самих алгоритмах сортировки каких-либо параллельно выполняющихся частей (не только циклов, но и еще "чего-либо внутри" алгоритма) это "чего-либо" благополучно оставил пока в покое.

Сообщение от гость Посмотреть сообщение
не выйдет. кластер слишком иная система чтобы так просто плавно к ней перейти. с нуля придется переписывать
хмм. а можно поподробней этот момент. в чем будут заключаться основные загвоздки? и как их можно будет разрешить? (нужны будут средства отличные от нитей? например, MPI? ... другое)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Распараллеливание диагонального умножения матрицы на вектор vilza Математические алгоритмы (другое) 1 11.01.2010 12:57
Эффективность алгоритмов сортировки Andrey K Сортировка и поиск 10 12.12.2009 18:50
Рассчет сложности алгоритмов Genesis_39 Математические алгоритмы 4 29.11.2009 03:05
Сортировки гость Сортировка и поиск 2 28.11.2009 07:34
Теория алгоритмов Galina2008 Математические алгоритмы (другое) 3 12.08.2009 14:35