كيفية تسريع مضاعفة المصفوفة في C ++؟

Question

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

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

 matrix mult_std(matrix a, matrix b) {
 matrix c(a.dim(), false, false);
 for (int i = 0; i < a.dim(); i++)
  for (int j = 0; j < a.dim(); j++) {
   int sum = 0;
   for (int k = 0; k < a.dim(); k++)
    sum += a(i,k) * b(k,j);
   c(i,j) = sum;
  }

 return c;
}

---

تعديل

---

لقد صححت سؤالي جاذبية! أضفت رمز المصدر الكامل أدناه وجربت بعض نصائحك:

• تبديل k و j تكرارات الحلقة -> تحسين الأداء
• أعلن dim() و operator()() كما inline -> تحسين الأداء
• تمرير الحجج بواسطة Const Reference -> فقدان الأداء! لماذا ا؟ لذلك أنا لا أستخدمه.

أصبح الأداء الآن هو نفسه تقريبًا كما كان في بورجرام القديم. ربما يجب أن يكون هناك المزيد من التحسن.

لكن لدي مشكلة أخرى: أحصل على خطأ في الذاكرة في الوظيفة mult_strassen(...). لماذا ا؟
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

---

البرنامج القديم
ج الرئيسية http://pastebin.com/qpgdwgpw

c99 main.c -o matrix -O3

---

برنامج جديد
Matrix.H http://pastebin.com/tyfycty7
Matrix.cpp http://pastebin.com/wyadlj8y
Main.cpp http://pastebin.com/48bsqgjr

g++ main.cpp matrix.cpp -o matrix -O3.

---

تعديل

---

فيما يلي بعض النتائج. المقارنة بين الخوارزمية القياسية (STD) ، ترتيب تم تبديله من حلقة J و K (SWAP) والتلاعب المحظور بحجم كتلة 13 (كتلة).

Answer 1

تمرير المعلمات عن طريق مرجع const للبدء مع:

matrix mult_std(matrix const& a, matrix const& b) {

لإعطائك المزيد من التفاصيل ، نحتاج إلى معرفة تفاصيل الأساليب الأخرى المستخدمة.
وللجيب على سبب أسرع 4 مرات 4 مرات ، سنحتاج إلى رؤية الطريقة الأصلية.

المشكلة هي بلا شك لك لأن هذه المشكلة قد تم حلها مليون مرة من قبل.

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

بدون الكود نحن فقط تخمين.

يحرر

بعد إصلاح الخلل الرئيسي في رمز C الأصلي (عازلة الإفراط في التشغيل)

لقد قمت بتحديث الرمز لتشغيل الاختبار جنبًا إلى جنب في مقارنة عادلة:

 // INCLUDES -------------------------------------------------------------------
 #include <stdlib.h>
 #include <stdio.h>
 #include <sys/time.h>
 #include <time.h>

 // DEFINES -------------------------------------------------------------------
 // The original problem was here. The MAXDIM was 500. But we were using arrays
 // that had a size of 512 in each dimension. This caused a buffer overrun that
 // the dim variable and caused it to be reset to 0. The result of this was causing
 // the multiplication loop to fall out before it had finished (as the loop was
 // controlled by this global variable.
 //
 // Everything now uses the MAXDIM variable directly.
 // This of course gives the C code an advantage as the compiler can optimize the
 // loop explicitly for the fixed size arrays and thus unroll loops more efficiently.
 #define MAXDIM 512
 #define RUNS 10

 // MATRIX FUNCTIONS ----------------------------------------------------------
 class matrix
 {
 public:
 matrix(int dim)
       : dim_(dim)
 {
         data_ = new int[dim_ * dim_];

 }

     inline int dim() const {
                         return dim_;
                 }
                 inline int& operator()(unsigned row, unsigned col) {
                         return data_[dim_*row + col];
                 }

                 inline int operator()(unsigned row, unsigned col) const {
                         return data_[dim_*row + col];
                 }

 private:
     int dim_;
     int* data_;
 };

// ---------------------------------------------------
 void random_matrix(int (&matrix)[MAXDIM][MAXDIM]) {
         for (int r = 0; r < MAXDIM; r++)
                 for (int c = 0; c < MAXDIM; c++)
                         matrix[r][c] = rand() % 100;
 }
 void random_matrix_class(matrix& matrix) {
         for (int r = 0; r < matrix.dim(); r++)
                 for (int c = 0; c < matrix.dim(); c++)
                         matrix(r, c) = rand() % 100;
 }

 template<typename T, typename M>
 float run(T f, M const& a, M const& b, M& c)
 {
         float time = 0;

         for (int i = 0; i < RUNS; i++) {
                 struct timeval start, end;
                 gettimeofday(&start, NULL);
                 f(a,b,c);
                 gettimeofday(&end, NULL);

                 long s = start.tv_sec * 1000 + start.tv_usec / 1000;
                 long e = end.tv_sec * 1000 + end.tv_usec / 1000;

                 time += e - s;
         }
         return time / RUNS;
 }
 // SEQ MULTIPLICATION ----------------------------------------------------------
  int* mult_seq(int const(&a)[MAXDIM][MAXDIM], int const(&b)[MAXDIM][MAXDIM], int (&z)[MAXDIM][MAXDIM]) {
          for (int r = 0; r < MAXDIM; r++) {
                  for (int c = 0; c < MAXDIM; c++) {
                          z[r][c] = 0;
                          for (int i = 0; i < MAXDIM; i++)
                                  z[r][c] += a[r][i] * b[i][c];
                  }
          }
  }
  void mult_std(matrix const& a, matrix const& b, matrix& z) {
          for (int r = 0; r < a.dim(); r++) {
                  for (int c = 0; c < a.dim(); c++) {
                          z(r,c) = 0;
                          for (int i = 0; i < a.dim(); i++)
                                  z(r,c) += a(r,i) * b(i,c);
                  }
          }
  }

  // MAIN ------------------------------------------------------------------------
  using namespace std;
  int main(int argc, char* argv[]) {
          srand(time(NULL));

          int matrix_a[MAXDIM][MAXDIM];
          int matrix_b[MAXDIM][MAXDIM];
          int matrix_c[MAXDIM][MAXDIM];
          random_matrix(matrix_a);
          random_matrix(matrix_b);
          printf("%d ", MAXDIM);
          printf("%f \n", run(mult_seq, matrix_a, matrix_b, matrix_c));

          matrix a(MAXDIM);
          matrix b(MAXDIM);
          matrix c(MAXDIM);
          random_matrix_class(a);
          random_matrix_class(b);
          printf("%d ", MAXDIM);
          printf("%f \n", run(mult_std, a, b, c));

          return 0;
  }

النتائج الآن:

$ g++ t1.cpp
$ ./a.exe
512 1270.900000
512 3308.800000

$ g++ -O3 t1.cpp
$ ./a.exe
512 284.900000
512 622.000000

من هذا نرى رمز C حوالي ضعف سرعة رمز C ++ عند تحسينه بالكامل. لا أستطيع رؤية السبب في الكود.

Answer 2

بالحديث عن التسريع ، ستكون وظيفتك أكثر ملاءمة للذاكرة التخزين المؤقت إذا قمت بتبديل ترتيب k و j تكرارات الحلقة:

matrix mult_std(matrix a, matrix b) {
 matrix c(a.dim(), false, false);
 for (int i = 0; i < a.dim(); i++)
  for (int k = 0; k < a.dim(); k++)
   for (int j = 0; j < a.dim(); j++)  // swapped order
    c(i,j) += a(i,k) * b(k,j);

 return c;
}

هذا لأن أ k الفهرس على الحلقة الداخلية أكثر b على كل تكرار. مع j باعتباره الفهرس الداخلي ، كلاهما c و b يتم الوصول إليها بشكل متجاور ، بينما a وضعت.

Answer 3

أنت تقول أنك لا تريد تعديل الخوارزمية ، لكن ماذا يعني ذلك بالضبط؟

هل يعتبر حلقة الحلقة "تعديل الخوارزمية"؟ ماذا عن استخدام SSE/VMX أيهما تتوفر تعليمات SIMD على وحدة المعالجة المركزية الخاصة بك؟ ماذا عن استخدام شكل من أشكال حظر لتحسين موقع ذاكرة التخزين المؤقت؟

إذا كنت لا تريد إعادة هيكلة الكود الخاص بك على الاطلاق, ، أشك في أن هناك ما يمكنك القيام به أكثر من التغييرات التي أجريتها بالفعل. يصبح كل شيء آخر مفاضلة للتغييرات الطفيفة على الخوارزمية لتحقيق دفعة الأداء.

بالطبع ، لا يزال يتعين عليك إلقاء نظرة على ASM التي تم إنشاؤها بواسطة المترجم. هذا سيخبرك بالمزيد حول ما يمكن القيام به لتسريع الكود.

Answer 4

تأكد من أن الأعضاء dim() و operator()() يتم إعلانها مضمّنًا ، ويتم تشغيل تحسين التحويل البرمجي. ثم العب مع خيارات مثل -funroll-loops (على مجلس التعاون الخليجي).

ما أكبر a.dim() على أي حال؟ إذا كان صف من المصفوفة لا يتناسب مع خطوط ذاكرة التخزين المؤقت للزوجين ، فستكون أفضل حالًا مع نمط الوصول إلى كتلة بدلاً من الصف الكامل في وقت واحد.

Answer 5

• استخدم SIMD إذا استطعت. يجب عليك تمامًا استخدام شيء مثل سجلات VMX إذا كنت تقوم بالرياضيات المتجهية واسعة النطاق على افتراض أنك تستخدم منصة قادرة على القيام بذلك ، وإلا فإنك ستتحمل نجاحًا كبيرًا في الأداء.
• لا تمر بالأنواع المعقدة مثل matrix بالقيمة - استخدم مرجع const.
• لا تسمي وظيفة في كل تكرار - ذاكرة التخزين المؤقت dim() خارج حلقاتك.
• على الرغم من أن المترجمين يحسنون عادةً هذا بكفاءة ، إلا أنه من الجيد غالبًا أن يوفر المتصل مرجعًا للمصفوفة لوظيفة وظيفتك بدلاً من إرجاع المصفوفة حسب النوع. في بعض الحالات ، قد يؤدي ذلك إلى عملية نسخ باهظة الثمن.

Answer 6

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

static void fastMatrixMultiply(const int dim, float* dest, const float* srcA, const float* srcB)
{
    memset( dest, 0x0, dim * dim * sizeof(float) );

    for( int i = 0; i < dim; i++ ) {
        for( int k = 0; k < dim; k++ ) 
        {
            const float* a = srcA + i * dim + k;
            const float* b = srcB + k * dim;
            float* c = dest + i * dim;

            float* cMax = c + dim;
            while( c < cMax ) 
            {   
                *c++ += (*a) * (*b++);
            }
        }
    }
}

Answer 7

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

لماذا لا تخصص الذاكرة للمصفوفات باليد ، وتضمن أنها متجاورة ، وبناء هيكل المؤشر بنفسك؟

أيضا ، هل طريقة Dim () لها أي تعقيد إضافي؟ أود أن أعلن ذلك مضمرا ، أيضا.