Reduktion af omkostningerne ved operationer

At reducere omkostningerne ved operationer i compilerteori er at erstatte langsomme operationer, såsom multiplikation og division, med hurtigere, såsom addition, subtraktion, skift. Så division (multiplikation) med svarer til et skift med bit til højre (venstre).

Der er algoritmer til at konvertere operationer med multiplikation og division med et vilkårligt heltal til en sekvens af enklere operationer (additioner, subtraktioner og forskydninger). En sådan optimering udføres normalt automatisk af compileren og kræver ikke programmørintervention.

Eksempler

Heltals multiplikation med 2:

{ før optimering (3 cyklusser på Core 2 Duo) } y := 2 * x ; { efter optimering } y := x + x ; // 1 ur på Core 2 Duo y := x shl 1 ; // 1 ur på Core 2 Duo


Heltals multiplikation med 3:

{ før optimering (3 cyklusser på Core 2 Duo) } y := 3 * x ; { efter optimering } y := x + x + x ; // 2 ure på Core 2 Duo y := x shl 1 + x ; // 2 ure på Core 2 Duo y := x shl 2 - x ; // 2 ure på Core 2 Duo


Heltals multiplikation med 4:

{ før optimering (3 cyklusser på Core 2 Duo) } y := 4 * x ; { efter optimering (1 cyklus på Core 2 Duo) } y := x shl 2 ;


Heltals multiplikation med 5:

{ før optimering (3 cyklusser på Core 2 Duo) } y := 5 * x ; { efter optimering (2 cyklusser på Core 2 Duo) } y := x shl 2 + x ;


Heltals multiplikation med 6:

{ før optimering (3 cyklusser på Core 2 Duo) } y := 6 * x ; { efter optimering } y := ( x shl 2 - x ) shl 1 ; // 3 cyklusser, suboptimal implementering y := x shl 2 + x shl 1 ; // 2 cyklusser, forudsat at skifteoperationerne falder ind i forskellige aktuatorer og udføres parallelt

Det kan ses, at ikke alle faktorer effektivt kan erstattes af enklere operationer. Derudover bør beslutningen om en sådan udskiftning tage højde for processorens mikroarkitektoniske egenskaber (i det mindste latensen af ​​udførelsen af ​​operationer), for hvilken en sådan optimering udføres (for eksempel tager skiftoperationer på Pentium 4-processoren meget længere tid end på andre processorer, hvilket skal tages i betragtning) [1] .

Fodnoter

  1. ↑ I mange compilere (for eksempel Intel C ++ Compiler ) er det muligt, ved hjælp af kommandolinjeindstillinger, at indikere over for compileren, hvilken processor programmet er planlagt til at blive udført på

Litteratur

  • Alfred Aho, Monica Lam, Ravi Seti, Jeffrey Ullman. Compilers : Principles, Techniques and Tools = Compilers: Principles, Techniques and Tools. — 2. udgave. - M . : "Williams", 2008. - 1184 s. - 1500 eksemplarer.  - ISBN 978-5-8459-1349-4 .
  • Allen, Francis E .; Cocke, John & Kennedy, Ken (1981), Reduction of Operator Strength, i Munchnik, Steven S. & Jones, Neil D., Program Flow Analysis: Theory and Applications , Prentice-Hall, ISBN 978-0-13-729681- en 
  • Cocke, John & Kennedy, Ken (november 1977), En algoritme til reduktion af operatørstyrke, Communications of the ACM bind 20 (11) 
  • Cooper, Keith; Simpson, Taylor & Vick, Christopher (oktober 1995), Operator Strength Reduction , Rice University , < http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95635-S.pdf > . Hentet 22. april 2010.