تعدد الخيوط الصريح

المعالجة المتعددة الصريحة ( XMT ) هي نموذج في علوم الحاسوب لبناء وبرمجة الحواسيب المتوازية المصممة وفقًا لنموذج الحوسبة المتوازية لآلة الوصول العشوائي المتوازية (PRAM). يبدأ شرح XMT بشكل مباشر من التجريد الأساسي الذي سهّل الحوسبة التسلسلية : أي تعليمة متاحة للتنفيذ في برنامج تسلسلي تُنفذ فورًا. ومن نتائج هذا التجريد شرحٌ تدريجي (استقرائي) للتعليمة التالية المتاحة للتنفيذ. أما التجريد المتوازي الأساسي الكامن وراء XMT، والذي أطلق عليه فيشكين (2011) اسم التنفيذ المتزامن الفوري (ICE) ، فهو أن عددًا غير محدود من التعليمات المتاحة للتنفيذ المتزامن تُنفذ فورًا. ومن نتائج ICE شرحٌ تدريجي (استقرائي) للتعليمات التالية المتاحة للتنفيذ المتزامن. بالانتقال إلى ما وراء حاسوب فون نيومان التسلسلي (المنصة الوحيدة الناجحة للأغراض العامة حتى الآن)، فإن طموح XMT هو أن يتمكن علم الحاسوب مرة أخرى من تعزيز الاستقراء الرياضي بتجريد حسابي بسيط من سطر واحد.

آلة الوصول العشوائي (RAM) هي نموذج آلة مجرد يُستخدم في علوم الحاسوب لدراسة الخوارزميات وتعقيد الحوسبة التسلسلية القياسية. أما نموذج PRAM الحسابي فهو نموذج آلة متوازية مجرد، طُرح لدراسة الخوارزميات المتوازية وتعقيدها في الحوسبة المتوازية ، قبل أن تُبنى هذه الأخيرة. وقد طوّر الباحثون كمًّا هائلًا من المعرفة حول الخوارزميات المتوازية لنموذج PRAM. وتُعرف هذه الخوارزميات المتوازية أيضًا ببساطتها، مقارنةً بأساليب أخرى في مجال الخوارزميات المتوازية.

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

تُبنى الحواسيب متعددة النوى حول نواتين أو أكثر من المعالجات المدمجة على شريحة دارة متكاملة واحدة . وهي تُستخدم على نطاق واسع في العديد من مجالات التطبيقات، بما في ذلك الحوسبة للأغراض العامة. وتُعدّ تقنية المعالجة المتعددة الصريحة (XMT) نموذجًا حاسوبيًا لبناء وبرمجة الحواسيب متعددة النوى التي تضم عشرات أو مئات أو آلاف النوى.

أظهرت الأعمال التجريبية المنشورة في عامي 2011 و 2012 تسارعًا أكبر بكثير لخوارزميات PRAM المتقدمة على نماذج XMT الأولية مقارنة بنفس المشاكل على أجهزة الكمبيوتر متعددة النوى الحديثة.

أظهرت دراسة نُشرت عام ٢٠١٨ أن البرمجة المتوازية المتزامنة (باستخدام ICE) قادرة على تحقيق نفس أداء أسرع كود متعدد الخيوط مُعدّل يدويًا على أنظمة XMT. ويُعدّ هذا النهج الاستقرائي المتزامن مُغايرًا لنهج البرمجة متعددة الخيوط في العديد من الأنظمة الأساسية الأخرى، والتي تُعرف بصعوبتها على المبرمجين.

تم تقديم نموذج XMT بواسطة أوزي فيشكين .

يدمج نموذج الحوسبة متعدد الخيوط الصريح (XMT) عدة مستويات من التجريد.

يُقدّم إطار عمل وقت العمل (WT) (ويُسمى أحيانًا عمق العمل)، الذي قدّمه شيلواخ وفيشكين (1982) ، طريقةً بسيطةً لتصوّر ووصف الخوارزميات المتوازية. في هذا الإطار، تُوصف الخوارزمية المتوازية أولًا من حيث الجولات المتوازية. تُحدّد العمليات المطلوب تنفيذها في كل جولة، ولكن يمكن إغفال بعض التفاصيل. على سبيل المثال، ليس من الضروري توضيح عدد العمليات في كل جولة، ولا ذكر المعالجات، ولا أي معلومات قد تُساعد في تخصيص المعالجات للمهام. ثانيًا، تُقدّم المعلومات المُغفلة. في الواقع، يستند تضمين هذه المعلومات إلى برهان نظرية جدولة منسوبة إلى برنت (1974) . يُعدّ إطار عمل وقت العمل مفيدًا لأنه، مع قدرته على تبسيط الوصف الأولي للخوارزمية المتوازية بشكل كبير، فإنّ إضافة التفاصيل المُغفلة في ذلك الوصف الأولي غالبًا ما تكون سهلة. على سبيل المثال، تم اعتماد إطار عمل WT كإطار عرض أساسي في كتب الخوارزميات المتوازية (لنموذج PRAM) مثل JaJa (1992) و Keller و Kessler و Traeff (2001) ، وكذلك في ملاحظات المحاضرات Vishkin (2009) . يشرح Vishkin (2011) العلاقة البسيطة بين إطار عمل WT وتجريد ICE الأكثر بدائية المذكور أعلاه.

يمكن برمجة نموذج XMT باستخدام XMTC ، وهي لغة برمجة متعددة الخيوط متوازية وهي امتداد صغير للغة البرمجة C. يتضمن نموذج XMT سير عمل للمبرمج يبدأ بتحويل الخوارزمية في إطار عمل WT ثم ينتقل إلى برمجتها في XMTC.

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

في يناير 2007، تم إنجاز حاسوب ذي 64 معالجًا ^{[ 2 ]} يُدعى Paraleap ^{[ 3 ]} ، والذي يُجسّد المفهوم العام. عُرض مفهوم XMT في دراسات فيشكين وآخرون (1998) ونايشلوس وآخرون (2003)، بينما عُرض حاسوب XMT ذو 64 معالجًا في دراسة وين وفيشكين (2008) . ولأن تسهيل البرمجة المتوازية يُعدّ من أكبر التحديات التي تواجه علوم الحاسوب اليوم، فقد سعى العرض التوضيحي أيضًا إلى تضمين تعليم أساسيات خوارزميات PRAM وبرمجة XMTC لطلاب تتراوح أعمارهم من المرحلة الثانوية (توربرت وآخرون، 2010) إلى الدراسات العليا.

أظهرت الدراسات التجريبية المنشورة في كاراجيا وفيشكين (2011) حول مسألة التدفق الأقصى ، وفي ورقتين بحثيتين لإدواردز وفيشكين ( 2012أ ، 2012 ب ) حول مسائل اتصال الرسوم البيانية ( الاتصال (نظرية الرسوم البيانية) )، واتصال الرسوم البيانية الثنائي ( الرسم البياني ثنائي الاتصال )، واتصال الرسوم البيانية الثلاثي ( المكون ثلاثي الاتصال )، أن نموذج XMT، بالنسبة لبعض الخوارزميات الأكثر تطورًا في مجال الخوارزميات المتوازية، يُمكن أن يُحقق تسارعًا يتراوح بين 8 أضعاف وأكثر من 100 ضعف مقارنةً بالخوارزميات نفسها على أحدث الحواسيب متعددة النوى. وقد تم الحصول على كل تسارع مُبلغ عنه من خلال مقارنة دورات الساعة على نموذج أولي لـ XMT مع أسرع خوارزمية تسلسلية تعمل على أسرع الأجهزة التسلسلية. 

تُوِّجت عملية تطوير نماذج XMT الأولية بدراسة غانم، فيشكين، وباروا (2018) ، التي أثبتت أن البرمجة المتوازية المتزامنة (باستخدام ICE) قادرة على تحقيق نفس أداء أسرع كود متعدد الخيوط مُحسَّن يدويًا على أنظمة XMT. تُبرز هذه النتيجة لعام 2018 التباين بين برمجة XMT وأساليب البرمجة متعددة الخيوط المُستخدمة في جميع أنظمة المعالجات متعددة النوى تقريبًا، والتي غالبًا ما تُشكِّل ظروف التزامن ومتطلباتها الأخرى تحديًا للمبرمجين، بل وقد تُؤدي أحيانًا إلى فشلهم (فيشكين، 2014) .

• برنت، ريتشارد ب. (1974)، "التقييم المتوازي للتعبيرات الحسابية العامة"، مجلة ACM ، 21 (2): 201-208 ، CiteSeerX 10.1.1.100.9361 ، doi : 10.1145/321812.321815 ، S2CID 16416106  .
• شيلواخ، يوسي؛ فيشكين، أوزي (1982)، " خوارزمية تدفق أقصى متوازية من رتبة O(n²log n)"، مجلة الخوارزميات ، 3 ⁽ 2 ) : 128-146 ، doi : 10.1016 / 0196-6774(82)90013-X  .
• جاجا، جوزيف (1992)، مقدمة في الخوارزميات المتوازية ، أديسون-ويسلي، رقم ISBN 978-0-201-54856-3
• كيلر، جورج. كيسلر، كريستوف دبليو. Traeff، Jesper L. (2001)، برمجة PRAM العملية ، وايلي إنترساينس، ISBN 978-0-471-35351-5
• نايشلوس، دوريت؛ نوزمان، جوزيف؛ تسينغ، تشاو-وين؛ فيشكين، أوزي (2003)، "نحو نموذج أولي رأسي أولي لنهج برمجة متوازية دقيق للغاية" (ملف PDF) ، نظرية أنظمة الحوسبة ، 36 (5): 551-552 ، doi : 10.1007/s00224-003-1086-6 ، S2CID 1929495 .

• توربرت، شين؛ فيشكين، أوزي؛ تزور، رون؛ إليسون، ديفيد (2010)، "هل من الممكن تدريس التفكير الخوارزمي المتوازي لطلاب المرحلة الثانوية؟"، وقائع الندوة الفنية الحادية والأربعين لجمعية آلات الحوسبة حول تعليم علوم الحاسوب - SIGCSE '10 ، ص  290، doi : 10.1145/1734263.1734363 ، ISBN 9781450300063.
• فيشكين، أوزي؛ داسكال، شلوميت؛ بيركوفيتش، إفرايم؛ نوزمان، جوزيف (1998)، "نماذج الربط بين تعدد الخيوط الصريح (XMT) لتوازي التعليمات" ، وقائع ندوة ACM لعام 1998 حول الخوارزميات والهياكل المتوازية (SPAA) ، الصفحات 140-151 .
• فيشكين، أوزي (2009)، التفكير بالتوازي: بعض الخوارزميات والتقنيات الأساسية للتوازي في البيانات، 104 صفحات (ملف PDF) ، ملاحظات صفية لمقررات دراسية حول الخوارزميات المتوازية تُدرَّس منذ عام 1992 في جامعة ميريلاند، كوليدج بارك، وجامعة تل أبيب، ومعهد التخنيون.
• وين، شينغزي؛ فيشكين، أوزي (2008)، "نموذج أولي قائم على مصفوفة البوابات المنطقية القابلة للبرمجة (FPGA) لمعالج PRAM-on-chip"، وقائع مؤتمر ACM لعام 2008 حول حدود الحوسبة (إيشيا، إيطاليا) (ملف PDF) ، الصفحات 55-66 ، doi : 10.1145/1366230.1366240 ، ISBN  9781605580777، S2CID 11557669 .
• فيشكين، أوزي (2011)، "استخدام التجريد البسيط لإعادة ابتكار الحوسبة من أجل التوازي"، اتصالات ACM ، 54 : 75-85 ، doi : 10.1145/1866739.1866757.
• كاراجيا، جورج؛ فيشكين، أوزي (2011)، "إعلان موجز: تحسينات أفضل في سرعة التدفق الأقصى المتوازي"، وقائع الندوة الثالثة والعشرين لجمعية الحوسبة الآلية حول التوازي في الخوارزميات والهياكل (SPAA) ، الصفحات 131-134 ، doi : 10.1145/1989493.1989511 ، ISBN  9781450307437، S2CID 5511743 .
• إدواردز، جيمس أ.؛ فيشكين، أوزي (2012أ)، "تحسينات في السرعة باستخدام برمجة متوازية أبسط لاتصال الرسوم البيانية والاتصال الثنائي"، وقائع ورشة العمل الدولية لعام 2012 حول نماذج البرمجة وتطبيقاتها للمعالجات متعددة النوى والمعالجات ذات النوى الكثيرة ، الصفحات 103-114 ، doi : 10.1145/2141702.2141714 ، ISBN  9781450312110، S2CID 15095569 .
• إدواردز، جيمس أ.؛ فيشكين، أوزي (2012ب)، "إعلان موجز: تحسينات في سرعة الاتصال الثلاثي للرسوم البيانية المتوازية"، وقائع الندوة الرابعة والعشرين لجمعية الحوسبة الآلية حول التوازي في الخوارزميات والهياكل (SPAA) ، الصفحات 190-192 ، doi : 10.1145/2312005.2312042 ، ISBN  9781450312134، S2CID 16908459 .
• فيشكين، أوزي (2014)، "هل أجهزة المعالجة المتوازية متعددة النوى للأغراض العامة معيبة؟ مقال رأي"، مجلة اتصالات رابطة مكائن ​​الحوسبة ، 57 (4): 35-39 ، doi : 10.1145/2580945 ، S2CID 30098719 .
• غانم، فادي؛ فيشكين، أوزي؛ باروا، راجيف (فبراير 2018)، "برمجة متوازية عالية الأداء سهلة تعتمد على PRAM باستخدام ICE"، معاملات IEEE في الأنظمة المتوازية والموزعة ، 29 (2): 377-390 ، doi : 10.1109/TPDS.2017.2754376 ، hdl : 1903/18521.

• الصفحة الرئيسية لمشروع XMT، مع روابط لإصدار البرنامج، والدروس التعليمية عبر الإنترنت، ومواد لتدريس التوازي .