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

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

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

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

15.06.2013, 20:43. Просмотров 805. Ответов 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++
#include &lt;cstdlib&gt; #include &lt;iostream&gt; #include &lt;stdlib.h&gt; #include &lt;math.h&gt; using namespace std; /* В одномерном...

как можно переписать вот это в с++ - C++
program lab4; var i,j,jmax:integer; a:array of real; b:array of real; k,max,s:real; begin for i:=1 to 5 do for j:=1 to 4 do...

Можно ли это назвать пузырьковой сортировкой? - C++
int last = arraySize-1; while (last &gt; 0) { int max = last; for (int i = 0; i &lt;= last; i++) if (sort &gt; sort) max...

как можно реализовать это в коде? - C++
Здравствуйте. Если вам не трудно скажите как можно в коде реализовать это: Вариантов множество. Например, заводится массив с указателями...

Можно ли это заменить чем-то менее объёмным - C++
Можно ли это заменить чем-то менее объёмным... :scratch: if (stroka == 'А') x = 0, y = 0; else if (stroka == 'Б') x =...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1927 / 1193 / 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
Эксперт С++
4881 / 3017 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 10
Завершенные тесты: 1
15.06.2013, 20:50     Можно ли это распараллелить? #3
Распараллелить рекурсию?.. ну хз...
Ты бы хоть написал что делает эта функция.
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
15.06.2013, 20:54     Можно ли это распараллелить? #4
Цитата Сообщение от lazybiz Посмотреть сообщение
что делает эта функция.
ищет минимум в массиве методом "разделяй и властвуй"
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
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
16.06.2013, 11:38     Можно ли это распараллелить? #6
Цитата Сообщение от taras atavin Посмотреть сообщение
А от чего замедление?
Для каждого вызова рекурсии будет создаваться свой поток. Учитывая то, что рекурсия сильно ветвится, будет задействовано ну очень много потоков.
Вот, кстати, реализация на с++11 для суммы.
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
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
16.06.2013, 12:36     Можно ли это распараллелить? #8
/me шепчет: worker threads.
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
16.06.2013, 13:15     Можно ли это распараллелить? #9
Цитата Сообщение от taras atavin Посмотреть сообщение
а не о миллиардах потоков ради самих потоков
В том то и проблема, что если количество потоков равно количеству ядер, то будет достигнута оптимальная скорость. Однако если потоков больше чем ядер, то начнется снижение производительности.
И в данном случае количество_потоков = размер_массива / 2
Т.е. уже для массива в 200 элементов создастся 100 потоков.
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++
надо сравнить введенный строковый литерал с одним из доступных. int main() { setlocale(0,&quot;&quot;); char const s =15; char...

как можно сделать это? если вообще возможно (не задача) - C++
есть задача, на двумерный массив... вывел массив 5х5 с рандомными числами, нужно найти числа локального минимума, т.е. чтоб число было...

Сумма всех цифр в строке. Как можно реализовать это в С++ ? - C++
Сумма всех цифр в строке.

Распараллелить процессы - C++
доброго вечера, прошу помощи, дали задание распараллелить процессы, что бы уменьшить время выполнения программы, я в программировании...

Помогите распараллелить цикл!!! - C++
Эксперты помогите, распараллелить консольное приложение на два(или четыре) ядра. Раньше ни когда не сталкивался с этим, даже не знаю, что...


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

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

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