1 |
Förgreningsfria optimeringsmöjligheter för modern hårdvaraLindfors, Mikael, Leuku Rudander, Max January 2020 (has links)
Traditionellt fokuserar algoritmanalys på tidskomplexitet där alla individuella instruktioner förmodas ta likvärdig “konstant” tid. Men med modern hårdvara går det att både kasta om ordningen på instruktioner (out-of-order-exekvering) och utföra dem parallellt (pipelining) vilket ändrar förutsättningarna för vad som kan betraktas som effektiv kod.I rapporten identifieras bitvisa operationer och conditional moves som två möjliga förgreningsfria tekniker. Möjligheterna att nå prestandaförbättringar genom att använda dessa tekniker undersöks med experiment där förgreningsfri kod jämförs med traditionell kod. Experimenten utförs på både enkla rutiner och sorteringsalgoritmer för att ta reda på om det blir någon skillnad i exekveringstid med de olika teknikerna.Resultatet tyder att man kan finna vissa vinster i exekveringstid med rätt förutsättningar. Vilken typ av data som rutinerna arbetar med, branch predictors förmåga att göra kvalificerade gissningar och kostnaden för de extra instruktioner som förgreningsfria kod innebär är avgörande faktorer. Dessutom är det avgörande att kompilatorn faktiskt lyckas utföra de optimeringar som conditional moves förlitar sig på. / Traditionally, algorithmic analysis focuses on time complexity where all individual instructions are assumed to take equal "constant" time. But with modern hardware it is possible to both reorder instructions (out-of-order execution) and execute them in parallel (pipelining) which changes the conditions for what can be regarded as effective code.The report identifies bitwise operations and conditional moves as two possible branch-free techniques. The possibilities of achieving improved performance through these techniques is investigated by experiments comparing branch-free code with traditional code. The experiments are performed on both simple routines and more advanced sorting algorithms to evaluate if these techniques will lead to a difference in execution-time. The results suggest that certain performance gains can be found in execution time with the right conditions. The type of data that the routines work with, the branch predictor's ability to make qualified guesses, and the cost of the extra instructions that branch-free code entails, are crucial factors. In addition, it is crucial that the compiler actually succeeds in performing the optimizations that conditional moves rely on.
|
Page generated in 0.0599 seconds