Předpovídání větví v procesoru: jak zrychlit kód a vyhnout se chybám

Jak predikce větvení v procesoru urychluje kód a vytváří zranitelnosti

Moderní procesory předpovídají výsledky podmíněných skoků, aby se vyhnuly prostojům konveyoru. Tato optimizace zrychluje provádění kódu v průměru o 30–50 %, ale v 5 % případů vede k resetu konveyoru a ztrátě výkonu. Na příkladu třídění dat může rozdíl v rychlosti dosáhnout šestkrát.

Princip fungování konveyoru a nutnost predikce

Procesor provádí instrukce po etapách přes konveyor, zahrnující stádia výběru, dekódování, provádění, přístupu k paměti a zápisu. Hloubka konveyoru v moderních CPU dosahuje 15–20 stádií. Při setkání s podmíněným skokem if procesor čelí dilematu: čekat na výpočet podmínky nebo načíst další instrukci předem. Čekání vede k prostojům v 15–20 taktech, proto procesor předpovídá, která větev kódu bude provedena.

Evoluce algoritmů predikce větvení

Přesnost predikce se vyvinula od jednoduchých metod po složité systémy na bázi neuronových sítí.

• Statická predikce – vždy předpovídá provedení nebo neprovedení větve, přesnost kolem 50 %.
• Dynamická predikce (1-bit predictor) – využívá historii předchozích skoků, dosahuje 99,8 % přesnosti pro cykly.
• Dvoubitový počítadlo – přidává stabilitu vůči náhodným chybám, zvyšuje přesnost na 85–90 %.
• Dvouúrovňový prediktor – analyzuje vzory posledních skoků přes Branch History Register a Pattern History Table.
• TAGE (TAgged GEometric history length predictor) – moderní standard, využívající několik tabulek s různou hloubkou historie, což dává 95–98 % přesnosti na reálném kódu.

Praktický vliv na výkon kódu

Chyba predikce vede k resetu konveyoru a ztrátě 15–20 taktů práce. Na frekvenci 5 GHz to je 4 nanosekundy, ale při milionech chyb za sekundu výkon klesá o 30–50 %. Klasický příklad – zpracování pole s podmínkou:

for (int i = 0; i < 100000; i++) {
    for (int j = 0; j < arraySize; j++) {
        if (data[j] >= 128) {
            sum += data[j];
        }
    }
}

Na netříděném poli prediktor chybuje v ~50 % případů, provádění trvá 11,2 sekundy. Na tříděném poli chyba nastane jednou na hranici hodnot, čas se zkrátí na 1,9 sekundy – zrychlení šestkrát.

Metody optimizace pro vývojáře

Ruční optimizace predikce větvení je nutná pouze pro kritické části kódu. Hlavní přístupy:

• Použití kódu bez větvení – nahrazení podmíněných operátorů aritmetickými nebo bitovými operacemi.
• Analýza metrik – nástroj perf stat v Linuxu ukazuje procento chyb prediktoru (branch-misses).
• Třídění dat – efektivní při opakovaném zpracování jednoho souboru.
• Profilování – povinná etapa pro identifikaci úzkých míst.
• Použití nápověd pro kompilátor – makra likely()/unlikely() nebo atributy [[likely]]/[[unlikely]] v C++20 ovlivňují umístění kódu.

Zranitelnost Spectre a bezpečnost

Zranitelnost Spectre, objevená v roce 2018, využívá spekulativní provádění instrukcí. Útočník trénuje prediktor na legitimních datech, poté vyvolá spekulativní přístup k chráněné paměti. Ačkoli výsledek se vrací zpět, stopy zůstávají v cache, což umožňuje obnovit data pomocí analýzy času přístupu. Záplaty pro odstranění zranitelnosti snižují výkon o 2–30 %.

Co je důležité

• Predikce větvení – klíčová optimizace procesorů, zvyšující výkon o 30–50 %.
• Chyby predikce se vyskytují v 5 % případů, vedouc k resetu konveyoru a ztrátě 15–20 taktů.
• Třídění dat může zrychlit provádění kódu šestkrát díky zlepšení predikce.
• Kód bez větvení a aritmetické operace eliminují potřebu predikce.
• Zranitelnost Spectre využívá spekulativní provádění pro přístup k chráněné paměti.

— Editorial Team