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

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

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

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

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

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

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

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

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

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

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

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

Нахождение корня

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

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

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

algorithm    Input: An array parent representing a forest of trees. parent[i] is the parent of vertex i or itself for a root    Output: An array containing the root ancestor for every vertex    for i ← 1 to length(parent) do in parallel        successor[i] ← parent[i]    while true        for i ← 1 to length(successor) do in parallel            successor_next[i] ← successor[successor[i]]        if successor_next = successor then            break        for i ← 1 to length(successor) do in parallel            successor[i] ← successor_next[i]    return successor

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

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

Хотя название прыжков с указателем появилось позже, 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]

Ссылки

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

[clrs-1] Jump up to: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03293-7 .

[JaJa-2] Jump up to: ^а ^б ^с ^д ^и ^ж ЯХА, Джозеф (1992). Введение в параллельные алгоритмы . Эддисон Уэсли. ISBN 0-201-54856-9 .

[3] Хиршберг, Д.С. (1976). «Параллельные алгоритмы для транзитивного замыкания и задач связных компонент». Материалы восьмого ежегодного симпозиума ACM по теории вычислений - STOC '76 . стр. 55–57. дои : 10.1145/800113.803631 . S2CID 306043 .

[4] Сэвидж, Карла Дайан (1977). Параллельные алгоритмы для задач теории графов (Диссертация). Университет Иллинойса в Урбана-Шампейн. Архивировано из оригинала 1 июня 2022 года.

[Wylie-5] Уайли, Джеймс К. (1979). «Глава 4: Вычислительные структуры» . Сложность параллельных вычислений (Диссертация). Корнелльский университет.

[Shiloach-6] Jump up to: ^а ^б Шилоах, Йоси; Вишкин, Узи (1982). «Алгоритм параллельной связности O (log n )». Журнал алгоритмов . 3 (1): 57–67. дои : 10.1016/0196-6774(82)90008-6 .

[Tarjan-7] Jump up to: ^а ^б Тарьян, Роберт Э; Вишкин, Узи (1984). «Нахождение двусвязных компонентов и вычисление древовидных функций в логарифмическом параллельном времени». 25-й ежегодный симпозиум по основам информатики, 1984 г. стр. 12–20. дои : 10.1109/SFCS.1984.715896 . ISBN 0-8186-0591-Х .

[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] Литтл, Джеймс Дж.; Блеллок, Гай Э.; Касс, Тодд А. (1989). «Алгоритмические методы компьютерного зрения на мелкозернистой параллельной машине». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 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 стр. doi : 10.1109/ICPADS.2006.96 . ISBN 0-7695-2612-8 . S2CID 15728730 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

v т и Параллельные вычисления
Общий	Распределенные вычисления Параллельные вычисления Массивная параллель Облачные вычисления Высокопроизводительные вычисления Многопроцессорность Многоядерный процессор ГПГПУ Компьютерная сеть Систолический массив
Уровни	Кусочек Инструкция Нить Задача Данные Память Петля Трубопровод
Многопоточность	Временной Одновременный (SMT) Одновременное и гетерогенное Спекулятивный (СпМТ) упреждающий Кооператив Кластерная многопоточная обработка (CMT) Аппаратный разведчик
Теория	Модель ПРАМ PEM-модели Анализ параллельных алгоритмов Закон Амдала Закон Густавсона Экономическая эффективность Метрика Карпа – Флатта Замедлять Ускорение
Элементы	Процесс Нить Волокно Окно инструкций Множество
Координация	Многопроцессорность Согласованность памяти Согласованность кэша Аннулирование кэша Барьер Синхронизация Контрольная точка приложения
Программирование	Потоковая обработка Программирование потоков данных Модели Неявный параллелизм Явный параллелизм Параллелизм Неблокирующий алгоритм
Аппаратное обеспечение	Таксономия Флинна СИСД SIMD Обработка массивов (SIMT) Конвейерная обработка Ассоциативная обработка МИСД МИМД Архитектура потока данных Конвейерный процессор Суперскалярный процессор Векторный процессор Мультипроцессор симметричный асимметричный Память общий распределенный распределенный общий ОДИН НУМА ЕСТЬ Массивно-параллельный компьютер Компьютерный кластер Кластер Беовульф Сетевой компьютер Аппаратное ускорение
API	Атеджи ПХ Способствовать росту Часовня HPX Очарование++ Том Коаррей Фортран ДРУГОЙ Дриада С++ AMP Глобальные массивы GPUОткрыть ИМБ OpenMP OpenCL OpenHMPP OpenACC Параллельные расширения НДС pthreads РафтЛиб РПЦм СКП TBB ЗПЛ
Проблемы	Автоматическое распараллеливание Тупик Детерминированный алгоритм Смущающе параллельно Параллельное замедление Состояние гонки Программная блокировка Масштабируемость Голод
Категория: Параллельные вычисления