کاهش قدرت کیست؟ توضیح بده.
در ساخت کامپایلر ، کاهش قدرت یک روش بهینه سازی کامپایلر است که در آن عملیات های پر هزینه با عملیات معادل اما کم هزینه تر جایگزین می شوند. مثال برای کاهش قدرتی ضرب های "قوی" در داخل حلقه را به جمع های "ضعیف تر" تبدیل می کند – چیزی که غالباً در آدرس دهی آرایه اتفاق می افتد. مثال هایی از کاهش قدرت عبارتند از: تجزیه و تحلیل کد.بیشتر زمان اجرای برنامه به طور معمول در یک بخش کوچک از کد (به نام منطقه داغ ) سپری می شود ، و آن بخش از کد اغلب در داخل یک حلقه است که بارها و بارها اجرا می شود. کامپایلر از روش هایی برای شناسایی حلقه ها و تشخیص ویژگی های مقادیر در آن حلقه ها استفاده می کند. برای کاهش قدرت ،به داده های زیر نیازمند است : ثابت های حلقه(Loop invariants) در اصل درون یک حلقه ثابت هستند ، اما ممکن است مقدار آنها در خارج از حلقه تغییر کنند. متغیرهای القایی با مقادیر شناخته شده(خاصی) در حال تغییر هستند. شرایط نسبت به یک حلقه خاص است. هنگامی که حلقه ها تودرتو باشند ، یک متغیر القایی در یک حلقه بیرونی می تواند یک ثابت حلقه ای (Loop invariants) در یک حلقه داخلی باشد. کاهش قدرت به دنبال عباراتی که شامل ثابت حلقه ای (Loop invariants)و متغیر القایی می گردد. برخی از این عبارات را می توان ساده سازی کرد. به عنوان مثال ، ضرب ثابت حلقه ای codice_1 و متغیر القایی codice_2 c = 7;for (i = 0; i &lt; N; i++) y[i] = c * i; می تواند با جمع های ضعیف تر پی در پی جایگزین شود c = 7;k = 0;for (i = 0; i &lt; N; i++) y[i] = k; k = k + c;مثال روش کاهش قدرت.در زیر مثالی وجود دارد که تمام ضرب های داخل حلقه که از محاسبات آدرس دهی فهرست بندی آرایه (array indexing address calculations)به وجود آمده اند با روش کاهش قدرت ،بهینه سازد. یک حلقه ساده را تصور کنید که یک آرایه را به یک ماتریس هویت(identity matrix) می نشاند . for (i = 0; i &lt; n; i++) for (j = 0; j &lt; n; j++) A[i,j] = 0.0; A[i,i] = 1.0;کد واسطه.کامپایلر کد زیر را به عنوان گزاره زیر میبیند : 0010 ; for (i = 0, i &lt; n; i++)0020 {0030 r1 = #0 ; i = 00040 G0000:0050 load r2, n ; i &lt; n0060 cmp r1, r20070 bge G000100800090 ; for (j = 0; j &lt; n; j++)0100 {0110 r3 = #0 ; j = 00120 G0002:0130 load r4, n ; j &lt; n0140 cmp r3, r40150 bge G000301600170 ; A[i,j] = 0.0;0180 load r7, n0190 r8 = r1 * r7 ; calculate subscript i * n + j0200 r9 = r8 + r30210 r10 = r9 * #8 ; calculate byte address0220 fr3 = #0.00230 fstore fr3, A[r10]02400250 r3 = r3 + #1 ; j++0260 br G00020280 G0003:0290 ; A[i,i] = 1.0;0300 load r12, n ; calculate subscript i * n + i0310 r13 = r1 * r120320 r14 = r13 + r10330 r15 = r14 * #8 ; calculate byte address0340 fr4 = #1.00350 fstore fr4, A[r15]03600370 ;i++0380 r1 = r1 + #10390 br G00000410 G0001: این کد آرایه 2 بعدی "A را" به عنوان یک آرایه 1 بعدی با ابعاد n * n تبدیل میکند ، به طوری که هر زمان که کد سطح بالا A [x ، y] را فرا میخواند ، از نظر داخلی(کامپایلر) A [(x * n) + y] برای هر مقدار معتبر x و y داده می شود. بهینه سازی های دیگر.کامپایلر شروع به انجام بسیاری از بهینه سازی های دیگر خواهد کرد – نه تنها کاهش قدرت. عباراتی که ثابت (invariant) در یک حلقه خارج از حلقه برافراشته(hoisted) هستند . ثابت ها را می توان در خارج از هر دو حلقه قرار داد - مانند ثبات های اعشاری fr3 و fr4. تشخیص اینکه برخی از متغیرها تغییر نمی‌کنند ، امکان ادغام ثبات ها را فراهم می آورد. n ثابت است ، بنابراین r2، r4، r7، r12 می توان آن ها را برافراشت و یا از بین برد. مقدار مشترک i * n در r8 و r13 (برافراشته)محاسبه می شود ، بنابراین آنها از بین می روند. درونی ترین حلقه (0120-0260) از 11 به 7 دستورالعمل میانی کاهش یافته است. تنها ضربی که در پایین ترین حلقه باقی مانده است ، ضرب 8 در خط 0210 است. 0010 ; for (i = 0, i &lt; n; i++)0020 {0030 r1 = #0 ; i = 00050 load r2, n0130 ; load r4, n killed; use r20180 ; load r7, n killed; use r20300 ; load r12, n killed; use r20220 fr3 = #0.00340 fr4 = #1.00040 G0000:0060 cmp r1, r2 ; i &lt; n0070 bge G000100800190 r8 = r1 * r2 ; calculate subscript i * n0310 ; r13 = r1 * r2 killed; use r8 ; calculate subscript i * n0090 ; for (j = 0; j &lt; n; j++)0100 {0110 r3 = #0 ; j = 00120 G0002:0140 cmp r3, r2 ; j &lt; n0150 bge G000301600170 ; A[i,j] = 0.0;0200 r9 = r8 + r3 ; calculate subscript i * n + j0210 r10 = r9 * #8 ; calculate byte address0230 fstore fr3, A[r10]02400250 r3 = r3 + #1 ; j++0260 br G00020280 G0003:0290 ; A[i,i] = 1.0;0320 r14 = r8 + r1 ; calculate subscript i * n + i0330 r15 = r14 * #8 ; calculate byte address0350 fstore fr4, A[r15]03600370 ;i++0380 r1 = r1 + #10390 br G00000410 G0001: برای بهینه سازی راه های بیشتری وجود دارد. ثبات r3 که متغیر اصلی است در درونی ترین حلقه (0140-0260) است. هر بار از طریق حلقه 1 عدد افزایش می یابد. ثبات r8 (که در درونی ترین حلقه ،ثابت (invariant )است) به r3 اضافه می شود. به جای استفاده از r3 ، کامپایلر می تواند r3 را از بین ببرد و از r9 استفاده کند. حلقه به جای اینکه توسط r3 = 0 تا n-1 کنترل شود ، می تواند توسط r9 = r8 + 0 تا r8 + n-1 کنترل شود. این عملیات چهار دستورالعمل را اضافه می کند و چهار دستورالعمل را از بین می برد ، اما اکنون یک دستورالعمل کمتر در داخل حلقه وجود دارد. 0110 ; r3 = #0 killed ; j = 00115 r9 = r8 ; new assignment0117 r20 = r8 + r2 ; new limit0120 G0002:0140 ; cmp r3, r2 killed ; j &lt; n0145 cmp r9, r20 ; r8 + j &lt; r8 + n = r200150 bge G000301600170 ; A[i,j] = 0.0;0200 ; r9 = r8 + r3 killed ; calculate subscript i * n + j0210 r10 = r9 * #8 ; calculate byte address0230 fstore fr3, A[r10]02400250 ; r3 = r3 + #1 killed ; j++0255 r9 = r9 + #1 ; new loop variable0260 br G0002 اکنون r9 متغیر حلقه است ، ولی با ضرب 8 تعامل دارد. در اینجا ما می توانیم با روش کاهش قدرت بهینه سازی انجام دهیم. ضرب در 8 را می توان به جمع های پی در پی 8 کاهش داد. اکنون هیچ ضرب در داخل حلقه وجود ندارد. 0115 r9 = r8 ; new assignment0117 r20 = r8 + r2 ; new limit0118 r10 = r8 * #8 ; initial value of r100120 G0002:0145 cmp r9, r20 ; r8 + j &lt; r8 + n = r200150 bge G000301600170 ; A[i,j] = 0.0;0210 ; r10 = r9 * #8 killed ; calculate byte address0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; strength reduced multiply0255 r9 = r9 + #1 ; loop variable0260 br G0002 ثبات های r9 و r10 (= 8 * r9) هر دو دیگر مورد نیاز نیستند. r9 را می توان در داخل حلقه از بین برد. حلقه اکنون 5 دستورالعمل است. 0115 ; r9 = r8 killed0117 r20 = r8 + r2 ; limit0118 r10 = r8 * #8 ; initial value of r100119 r22 = r20 * #8 ; new limit0120 G0002:0145 ; cmp r9, r20 killed ; r8 + j &lt; r8 + n = r200147 cmp r10, r22 ; r10 = 8*(r8 + j) &lt; 8*(r8 + n) = r220150 bge G000301600170 ; A[i,j] = 0.0;0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; strength reduced multiply0255 ; r9 = r9 + #1 killed ; loop variable0260 br G0002حلقه بیرونی.حال به کل کد نگاه میکنیم: 0010 ; for (i = 0, i &lt; n; i++)0020 {0030 r1 = #0 ; i = 00050 load r2, n0220 fr3 = #0.00340 fr4 = #1.00040 G0000:0060 cmp r1, r2 ; i &lt; n0070 bge G000100800190 r8 = r1 * r2 ; calculate subscript i * n0117 r20 = r8 + r2 ; limit0118 r10 = r8 * #8 ; initial value of r100119 r22 = r20 * #8 ; new limit0090 ; for (j = 0; j &lt; n; j++)0100 {0120 G0002:0147 cmp r10, r22 ; r10 = 8*(r8 + j) &lt; 8*(r8 + n) = r220150 bge G000301600170 ; A[i,j] = 0.0;0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; strength reduced multiply0260 br G00020280 G0003:0290 ; A[i,i] = 1.0;0320 r14 = r8 + r1 ; calculate subscript i * n + i0330 r15 = r14 * #8 ; calculate byte address0350 fstore fr4, A[r15]03600370 ;i++0380 r1 = r1 + #10390 br G00000410 G0001: اکنون چهار ضرب در حلقه بیرونی وجود دارد که ثبات R1 را افزایش می دهند. ثبات r8 = r1*r2 در خط 0190 با روش کاهش قدرت میتواند قبل از ورود به حلقه (0055) و افزایشش توسط ثبات r2 در انتهای حلقه (0385) مقدار دهی شود . مقدار r8 * 8 (با شماره 0118) می تواند با مقدار دهی اولیه آن (0056) با کاهش قدرت و افزودن 8 * r2 به آن هنگام افزایش r8 (0386) مقدار آن کاهش یابد. ثبات r20 توسط متغیر ثابت R2 هر بار از طریق حلقه در 0117 خط افزایش می یابد. پس از افزایش ، در 8 ضرب می شود تا r22 در 0119 را بوجود آورد. این ضرب میتواند با روش کاهشی قدرتی با اضافه کردن 8 * r2در هر تکرار بار حلقه بهینه سازی شود. 0010 ; for (i = 0, i &lt; n; i++)0020 {0030 r1 = #0 ; i = 00050 load r2, n0220 fr3 = #0.00340 fr4 = #1.00055 r8 = r1 * r2 ; set initial value for r80056 r40 = r8 * #8 ; initial value for r8 * 80057 r30 = r2 * #8 ; increment for r400058 r20 = r8 + r2 ; copied from 01170058 r22 = r20 * #8 ; initial value of r220040 G0000:0060 cmp r1, r2 ; i &lt; n0070 bge G000100800190 ; r8 = r1 * r2 killed ; calculate subscript i * n0117 ; r20 = r8 + r2 killed - dead code0118 r10 = r40 ; strength reduced expression to r400119 ; r22 = r20 * #8 killed ; strength reduced0090 ; for (j = 0; j &lt; n; j++)0100 {0120 G0002:0147 cmp r10, r22 ; r10 = 8*(r8 + j) &lt; 8*(r8 + n) = r220150 bge G000301600170 ; A[i,j] = 0.0;0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; strength reduced multiply0260 br G00020280 G0003:0290 ; A[i,i] = 1.0;0320 r14 = r8 + r1 ; calculate subscript i * n + i0330 r15 = r14 * #8 ; calculate byte address0350 fstore fr4, A[r15]03600370 ;i++0380 r1 = r1 + #10385 r8 = r8 + r2 ; strength reduce r8 = r1 * r20386 r40 = r40 + r30 ; strength reduce expression r8 * 80388 r22 = r22 + r30 ; strength reduce r22 = r20 * 80390 br G00000410 G0001:آخرین ضرب.در آخر این دو حلقه ب که تنها با یک عمل ضرب (در 0330) در حلقه بیرونی و هیچ ضرب در حلقه درونی باقی می مانند. 0010 ; for (i = 0, i &lt; n; i++)0020 {0030 r1 = #0 ; i = 00050 load r2, n0220 fr3 = #0.00340 fr4 = #1.00055 r8 = r1 * r2 ; set initial value for r80056 r40 = r8 * #8 ; initial value for r8 * 80057 r30 = r2 * #8 ; increment for r400058 r20 = r8 + r2 ; copied from 01170058 r22 = r20 * #8 ; initial value of r220040 G0000:0060 cmp r1, r2 ; i &lt; n0070 bge G000100800118 r10 = r40 ; strength reduced expression to r400090 ; for (j = 0; j &lt; n; j++)0100 {0120 G0002:0147 cmp r10, r22 ; r10 = 8*(r8 + j) &lt; 8*(r8 + n) = r220150 bge G000301600170 ; A[i,j] = 0.0;0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; strength reduced multiply0260 br G00020280 G0003:0290 ; A[i,i] = 1.0;0320 r14 = r8 + r1 ; calculate subscript i * n + i0330 r15 = r14 * #8 ; calculate byte address0350 fstore fr4, A[r15]03600370 ;i++0380 r1 = r1 + #10385 r8 = r8 + r2 ; strength reduce r8 = r1 * r20386 r40 = r40 + r30 ; strength reduce expression r8 * 80388 r22 = r22 + r30 ; strength reduce r22 = r20 * 80390 br G00000410 G0001: در خط 0320 ، r14 مجموع r8 و r1 است ، و r8 و r1 در حلقه افزایش می یابد. ثبات r8 توسط r2 (= n) = افزایش میابد(bumped ) و r1 توسط 1 افزایش میابد . در نتیجه ، r14 در هر بار تکرار حلقه n + 1 افزایش می یابد. آخرین ضرب حلقه ، در خط 0330 می تواند با روش کاهش قدرتی با افزودن (r2 + 1) * 8 در هر تکرار حلقه بهینه شود . 0010 ; for (i = 0, i &lt; n; i++)0020 {0030 r1 = #0 ; i = 00050 load r2, n0220 fr3 = #0.00340 fr4 = #1.00055 r8 = r1 * r2 ; set initial value for r80056 r40 = r8 * #8 ; initial value for r8 * 80057 r30 = r2 * #8 ; increment for r400058 r20 = r8 + r2 ; copied from 01170058 r22 = r20 * #8 ; initial value of r22005A r14 = r8 + r1 ; copied from 0320005B r15 = r14 * #8 ; initial value of r15 (0330)005C r49 = r2 + #1005D r50 = r49 * #8 ; strength reduced increment0040 G0000:0060 cmp r1, r2 ; i &lt; n0070 bge G000100800118 r10 = r40 ; strength reduced expression to r400090 ; for (j = 0; j &lt; n; j++)0100 {0120 G0002:0147 cmp r10, r22 ; r10 = 8*(r8 + j) &lt; 8*(r8 + n) = r220150 bge G000301600170 ; A[i,j] = 0.0;0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; strength reduced multiply0260 br G00020280 G0003:0290 ; A[i,i] = 1.0;0320 ; r14 = r8 + r1 killed ; dead code0330 ; r15 = r14 * #8 killed ; strength reduced0350 fstore fr4, A[r15]03600370 ;i++0380 r1 = r1 + #10385 r8 = r8 + r2 ; strength reduce r8 = r1 * r20386 r40 = r40 + r30 ; strength reduce expression r8 * 80388 r22 = r22 + r30 ; strength reduce r22 = r20 * 80389 r15 = r15 + r50 ; strength reduce r15 = r14 * 80390 br G00000410 G0001: هنوز کار های بیشتری برای انجام هست. تاشو ثابت(Constant folding) r1 = 0 را در مقدمه کد شناسایی میکند ، بنابراین چندین دستورالعمل تمیز می شوند(کاهش میابند). ثبات r8 در حلقه استفاده نمی‌شود ، بنابراین می تواند از بین برود علاوه بر این ، r1 فقط برای کنترل حلقه مورد استفاده قرار گرفته است ، پس r1 را می توان با یک متغیر القایی متفاوت مانند R40 جایگزین کرد. زیرا جایی که متغیر i از 0 تا n تغیر میکند ، ثبات r40 از 0 تا8 * n * n تغییر میکند . 0010 ; for (i = 0, i &lt; n; i++)0020 {0030 ; r1 = #0 ; i = 0, becomes dead code0050 load r2, n0220 fr3 = #0.00340 fr4 = #1.00055 ; r8 = #0 killed ; r8 no longer used0056 r40 = #0 ; initial value for r8 * 80057 r30 = r2 * #8 ; increment for r400058 ; r20 = r2 killed ; r8 = 0, becomes dead code0058 r22 = r2 * #8 ; r20 = r2005A ; r14 = #0 killed ; r8 = 0, becomes dead code005B r15 = #0 ; r14 = 0005C r49 = r2 + #1005D r50 = r49 * #8 ; strength reduced increment005D r60 = r2 * r30 ; new limit for r400040 G0000:0060 ; cmp r1, r2 killed ; i &lt; n; induction variable replaced0065 cmp r40, r60 ; i * 8 * n &lt; 8 * n * n0070 bge G000100800118 r10 = r40 ; strength reduced expression to r400090 ; for (j = 0; j &lt; n; j++)0100 {0120 G0002:0147 cmp r10, r22 ; r10 = 8*(r8 + j) &lt; 8*(r8 + n) = r220150 bge G000301600170 ; A[i,j] = 0.0;0230 fstore fr3, A[r10]02400245 r10 = r10 + #8 ; strength reduced multiply0260 br G00020280 G0003:0290 ; A[i,i] = 1.0;0350 fstore fr4, A[r15]03600370 ;i++0380 ; r1 = r1 + #1 killed ; dead code (r40 controls loop)0385 ; r8 = r8 + r2 killed ; dead code0386 r40 = r40 + r30 ; strength reduce expression r8 * 80388 r22 = r22 + r30 ; strength reduce r22 = r20 * 80389 r15 = r15 + r50 ; strength reduce r15 = r14 * 80390 br G00000410 G0001:سایر عملیات کاهش قدرت.اپراتور روش کاهش قدرت ،از ریاضیات برای جایگزینی عملیات ها یواش با عملیات های سریع استفاده میکند. مزایا به پردازنده (CPU) هدف و گاهی اوقات به کد های اطراف(که میتواند بر در دسترس بودن واحد های کاری درون پردازنده تاثیر داشته باشد) بستگی دارد. متغیر القایی (یتیم).متغیر القایی یا کاهش قدرت بازگشتی ، تابع برخی از متغیرهای در حال تغییر سیستماتیک را با یک محاسبه ساده تر با استفاده از مقادیر قبلی تابع جایگزین می کند. در یک زبان برنامه نویسی روندی() این عبارت برای یک عبارت شامل متغیر حلقه ای کاربرد دارد و در یک زبان اعلامی برای استدلال یک تابع بازگشتی اعمال می شود . مثلاً، 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) جایگزین شود.