and testch p = udef then
begin state p := found ; send á report, bestwt p ) to father p end
end
(9) При получении á report, w ñ от g:
begin if q¹ father p
then (* reply for initiate message *)
begin if w < bestwt p then
begin bestwt p := w ; bestch p := q end ;
rec p := rec p + 1 ; report
else (* pq является основным ребром *)
if state p = find
then обработать это сообщение позже
else if w > bestwt p then changeroot
else if w = bestwt p = ¥ then stop
(10) procedure changeroot;
begin if stach p [bestch p] = branch
then send á changeroot ñ to bestch p
else begin send á connect, level p ñ to bestch p ;
stach p [bestch p] := branch
(11) При получении áchangerootñ:
begin changeroot end
Алгоритм 7.12 gallager-humblet-spira алгоритм (часть 3).
Затем рассмотрите случай, когда новый фрагмент сформирован, объединяя два фрагмента, соединяя их ребром e = pq. Если два объединенных фрагмента имели одинаковый уровень, L, p и q пошлют сообщение á connect, 1ñ через e, и получат в ответ сообщение á connect, Lñ , в то время как статус e - branch, см. действие (2). Ребро pq становится основным ребром фрагмента, p и q обменивают сообщением áinitiate, L + 1, N, S ñ, присваивая новый уровень и имя фрагменту. Имя - w (pq), и статус find приводит к тому, что каждый процесс начинает искать исходящее ребро с наименьшим весом; см. действие (3). Сообщение á initiate, L + 1, N, Sñ посылается каждому узлу в новом фрагменте. Если уровень p был меньше чем уровень q, p пошлет сообщение á connect, L ñ через e, и получит сообщение (initiate, L' , N, S ñ в ответ от q; см. действие (2). В этом случае, L ' и N - текущий уровень и имя фрагмента q, а имя и уровень узлов на стороне q ребра не изменяется. На стороне p ребра сообщение инициализации отправляется к всем узлам (см. действие (3)), заставляя каждый процесс изменять имя фрагмента и уровень. Если q в настоящее время ищет исходящее ребро с наименьшим весом (S = find) процессы во фрагменте p присоединяются к поиску с помощью вызова test.
Каждый процесс во фрагменте осуществляет поиск по все его ребрам (если такие существуют, см. (4), (5), (6), и (7)) для того, что определить имеются ли ребра выходящие из фрагмента, и если такие есть, выбирает наименьшее по весу. Исходящее ребро с наименьшим весом сообщается всем поддеревьям, с помощью сообщения áreport, wñ; см. (8). Узел p подсчитывает число сообщений áreport, wñ, которые получает, используя переменную recp, которой присваивается значение 0 при начале поиска (см. (3)) и увеличивается на единицу при получении сообщения áreport, wñ; см. (9). Каждый процесс посылает сообщение áreport, wñ отцу, когда он получает такое сообщение от каждого из своих сыновей и заканчивает локальный поиск исходящего ребра.
Сообщения áreport, wñ посылаются по направлению к основному ребру каждым процессом, и сообщения двух основных узлов пересекаются на ребре; оба получают сообщение от их отца; см. (9). Каждый основной узел ждет, пока он не пошлет сообщение áreport, wñ сам пока он обрабатывает сообщение другого процесса. Когда два сообщения áreport, wñ основных узлов пересеклись, основные узлы знают вес наименьшего исходящего ребра. Алгоритм закончился бы в этом точке, если никакое исходящее ребро не было бы передано (оба сообщения передают значения ¥).
Если исходящее ребро было передано, лучшее ребро находится следуя указателям bestch в каждом узле, начиная с основного узла той стороны, с которой было передано лучшее ребро. Сообщение á connect, L ñ должно быть послано через это ребро, и все указатели отца во фрагменте должны указать в этом направлении; это выполняется с помощью посылки сообщения á changeroot ñ. Основной узел, на чьей стороне расположено исходящее ребро с наименьшим весом, посылает сообщение á changeroot ñ, которое посылается через дерево к исходящему ребру с наименьшим весом; см. (10) и (11). Когда сообщение á changeroot ñ достигает узла инцидентнорго исходящему ребру с наименьшим весом , этот узел посылает сообщениеáconnect ,Lñ через исходящее ребро с наименьшим весом.
Проверка граней. Для нахождения наименьшего исходящего ребра узел p осматривает основные ребра одно за другим в порядке увеличения веса; см. (4). Локальный поиск ребра заканчивается когда либо не остается ребер(все грани - reject или branch ), см. (4), либо один край идентифицирован как исходящий; см. (6). Из-за порядка, в котором p осматривает грани, если p опознает одно ребро как исходящее, оно должно иметь наименьший вес.
Для осметра ребра pq, p посылает сообщение á test, levelp, namep ñ к q и ждет ответ, который может сообщениями á reject ñ, á accept ñ или á test, L, F ñ . Сообщение áreject ñ, посылается процессом q (см. (5)) если q обнаруживает, что имя фрагмента p, как в сообщении test, совпадает с именем фрагмента q; узел q также отклоняет ребро в этом случае. При получении сообщения á reject ñ p отклоняет ребро pq и продолжает локальный поиск; см. (7). Сообщение á reject ñ пропускается, если ребро pq только что использовалось q также, чтобы послать сообщение á test,L,Fñ; в этом случае сообщение á test, L, F ñ от q служит как ответ на сообщение p; см. (5). Если имя фрагмента q отличается от p, посылается сообщение á accept ñ. По получении этого сообщения p заканчивает локальный поиск исходящих ребер ребром pq как лучшим локальным выбором; см. (6).
Обработка сообщения á test, L, F ñ p отсрочена если L> levelp. Причина - то, что p и q может фактически принадлежать одному и тому же фрагменту, но сообщение áinitiate, L, F, S ñ еще не достиг p. Узел p мог бы ошибочно отвечать q сообщением á accept ñ .
Объединение фрагментов. После того как исходящее ребро с наименьшим весом фрагмента F = (name, level) было определено, сообщение áconnect, levelñ посылается через это ребро, и получается узлом, принадлежащим к фрагменту F ' - = (name', level'). Назовем процесс, посылающий сообщение áconnect, levelñ p и процесс, получающий его q. Узел q ранее послал сообщение áacceptñ к p в ответ на сообщение á test, level, nameñ, потому что поиск лучшего исходящегоребра во фрагменте p закончился. Ожидание, организованное перед ответом на сообщения test (см. (5)) дает level' £ level.
Согласно правилам объединения, обсужденным ранее, ответ áconnect, levelñ на сообщение áinitiate, L, F, S ñ имеет местов двух случаях.
Случай A: если level' > level, фрагмент p поглощается; узлам в этом фрагменте сообщается новое имя фрагмента и уровень с помощью сообщения á initiate, level', name', S ñ, которое отправляется всем узлам во фрагменте F. Полный поглощенный фрагмент F становится поддеревом q в дереве охватов фрагмента F ' и если q в настоящее время занят в поиске лучшего исходящего ребра фрагмента F', все процессы в F должны участвовать. Вот почему q включает состояние (find или found) в сообщение á initiate, level', name', S ñ.
Случай B: если два фрагмента имеют один и тот же уровень и лучшее исходящее ребро фрагмента F ' также pq, новый фрагмент формируется с уровнем наимбольшим из двух и именем - вес ребра pq: см. (2). Этот случай происходит, если два уровня равны, и сообщение connect получено через ребро branch : заметьте, что статус ребра становится branch, если сообщение connect послано через него.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
