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

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

02.02.2018, 12:35. Показов 5547. Ответов 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
2872 / 2019 / 991
Регистрация: 21.12.2010
Сообщений: 3,754
Записей в блоге: 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
2872 / 2019 / 991
Регистрация: 21.12.2010
Сообщений: 3,754
Записей в блоге: 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
Ответ Создать тему
Новые блоги и статьи
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android
8Observer8 26.01.2026
Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д.
8Observer8 25.01.2026
Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf
8Observer8 25.01.2026
Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly
8Observer8 24.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль
iceja 24.01.2026
Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы
anaschu 24.01.2026
Решили писать научную статью с неким РОманом
http://iceja.net/ математические сервисы
iceja 20.01.2026
Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов
iceja 18.01.2026
Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru