Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.88/25: Рейтинг темы: голосов - 25, средняя оценка - 4.88
0 / 0 / 1
Регистрация: 16.07.2015
Сообщений: 28

Распараллеливание циклов

02.02.2018, 12:35. Показов 5572. Ответов 14
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Есть такой цикл
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::list<int>::iterator iter;
std::list<int>_paramsFFT;
 
for(iter = _paramsFFT.begin(); iter != _paramsFFT.end(); ++ iter)
    {
 
        if ((*iter).isign != fft_ward)
            continue;
 
        if ((*iter).length != mas.size())
            continue;
 
        isGo = true;
        break;
    }
Возможно ли сие чудо инженерной мысли распараллелить с помощью библиотеки OPenMP или библиотекой threads?
В настоящее время пытаюсь проделать это в OPenMP и компилятор жалуется на переменную цикла. Эта переменная почему-то отказывается приводиться к другим типам. Какие мысли имеются?
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
02.02.2018, 12:35
Ответы с готовыми решениями:

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

Распараллеливание циклов
Доброго времени суток. Возникла необходимость распараллелить один численный алгоритм средствами OpenMP. В частности в этом алгоритме...

Распараллеливание циклов с использованием OpenMP C++
Доброго времени суток. (Нужен совет, так как разбираюсь с omp почти 3 дня и не хватает знанний) Есть следующий последовательный код ...

14
зомбяк
 Аватар для TRam_
1585 / 1219 / 345
Регистрация: 14.05.2017
Сообщений: 3,940
02.02.2018, 20:53
Цитата Сообщение от Zlobnyj_Prapor Посмотреть сообщение
или библиотекой threads?
это распараллеливать бессмыленно. Если переделаешь std::list на std::vector, чтобы можно было за o(1) перейти на "1/4 длины, 1/2, 3/4" и начиная с этих мест каждым из потоков проверять массив, то смысл будет. А в таком виде параллелить бессмысленно.

И то, когда сделаешь с вектором, как собираешься "глушить" потоки, которые придут вторыми/третьими? А то ж они будут честно проходить свои куски массивов до конца, и их придётся ждать для корректного завершения.
0
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
02.02.2018, 21:11
https://www.youtube.com/playli... 5X2utwnoEG прикольный плей лист
0
What a waste!
 Аватар для gray_fox
1610 / 1302 / 180
Регистрация: 21.04.2012
Сообщений: 2,733
02.02.2018, 21:22
Цитата Сообщение от TRam_ Посмотреть сообщение
И то, когда сделаешь с вектором, как собираешься "глушить" потоки, которые придут вторыми/третьими
В принципе можно проверку флага добавить в условие цикла), что-нибудь вроде:
C++
1
2
3
4
5
6
for (auto it = localParamsBegin; it != localParamsEnd && !isGo.load(std::memory_order_acquire); ++it) {
   if (it->isign == fft_ward && it->length == mas.size()) {
      isGo.store(true, std::memory_order_release);
      break;
   }
};
Но вряд ли это будет быстро работать...
0
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
03.02.2018, 01:38
Цитата Сообщение от gray_fox Посмотреть сообщение
Но вряд ли это будет быстро работать...
Ага, вот смотрю курс по OpenMP там как раз поднималась тема, что доступ к shared memory между потоками должен быть минимизироваться и выполняться синхронно дабы избежать cache invalidation. И если синхронизировать данные часто overhead перекроет приемущесто от использования паралельных вычислений.

Zlobnyj_Prapor, TRam_, если делать цыкл указанный в вопросе на OpenMP эффективно, должно быть что-то такое (на итераторах, к сожалению, не добился работы)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
 
#include <omp.h>
 
int main()
{
    bool found = false;
    const uint8_t threads_count = 4;
    const size_t size = 100 * 1000 * 1000;
    ::std::vector<int> v(size, 1);
 
    double start = omp_get_wtime();
    ::omp_set_num_threads(threads_count);
#pragma omp parallel for reduction(|:found)
    for (int i = 0; i < size; ++i)
        if (v[i] == 1)
            found = true;
    double end = omp_get_wtime();
    ::std::cout << "time: " << end - start << ::std::endl;
}
Если reduction(|:found) забрать, found будет браться с shared memory и время только уходшится. Я поставил все элементы в 1 специально чтобы показать этот случай. В целом же, на моих 2х ядрах, время на 30% уменьшилось.

И да, break использовать нельзя... Вообще, если у тебя в цыкле есть зависимости от предыдущей итерации, его нельза разпаралелить.
0
03.02.2018, 01:58

Не по теме:

Цитата Сообщение от outoftime Посмотреть сообщение
Zlobnyj_Prapor, TRam_, если делать цыкл указанный в вопросе на OpenMP эффективно, должно быть что-то такое (на итераторах, к сожалению, не добился работы)
Было время (может и сейчас есть), что компилятор не понимал != в условии цикла c #pragma omp parallel for - только < )

0
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
03.02.2018, 03:53
Zlobnyj_Prapor, gray_fox оказался прав, жаль лайк не поставить...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
 
#include <omp.h>
 
int main()
{
    bool found = false;
    const uint8_t threads_count = 4;
    const size_t size = 100 * 1000 * 1000;
    ::std::vector<int> v(size, 1);
 
    double start = omp_get_wtime();
    ::omp_set_num_threads(threads_count);
#pragma omp parallel
    {
        const auto cend = v.end();
#pragma omp for reduction(|| : found)
        for (auto it = v.begin(); it < cend; ++it)
            if (*it == 1)
                found = true;
    }
    double end = omp_get_wtime();
    ::std::cout << "time: " << end - start << ::std::endl;
}
Время без разпаралеливания: 2.19197, с: 0.510509
0
What a waste!
 Аватар для gray_fox
1610 / 1302 / 180
Регистрация: 21.04.2012
Сообщений: 2,733
03.02.2018, 04:41
delete

Добавлено через 22 минуты
Цитата Сообщение от outoftime Посмотреть сообщение
Время без разпаралеливания: 2.19197, с: 0.510509
Т.е. имея массив из '1'-ц поиск (1-й по сути) '1'-цы быстрее с 4-я потоками?! Что-то здесь не так...
0
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
03.02.2018, 05:28
Цитата Сообщение от gray_fox Посмотреть сообщение
поиск
Ну.. это ведь не "поиск" ведь в цыкл нельзя прервать (break). Я вот думаю, что можно выполнить поиск в виде отдельной функции, которая будет получать ренж в виде итераторов и возвращать найден элемент на определенном отрезке.

Можно даже использовать тотже код, что предоставляет ТС в первом посте. Просто обернуть его в функцию и вызывать на поддиапазонах нужного вектора.

В худшем случае надо проходить N, а разпарелеливая, мы худший случай делим на количество потоков, что не O(1), конечно, но всё равно приятно.

Вообще, для эффективного алгоритма надо знать больше о решаемой задаче и, вероятно, сделать свою структуру данных.

Добавлено через 17 минут
gray_fox,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>
 
#include <omp.h>
 
template <class BidirectionalIterator>
bool check(BidirectionalIterator first,
           const BidirectionalIterator &last,
           const size_t &step)
{
    while (first < last)
    {
        if (*first == 1)
            return true;
        first += step;
    }
    return false;
}
 
int main()
{
    const uint8_t threads_count = 4;
    const size_t size = 100 * 1000 * 1000;
    const ::std::vector<int> v(size, 1);
 
    bool found = false;
    size_t step;
 
    ::omp_set_num_threads(threads_count);
    double start = omp_get_wtime();
#pragma omp parallel
    {
#pragma omp single
        step = ::omp_get_num_threads();
        size_t id = ::omp_get_thread_num();
        bool value = ::check(v.begin() + id, v.end(), step);
#pragma omp critical
        found |= value;
    }
    double end = omp_get_wtime();
    ::std::cout << "time: " << end - start << ", found: " << found << ::std::endl;
}
Даже с учетом того что 1 поток завершается быстро, не факт что кому-то попадется отрезок без искомого значения, ну из-за джойна всех потоков, всё равно придется ждать такое-же время в худшем случае (процессор правда не так загружен будет)
0
What a waste!
 Аватар для gray_fox
1610 / 1302 / 180
Регистрация: 21.04.2012
Сообщений: 2,733
03.02.2018, 05:39
Цитата Сообщение от outoftime Посмотреть сообщение
Ну.. это ведь не "поиск" ведь в цыкл нельзя прервать (break).
Изначально задача именно "поиск"; по сути, "в терминах STL":
C++
1
2
auto const it = std::find_if(std::begin(_fftParams), std::end(_fftParams), [&] (auto const& v) { return v.isign == fft_end && v.length == mas.size(); };
isGo = it != std::end(_fftParams);
Цитата Сообщение от outoftime Посмотреть сообщение
В худшем случае надо проходить N, а разпарелеливая, мы худший случай делим на количество потоков, что не O(1), конечно, но всё равно приятно.
Вот именно, что в худшем случае. В лучшем случае банальный линейный поиск найдёт первый элемент и всё.

Не по теме:


Цитата Сообщение от outoftime Посмотреть сообщение
Вообще, для эффективного алгоритма надо знать больше о решаемой задаче и, вероятно, сделать свою структуру данных.
Тут, конечно, лучше бы знать контекст этого "поиска" - скорее всего можно перетасовать данные и/или поменять алгоритмы.
Bottleneck в линейном поиске..?

0
 Аватар для igorrr37
2895 / 2042 / 992
Регистрация: 21.12.2010
Сообщений: 3,791
Записей в блоге: 9
03.02.2018, 11:33
Как верно подмечено необходимость делить список между потоками O(n) отъедает время, и тут вопрос в том где лежат искомые данные. Если искомое в последнем узле списка расклад такой (потоки - время):
4 - 1100; 3 - 1330; 2 - 1800; 1 - 3140,
а если в первом узле списка то:
4 - 199; 3 - 265; 2 - 201; 1 - 2.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <list>
#include <thread>
#include <iterator>
#include <vector>
#include <atomic>
#include <ctime>
#include <string>
 
 
void func(std::atomic<bool>& isgo, std::list<std::string>::iterator ib, std::list<std::string>::iterator ie)
{
    for (; ib != ie; ++ib)
    {
        if (*ib == "aaab")
        {
            std::cout << "yes " << int(ib == ie) << '\n';
            isgo = true;
            break;
        }
        else if (isgo)
        {
            std::cout << "already " << int(ib == ie) << '\n';
            break;
        }
    }
    if(!isgo)
    {
        std::cout << "no " << int(ib == ie) << '\n';
    }
}
 
int main()
{
    std::list<std::string> lst(5'000'000, "aaaa");
    
    std::list<std::string>::iterator ib = lst.begin(), ie = lst.end();
 
    ie = lst.begin();
    std::advance(ie, 2);
 
    *--ie = "aaab";
    ie = lst.begin();
 
    std::atomic<bool> isgo = false;
    int tc = 3; // 4 - 199; 3 - 265; 2 - 201; 1 - 2  // 4 - 1100; 3 - 1330; 2 - 1800; 1 - 3140
    std::vector<std::thread> vec;
    vec.reserve(tc);
    int istep = lst.size() / tc;
    clock_t t1 = clock();
    for (int i = 0; i < tc; ++i)
    {
        if (isgo)
        {
            break;
        }
        ib = ie;
        if (i == tc - 1)
        {
            ie = lst.end();
        }
        else
        {
            std::advance(ie, istep);
        }
        vec.emplace_back(func, std::ref(isgo), ib, ie);
    }
    for (auto& val : vec)
    {
        val.join();
    }
    clock_t t2 = clock();
    std::cout << "time spent: " << t2 - t1 << std::endl;
}
1
0 / 0 / 1
Регистрация: 16.07.2015
Сообщений: 28
03.02.2018, 18:37  [ТС]
Всем спасибо за помощь. Собственно список _paramsFFT содержал не просто тип int а структуры. И итератор был в цикле просто проходил по всем структурам списка paramsFFT и проверял структуры списка paramsFFT на соответствие ключевым параметрам. Вышел я из положения следующим образом: сначала по коду посчитал, сколько максимум структур может оказаться в списке paramsFFT и переделал переменную цикла в int. А чтобы избавиться от break добавил вместо него изменение переменной цикла таким образом чтобы условие цикла стало неверно. Вот что получилось:
iter = _paramsFFT.begin();

for(int i = 0; i< 16; i++)
{
if ((*iter).isign != fft_ward)
{
++iter;
continue;
}

if ((*iter).length != mas.size())
{
++iter;
continue;
}

isGo = true;

i = 16;
}



В принципе можно и убрать, i = 16; ведь 8 потоков быстрее чем один выполнят подобный цикл, но я оставил так.
0
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
03.02.2018, 21:39
Цитата Сообщение от Zlobnyj_Prapor Посмотреть сообщение
В принципе можно и убрать, i = 16; ведь 8 потоков быстрее чем один выполнят подобный цикл, но я оставил так.
Херня (:

Если у тебя "i" в стеке потока, остальные потоки продолжат лопатить свои куски массива. igorrr37 показал портируемый пример с ручным управлением потоками и с использованием ::std::list. Я как раз хотел разобрать как оно всё работает, так как с потоками в STL я еще не сталкивался, но очень похоже на pthread.

Добавлено через 6 минут
igorrr37, хотел спросить: как сильно использование ::std::atomic на каждой итерации бьет по производительности? Ведь чем больше потоков, тем больше они должны ожидать пока атомик станет доступным. Объясните, пожалуйста.
0
 Аватар для igorrr37
2895 / 2042 / 992
Регистрация: 21.12.2010
Сообщений: 3,791
Записей в блоге: 9
04.02.2018, 02:35
outoftime, если искомая величина находится в последнем узле списка и использовать атомик то результаты:
4 - 1110; 1 - 3140; 8 - 1130
а если атомик заменить на простой bool то:
4 - 960, 1 - 2530; 8 - 950
0
║XLR8║
 Аватар для outoftime
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,360
Записей в блоге: 5
04.02.2018, 04:06
igorrr37, на сколько я понял с доки по atomic он использует локи, что значит, остальные потоки будут ждать. И если мы говорим о паралельных вычислениях, то лочить выполнение на каждой итерации цыкла неприемлимо (я не говорю о случае когда искомый элемент первый). Еще, в отличии от OpenMP я не нашел информации о том какая стратегия применяеся в STL когда потоку нужно ждать освобождения лока.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
04.02.2018, 04:06
Помогаю со студенческими работами здесь

OpenIM - не работает распараллеливание циклов
void Multiplication(int a, int b) { int c; int i; int j; int count(0); omp_set_num_threads(count); #pragma omp...

Распараллеливание циклов с ипользованием OpenMP
Есть проблема , получился парадокс - время роботы программы с распараллеливанием дольше на 1 сек чем без распараллеливания, ожидалось...

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

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

Распараллеливание программы
Пишу брутер и встал вопрос о добавление многопоточности. Вот у меня есть функция: std::string wbfunc(std::string&amp; hash) { ...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Новые блоги и статьи
Отправка уведомления на почту при изменении наименования справочника
Maks 24.03.2026
Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .
модель ЗдравоСохранения 5. Меньше увольнений- больше дохода!
anaschu 24.03.2026
Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .
Midnight Chicago Blues
kumehtar 24.03.2026
Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++
8Observer8 24.03.2026
Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip
Жизнь в неопределённости
kumehtar 23.03.2026
Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .
Модель здравоСохранения: работники работают быстрее после её введения.
anaschu 23.03.2026
geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .
Контроль уникальности заводского номера
Maks 23.03.2026
Алгоритм контроля уникальности заводского (или серийного) номера на примере нетипового документа выдачи шин для спецтехники с табличной частью, разработанного в конфигурации КА2. Данные берутся из. . .
Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения
anaschu 22.03.2026
e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru