أفكار لمشروع باستخدام CUDA؟

[Khaled Alshaya 826]

السلام عليكم ...

أود سماع أفكاركم حول مشاريع صغيرة على منصة CUDA. هل لدى أحدكم فكرة معينة يود رؤيتها تطبق في العالم المتوازي و العالم المتتالي مع مقارنة بسيطة؟

الفكرة التي سأطبقها إن شاء الله, إن لم يكن هناك فكرة أكثر فائدة :sad: هي إيجاد الـ Transitive Closure لـ Undirected Graph(و Directed Graph بالمحصلة). هذه ستتضمن العديد من الأجزاء الجيدة و السهلة التطبيق, إضافة إلى أنها أكثر من مناسبة للعمل بشكل متوازي. إضافة إلى ذلك, سأقوم بمقارنة أداء النسخة المكتوبة على CUDA بنسخة مكتوبة بـ Standard Cpp و ربما بنسخة أخرى مكتبة بـ Boost.uBlas! الهدف هو التعرف على CUDA لا أكثر, و هذه مسألة يسهل كتابة برنامج متوازي لحلها. ربما أقوم بكتابة نسخة منقحة مثلاً ليكون رفع المصفوفات لأس ما باستخدام exponentiation by squaring أو ربما أتهور أكثر و أقوم بكتابة addition chain exponentiation و لكن لا أدري حقيقة إن كنت سأصل إلى هذه النقطة, ادعوا لنا بالتوفيق في تعلم CUDA :)

فائدة المشروع تكمن في أننا يمكن أن نستخدم الفكرة في التالي: تصور أن لدينا الأعضاء في الفريق العربي للبرمجة, و مع كل عضو لدينا قائمة بأصدقائه. نريد أن نقسم الأعضاء إلى disjoint subsets بحيث أن الأعضاء في أي مجموعة أصدقاء مباشرين أو غير مباشرين(صديق صديقك هو صديقك, و صديق صديق صديقك هو صديقك و هلم جرا). ببساطة, أي عضو في أي مجموعة ليس هناك علاقة مباشرة أو غير مباشرة بينه و بين أي عضو في أي مجموعة أخرى. يمكن أن يكون نظام للدعايات في الموقع, أو خلافه ربما من يستفيد من هكذا تحليل. عموماً هذه هي الفكرة!

تحياتي...

تم تعديل 25 Sep 2011 بواسطه Khaled.Alshaya

[-Ahmed Hassan 15]

السلام عليكم ...

أود سماع أفكاركم حول مشاريع صغيرة على منصة CUDA. هل لدى أحدكم فكرة معينة يود رؤيتها تطبق في العالم المتوازي و العالم المتتالي مع مقارنة بسيطة؟

الفكرة التي سأطبقها إن شاء الله, إن لم يكن هناك فكرة أكثر فائدة :sad: هي إيجاد الـ Transitive Closure لـ Undirected Graph(و Directed Graph بالمحصلة). هذه ستتضمن العديد من الأجزاء الجيدة و السهلة التطبيق, إضافة إلى أنها أكثر من مناسبة للعمل بشكل متوازي. إضافة إلى ذلك, سأقوم بمقارنة أداء النسخة المكتوبة على CUDA بنسخة مكتوبة بـ Standard Cpp و ربما بنسخة أخرى مكتبة بـ Boost.uBlas! الهدف هو التعرف على CUDA لا أكثر, و هذه مسألة يسهل كتابة برنامج متوازي لحلها. ربما أقوم بكتابة نسخة منقحة مثلاً ليكون رفع المصفوفات لأس ما باستخدام exponentiation by squaring أو ربما أتهور أكثر و أقوم بكتابة addition chain exponentiation و لكن لا أدري حقيقة إن كنت سأصل إلى هذه النقطة, ادعوا لنا بالتوفيق في تعلم CUDA :)

فائدة المشروع تكمن في أننا يمكن أن نستخدم الفكرة في التالي: تصور أن لدينا الأعضاء في الفريق العربي للبرمجة, و مع كل عضو لدينا قائمة بأصدقائه. نريد أن نقسم الأعضاء إلى disjoint subsets بحيث أن الأعضاء في أي مجموعة أصدقاء مباشرين أو غير مباشرين(صديق صديقك هو صديقك, و صديق صديق صديقك هو صديقك و هلم جرا). ببساطة, أي عضو في أي مجموعة ليس هناك علاقة مباشرة أو غير مباشرة بينه و بين أي عضو في أي مجموعة أخرى. يمكن أن يكون نظام للدعايات في الموقع, أو خلافه ربما من يستفيد من هكذا تحليل. عموماً هذه هي الفكرة!

تحياتي...

Quadratic sieve

[Khaled Alshaya 826]

يا أخ أحمد الخوارزمية التي تفضلت بها كيف تقترح كتابتها؟ كتابة دالة لتحليل arbitrary precision integer صعب باعتقادي باستخدام الـ SPMD. ربما لعمل تحليل لمصفوفة من الأعداد؟ و لكنها لن تكون مختلفة عن الطريقة العادية sequential. عموماً, كنت أتحمس لفكرة يسهل إيجاد حل لها تحت SPMD model, أقصد هنا أن المشكلة يمكن أن تجزأ إلى أجزاء تعمل بشكل متوازي, أما تطبيق خوارزمية sequential على عدة عناصر بيانات فهذا ممكن أيضاً و لكنه ليس فكرة جيدة للتطبيق على CUDA برأيي الشخصي. و بصراحة أيضاً, الخوارزمية صعبة قليلاً لإنجازها في يومين أو ثلاثة و التأكد أنها تعمل بشكل سليم :S

تم تعديل 26 Sep 2011 بواسطه Khaled.Alshaya

[محمد علاء الدين 885]

إذا كان لديك الوقت اقترح عليك كتاب GPU Computing Gems حيث يحتوى على العديد من الامثله الرائعه و يعطيك الـ algorithms لتستطيع التطبيق، ايضا يمكنك تحميل الكود من صفحة الكتاب.

ملحوظه: لا تحتاج ان تكون على درايه بالـ computer graphics لتطبيق الأمثله.

و الله ولي التوفيق

[Khaled Alshaya 826]

شكراً أخ محمد, الكتاب يحوي الكثير من الأفكار الجيدة.