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

Можно ли это распараллелить? - C++

Восстановить пароль Регистрация
 
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
15.06.2013, 20:43     Можно ли это распараллелить? #1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int min(int *s, int *e)
{
 int *m;
 int l;
 int r;
 if (s==e)
 {
  return *s;
 }
 m=s+(e-s)/2;
 l=min(s, m);
 r=min(m+1, e);
 if (l<r)
 {
  return l;
 }
 return r;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
15.06.2013, 20:49     Можно ли это распараллелить? #2
Цитата Сообщение от taras atavin Посмотреть сообщение
l=min(s, m);
Эту вычислить асинхронно.

Цитата Сообщение от taras atavin Посмотреть сообщение
r=min(m+1, e);
А эту - в текущем потоке. Затем дождаться завершения первого запроса и забрать результат.

Ну, это достаточно мощная пессимизация (т.е. сильно замедлит вычисления), но ведь параллелиться же.
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
15.06.2013, 20:50     Можно ли это распараллелить? #3
Распараллелить рекурсию?.. ну хз...
Ты бы хоть написал что делает эта функция.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
15.06.2013, 20:54     Можно ли это распараллелить? #4
Цитата Сообщение от lazybiz Посмотреть сообщение
что делает эта функция.
ищет минимум в массиве методом "разделяй и властвуй"
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
16.06.2013, 08:37  [ТС]     Можно ли это распараллелить? #5
Цитата Сообщение от diagon Посмотреть сообщение
Ну, это достаточно мощная пессимизация (т.е. сильно замедлит вычисления),
А от чего замедление? Часть или всё время ожидания результата
C++
1
l=min(s, m);
при параллельном вычислении вычисляется
C++
1
r=min(m+1, e);
, а при последовательном не делается больше ни чего, но дождаться результата надо в любом случае.

Добавлено через 46 секунд
Цитата Сообщение от lazybiz Посмотреть сообщение
Ты бы хоть написал что делает эта функция.
Это написано в самой функции.

Добавлено через 17 секунд
Цитата Сообщение от lazybiz Посмотреть сообщение
Распараллелить рекурсию?
Именно рекурсию.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
16.06.2013, 11:38     Можно ли это распараллелить? #6
Цитата Сообщение от taras atavin Посмотреть сообщение
А от чего замедление?
Для каждого вызова рекурсии будет создаваться свой поток. Учитывая то, что рекурсия сильно ветвится, будет задействовано ну очень много потоков.
Вот, кстати, реализация на с++11 для суммы.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
16.06.2013, 12:29  [ТС]     Можно ли это распараллелить? #7
Цитата Сообщение от diagon Посмотреть сообщение
Для каждого вызова рекурсии будет создаваться свой поток. Учитывая то, что рекурсия сильно ветвится, будет задействовано ну очень много потоков.
На 32-м вызове в глубь будет 2 147 483 648. Сколько времени надо, чтоб сравнить 2 147 483 648-ми чисел и сколько для сравнения 32-х? Речь ведь именно о физически параллельном исполнении, а не о миллиардах потоков ради самих потоков. А если аппаратно столько ветвей поддержать нельзя, то получаем ограничение на размер массива.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
16.06.2013, 12:36     Можно ли это распараллелить? #8
/me шепчет: worker threads.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
16.06.2013, 13:15     Можно ли это распараллелить? #9
Цитата Сообщение от taras atavin Посмотреть сообщение
а не о миллиардах потоков ради самих потоков
В том то и проблема, что если количество потоков равно количеству ядер, то будет достигнута оптимальная скорость. Однако если потоков больше чем ядер, то начнется снижение производительности.
И в данном случае количество_потоков = размер_массива / 2
Т.е. уже для массива в 200 элементов создастся 100 потоков.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
16.06.2013, 13:24  [ТС]     Можно ли это распараллелить? #10
Цитата Сообщение от diagon Посмотреть сообщение
В том то и проблема, что если количество потоков равно количеству ядер, то будет достигнута оптимальная скорость. Однако если потоков больше чем ядер, то начнется снижение производительности.
Ветвей больше, чем ядер, быть не может, но бывают маленькие массивы. Интересует разделение этой функции именно на ветви, а не потоки ради потоков.

Добавлено через 3 минуты
Цитата Сообщение от diagon Посмотреть сообщение
И в данном случае количество_потоков = размер_массива / 2
Т.е. уже для массива в 200 элементов создастся 100 потоков.
Массированный параллелизм водится на соответствующем "железе" из будущего, скорее всего квантовом, а массив может иметь и 4 элемента.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.06.2013, 13:32     Можно ли это распараллелить?
Еще ссылки по теме:

C++ нужно создать таблицу из 3 строк и 4 столбцов и заполнить её (любой информацией,это неважно) . Как это можно сделать ?
Как это можно реализовать? C++
Можно ли это назвать пузырьковой сортировкой? C++

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
16.06.2013, 13:32     Можно ли это распараллелить? #11
Цитата Сообщение от taras atavin Посмотреть сообщение
Ветвей больше, чем ядер быть не может
Я проинтерпретирую это как "количество одновременно работающих потоков не может превышать число ядер". Еще как может. В таком случае ось будет стараться создать иллюзию, что потоки работают одновременно - каждое ядро будет выполнять кусочек от одного потока, потом кусочек от другого и так далее. И вот на такое переключение между потоками тратится достаточно много времени. А если потоков сотни, то переключение между потоками будет занимать больше времени, чем, собственно, выполнение полезной работы.

Цитата Сообщение от taras atavin Посмотреть сообщение
бывают маленькие массивы
Для них попросту невыгодно создавать несколько потоков. Например
Цитата Сообщение от taras atavin Посмотреть сообщение
массив может иметь и 4 элемента
Найти минимум из 4 элементов явно быстрее, чем создать новый поток.

Цитата Сообщение от taras atavin Посмотреть сообщение
Интересует разделение этой функции именно на ветви, а не потоки ради потоков.
Ну, на ветви она разделятся сама по себе, рекурсия же. На потоки она тоже прекрасно разделяется - я показал, как.
Я лишь пытаюсь намекнуть, что если вам это нужно для увеличения производительности, то ничего из этого не выйдет.
Yandex
Объявления
16.06.2013, 13:32     Можно ли это распараллелить?
Ответ Создать тему
Опции темы

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