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

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

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

Author24 — интернет-сервис помощи студентам
Есть такой цикл
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 C++
Доброго времени суток. (Нужен совет, так как разбираюсь с omp почти 3 дня и не хватает знанний) ...

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

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

И то, когда сделаешь с вектором, как собираешься "глушить" потоки, которые придут вторыми/третьими? А то ж они будут честно проходить свои куски массивов до конца, и их придётся ждать для корректного завершения.
0
║XLR8║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
02.02.2018, 21:11 3
https://www.youtube.com/playli... 5X2utwnoEG прикольный плей лист
0
What a waste!
1610 / 1302 / 180
Регистрация: 21.04.2012
Сообщений: 2,733
02.02.2018, 21:22 4
Цитата Сообщение от 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║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
03.02.2018, 01:38 5
Цитата Сообщение от 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
gray_fox
03.02.2018, 01:58
  #6

Не по теме:

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

0
║XLR8║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
03.02.2018, 03:53 7
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!
1610 / 1302 / 180
Регистрация: 21.04.2012
Сообщений: 2,733
03.02.2018, 04:41 8
delete

Добавлено через 22 минуты
Цитата Сообщение от outoftime Посмотреть сообщение
Время без разпаралеливания: 2.19197, с: 0.510509
Т.е. имея массив из '1'-ц поиск (1-й по сути) '1'-цы быстрее с 4-я потоками?! Что-то здесь не так...
0
║XLR8║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
03.02.2018, 05:28 9
Цитата Сообщение от 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!
1610 / 1302 / 180
Регистрация: 21.04.2012
Сообщений: 2,733
03.02.2018, 05:39 10
Цитата Сообщение от 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
2859 / 2006 / 988
Регистрация: 21.12.2010
Сообщений: 3,711
Записей в блоге: 15
03.02.2018, 11:33 11
Как верно подмечено необходимость делить список между потоками 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  [ТС] 12
Всем спасибо за помощь. Собственно список _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║
1212 / 909 / 270
Регистрация: 25.07.2009
Сообщений: 4,361
Записей в блоге: 5
03.02.2018, 21:39 13
Цитата Сообщение от Zlobnyj_Prapor Посмотреть сообщение
В принципе можно и убрать, i = 16; ведь 8 потоков быстрее чем один выполнят подобный цикл, но я оставил так.
Херня (:

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

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

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

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

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

Распараллеливание программы
Пишу брутер и встал вопрос о добавление многопоточности. Вот у меня есть функция: std::string...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Новые блоги и статьи
Telegram бот на C#
InfoMaster 08.01.2025
Разработка ботов для Telegram стала неотъемлемой частью современной экосистемы мессенджеров. C# предоставляет мощный и удобный инструментарий для создания разнообразных ботов, от простых. . .
Использование GraphQL в Go (Golang)
InfoMaster 08.01.2025
Go (Golang) является одним из наиболее популярных языков программирования, используемых для создания высокопроизводительных серверных приложений. Его архитектурные особенности и встроенные. . .
Что лучше использовать при создании класса в Java: сеттеры или конструктор?
Alexander-7 08.01.2025
Вопрос подробнее: На вопрос: «Когда одновременно создаются конструктор и сеттеры в классе – это нормально?» куратор уточнил: «Ваш класс может вообще не иметь сеттеров, а только конструктор и геттеры. . .
Как работать с GraphQL на TypeScript
InfoMaster 08.01.2025
Введение в GraphQL и TypeScript В современной разработке веб-приложений GraphQL стал мощным инструментом для создания гибких и эффективных API. В сочетании с TypeScript, эта технология. . .
Счётчик на базе сумматоров + регистров и генератора сигналов согласования.
Hrethgir 07.01.2025
Создан с целью проверки скорости асинхронной логики: ранее описанного сумматора и предополагаемых fast регистров. Регистры созданы на базе ранее описанного, предполагаемого fast триггера. То-есть. . .
Как перейти с Options API на Composition API в Vue.js
BasicMan 06.01.2025
Почему переход на Composition API актуален В мире современной веб-разработки фреймворк Vue. js продолжает эволюционировать, предлагая разработчикам все более совершенные инструменты для создания. . .
Архитектура современных процессоров
inter-admin 06.01.2025
Процессор (центральный процессор, ЦП) является основным вычислительным устройством компьютера, которое выполняет обработку данных и управляет работой всех остальных компонентов системы. Архитектура. . .
История создания реляционной модели баз данных, правила Кодда
Programming 06.01.2025
Предпосылки создания реляционной модели В конце 1960-х годов компьютерная индустрия столкнулась с серьезными проблемами в области управления данными. Существовавшие на тот момент модели данных -. . .
Полезные поделки на Arduino, которые можно сделать самому
raxper 06.01.2025
Arduino как платформа для творчества Arduino представляет собой удивительную платформу для технического творчества, которая открывает безграничные возможности для создания уникальных проектов. Эта. . .
Подборка решений задач на Python
IT_Exp 06.01.2025
Целью данной подборки является предоставление возможности ознакомиться с различными задачами и их решениями на Python, что может быть полезно как для начинающих, так и для опытных программистов. . . .
С чего начать программировать микроконтроллер­­ы
raxper 06.01.2025
Введение в мир микроконтроллеров Микроконтроллеры стали неотъемлемой частью современного мира, окружая нас повсюду: от простых бытовых приборов до сложных промышленных систем. Эти маленькие. . .
Из чего собрать игровой компьютер
inter-admin 06.01.2025
Сборка игрового компьютера требует особого внимания к выбору комплектующих и их совместимости. Правильно собранный игровой ПК не только обеспечивает комфортный геймплей в современных играх, но и. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru