Рис. 30.3 30.3. Работа алгоритма LlST-PREFIX. (а). Вначале для k-го объекта значение у равно [к, к], а указатель next[k] указывает на (& + 1)-й объект (указатель последнего - на NIL), (b)-(d). Значения у и next после каждого выполнения цикла while (строки 3-6). В конце алгоритма (d) для к-ого объекта значение у равно [1, к].

равны nil), а к-ъ по списку элемент хранит значение [тах(1,А; - 2* + 1),к] для к = 1,2,... , га. Перед первым выполнением цикла (t = 0) каждый объект (кроме последнего) указывает на следующий. В строке 6 алгоритма к-ъ элемент (точнее, отвечающий за него процессор) вычисляет значение [к, /г+1] = [к, к] <g> [к + 1, к + 1], которое передаётся (к + 1)-му элементу. Указатели меняются так же, как и в алгоритме List-Rank. Состояние списка после первого выполнения цикла показано на рис. 30.3 (Ь). При втором выполнении цикла к-ъ элемент (при к = 2, 3,... , га - 2) вычисляет значение [к - 1, к + 2] = [к - 1, к] <g> [к + 1, к + 2], которое передаётся к + 2-му элементу; результат показан на рис. 30.3 (с). Наконец, в ходе третьего (последнего) выполнения цикла оставшиеся два элемента вычисляют нужные значения (рис. 30-3 (d)).

Как и предыдущий алгоритм, алгоритм List-Prefix работает за время О (lgra), а общие затраты составляют О (га lgra).

30.1.5. Метод эйлерова цикла

В этом разделе рассмотрен метод эйлерова цикла и его использование в задаче вычисления глубины вершин двоичного дерева. Если дерево имеет га вершин, то вычисление их глубин займёт время О (lgra); при этом будет использована техника параллельной обработки префиксов.

Дерево хранится в памяти так, как описано в разделе 11.4: каждая вершина i имеет поля parent[i] (родитель), left[i] (левый ребёнок) и right[i] (правый ребёнок).

Имея один процессор, можно вычислить глубину всех вершин дерева с га вершинами за время О (га). Как сократить это время, используя несколько процессоров? Простейший параллельный алгоритм состоит в движении от корня дерева к листьям с увеличением счётчика глубины. При этом вершина глубины к достигается в момент времени к, так что время работы пропорционально высоте дерева. Для полного дерева этот алгоритм требует логарифмического времени, но бывают деревья, у которых высота равна п - 1. Метод эйлерова цикла, который мы сейчас изложим, позволяет обработать любое дерево с га вершинами за время 0(lg га) (независимо от его высоты).

Эйлеровым циклом в графе называется путь, проходящий ровно один раз по каждому ребру (вершины могут проходиться мно-

Рис. 30.4 30.4. Использование метода эйлерова цикла для вычисления глубины вершин двоичного дерева, (а) Эйлерову циклу (обходу дерева) соответствует список. Каждый процессор хранит число, которое используется при параллельном вычислении префиксов. (Ь) Результат вычисления префиксов для дерева на рисунке (а). С-процессор каждой вершины (зачернённый) содержит её глубину.

гократно). Согласно задаче 23-2, связный ориентированный граф имеет эйлеров цикл в том и только в том случае, когда у каждой вершины входная и выходная степени совпадают. Если превратить связный неориентированный граф в ориентированный, заменив каждое ребро двумя противонаправленными, то такой граф, очевидно, будет иметь эйлеров цикл.

Пусть Г - двоичное дерево. Будем предполагать, что его вершины занумерованы неотрицательными целыми числами. С каждой вершиной мы связываем три процессора А, В ж С] узлу с номером г соответствуют процессоры с номерами Зг, Зг + 1 и Зг + 2. Рассмотрим ориентированный вариант дерева (с удвоенными рёбрами). Эйлеров цикл (или обход дерева) можно превратить в список (см. рис. 30.4(a)):

•А-процессор вершины указывает на А-процессор левого ребёнка, если он есть, а иначе на 5-процессор той же вершины.

•5-процессор вершины указывает на А-процессор правого ребёнка, если он есть, а иначе на С-процессор той же вершины.

•С-процессор вершины указывает на 5-процессор родителя, если это левый ребёнок, и на С-процессор родителя, если это правый ребёнок. С-процессор корневой вершины указывает на NIL.

Таким образом, список начинается в А-процессоре корневой вершины и заканчивается в её С-процессоре. Этот список может быть построен по данному дереву за время 0(1).

Глубину каждой вершины можно подсчитать как сумму изменений глубин по пути к ней (по эйлеровому циклу). Более формально, пусть в каждом А-процессоре находится число 1, в каждом В-процессоре - число 0, а в каждом С-процессоре - число ( - 1). Произведём параллельное вычисление префиксов, используя в качестве операции обычное сложение. Его результат для дерева рис. 30.4(a) показан на рис. 30.4(b).

После этого С-процессор каждой вершины будет содержать её глубину, а А- и 5-процессоры - на единицу большее значение. Это можно проверить, двигаясь вдоль эйлерова цикла. В самом деле, к А-процессору ведёт стрелка вниз по дереву с началом в А- или 5-процессоре родителя; к 5-процессору ведёт либо стрелка вверх из С-процессора левого потомка, либо стрелка из А-процессора той же вершины; к С-процессору ведёт либо стрелка вверх из С-процессора правого потомка, либо стрелка из 5-процессора той

же вершины; во всех случаях наше утверждение остаётся верным.

Создание списка занимает время 0(1), а параллельная обработка префиксов - время 0(lg3ra), т. е. О (lgra). Таким образом, общее время работы составляет О (lgra). Поскольку параллельная обработка префиксов не требует одновременного доступа к памяти, алгоритм может быть реализован на EREW-машине.

Упражнения

30.1-1. Укажите EREW-алгоритм, который для каждого элемента га-элементного списка определяет, является ли он средним ( га/2 -м), за время O(lgra).

30.1-2. Постройте EREW-алгоритм для обработки префиксов массива х[1.. .га] за время О (lgra). (Можно обойтись без указателей)

30.1-3. Пусть в списке L имеются объекты двух разных типов (некоторые красные, а остальные синие). Укажите эффективный EREW-алгоритм, формирующий из этого списка два: один из синих объектов, а другой из красных (с сохранением взаимного расположения).

30.1-4. Пусть имеется несколько непересекающихся кольцевых списков, содержащих в совокупности га элементов. Укажите эффективный EREW-алгоритм, который выбирает по одному представителю из каждого списка и сообщает каждому элементу, кто является представителем его списка. (Считается, что процессоры занумерованы и каждому процессору известен его собственный номер.)

30.1-5. Найдите EREW-алгоритм, который за время 0(lg га) определяет для каждой вершины размер поддерева с корнем в этой вершине. (Указание: следует взять разность двух префиксов суммы вдоль эйлерова цикла).

30.1-6. Вершины дерева можно нумеровать в разном порядке. Рассмотрим три способа: корень - левое поддерево - правое поддерево (preorder); левое поддерево - корень - правое поддерево (inorder); левое поддерево - правое поддерево - корень (pos-torder). Укажите для каждого из способов алгоритм, вычисляющий номера всех вершин.

30.1-7. Распространите метод эйлерова цикла на деревья с произвольной степенью вершин (выбрав подходящее представление дерева). Постройте алгоритм, вычисляющий глубину всех га вершин дерева (в этом представлении) за время О (lgra).

30.1-8. Измените алгоритм List-Rank так, чтобы проверка условия окончания цикла производилась явно (без использования управляющей сети), сохранив оценку на работы. (Указание: следите за первым элементом списка).