алгоритм балансировки загрузки, инициируемой отправителем
Схема алгоритма балансировки загрузки, инициируемой отправителем, имеет следующий вид. Если у процессора Pi появляется новый процесс, то этот процессор проверяет свою текущую загрузку. Если текущая загрузка процессора Pi выше некоторой заданной загрузки, то процессор Pi случайным образом выбирает другой процессор Pj и посылает ему запрос. Если загрузка процессора Pj меньше некоторой заданной загрузки, то процессор Pj посылает этому процессору свой новый процесс. Если процессор Pj также перегружен, то процессор Pi выбирает другой процессор (опять же случайным образом). И т.д.
алгоритм балансировки загрузки, инициируемой получателем
Схема алгоритма балансировки загрузки, инициируемой получателем, имеет следующий вид. Если процессор Pi завершает выполнение некоторого процесса, то этот процессор проверяет свою текущую загрузку. Если текущая загрузка процессора Pi ниже некоторой заданной загрузки, то процессор Pi случайным образом выбирает другой процессор Pj и посылает ему запрос. Если загрузка процессора Pj больше некоторой заданной величины, то процессор Pj посылает процессору Pi один из своих процессов. Если процессор Pj также недогружен, то процессор Pi выбирает другой процессор (опять же случайным образом). И.т.д.
иерархический графовый алгоритм балансировки загрузки
Иерархический графовый алгоритм балансировки загрузки - это один из алгоритмов решения задачи балансировки путем разрезания графа задачи на N подграфов (по числу процессоров в системе) так, чтобы суммы весов узлов в каждом подграфе были приблизительно равны, а сумма весов ребер, которые инцидентны узлам из разных подграфов, была минимальна. В соответствии с этим алгоритмом разрезание графа на подграфы осуществляется в три этапа: рекурсивное огрубление графа; рекурсивная бисекция огрубленного графа; восстановление исходного графа.
паросочетание
Паросочетание - это набор ребер графа и инцидентных им вершин, в котором любые два ребра не инцидентны общему узлу графа.
алгоритм случайных паросочетаний
Алгоритм случайных паросочетаний - это достаточно эффективным алгоритмом формирования паросочетаний. Схема алгоритма: если некоторый узел графа (узел 1) не включен ни в одно из паросочетаний, то случайным образом выбирается один из его смежных узлов (узел 2) и ребро, связывающее узлы 1, 2, включается в паросочетание.
алгоритм паросочетаний из тяжелых ребер
Если в алгоритме случайных паросочетаний в качестве узла 2 выбирается узел с максимальным весом ребра, то такой алгоритм называется алгоритмом паросочетаний из тяжелых ребер.
алгоритм паросочетаний из тяжелых клик
Алгоритм паросочетаний из тяжелых клик относится к классу алгоритмов формирования паросочетаний, в которых в мультиузлы стягиваются группы сильно связанных узлов (с высоким уровнем внутригруппового трафика), которые слабо взаимодействуют с другими группами узлов (низкий межгрупповой трафик).
поисковый алгоритм бисекции графа
Идея поискового алгоритма бисекции графа состоит в следующем: задается некоторое исходное разбиение графа на два подграфа; итерационно делается попытка перенести один или несколько узлов из одного подграфа в другой так, чтобы уменьшить критерий оптимальности разбиения. В качестве критерия оптимальности целесообразно использовать суммарный объем обменов между подграфами при условии, что суммарные вычислительные сложности подграфов примерно равны.
алгоритм бисекции графа путем наращивания
Идея алгоритма бисекции графа путем наращивания состоит в том, чтобы начать с одного узла и наращивать область вокруг этого первого узла до тех пор, пока не будет получено два удовлетворительных (с точки зрения выбранного критерия оптимальности) подграфа.