Что такое чистый способ перехода от параллельной к последовательной оценке?

Question

В алгоритме разделяй и властвуй, это имеет смысл, чтобы отправить разделенные проблемные части на отдельные потоки, если

1. Каждая часть является достаточно большим и
2. Там не очень много потоков работает пока.

Простой пример: при сортировке слияния, учитывая список элементов 50 000 000, имеет смысл отправить первую половину в один поток, а второй в другую и так далее несколько раз, но в какой-то момент (возможно, после не более четырех разрывов на типичном ПК, я бы мог предположить), накладные накладные расходы обгоняют любые выгоды. Каков наилучший способ написать код, чтобы сделать переход от разделения потоков, чтобы не делать этого?

Answer 1

«имеет смысл отправить первую половину в одну нить, а вторую в другую» - нет, поскольку точное время каждой нити может меняться. В результате один поток заканчивается, а второй продолжается один, что уменьшает параллелизм.

Так требования:

1. Каждая часть достаточно велика, и есть многие из них, чтобы сохранить баланс полезной нагрузки процессора

2. Там не очень много потоков работают еще, потому что многие потоки только потребляют память и не улучшают производительность.

В результате количество кусков работы! = Количество нитей. Это означает, что необходимо использовать пул потоков. Разделение на куски не зависит от выбора размера пула потоков. Чем больше кусок, тем меньше переключение, но меньше балансировки. Как правило, должно быть> 100 штук, каждый из которых выполняется от 1 до 1000 миллисекунд. Сторона пула потоков - это количество доступных процессоров, умноженное на некоторый коэффициент, если работает I/O.

Answer 2

Проблема, с которой вы сталкиваетесь, может быть решена с использованием платформы виджета/объединения Java. Here is an example. ForkJoinPool не будет генерировать много потоков, а скорее повторно использовать их, пока некоторые ждут. FJP был создан именно для решения проблем с разделом и конъюнктурой.