10143

10143

موازي‌سازي برنامه‌هاي ترتيبي در سطح نخ

كارشناسي ارشد

كامپيوتر گرايش نرم¬افزار

بهمن ماه 1390

بهمن ماه 1390

دكتر سعيد پارسا

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