9872

9872

طراحي و پياده‌سازي يك حل‌كننده چندنخي براي مدل‌هاي كارايي

دريافت درجه كارشناسي ارشد

مهندسي كامپيوتر - گرايش نرم‌افزار

خرداد 1390

خرداد 1390

دكتر محمدعبداللهي ازگمي

چكيده زنجيره¬هاي ماركوف زمان‌پيوسته¬ (‍CTMCs)، براي تحليل كارايي و اتكاپذيري سيستم¬هاي كامپيوتري و ارتباطي مورد استفاده قرار مي‌گيرند. با محاسبه توزيع احتمالات حالات پايدار مدل‌هاي CTMC، بسياري از معيارهاي مفيد كارايي به دست مي¬آيند. اين احتمالات حالات پايدار از حل دستگاه معادلات خطي به دست مي‌آيند. اما مدل¬هاي CTMC براي سيستم¬هاي واقعي بسيار بزرگ بوده، حل آنها زمان¬گير است و از مشكل انفجار فضاي حالت رنج مي¬برند. از سوي ديگر، در سال‌هاي اخير امكان بهره‌گيري از توان محاسباتي پردازنده‌هاي چندهسته‌اي فراهم شده است. استفاده مؤثر از اين فناوري مي‌تواند منجر به كاهش زمان حل مدل‌ها شود. در اين پايان‌نامه يك راه¬حل چندنخي جديد براي حل حالت پايدار مدل¬هاي CTMC ارائه مي¬كنيم. در اين راه‌حل مشكل انفجار فضاي حالت را با استفاده از چندنخي كردن روش‌هاي ضمني تخفيف داده‌ايم. براي حل دستگاه معادلات روش حل عددي تركيبي جديدي معرفي شده است كه سرعت و دقت حل مدل را افزايش مي‌دهد. ايده چندنخي كردن در سطح نرم‌افزار، با استفاده از الگوريتم پيشنهادي براي رنگ‌آميزي گراف وابستگي وظايف و با بهره‌گيري مؤثر از قابليت‌هاي چندنخي بر روي پردازنده‌هاي چندهسته‌اي پياده‌سازي شده است. ابزار ساخته شده توسط محك‌هاي معروف در زمينه ابزارها و فنون حل مدل‌هاي ماركوفي، آزمايش و ارزيابي گرديده كه نتايج حاصله در اين پايان‌نامه ارائه شده است. واژه‌هاي كليدي: حل تحليلي مدل¬هاي كارايي، فرايند‌هاي ماركوف، پردازنده¬هاي چندهسته¬اي، الگوريتم‌هاي موازي، چندنخي كردن.