خوارزمية كانون

في علوم الحاسوب ، تُعد خوارزمية كانون خوارزمية موزعة لضرب المصفوفات للشبكات ثنائية الأبعاد، وقد وصفها لين إليوت كانون لأول مرة عام 1969. ^{[ 1 ] [ 2 ]}

يُعدّ هذا الأسلوب مناسبًا بشكل خاص لأجهزة الكمبيوتر المصممة على شبكة N × N. ^{[ 3 ]} في حين أن خوارزمية كانون تعمل بكفاءة في الشبكات ثنائية الأبعاد المتجانسة، فقد تبيّن أن توسيعها لتشمل الشبكات ثنائية الأبعاد غير المتجانسة أمرٌ صعب. ^{[ 4 ]}

تتمثل الميزة الرئيسية للخوارزمية في أن متطلبات التخزين الخاصة بها تظل ثابتة ولا تعتمد على عدد المعالجات. ^{[ 2 ]}

تُعدّ خوارزمية ضرب المصفوفات الشاملة القابلة للتوسع (SUMMA) ^{[ 5 ]} خوارزمية أكثر عملية تتطلب مساحة عمل أقل وتتجاوز الحاجة إلى شبكة مربعة ثنائية الأبعاد. وهي مستخدمة في مكتبات ScaLAPACK و PLAPACK و Elemental .

عند ضرب مصفوفتين من الرتبة n × n ، A و B، نحتاج إلى n × n عقدة معالجة p مرتبة في شبكة ثنائية الأبعاد.

// PE(i , j) k := (i + j) mod N; a := a[i][k]; b := b[k][j]; c[i][j] := 0; for (l := 0; l < N; l++) { c[i][j] := c[i][j] + a * b; في وقت واحد { أرسل a إلى PE(i, (j + N − 1) mod N)؛ أرسل b إلى PE((i + N − 1) mod N, j)؛ } مع { استلام a' من PE(i, (j + 1) mod N)؛ استلام b' من PE((i + 1) mod N, j ); } a := a'; b := b'; }

نحتاج إلى تحديد قيمة k في كل تكرار لكل عنصر معالجة (PE) حتى لا تصل المعالجات إلى نفس البيانات لإجراء العمليات الحسابية.${\displaystyle a_{ik}*b_{kj}}$.

لذلك، يجب أن تبدأ المعالجات في نفس الصف/العمود عملية الجمع بمؤشرات مختلفة. على سبيل المثال، إذا قامت PE(0,0) بحساب${\displaystyle a_{00}*b_{00}}$في الخطوة الأولى، يختار PE(0,1)${\displaystyle a_{01}*b_{11}}$أولاً. إن اختيار k  := (i + j) mod n لـ PE(i,j) يفي بهذا القيد للخطوة الأولى.

في الخطوة الأولى، نقوم بتوزيع مصفوفات الإدخال بين المعالجات بناءً على القاعدة السابقة.

في التكرارات التالية، نختار قيمة جديدة لـ k'  := (k + 1) mod n لكل معالج. بهذه الطريقة، سيستمر كل معالج في الوصول إلى قيم مختلفة للمصفوفات. وبالتالي، تكون البيانات المطلوبة موجودة دائمًا لدى المعالجات المجاورة. يحتاج المعالج PE(i,j) حينها إلى${\displaystyle a}$من PE(i,(j + 1) mod n) و${\displaystyle b}$من PE((i + 1) mod n,j) للخطوة التالية. هذا يعني أن${\displaystyle a}$يجب تمريرها بشكل دوري إلى اليسار وأيضًا${\displaystyle b}$بشكل دوري تصاعدي. تُجمع نتائج عمليات الضرب كالمعتاد. بعد n خطوة، يكون كل معالج قد حسب جميع${\displaystyle a_{ik}*b_{kj}}$مرة واحدة، ومجموعها هو المطلوب.${\displaystyle c_{ij}}$.

بعد التوزيع الأولي لكل معالج، لا يلزم سوى تخزين بيانات الخطوة التالية. وهذه هي النتيجة الوسيطة للمجموع السابق، وهي أ${\displaystyle a_{ik}}$و أ${\displaystyle b_{kj}}$وهذا يعني أن المصفوفات الثلاث تحتاج فقط إلى التخزين في الذاكرة بمجرد توزيعها بالتساوي عبر المعالجات.

• مصفوفة انقباضية