Branch predictions in de praktijk

[lauwsa]

Voor een school opdracht ben ik naar Branch Predictions in de praktijk aan het kijken. Op het moment ben ik aan het uitzoeken of de software engineer met Branch Predictions rekening mee kan houden.

Applicaties die snel bewerkingen moet kunnen uitvoeren zouden veel voordeel hebben wanneer er ingespeeld kan worden op de prediction. Met een simpele test kan er aangetoond worden dat vergelijkingen vele malen sneller zijn bij alleen maar juiste predictions.

Mijn vraag is of het überhaupt wel mogelijk is om hier mee rekening te houden. Ik kan me voorstellen dat dit wel gedaan kan worden bij bijvoorbeeld de NASA (Hier kan een applicatie ontwikkeld worden welke met bepaalde compiler settings gebuild moet worden en welke op bepaalde hardware moet draaien). Maar hoe zit het met een applicaties welke in meerdere omgevingen moet kunnen draaien? Bijvoorbeeld een applicatie met een zware vorm van encryptie?

Edit: Kan iemand de typo uit de title halen ? practijk

[ Voor 14% gewijzigd door lauwsa op 24-05-2015 13:23 ]

[Boudewijn]

Wat heeft encryptie met meerdere omgevingen te maken?
Kijk eens naar hoe software die in een eigen VM (Java) zit dat soort dingen doet, of vergelijk gecompileerde software eens met geïnterpreteerde...

Huiswerk betekent zelf doen eh, niet anderen op een forum laten doen.

[lauwsa]

Boudewijn schreef op zondag 24 mei 2015 @ 13:24:
Wat heeft encryptie met meerdere omgevingen te maken?
Kijk eens naar hoe software die in een eigen VM (Java) zit dat soort dingen doet, of vergelijk gecompileerde software eens met geïnterpreteerde...

Met omgeving bedoel ik de hardware omgeving. Er zijn vele processoren met andere predictors en verschillende technieken. Als je bij zo'n applicatie rekening wilt houden met Branche prediction dien je ondersteuning voor veel vormen in te bouwen. Gebruik maken van een virtuele machine zal denk ik niet heel veel impact hebben op de prediction. Dit zal ik wel nog gaan onderzoeken.

Het genen wat ik wilde weten is of het mogelijk is om in verschilende hardware omgevingen rekening te houden met Branch prediction. Een I7 en een Core 2 hebben al een andere manier van prediction. De kans is aanwezig dat iemand op dit forum hier al ervaring mee heeft.

Boudewijn schreef op zondag 24 mei 2015 @ 13:24:
Huiswerk betekent zelf doen eh, niet anderen op een forum laten doen.

Het gaat om een onderzoek, om te beginnen ben ik wat veld werk aan het doen. Dat is de reden waarom ik deze vraag hier ook stel. Met deze voorkennis ga ik uiteraard zelf verder met het "echte" onderzoek.

[ Voor 26% gewijzigd door lauwsa op 24-05-2015 14:04 ]

[Camulos]

Intel heeft een groot aantal whitepapers online staan over Branch Prediction (voor verschillende architecturen).

Eerste paar hits bij mij:
- https://software.intel.co...n-to-prevent-mispredicts/ (met code!)
- http://www.intel.com/pres...ce/whitepaper_Nehalem.pdf

Maar veel interessanter is natuurlijk de Intel Developer Zone: https://software.intel.com/en-us
Simpele zoekopdracht levert al veel hits op, software zoals Parallel Studio; maar vooral VTune vallen op.
De laatste analyseert oa op cache-missers en branche predection, aldus wiki

Ik neem aan dat bij al deze informatie een aantal praktijk voorbeelden gegeven worden.
Succes !

[H!GHGuY]

Het eerste wat je al over branch prediction moet weten is dat de naam eigenlijk fout is.
Je spreekt beter over een branch cache die data bijhoudt over de genomen branches in de hoop dat hetzelfde in de toekomst geldig blijft.

De developer heeft er over het algemeen weinig over te zeggen. Er bestaan op sommige architecturen branch-likely en branch-unlikely instructies. Meestal komt dit neer op de waarde die de CPU zal gebruiken als er geen entry in de branch cache zit (i.e. de initialisatiewaarde). Dus de developer heeft er eigenlijk weinig aan te zeggen.
Een CPU kan ook andere heuristieken gebruiken (bvb er vanuit gaan dat de branch nooit genomen wordt - dit zorgt ervoor dat de volgende instructies al in de instruction cache zitten). Een CPU zou zelfs kunnen een instruction cache prefetch doen op het nemen van de branch maar de pipeline vullen als zou de branch niet genomen worden.

Het grootste effect van die likely en unlikely annotaties in code is trouwens het organiseren van de instructies zodat de likely() branch code cache-hot is terwijl de unlikely code ergens achterin de functie geplaatst wordt en dus cache-cold is. De effecten hiervan zijn meestal veel groter dan de mogelijke pipeline flush bij een mispredict zelf. Deze spelen pas echt een rol als je code al cache-hot is, maar dan heb je waarschijnlijk ook al entries in je branch cache en spelen de branch hints in je code geen rol meer.

Je kan die branch hints dus best achterwege laten, tenzij je behoorlijk zeker bent van je stuk. Typisch gebruik is bij error handling (dan zit je sowieso al niet meer in de fast-lane) of daar waar je je code hebt opgesplitst in een fast-path en een slow-path kun je een likely doen voor het fast-path, want het slow-path is al zo traag dat een extra cache miss en/of pipeline flush weinig impact hebben.

Recente CPU's (ook non-x86) hebben veel performance counters waarmee je dit soort events kunt tellen. Dit gaat van instructions executed, branches taken, branches mispredicted, instruction cache misses, etc.

[ Voor 17% gewijzigd door H!GHGuY op 24-05-2015 17:09 ]

[deadinspace]

lauwsa schreef op zondag 24 mei 2015 @ 13:18:
Op het moment ben ik aan het uitzoeken of de software engineer met Branch Predictions rekening mee kan houden.

Dat kan zeker, door te zorgen dat de branch predictor het zo vaak mogelijk goed heeft. Stack Overflow heeft een mooi voorbeeld hiervan.

Bijvoorbeeld een applicatie met een zware vorm van encryptie?

OP wat voor manier denk je dat encryptie hiervoor uit zou maken? En waarom specifiek "zware" encryptie?

lauwsa schreef op zondag 24 mei 2015 @ 13:53:
Met omgeving bedoel ik de hardware omgeving. Er zijn vele processoren met andere predictors en verschillende technieken.

Mwah, dat valt wel mee. Elke niet-triviale branch predictor kijkt naar de geschiedenis van een specifieke branch, probeert daar een patroon in te zien en doet op basis daarvan een voorspelling. Ze verschillen in hoe veel geschiedenis ze bekijken en hoe erg ze hun best doen om patronen te herkennen, maar de algemene werking verschilt weinig.

Als je er dus voor kunt zorgen dat een branch meestal wel, of meestal niet genomen wordt dan pikt vrijwel elke branch predictor dat op.

H!GHGuY schreef op zondag 24 mei 2015 @ 16:20:
Het eerste wat je al over branch prediction moet weten is dat de naam eigenlijk fout is.
Je spreekt beter over een branch cache die data bijhoudt over de genomen branches in de hoop dat hetzelfde in de toekomst geldig blijft.

Daar ben ik het niet mee eens.

Om te beginnen is branch prediction wel degelijk een correcte naam, aangezien er daadwerkelijk een voorspelling wordt gedaan over die branch. Dat dat op basis van de geschiedenis van die branch gebeurt doet daar niks aan af.

Verder is cache geen correcte naam hiervoor; een cache is storage waar data in wordt gekopieerd om het sneller toegankelijk te hebben dan zonder de cache. De geschiedenis van een branch wordt zonder predictor helemaal niet bijgehouden. Er is geen sprake van een kopie, en dus geen cache. Je zou het een branch history kunnen noemen, maar dat gaat (net als cache overigens) compleet voorbij aan het feit dat er voorspellingen gemaakt worden.

[bwerg]

lauwsa schreef op zondag 24 mei 2015 @ 13:18:
Bijvoorbeeld een applicatie met een zware vorm van encryptie?

Ik weet net als anderen niet precies wat je bedoelt, maar wat grappige achtergrond-info is dat je branch-prediction in sommige gevallen juist níet wil bij encryptie omdat dat tot timing-attacks leidt. En daar heb je hetzelfde probleem: de CPU doet lekker wat 'ie wil en het is veel gedoe om dit gedrag te voorkomen. Als ik je post zo lees is dat misschien ook nog wel interessant voor je opdracht, al komt dat vaak neer op zorgen dat er geen branching plaatsvindt, of dat je daar geen informatie uit kan halen. Maar branch prediction voorkomen lijkt me gemakkelijker dan branch prediction juist helpen. Je kunt wel het gedrag onderzoeken en zorgen dat de juiste branch vaker genomen wordt maar daar moet je programmalogica ook maar geschikt voor zijn - je moet als programmeur de branches natuurlijk ook wel weten te voorspellen en dat kan niet altijd (anders had je in simpel gezegd de branch ook wel weg kunnen laten). Echt structurele winst zal er niet te boeken zijn.

deadinspace schreef op maandag 25 mei 2015 @ 16:01:
Mwah, dat valt wel mee. Elke niet-triviale branch predictor kijkt naar de geschiedenis van een specifieke branch, probeert daar een patroon in te zien en doet op basis daarvan een voorspelling. Ze verschillen in hoe veel geschiedenis ze bekijken en hoe erg ze hun best doen om patronen te herkennen, maar de algemene werking verschilt weinig.

Als je er dus voor kunt zorgen dat een branch meestal wel, of meestal niet genomen wordt dan pikt vrijwel elke branch predictor dat op.

Zorgen dat een branch meestal wel of niet genomen wordt is al wat je gewoonlijk doet bij de meeste while/for-loops. Om dáár nog winst bovenop te krijgen moet je echt naar micro-optimalisaties kijken, die inderdaad wel per branch predictor verschillen. Als je weet dat een if-block de eerste keer altijd uitgevoerd wordt kun je dat op de predictor afstemmen, als je weet wat voor keuze die standaard neemt.

[ Voor 50% gewijzigd door bwerg op 25-05-2015 16:31 ]

[DukeBox]

deadinspace schreef op maandag 25 mei 2015 @ 16:01:
Om te beginnen is branch prediction wel degelijk een correcte naam, aangezien er daadwerkelijk een voorspelling wordt gedaan over die branch. Dat dat op basis van de geschiedenis van die branch gebeurt doet daar niks aan af.

Ben ik het ook mee eens.

Daarnaast heb je ook (cpu) cache prediction als onderdeel is van de prefetch wat het helemaal verwarrend zou maken.

[ Voor 3% gewijzigd door DukeBox op 25-05-2015 16:23 ]

[Vinnienerd]

If statements vermijden en als het niet anders kan zoveel mogelijk zorgen dat de distributie van het nemen van een branch (dus een if block) niet rond de 50/50 ligt.

[PrisonerOfPain]

Dit is niet echt een topic wat makkelijk te bespreken is zonder te weten over welke CPU het specifiek gaat. Zonder CPU valt er weinig vast te stellen - je weet de kosten / latencies niet en je weet niet wat voor predictor je mee te maken hebt.

deadinspace schreef op maandag 25 mei 2015 @ 16:01:
Elke niet-triviale branch predictor kijkt naar de geschiedenis van een specifieke branch, probeert daar een patroon in te zien en doet op basis daarvan een voorspelling.

Kom op, dat is wel erg vereenvoudigt. Het spectrum ranged van manual/static branch prediction (als in, dit geeft de programmeur zelf aan in de source-code) tot belachelijk complex met het herkennen van schillende pratronen. Verder bestaan er natuurlijk verschillende jumps (indirect, direct, ret, etc). Je hebt branch predictors die zich vooral met de loop flow control en andere op bijvoorbeeld if-statements met bepaalde patronen.

[ Voor 12% gewijzigd door PrisonerOfPain op 25-05-2015 16:28 ]

[DukeBox]

PrisonerOfPain schreef op maandag 25 mei 2015 @ 16:23:
Volgens mij bedoel je cache prefetching?

Nee, zie mijn edit. Multi cpu (dus fysieke cpus) setups doen aan cache prediction, welke cache evt getruckt kan worden en welke gemerged op een andere cpu wanneer een thread gewisseld wordt van cpu verhuisd de cache mee. Dit zie je bij hypervisors veel gebeuren die een agressieve scheduling doen. In de nieuwe x86 instructie set wordt dat cache prediction genoemd.

[PrisonerOfPain]

Vinnienerd schreef op maandag 25 mei 2015 @ 16:23:
If statements vermijden en als het niet anders kan zoveel mogelijk zorgen dat de distributie van het nemen van een branch (dus een if block) niet rond de 50/50 ligt.

Dat laaste hoeft niet, de AMD Jaguar is bijvoorbeeld heel goed met 0,1,0,1,0,1 patronen.

DukeBox schreef op maandag 25 mei 2015 @ 16:28:
[...]

Nee, zie mijn edit. Multi cpu (dus fysieke cpus) setups doen aan cache prediction, welke cache evt getruckt kan worden en welke gemerged op een andere cpu wanneer een thread gewisseld wordt van cpu verhuisd de cache mee. Dit zie je bij hypervisors veel gebeuren die een agressieve scheduling doen. In de nieuwe x86 instructie set wordt dat cache prediction genoemd.

Toen ik je edit zag had ik 'm door

[H!GHGuY]

deadinspace schreef op maandag 25 mei 2015 @ 16:01:
[...]

Daar ben ik het niet mee eens.

Om te beginnen is branch prediction wel degelijk een correcte naam, aangezien er daadwerkelijk een voorspelling wordt gedaan over die branch. Dat dat op basis van de geschiedenis van die branch gebeurt doet daar niks aan af.

Verder is cache geen correcte naam hiervoor; een cache is storage waar data in wordt gekopieerd om het sneller toegankelijk te hebben dan zonder de cache. De geschiedenis van een branch wordt zonder predictor helemaal niet bijgehouden. Er is geen sprake van een kopie, en dus geen cache. Je zou het een branch history kunnen noemen, maar dat gaat (net als cache overigens) compleet voorbij aan het feit dat er voorspellingen gemaakt worden.

Misschien is branch cache ook niet de perfecte naam (elke vendor geeft er tenslotte een andere naam aan), je hoort ook branch history buffer bvb wat wsch accurater is.

De reden waarom ik de naam predictor niet graag hoor is omdat teveel developers denken dat de CPU branches enkel voorspelt aan de hand van de instructies die hij voorgeschoteld krijgt. Branch history buffer verhult daarbij beter wat het ding eigenlijk in de eerste plaats doet, namelijk de resultaten van de vorige iteraties van die branch bijhouden en aan de hand daarvan speculative execution toelaat van de gekozen branch.

Er zijn nog wat interessante heuristieken die gebruikt worden. Zo kan een CPU speculeren dat een achterwaartse branch waarschijnlijk wel genomen wordt (want dit is vermoedelijk een (for-)lus) terwijl een voorwaartse branch waarschijnlijk niet genomen wordt (welke wsch een gewone if-conditie is).