خوارزمية تجنب الاتصال

تعمل خوارزميات تجنب الاتصال على تقليل حركة البيانات داخل التسلسل الهرمي للذاكرة لتحسين وقت التشغيل واستهلاك الطاقة. وتقلل هذه الخوارزميات من إجمالي تكلفتين (من حيث الوقت والطاقة): العمليات الحسابية والاتصال. يشير الاتصال، في هذا السياق، إلى نقل البيانات، سواء بين مستويات الذاكرة أو بين معالجات متعددة عبر الشبكة. وهو أكثر تكلفة بكثير من العمليات الحسابية. ^{[ 1 ]}

النظرية الرسمية

نموذج ذاكرة ثنائي المستوى

يُعد نموذج الذاكرة ثنائي المستوى نموذجًا حسابيًا شائعًا في تحليل خوارزميات تجنب الاتصال:

يوجد معالج واحد ومستويان من الذاكرة.
ذاكرة المستوى 1 كبيرة بلا حدود. ذاكرة المستوى 0 ("الذاكرة المؤقتة") لها حجم محدد. $M$ .
في البداية، يكون المدخل موجودًا في المستوى 1. وفي النهاية، يكون المخرج موجودًا في المستوى 1.
لا يمكن للمعالج العمل إلا على البيانات الموجودة في ذاكرة التخزين المؤقت.
الهدف هو تقليل عمليات نقل البيانات بين مستويي الذاكرة.

ضرب المصفوفات

^{[ 2 ]} النتيجة 6.2:

نظرية — بالنظر إلى المصفوفات $A,B,C$ من الأحجام $n\times m,m\times k,n\times k$ ، ثم $AB+C$ تتسم بتعقيدات في التواصل $\Omega (\max(mkn/M^{1/2},mk+kn+mk))$ .

يمكن تحقيق هذا الحد الأدنى عن طريق ضرب المصفوفات بالبلاطات .

يمكن الاطلاع على نتائج أكثر عمومية لعمليات الجبر الخطي العددي الأخرى في ^{[ 3 ]} . والبرهان التالي مأخوذ من ^{[ 4 ] .}

دليل

يمكننا رسم مخطط الحساب لـ $D=AB+C$ باعتبارها مكعبًا من نقاط الشبكة، فإن كل نقطة لها شكل $(i,j,k)$ . منذ $D[i,k]=\sum _{j}A[i,j]B[j,k]+C[i,k]$ ، الحوسبة $AB+C$ يتطلب ذلك أن يتمكن المعالج من الوصول إلى كل نقطة داخل المكعب مرة واحدة على الأقل. لذا تصبح المشكلة هي تغطية $mnk$ نقاط الشبكة ذات الحد الأدنى من التواصل.

لو $M$ إذا كان حجمها كبيرًا، فيمكننا ببساطة تحميل الكل $mn+nk+mk$ ثم اكتب المدخلات $nk$ هذه المدخلات غير مثيرة للاهتمام.

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

خلال كل جزء، يكون للمعالج إمكانية الوصول إلى أكثر من $2M$ نقاط مختلفة من $A,B,C$ .

يترك $E$ لتكن مجموعة نقاط الشبكة التي تم تغطيتها خلال هذا الجزء. عندئذٍ، وفقًا لمتباينة لوميس-ويتني ،

$|E|\leq {\sqrt {|\pi _{1}(E)||\pi _{2}(E)||\pi _{3}(E)|}}$ مع وجود قيود $\sum _{i}|\pi _{i}(E)|\leq 2M$ .

بسبب عدم تساوي المتوسط الحسابي والمتوسط الهندسي ، لدينا $|E|\leq \left({\frac {2}{3}}M\right)^{3/2}$ ، حيث يتم الوصول إلى أقصى قيمة عندما $\pi _{i}(E)={\frac {2}{3}}M$ .

وبالتالي فإن الكثافة الحسابية محدودة من الأعلى بـ $CM^{1/2}$ أين $C=(2/3)^{3/2}$ وبالتالي فإن الاتصال محدود أدناه بواسطة ${\frac {nmk}{CM^{1/2}}}$ .

تؤكد الحسابات المباشرة أن خوارزمية ضرب المصفوفات المتجانبة تصل إلى الحد الأدنى.

تحفيز

ضع في اعتبارك نموذج وقت التشغيل التالي: ^{[ 5 ]}

مقياس الحساب = الوقت لكل عملية حسابية = γ
مقياس التواصل = عدد كلمات البيانات المنقولة = β

⇒ إجمالي وقت التشغيل = γ × (عدد عمليات الفاصلة العائمة ) + β × (عدد الكلمات)

انطلاقًا من حقيقة أن β >> γ من حيث الوقت والطاقة، فإن تكلفة الاتصال تهيمن على تكلفة الحوسبة. وتشير التوجهات التكنولوجية ^{[ 6 ]} إلى أن التكلفة النسبية للاتصال تتزايد على مختلف المنصات، بدءًا من الحوسبة السحابية ووصولًا إلى الحواسيب العملاقة والأجهزة المحمولة. ويتوقع التقرير أيضًا أن الفجوة بين زمن الوصول إلى ذاكرة الوصول العشوائي الديناميكية (DRAM) وعدد عمليات الفاصلة العائمة في الثانية (FLOPs) ستزداد بمقدار 100 ضعف خلال العقد القادم لتحقيق توازن في استهلاك الطاقة بين المعالجات وذاكرة الوصول العشوائي الديناميكية. ^{[ 1 ]}

معدل FLOP (γ)	عرض نطاق ذاكرة الوصول العشوائي الديناميكية (β)	عرض نطاق الشبكة (β)
59% سنوياً	23% سنوياً	26% سنوياً

يزداد استهلاك الطاقة بشكل كبير كلما ارتفعنا في التسلسل الهرمي للذاكرة. ^{[ 7 ]}

أشار الرئيس الأمريكي باراك أوباما إلى خوارزميات تجنب الاتصالات في طلب ميزانية وزارة الطاقة للسنة المالية 2012 المقدم إلى الكونجرس: ^{[ 1 ]}

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

أهداف

تم تصميم خوارزميات تجنب الاتصال لتحقيق الأهداف التالية:

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

يوضح المثال البسيط التالي ^{[ 1 ]} كيفية تحقيق ذلك.

مثال على ضرب المصفوفات

لتكن A و B و C مصفوفات مربعة من الرتبة n × n . تُنفذ الخوارزمية البسيطة التالية C = C + A * B:

من أجل i = 1 إلى n من j = 1 إلى n من k = 1 إلى n C(i,j) = C(i,j) + A(i,k) * B(k,j)

التكلفة الحسابية (التعقيد الزمني): n ² (2 n − 1) لـ n كبير بما فيه الكفاية أو O( n ³ ).

إعادة كتابة هذه الخوارزمية مع تحديد تكلفة الاتصال في كل خطوة

من أجل i = 1 إلى n {قراءة الصف i من المصفوفة A في الذاكرة السريعة} - n ² قراءة من j = 1 إلى n {قراءة C(i,j) في الذاكرة السريعة} - n ² قراءة {قراءة العمود j من المصفوفة B في الذاكرة السريعة} - n ³ عمليات قراءة من k = 1 إلى n C(i,j) = C(i,j) + A(i,k) * B(k,j) {كتابة C(i,j) مرة أخرى إلى الذاكرة البطيئة} - n ² كتابة

يمكن تعريف الذاكرة السريعة بأنها ذاكرة المعالج المحلية ( ذاكرة التخزين المؤقت لوحدة المعالجة المركزية ) بحجم M، ويمكن تعريف الذاكرة البطيئة بأنها ذاكرة الوصول العشوائي الديناميكية (DRAM).

تكلفة الاتصال (قراءة/كتابة): n ³ + 3 n ² أو O( n ³ )

بما أن إجمالي زمن التشغيل = γ ·O( n ³ ) + β ·O( n ³ ) و β >> γ ، فإن تكلفة الاتصال هي العامل المهيمن. تعمل خوارزمية ضرب المصفوفات المجزأة (المقسمة) ^{[ 1 ]} على تقليل هذا العامل المهيمن.

ضرب المصفوفات المجزأة (المقسمة إلى مربعات)

اعتبر A و B و C مصفوفات n / b -by- n / b من b -by- b كتل فرعية حيث b يسمى حجم الكتلة؛ افترض أن ثلاث كتل b -by- b تتناسب مع الذاكرة السريعة.

من أجل i = 1 إلى n/b من أجل j = 1 إلى n/b {قراءة الكتلة C(i,j) في الذاكرة السريعة} - b² ^× (n/b) ^² = ^n² قراءة من k = 1 إلى n/b {قراءة الكتلة A(i,k) في الذاكرة السريعة} - b ² × (n/b) ³ = n ³ /b قراءة {قراءة الكتلة B(k,j) في الذاكرة السريعة} - b ² × (n/b) ³ = n ³ /b قراءة C(i,j) = C(i,j) + A(i,k) * B(k,j) - {قم بعملية ضرب المصفوفات على الكتل} {كتابة الكتلة C(i,j) مرة أخرى إلى الذاكرة البطيئة} - b² ^× (n/b) ^² = n² ^عملية كتابة

تكلفة الاتصال: 2 ن ³ / ب + 2 ن ² عمليات قراءة/كتابة << 2 ن ³ التكلفة الحسابية

جعل قيمة b أكبر ما يمكن:

3 ب ² ≤ م

نحقق الحد الأدنى التالي للاتصال:

3 ^1/2n ³ / M ^1/2 + 2 n ² أو Ω (عدد عمليات الفاصلة العائمة / M ^1/2 )

الأساليب السابقة لتقليل التواصل

Most of the approaches investigated in the past to address this problem rely on scheduling or tuning techniques that aim at overlapping communication with computation. However, this approach can lead to an improvement of at most a factor of two. Ghosting is a different technique for reducing communication, in which a processor stores and computes redundantly data from neighboring processors for future computations. Cache-oblivious algorithms represent a different approach introduced in 1999 for fast Fourier transforms,^[8] and then extended to graph algorithms, dynamic programming, etc. They were also applied to several operations in linear algebra^[9]^[10]^[11] as dense LU and QR factorizations. The design of architecture specific algorithms is another approach that can be used for reducing the communication in parallel algorithms, and there are many examples in the literature of algorithms that are adapted to a given communication topology.^[12]

References

1 2 3 4 5Demmel, Jim. "Communication avoiding algorithms". 2012 SC Companion: High Performance Computing, Networking Storage and Analysis. IEEE, 2012.
↑Jia-Wei, Hong; Kung, H. T. (1981). "I/O complexity". Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81. New York, New York, USA: ACM Press. pp. 326–333. doi:10.1145/800076.802486. S2CID 8410593.
↑Ballard, G.; Carson, E.; Demmel, J.; Hoemmen, M.; Knight, N.; Schwartz, O. (May 2014). "Communication lower bounds and optimal algorithms for numerical linear algebra". Acta Numerica. 23: 1–155. doi:10.1017/s0962492914000038. ISSN 0962-4929. S2CID 122513943.
↑Demmel, James; Dinh, Grace (2018-04-24). "Communication-Optimal Convolutional Neural Nets". arXiv:1802.06905 [cs.DS].
↑Demmel, James, and Kathy Yelick. "Communication Avoiding (CA) and Other Innovative Algorithms". The Berkeley Par Lab: Progress in the Parallel Computing Landscape: 243–250.
↑ بيرغمان، كيرين، وآخرون. " دراسة الحوسبة فائقة السرعة: التحديات التكنولوجية في أنظمة الحوسبة فائقة السرعة ." مكتب تقنيات معالجة المعلومات التابع لوكالة مشاريع البحوث الدفاعية المتقدمة (DARPA IPTO)، التقرير الفني 15 (2008).
↑ شالف، جون، سوديب دوسانج، وجون موريسون. "تحديات تكنولوجيا الحوسبة فائقة السرعة". الحوسبة عالية الأداء للعلوم الحاسوبية - VECPAR 2010. سبرينغر برلين هايدلبرغ، 2011. 1-25.
↑ M. Frigo, CE Leiserson, H. Prokop, and S. Ramachandran, "Cacheoblivious algorithms", In FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999. IEEE Computer Society.
↑ S. Toledo, " Locality of reference in LU Decomposition with partial pivoting ,” SIAM J. Matrix Anal. Appl., vol. 18, no 4, 1997.
↑ F. Gustavson, "التكرار يؤدي إلى حجب المتغيرات التلقائي لخوارزميات الجبر الخطي الكثيف"، مجلة IBM للبحوث والتطوير، المجلد 41، العدد 6، الصفحات 737-755، 1997.
↑ E. Elmroth, F. Gustavson, I. Jonsson, and B. Kagstrom, “ Recursive blocking algorithms and hybrid data structures for dense matrix library software ,” SIAM Review, vol. 46, no. 1, pp. 3–45, 2004.
↑ غريغوري، لورا . " مقدمة في الاتصالات تتجنب خوارزميات الجبر الخطي في الحوسبة عالية الأداء" .

[Demmel_2012-1] 1 2 3 4 5Demmel, Jim. "Communication avoiding algorithms". 2012 SC Companion: High Performance Computing, Networking Storage and Analysis. IEEE, 2012.

[2] Jia-Wei, Hong; Kung, H. T. (1981). "I/O complexity". Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81. New York, New York, USA: ACM Press. pp. 326–333. doi:10.1145/800076.802486. S2CID 8410593.

[3] Ballard, G.; Carson, E.; Demmel, J.; Hoemmen, M.; Knight, N.; Schwartz, O. (May 2014). "Communication lower bounds and optimal algorithms for numerical linear algebra". Acta Numerica. 23: 1–155. doi:10.1017/s0962492914000038. ISSN 0962-4929. S2CID 122513943.

[4] Demmel, James; Dinh, Grace (2018-04-24). "Communication-Optimal Convolutional Neural Nets". arXiv:1802.06905 [cs.DS].

[Demmel_2-5] Demmel, James, and Kathy Yelick. "Communication Avoiding (CA) and Other Innovative Algorithms". The Berkeley Par Lab: Progress in the Parallel Computing Landscape: 243–250.

[DARPA_2008-6] بيرغمان، كيرين، وآخرون. " دراسة الحوسبة فائقة السرعة: التحديات التكنولوجية في أنظمة الحوسبة فائقة السرعة ." مكتب تقنيات معالجة المعلومات التابع لوكالة مشاريع البحوث الدفاعية المتقدمة (DARPA IPTO)، التقرير الفني 15 (2008).

[Shalf_2010-7] شالف، جون، سوديب دوسانج، وجون موريسون. "تحديات تكنولوجيا الحوسبة فائقة السرعة". الحوسبة عالية الأداء للعلوم الحاسوبية - VECPAR 2010. سبرينغر برلين هايدلبرغ، 2011. 1-25.

[Frigo_1999-8] M. Frigo, CE Leiserson, H. Prokop, and S. Ramachandran, "Cacheoblivious algorithms", In FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999. IEEE Computer Society.

[Toledo_1997-9] S. Toledo, " Locality of reference in LU Decomposition with partial pivoting ,” SIAM J. Matrix Anal. Appl., vol. 18, no 4, 1997.

[Gustavson_1997-10] F. Gustavson, "التكرار يؤدي إلى حجب المتغيرات التلقائي لخوارزميات الجبر الخطي الكثيف"، مجلة IBM للبحوث والتطوير، المجلد 41، العدد 6، الصفحات 737-755، 1997.

[Elmroth_2004-11] E. Elmroth, F. Gustavson, I. Jonsson, and B. Kagstrom, “ Recursive blocking algorithms and hybrid data structures for dense matrix library software ,” SIAM Review, vol. 46, no. 1, pp. 3–45, 2004.

[Grigori_2014-12] غريغوري، لورا . " مقدمة في الاتصالات تتجنب خوارزميات الجبر الخطي في الحوسبة عالية الأداء" .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ] .

[ 5 ]

[ 6 ]

[ 7 ]

[8]

[9]

[10]

[11]

[12]

اللغة	العربية (RTL)
روابط موسوعية	24 رابطاً
المصدر الأصلي	ويكيبيديا ↗