Алгоритм Дейкстры – Шолтена
(Перенаправлено из алгоритма Дейкстры-Шолтена )
Алгоритм Дейкстры-Шолтена (названный в честь Эдсгера В. Дейкстры и Карела С. Шолтена ) — это алгоритм обнаружения завершения в распределенной системе . [1] [2] Алгоритм был предложен Дейкстрой и Шолтеном в 1980 году. [3]
Сначала рассмотрим случай простого графа процесса , который представляет собой дерево . Распределенные вычисления с древовидной структурой не являются редкостью. Такой граф процесса может возникнуть, когда вычисления строго относятся к типу «разделяй и властвуй» . Узел . начинает вычисление и делит задачу на две (или более, обычно кратные 2) примерно равные части и распределяет эти части по другим процессорам Этот процесс продолжается рекурсивно до тех пор, пока проблемы не станут достаточно маленькими, чтобы их можно было решить на одном процессоре.
Алгоритм
[ редактировать ]Алгоритм Дейкстры-Шолтена представляет собой древовидный алгоритм, который можно описать следующим образом:
- Инициатором вычисления является корень дерева.
- При получении вычислительного сообщения:
- Если принимающий процесс в данный момент не участвует в вычислениях: процесс присоединяется к дереву, становясь дочерним по отношению к отправителю сообщения. (На этом этапе сообщение подтверждения не отправляется.)
- Если принимающий процесс уже участвует в вычислении: процесс немедленно отправляет сообщение подтверждения отправителю сообщения.
- Когда у процесса больше нет дочерних элементов и он простаивает, процесс отделяется от дерева, отправляя сообщение подтверждения своему родителю дерева.
- Завершение происходит, когда у инициатора нет детей и он стал бездействующим.
Алгоритм Дейкстры – Шолтена для дерева
[ редактировать ]- Для дерева легко обнаружить завершение. Когда листовой процесс определяет, что он завершился, он отправляет сигнал своему родителю. Как правило, процесс ожидает, пока все его дочерние элементы отправят сигналы, а затем отправляет сигнал своему родителю.
- Программа завершается, когда корень получает сигналы от всех своих дочерних элементов.
Алгоритм Дейкстры – Шолтена для ориентированных ациклических графов
[ редактировать ]- Алгоритм для дерева можно распространить на ациклические ориентированные графы. К каждому ребру добавляем дополнительный целочисленный атрибут Дефицит.
- На входящем фронте Дефицит будет обозначать разницу между количеством полученных сообщений и количеством сигналов, отправленных в ответ.
- Когда узел желает завершить работу, он ждет, пока не получит сигналы от исходящих ребер, сводя их дефицит к нулю.
- Затем он отправляет достаточно сигналов, чтобы гарантировать, что дефицит равен нулю на каждом входящем фронте.
- Поскольку граф является ациклическим, некоторые узлы не будут иметь исходящих ребер, и эти узлы завершатся первыми после отправки достаточного количества сигналов на свои входящие ребра. После этого узлы на более высоких уровнях завершат свою работу уровень за уровнем.
Алгоритм Дейкстры – Шолтена для циклических ориентированных графов
[ редактировать ]- Если циклы разрешены, предыдущий алгоритм не работает. Это связано с тем, что не может быть узла с нулевыми исходящими ребрами. Таким образом, потенциально не существует узла, который мог бы завершить работу без консультации с другими узлами.
- Алгоритм Дейкстры-Шолтена решает эту проблему, неявно создавая остовное дерево графа. Связующее дерево — это дерево, которое включает в себя каждый узел базового графа один раз, а набор ребер является подмножеством исходного набора ребер.
- Дерево будет направлено (т. е. каналы будут направлены) с исходным узлом (который инициирует вычисление) в качестве корня.
- Связующее дерево создается следующим образом. переменная First_Edge К каждому узлу добавляется . Когда узел получает сообщение в первый раз, он инициализирует First_Edge ребром, через который он получил сообщение. First_Edge впоследствии никогда не изменяется. Обратите внимание, что связующее дерево не уникально и зависит от порядка сообщений в системе.
- Завершение обрабатывается каждым узлом в три этапа:
- Отправьте сигналы на все входящие фронты, кроме первого. (Каждый узел будет отправлять сигналы, которые уменьшают дефицит на каждом входящем ребре до нуля.)
- Дождитесь сигналов со всех исходящих фронтов. (Количество сигналов, полученных на каждом исходящем фронте, должно свести каждый из их дефицитов к нулю.)
- Отправляйте сигналы на First_Edge . (После завершения шагов 1 и 2 узел информирует своего родителя в связующем дереве о своем намерении завершить работу.)
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Гош, Сукумар (2010), «9.3.1 Алгоритм Дейкстры – Шолтена», Распределенные системы: алгоритмический подход , CRC Press, стр. 140–143, ISBN 9781420010848 .
- ^ Фоккинк, Ван (2013), «6.1 Алгоритм Дейкстры – Шолтена», Распределенные алгоритмы: интуитивный подход , MIT Press, стр. 38–39, ISBN 9780262318952 .
- ^ Дейкстра, Эдсгер В.; Схолтен, К.С. (1980), «Обнаружение завершения для диффузных вычислений» (PDF) , Information Processing Letters , 11 (1): 1–4, doi : 10.1016/0020-0190(80)90021-6 , MR 0585394 .
