Obor (informatika) - Branch (computer science)

Pro jiná použití, vidět větev (disambiguation) .
Strojový kód
Obecné pojmy
Instrukce

Větev je instrukce v počítačovém programu , který může způsobit, že počítač začne provedením jinou pořadí instrukcí a tedy odchylovat od jeho výchozí chování provádění pokynů v uvedeném pořadí. Větev (nebo rozvětvená , rozvětvená ) může také odkazovat na akt přepnutí provádění na jinou sekvenci instrukcí v důsledku provedení větvové instrukce. Instrukce větví se používají k implementaci řídicího toku do smyček a podmíněných programů (tj. Provádění určité sekvence instrukcí pouze tehdy, jsou -li splněny určité podmínky).

Instrukce větve může být buď bezpodmínečná větev , která vždy vede k větvení, nebo podmíněná větev , která může nebo nemusí způsobit větvení v závislosti na nějaké podmínce. V závislosti na tom, jak určuje adresu nové sekvence instrukcí („cílová“ adresa), je větvová instrukce obecně klasifikována jako přímá , nepřímá nebo relativní , což znamená, že instrukce obsahuje cílovou adresu nebo určuje, kde je cíl adresa má být nalezena (např. registr nebo umístění v paměti), nebo určuje rozdíl mezi aktuální a cílovou adresou.

Implementace

Mechanicky může instrukce větve změnit programový čítač (PC) CPU . Čítač programu ukládá adresu paměti další instrukce, která má být provedena. Větev proto může způsobit, že CPU začne načítat své instrukce z jiné sekvence paměťových buněk.

Instrukce větve na úrovni stroje se někdy nazývají instrukce skoku . Návod na úrovni stroj skok typicky mají nepodmíněné a podmíněné formy podle toho, které mohou být přijata , nebo neberou v závislosti na nějaké podmínce. Obvykle existují různé formy pro jednosměrné skoky, často nazývané vyvolání skoků a podprogramů známé jako volání, které automaticky uloží původní adresu jako zpáteční adresu v zásobníku, což umožňuje vyvolání jednoho podprogramu z více míst v kódu.

Když je přijata větev , čítač programu CPU je nastaven na argument instrukce skoku. Takže další instrukce se stane instrukcí na této adrese v paměti . Tok řízení se proto mění.

Pokud není větev přijata , čítač programu CPU se nezmění. Další provedenou instrukcí je tedy instrukce za instrukcí větve. Tok řízení je tedy nezměněn.

Termín větev lze použít při odkazování na programy ve vyšších jazycích, stejně jako na programy napsané ve strojovém kódu nebo v jazyce sestavení . V programovacích jazycích na vysoké úrovni mají větve obvykle formu podmíněných příkazů různých forem, které zapouzdřují sekvenci instrukcí, která bude provedena, pokud jsou splněny podmínky. Bezpodmínečné větvící instrukce, jako je GOTO, se používají k bezpodmínečnému „skoku“ na (zahájení provádění) jiné instrukční sekvence.

V CPU s vlajkovými registry dřívější instrukce nastavuje podmínku v příznakovém registru. Dřívější instrukce může být aritmetická nebo logická . Často je blízko pobočky, i když ne nutně instrukce bezprostředně před pobočkou. Uložená podmínka se pak použije ve větvi, jako je skok, pokud je nastaven příznak přetečení . Tyto dočasné informace jsou často uloženy v registru příznaků, ale mohou být také umístěny jinde. Vlajkový registr je v pomalejších jednoduchých počítačích jednoduchý. V rychlých počítačích může registr příznaků omezovat rychlost, protože instrukce, které by jinak mohly fungovat souběžně (v několika prováděcích jednotkách ), musí nastavit bity příznaků v konkrétní sekvenci.

Existují také stroje (nebo konkrétní instrukce), kde může být stav zkontrolován samotnou instrukcí skoku, jako je větev <label>, pokud je registr X negativní . V jednoduchých počítačových návrzích vykonávají srovnávací větve více aritmetiky a mohou spotřebovat více energie než větve registrů vlajek. V rychlých návrzích počítačů mohou porovnávací větve běžet rychleji než větve vlajkových registrů, protože porovnávací větve mohou přistupovat k registrům s více paralelismem pomocí stejných mechanismů CPU jako výpočet.

Některé rané a jednoduché architektury CPU, které se stále nacházejí v mikrokontrolérech, nemusí implementovat podmíněný skok, ale spíše pouze podmíněnou operaci „přeskočit další instrukci“. Podmíněný skok nebo volání je tedy implementováno jako podmíněné přeskočení instrukce bezpodmínečného skoku nebo volání.

Příklady

V závislosti na architektuře počítače se assembleru mnemotechnická pomůcka pro výuku skoku je typicky nějaký zkrácený tvar slova skoku nebo slovní pobočky , často spolu s dalšími informačními dopisy (nebo extra parametru), které představují podmínku. Někdy jsou zahrnuty i další podrobnosti, například rozsah skoku (velikost posunu) nebo speciální režim adresování, který by měl být použit k vyhledání skutečného efektivního posunu.

Tato tabulka uvádí pokyny k větvení nebo skokům na úrovni stroje, které se nacházejí v několika známých architekturách:

stav nebo výsledek x86 PDP-11, VAX ARM (částečně 6502) rovnice
nula (znamená stejné pro sub/cmp) JZ; JNZ BEQ; BNE BEQ; BNE nula; ne nula
negativní (N), znaménko (S) nebo minus (M) JS; JNS BMI; BPL BMI; BPL záporný; ne negativní
aritmetické přetečení (příznak nazývaný O nebo V) JO; JNO BVS; BVC BVS; BVC přetékat; nepřetékat
carry (od add, cmp, shift atd.) JC; JNC BCS; BCC BCS; BCC nést; nenosit
níže bez znaménka (níže) JB BLO BLO * půjčit si
bez znaménka pod nebo rovno (nižší nebo stejné) JBE BLOS BLS * půjčit nebo nula
bez znaménka nad nebo rovno (vyšší nebo stejné) JAE BIS BHS * nepůjčit si
bez znaménka výše (vyšší) JA BHI BHI * nepůjčovat si a nula
podepsal méně než JL BLT BLT podepsat flow přetečení
podepsáno méně nebo rovno JLE BLE BLE (znaménko flow přetečení) nebo nula
podepsané větší nebo rovné JGE BGE BGE znak = přetečení
podepsáno větší než JG BGT BGT (znaménko = přetečení) a ne nula

* x86, PDP-11, VAX a některé další, nastaví příznak přenosu na signalizaci vypůjčení a zruší znak přenosu na znamení, že není vypůjčeno . ARM, 6502 , PIC a některé další dělají u subtraktivních operací opak. Tato obrácená funkce vlajky carry pro určité pokyny je označeno ( * ), to znamená, že půjčit = ne nosit v některých částech tabulky, ale není-li uvedeno jinak, borrow≡carry. Provádění aditivních operací však většina architektur řeší stejným způsobem.

Problémy s výkonem s pokyny pobočky

Aby bylo dosaženo vysokého výkonu, jsou moderní procesory pipelineovány . Skládají se z více částí, z nichž každá částečně zpracuje instrukci, přenese své výsledky do další fáze potrubí a začne pracovat na další instrukci v programu. Tento návrh očekává, že se instrukce spustí v určité neměnné sekvenci. Podmíněné větve znemožňují znát tuto sekvenci. Podmíněné větve tedy mohou způsobit „zastavení“, ve kterých musí být potrubí restartováno v jiné části programu.

Zlepšení výkonu snížením stání z poboček

Několik technik zvyšuje rychlost snížením stání z podmíněných větví.

Tipy pro předpověď větví

Historicky předpověď větve brala statistiky a používala výsledek k optimalizaci kódu. Programátor by zkompiloval testovací verzi programu a spustil ji s testovacími daty. Testovací kód počítal, jak byly větve skutečně pořízeny. Statistiky z testovacího kódu pak kompilátor použil k optimalizaci větví uvolněného kódu. Optimalizace by zajistila, že nejrychlejší směr větve (přijatý nebo ne) bude vždy nejčastěji používanou cestou řídicího toku. Aby to bylo možné, CPU musí být navrženo s (nebo alespoň mít) předvídatelným časováním větví. Některé procesory mají sady instrukcí (například Power ISA ), které byly navrženy s „radami větví“, aby kompilátor mohl CPU sdělit, jak má být každá větev přijata.

Problém s předpovědí softwarové větve je, že vyžaduje složitý proces vývoje softwaru.

Hardware prediktory větví

Chcete -li spustit jakýkoli software, prediktory hardwarových větví přesunuly statistiky do elektroniky. Prediktory větví jsou části procesoru, které odhadují výsledek podmíněné větve. Logika procesoru pak začne hádat tak, že začne provádět očekávaný tok instrukcí. Příkladem jednoduchého schématu predikce větví hardwaru je předpokládat, že jsou odebrány všechny zpětné větve (tj. Na menší čítač programů) (protože jsou součástí smyčky) a všechny větve vpřed (na větší čítač programu) nejsou převzaty (protože nechávají smyčku). Lepší prediktory větví jsou vyvíjeny a ověřovány statisticky jejich spuštěním v simulaci na různých testovacích programech. Dobří prediktoři obvykle počítají výsledky předchozích poprav pobočky. Rychlejší a dražší počítače pak mohou běžet rychleji investováním do lepší elektroniky pro předpovídání poboček. V CPU s hardwarovou předpovědí větví rady větev nechají pravděpodobně lepší předpověď větve kompilátoru přepsat hardwarově jednodušší predikci větví.

Kód bez poboček

Určitou logiku lze zapsat bez větví nebo s menším počtem větví. Často je možné místo větví použít bitové operace , podmíněné pohyby nebo jinou predikci . Ve skutečnosti je kód bez větví pro kryptografii nutný kvůli časovým útokům .

Odložený slot

Další technikou je slot pro zpoždění větví . V tomto přístupu je vždy provedena jedna instrukce po větvi. Počítač proto může pomocí této instrukce provádět užitečnou práci bez ohledu na to, zda se jeho potrubí zastaví. Tento přístup byl historicky populární v počítačích RISC . V rodině kompatibilních procesorů to komplikuje vícekolové procesory (bez potrubí), rychlejší CPU s delšími než očekávanými kanály a superskalární CPU (které mohou vykonávat pokyny mimo pořadí.)

Viz také

Poznámky

Reference

externí odkazy