Как называется шаблон параллельных вычислений?

Question

[Safary1094]

Имеется задача, состоящая из подзадач разной сложности. Хочется решать эти подзадачи параллельно.

Пусть имеется итератор подзадач. Нужно сделать так, чтобы когда один процессор завершает свою подзадачу, ему тут же выдается следующая. При этом процессор не ориентируется на остальные процессоры. И так, пока не будет решена вся задача целиком.

Как НЕ нужно: выдаем четырем процессорам по одной подзадаче. Ждем пока все подзадачи будут решены. После этого каждый процессор снова получает подзадачу.

Как это называется по-умному. Где об этом можно почитать?

Мое предположение:
пусть у нас 100500 подзадач. Создадим для каждой подзадачи поток. И пусть операционная система сама разруливает эти потоки. Ждем когда все потоки завершатся.

Comments

[Perzh]

если я правильно понял, то Вам подойдет ThreadPool

Answer 1

[Владимир Мартьянов]

Это и называется "параллельные вычисления".

Comments

[Safary1094]

Замечательно. Как это реализовать? Допустим, у меня четырехядерный процессор. Я хочу, чтобы у меня работало одновременно четыре потока. Как только какой-то из них завершается, сразу же создается новый с новой подзадачей.

На сайте cplusplus.com предлагают создать сразу много потоков на весь размер задачи (например, 10). А потом ждать когда все завершатся.

www.cplusplus.com/reference/thread/thread/thread

А можно как-нибудь сделать, чтобы работало только четыре потока? Или это неэффективно?
Конкретно моя задача состоит примерно из 20-40 подзадач.

[Владимир Мартьянов]

Safary1094: Вы можете реализовать именно так, как вы описали: создается 1 поток на каждое ядро, решает задачу, завершается. Создается новый и так далее. Альтернативный подход - не завершать поток, а прямо внутри него получать новое задание. Профайлер и тестирование с пустыми задачами покажут какой вариант в вашей реализации будет лучше. Много потоков - плохо, когда задача начнет состоять из 12 млн кусков будет пичалько.

[Safary1094]

Спасибо за ответ! Реализовал с помощью общей очереди, все работает, как надо!

[Владимир Мартьянов]

Safary1094: Теперь посмотрите в профайлере на пустой очереди и еще на заданиях, которые будут выполняться очень малое время. У меня в первой реализации до 5% времени уходило на поддержку очереди и потоков.

Answer 2

[Александр Рулёв]

1. Создаём общую очередь задач (потокобезопасную, блокирующую/неблокирующую, зависит от шансов коллизий)
   
2. Запускаем сколько нам нужно потоков, которые в цикле берут себе задачу из очереди, обрабатывают её и кладут куда нужно результат (лучше — вызывают коллбек у задачи, который сам решит, что делать с результатом)
   

Comments

[Safary1094]

Спасибо за помощь! Все реализовал, как вы описали, все работает. Было несколько трудностей, но все отладил. Еще раз спасибо!