عدد العمليات من أجل مضاعفة المصفوفة الكثيفة المتفرقة *

1
  1. كم عدد عمليات الفاصلة العائمة التي يستغرقها مضاعفة مصفوفة CSR المتفرقة x الكثيفة أو مصفوفة متفرقة x CSR المتفرقة باستخدام إجراءات متفرقة محسنة (مثل cuSparse أو Eigen أو Matlab).

  2. في الحد الذي تكون فيه المصفوفة المتناثرة كثيفة بالكامل ، يكون عدد العمليات N^2*(2*N-1) - فلماذا تكون الروتينات المتفرقة أبطأ من الروتين الكثيفة عندما تكون المصفوفة المتفرقة غير متناثرة بما فيه الكفاية؟ ما العمل الإضافي الذي يتم القيام به؟

1 إجابة

2
افضل جواب
  1. إلى عن على R += S * D عدد التقليب هو 2*nnz(S)*ncols(D) حيث يشير nnz إلى عدد الأصفار.

  2. إذا كانت المصفوفة المتفرقة S يصبح كثيفًا ثم يكون عدد التقليب هو نفسه كما هو الحال في الحالة الكثيفة ، ولكن عدد التقليب ليس المعيار الفريد الذي يحدد السرعة ، وعادة ما تكون عمليات الوصول إلى الذاكرة أكثر أهمية. أولا ، مع التخزين المتناثر كل الوصول إلى عنصر S سيكلف عملية غير مباشرة إضافية ، مثل: value[p[k]] بدلا من value[i+j*N] للقضية الكثيفة. ثم في عالم كثيف ، تأتي خوارزميات الحظر لتقليل أخطاء التخزين المؤقت ، والتوجيه (SIMD) ، والتوجيه الأمثل للإرشادات للوصول إلى الأداء الأقصى لوحدة المعالجة المركزية. إن منتج المصفوفة الكثيفة الفعالة هو في الواقع أوامر بحجم أكثر تعقيدًا من الحلقات المتداخلة الثلاثة الساذجة ، انظر بنفسك تنفيذ Eigen. مخيف جدا أليس كذلك؟

:مؤلف
فوق
قائمة طعام