Алгоритм уплотнения загрузки процессоров

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

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

.

где T — заданное время выполнения задачи, — множество времен окончания выполнения нитей, — множество времен начала выполнения нитей, .

Будем последовательно формировать все возможные комбинации компоновки нитей и рассчитывать для каждой такой комбинации значение критерия, минимальное значение критерия будет соответствовать оптимальной комбинации. Комбинации будем формировать в естественном лексикографическом порядке, то есть следующим образом:. Также следует помнить, что времена выполнения нитей не должны пересекаться, для упрощения проверки этого условия перед началом уплотнения отсортируем нити в порядке не убывания времен начала выполнения, и, в дальнейшем будем проверять условие .

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