В мультикомпьютере каждый процессор имеет собственный набор процессов. Поэтому планирование процессов для мультикомпьютера сводится к двум следующим задачам:
Последняя задача состоит в поиске такого распределения процессов по процессорам, при котором эффективность системы максимальна. Обычно в операционных системах эта задача решается как задача балансировки загрузки.
Алгоритм балансировки загрузки, инициируемой отправителем.
Алгоритм балансировки загрузки, инициируемой отправителем, требует оценки текущей загрузки каждого из процессоров мультикомпьютера. Текущая загрузка процессора может оцениваться по количеству процессов, выполняемых на этом процессоре, суммарной вычислительной сложности этих процессов и пр.
Схема алгоритма имеет следующий вид (см. рис. 1).
  1. Если у процессора появляется новый процесс, то этот процессор проверяет свою текущую загрузку.
  2. Если текущая загрузка процессора выше некоторой заданной загрузки, то процессор случайным образом выбирает другой процессор и посылает ему запрос.
  3. Если загрузка процессора меньше некоторой заданной загрузки, то процессор посылает этому процессору свой новый процесс.
  4. Если процессор также перегружен, то процессор выбирает другой процессор (опять же случайным образом). И т.д.
В случае, когда все или большинство процессоров мультикомпьютера перегружены, они будут в соответствии с этим алгоритмом постоянно посылать в коммуникационную сеть запросы. При этом загрузку удастся уменьшить немногим из них, но сеть может оказаться перегруженной.
Рис. 1.  К алгоритму балансировки загрузки, инициируемой отправителем. Загрузка процессора Pi (отправителя) выше максимально допустимой загрузки, а загрузка процессора Pj - ниже минимально допустимой загрузки. Процессор Pi передает процессору Pj процесс Qf.
Алгоритм балансировки загрузки, инициируемой получателем.
Схема алгоритма балансировки загрузки, инициируемой получателем, имеет следующий вид (см. рис. 2).
  1. Если процессор завершает выполнение некоторого процесса, то этот процессор проверяет свою текущую загрузку.
  2. Если текущая загрузка процессора ниже некоторой заданной загрузки, то процессор случайным образом выбирает другой процессор и посылает ему запрос.
  3. Если загрузка процессора больше некоторой заданной величины, то процессор посылает процессору один из своих процессов (на Рис.2 - процесс Qd).
  4. Если процессор также недогружен, то процессор выбирает другой процессор (опять же случайным образом). И.т.д.
Преимущество данного алгоритма состоит в том, что он не оказывает дополнительную нагрузку на коммуникационную сеть в момент, когда мультикомпьютер перегружен. Очевидно, что в случае, когда почти все процессоры мультикомпьютера простаивают, данный алгоритм создает существенную нагрузку на коммуникационную сеть. Однако, поскольку система недогружена, эта нагрузка не слишком обременительна.
Рис. 2.  К алгоритму балансировки загрузки, инициируемой получателем.
Иерархический графовый алгоритм балансировки загрузки.
Как отмечалось, задачу балансировки можно поставить как задачу разрезания графа на (по числу процессоров в системе) непересекающихся подмножеств так, чтобы суммы весов узлов в каждом подмножестве были приблизительно равны, а сумма весов ребер, которые инцидентны узлам из разных подмножеств, была минимальна. Известно несколько алгоритмов приближенного решения этой задачи, наиболее известными из которых являются иерархический алгоритм и спектральный алгоритм.
Иерархический графовый алгоритм балансировки загрузки достаточно хорошо зарекомендовал себя для графов большого размера. В соответствии с этим алгоритмом разрезание графа на подграфы осуществляется в три этапа:

Рекурсивное огрубление графа.
В процессе рекурсивного огрубления графа строится последовательность графов меньшего размера. При этом в графе выделяется некоторое количество подмножеств узлов и узлы каждого из этих подмножеств стягиваются в один мультиузел графа (см. рис. 3). Вес мультиузла принимается равным сумме весов входящих в него узлов. Аналогично в мультиребра графа стягиваются ребра графа . Вес мультиребра определяется путем суммирования весов соответствующих ребер графа . Из графа по той же схеме получается граф и т.д. до достижения приемлемого размера графа.
Для формирования подмножеств, узлы которых стягиваются в один мультиузел, используется два подхода:
первом подходе мультиузел получается путем стягивания смежных узлов. Формально идея этого подхода обычно формулируется в терминах паросочетаний - наборов ребер графа и инцидентных им вершин, в котором любые два ребра не инцидентны общему узлу. Граф, огрубленный с использованием паросочетаний, сохраняет многие свойства первоначального графа. Например, если граф планарен, то граф также планарен. Достаточно эффективным алгоритмом формирования паросочетаний является алгоритм случайных паросочетаний: если мультиузел не включен ни в одно из паросочетаний, то случайным образом выбирается один из его смежных мультиузлов и мультиребро включается в паросочетание. В качестве мультиузла может также выбираться узел с максимальным весом мультиребра (алгоритм паросочетаний из тяжелых ребер).
Рис. 3.  К огрублению графа. 1- 5 – мультиузлы.
втором подходе в мультиузлы стягиваются группы сильно связанных узлов (с высоким уровнем внутригруппового трафика), которые слабо взаимодействуют с другими группами узлов (низкий межгрупповой трафик). Для выделения таких групп используются различные эвристические алгоритмы, например, алгоритм паросочетаний из тяжелых клик. Напомним, что кликой графа называется его полный подграф, а полным графом называется неориентированный граф, все вершины которого смежны между собой. В качестве меры близости графа к клике можно использовать реберную плотность графа , где - количество вершин графа, а - количество его дуг. Если граф близок к клике, то его реберная плотность блика к единице, в противном случае – реберная плотность близка к нулю. Заметим, что величина представляет собой ни что иное, как общее количество дуг в полном графе (клике) с вершинами. В алгоритме паросочетаний из тяжелых клик паросочетание образуется свободным мультиузлом и тем из его смежных мультиузлов , который обеспечивает максимальную реберную плотность мультиузла, полученного объединением мультиузлов , .

Рекурсивная бисекция огрубленного графа.
На втором этапе иерархического графового алгоритма балансировки загрузки выполняется рекурсивное деление пополам графа, полученного на первом этапе алгоритма. Деление выполняется таким образом, чтобы каждая из частей содержала примерно половину узлового веса первоначального графа.
Бисекция графа может быть выполнена с использованием различных алгоритмов:
Поисковый алгоритм. Идея поискового алгоритма бисекции графа состоит в следующем: задается некоторое исходное разбиение графа на два подграфа; итерационно делается попытка перенести один или несколько узлов из одного подграфа в другой так, чтобы уменьшить критерий оптимальности разбиения. В качестве критерия оптимальности целесообразно использовать суммарный объем обменов между подграфами при условии, что суммарные вычислительные сложности подграфов примерно равны. Поскольку данный критерий оптимальности является многоэкстремальным, результирующее разбиение графа сильно зависит от исходного приближения. Поэтому обычно приходится решать задачу многократно – для некоторого количества случайных исходных разбиений (по некоторым оценкам достаточно ~10 разбиений).
Алгоритм бисекции путем наращивания. Другой простой путь деления графа пополам состоит использовании алгоритма бисекции графа путем наращивания. Идея алгоритма состоит в том, чтобы начать с одного узла и наращивать область вокруг этого первого узла до тех пор, пока не будет получено два удовлетворительных (с точки зрения выбранного критерия оптимальности) подграфа. Данный алгоритм чувствителен к выбору узла, с которого начинается рост графа. Поэтому, как и в предыдущем алгоритме, приходится решать задачу многократно – для некоторого количества случайных исходных узлов.

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

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