You can edit almost every page by Creating an account. Otherwise, see the FAQ.

کاهش فشار

از EverybodyWiki Bios & Wiki
پرش به:ناوبری، جستجو

در ساخت کامپایلر ، کاهش قدرت بهینه سازی کامپایلر است که در آن عملیات گران قیمت با عملیات معادل اما ارزان تر جایگزین می شوند. مثال کلاسیک کاهش قدرت ضربات "قوی" در داخل حلقه را به افزودنیهای "ضعیف تر" تبدیل می کند - اتفاقی که اغلب در پرداختن به آرایه رخ می دهد.

نمونه هایی از کاهش قدرت عبارتند از:

  • جایگزینی ضرب در یک حلقه با یک افزودنی
  • یک ضرب را در یک حلق اصلاح کنید

تجزیه و تحلیل کد[ویرایش]

بیشتر زمان اجرای برنامه به طور معمول در یک بخش کوچک از کد (به نام نقطه داغ) سپری می شود ، و آن کد اغلب در داخل یک حلقه است که بارها و بارها اجرا می شود.

یک کامپایلر از روش هایی برای شناسایی حلقه ها و تشخیص خصوصیات مقادیر ثبت در آن حلقه ها استفاده می کند. برای کاهش قدرت ، کامپایلر به آن علاقه مند است

  • متغیرهای حلقه این مقادیر هستند که در بدن یک حلقه تغییر نمی کنند.
  • متغیرهای القایی. اینها مقادیری هستند که هر بار از طریق حلقه تکرار می شوند.

متغیرهای حلقه در اصل ثابت در یک حلقه هستند ، اما ممکن است مقدار آنها در خارج از حلقه تغییر کند. متغیرهای القایی با مقادیر شناخته شده در حال تغییر هستند. شرایط نسبت به یک حلقه خاص است. هنگامی که حلقه ها لانه دار هستند ، یک متغیر القایی در حلقه بیرونی می تواند یک حلقه ثابت در حلقه داخلی باشد.

کاهش قدرت به دنبال عبارات مربوط به متغیر ثابت و متغیر القایی است. برخی از این عبارات را می توان ساده کرد. به عنوان مثال ، ضرب حلقوی ثابت c و متغیر القایی i

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

می تواند با اضافات ضعیف پی در پی جایگزین شود.

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

مثال کاهش قدرت[ویرایش]

در زیر مثالی وجود دارد که باعث می شود تمام ضرب های حلقه ای که از محاسبات آدرس دهی فهرست بندی ناشی از آرایه ایجاد می شود ، کاهش یابد.

حلقه ساده ای را تصور کنید که آرایه ای را به ماتریس هویت می دهد.

for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        A[i,j] = 0.0;
    }
    A[i,i] = 1.0;
}

کد واسطه کامپایلر این کد را به عنوان مشاهده می کند

0010  ; for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        ; i = 0
0040  G0000:
0050      load r2, n                     ; i < n
0060      cmp r1, r2
0070      bge G0001
0080
0090      ; for (j = 0; j < n; j++)
0100        {
0110           r3   = #0                 ; j = 0
0120  G0002:
0130           load r4, n                ; j < n
0140           cmp r3, r4
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0180           load r7, n
0190           r8  = r1 * r7             ; calculate subscript i * n + j
0200           r9  = r8 + r3
0210           r10 = r9 * #8             ; calculate byte address
0220           fr3 = #0.0
0230           fstore fr3, A[r10]
0240
0250           r3 = r3 + #1              ; j++
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0300      load r12, n                    ; calculate subscript i * n + i
0310      r13 = r1 * r12
0320      r14 = r13 + r1
0330      r15 = r14 * #8                 ; calculate byte address
0340      fr4 = #1.0
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380      r1 = r1 + #1
0390      br G0000
0400    }
0410  G0001:

این آرایه 2 بعدی A را به عنوان یک آرایه 1 بعدی با اندازه n * n بیان می کند ، به طوری که هر زمان که کد سطح بالا [A [x ، y را بیان کند ، از نظر داخلی [A [(x * n) + y برای هر شاخص های معتبر x و y داده می شود.

بهینه سازی های بسیاری[ویرایش]

کامپایلر شروع به انجام بسیاری از بهینه سازی ها خواهد کرد - نه تنها کاهش قدرت. عبارات ثابت (ثابت) در داخل حلقه از حلقه خارج می شوند. ثابت ها را می توان در خارج از هر دو حلقه قرار داد - مانند ثبات های شناور fr3 و fr4. تشخیص اینکه برخی از متغیرها تغییر نمی کنند ، امکان ادغام ثبت ها را فراهم می آورد. n ثابت است ، بنابراین r2، r4، r7، r12 می توان آنرا برداشت و فرو ریخت. مقدار مشترک i * n در r8 و r13 محاسبه می شود ، بنابراین آنها به هم می ریزند. حلقه درونی (0120-0260) از 11 به 7 دستورالعمل میانی کاهش یافته است. تنها ضربی که در پایین ترین حلقه باقی مانده است ، ضرب خط 0210 در 8 است.

0010  ; for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        ; i = 0
0050      load r2, n
0130 ;   load r4, n     killed; use r2
0180 ;   load r7, n     killed; use r2
0300 ;   load r12, n    killed; use r2
0220      fr3 = #0.0
0340      fr4 = #1.0
0040  G0000:
0060      cmp r1, r2                     ; i < n
0070      bge G0001
0080
0190      r8  = r1 * r2                  ; calculate subscript i * n
0310 ;   r13 = r1 * r2  killed; use r8   ; calculate subscript i * n
0090      ; for (j = 0; j < n; j++)
0100        {
0110           r3   = #0                 ; j = 0
0120  G0002:
0140           cmp r3, r2                ; j < n
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0200           r9  = r8 + r3             ; calculate subscript i * n + j
0210           r10 = r9 * #8             ; calculate byte address
0230           fstore fr3, A[r10]
0240
0250           r3 = r3 + #1              ; j++
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0320      r14 = r8  + r1                 ; calculate subscript i * n + i
0330      r15 = r14 * #8                 ; calculate byte address
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380      r1 = r1 + #1
0390      br G0000
0400    }
0410  G0001:

برای بهینه سازی های بیشتری وجود دارد. Register r3 متغیر اصلی در پایینترین حلقه (0140-0260) است. هر بار از طریق حلقه 1 عدد افزایش می یابد. Register r8 (که در پایینترین حلقه ثابت است) به r3 اضافه می شود. به جای استفاده از r3 ، کامپایلر می تواند r3 را از بین ببرد و از r9 استفاده کند. حلقه به جای اینکه توسط r3 = 0 تا n-1 کنترل شود ، می تواند توسط r9 = r8 + 0 تا r8 + n-1 کنترل شود. این چهار دستورالعمل را اضافه می کند و چهار دستورالعمل را از بین می برد ، اما یک دستورالعمل کمتری در داخل حلقه وجود دارد.

0110  ;       r3   = #0     killed       ; j = 0
0115           r9   = r8                 ; new assignment
0117           r20  = r8 + r2            ; new limit
0120  G0002:
0140  ;       cmp r3, r2    killed       ; j < n
0145           cmp r9, r20               ; r8 + j < r8 + n = r20
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0200  ;       r9  = r8 + r3 killed       ; calculate subscript i * n + j
0210           r10 = r9 * #8             ; calculate byte address
0230           fstore fr3, A[r10]
0240
0250  ;       r3 = r3 + #1  killed       ; j++
0255           r9 = r9 + #1              ; new loop variable
0260           br G0002

اکنون r9 متغیر حلقه است ، اما با ضرب 8 در تعامل است. در اینجا می توانیم به کاهش قدرت بپردازیم. ضرب 8 را می توان به برخی از پی در پی های 8 کاهش داد. در حال حاضر هیچ ضرب در داخل حلقه وجود ندارد.

0115           r9   = r8                 ; new assignment
0117           r20  = r8 + r2            ; new limit
0118           r10  = r8 * #8            ; initial value of r10
0120  G0002:
0145           cmp r9, r20               ; r8 + j < r8 + n = r20
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0210  ;       r10 = r9 * #8    killed    ; calculate byte address
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0255           r9 = r9 + #1              ; loop variable
0260           br G0002

Register های r9 و (r10 (= 8 * r9 هر دو مورد نیاز نیستند. r9 را می توان در حلقه از بین برد. حلقه اکنون 5 دستورالعمل است.

0115  ;       r9   = r8         killed
0117           r20  = r8 + r2            ; limit
0118           r10  = r8 * #8            ; initial value of r10
0119           r22  = r20 * #8           ; new limit
0120  G0002:
0145  ;       cmp r9, r20       killed   ; r8 + j < r8 + n = r20
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0255  ;       r9 = r9 + #1      killed   ; loop variable
0260           br G0002

حلقه بیرونی بازگشت به کل تصویر:

0010  ; for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        ; i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0040  G0000:
0060      cmp r1, r2                     ; i < n
0070      bge G0001
0080
0190      r8   = r1 * r2                 ; calculate subscript i * n
0117      r20  = r8 + r2                 ; limit
0118      r10  = r8 * #8                 ; initial value of r10
0119      r22  = r20 * #8                ; new limit
0090      ; for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0320      r14 = r8  + r1                 ; calculate subscript i * n + i
0330      r15 = r14 * #8                 ; calculate byte address
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380      r1 = r1 + #1
0390      br G0000
0400    }
0410  G0001:

اکنون چهار ضرب در حلقه بیرونی وجود دارد که R1 را افزایش می دهد. می توانید با تنظیم کردن آن قبل از ورود به حلقه (0055) و افزایش آن توسط r2 در پایین حلقه (0385) از قدرت r8 = r1 * r2 در 0190 استفاده کنید.

مقدار r8 * 8 (با شماره 0118) می تواند با مقدار دهی اولیه آن (0056) کاهش یابد و با افزایش R8 (0386) 8 * r2 به آن اضافه شود.

Register r20 توسط متغیر ثابت / ثابت r2 هر بار از طریق حلقه در 0117 افزایش می یابد. پس از افزایش ، با ایجاد 8 برای ایجاد r22 در 0119 ضرب می شود. این ضرب می تواند با افزودن 8 * r2 هر بار از طریق حلقه قدرت کاهش یابد.

0010  ; for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        ; i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055      r8  = r1 * r2                  ; set initial value for r8
0056      r40 = r8 * #8                  ; initial value for r8 * 8
0057      r30 = r2 * #8                  ; increment for r40
0058      r20 = r8 + r2                  ; copied from 0117
0058      r22 = r20 * #8                 ; initial value of r22
0040  G0000:
0060      cmp r1, r2                     ; i < n
0070      bge G0001
0080
0190  ;  r8   = r1 * r2    killed        ; calculate subscript i * n
0117  ;  r20  = r8 + r2    killed - dead code
0118      r10  = r40                     ; strength reduced expression to r40
0119  ;  r22  = r20 * #8   killed        ; strength reduced
0090      ; for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0320      r14 = r8  + r1                 ; calculate subscript i * n + i
0330      r15 = r14 * #8                 ; calculate byte address
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380      r1  = r1 + #1
0385      r8  = r8 + r2                  ; strength reduce r8 = r1 * r2
0386      r40 = r40 + r30                ; strength reduce expression r8 * 8
0388      r22 = r22 + r30                ; strength reduce r22 = r20 * 8
0390      br G0000
0400    }
0410  G0001:

آخرین ضرب این دو حلقه تنها با یک عمل ضرب (در 0330) در حلقه بیرونی باقی می ماند و هیچ ضرب در حلقه داخلی وجود ندارد.

0010  ; for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        ; i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055      r8  = r1 * r2                  ; set initial value for r8
0056      r40 = r8 * #8                  ; initial value for r8 * 8
0057      r30 = r2 * #8                  ; increment for r40
0058      r20 = r8 + r2                  ; copied from 0117
0058      r22 = r20 * #8                 ; initial value of r22
0040  G0000:
0060      cmp r1, r2                     ; i < n
0070      bge G0001
0080
0118      r10  = r40                     ; strength reduced expression to r40
0090      ; for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0320      r14 = r8  + r1                 ; calculate subscript i * n + i
0330      r15 = r14 * #8                 ; calculate byte address
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380      r1  = r1 + #1
0385      r8  = r8 + r2                  ; strength reduce r8 = r1 * r2
0386      r40 = r40 + r30                ; strength reduce expression r8 * 8
0388      r22 = r22 + r30                ; strength reduce r22 = r20 * 8
0390      br G0000
0400    }
0410  G0001:

در خط 0320 ، r14 مجموع r8 و r1 است ، و r8 و r1 در حلقه افزایش می یابد. Register r8 توسط r2 (= n) bumped می شود و r1 توسط 1 انجام می شود. در نتیجه ، r14 هر بار از طریق حلقه توسط n + 1 bumped می شود. آخرین ضرب حلقه در 0330 می تواند با افزودن r2 + 1) * 8) هر بار از طریق حلقه قدرت کاهش یابد.

0010  ; for (i = 0, i < n; i++)
0020    {
0030      r1 = #0                        ; i = 0
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055      r8  = r1 * r2                  ; set initial value for r8
0056      r40 = r8 * #8                  ; initial value for r8 * 8
0057      r30 = r2 * #8                  ; increment for r40
0058      r20 = r8 + r2                  ; copied from 0117
0058      r22 = r20 * #8                 ; initial value of r22
005A      r14 = r8 + r1                  ; copied from 0320
005B      r15 = r14 * #8                 ; initial value of r15 (0330)
005C      r49 = r2 + #1
005D      r50 = r49 * #8                 ; strength reduced increment
0040  G0000:
0060      cmp r1, r2                     ; i < n
0070      bge G0001
0080
0118      r10  = r40                     ; strength reduced expression to r40
0090      ; for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0320  ;  r14 = r8  + r1     killed      ; dead code
0330  ;  r15 = r14 * #8     killed      ; strength reduced
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380      r1  = r1 + #1
0385      r8  = r8 + r2                  ; strength reduce r8 = r1 * r2
0386      r40 = r40 + r30                ; strength reduce expression r8 * 8
0388      r22 = r22 + r30                ; strength reduce r22 = r20 * 8
0389      r15 = r15 + r50                ; strength reduce r15 = r14 * 8
0390      br G0000
0400    }
0410  G0001:

هنوز چیزهای بیشتری برای رفتن وجود دارد تاشو ثابت ، r1 = 0 را در مقدمه تشخیص می دهد ، بنابراین چندین دستورالعمل تمیز می شوند. ثبت r8 در حلقه استفاده نمی شود ، بنابراین می تواند ناپدید شود. علاوه بر این ، r1 فقط برای کنترل حلقه مورد استفاده قرار می گیرد ، بنابراین r1 را می توان با یک متغیر القایی متفاوت مانند R40 جایگزین کرد. از کجا رفتم 0 <= i <n ، Register r40 می رود 0 <= r40 <8 * n * n.

0010  ; for (i = 0, i < n; i++)
0020    {
0030  ;  r1 = #0                        ; i = 0, becomes dead code
0050      load r2, n
0220      fr3 = #0.0
0340      fr4 = #1.0
0055  ;  r8  = #0         killed         ; r8 no longer used
0056      r40 = #0                       ; initial value for r8 * 8
0057      r30 = r2 * #8                  ; increment for r40
0058  ;  r20 = r2         killed         ; r8 = 0, becomes dead code
0058      r22 = r2  * #8                 ; r20 = r2
005A  ;  r14 =       #0   killed         ; r8 = 0, becomes dead code
005B      r15 =       #0                 ; r14 = 0
005C      r49 = r2 + #1
005D      r50 = r49 * #8                 ; strength reduced increment
005D      r60 = r2 * r30                 ; new limit for r40
0040  G0000:
0060  ;  cmp r1, r2       killed         ; i < n; induction variable replaced
0065      cmp r40, r60                   ; i * 8 * n < 8 * n * n
0070      bge G0001
0080
0118      r10  = r40                     ; strength reduced expression to r40
0090      ; for (j = 0; j < n; j++)
0100        {
0120  G0002:
0147           cmp r10, r22              ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22
0150           bge G0003
0160
0170           ; A[i,j] = 0.0;
0230           fstore fr3, A[r10]
0240
0245           r10 = r10 + #8            ; strength reduced multiply
0260           br G0002
0270        }
0280  G0003:
0290      ; A[i,i] = 1.0;
0350      fstore fr4, A[r15]
0360
0370      ;i++
0380  ;  r1  = r1 + #1      killed       ; dead code (r40 controls loop)
0385  ;  r8  = r8 + r2      killed       ; dead code
0386      r40 = r40 + r30                ; strength reduce expression r8 * 8
0388      r22 = r22 + r30                ; strength reduce r22 = r20 * 8
0389      r15 = r15 + r50                ; strength reduce r15 = r14 * 8
0390      br G0000
0400    }
0410  G0001:

سایر عملیات کاهش قدرت[ویرایش]

این ماده مورد اختلاف است. بهتر است به عنوان بهینه سازی پیله و تکالیف دستورالعمل توصیف شود.

کاهش قدرت اپراتور از هویت ریاضی برای جایگزینی عملیات ریاضی کند با عملیات سریعتر استفاده می کند. مزایای آن به CPU هدف و بعضی اوقات به کد اطراف آن بستگی دارد (که می تواند در دسترس بودن سایر واحدهای کاربردی درون CPU تأثیر بگذارد).

جایگزینی تقسیم عدد صحیح یا ضرب با توان 2 با یک تغییر حسابی یا تغییر منطقی

جایگزینی ضرب عدد صحیح توسط ثابت با ترکیبی از شیفت ، اضافه یا تفریق

جایگزینی تقسیم عدد صحیح توسط یک ثابت با ضرب ، با بهره گیری از محدوده عدد صحیح دستگاه ها. این روش همچنین در صورتی کار می کند که تقسیم کننده یک عدد غیر کامل به اندازه کافی بزرگتر از 1 باشد ، به عنوان مثال or2 یا π.

محاسبه جایگزینی محاسبه اصلی
y = x >> 3 y = x / 8
y = x << 6 y = x * 64
y = x << 1 y = x * 2
y = (x << 4) - x y = x * 15
y = ((uint32_t)x * (uint32_t)0xCCCD) >> 19) y = x / 10 (where x is of type uint16_t)
y = (((uint32_t)x * (uint32_t)0x45F3) >> 16) + x) >> 2) y = x / π (where x is of type uint16_t)

متغیر القایی (یتیم)[ویرایش]

متغیر القایی یا کاهش قدرت بازگشتی ، تابع برخی از متغیرهای در حال تغییر سیستماتیک را با یک محاسبه ساده تر با استفاده از مقادیر قبلی تابع جایگزین می کند. در یک زبان برنامه نویسی رویه ای این عبارت در مورد عبارات مربوط به متغیر حلقه و در یک زبان اعلامی برای استدلال یک عملکرد بازگشتی اعمال می شود. مثلا،

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

تبدیل می شود

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

در اینجا عملکرد بازگشتی تغییر یافته f ′ پارامتر دوم z = 3 ** x را در اختیار شما قرار می دهد و اجازه می دهد محاسبات گران قیمت (3 * x) با ارزانتر (3 * z) جایگزین شود.

جستار های وابسته[ویرایش]

یادداشت[ویرایش]

  1. Steven Muchnick; Muchnick and Associates (15 August 1997) Advanced Compiler Design Implementation.Morgan Kaufmann.ISBN 978-1-55860-320-2

منابع[ویرایش]

This article "کاهش فشار" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:کاهش فشار. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.



Read or create/edit this page in another language[ویرایش]