Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.88/25: Рейтинг темы: голосов - 25, средняя оценка - 4.88
 Аватар для HamsterGamer
40 / 29 / 11
Регистрация: 21.06.2019
Сообщений: 201

Не могу понять задание на многопоточку

27.01.2021, 11:38. Показов 5812. Ответов 35

Студворк — интернет-сервис помощи студентам
Всем привет, пытаюсь добить книжку Уильямса, но как-то тяжело без практики и поэтому нашел (вроде бы) неплохие задания по многопоточке - http://oop.afti.ru/task_blocks/10-mnogopotochnost .
Парочку уже реализовал и мне они казались несложными, но вот задание под названием «Алгоритмы min, max» я понять не могу.
А именно следующий текст:
"Многопоточность должна быть реализована как с помощью потоков (std::thread) так и с помощью асинхронных функций (std::async). Способ параллелизма должен определяться с помощью ExecutionPolicy классов (наподобие как это сделано в stl). Определение количества потоков выполнения и асинхронных функций является деталью реализации. Нижеприведенные сигнатуры функций pmin_element и pmax_element фиксированы и не подлежат изменению."

Во-первых, что значит многопоточность должна быть реализована как с помощью thread, так и с помощью async (хотя async'и то на thread'ах и работают :| ...). Ну как я понимаю это задание, нужно сделать 2 версии одна с thread, а другая с async, хотя сбивает следующая строка.
Во-вторых, что значит способ параллелизма должен определяться с помощью политик выполнения как в стандарте. То есть мне как-то надо самому сделать так, чтобы параллелизм мог быть seq, par, unseq_par, unseq? Я понимаю как сделать первые 2, но как быть с остальным, это уже какая-то векторизация (тема далеко непростая). Или это легко сделать? Хотелось бы тогда пример :3

Заранее благодарю!
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
27.01.2021, 11:38
Ответы с готовыми решениями:

Не могу понять задание
В общем дана выборка, какая особо не важно. Значит, по этой выборке нужно вычислить: \overline {X}\quad {S}_{b}^{2}\quad ...

Не могу понять задание
Здравствуйте. Нужна помощь но даже не по самому С, а вопрос в том что не могу понять что от меня "хотят" в этом задании Что...

Не могу понять задание
Добрый день, стала осваивать Ocaml... Нужно написать код для реализации "вычисления суммы элементов списка с использованием только...

35
 Аватар для HamsterGamer
40 / 29 / 11
Регистрация: 21.06.2019
Сообщений: 201
28.01.2021, 14:49  [ТС]
Студворк — интернет-сервис помощи студентам
oleg-m1973, как-то с atomic не выходит корректно итераторы использовать, не подскажите как сделать? (size_t тут не подходит, так как алгоритм принимает итераторы, а новый контейнер делать как-то не хочется)
Тут как я понимаю происходит гонка, может как-то compare_exchange нужно прикрутить, не знаю что делать :c
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
        std::atomic<ForwardIt> smallest = first;
        std::atomic<ForwardIt> cmp = std::next(first);
        std::vector<std::thread> t_pool(thread_count - 1);
        for (size_t i = 0; i < thread_count - 1; i++){
            t_pool[i] = std::thread([&smallest, &cmp, last]{
                while (cmp.load() != last){
                    auto cur = cmp.load();
                    if (*smallest.load() > *cur){
                        smallest.store(cur);
                    }
                    cmp.store(++cur);
                }
            });
        }
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
28.01.2021, 15:37
Цитата Сообщение от HamsterGamer Посмотреть сообщение
oleg-m1973, как-то с atomic не выходит корректно итераторы использовать, не подскажите как сделать? (size_t тут не подходит, так как алгоритм принимает итераторы, а новый контейнер делать как-то не хочется)
Не надо здесь использовать итераторы. Такой алгоритм будет работать только для массивов, RandomAccessIterator, т.е. достаточно индекса.

Добавлено через 2 минуты
Хотя, наверное можно и для любых итераторов сделать. Но сделай пока хотя бы для массива

Добавлено через 10 минут
Цитата Сообщение от HamsterGamer Посмотреть сообщение
std::atomic<ForwardIt> cmp = std::next(first);
Потому что: next, это не атомарная операция, поэтому придётся использовать мьютекс. И, как результат, твоя многопоточная реализация скорее всего будет работать медленнее, чем однопоточная.
0
 Аватар для HamsterGamer
40 / 29 / 11
Регистрация: 21.06.2019
Сообщений: 201
29.01.2021, 13:28  [ТС]
oleg-m1973, Добрый день, вроде сделал с итератором (при условии конечно что этот алгоритм один работает над структурой и вообще, только читает из нее) (реализовал в 3 constexpr if, то есть там где unseq_par (хотя мб это вообще не тоже самое)):

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
75
76
77
78
template< class ExecutionPolicy, class ForwardIt >
ForwardIt pmin_element( ExecutionPolicy&& policy,
                        ForwardIt first, ForwardIt last ){
    policy_checker(ExecutionPolicy);
    if constexpr (std::is_same_v<typename std::decay<ExecutionPolicy>::type, sequenced_policy>){
        return min_element(first, last);
    } else if constexpr (std::is_same_v<typename std::decay<ExecutionPolicy>::type, parallel_policy>) {
        auto [threads_count, block_size] = tb_count(last - first);
        std::vector<boost::future<ForwardIt>> futures (threads_count);
        auto cur_first = first;
        auto cur_last = first + block_size;
        size_t i = 0;
        for (; i < threads_count - 1; i++){
            futures[i] = boost::async(boost::launch::async, [cur_first, cur_last] { return my_algos::min_element<ForwardIt>(cur_first, cur_last); });
            cur_first = cur_last;
            cur_last += block_size;
        }
        futures[i] = boost::async(boost::launch::async, [cur_first, last] { return my_algos::min_element<ForwardIt>(cur_first, last); });
        return boost::when_all(futures.begin(), futures.end()).then([](boost::future<std::vector<boost::future<ForwardIt>>> ready_results){
            auto result = ready_results.get();
            auto smallest = result.begin()->get();
            for (size_t i = 1; i < result.size(); i++){
                auto el = result[i].get();
                if (*smallest > *el)
                    smallest = el;
            }
            return smallest;
        }).get();
    } else if constexpr(std::is_same_v<typename std::decay<ExecutionPolicy>::type, parallel_unsequenced_policy>){
        auto [thread_count, block_count] = tb_count(last - first);
        std::vector<ForwardIt> smallests(thread_count, first);
        std::atomic<ForwardIt> cmp = std::next(first);
        std::vector<std::thread> t_pool(thread_count - 1);
        auto fun = [&cmp, last](ForwardIt & answer) {
            for (;;) {
                auto cur = cmp.load();
                if (cur == last)
                    break;
                if (*cur < *answer)
                    answer = cur;
                cmp.compare_exchange_weak(cur, std::next(cur));
            }
        };
        size_t i = 0;
        for (; i < thread_count - 1; i++){
            t_pool[i] = std::thread(fun, std::ref(smallests[i]));
        }
        fun(smallests[i]);
        ForwardIt smallest = *smallests.begin();
        for (auto & thread : t_pool)
            thread.join();
        for (size_t j = 0; j < thread_count; j++) {
            if (*smallests[j] < *smallest)
                smallest = smallests[j];
        }
        return smallest;
    } else if constexpr(std::is_same_v<typename std::decay<ExecutionPolicy>::type, unsequenced_policy>){
        auto [threads_count, block_size] = tb_count(last - first);
        std::vector<std::future<ForwardIt>> futures (threads_count);
        auto cur_first = first;
        auto cur_last = first + block_size;
        size_t i = 0;
        for (; i < threads_count - 1; i++){
            futures[i] = std::async(std::launch::deferred, [cur_first, cur_last] { return my_algos::min_element<ForwardIt>(cur_first, cur_last); });
            cur_first = cur_last;
            cur_last += block_size;
        }
        futures[i] = std::async(std::launch::deferred, [cur_first, last] { return my_algos::min_element<ForwardIt>(cur_first, last); });
        ForwardIt smallest = first;
        for (auto & el : futures){
            auto element = el.get();
            if (*smallest > *element){
                smallest = element;
            }
        }
        return smallest;
    }
}
Но появился вопрос, почему это медленнее в сравнении с однопоточным обходом? Набор из 9'999'999 дает такое время:
unseq_par: 1145
seq: 80
Есть вероятность что я где-то серьезно ошибся и он не параллелится, ответы же на всех тестах были валидны.

Других правок не вносил, но учту Ваши рекомендации в дальнейших заданиях!
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
29.01.2021, 13:39
Цитата Сообщение от HamsterGamer Посмотреть сообщение
oleg-m1973, Добрый день, вроде сделал с итератором (при условии конечно что этот алгоритм один работает над структурой и вообще, только читает из нее) (реализовал в 3 constexpr if, то есть там где unseq_par (хотя мб это вообще не тоже самое)):
Ты бы сделал сначала как я показывал, потом извращался с итераторами.

Цитата Сообщение от HamsterGamer Посмотреть сообщение
auto cur = cmp.load();
Так у тебя все потоки будут работать с одним и тем же элементом.

Цитата Сообщение от HamsterGamer Посмотреть сообщение
cmp.compare_exchange_weak(cur, std::next(cur));
А что будет, если compare_exchange_weak не отработает?

Добавлено через 1 минуту
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
const size_t i = idx++;
    if (i >= size)
Это сделано для того, чтобы чтение старого значения индекса и присвоение нового происходило атомарно. Таким образом я гарантирую что потоки будут всегда работать с разными элементами.
0
 Аватар для HamsterGamer
40 / 29 / 11
Регистрация: 21.06.2019
Сообщений: 201
29.01.2021, 13:42  [ТС]
oleg-m1973,
1) я сделал пробный:
C++
1
2
3
4
5
6
7
8
9
10
11
12
    std::atomic<size_t> idx{0};
    size_t answer{0}, answer2{0};
    size_t const size = v.size();
    auto fun = [&idx, &v, size](size_t & answer) {
        for (;;) {
            const size_t i = idx++;
            if (v[i] < v[answer])
                answer = i;
            if (i >= size)
                break;
        }
    };
2) https://en.cppreference.com/w/... tomic/load он возвращает не atomic, так что я работаю с локальным объектом для потока
3) ну оно выполнится так или иначе хотя бы в одном потоке, то есть инкремент точно произойдет, но возможно стоит ее записать внутри while, чтобы каждый поток инкрементил.
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
29.01.2021, 13:44
Цитата Сообщение от HamsterGamer Посмотреть сообщение
) я сделал пробный:
C++
1
2
3
4
5
6
7
8
   for (;;) {
            const size_t i = idx++;
            if (i >= size)
                break;
 
            if (v[i] < v[answer])
                answer = i;
        }
Индекс надо проверять перед тем, как его используешь
1
 Аватар для HamsterGamer
40 / 29 / 11
Регистрация: 21.06.2019
Сообщений: 201
29.01.2021, 13:45  [ТС]
oleg-m1973, согласен, в итераторе я это учел, а тут что-то нет
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
29.01.2021, 13:48
Цитата Сообщение от HamsterGamer Посмотреть сообщение
2) https://en.cppreference.com/w/... tomic/load он возвращает не atomic, так что я работаю с локальным объектом для потока
Вот это
Цитата Сообщение от HamsterGamer Посмотреть сообщение
auto cur = cmp.load();
и вот это
Цитата Сообщение от HamsterGamer Посмотреть сообщение
cmp.compare_exchange_weak(cur, std::next(cur));
должно делаться одновременно, атомарно. Иначе cur для всех потоков будет почти всегда одинаковым. Т.е. ты просто в каждом потоке пробежишься по всему массиву. А потом будешь удивляться - а чё так медленно?
0
 Аватар для HamsterGamer
40 / 29 / 11
Регистрация: 21.06.2019
Сообщений: 201
29.01.2021, 13:48  [ТС]
oleg-m1973, еще это забыл к 1)

C++
1
2
3
    std::thread t1(fun, std::ref(answer)), t2(fun, std::ref(answer2));
    t1.join(); t2.join();
    std::cout << ((answer > answer2) ? v[answer2] : v[answer]);
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
29.01.2021, 13:51
Цитата Сообщение от HamsterGamer Посмотреть сообщение
oleg-m1973, еще это забыл к 1)
И что, это всё не работает?
0
 Аватар для HamsterGamer
40 / 29 / 11
Регистрация: 21.06.2019
Сообщений: 201
29.01.2021, 13:52  [ТС]
oleg-m1973, ну с индексом работает, только тоже медленнее чем однопоточный :|
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
29.01.2021, 14:02
Лучший ответ Сообщение было отмечено HamsterGamer как решение

Решение

Цитата Сообщение от HamsterGamer Посмотреть сообщение
oleg-m1973, ну с индексом работает, только тоже медленнее чем однопоточный :|
Но быстрее чем твой вариант?
Это нормально, что медленнее - там накладных расходов просто получается больше, чем на обработку одного элемента.
Во первых, запускай не два потока, а по количеству на процессоров - std::thread::hardware_concurrency()

Добавлено через 2 минуты
Во-вторых, сэмулируй долгую обработку
C++
1
2
3
4
5
6
7
8
9
   for (;;) {
            const size_t i = idx++;
            if (i >= size)
                break;
 
std::this_thread::sleep_for(std::chrono::milliseconds(1));
            if (v[i] < v[answer])
                answer = i;
        }
То же самое добавь в однопоточный вариант. Тогда разница будет.

Добавлено через 3 минуты
Тут производительность зависит от алгоритма. Для разных алгоритмов нужно выбирать разные типы распараллеливания.
1
 Аватар для HamsterGamer
40 / 29 / 11
Регистрация: 21.06.2019
Сообщений: 201
29.01.2021, 14:06  [ТС]
oleg-m1973,
par: 1963
seq: 15461

ну да, скорее операция сравнения тут играет самую важную роль, большое спасибо за помощь. Буду дальше разбираться
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
29.01.2021, 14:11
Цитата Сообщение от HamsterGamer Посмотреть сообщение
ну да, скорее операция сравнения тут играет самую важную роль, большое спасибо за помощь. Буду дальше разбираться
Не сравнения, тормозит вот на этом
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
const size_t i = idx++;
Доступ к атомарной переменной, это нифига не бесплатная операция. А здесь приходится её изменять на каждой итерации. Отсюда и тормоза.

Добавлено через 2 минуты
Можно попробовать вот так
C++
1
const size_t i = idx.fetch_add(1, std::memory_order_release);
должно стать быстрее
1
 Аватар для HamsterGamer
40 / 29 / 11
Регистрация: 21.06.2019
Сообщений: 201
29.01.2021, 14:16  [ТС]
oleg-m1973,
par: 2069
seq: 15542

Вроде бы тоже самое

С итераторами там вообще одинаково с seq :c
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
29.01.2021, 14:20
Цитата Сообщение от HamsterGamer Посмотреть сообщение
Вроде бы тоже самое
Ну, значит здесь особо уже не ускоришь. Там ещё проблема, что потоки обращаются к рядом стоящим элементам массива, соответственно процессорам приходится кэшировать одни и те же участки памяти. В случае с блоками - каждый процессор загружает в кэш свой кусок массива и работает с ним.
В общем, для задачи поиска минимума-максимума лучше работать с блоками, а не с отдельными элементами.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
29.01.2021, 14:20

Не могу понять задание
Доброе время суток. Не могу понять задание, объясните как-нибудь по другому пожалуйста.:D Решать не надо. Даны два массива....

Не могу понять.6 задание

Не могу понять задание
Имеется вот такой метод. Вот только в толк не возьму, как его реализовать? Я новичок в java. Помогите пожалуйста понять что от меня...

Не могу понять 2 задание
задачи1 Настройте VLAN как на схеме; Выделите телефон в голосовой VLAN и сделайте его приоритетным; Файл с выполненной работой...

Не могу понять задание.
Определить класс - &quot;Комплексное число&quot; в виде модуля и аргумента комплексного числа. Составить пользовательскую функцию, которая...


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

Или воспользуйтесь поиском по форуму:
36
Ответ Создать тему
Новые блоги и статьи
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F
Argus19 02.09.2026
Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru