ما الذي يعتبر التقليب؟

Question

لنفترض أن لدي برنامج C هو:

For i=0 to 10
    x++
    a=2+x*5
next

هل عدد التقلبات لهذا (1 [x ++]+1 [x * 5]+1 [2+ (x+5))] * 10 [حلقة] ، لـ 30 flops؟ أواجه مشكلة في فهم ماهية التقليب.

لاحظ أن [...] يشير إلى المكان الذي أحصل فيه على "العمليات" من.

Answer 1

لأغراض قياسات التقليب ، عادة ما يتم تضمين الإضافات والتكاثر فقط. أشياء مثل الانقسامات والمتبادلين والجذور المربعة والوظائف المتعالية مكلفة للغاية بحيث لا يمكن تضمينها كعملية واحدة ، في حين أن أشياء مثل الأحمال والمتاجر تافهة للغاية.

بمعنى آخر ، يحتوي جسمك الحلقة على إضافة 2 و 1 مضاعفة ، لذلك (على افتراض x هو نقطة عائمة) كل تكرار حلقة هو 3 OPS. إذا قمت بتشغيل الحلقة 10 مرات ، فقد قمت بـ 30 OPS.

لاحظ أنه عند قياس MIPs ، ستكون الحلقة الخاصة بك أكثر من 3 تعليمات لأنها تتضمن أيضًا أحمالًا ومتاجر لا يتم احتساب قياسها.

Answer 2

يتخبط تعني العمليات العائمة في الثانية. إذا كنت تتعامل مع أعداد صحيحة ، فلا يوجد لديك أي عمليات عائمة في الكود الخاص بك.

Answer 3

أوضحت الملصقات أن التقلب (مفصل هنا) تهتم بعمليات النقطة العائمة (على عكس عدد صحيح) في الثانية, ، لذلك ليس عليك فقط حساب عدد العمليات التي تقوم بها ، ولكن في أي فترة من الزمن.

إذا كانت "X" و "A" عوامات ، فأنت تقوم بمحاولة جيدة لحساب عدد العمليات في التعليمات البرمجية الخاصة بك ، ولكن عليك التحقق من رمز الكائن للتأكد من أن كمية تعليمات النقطة العائمة تستخدم بالفعل . على سبيل المثال ، إذا لم يتم استخدام "A" في وقت لاحق ، فقد لا يزعج برنامج التحويل البرمجي تحسينه لحسابه.

أيضًا ، قد تكون بعض العمليات العائمة (مثل الإضافة) أسرع بكثير من غيرها (مثل الضرب) ، لذلك يمكن أن تعمل حلقة من الإضافة فقط في العديد من التقلبات أكثر من حلقة من مضاعفات تعويم فقط على نفس الجهاز.

Answer 4

تشير التقلبات (يشير Shedrase S إلى صيغة التقليب ، لكل تعليق Martinho Fernandes) إلى تعليمات النقطة العائمة لغة الماكينة ، لذلك يعتمد على عدد التعليمات التي يتم تجميع الكود الخاص بك إلى.

أولاً ، إذا كانت كل هذه المتغيرات هي أعداد صحيحة ، فلا توجد زحافات في هذا الرمز. لنفترض ، مع ذلك ، أن لغتك تتعرف على كل هذه الثوابت والمتغيرات كمتغيرات عائمة ذات دقة واحدة (باستخدام الدقة الواحدة يجعل تحميل الثوابت أسهل).

يمكن أن يتجمع هذا الرمز إلى (على MIPS):

Assignment of variables: x is in $f1, a is in $f2, i is in $f3.
All other floating point registers are compiler-generated temporaries.
$f4 stores the loop exit condition of 10.0
$f5 stores the floating point constant 1.0
$f6 stores the floating point constant 2.0
$t1 is an integer register used for loading constants
    into the floating point coprocessor.

     lui $t1, *upper half of 0.0*
     ori $t1, $t1,  *lower half of 0.0*
     lwc1 $f3, $t1
     lui $t1, *upper half of 10.0*
     ori $t1, $t1,  *lower half of 10.0*
     lwc1 $f4, $t1
     lui $t1, *upper half of 1.0*
     ori $t1, $t1,  *lower half of 1.0*
     lwc1 $f5, $t1
     lui $t1, *upper half of 2.0*
     ori $t1, $t1,  *lower half of 2.0*
     lwc1 $f6, $t1
st:  c.gt.s $f3, $f4
     bc1t end
     add.s $f1, $f1, $f5
     lui $t1, *upper half of 5.0*
     ori $t1, $t1,  *lower half of 5.0*         
     lwc1 $f2, $t1
     mul.s $f2, $f2, $f1
     add.s $f2, $f2, $f6
     add.s $f3, $f3, $f5
     j st
end: # first statement after the loop

لذلك وفقًا لتعريف Gabe ، هناك 4 تتخبط داخل الحلقة (3x add.s و 1x mul.s). هناك 5 تتخبط إذا قمت أيضًا بحساب مقارنة الحلقة c.gt.s. اضرب هذا بمقدار 10 لما مجموعه 40 (أو 50) يتخبط من قبل البرنامج.

قد يدرك برنامج التحويل البرمجي الأفضل تحسينًا أن قيمة a لا تستخدم داخل الحلقة ، لذلك يحتاج فقط إلى حساب القيمة النهائية لـ a. يمكن أن يولد رمزًا يبدو

     lui $t1, *upper half of 0.0*
     ori $t1, $t1,  *lower half of 0.0*
     lwc1 $f3, $t1
     lui $t1, *upper half of 10.0*
     ori $t1, $t1,  *lower half of 10.0*
     lwc1 $f4, $t1
     lui $t1, *upper half of 1.0*
     ori $t1, $t1,  *lower half of 1.0*
     lwc1 $f5, $t1
     lui $t1, *upper half of 2.0*
     ori $t1, $t1,  *lower half of 2.0*
     lwc1 $f6, $t1
st:  c.gt.s $f3, $f4
     bc1t end
     add.s $f1, $f1, $f5
     add.s $f3, $f3, $f5
     j st
end: lui $t1, *upper half of 5.0*
     ori $t1, $t1,  *lower half of 5.0*         
     lwc1 $f2, $t1
     mul.s $f2, $f2, $f1
     add.s $f2, $f2, $f6

في هذه الحالة ، لديك 2 إضافات ومقارنة واحدة داخل الحلقة (تمنحك 10 أو 30 أو 30 زحفًا) ، بالإضافة إلى 1 مضاعفة وإضافة واحدة خارج الحلقة. وبالتالي ، يستغرق برنامجك الآن 22 أو 32 يتخبط اعتمادًا على ما إذا كنا نحسب المقارنات.

Answer 5

هل X عدد صحيح أم متغير نقطة عائمة؟ إذا كان عدد صحيح ، فقد لا تحتوي الحلقة الخاصة بك على أي تقلبات.