Ukazatel skákání - Pointer jumping

Ukazatel skákání nebo zdvojnásobení cesty je designová technika pro paralelní algoritmy které fungují na strukturách ukazatelů, jako např propojené seznamy a řízené grafy. Skákání ukazatele umožňuje algoritmu sledovat cesty pomocí a časová složitost to je logaritmické s ohledem na délku nejdelší cesty. Dělá to „skokem“ na konec cesty vypočítané sousedy.

Základní operací skákání ukazatele je nahradit každého souseda ve struktuře ukazatele sousedem souseda. V každém kroku algoritmu se toto nahrazení provádí pro všechny uzly v datové struktuře, které lze provádět nezávisle paralelně. V dalším kroku, když je sledován sousedův soused, je cesta souseda, kterou již sledoval v předchozím kroku, přidána do sledované cesty uzlu v jednom kroku. Každý krok tedy účinně zdvojnásobuje vzdálenost, kterou urazily prozkoumané cesty.

Skákání ukazatele nejlépe pochopíme na jednoduchých příkladech, jako je seznam pořadí a kořenový nález.

Seznam hodnocení

Jedním z jednodušších úkolů, které lze vyřešit algoritmem skákání ukazatelů, je seznam pořadí problém. Tento problém je definován takto: vzhledem k propojenému seznamu N uzly, najděte vzdálenost (měřenou v počtu uzlů) každého uzlu ke konci seznamu. Vzdálenost d (n) je definován takto, pro uzly n které ukazují na jejich nástupce ukazatelem další:

  • Li n. další je nula, pak d (n) = 0.
  • Pro jakýkoli jiný uzel d (n) = d (n.next) + 1.

Tento problém lze snadno vyřešit v lineárním čase na sekvenčním stroji, ale paralelní algoritmus může být lepší: daný n procesory, problém lze vyřešit v logaritmický čas, Ó(log N), následujícím algoritmem skákání ukazatelů:[1]:693

  • Přidělte pole N celá čísla.
  • Inicializovat: pro každý uzel procesoru / seznamu n, paralelně:
    • Li n.next = nil, nastavit d [n] ← 0.
    • Jinak nastavit d [n] ← 1.
  • Zatímco jakýkoli uzel n má n.next ≠ nil:
    • Pro každý procesor / uzel seznamu n, paralelně:
      • Li n.next ≠ nil:
        • Soubor d [n] ← d [n] + d [n.next].
        • Soubor n.next ← n.next.next.

Skákání ukazatele nastává na posledním řádku algoritmu, kde je každý uzel další ukazatel se resetuje, aby se přeskočil přímý následník uzlu. Předpokládá se, jak je běžné v EU PRAM model výpočtu, že přístup do paměti se provádí v uzamčeném kroku, takže každý n.next.next načítání paměti se provádí před každým n. další úložiště paměti; v opačném případě si procesory mohou navzájem spojovat svá data a vytvářet tak nekonzistence.[1]:694

Následující diagram sleduje, jak algoritmus hodnocení paralelního seznamu používá skákání ukazatele pro propojený seznam s 11 prvky. Jak popisuje algoritmus, první iterace začíná inicializována se všemi řadami nastavenými na 1, kromě těch s nulovým ukazatelem pro další. První iterace se zaměřuje na bezprostřední sousedy. Každá následující iterace skočí dvakrát tak daleko jako předchozí.

Příklad provedení techniky skákání paralelního ukazatele k výpočtu pořadí seznamu.

Analýzou algoritmu se získá logaritmická doba chodu. Inicializační smyčka trvá konstantní čas, protože každá z N procesory vykonávají konstantní množství práce, vše paralelně. Vnitřní smyčka hlavní smyčky také vyžaduje konstantní čas, stejně jako (podle předpokladu) kontrola ukončení smyčky, takže doba běhu je určena tím, jak často se tato vnitřní smyčka provádí. Jelikož ukazatel přeskakující v každé iteraci rozděluje seznam na dvě části, z nichž jedna se skládá z „lichých“ prvků a jedna z „sudých“ prvků, délka seznamu, na kterou ukazuje každý procesor n je poloviční v každé iteraci, což lze provést maximálně Ó(log N) doba, než bude mít každý seznam maximálně jeden.[1]:694–695

Kořenový nález

Po a cesta v graf je neodmyslitelně sériová operace, ale skákání ukazatele snižuje celkové množství práce sledováním všech cest současně a sdílením výsledků mezi závislými operacemi. Skákání ukazatele iteruje a najde a nástupce - a vrchol blíže ke kořeni stromu - pokaždé. Sledováním nástupců vypočítaných pro jiné vrcholy lze traverz dolů po každé cestě zdvojnásobit každou iteraci, což znamená, že kořeny stromu lze najít v logaritmický čas.

Zdvojnásobení ukazatele funguje na poli nástupce se záznamem pro každý vrchol v grafu. Každý nástupce[i] je inicializován nadřazeným indexem vrcholu i pokud tento vrchol není root nebo to i sám, pokud je tento vrchol kořenem. Při každé iteraci je každý nástupce aktualizován na svého nástupce. Kořen je nalezen, když nástupce nástupce ukazuje na sebe.

Následující pseudo kód demonstruje algoritmus.

algoritmus    Vstup: Rodič pole představující les stromů. rodič [i] je rodičem vrcholu i sám pro kořen Výstup: Pole obsahující kořenového předka pro každý vrchol pro i ← 1 na délka (rodič) dělat paralelně        nástupce[i] ← rodič [i]    zatímco skutečný pro i ← 1 na délka (nástupce) dělat paralelně            successor_next [i] ← nástupce [nástupce [i]]        -li successor_next = nástupce pak            přestávka pro i ← 1 na délka (nástupce) dělat paralelně            nástupce[i] ← následník_další [i]    vrátit se nástupce

Následující obrázek poskytuje příklad použití ukazatele skákání na malém lese. Při každé iteraci následník ukazuje na vrchol následující po jednom dalším nástupci. Po dvou iteracích směřuje každý vrchol na svůj kořenový uzel.

Skákání ukazatele: ukázkové provedení

Historie a příklady

Ačkoli skok s ukazatelem názvu by přišel později, JáJá[2]:88 připisuje první použití této techniky na začátku paralelní grafové algoritmy[3][4]:43 a seznam pořadí.[5] Tato technika byla popsána u jiných jmen, jako je zkratka,[6][7] ale do 90. let učebnice na paralelní algoritmy důsledně používal termín pointer jumping.[2]:52–56[1]:692–701[8]:34–35 Dnes je skákání ukazatele považováno za vzor návrhu softwaru pro provoz na rekurzivní datové typy paralelně.[9]:99

Jako technika pro sledování propojených cest, grafové algoritmy jsou přirozeně vhodné pro skákání ukazatelů. V důsledku toho několik paralelní grafové algoritmy byly využity skoky ukazatele. Patří mezi ně algoritmy pro nalezení kořenů a les z zakořeněné stromy,[2]:52–53[6] připojené komponenty,[2]:213–221 minimální kostry[2]:222–227[10], a vzájemně propojené komponenty[2]:227–239[7]. Skákání ukazatelů se však také ukázalo jako užitečné v řadě dalších problémů, včetně počítačové vidění,[11] komprese obrazu,[12] a Bayesovský závěr.[13]

Reference

  1. ^ A b C d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Úvod do algoritmů (2. vyd.). MIT Press a McGraw-Hill. ISBN  0-262-03293-7.
  2. ^ A b C d E F JáJá, Joseph (1992). Úvod do paralelních algoritmů. Addison Wesley. ISBN  0-201-54856-9.
  3. ^ Hirschberg, D. S. (1976). Msgstr "Paralelní algoritmy pro tranzitivní uzávěr a problémy připojených komponent". STOC '76: Proceedings of the Eighth Annual ACM Symposium on Theory of Computing: 55–57. doi:10.1145/800113.803631. S2CID  306043.
  4. ^ Savage, Carla Diane (1977). Paralelní algoritmy pro teoretické problémy grafů (Teze). University of Illinois v Urbana-Champaign.
  5. ^ Wylie, James C. (1979). „Kapitola 4: Výpočetní struktury“. Složitost paralelních výpočtů (Teze). Cornell University.
  6. ^ A b Shiloach, Yossi; Vishkin, Uzi (1982). „O (log n) Algoritmus paralelního připojení ". Journal of Algorithms. 3 (1): 57–67. doi:10.1016/0196-6774(82)90008-6.
  7. ^ A b Tarjan, Robert E; Vishkin, Uzi (1984). "Hledání vzájemně propojených komponent a výpočetních funkcí stromu v logaritmickém paralelním čase". SFCS '84: Proceedings of the 25.th Symposium on Foundations of Computer Science: 12–20. doi:10.1109 / SFCS.1984.715896. ISBN  0-8186-0591-X.
  8. ^ Quinn, Michael J. (1994). Parallel Computing: Theory and Practice (2. vyd.). McGraw-Hill. ISBN  0-07-051294-9.
  9. ^ Mattson, Timothy G .; Sanders, Beverly A .; Massingill, Berna L. (2005). Vzory pro paralelní programování. Addison-Wesley. ISBN  0-321-22811-1.
  10. ^ Chung, slunce; Condon, Anne (1996). "Paralelní implementace algoritmu Bouvka's Minimum Spanning Tree Algorithm". Sborník mezinárodní konference o paralelním zpracování: 302–308. doi:10.1109 / IPPS.1996.508073. ISBN  0-8186-7255-2. S2CID  12710022.
  11. ^ Malý, James J .; Blelloch, Guy E .; Cass, Todd A. (1989). „Algoritmické techniky pro počítačové vidění na jemnozrnném paralelním stroji“. Transakce IEEE na analýze vzorů a strojové inteligenci. 11 (3): 244–257. doi:10.1109/34.21793.
  12. ^ Cook, Gregory W .; Delp, Edward J. (1994). Msgstr "Vyšetřování komprese obrazu a videa JPEG pomocí paralelního zpracování". Sborník ICASSP '94. Mezinárodní konference IEEE o akustice, řeči a zpracování signálu: 437–440. doi:10.1109 / ICASSP.1994.389394. ISBN  0-7803-1775-0. S2CID  8879246.
  13. ^ Namasivayam, Vasanth Krishna; Prasanna, Viktor K. (2006). "Škálovatelná paralelní implementace ExactInference v Bayesian Networks". 12. mezinárodní konference o paralelních a distribuovaných systémech - (ICPADS'06): 8 stran doi:10.1109 / ICPADS.2006.96. ISBN  0-7695-2612-8. S2CID  15728730.