Güç azaltma - Strength reduction

İçinde derleyici yapımı, güç azalması bir derleyici optimizasyonu Pahalı işlemlerin eşdeğer ancak daha ucuz işlemlerle değiştirildiği yerler[1] Mukavemet azaltımının klasik örneği, bir döngü içindeki "güçlü" çarpımları "daha zayıf" eklemelere dönüştürür - dizi adreslemede sıklıkla meydana gelen bir şey. (Cooper, Simpson ve Vick 1995, s. 1)

Güç azaltma örnekleri şunları içerir:

  • bir döngü içindeki bir çarpmanın bir eklemeyle değiştirilmesi
  • bir döngü içindeki üsleri çarpma ile değiştirme

Kod analizi

Bir programın yürütme süresinin çoğu genellikle kodun küçük bir bölümünde ( sıcak nokta ) ve bu kod genellikle defalarca yürütülen bir döngü içindedir.

Derleyici, döngüleri tanımlamak ve bu döngülerdeki kayıt değerlerinin özelliklerini tanımak için yöntemler kullanır. Mukavemeti azaltmak için derleyici şunlarla ilgilenir:

  • Döngü değişmezleri: bir döngünün gövdesi içinde değişmeyen değerler.
  • Tümevarım değişkenleri: döngü boyunca her seferinde yinelenen değerler.

Döngü değişmezleri aslında bir döngü içindeki sabitlerdir, ancak değerleri döngünün dışında değişebilir. Tümevarım değişkenleri bilinen miktarlarda değişiyor. Terimler belirli bir döngüye bağlıdır. Döngüler iç içe geçtiğinde, dış döngüdeki bir indüksiyon değişkeni, iç döngüde döngüsel değişmez olabilir.

Güç azaltma, bir döngü değişmezi ve bir tümevarım değişkenini içeren ifadeleri arar. Bu ifadelerden bazıları basitleştirilebilir. Örneğin, döngü değişmezinin çarpımı c ve indüksiyon değişkeni ben

c = 7;için (ben = 0; ben < N; ben++){    y[ben] = c * ben;}

art arda daha zayıf eklemelerle değiştirilebilir

c = 7;k = 0;için (ben = 0; ben < N; ben++){    y[ben] = k;    k = k + c;}

Mukavemet azaltma örneği

Aşağıda, dizi indeksleme adresi hesaplamalarından kaynaklanan tüm döngü çarpımlarının gücünü azaltacak bir örnek bulunmaktadır.

Bir diziyi ayarlayan basit bir döngü hayal edin. kimlik matrisi.

için (ben = 0; ben < n; ben++){    için (j = 0; j < n; j++)    {        Bir[ben,j] = 0.0;    }    Bir[ben,ben] = 1.0;}

Ara kod

Derleyici bu kodu şu şekilde görecek:

0010  ; for (i = 0, i 0020  ; {0030      r1 = #0                        ; i = 00040  G0000:0050      yük r2, n                     ; i 0060      cmp r1, r20070      bge G000100800090      ; for (j = 0; j 0100      ; {0110           r3   = #0                 ; j = 00120  G0002:0130           yük r4, n                ; j 0140           cmp r3, r40150           bge G000301600170           ; A [i, j] = 0,0;0180           yük r7, n0190           r8  = r1 * r7             ; alt simge hesapla i * n + j0200           r9  = r8 + r30210           r10 = r9 * #8             ; bayt adresini hesapla0220           fr3 = #0.00230           fstore fr3, Bir[r10]02400250           r3 = r3 + #1              ; j ++0260           br G00020270      ; }0280  G0003:0290      ; A [i, i] = 1.0;0300      yük r12, n                    ; alt simge hesapla i * n + i0310      r13 = r1 * r120320      r14 = r13 + r10330      r15 = r14 * #8                 ; bayt adresini hesapla0340      fr4 = #1.00350      fstore fr4, Bir[r15]03600370      ; i ++0380      r1 = r1 + #10390      br G00000400  ; }0410  G0001:

Bu, 2 boyutlu diziyi ifade eder Bir 1 boyutlu n * n boyutlu bir dizi olarak, böylece yüksek seviyeli kod A [x, y] ifadesini ifade ettiğinde, herhangi bir x ve y geçerli indisleri için dahili olarak A [(x * n) + y] olacaktır.

Birçok optimizasyon

Derleyici pek çok optimizasyon yapmaya başlayacaktır - sadece güç azaltımı değil. Bir döngü içinde sabit (değişmez) olan ifadeler kaldırılmış döngünün dışında. Sabit değerler, fr3 ve fr4 kayan noktalı yazmaçlar gibi her iki döngünün dışında yüklenebilir. Bazı değişkenlerin değişmediğinin kabul edilmesi, kayıtların birleştirilmesine izin verir; n sabittir, bu nedenle r2, r4, r7, r12 kaldırılabilir ve çökebilir. Ortak değer i * n, (kaldırılan) r8 ve r13'te hesaplanır, böylece çökerler. En içteki döngü (0120-0260) 11'den 7 ara talimata düşürüldü. En içteki döngüde kalan tek çarpma, 0210 satırının 8 ile çarpmasıdır.

0010  ; for (i = 0, i 0020    {0030      r1 = #0                        ; i = 00050      yük r2, n0130 ; yük r4, n öldürüldü; r2 kullan0180 ; yük r7, n öldürüldü; r2 kullan0300 ; yük r12, n öldürüldü; r2 kullan0220      fr3 = #0.00340      fr4 = #1.00040  G0000:0060      cmp r1, r2                     ; i 0070      bge G000100800190      r8  = r1 * r2                  ; alt simge hesapla i * n0310 ; r13 = r1 * r2 öldürüldü; r8 kullanın; alt simge hesapla i * n0090      ; for (j = 0; j 0100        {0110           r3   = #0                 ; j = 00120  G0002:0140           cmp r3, r2                ; j 0150           bge G000301600170           ; A [i, j] = 0,0;0200           r9  = r8 + r3             ; alt simge hesapla i * n + j0210           r10 = r9 * #8             ; bayt adresini hesapla0230           fstore fr3, Bir[r10]02400250           r3 = r3 + #1              ; j ++0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1.0;0320      r14 = r8  + r1                 ; alt simge hesapla i * n + i0330      r15 = r14 * #8                 ; bayt adresini hesapla0350      fstore fr4, Bir[r15]03600370      ; i ++0380      r1 = r1 + #10390      br G00000400    }0410  G0001:

Yapılacak daha fazla optimizasyon var. Kayıt r3, en içteki döngüdeki ana değişkendir (0140-0260); döngü boyunca her seferinde 1 artar. R8 kaydı (en içteki döngüde değişmez olan) r3'e eklenir. Derleyici r3 kullanmak yerine r3'ü ortadan kaldırabilir ve r9'u kullanabilir. Döngü, r3 = 0 ila n-1 tarafından kontrol edilmek yerine, r9 = r8 + 0 ila r8 + n-1 tarafından kontrol edilebilir. Bu, dört talimat ekler ve dört talimatı sonlandırır, ancak döngü içinde daha az talimat vardır.

0110  ; r3 = # 0 öldürüldü; j = 00115           r9   = r8                 ; Yeni görev0117           r20  = r8 + r2            ; yeni limit0120  G0002:0140  ; cmp r3, r2 öldürüldü; j 0145           cmp r9, r20               ; r8 + j 0150           bge G000301600170           ; A [i, j] = 0,0;0200  ; r9 = r8 + r3 öldürüldü; alt simge hesapla i * n + j0210           r10 = r9 * #8             ; bayt adresini hesapla0230           fstore fr3, Bir[r10]02400250  ; r3 = r3 + # 1 öldürüldü; j ++0255           r9 = r9 + #1              ; yeni döngü değişkeni0260           br G0002

Şimdi r9 döngü değişkenidir, ancak 8 ile çarpma ile etkileşime girer. Burada biraz güç azaltma yapacağız. 8 ile çarpma, 8'in bazı ardışık toplamalarına indirgenebilir. Artık döngü içinde çarpma yok.

0115           r9   = r8                 ; Yeni görev0117           r20  = r8 + r2            ; yeni limit0118           r10  = r8 * #8            ; r10'un başlangıç ​​değeri0120  G0002:0145           cmp r9, r20               ; r8 + j 0150           bge G000301600170           ; A [i, j] = 0,0;0210  ; r10 = r9 * # 8 öldürüldü; bayt adresini hesapla0230           fstore fr3, Bir[r10]02400245           r10 = r10 + #8            ; çarpma gücü azaldı0255           r9 = r9 + #1              ; döngü değişkeni0260           br G0002

R9 ve r10 (= 8 * r9) yazmaçlarının her ikisi de gerekli değildir; r9 döngüde elenebilir. Döngü şimdi 5 talimattır.

0115  ; r9 = r8 öldürüldü0117           r20  = r8 + r2            ; limit0118           r10  = r8 * #8            ; r10'un başlangıç ​​değeri0119           r22  = r20 * #8           ; yeni limit0120  G0002:0145  ; cmp r9, r20 öldürüldü; r8 + j 0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           bge G000301600170           ; A [i, j] = 0,0;0230           fstore fr3, Bir[r10]02400245           r10 = r10 + #8            ; çarpma gücü azaldı0255  ; r9 = r9 + # 1 öldürüldü; döngü değişkeni0260           br G0002

Dış döngü

Resmin tamamına dönelim:

0010  ; for (i = 0, i 0020    {0030      r1 = #0                        ; i = 00050      yük r2, n0220      fr3 = #0.00340      fr4 = #1.00040  G0000:0060      cmp r1, r2                     ; i 0070      bge G000100800190      r8   = r1 * r2                 ; alt simge hesapla i * n0117      r20  = r8 + r2                 ; limit0118      r10  = r8 * #8                 ; r10'un başlangıç ​​değeri0119      r22  = r20 * #8                ; yeni limit0090      ; for (j = 0; j 0100        {0120  G0002:0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           bge G000301600170           ; A [i, j] = 0,0;0230           fstore fr3, Bir[r10]02400245           r10 = r10 + #8            ; çarpma gücü azaldı0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1.0;0320      r14 = r8  + r1                 ; alt simge hesapla i * n + i0330      r15 = r14 * #8                 ; bayt adresini hesapla0350      fstore fr4, Bir[r15]03600370      ; i ++0380      r1 = r1 + #10390      br G00000400    }0410  G0001:

Dış döngüde artık r1'i artıran dört çarpma vardır. 0190'daki r8 = r1 * r2 kaydı, döngüye girmeden önce ayarlanarak (0055) ve döngünün alt kısmında (0385) r2 artırılarak azaltılabilir.

R8 * 8 (0118'de) değeri, onu başlatarak (0056) ve r8 arttığında (0386) 8 * r2 eklenerek güç azaltılabilir.

R20 kaydı, 0117'deki döngü boyunca her seferinde değişmez / sabit r2 tarafından artırılır. Arttırıldıktan sonra, 0119'da r22 oluşturmak için 8 ile çarpılır. Bu çarpma, döngü boyunca her seferinde 8 * r2 eklenerek azaltılabilir. .

0010  ; for (i = 0, i 0020    {0030      r1 = #0                        ; i = 00050      yük r2, n0220      fr3 = #0.00340      fr4 = #1.00055      r8  = r1 * r2                  ; r8 için başlangıç ​​değerini ayarla0056      r40 = r8 * #8                  ; r8 * 8 için başlangıç ​​değeri0057      r30 = r2 * #8                  ; r40 için artış0058      r20 = r8 + r2                  ; 0117'den kopyalanmıştır0058      r22 = r20 * #8                 ; r22'nin başlangıç ​​değeri0040  G0000:0060      cmp r1, r2                     ; i 0070      bge G000100800190  ; r8 = r1 * r2 öldürüldü; alt simge hesapla i * n0117  ; r20 = r8 + r2 öldürüldü - ölü kod0118      r10  = r40                     ; gücü r40'a indirgenmiş ifade0119  ; r22 = r20 * # 8 öldürüldü; güç azaldı0090      ; for (j = 0; j 0100        {0120  G0002:0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           bge G000301600170           ; A [i, j] = 0,0;0230           fstore fr3, Bir[r10]02400245           r10 = r10 + #8            ; çarpma gücü azaldı0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1.0;0320      r14 = r8  + r1                 ; alt simge hesapla i * n + i0330      r15 = r14 * #8                 ; bayt adresini hesapla0350      fstore fr4, Bir[r15]03600370      ; i ++0380      r1  = r1 + #10385      r8  = r8 + r2                  ; güç r8 = r1 * r2'yi azaltır0386      r40 = r40 + r30                ; gücü azaltma ifadesi r8 * 80388      r22 = r22 + r30                ; güç r22 = r20 * 8 azaltır0390      br G00000400    }0410  G0001:

Son çarpma

Bu, iki döngüyü dış döngü içinde yalnızca bir çarpma işlemiyle (0330'da) ve iç döngü içinde çarpma olmadan bırakır.

0010  ; for (i = 0, i 0020    {0030      r1 = #0                        ; i = 00050      yük r2, n0220      fr3 = #0.00340      fr4 = #1.00055      r8  = r1 * r2                  ; r8 için başlangıç ​​değerini ayarla0056      r40 = r8 * #8                  ; r8 * 8 için başlangıç ​​değeri0057      r30 = r2 * #8                  ; r40 için artış0058      r20 = r8 + r2                  ; 0117'den kopyalanmıştır0058      r22 = r20 * #8                 ; r22'nin başlangıç ​​değeri0040  G0000:0060      cmp r1, r2                     ; i 0070      bge G000100800118      r10  = r40                     ; gücü r40'a indirgenmiş ifade0090      ; for (j = 0; j 0100        {0120  G0002:0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           bge G000301600170           ; A [i, j] = 0,0;0230           fstore fr3, Bir[r10]02400245           r10 = r10 + #8            ; çarpma gücü azaldı0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1.0;0320      r14 = r8  + r1                 ; alt simge hesapla i * n + i0330      r15 = r14 * #8                 ; bayt adresini hesapla0350      fstore fr4, Bir[r15]03600370      ; i ++0380      r1  = r1 + #10385      r8  = r8 + r2                  ; güç r8 = r1 * r2'yi azaltır0386      r40 = r40 + r30                ; gücü azaltma ifadesi r8 * 80388      r22 = r22 + r30                ; güç r22 = r20 * 8 azaltır0390      br G00000400    }0410  G0001:

0320 satırında r14, r8 ve r1'in toplamıdır ve r8 ve r1 döngüde artırılır. R8 kaydı r2 (= n) tarafından çarpılıyor ve r1 1 tarafından çarpılıyor. Sonuç olarak, r14 döngü boyunca her seferinde n + 1 tarafından çarpılıyor. 0330'da son döngü çarpımı, döngü boyunca her seferinde (r2 + 1) * 8 eklenerek azaltılabilir.

0010  ; for (i = 0, i 0020    {0030      r1 = #0                        ; i = 00050      yük r2, n0220      fr3 = #0.00340      fr4 = #1.00055      r8  = r1 * r2                  ; r8 için başlangıç ​​değerini ayarla0056      r40 = r8 * #8                  ; r8 * 8 için başlangıç ​​değeri0057      r30 = r2 * #8                  ; r40 için artış0058      r20 = r8 + r2                  ; 0117'den kopyalanmıştır0058      r22 = r20 * #8                 ; r22'nin başlangıç ​​değeri005Bir      r14 = r8 + r1                  ; 0320'den kopyalandı005B      r15 = r14 * #8                 ; r15'in başlangıç ​​değeri (0330)005C      r49 = r2 + #1005D      r50 = r49 * #8                 ; gücü azaltılmış artış0040  G0000:0060      cmp r1, r2                     ; i 0070      bge G000100800118      r10  = r40                     ; gücü r40'a indirgenmiş ifade0090      ; for (j = 0; j 0100        {0120  G0002:0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           bge G000301600170           ; A [i, j] = 0,0;0230           fstore fr3, Bir[r10]02400245           r10 = r10 + #8            ; çarpma gücü azaldı0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1.0;0320  ; r14 = r8 + r1 öldürüldü; ölü kod0330  ; r15 = r14 * # 8 öldürüldü; güç azaldı0350      fstore fr4, Bir[r15]03600370      ; i ++0380      r1  = r1 + #10385      r8  = r8 + r2                  ; güç r8 = r1 * r2'yi azaltır0386      r40 = r40 + r30                ; gücü azaltma ifadesi r8 * 80388      r22 = r22 + r30                ; güç r22 = r20 * 8 azaltır0389      r15 = r15 + r50                ; güç r15 = r14 * 8 azaltır0390      br G00000400    }0410  G0001:

Hala gidecek daha çok şey var. Sürekli katlama, önsözde r1 = 0 olduğunu fark edecek, bu nedenle birkaç talimat temizleyecektir. Register r8 döngüde kullanılmadığından kaybolabilir.

Ayrıca, r1 yalnızca döngüyü kontrol etmek için kullanılmaktadır, bu nedenle r1, r40 gibi farklı bir indüksiyon değişkeniyle değiştirilebilir. Gittiğim yerde 0 <= i 

0010  ; for (i = 0, i 0020    {0030  ; r1 = # 0; i = 0, ölü kod olur0050      yük r2, n0220      fr3 = #0.00340      fr4 = #1.00055  ; r8 = # 0 öldürüldü; r8 artık kullanılmıyor0056      r40 = #0                       ; r8 * 8 için başlangıç ​​değeri0057      r30 = r2 * #8                  ; r40 için artış0058  ; r20 = r2 öldürüldü; r8 = 0, ölü kod olur0058      r22 = r2  * #8                 ; r20 = r2005Bir  ; r14 = # 0 öldürüldü; r8 = 0, ölü kod olur005B      r15 =       #0                 ; r14 = 0005C      r49 = r2 + #1005D      r50 = r49 * #8                 ; gücü azaltılmış artış005D      r60 = r2 * r30                 ; r40 için yeni sınır0040  G0000:0060  ; cmp r1, r2 öldürüldü; i 0065      cmp r40, r60                   ; i * 8 * n <8 * n * n0070      bge G000100800118      r10  = r40                     ; gücü r40'a indirgenmiş ifade0090      ; for (j = 0; j 0100        {0120  G0002:0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           bge G000301600170           ; A [i, j] = 0,0;0230           fstore fr3, Bir[r10]02400245           r10 = r10 + #8            ; çarpma gücü azaldı0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1.0;0350      fstore fr4, Bir[r15]03600370      ; i ++0380  ; r1 = r1 + # 1 öldürüldü; ölü kod (r40 kontrol döngüsü)0385  ; r8 = r8 + r2 öldürüldü; ölü kod0386      r40 = r40 + r30                ; gücü azaltma ifadesi r8 * 80388      r22 = r22 + r30                ; güç r22 = r20 * 8 azaltır0389      r15 = r15 + r50                ; güç r15 = r14 * 8 azaltır0390      br G00000400    }0410  G0001:

Diğer güç azaltma işlemleri

Bu materyal tartışmalı. Daha iyi şöyle tanımlanır: gözetleme deliği optimizasyonu ve talimat ödevi.

Operatör gücü azaltma kullanımları matematiksel kimlikler Yavaş matematik işlemlerini daha hızlı işlemlerle değiştirmek için. Faydalar, hedef CPU'ya ve bazen çevreleyen koda bağlıdır (bu, CPU içindeki diğer işlevsel birimlerin kullanılabilirliğini etkileyebilir).

  • tamsayı bölme veya çarpma işleminin 2 kuvvetiyle değiştirilmesi aritmetik kaydırma veya mantıksal kayma[2]
  • tamsayı çarpımını bir sabit ile değiştirme, toplama veya çıkarma kombinasyonuyla değiştirme
  • sınırlı makine tamsayı aralığından yararlanarak tamsayı bölmesini bir sabit ile çarpma ile değiştirme.[3] Bu yöntem, bölen 1'den yeterince büyük bir tamsayı değilse de işe yarar, ör. √2 veya π.[4]
Orijinal hesaplamaDeğiştirme hesaplaması
y = x / 8y = x >> 3
y = x * 64y = x << 6
y = x * 2y = x << 1
y = x * 15y = (x << 4) - x
y = x / 10 (burada x, uint16_t türündedir)y = ((uint32_t) x * (uint32_t) 0xCCCD) >> 19)
y = x / π (burada x, uint16_t türündedir)y = (((uint32_t) x * (uint32_t) 0x45F3) >> 16) + x) >> 2)

Tümevarım değişkeni (yetim)

İndüksiyon değişkeni veya yinelemeli güç azaltma, sistematik olarak değişen bazı değişkenlerin bir işlevini, işlevin önceki değerlerini kullanan daha basit bir hesaplamayla değiştirir. İçinde prosedürel programlama dili bu, bir döngü değişkenini içeren bir ifade için geçerlidir ve bir bildirim dili bir argüman için geçerli olacaktır özyinelemeli işlev. Örneğin,

 f x = ... (3 ** x) ... (f (x + 1)) ...

olur

 f x = f ' x 1 nerede   f ' x z = ... z ... (f ' (x + 1) (3 * z)) ...

Burada değiştirilmiş özyinelemeli fonksiyon f′ ikinci bir parametre z = 3 ** x alır ve pahalı hesaplamanın (3 ** x) daha ucuz olanla (3 * z) değiştirilmesine izin verir.

Ayrıca bakınız

Notlar

  1. ^ Steven Muchnick; Muchnick and Associates (15 Ağustos 1997). Gelişmiş Derleyici Tasarım Uygulaması. Morgan Kaufmann. ISBN  978-1-55860-320-2. Güç azalması.
  2. ^ C ve Java gibi dillerde, tamsayı bölmesinin sıfıra doğru yuvarlama semantiği vardır, oysa bir bit kaydırma her zaman aşağı yuvarlar ve negatif sayılar için özel işlem gerektirir. Örneğin Java'da -3 / 2 değerlendirir -1, buna karşılık -3 >> 1 değerlendirir -2. Bu durumda, derleyici olumsuz bölmeyi biraz kaydırarak değiştirerek ikiye bölmeyi optimize edin.
  3. ^ Granlund, Torbjörn; Peter L. Montgomery. "Çarpma Kullanarak Değişmez Tam Sayılarla Bölme" (PDF).
  4. ^ Jones, Nigel. "Tamsayıların sabitlere göre bölümü".

Referanslar

Bu makale, şuradan alınan malzemeye dayanmaktadır: Ücretsiz Çevrimiçi Bilgisayar Sözlüğü 1 Kasım 2008'den önce ve "yeniden lisans verme" şartlarına dahil edilmiştir. GFDL, sürüm 1.3 veya üzeri.