Алгоритмы решения задачи

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

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

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

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