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

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

27.01.2021, 11:38. Показов 5725. Ответов 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
Ответ Создать тему
Новые блоги и статьи
Из невошедшего на форум (диалог с ИИ-гугла)
zorxor 29.07.2026
А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .
Был праздник вчера, а я и не знал.
kumehtar 28.07.2026
27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:
Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему
Hrethgir 27.07.2026
То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .
тв 16 бой ии
anaschu 27.07.2026
Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк
anaschu 27.07.2026
НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .
Очистка реквизитов и табличных частей документа при копировании (вариант 2)
Maks 26.07.2026
Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .
Доктрина интенционального знания - Доктрина для портала "Срез".
Hrethgir 25.07.2026
Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых
anaschu 25.07.2026
Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru