Форум программистов, компьютерный форум CyberForum.ru

Распараллеливание алгоритмов - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
30.06.2012, 11:57     Распараллеливание алгоритмов #1
Доброго дня всем. Встал вопрос о выборе темы,связанной с распараллеливанием алгоритмов.
Какие задачи наиболее "восприимчивы" к распараллеливанию?
Есть ли польза при распараллеливании сортировок?

P.S. Буду рад, если кто-нибудь подскажет какие-либо ресурсы, связанные с данной проблемой
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.06.2012, 11:57     Распараллеливание алгоритмов
Посмотрите здесь:

Распараллеливание C++
Распараллеливание с помощью OpenMP C++
распараллеливание C++
Распараллеливание арифметических выражений C++
Распараллеливание циклов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
30.06.2012, 13:11     Распараллеливание алгоритмов #2
А смысл параллелить? Распараллеливают, когда ни одна часть работы не зависит от остальных. Например, вычисление суммы массива можно. Сначала получаем суммы: a[0]+a[1], a[2]+a[3], a[4]+a[5], a[6]+a[7], ..., a[n-8]+a[n-7], a[n-6]+a[n-5], a[n-4]+a[n-3], a[n-2]+a[n-1], потом (a[0]+a[1])+(a[2]+a[3]), (a[4]+a[5])+(a[6]+a[7]),..., (a[n-8]+a[n-7])+(a[n-6]+a[n-5]), (a[n-4]+a[n-3])+(a[n-2]+a[n-1]), потом ((a[0]+a[1])+(a[2]+a[3]))+((a[4]+a[5])+(a[6]+a[7])),..., ((a[n-8]+a[n-7])+(a[n-6]+a[n-5]))+((a[n-4]+a[n-3])+(a[n-2]+a[n-1])) и так далее. Ни одна из частичных сумм каждого этапа не зависит от остальных, зависимы только суммы, вычисляемые на следующих этапах от предыдущих сумм. То есть одновременно считаем суммы первой и второй половин массива, а потом складываем их и для получения каждой из частичных сумм применяем ещё раз распараллеливание и так, пока не упрёмся в какое нибудь ограничение или по данным, или по исполнителям. А при сортировке положение каждого элемента зависит от значений остальных. Смысл параллелить? Разве что в задаче на сортировку именно нескольких массивов, а не одного. Общее правило: если можешь выделить в поток, то можешь выделить и в ветвь.
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
30.06.2012, 13:20  [ТС]     Распараллеливание алгоритмов #3
Цитата Сообщение от taras atavin Посмотреть сообщение
А смысл параллелить? Распараллеливают, когда ни одна часть работы не зависит от остальных. Например, вычисление суммы массива можно. Сначала получаем суммы: a[0]+a[1], a[2]+a[3], a[4]+a[5], a[6]+a[7], ..., a[n-8]+a[n-7], a[n-6]+a[n-5], a[n-4]+a[n-3], a[n-2]+a[n-1], потом (a[0]+a[1])+(a[2]+a[3]), (a[4]+a[5])+(a[6]+a[7]),..., (a[n-8]+a[n-7])+(a[n-6]+a[n-5]), (a[n-4]+a[n-3])+(a[n-2]+a[n-1]), потом ((a[0]+a[1])+(a[2]+a[3]))+((a[4]+a[5])+(a[6]+a[7])),..., ((a[n-8]+a[n-7])+(a[n-6]+a[n-5]))+((a[n-4]+a[n-3])+(a[n-2]+a[n-1])) и так далее. Ни одна из частичных сумм каждого этапа не зависит от остальных, зависимы только суммы, вычисляемые на следующих этапах от предыдущих сумм. То есть одновременно считаем суммы первой и второй половин массива, а потом складываем их и для получения каждой из частичных сумм применяем ещё раз распараллеливание и так, пока не упрёмся в какое нибудь ограничение или по данным, или по исполнителям. А при сортировке положение каждого элемента зависит от значений остальных. Смысл параллелить? Разве что в задаче на сортировку именно нескольких массивов, а не одного. Общее правило: если можешь выделить в поток, то можешь выделить и в ветвь.
Благодарю за ответ. А можете подсказать, в какую сторону в распараллеливании копать?
ЛетающийЕнот
88 / 67 / 12
Регистрация: 28.06.2012
Сообщений: 161
30.06.2012, 13:22     Распараллеливание алгоритмов #4
taras atavin, merge sort, фазовая сортировка (как вариант чётно-нечётной), например.
-=ЮрА=-
Заблокирован
Автор FAQ
30.06.2012, 21:16     Распараллеливание алгоритмов #5
Цитата Сообщение от RaiaNKnight Посмотреть сообщение
можете подсказать, в какую сторону в распараллеливании копать?
По ссылке распараллеливание с синхронизацией через критическую секцию
Найти произведение минимальных элементов каждой строки матрицы
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2294 / 1664 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.07.2012, 00:37     Распараллеливание алгоритмов #6
taras atavin, ты не прав, вездесущий quick sort отлично параллелится, как и любой, по-моему, алгоритм из разряда "разделяй и властвуй".
Yandex
Объявления
01.07.2012, 00:37     Распараллеливание алгоритмов
Ответ Создать тему
Опции темы

Текущее время: 15:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru