[Delphinaut]

Имеется алгоритм, который строит бинарное дерево. Требуется распараллелить алгоритм построения. Самый очевидный вариант - строить левое и правое поддеревья в двух разных потоках. Потом объединить поддеревья после того, как оба потока завершат работу (WaitForMultipleObjects).

Но можно же строить и в четыре потока: левое (1) и правое (2) поддеревья левого поддерева, левое (3) и правое (4) поддеревья правого поддерева. И т.д.

Задача. Определить оптимальное кол-во потоков, при котором бинарное дерево строится за наименьшее кол-во времени на 2-х, 4-х и 8-ми ядерных процессорах. Написать рекурсивный алгоритм создания потоков.

Т.е. первоначально имеется один поток (главный), которой создаёт два дочерних потока для построения левого и правого поддеревьев. Затем дочерние потоки поступают точно так же и т.д.

[Delphinaut]

Сам алгоритм вроде бы простой. Но можно насоздавать лишних потоков, которые только замедлят построение из-за сохранения/загрузки контекста потока, если два или несколько потоков программы будут выполняться в одном физическом потоке процессора. Вопрос: когда остановиться? Сколько потоков реально будут выполняться параллельно на современных процессорах?

[AlexSku]

Допустим, у вас 8 ядер. Тогда сколько потоков не создавай, параллельно больше 8 не будет работать. А вот запустить на графическом процессоре (допустим, библиотека CUDA) можно намного больше параллельных потоков. Правда, т.к. центральный процессор быстрее, то выигрыш ощущается только на больших объёмах данных (при этом, естественно, теряется время на перекачку данных CPU <-> GPU)