Pipelining (zřetězené zpracování)

Příklady z praxe

1. 01

   Dávka příkazů do Redisu místo tisíce round-tripů

   Klient potřebuje zapsat tisíc klíčů. Bez pipeliningu čeká po každém SET na potvrzení, takže celkový čas je zhruba tisíckrát RTT. S pipeliningem odešle příkazy v několika síťových zápisech a odpovědi přečte naráz, čímž se z minut nad WAN linkou stanou desetiny sekundy. Podmínkou je, že žádný příkaz nepotřebuje výsledek předchozího.

   pipe = r.pipeline(transaction=False)
   for i in range(1000):
       pipe.set(f"key:{i}", i)
   pipe.execute()  # jedno kolo místo tisíce

2. 02

   Chybná predikce větvení vyprázdní potrubí

   Cyklus prochází pole a podmínku vyhodnocuje podle neseřazených hodnot. Prediktor větvení se trefuje zhruba v polovině případů, takže procesor opakovaně zahazuje rozpracované instrukce a naplňuje potrubí znovu. Po seřazení pole se stejný kód bez jediné změny provede výrazně rychleji, protože skok se stane předvídatelným.

   // setřídění pole před tímto cyklem dramaticky
   // sníží počet chybných predikcí
   for (int i = 0; i < n; i++)
       if (data[i] >= 128) sum += data[i];

Časté omyly

MýtusPipeline s pěti fázemi je pětkrát rychlejší.

Ve skutečnostiZrychlení je vždy menší než počet fází. Takt určuje nejpomalejší fáze, mezi stupni přibývá režie registrů a hazardy i chybné predikce vkládají prázdné cykly.

MýtusPipelining zkracuje dobu zpracování jedné položky.

Ve skutečnostiPipelining zvyšuje průchodnost, ne latenci jedné položky. Jedna instrukce projde potrubím stejně dlouho nebo o něco déle; profit je v tom, že jich je uvnitř současně několik.

MýtusHTTP pipelining je běžně používaný způsob, jak zrychlit web.

Ve skutečnostiHTTP/1.1 pipelining sice standard umožňuje, ale hlavní prohlížeče ho kvůli blokování v čele fronty a nekompatibilním proxy nemají zapnutý. Praktickým řešením je multiplexing v HTTP/2 a HTTP/3.

Časté dotazy

Jak souvisí pipelining s délkou pipeline u moderních CPU?

Delší pipeline umožňuje vyšší taktovací frekvenci, protože každá fáze dělá méně práce a stihne se v kratším taktu. Cena je vyšší postih za chybnou predikci větvení: čím delší potrubí, tím víc rozpracovaných instrukcí se při špatném odhadu zahodí. Historicky se ukázalo, že extrémně dlouhé pipeline naráží na spotřebu i na tento postih, takže současné návrhy hledají kompromis a kombinují pipelining s vícenásobným vydáváním instrukcí a přeuspořádaným během.

Kdy pipelining na úrovni protokolu nepomůže?

Pipelining nepomůže, pokud další požadavek závisí na odpovědi předchozího, protože klient nemá co odeslat dopředu. Nepomůže ani u velmi malého počtu operací, kde režie dávkování převáží úsporu jednoho round-tripu, ani na velmi rychlé lince s nízkou latencí, kde je RTT zanedbatelné oproti práci na serveru. Problém nastává také tehdy, když protokol vyžaduje odpovědi ve stejném pořadí jako požadavky: jedna pomalá operace pak blokuje celou frontu.

Je pipelining totéž co paralelismus?

Pipelining je specifická forma paralelismu, kde současně běží různé fáze nad různými položkami, nikoli táž práce na více jednotkách. Klasický paralelismus zdvojuje výpočetní zdroje, aby dvě položky prošly celým zpracováním nezávisle. Pipelining naopak zdroje nezdvojuje, jen je nenechá stát naprázdno. Obojí se běžně kombinuje: superskalární procesor má více pipeline vedle sebe a v každé z nich probíhá zřetězené zpracování.

Jak poznám, že aplikace zbytečně čeká a hodil by se pipelining?

Typickým příznakem je nízké vytížení CPU i databáze při dlouhé celkové době běhu a velký počet drobných požadavků v profilu. Když trasování ukáže tisíce volání trvajících jednotky milisekund, kde většinu času tvoří síťové čekání, je pipelining nebo dávkování na místě. Pomůže spočítat, kolik round-tripů operace udělá: pokud roste lineárně s počtem záznamů, jde o klasický problém N+1, který se řeší dávkou, pipeliningem nebo jedním hromadným dotazem.

Zdroje

1. Instruction pipelining(otevře se v novém okně)Wikipedia
2. Redis pipelining(otevře se v novém okně)Redis
3. RFC 9112: HTTP/1.1(otevře se v novém okně)IETF, 2022
4. Connection management in HTTP/1.x(otevře se v novém okně)MDN Web Docs

Související pojmy

• Bit a byteBit a byte znamená dvojici základních jednotek digitálních dat: bit vyjadřuje jednu binární hodnotu 0 nebo 1, zatímco byte je skupina osmi bitů používaná jako praktická jednotka paměti a souborů. Rozdíl je důležitý při počítání kapacity, síťové rychlosti, kódování textu i práci s nízkoúrovňovými daty.
• BufferováníBufferování je dočasné shromažďování dat ve vyhrazené oblasti paměti (bufferu) mezi dvěma částmi systému, které pracují různou rychlostí nebo po různě velkých dávkách. Zápis se hromadí, dokud se buffer nezaplní nebo dokud ho program nevyprázdní, a teprve pak odchází dál. Cílem je méně drahých operací a plynulejší tok dat.
• Endianita (Big endian a little endian)Endianita je pravidlo, v jakém pořadí se bajty vícebajtového čísla ukládají do paměti nebo posílají po síti. Big endian zapisuje nejvýznamnější bajt jako první, little endian naopak nejméně významný. Rozdíl se projeví vždy, když jeden systém čte binární data zapsaná jiným systémem s opačnou konvencí.
• ACIDACID je sada čtyř vlastností databázové transakce: atomicity, consistency, isolation a durability. Zaručuje, že skupina zápisů proběhne jako jeden celek, neporuší definovaná pravidla databáze, nebude se nebezpečně míchat s jinými transakcemi a po potvrzení přežije pád systému, například při převodu peněz.
• Adaptive IconAdaptivní ikona je formát ikony aplikace na Androidu, který se místo jedné hotové bitmapy skládá z oddělených vrstev: pozadí a popředí. Systém výsledný tvar sám ořízne podle masky výrobce zařízení a může vrstvy animovat nebo přebarvit. Vývojář tak dodá jeden zdroj a launcher z něj vytvoří kruh, čtverec i squircle.
• Adresa v pamětiAdresa v paměti je číslo, kterým procesor jednoznačně označuje konkrétní buňku operační paměti, obvykle jeden bajt. Program pomocí adresy říká, odkud má data načíst nebo kam je zapsat. Adresy tvoří souvislý číselný rozsah, jehož velikost určuje šířka adresní sběrnice a architektura, typicky 32 nebo 64 bitů.
• AI agentAI agent je softwarový systém, který pomocí modelu umělé inteligence vnímá zadaný kontext, plánuje další kroky a samostatně volá nástroje nebo služby k dosažení cíle. Na rozdíl od jednorázového promptu udržuje stav úlohy, vyhodnocuje výsledky akcí a může opakovat postup, dokud nesplní zadání nebo nenarazí na limit.
• AndroidAndroid je operační systém postavený nad linuxovým jádrem, který vyvíjí Google a otevřeně uvolňuje jako projekt AOSP. Android pohání převážnou většinu chytrých telefonů, dále tablety, televize, hodinky i palubní systémy aut. Aplikace se pro něj píší hlavně v Kotlinu nebo Javě a distribuují přes Google Play i alternativní obchody.