it-swarm-eu.dev

Proč není podmíněné přesunutí zranitelné pro selhání Branch Prediction?

Po přečtení tento příspěvek (odpověď na StackOverflow) (v sekci optimalizace) jsem přemýšlel, proč podmíněné pohyby nejsou zranitelné pro selhání Branch Prediction. Našel jsem na článek o cond se pohybuje zde (PDF AMD) . Také tam, oni prohlašují výkonnostní výhodu cond. se pohybuje. Ale proč je to? Nevidím to. V okamžiku vyhodnocení instrukce ASM ještě není znám výsledek předchozí instrukce CMP.

Dík.

69

Odlišné předpovědi jsou drahé

Moderní procesor obecně vykonává mezi jedním a třemi instrukcemi každý cyklus, pokud věci jdou dobře (pokud to nezastaví čekání na datové závislosti pro tyto instrukce přijít z předchozích pokynů nebo z paměti).

Výše uvedené tvrzení je překvapivě dobré pro těsné smyčky, ale to by vás nemělo zaslepit na jednu další závislost, která může zabránit provedení instrukce při jejím cyklu: Pro provedení instrukce, procesor musí mít začal ji načítat a dekódovat 15-20 cyklů dříve.

Co by měl procesor dělat, když narazí na pobočku? Načítání a dekódování obou cílů se nemění (pokud následuje více větví, exponenciální počet cest by musel být vyvolán paralelně). Procesor tedy pouze vyvolá a dekóduje jednu ze dvou větví spekulativně.

To je důvod, proč chybně předvídané větve jsou drahé: stojí 15-20 cyklů, které jsou obvykle neviditelné díky efektivnímu instrukčnímu potrubí.

Podmíněný pohyb není nikdy příliš drahý

Podmíněný pohyb nevyžaduje předpověď, takže tento trest nikdy nemůže mít. Má závislost na údajích, stejně jako běžné pokyny. Podmíněný pohyb má ve skutečnosti více závislostí na datech než běžné instrukce, protože datové závislosti zahrnují případy „podmínka true“ a „podmínka false“. Po instrukci, která podmíněně přesune r1 do r2, se zdá, že obsah r2 závisí na předchozí hodnotě r2 a na r1. Dobře předvídaná podmíněná větev umožňuje procesoru odvodit přesnější závislosti. Závislosti na údajích však obvykle trvají jeden až dva cykly, pokud potřebují čas na to, aby dorazily vůbec.

Všimněte si, že podmíněný přesun z paměti do registru by byl někdy nebezpečnou sázkou: pokud je podmínka taková, že hodnota načtená z paměti není přiřazena registru, čekali jste na paměť nic. Instrukce podmíněného pohybu nabízené v sadách instrukcí se však zpravidla registrují, aby zabránily této chybě na straně programátora.

61
Pascal Cuoq

Je to všechno o instrukčním potrubí . Nezapomeňte, že moderní procesory spouští své instrukce v potrubí, což přináší výrazné zvýšení výkonu, když je proces předvídatelný procesorem.

cmov

    add     eax, ebx
    cmp     eax, 0x10
    cmovne  ebx, ecx
    add     eax, ecx

V okamžiku vyhodnocení instrukce ASM ještě není znám výsledek předchozí instrukce CMP.

Možná, ale CPU stále ví, že instrukce následující cmov bude provedena hned po, ​​bez ohledu na výsledek z cmp a cmov instrukce. Další instrukce tak může být bezpečně načtena/dekódována předem, což není případ větví.

Další instrukce by mohla být provedena ještě před cmov (v mém příkladu by to bylo bezpečné)

větev

    add     eax, ebx
    cmp     eax, 0x10
    je      .skip
    mov     ebx, ecx
.skip:
    add     eax, ecx

V tomto případě, když dekodér CPU vidí je .skip, bude muset zvolit, zda bude pokračovat v instrukcích předběžného načítání/dekódování buď 1) z další instrukce, nebo 2) z cíle skoku. CPU bude odhadovat, že se tato podmíněná větev neprojde, takže další instrukce mov ebx, ecx půjde do potrubí.

O několik cyklů později se provede je .skip a pobočka se přijme. Sakra! Naše potrubí nyní drží nějaký náhodný odpad, který by nikdy neměl být vykonán. CPU musí vyprázdnit všechny instrukce uložené v mezipaměti a začít čerstvé od .skip:.

To je výkonový trest chybně předvídaných větví, který se nikdy nemůže stát s cmov, protože nemění průběh provádění.

42
Martin

Výsledek nemusí být ještě znám, ale pokud to dovolují jiné okolnosti (zejména závislostní řetězec), může cpu přeuspořádat a provádět instrukce následující po cmov. Vzhledem k tomu, že se nejedná o rozvětvení, je třeba tyto pokyny v každém případě vyhodnotit.

Zvažte tento příklad:

cmoveq edx, eax
add ecx, ebx
mov eax, [ecx]

Dva instrukce následující za cmov nezávisí na výsledku cmov, takže mohou být provedeny i když je cmov samotný nevyřízený (toto se nazývá out of order order ). I když nemohou být provedeny, mohou být stále načteny a dekódovány.

Verze větvení může být:

    jne skip
    mov edx, eax
skip:
    add ecx, ebx
    mov eax, [ecx]

Problém je v tom, že se mění tok řízení a cpu není dostatečně chytrý, aby viděl, že by mohl jen "vložit" vynechanou instrukci mov, pokud by větev byla předpovězena tak, jak byla přijata - namísto toho odhodí všechno, co udělal po větvi, a od nuly. Odtud pochází trest.

16
Jester

Měli byste si je přečíst. S Fog + Intel, jen hledat CMOV.

Kritika CMOV Linuse Torvalda z roku 2007
Porovnání mikroarchitektur Agnera Foga
Referenční příručka pro architektury Intel® 64 a IA-32

Krátká odpověď, správné předpovědi jsou „volné“, zatímco podmíněné předpovědi mohou na Haswellu stát 14-20 cyklů. Nicméně, CMOV není nikdy volný. Stále si myslím, že CMOV je teď lepší než když Torvalds vyděsil. Neexistuje žádný jediný správný pro všechny časy na všech procesorech někdy odpovědět.

2
Olsonist

Mám tuto ilustraci ze snímku [Peter Puschner et al.], Který vysvětluje, jak se transformuje do jediného kódu cesty a zrychluje provádění. 

 enter image description here

0
COLD ICE