وثيقة

A parallel algorithm for solving large scale markov chains on a high performance computer

الناشر
Sultan Qaboos University
ميلادي
2012
اللغة
الأنجليزية
الملخص الإنجليزي
The use of large scale Markov chains participate extensively in many different disciplines, such as biological, chemical, physical and social science as well as in business and engineering. In many cases, generated models are complex and very large which, in turn, poses a number of challenges in terms of memory requirements and computation time. Parallel computing techniques provide a good alternative to overcome such constraints. However, to take the advantage of Parallel computation we required to ensure the communication between the processors is reduced as minimum as possible. In this report, the concern of the memory requirement is addressed by using a distributed memory machine and sparse representation. A new Aggregation Isolation algorithm (AI) has been studied and a sparse sequential version has been implemented to solve the both computation as well as memory storage requirements. In this thesis, a parallel sparse version of the Al algorithm (PAI) has been proposed and developed. Our experimental study shows that for the tested model the convergence rate of PAI is slower than: Al. This can be explained by the presence of a very strong Gauss-Seidel effect in AI algorithm which is lost in the parallel version PAI which has been implemented on the Sultan Qaboos University High Performance Computer (HPC) system
الوصف
Thesis
الملخص العربي
تستخدم سلاسل ماركوف (Markov Chain) على نطاق واسع في جميع الفروع العلمية و لاسيماء في العلوم الكيميائية والبيولوجية، و في العلوم الاجتماعية وإدارة الأعمال و الهندسة. وتعتبر سلاسل مارکوف من اهم ادوات بناء النماذج للقيام بالتحليل الحسابي و الذي يواجه بدورة الكثير من التعقيدات في البناء و التحليل و ایجاد الحلول لها.و من اهم تلك التحديات كيفية تخزين تلك السلاسل الكبيرة و كيفية بناء خوارزميات قادرة على ايجاد الحلول لها في أوقات قصيرة و قياسية. و من اجل مواجهة تلك التحديات قامت هذة الدراسة باستخدام احدث الخوارزميات و تعرف ب( Aggregation Isolation).و عند تصميمها تم تمثيل تلك السلاسل بإستخدام ما يعرف ب(Sparse Presentation) و التي من خلالها تتخلص من جميع قيم الأصفار. كما قامت هذه الدراسة في إعادة تنفيذ خوارزمة AI بالحوسبة المتوازية (Parallel Programing) مع مراعاة الحفاظ على خصائص هذه الخوارزمية من حيث تكاملها و تراكيبها و تماسك متغيراتها باستخدام عملية الدوران و ذلك من اجل معرفة ما قد يساهمة هذا البناء المتوازي في التقليل من الوقت الازم الايجاد الحل الحقيقي لها و الاستفادة من زيادة ذاكرة التخزين المتواجدة في مختلف الحواسيب المشتركة في العمليات الحسابية. و من خلال التجارب المختلفة بالنموذج المستخدم (Banded Matrix) اتضح بأن تنفيذ تلك الخوارزمية في الحواسيب المتوازية لها تأثير سلبي على الوقت الذي تستغرقة (زيادة في الوقت لايجاد الحلول لتلك السلاسل ويفسر هذا بالتأثير الكبير لخاصية غاوس زايدل ( Gauss - Siedel ) المتواجدة في نسخة البرنامج التسلسي و الذي فقدت خاصيتها عند تنفيذ تلك الخوارزمية في الحواسيب المتوازية.علما بأن النسخة المتوازية قد تم تنفيذها على حواسيب فائقة السرعة (HPC) توفرها جامعة السلطان قابوس من أجل أغراض البحوث العلمية وتعرف هذه البيئة بنظام بهلاء.
قالب العنصر
الرسائل والأطروحات الجامعية