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

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

Войти
Регистрация
Восстановить пароль
 
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
#1

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

15.06.2013, 20:43. Просмотров 745. Ответов 10
Метки нет (Все метки)

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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.06.2013, 20:43     Можно ли это распараллелить?
Посмотрите здесь:

C++ Как это можно реализовать
C++ как можно сделать это? если вообще возможно (не задача)
Можно ли это написать как то проще C++
как можно переписать вот это в с++ C++
C++ как можно реализовать это в коде?
Выяснить можно ли с поля (k,l) одним ходом ферьзя попасть на поле(m,n). Если нет, то выяснить, как это можно сделать за два хода C++
Как это можно реализовать? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1921 / 1187 / 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
Эксперт С++
4870 / 3009 / 370
Регистрация: 10.11.2010
Сообщений: 11,059
Записей в блоге: 10
Завершенные тесты: 1
15.06.2013, 20:50     Можно ли это распараллелить? #3
Распараллелить рекурсию?.. ну хз...
Ты бы хоть написал что делает эта функция.
Thinker
Эксперт C++
 Аватар для Thinker
4218 / 2192 / 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
1921 / 1187 / 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
1242 / 991 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
16.06.2013, 12:36     Можно ли это распараллелить? #8
/me шепчет: worker threads.
diagon
Higher
 Аватар для diagon
1921 / 1187 / 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++
Можно ли сравнивать строковые литералы? как правильно это сделать? C++
C++ Сумма всех цифр в строке. Как можно реализовать это в С++ ?
C++ Можно ли это заменить чем-то менее объёмным
Распараллелить процессы C++

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1921 / 1187 / 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     Можно ли это распараллелить?
Ответ Создать тему
Опции темы

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