Н.А. Беляков, Б.Е. Винтайкин
10
особенность может быть присуща и любой другой задаче. Поэтому
простая статическая разбивка всего диапазона параметров на одина-
ковые по объему интервалы, число которых равно числу вычисли-
тельных ядер в системе, оказывается неэффективной, и требуется не-
которая динамическая балансировка загрузки ядер. Такую баланси-
ровку (а также предварительную разбивку диапазона параметров,
распределение работы между вычислительными потоками и сбор ре-
зультатов) осуществляет основной компонент модуля М
3
– объект–
планировщик
потоков. Причем любая подобная организация работы
потоков требует их синхронизации, но, как показывает практика, все
издержки окупаются за счет более полной загрузки вычислительных
ядер системы.
Один из способов такой балансировки – поделить всю задачу на
достаточно мелкие части –
порции
(в пределе – на атомарные порции)
и выдавать эти порции потокам по мере необходимости. На началь-
ном этапе отдать каждому потоку по порции задачи и при заверше-
нии каждого потока выдавать ему следующую порцию из общего
«набора порций» задачи, пока порции не закончатся (поток должен
как-то сообщить планировщику о своем завершении). Под такой
порцией в данном случае подразумевается некоторое число значений
вектора параметров
p
задачи из заданного диапазона (очевидно, что
атомарная порция – одно значение). Но возникает вопрос: насколько
большими должны быть эти порции? Если они слишком большие, то
это приведет к неравномерности загрузки потоков. Слишком малень-
кие порции (в пределе – атомарные) приведут к равномерной загруз-
ке, но потребуют дополнительных затрат, прежде всего на организа-
цию последовательного доступа к общему «набору порций» и другие
синхронизации: в схеме появится слишком много вынужденных по-
следовательных участков, что в соответствии с законом Амдала [9]
приведет к снижению эффективности параллельной программы.
Кроме того, при слишком маленьких порциях появляется и другая
«статья дополнительных расходов»: возможная необходимость ча-
стого создания потоков выполнения (как сущностей ОС). Хотя по-
токи для своего создания требуют значительно меньше ресурсов,
чем процессы, тем не менее слишком частое их создание может
привести к снижению производительности (особенно это касается
потоков уровня ядра, с которыми взаимодействует системный пла-
нировщик ОС в вытесняющем режиме – именно такие потоки рас-
сматриваются в данной работе). Хотелось бы иметь схему планиро-
вания с динамической балансировкой загрузки, сочетающую досто-
инства статического разбиения задачи (редкое создание потоков ОС,
минимум синхронизаций) и динамической схемы с очень малыми
порциями (равномерная высокая загрузка потоков) и сводящую к не-
которому минимуму их недостатки.
