Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 465
Записей в блоге: 1
#1

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

30.06.2012, 11:57. Просмотров 2099. Ответов 5
Метки нет (Все метки)

Доброго дня всем. Встал вопрос о выборе темы,связанной с распараллеливанием алгоритмов.
Какие задачи наиболее "восприимчивы" к распараллеливанию?
Есть ли польза при распараллеливании сортировок?

P.S. Буду рад, если кто-нибудь подскажет какие-либо ресурсы, связанные с данной проблемой
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.06.2012, 11:57
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Распараллеливание алгоритмов (C++):

распараллеливание - C++
Скажите, кто-нибудь занимался распараллеливанием в си++? В моих попытках что-либо распараллелить через omp все выходило только в несколько...

Распараллеливание - C++
Всем добрый вечер. Если кто знает подскажите,мне надо распараллелить перемножение матриц,преподаватель сказал,что это делается просто с...

Распараллеливание циклов - C++
Возникли трудности с освоением OpenMP Непонимаю, почему если закоментировать вот этот фрагмент кода, то программа работает вы разы...

Распараллеливание вычислений - C++
Здравствуйте. Может кто сможет подсказать как мне решить следующую задачу: необходимо распараллелить следующий последовательный код:...

Распараллеливание программы - C++
Помогите эту последовательную программу распараллелить на параллельных 2 процесса. #include <iostream> #include<thread> using...

Распараллеливание вычислений - C++
Вычисляю произведение матриц несколькими потоками (количество задаётся пользователем). Потоки "засыпают" на 1 мс. При вычислении...

5
taras atavin
3570 / 1753 / 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])) и так далее. Ни одна из частичных сумм каждого этапа не зависит от остальных, зависимы только суммы, вычисляемые на следующих этапах от предыдущих сумм. То есть одновременно считаем суммы первой и второй половин массива, а потом складываем их и для получения каждой из частичных сумм применяем ещё раз распараллеливание и так, пока не упрёмся в какое нибудь ограничение или по данным, или по исполнителям. А при сортировке положение каждого элемента зависит от значений остальных. Смысл параллелить? Разве что в задаче на сортировку именно нескольких массивов, а не одного. Общее правило: если можешь выделить в поток, то можешь выделить и в ветвь.
1
RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 465
Записей в блоге: 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])) и так далее. Ни одна из частичных сумм каждого этапа не зависит от остальных, зависимы только суммы, вычисляемые на следующих этапах от предыдущих сумм. То есть одновременно считаем суммы первой и второй половин массива, а потом складываем их и для получения каждой из частичных сумм применяем ещё раз распараллеливание и так, пока не упрёмся в какое нибудь ограничение или по данным, или по исполнителям. А при сортировке положение каждого элемента зависит от значений остальных. Смысл параллелить? Разве что в задаче на сортировку именно нескольких массивов, а не одного. Общее правило: если можешь выделить в поток, то можешь выделить и в ветвь.
Благодарю за ответ. А можете подсказать, в какую сторону в распараллеливании копать?
0
ЛетающийЕнот
88 / 67 / 12
Регистрация: 28.06.2012
Сообщений: 161
30.06.2012, 13:22 #4
taras atavin, merge sort, фазовая сортировка (как вариант чётно-нечётной), например.
0
-=ЮрА=-
Заблокирован
Автор FAQ
30.06.2012, 21:16 #5
Цитата Сообщение от RaiaNKnight Посмотреть сообщение
можете подсказать, в какую сторону в распараллеливании копать?
По ссылке распараллеливание с синхронизацией через критическую секцию
Найти произведение минимальных элементов каждой строки матрицы
0
CyBOSSeR
Эксперт С++
2304 / 1674 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.07.2012, 00:37 #6
taras atavin, ты не прав, вездесущий quick sort отлично параллелится, как и любой, по-моему, алгоритм из разряда "разделяй и властвуй".
0
01.07.2012, 00:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.07.2012, 00:37
Привет! Вот еще темы с ответами:

Странное распараллеливание - C++
Добрый вечер, коллеги. У меня следующая проблема. Преподаватель сказал распараллелить программу, обрабатывающую изображения в папке....

Распараллеливание через omp.h - C++
// labaOMP.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" #include <iostream> #include <omp.h> ...

Распараллеливание с помощью OpenMP - C++
Здравствуйте, уважаемые участники форума! Имеется цикл вида:for (i=1; i<number; i++) { do something; }Цикл выполняется...

Распараллеливание арифметических выражений - C++
Здравствуйте. Есть задача - распараллелить вычисление арифмитического выражения, подобное виду (a+b)+(c+(d+e+f))+h т.е....


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru