پاورپوینت بررسي يکي از روش هاي موازي سازي خودکار (pptx) 31 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 31 اسلاید

قسمتی از متن PowerPoint (.pptx) :

بنام خدا 1 بررسي يکي از روش هاي موازي سازي خودکار 2 مقدمه موازي سازي در سطح نخ به دو صورت دانه درشت در سطح حلقه ها و دانه ریز می باشد. موازي سازي دانه درشت تشخیص تکرارهای وابسته تخصیص تکرارها به پردازنده ها موازي سازي دانه ريز افراز بندی کد در قالب نخها با حداقل انتظار برای دریافت نتایج از سایر نخها و خداکثر سرعت اجرایی استفاده از صف تولید کننده – مصرف کننده برای همگام سازی نخهای وابسته مکانيسم سخت افزاري براي ارتباط بين هسته ها آرايه هاي همگام سازي: ارسال و دريافت مقادير از طريق يک صف produce, consume 3 مراحل تبدیل خودکار کد ترتیبی به چند نخی 1. استخراج گراف وابستگی برنامه Program Dependence Graph(PDG) همانند گراف وظايف مشخص کننده انواع وابستگي ها می باشد 2. افراز بندی گراف وابستگی برنامه به نخها با توجه به تعداد هسته ها و نخهای موجود اضافه کردن دستورهای ارتباطي و همگام سازي 3. ایجاد کد چند نخی اضافه کردن دستورهای ارتباطي و همگام سازي 4 1. استخراج گراف وابستگی وابستگي هاي بين جمله ها وابستگي کنترلي وابستگي داده اي حافظه رجيستر وابستگی داده ای از دسترسی دو جمله به یک مکان مشترک حافظه وابستگی داده ای حاصل می شود وابستگی کنترلی فرض کنید G یک CFG و Y و X دو گره در آن هستند در اینصورت Y وایسته کنترلی به G دارد اگر و تنها فقط اگر مسیر P از X به Y درون G وجود دارد به قسمی که Y بر هر گره Z در این مسیر به غیر از X پس تسلط دارد و Y بر X پس تسلط ندارد. 5 6 2- خوشه بندي زمانبندي بر مبناي PDG هدف: کمينه کردن مسير بحراني در گراف مشکل: وجود حلقه در PDG راه حل: رويکرد ساده سازي مسئله و تبديل به گراف بدون حلقه هر حلقه تبديل به يک گره شود! بدست آوردن زمان تقريبي اجراي حلقه و انتساب آن به عنوان وزن گره در نظر گرفتن وابستگي هاي بين حلقه اي در صورتي که خود کد در حلقه باشد به این ترتیب برای حلقه ها یک ساختار سلسله مراتبی ایجاد می شود. موازی سازی در حد تخصیص تکرارها به نخهای متفاوت مد نظر قرار داده نشده است. بدست آمدن PDG بدون حلقه: HPDG یا گراف وابستگی سلسله مراتبی 7 الگوريتم خوشه بندي (GREMIO) 8 الگوريتم خوشه بندي (GREMIO) افرازبندي HPDG با هدف حداکثر سازي بخش هاي موازي با در نظر گرفتن ميزان وابستگي بدون درنظر گرفتن تعداد هسته ها صورت مي گيرد براي افرازبندي، ابتدا به هر گره HPDG وزني معادل زمان تقريبي اجراي آن انتساب داده مي شود و با استفاده از يک الگوريتم heuristic به نام DSC افرازبندي با در نظر گرفتن هزينه ارتباطي صورت مي گيرد الگوريتم شناخته شده برای خوشه بندي: Dominant Sequence Clustering (DSC) - در ابتدا هر گره در یک خوشه قرار داده می شود. هدف کوتاه تر نمودن مسیرهای بحرانی است. - برای هر گره در صورت وجود مسیر بحرانی مشخص می شود. - گراف مرتب سازی توپولوژیک می شود. - هر گره با یک گره قبلی ادغام می شود سربار ارتباطی بیش از میزان تسریع با اجرای موازی باشد. خوشه بندي به منظورتخصيص دستورالعمل ها به خوشه ها صورت مي گيرد سپس زمانبندي خوشه ها به منظورتخصيص خوشه ها به نخ ها (پردازنده ها) صورت مي گيرد. در مرحله بعد(زمانبندي) با توجه به تعداد هسته ها تعدادي از اين بخش ها ممکن است با هم ادغام شوند 9