Алгоритм оптимизации # потоков, используемых при вычислении

Question

Я выполняю операцию, разрешаю ее CalculateSomeData. CalculateSomeData работает в последовательных «поколениях», пронумерованных 1..x. Количество поколений во всем прогоне фиксируется входными параметрами для CalculateSomeData и известно априори. Одно поколение занимает от 30 минут до 2 часов. Некоторая часть этой изменчивости обусловлена ​​входными параметрами и не может контролироваться. Тем не менее, часть этой изменчивости обусловлена ​​такими вещами, как аппаратные возможности, загрузка процессора из других процессов, пропускная способность сети и т. Д. Одним из параметров, который можно контролировать за поколение, является количество потоков, используемых CalculateSomeData. Сейчас это исправлено и, вероятно, неоптимально. Я хотел бы отслеживать время, которое занимает каждое поколение, и затем иметь некоторый алгоритм, с помощью которого я настраиваю количество потоков, чтобы каждое последующее поколение улучшалось по времени вычисления предыдущего поколения (минимизируя время). Какой подход я должен использовать? Насколько применимы генетические алгоритмы? Intuition говорит мне, что диапазон будет довольно жестким - может быть, от 1 до 16 потоков на двухъядерном процессоре с четырьмя ядрами.

любые указатели, псевдокоды и т. Д. Очень ценятся.

Answer 1

Как насчет эволюционного алгоритма.

Начать с предположения. 1 поток на ядро ​​процессора кажется хорошим, но зависит от задачи.

Измерьте среднее время для каждой задачи в генерации. Сравните его со временем, которое было принято предыдущим поколением. (Предположим эффективно бесконечное время и 0 потоков для генерации 0).

Если задачи последнего поколения усреднили лучшее время, чем предыдущее, продолжайте изменять количество потоков в том же направлении, что и последний шаг (так что если в последнем поколении было больше потоков, чем в предыдущем потоке, тогда добавьте поток для нового поколения, но если его было меньше, то используйте меньше (очевидно, с нижним пределом 1 потока).

Если самые последние задачи поколения потребовали больше времени, в среднем, чем предыдущее поколение, затем измените количество потоков в противоположном направлении (так что, если увеличение количества потоков приведет к худшему времени, в следующий раз используйте еще один поток).

Пока оптимальное количество потоков не слишком близко к 1, вы, вероятно, закончите колебание между 3 значениями, которые все достаточно близки к оптимальным. Вы можете явно обнаружить этот случай и заблокировать себя в центральном значении, если у вас есть большое количество поколений.

Answer 2

Если вычисления полностью связаны с ЦП, количество потоков должно быть равно числу ядер на машине. Таким образом вы минимизируете количество переключателей контекста.

Если ваши расчеты связаны с ввода-выводами, сетью, синхронизацией или чем-то еще, что блокирует выполнение, вы должны найти предельный ресурс и измерить использование. Вам нужно следить за использованием и медленно добавлять больше потоков, пока использование не приблизится к 100%. У вас должно быть как можно меньше потоков, чтобы насытить ваш лимитирующий ресурс.

Answer 3

Вы должны разделить свои поколения на множество мелких задач и поставить их в очередь. Создайте один поток на ядро ​​и попросите каждую нить выполнить задачу, запустите ее до завершения и повторите.

Вы хотите, чтобы у вас было больше задач, чем ядер, чтобы убедиться, что вы не закончите с одной задачей, запущенной в конце поколения, и все остальные потоки простаивают. Это то, что может произойти, если вы установите #tasks = #threads = #cores, как предлагает Альбин (если вы не можете гарантировать, что все задачи занимают ровно столько же времени).

Возможно, вы также не хотите больше потоков, чем ядра. Контекстное переключение не очень дорого, но больший объем кеша, который поставляется с одновременным активностью более чем в # часах, может повредить вам (если в ваших задачах не используется очень мало памяти).