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

Question

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

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

Answer 1

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

Начните с догадки. 1 поток на ядро ​​ЦП выглядит неплохо, но зависит от поставленной задачи.

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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