Указатель прыжков - Pointer jumping

Указатель прыжков или же удвоение пути это дизайнерская техника за параллельные алгоритмы которые работают со структурами указателей, такими как связанные списки и ориентированные графы. Переход по указателю позволяет алгоритму следовать по пути с временная сложность что является логарифмическим по отношению к длине самого длинного пути. Он делает это, "перескакивая" в конец пути, вычисленного соседями.

Основная операция перехода по указателю заключается в замене каждого соседа в структуре указателя соседом своего соседа. На каждом шаге алгоритма эта замена выполняется для всех узлов в структуре данных, что может выполняться независимо параллельно. На следующем шаге, когда идет след за соседом, путь соседа, уже пройденный на предыдущем шаге, добавляется к пройденному пути узла за один шаг. Таким образом, каждый шаг фактически удваивает расстояние, пройденное исследованными путями.

Прыжок по указателю лучше всего понять, взглянув на простые примеры, такие как рейтинг списка и поиск корня.

Рейтинг списка

Одной из более простых задач, которую можно решить с помощью алгоритма перехода по указателю, является рейтинг списка проблема. Эта проблема определяется следующим образом: при наличии связанного списка N узлов, найдите расстояние (измеренное в количестве узлов) каждого узла до конца списка. Расстояние d (n) определяется следующим образом, для узлов п которые указывают на своего преемника указателем, называемым следующий:

  • Если n.next является ноль, тогда д (п) = 0.
  • Для любого другого узла d (n) = d (n.next) + 1.

Эта проблема может быть легко решена за линейное время на последовательной машине, но параллельный алгоритм может работать лучше: п процессоров, проблема может быть решена в логарифмическое время, О(бревно N), по следующему алгоритму перехода указателя:[1]:693

  • Выделить массив N целые числа.
  • Инициализировать: для каждого процессора / узла списка п, в параллели:
    • Если n.next = nil, набор d [n] ← 0.
    • В противном случае установите d [n] ← 1.
  • Пока любой узел п имеет n.next ≠ nil:
    • Для каждого процессора / узла списка п, в параллели:
      • Если n.next ≠ nil:
        • Набор d [n] ← d [n] + d [n.next].
        • Набор n.next ← n.next.next.

Переход указателя происходит в последней строке алгоритма, где каждый узел следующий указатель сбрасывается, чтобы пропустить прямого преемника узла. Предполагается, как обычно в PRAM модель вычислений, что доступ к памяти выполняется в блокировке, так что каждый n.next.next выборка из памяти выполняется перед каждым n.next хранилище памяти; в противном случае процессоры могут сбивать данные друг друга, вызывая несогласованность.[1]:694

На следующей диаграмме показано, как алгоритм ранжирования параллельного списка использует переход по указателю для связанного списка из 11 элементов. Как описывает алгоритм, первая итерация начинает инициализироваться со всеми рангами, установленными на 1, кроме тех, у которых нулевой указатель на следующий. Первая итерация смотрит на ближайших соседей. Каждая последующая итерация увеличивается вдвое по сравнению с предыдущей.

Пример выполнения метода параллельного перехода по указателю для вычисления ранжирования списка.

Анализ алгоритма дает логарифмическое время выполнения. Цикл инициализации занимает постоянное время, потому что каждый из N процессоры выполняют постоянный объем работы, причем все параллельно. Внутренний цикл основного цикла также занимает постоянное время, как и (по предположению) проверка завершения цикла, поэтому время выполнения определяется тем, как часто выполняется этот внутренний цикл. Поскольку указатель, прыгающий на каждой итерации, разбивает список на две части, одна из которых состоит из «нечетных» элементов, а другая - из «четных», длина списка, на который указывает каждый процессор п уменьшается вдвое на каждой итерации, что может быть выполнено не более чем О(бревно N) время до того, как каждый список будет иметь длину не более единицы.[1]:694–695

Поиск корня

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

Удвоение указателя работает с массивом преемник с записью для каждой вершины в графе. Каждый преемник [я] инициализируется родительским индексом вершины я если эта вершина не является корнем или я сам, если эта вершина является корнем. На каждой итерации каждый преемник обновляется до преемника своего преемника. Корень находится, когда преемник преемника указывает на себя.

Следующее псевдокод демонстрирует алгоритм.

алгоритм    Вход: Родительский массив, представляющий лес деревьев. parent [i] - родитель вершины i или сам корень Выход: Массив, содержащий корневого предка для каждой вершины за я ← 1 к длина (родитель) делать параллельно        преемник [я] ← родитель [я]    пока истинный за я ← 1 к длина (преемник) делать параллельно            successor_next [я] ← преемник [преемник [я]]        если successor_next = преемник тогда            перемена за я ← 1 к длина (преемник) делать параллельно            преемник [я] ← successor_next [я]    возвращаться преемник

На следующем изображении показан пример использования прыжка указателя в небольшом лесу. На каждой итерации преемник указывает на вершину, следующую за еще одним преемником. После двух итераций каждая вершина указывает на свой корневой узел.

Прыжок по указателю: пример выполнения

История и примеры

Хотя прыжки по указателям на имена появятся позже, JáJá[2]:88 приписывает первые применения техники в раннем параллельно графовые алгоритмы[3][4]:43 и рейтинг списка.[5] Этот метод был описан под другими названиями, такими как сокращение,[6][7] но к 1990-м годам учебники на параллельные алгоритмы постоянно употреблялся термин прыжок указателя.[2]:52–56[1]:692–701[8]:34–35 Сегодня прыжки с указателем считается шаблон разработки программного обеспечения для работы на рекурсивные типы данных в параллели.[9]:99

Как метод следования связанными путями, графовые алгоритмы идеально подходят для прыжков с указателем. Следовательно, несколько параллельно графовые алгоритмы с использованием прыжков по указателю. К ним относятся алгоритмы поиска корней лес из укоренившиеся деревья,[2]:52–53[6] связанные компоненты,[2]:213–221 минимальные остовные деревья[2]:222–227[10], и двусвязные компоненты[2]:227–239[7]. Тем не менее, переход по указателю также оказался полезным для решения множества других задач, включая компьютерное зрение,[11] сжатие изображений,[12] и Байесовский вывод.[13]

Рекомендации

  1. ^ а б c d Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN  0-262-03293-7.
  2. ^ а б c d е ж JáJá, Джозеф (1992). Введение в параллельные алгоритмы. Эддисон Уэсли. ISBN  0-201-54856-9.
  3. ^ Хиршберг, Д. С. (1976). «Параллельные алгоритмы транзитивного замыкания и связанных компонентных задач». STOC '76: Материалы восьмого ежегодного симпозиума ACM по теории вычислений: 55–57. Дои:10.1145/800113.803631. S2CID  306043.
  4. ^ Сэвидж, Карла Дайан (1977). Параллельные алгоритмы для задач теории графов (Тезис). Университет Иллинойса в Урбане-Шампейн.
  5. ^ Уайли, Джеймс С. (1979). «Глава 4: Вычислительные структуры». Сложность параллельных вычислений (Тезис). Корнелл Университет.
  6. ^ а б Шилоах, Йосси; Вишкин, Узи (1982). "An O (журнал п) Алгоритм параллельного подключения ». Журнал алгоритмов. 3 (1): 57–67. Дои:10.1016/0196-6774(82)90008-6.
  7. ^ а б Тарджан, Роберт Э; Вишкин, Узи (1984). «Нахождение двусвязных компонентов и вычисление древовидных функций в логарифмическом параллельном времени». SFCS '84: Материалы 25-го ежегодного симпозиума по основам компьютерных наук: 12–20. Дои:10.1109 / SFCS.1984.715896. ISBN  0-8186-0591-X.
  8. ^ Куинн, Майкл Дж. (1994). Параллельные вычисления: теория и практика (2-е изд.). Макгроу-Хилл. ISBN  0-07-051294-9.
  9. ^ Маттсон, Тимоти Дж .; Сандерс, Беверли А .; Массингилл, Берна Л. (2005). Шаблоны для параллельного программирования. Эддисон-Уэсли. ISBN  0-321-22811-1.
  10. ^ Чанг, Сун; Кондон, Энн (1996). "Параллельная реализация алгоритма минимального остовного дерева Бувки". Труды Международной конференции по параллельной обработке: 302–308. Дои:10.1109 / IPPS.1996.508073. ISBN  0-8186-7255-2. S2CID  12710022.
  11. ^ Литтл, Джеймс Дж .; Blelloch, Guy E .; Кэсс, Тодд А. (1989). «Алгоритмические методы компьютерного зрения на мелкозернистой параллельной машине». IEEE Transactions по анализу шаблонов и машинному анализу. 11 (3): 244–257. Дои:10.1109/34.21793.
  12. ^ Кук, Грегори У .; Делп, Эдвард Дж. (1994). «Исследование сжатия изображений и видео в формате JPEG с использованием параллельной обработки». Труды ICASSP '94. Международная конференция IEEE по акустике, обработке речи и сигналов: 437–440. Дои:10.1109 / ICASSP.1994.389394. ISBN  0-7803-1775-0. S2CID  8879246.
  13. ^ Намасиваям, Васант Кришна; Прасанна, Виктор К. (2006). «Масштабируемая параллельная реализация ExactInference в байесовских сетях». 12-я Международная конференция по параллельным и распределенным системам - (ICPADS'06): 8 стр. Дои:10.1109 / ICPADS.2006.96. ISBN  0-7695-2612-8. S2CID  15728730.