لماذا يكون SSE العددي sqrt(x) أبطأ من rsqrt(x) * x؟

Question

لقد قمت بتوصيف بعض من الرياضيات الأساسية لدينا على Intel Core Duo، وأثناء النظر في الأساليب المختلفة للجذر التربيعي لاحظت شيئًا غريبًا:باستخدام عمليات SSE العددية، يكون من الأسرع أخذ جذر تربيعي متبادل وضربه للحصول على sqrt، بدلاً من استخدام كود تشغيل sqrt الأصلي!

أقوم باختباره باستخدام حلقة مثل:

inline float TestSqrtFunction( float in );

void TestFunc()
{
  #define ARRAYSIZE 4096
  #define NUMITERS 16386
  float flIn[ ARRAYSIZE ]; // filled with random numbers ( 0 .. 2^22 )
  float flOut [ ARRAYSIZE ]; // filled with 0 to force fetch into L1 cache

  cyclecounter.Start();
  for ( int i = 0 ; i < NUMITERS ; ++i )
    for ( int j = 0 ; j < ARRAYSIZE ; ++j )
    {
       flOut[j] = TestSqrtFunction( flIn[j] );
       // unrolling this loop makes no difference -- I tested it.
    }
  cyclecounter.Stop();
  printf( "%d loops over %d floats took %.3f milliseconds",
          NUMITERS, ARRAYSIZE, cyclecounter.Milliseconds() );
}

لقد جربت ذلك مع عدد قليل من الهيئات المختلفة لـ TestSqrtFunction، ولدي بعض التوقيتات التي تخدش رأسي حقًا.الأسوأ على الإطلاق هو استخدام الدالة sqrt() الأصلية والسماح للمترجم "الذكي" "بالتحسين".عند 24ns/float، كان استخدام x87 FPU سيئًا بشكل مثير للشفقة:

inline float TestSqrtFunction( float in )
{  return sqrt(in); }

الشيء التالي الذي حاولته هو استخدام جوهري لإجبار المترجم على استخدام كود التشغيل SSE العددي sqrt:

inline void SSESqrt( float * restrict pOut, float * restrict pIn )
{
   _mm_store_ss( pOut, _mm_sqrt_ss( _mm_load_ss( pIn ) ) );
   // compiles to movss, sqrtss, movss
}

كان هذا أفضل، عند 11.9 نانو ثانية/طفو.لقد حاولت أيضًا تقنية تقريب كارماك الغريبة لنيوتن-رافسون, ، والذي كان يعمل بشكل أفضل من الأجهزة، بمعدل 4.3ns/float، على الرغم من وجود خطأ قدره 1 في 2¹⁰ (وهو أكثر من اللازم لأغراضي).

كان الأمر مزعجًا عندما جربت عملية SSE متبادل الجذر التربيعي، ثم استخدم الضرب للحصول على الجذر التربيعي ( x * 1/√x = √x ).على الرغم من أن هذا يتطلب عمليتين تابعتين، إلا أنه كان الحل الأسرع على الإطلاق، عند 1.24ns/float ودقة تصل إلى 2^-14:

inline void SSESqrt_Recip_Times_X( float * restrict pOut, float * restrict pIn )
{
   __m128 in = _mm_load_ss( pIn );
   _mm_store_ss( pOut, _mm_mul_ss( in, _mm_rsqrt_ss( in ) ) );
   // compiles to movss, movaps, rsqrtss, mulss, movss
}

سؤالي هو في الأساس ما يعطي? لماذا يعد كود تشغيل الجذر التربيعي المدمج في الأجهزة لـ SSE أبطأ من توليفها من عمليتين رياضيتين أخريين؟

أنا متأكد من أن هذه هي تكلفة العملية نفسها، لأنني تحققت من ذلك:

• جميع البيانات تناسب ذاكرة التخزين المؤقت ، والوصول متتابع
• الوظائف مضمنة
• إن فتح الحلقة لا يحدث فرقًا
• تم ضبط إشارات المترجم على التحسين الكامل (ولقد قمت بفحص التجميع بشكل جيد)

(يحرر:يشير ستيفنتيرون بشكل صحيح إلى أن العمليات على سلاسل طويلة من الأرقام يجب أن تستخدم العمليات المجمعة لـ SIMD، مثل rsqrtps - لكن بنية بيانات المصفوفة هنا لأغراض الاختبار فقط:ما أحاول قياسه حقًا هو العددية الأداء للاستخدام في التعليمات البرمجية التي لا يمكن توجيهها.)

Answer 1

sqrtss يعطي نتيجة تقريب بشكل صحيح. rsqrtss يعطي تقريب إلى المتبادل، دقيق إلى حوالي 11 بت.

sqrtss هو توليد نتيجة أكثر دقة بكثير، عندما تكون الدقة مطلوبة. rsqrtss يوجد في الحالات عندما يكفي تقريب، ولكن السرعة مطلوبة. إذا قرأت وثائق Intel، فسوف تجد أيضا تسلسل تعليمات (تقريب جذر مربعة متبادلة متبوعا بخطوة Newton-Raphson واحدة) التي توفر دقة كاملة تقريبا (~ 23 بت من الدقة، إذا كنت أتذكر بشكل صحيح)، وما زال إلى حد ما اسرع من sqrtss.

تعديل: إذا كانت السرعة أمرا بالغ الأهمية، فأنت تدعو هذا بالفعل في حلقة للعديد من القيم، فيجب أن تستخدم الإصدارات الموجهة لهذه التعليمات rsqrtps أو sqrtps, ، وكلاهما العملية أربعة عوامات لكل تعليمات.

Answer 2

هذا صحيح أيضا للانقسام. البقرات (A، RCPSS (B)) أسرع من Divss (A، B). في الواقع، ما زالت أسرع حتى عندما تزيد من دقتها مع تكرار Newton-Raphson.

يوصي كلاهما Intel و AMD بهذه التقنية في أدلة التحسين الخاصة بهم. في التطبيقات التي لا تتطلب الامتثال IEEE-754، فإن السبب الوحيد لاستخدام DIV / SQRT هو قابلية القراءة رمز.

Answer 3

بدلاً من تقديم إجابة، قد يكون ذلك غير صحيح في الواقع (لن أقوم أيضًا بالتحقق أو الجدال حول ذاكرة التخزين المؤقت والأشياء الأخرى، دعنا نقول أنها متطابقة) سأحاول توجيهك إلى المصدر الذي يمكنه الإجابة على سؤالك.
قد يكمن الاختلاف في كيفية حساب sqrt وrsqrt.يمكنك قراءة المزيد هنا http://www.intel.com/products/processor/manuals/.أقترح البدء بالقراءة عن وظائف المعالج التي تستخدمها، فهناك بعض المعلومات، خاصة حول rsqrt (تستخدم وحدة المعالجة المركزية جدول بحث داخلي بتقريب كبير، مما يجعل الحصول على النتيجة أسهل بكثير).قد يبدو أن rsqrt أسرع بكثير من sqrt، وأن عملية متعددة إضافية (وهي ليست مكلفة) قد لا تغير الوضع هنا.

يحرر:بعض الحقائق التي قد تستحق الذكر:
1.ذات مرة كنت أقوم ببعض التحسينات الدقيقة لمكتبة الرسومات الخاصة بي واستخدمت rsqrt لحساب طول المتجهات.(بدلاً من sqrt، قمت بضرب مجموع المربعات في rsqrt، وهو بالضبط ما فعلته في اختباراتك)، وكان أداؤه أفضل.
2.قد يكون حساب rsqrt باستخدام جدول بحث بسيط أسهل، كما هو الحال بالنسبة لـ rsqrt، عندما تنتقل x إلى ما لا نهاية، فإن 1/sqrt(x) يذهب إلى 0، لذلك بالنسبة لقيم x الصغيرة لا تتغير قيم الدالة (كثيرًا)، بينما بالنسبة لـ sqrt - يذهب إلى ما لا نهاية، لذلك هذه الحالة البسيطة؛).

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

Answer 4

نيوتن رافون يتصاعد إلى الصفر من f(x) باستخدام الزيادات يساوي إلى -f/f' أين f' هو المشتق.

ل x=sqrt(y), ، يمكنك محاولة حل f(x) = 0 ل x استخدام f(x) = x^2 - y;

ثم الزيادة هي: dx = -f/f' = 1/2 (x - y/x) = 1/2 (x^2 - y) / xالذي لديه انقسام بطيء فيه.

يمكنك تجربة وظائف أخرى (مثل f(x) = 1/y - 1/x^2) لكنها ستكون معقدة بنفس القدر.

دعنا ننظر إلى 1/sqrt(y) الآن. يمكنك المحاولة f(x) = x^2 - 1/y, ، ولكن سيكون معقد بنفس القدر: dx = 2xy / (y*x^2 - 1) على سبيل المثال. اختيار بديل واحد غير واضح ل f(x) هو: f(x) = y - 1/x^2

ثم: dx = -f/f' = (y - 1/x^2) / (2/x^3) = 1/2 * x * (1 - y * x^2)

آه! إنه ليس تعبيرا تافها، لكن لديك فقط تضاعف فيه، لا يوجد فقس. => أسرع!

و: خطوة التحديث الكامل new_x = x + dx ثم يقرأ:

x *= 3/2 - y/2 * x * x وهو سهل جدا.

Answer 5

من الناحية الأسرع لأن هذه التعليمات تتجاهل أوضاع التقريب، ولا تتعامل مع استثناءات النقاط العائمة أو أرقام dernormalized. لهذه الأسباب، من الأسهل بكثير خط الأنابيب، وتكهن بتنفيذ تعليمات FP الأخرى خارج النظام.