Алгоритм обхода тора

Граф вида «тор» представляет собой решетку с дополнительными ребрами, соединяющими вершины из верхнего ряда («строки») решетки с вершинами из нижнего ряда, а также с ребрами, соединяющими вершины из левого ряда («столбца») решетки с вершинами из правого ряда. Таким образом, возникают дополнительные циклы. Каждая вершина тора (в отличие от решетки) имеет степень 4, т.е. граф является регулярным. При стандартном изображении такого графа каждая вершина имеет «левого» соседа, «правого» соседа, «верхнего» соседа, «нижнего» соседа (рис. 26). Тор, построенный на основе решетки m ´ n, содержит mn узлов и 2 mn ребер. Количество ребер можно подсчитать как непосредственно, так и на основе известной теоремы теории графов: «сумма степеней узлов равна удвоенному числу ребер».

Рис. 26. Тор 3 ´ 5. Ребра различных направлений.

Из-за его регулярных свойств тор или его модификации часто используются в различных архитектурах. Например, одна из первых архитектур многопроцессорных ЭВМ ILLIAC-IV использовала тороподобное соединение процессоров.

Требуется обойти все узлы тора m ´ n (но не все ребра). Инициатором – начальным узлом при обходе может быть любой из узлов. Алгоритм ориентирован на топологию тора, но на сайтах нет глобальной информации о топологии, имеются лишь имена ребер (L, R, U, D), определяющие направления в соответствии с приведенным выше рисунком. Их можно считать локальным знанием о топологии.

Действия инициатора (выполняется один раз):

out (token, 1) through U

Действия процесса каждого сайта при получении маркера (token, k):

begin if k = m*n then return(OK)

else if (k mod n = 0) then out (token, k+1) through U

else out (token, k+1) through R

End

На рис. 27 и 28 показан порядок обхода торов 3 ´ 4 и 2 ´ 5. Звездочкой обозначен сайт – инициатор обхода, а буквами «ОК» – сайт, сообщающий о завершении обхода. Около ребра записано число – значение k, которое передается по этому ребру от одного сайта к другому.

Рис. 27. Порядок обхода тора 3 ´ 4

Рис. 28. Порядок обхода тора 2 ´ 5