مضاعفة المصفوفة: Strassen مقابل Standard

Question

حاولت تنفيذ خوارزمية Strassen لضرب المصفوفة مع C ++ ، ولكن النتيجة ليست كذلك ، ما كنت أتوقعه. كما ترون أن Strassen يستغرق دائمًا المزيد من الوقت ثم التنفيذ القياسي وفقط مع وجود بُعد من قوة 2 ، يكون التطبيق القياسي فقط. ماذا حصل؟

matrix mult_strassen(matrix a, matrix b) {
if (a.dim() <= cut)
    return mult_std(a, b);

matrix a11 = get_part(0, 0, a);
matrix a12 = get_part(0, 1, a);
matrix a21 = get_part(1, 0, a);
matrix a22 = get_part(1, 1, a);

matrix b11 = get_part(0, 0, b);
matrix b12 = get_part(0, 1, b);
matrix b21 = get_part(1, 0, b);
matrix b22 = get_part(1, 1, b);

matrix m1 = mult_strassen(a11 + a22, b11 + b22); 
matrix m2 = mult_strassen(a21 + a22, b11);
matrix m3 = mult_strassen(a11, b12 - b22);
matrix m4 = mult_strassen(a22, b21 - b11);
matrix m5 = mult_strassen(a11 + a12, b22);
matrix m6 = mult_strassen(a21 - a11, b11 + b12);
matrix m7 = mult_strassen(a12 - a22, b21 + b22);

matrix c(a.dim(), false, true);
set_part(0, 0, &c, m1 + m4 - m5 + m7);
set_part(0, 1, &c, m3 + m5);
set_part(1, 0, &c, m2 + m4);
set_part(1, 1, &c, m1 - m2 + m3 + m6);

return c; 
}

---

برنامج
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.

Answer 1

بعض الأفكار:

• هل قمت بتحسينه للنظر في أن لا قوة من مصفوفة بحجم اثنين من الأصفار؟ أعتقد أن الخوارزمية تفترض أنك لا تهتم بضرب هذه المصطلحات. هذا هو السبب في أنك تحصل على المناطق المسطحة حيث يكون وقت التشغيل ثابتًا بين 2^n و 2^(n+1) -1. من خلال عدم ضرب المصطلحات التي تعرفها ، يجب أن تكون قادرًا على تحسين هذه المناطق. أو ربما يهدف Strassen فقط إلى العمل مع المصفوفات بحجم 2^n.
• فكر في أن المصفوفة "الكبيرة" تعسفية وأن الخوارزمية أفضل قليلاً من الحالة الساذجة ، O (n^3) vs o (n^2.8). قد لا ترى مكاسب قابلة للقياس حتى تتم محاكمة المصفوفات الأكبر. على سبيل المثال ، لقد قمت ببعض نمذجة العناصر المحدودة حيث تم اعتبار 10000 × 10،000 مصفوفات "صغيرة". من الصعب معرفة من الرسم البياني الخاص بك ، لكن يبدو أن حالة 511 قد تكون أسرع في حالة Stassen.
• حاول الاختبار مع مستويات التحسين المختلفة بما في ذلك عدم التحسينات على الإطلاق.
• يبدو أن هذه الخوارزمية تفترض أن الضربات أغلى بكثير من الإضافات. كان هذا صحيحًا بالتأكيد منذ 40 عامًا عندما تم تطويره لأول مرة ، لكنني أؤمن بالمعالجات الأكثر حداثة ، أصبح الفرق بين Add and Mulply أصغر. قد يقلل هذا من فعالية الخوارزمية التي يبدو أنها تقلل من الضربات ولكنها تزيد من الإضافات.
• هل نظرت إلى بعض تطبيقات Strassen الأخرى الموجودة في الأفكار؟ حاول قياس تطبيق جيد معروف لمعرفة مدى أسرع يمكنك الحصول عليه.

Answer 2

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

حاول استخدام فئة مصفوفة الحجم الثابت (مع معلمة القالب)؟ هذا سوف يحل على الأقل مشكلة التخصيص.

ملاحظة: لست متأكدًا من أن الحدث يعمل بشكل صحيح مع الكود الخاص بك. تستخدم فئة المصفوفة المؤشرات ولكن ليس لديها منشئ نسخ أو عامل تعيين. أنت أيضًا تتسرب من الذاكرة في النهاية ، حيث أنك لا تملك مدمرة ...

Answer 3

Big O من Strassen هو O (n ^ log 7) مقارنة بـ O (n ^ 3) العادية ، أي سجل 7 قاعدة 2 أقل بقليل من 3.

هذا هو عدد الضربات التي تحتاج إلى صنعها.

يفترض أنه لا يوجد أي تكلفة على أي شيء آخر لديك ، ويجب أن يكون "أسرع" أيضًا فقط حيث أن N يصبح كبيرًا بما يكفي لك.

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

Answer 4

لقد صدمت فعليًا من مدى أسرع تنفيذي لضرب Stassen:

http://ezekiel.vancouver.wsu.edu/~cs330/lectures/linear_algebra/mm/mm.c

أحصل على تسريع ما يقرب من 16x على الجهاز الخاص بي عندما ن = 1024. الطريقة الوحيدة التي يمكنني بها شرح الكثير من التسريع هي أن الخوارزمية الخاصة بي هي أكثر ملاءمة للذاكرة التخزين المؤقت-أي أنها تركز على أجزاء صغيرة من المصفوفات وبالتالي تكون البيانات أكثر ترجمة.

من المحتمل أن يكون النفقات العامة في تطبيق C ++ مرتفعًا جدًا - يولد المترجم أكثر من المؤسسات مما هو ضروري حقًا. يحاول تنفيذي تقليل ذلك عن طريق إعادة استخدام الذاكرة كلما أمكن ذلك.

Answer 5

لقطة طويلة ، ولكن هل فكرت في أن الضرب القياسي قد يتم تحسينه بواسطة المترجم؟ هل يمكنك إغلاق التحسينات؟