Reducerea costurilor operațiunilor

Reducerea costului operațiilor în teoria compilatorului este înlocuirea operațiilor lente, cum ar fi înmulțirea și împărțirea, cu altele mai rapide, cum ar fi adunarea, scăderea, deplasarea. Deci, împărțirea (înmulțirea) cu este echivalentă cu o deplasare cu biți la dreapta (stânga).

Există algoritmi pentru conversia operațiilor de înmulțire și împărțire printr-un număr întreg arbitrar într-o succesiune de operații mai simple (adunări, scăderi și deplasări). O astfel de optimizare este de obicei efectuată automat de către compilator și nu necesită intervenția programatorului.

Exemple

Înmulțirea întregului cu 2:

{ înainte de optimizare (3 cicluri pe Core 2 Duo) } y := 2 * x ; { dupa optimizare } y := x + x ; // 1 ceas pe Core 2 Duo y := x shl 1 ; // 1 ceas pe Core 2 Duo


Înmulțirea întregului cu 3:

{ înainte de optimizare (3 cicluri pe Core 2 Duo) } y := 3 * x ; { dupa optimizare } y := x + x + x ; // 2 ceasuri pe Core 2 Duo y := x shl 1 + x ; // 2 ceasuri pe Core 2 Duo y := x shl 2 - x ; // 2 ceasuri pe Core 2 Duo


Înmulțirea întregului cu 4:

{ înainte de optimizare (3 cicluri pe Core 2 Duo) } y := 4 * x ; { după optimizare (1 ciclu pe Core 2 Duo) } y := x shl 2 ;


Înmulțirea întregului cu 5:

{ înainte de optimizare (3 cicluri pe Core 2 Duo) } y := 5 * x ; { după optimizare (2 cicluri pe Core 2 Duo) } y := x shl 2 + x ;


Înmulțirea întregului cu 6:

{ înainte de optimizare (3 cicluri pe Core 2 Duo) } y := 6 * x ; { după optimizare } y := ( x shl 2 - x ) shl 1 ; // 3 cicluri, implementare suboptimală y := x shl 2 + x shl 1 ; // 2 cicluri, cu condiția ca operațiunile de schimbare să se încadreze în diferite actuatoare și să fie efectuate în paralel

Se poate observa că nu toți factorii pot fi înlocuiți efectiv cu operații mai simple. În plus, decizia privind o astfel de înlocuire ar trebui să țină cont de caracteristicile microarhitecturale ale procesorului (cel puțin latența execuției operațiunilor) pentru care se realizează o astfel de optimizare (de exemplu, operațiunile de schimbare pe procesorul Pentium 4 durează mult mai mult ). decât pe alte procesoare, care trebuie luate în considerare) [1] .

Note de subsol

  1. ↑ În multe compilatoare (de exemplu, Intel C ++ Compiler ) este posibil, folosind opțiunile din linia de comandă, să se indice compilatorului procesorul pe care este planificat să fie executat programul

Literatură

  • Alfred Aho, Monica Lam, Ravi Seti, Jeffrey Ullman. Compilatoare : Principles, Techniques, and Tools = Compilatoare: Principles, Techniques, and Tools. — ediția a II-a. - M . : „Williams”, 2008. - 1184 p. - 1500 de exemplare.  - ISBN 978-5-8459-1349-4 .
  • Allen, Francis E .; Cocke, John & Kennedy, Ken (1981), Reducerea puterii operatorului, în Munchnik, Steven S. & Jones, Neil D., Program Flow Analysis: Theory and Applications , Prentice-Hall, ISBN 978-0-13-729681- unu 
  • Cocke, John & Kennedy, Ken (noiembrie 1977), Un algoritm pentru reducerea puterii operatorului, Communications of the ACM vol . 20 (11) 
  • Cooper, Keith; Simpson, Taylor & Vick, Christopher (octombrie 1995), Operator Strength Reduction , Rice University , < http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR95635-S.pdf > . Preluat la 22 aprilie 2010.