Potrubí (výpočet) - Pipeline (computing)

Ve výpočetní technice je kanál , známý také jako datový kanál , sada prvků zpracování dat spojených do série, kde výstupem jednoho prvku je vstup dalšího. Prvky kanálu se často provádějí paralelně nebo časově omezeným způsobem. Mezi prvky se často vkládá určité množství vyrovnávací paměti .

Počítačové kanály zahrnují:

Některé operační systémy mohou poskytovat syntaxi podobnou systému UNIX k řetězci několika běhů programů v kanálu, ale implementovat je jako jednoduché sériové spuštění, spíše než skutečné pipeline - totiž čekáním na dokončení každého programu před spuštěním dalšího.

Koncept a motivace

Pipeline je běžně používaný pojem v každodenním životě. Například na montážní lince automobilky každý konkrétní úkol - například instalace motoru, instalace kapoty a instalace kol - často provádí samostatná pracovní stanice. Stanice plní své úkoly souběžně, každý na jiném autě. Jakmile má auto jeden úkol provedený, přesune se na další stanici. Změny času potřebného k dokončení úkolů lze přizpůsobit „vyrovnávací paměti“ (držení jednoho nebo více automobilů v prostoru mezi stanicemi) a / nebo „zastavením“ (dočasným zastavením stanic proti proudu), dokud nebude k dispozici další stanice .

Předpokládejme, že sestavení jednoho vozu vyžaduje tři úkoly, které trvají 20, 10 a 15 minut. Pokud by pak všechny tři úkoly prováděla jediná stanice, továrna by každých 45 minut vyprodukovala jedno auto. Použitím plynovodu tří stanic by továrna vyprodukovala první auto za 45 minut a poté každých 20 minut nový.

Jak ukazuje tento příklad, pipelining nesnižuje latenci , to znamená celkovou dobu, po kterou jedna položka projde celým systémem. Zvyšuje však propustnost systému , to znamená rychlost zpracování nových položek po první.

Úvahy o návrhu

Vyvažování etap

Vzhledem k tomu, že propustnost kanálu nemůže být lepší než propustnost jeho nejpomalejšího prvku, měl by se návrhář pokusit rozdělit práci a prostředky mezi fáze tak, aby jejich plnění všech trvalo stejnou dobu. Ve výše uvedeném příkladu montáže automobilu, pokud by tyto tři úkoly trvaly 15 minut, místo 20, 10 a 15 minut, by latence byla stále 45 minut, ale nové auto by pak bylo dokončeno každých 15 minut, místo 20.

Vyrovnávací paměť

Za ideálních okolností, pokud jsou všechny prvky zpracování synchronizovány a jejich zpracování trvá stejně dlouho, pak může každý prvek přijímat každý prvek, stejně jako je uvolněn předchozím, v jediném hodinovém cyklu. Tímto způsobem budou položky protékat potrubím konstantní rychlostí, jako vlny ve vodním kanálu. V takových „vlnových kanálech“ není mezi fázemi kromě synchronizace potřebné pro datové položky nutná žádná synchronizace ani ukládání do vyrovnávací paměti.

Obecněji je ukládání do vyrovnávací paměti mezi fázemi kanálu nutné, když jsou doby zpracování nepravidelné nebo když mohou být položky vytvořeny nebo zničeny podél kanálu. Například v grafickém kanálu, který zpracovává trojúhelníky, které se mají vykreslit na obrazovce, může prvek, který kontroluje viditelnost každého trojúhelníku, zahodit trojúhelník, pokud je neviditelný, nebo může vyvést dva nebo více trojúhelníkových částí prvku, pokud jsou částečně skrytý. Vyrovnávací paměť je také nutná, aby se vyrovnaly nesrovnalosti v rychlostech, při kterých aplikace přivádí položky do první fáze a spotřebovává výstup poslední.

Vyrovnávací paměť mezi dvěma stupni může být jednoduše hardwarový registr s vhodnou synchronizační a signalizační logikou mezi dvěma stupni. Když fáze A uloží datovou položku do registru, odešle signál „data available“ (data k dispozici) do další fáze B. Jakmile B tato data použije, odpoví signálem „data receive“ (data přijata) na A. Fáze A se zastaví a čeká pro tento signál, před uložením další datové položky do registru. Fáze B se zastaví a čeká na signál „data available“, pokud je připravena zpracovat další položku, ale fáze A ji dosud neposkytla.

Pokud jsou doby zpracování prvku proměnné, může se často stát, že se celý kanál musí zastavit a čekat, až tento prvek a všechny předchozí spotřebují položky ve svých vstupních vyrovnávacích pamětích. Frekvenci takových stání potrubí lze snížit poskytnutím prostoru pro více než jednu položku ve vstupní vyrovnávací paměti této fáze. Taková vyrovnávací paměť s více položkami je obvykle implementována jako fronta prvního vstupu a prvního výstupu . Jakmile se fronta zaplní, může být nutné zastavit fázi upstream, ale frekvence těchto událostí se sníží, jakmile bude k dispozici více slotů pro vyrovnávací paměť. Teorie front může zjistit počet potřebných slotů pro vyrovnávací paměť v závislosti na variabilitě časů zpracování a na požadovaném výkonu.

Nelineární potrubí

Pokud některá fáze trvá (nebo může trvat) mnohem déle než ostatní a nelze ji zrychlit, může návrhář poskytnout dva nebo více prvků zpracování, které paralelně provedou tento úkol, s jednou vstupní vyrovnávací pamětí a jednou výstupní vyrovnávací pamětí. Jakmile každý prvek dokončí zpracování své aktuální datové položky, doručí ji do společné výstupní vyrovnávací paměti a vezme další datovou položku ze společné vstupní vyrovnávací paměti. Tento koncept „nelineárního“ nebo „dynamického“ kanálu je doložen příklady obchodů nebo bank, které mají dva nebo více pokladníků obsluhujících klienty z jedné čekající fronty.

Závislosti mezi položkami

V některých aplikacích může zpracování položky Y fází A záviset na výsledcích nebo účinku zpracování předchozí položky X některou pozdější fází B kanálu. V takovém případě nemůže fáze A správně zpracovat položku Y, dokud položka X nevyčistí fázi B.

K této situaci dochází velmi často v potrubí instrukcí. Předpokládejme například, že Y je aritmetická instrukce, která čte obsah registru, který měl být upraven dřívější instrukcí X. Nechť A je fáze, která načte operandy instrukce , a B je fáze, která zapíše výsledek do zadaného registru. Pokud se fáze A pokusí zpracovat instrukci Y dříve, než instrukce X dosáhne fáze B, registr může stále obsahovat starou hodnotu a účinek Y by byl nesprávný.

Aby bylo možné takové konflikty zpracovat správně, musí být kanál vybaven dalšími obvody nebo logikou, která je detekuje a provede příslušnou akci. Mezi tyto strategie patří:

  • Zastavení: Každá ovlivněná fáze, například A, je zastavena, dokud není závislost vyřešena - to znamená, dokud nebudou k dispozici požadované informace a / nebo dokud nebude dosaženo požadovaného stavu.
  • Změna pořadí položek: Místo pozastavení může fáze A odložit položku Y stranou a vyhledat jakoukoli další položku Z ve svém vstupním proudu, která nemá žádné závislosti čekající na žádnou předchozí položku. V instrukčních kanálech se tato technika nazývá provádění mimo pořadí .
  • Hádání a ústupek: Jedním důležitým příkladem závislosti položky na položce je zpracování podmíněné větve instrukce X potrubím instrukcí. První stupeň A kanálu, který načte další instrukci Y, která má být provedena, nemůže vykonávat svůj úkol, dokud X nenačte svůj operand a neurčí, zda má být větev přijata nebo ne. To může trvat mnoho hodinových cyklů, protože operand X může zase záviset na předchozích pokynech, které načítají data z hlavní paměti.
Místo toho, aby se zastavil během čekání na dokončení X, může fáze A odhadnout, zda bude větev přijata, nebo ne, a na základě tohoto odhadu načíst další instrukci Y. Pokud se odhad později ukáže jako nesprávný (doufejme, že jen zřídka), systém by se musel vrátit zpět a pokračovat se správnou volbou. Konkrétně by všechny změny, které byly provedeny ve stavu stroje ve fázi A a dalších fázích založených na tomto odhadu, musely být vráceny zpět, instrukce následující po X již v potrubí by musely být propláchnuty a fáze A by musela restartovat s správný ukazatel instrukce . Tato strategie predikce větví je zvláštním případem spekulativního provedení .

Náklady a nevýhody

Zřetězený systém obvykle vyžaduje více zdrojů (prvky obvodu, procesní jednotky, paměť počítače atd.) Než ten, který spouští jednu dávku najednou, protože jeho fáze tyto zdroje nemůže sdílet, a protože může být zapotřebí vyrovnávací paměť a další synchronizační logika elementy.

Kromě toho může přenos položek mezi samostatnými prvky zpracování zvýšit latenci, zejména u dlouhých kanálů.

Další náklady na složitost pipeline mohou být značné, pokud existují závislosti mezi zpracováním různých položek, zejména pokud je k jejich zpracování použita strategie hádání a ústupu. Náklady na implementaci této strategie pro složité instrukční sady skutečně motivovaly některé radikální návrhy na zjednodušení počítačové architektury , jako jsou RISC a VLIW . Kompilátoři byli také zatěžováni úkolem přeskupit strojové instrukce tak, aby se zlepšil výkon instrukčních kanálů.

Nové technologie

Je pravda, že v posledních letech byly vysoké nároky na aplikace a jejich hardware. Například budování kanálů s aplikacemi s jedním uzlem, které procházejí datovými řádky po řádcích, již není možné s objemem a rozmanitostí velkých dat . S příchodem motorů pro analýzu dat, jako je Hadoop nebo nověji Apache Spark , je však možné distribuovat velké datové sady napříč několika uzly zpracování, což aplikacím umožňuje dosáhnout výšky efektivity několik stokrát vyšší, než se dříve myslelo. Důsledkem toho je dnes to, že i počítač střední úrovně využívající distribuované zpracování tímto způsobem zvládne budování a provozování velkých datových kanálů.


Viz také

Reference

  1. ^ Data Pipeline Development Publikováno společností Dativa, vyvoláno 24. května 2018
  2. ^ O. Hauck; Sorin A. Huss; M. Garg. "Dvoufázové asynchronní vlnovody a jejich aplikace na 2D-DCT" . sémantický učenec . Vyvolány 14 September 2019 .
  3. ^ Co je datový kanál? Publikováno společností Data Pipelines, vyvoláno 11. března 2021

Bibliografie