EXPERIMENTAL EVALUATION OF PARALLEL PROGRAM SCALABILITY ON XEON PHI SMP

Abstract

قانون مور اصبح يتجه الى نهايته، ويظهر ذلك جليا في ظهور المعالجات متعددة الأنويه. البرمجة لهذه الرقائق تظهر تحديات ومشاكل جديدة في وجه المبرمجين. في هذا السياق، نقوم على تقييم تجريبي لتدرجية البرامج الموازية في المعالجات عديدة النواة ذات التماثلية باستخدام نموذج برمجة OpenMP. قمنا باختيار فئتين من التطبيقات. الفئة الأولى التطبيقات ذات الحمل الثابت والفئة الثانية التطبيقات ذات الحمل المتغير. في الفئة الأولى قمنا باختيار ضرب المصفوفات والتي تصنف من مكتبة علم الجبر الأساسي، وايضا تم اختيار تطبيق من التحليل العددي في حل المعادلات الخطية يطلق عليه اسم JACOBI. في حقيقة الأمر قمنا بتحليل وتنفيذ وتحسين هذه البرامج. في ضرب المصفوفات قمنا باستخدام خوارزمية STRASSEN والتي لها حساب تعقيد اقل من حساب التعقيد لعملية ضرب المصفوفات الأساسية. التحسين لدينا يعتمد على اعادة ترتيب المصفوفات البينية لتقليل الحجم المطلوب، واستخدام المشي الأولي للمصادر، بالإضافة الى استدعاء المكتبة MKL للمصفوفات ذات الحجم الصغير. النتائج اثبتت ان طريقتنا استطاعة ان تتغلب على استخدام المكتبة MKL لوحدها في احجام المصفوفات الكبيرة بنسبه تتراوح من 8% الى 24%. في تطبيق JACOBI لوحظ عدم تدرجية اداءه بسبب الاحتياج الكبير للمزامنة في اثناء التنفيذ و خصوصا في التكرير ما بين جميع ال Thread العاملة. لتحسين العمل تم استكشاف ثلاث انواع من التطبيق 1) المتزامن 2) الغير متزامن 3)المتزامن المسترخي. في المتزامن تم استخدام مزامنه واضحه للعيان. في الغير متزامن تم حذف المزامنة وفي الحالة الأخيرة تم اعادة كتابة المزامنة وذلك من خلال السماح بالتداخل ما بين عمليات التكرار باستخدام النتائج الجزئية من كل Thread. يجدر الإشارة ان الغير متزامن يستخدم النتائج الحالية والتي يمكن ان تكون خليط من النتائج السابقة والحديثة والتي تقلل من سرعة التقاء الخوارزمية بالحل. النتائج اظهرت ان المزامنة تأخذ 50% من وقت النفيذ في حالة المصفوفة بحجم 4096. الغير متزامن يعطي افضل النتائج بسبب حذف المزامنة ولكن في حالة قبول الحل التقريبي. في حالة الحل الدقيق فإن التزامن المسترخي اظهر تحسن بالإداء على التزامن بمقدار, 57.16$.42.6%, 32.6% في الأحجام 3840 7680 15360 30720 باستخدام 60 نواة. في الفئة الثانية تم اختيار مشكلة كلاسيكية تحاكي حركة الأجسام في الفراغ تدعي (N-body). تم تنفيذ حل تقريبي للمشكلة باستخدام خوارزمية Barn-Hut. تعتمد هذه الخوارزمية على بنية الشجرة الثمانية لتمثيل توزيع الأجسام بالفراغ. حيث يتم تخزين البيانات التراكمية للكتلة المركزية في كل عقدة، للشجرات الجزئية التي اسفلها. وايضا من تحديات الخوارزمية هو تغير توزيع الحمل على ال Thread عند الانتقال من خطوة الى الثانية وذلك بسبب حركة الأجسام في الفراغ. للتحسين تم تطوير توزيع للحمل بشكل ديناميكي بالإضافة الى زيادة محلية البيانات. النتائج اظهرت ان الحمل التراكمي يتناسب بشكل خطي مع وقت التنفيذ باستخدام احجام مختلفة تتراوح من 1 مليون الى 4 مليون. بالإضافة الى ذلك فان هناك تحسين بالتسريع للعملية بمقدار 42% و 36% في المشاكل بحجم 1 مليون و 4 مليون مقارنه بالطريقة الثابتة لتوزيع الأحمال. إن هذه الطريقة نوصي باستخدامها كاستراتيجية في تحسين المترجمات عند القيام بترجمة للمشاكل ذات الحمل المتغير