15068

15068

موازي سازي زمان كامپايل حلقه هاي تودرتو با تاكيد بر بهبود محليت داده ها براي پردازنده هاي چندهسته اي

دكتري

نرم افزار

خردادماه 1394

خردادماه 1394

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

كامپيوتر

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