بخشی از پاورپوینت
اسلاید 2 :
موضوع :طراحی و پیاده سازی یک مکانیزم زمانبندی توسعه پذیر برای مدل BSP
اسلاید 3 :
یک مکانیزم زمانبندی دینامیکی برای مدل موازی BSP
اسلاید 4 :
یک مکانیزم زمانبندی دینامیکی برای مدل موازی BSP
زمانبندي انتساب كارها بصورت كارا از مسائل مهم در طراحي سيستمهاي موازي به شمار ميآيد . اما بخاطر پيچيدگي سيستمها تعداد زياد كارها، پيدا كردن يـك اهحل بهينه معمولا كار بسيار دشواري است . در اين مقاله يك الگوريتم زمانبندي ديناميكي براي مدل موازي BSP پيشنهاد پيشنهاد شده است. اين مدل متشكل از تعـدادي واحـد پـردازنده /حافظـه اسـت كـه از طـريق يـك شـبكه ارتباطـي با يكديگر ارتباط برقرار ميكنند . الگوريتم زمانبندي پيشنهادي بصورت يك رشته از ابـرگامهـا نوشـته شـده اسـت . در هـر ابرگام پردازنده زمانبند به زمانبندي كارها ساير پردازندهها به اجراي كارها ميپردازند . نتايج بدست آمده از اين الگوريتم تحت مدل شبيه سازي شده (Parallel Synchronous Bulk(BSP نشان ميدهد كه ميزان توجه به بار روي پر ازنده ها جريمه ارتباطات بايد متوازن باشد تـا كارهـا بـه شـكل مناسـبي روي پـردازنده هـا توزيع شوند . برخلاف اكثرالگوريتمهاي زمانبندي مدت زمان فاز زمانبندي تنها به نرخ ورود زمان اجراي كارها بستگي ندارد. بلكه مؤثرترين عامل تعداد پردازنده هاست.
اسلاید 5 :
مدل موازي BSP الگوريتم زمانبندي ديناميكي
سـالهاي اخـير شـاهد اسـتفاده روزافـزون از كامپيوترهاي موازي توزيع شده اسـت. در ايـنگونه سيسـتم هـا ايـن مسـئله بوجـود مـيآيـد كـه چطـور كارها بين پـردازنده هـا توزيـع شـوند تا در كمترين زمان ممكن اجرا شوند . اين مسئله بعنوان مسـئله زمانبـندي شـناخته مـي شـود . زمانبـندي كارهـا روي پـردازنده هـا ميتواند بصـورت اسـتاتيكي يـا دينامیكـي انجـام شود. در الگوريتمهاي استاتيكي، انتساب كارهـا بـه پـردازنده ها در زمان كامپايل مشخص ميشود . الگوريتمهاي استاتيكي، اغلـب بـراي زمانبـندي كارهـاي دورهاي بـا طـول عمـر مؤكـد اسـتفاده ميشود. الگوريـتمهـاي اسـتاتيكي در همـه بـرنامه هـا قـابل اسـتفاده نيسـتند . در سيستمهاي بلادرنـگ كارها در زمان جراي برنامه پديد مي آيند بنابراين مشخصات وتعداد آنهـا در زمـان كامـپايل مشـخص نيسـت .
اسلاید 6 :
بنابرايـن زمانبـندي تخصيص كارها به پـردازنده هـا بـايد در زمـان جـراي بـرنامه بصـورت ديناميكـي صـورت پذيـرد. الگوريـتمهـاي دينامیكـي خـود بـه دو گـروه الگو ريـتمهـاي زمانبـندي ديناميكي مـتمركز توزيـع شـده تقسيم ميشوند. در الگوريتمهاي توزيع شده، پردازنده هاي بـيكار بـه يـك صف كار كزي يا توزيع شده مراجعه كرده كار يا كارهايي را بخـود تخصـيص داده اجرا ميكنند . در استراتژي متمركز، یكي از پردازنده هاي سيسـتم بعـنوان زمانبند در نظر گرفته ميشود. فقط پردازنده زمانبند به صف كارها دسترسـي دارد كارهـا را با توجه به بار روي پردازنده ها اطلاعاتي كه در زمان اجـرا از كارهـا پـردازنده هـا بدست مي آورد، بين پردازند ها توزيع مينمايد .
اسلاید 7 :
در زمانبندي ديناميكي بخاطر تخصيص يك پردازنده به زمانبندي قدرت محاسباتی حـدودي كاهش مييابد در ضمن چون اطلاعات مربوط به زمانبندي با ستي در زمـان اجـرا جمـع آوري شود، كلي بنام سربار زمانبندي بوجود مي آيد . چنانچه سيستمهاي موازي داراي حافظه مشترك سراسري باشند، استفاده از الگوريتمهاي زمانبندي توزيع شده راحتتر است. اما اگر حافظه سيستم موازي از نوع توزيع شده باشـد، اسـتفاده از الگوريـتمهاي زمانبندي ديناميكي متمركز اجتناب ناپذير است . هـدف از اين تحقيق طراحي يك الگوريتم زمانبندي ديناميكي متمركزبراي كي از مدلهـاي مـوازي مطـرح موسـوم به مدل BSP است. در مدل BSP سيستم از تعدادي واحد پردازنده/حافظه تشكيل شده است پردازندهها از طريق يك شبكه تباطي با يكديگربه مبادله اطلاعات ميپردازند. ادامـه ايـن مقاله بصورت زير سازماندهي شده است .
اسلاید 8 :
بخش 2 به بررسي برخي از الگوريـتمهـاي زمانبندي ديناميكي متمركز توزيع شده مي پردازد. در بخش 3 برخـي از مفاهـيم اصـلي مـدل BSP كه در طراحي الگوريتم زمانبندي پيشنهادي مـورد اسـتفاده قـرار گرفـته انـد، مطـرح شـده اسـت . بخـش 4 به طراحي الگوريتم پیشـنهادي نحـوه پياده سازي آن روي مدل BSP اختصاص يافته است. بخش 5 بـه ارزيابي زمانبند ميپردازد و نهایتا نتایج وپيشنهادات جهت كار آينده در بخش 6 ارائه شده است.
اسلاید 9 :
مروري بر الگوريتم هاي زمانبندي موجود
همانطوريكه گفته شد الگوريتمهاي زمانبندي ديناميكي به دو گروه متمركز توزيـعشـده تقسيم ميشوند . در اين بخش برخي از الگوريتمهاي طراحي شده در هـر دو گـروه، كـه از ايده هاي مطرح شده در آنها در طراحي الگوريتم پيشنهادي استفاده شده است، بطور مختصر معرفي ميگردند.
Self Scheduling ســاده تريــن شــكل زمانبــندي اســت. در ايــن الگوريـتم، هـر پـردازنده بـيكار يـك تكرار از حلقه كارها را از طر يق دسترسي به صـف مشـترك كارهـا بخـود اختصـاص داده اجـرا مـيكـند . به علت اينكه هر پـردازنده، هـر بـار فقـط يـك كـار را بخـود تخصيص مي دهد، اين الگوريتم بار كـاري را بخوبـي بيـن پردازندهها متوازن ميكند ولي بهمين علت سربار زمانبندي زيـادي تولـيد مـيكـند.
اسلاید 10 :
بـراي كـاهش ايـن سـربار زمانبندي الگوريتم Chunk Scheduling پيشـنهاد شـده اسـت . ايـن الگوريـتم هر بار تعداد ثابتي از كارها را به هر پردازنده انتساب ميدهد . بنابراين تعداد دسترسي هاي پردازنده ها به صـف كـار كـاهش مـييـابد. بخاطر تعداد زياد كارهايي كه هر بار به پردازنده ها انتسـاب داده مـيشـود اين الگوريتم بيشتر از SS مستعد عدم توازن بار است. زيرا ممكن است زمان پردازش كارها بصورت صعودي يا نزولي كاهش يا افزايش پيدا كـند.
اسلاید 11 :
بـه مـنظور كاهش عدم توازن بار همزمان با پايين نگهداشتن سربار زمانبندي الگوريتم هاي Guided Self Scheduling و Factoring پیشنهاد شد.
ايـن الگوريـتمها مانند cs هر بار گروهي از كارها را به پردازنده ها تخصـيص ميدهند. تعداد كارهاي گروه كارها بصورت غيرخطي كاهش مييابد . همـانطور كـه تعـداد تكـرارهاي باقيمانده كاهش مييابد، اندازه دسته هاي كار نيز كوچـك مـيشـود بهميـن علـت بـار روي پـردازنده هـا نسبت به الگوريتم قبلي مـتوازنتـر مـيگـردد.traipzoid self scheduling انـدازه دسته هاي كار بصورت خطي كاهش ميدهد در مقايسه با استراتژي هاي غير خطي توازن بهتري بين سربار زمانبندي بار كاري پردازنده ها ايجاد ميكند.
اسلاید 12 :
الگوریتمهای زمانبندی دینامیکی متمرکز
پردازنده زمانبند در الگوریتم Myopic در شروع زمانبندی، صف کارها را بـر اسـاس طـول عمـر آنهـا بصورت صعودی مرتب میکند. برای پیدا کردن یک زمانبـندی امکان پذیر از یک درخت جستجو استفاده میشود. ریشه درخت بعنوان یـک زمانبندی تهی در نظر گرفته می شود. الگوریتم هر بار با بکار بردن یک تابع روی بخشـی از صـف کار، کاری که کوچکترین مقدار را برای تابع از خود نشان دهـد انـتخاب می کند. این تابع هر بار برای یک پردازنده بکار گرفته می شود و با خصوصـیات آن پردازنده مطابقت دارد. سپس کار انتخاب شده به پردازنده مزبور انتسـاب داده مـی شـود و ایـن انتسـاب به عنوان یک گره به درخت جستجو اضافه می شود. هر یک از گره های درخت دارای فرزندانی به تعداد پردازنده های سیستم اسـت. پـس از انتساب یک کار به پردازنده ای، درخت توسط گره نشان دهنده آن پـردازنده توسعه داده می شود. هرگاه الگوریتم زمانبندی به گره ای برسد که دیگر قـادر بـه ادامـه توسـعه درخت نباشد، یک مرحله به عقب برگشته و کار را مجددا شـروع مـی کـند تا زمانی که به انتهای صف کار یا پایان فاز زمانبندی برسد و یا به جایی برسد که دیگر امکان زمانبندی هیچ کار دیگری وجود نداشته باشد.
اسلاید 13 :
الگوریتمهای زمانبندی دینامیکی متمرکز
الگوریــتمهــای گــروه SAS, SADS, RT_SADS,) SADS (MESADS, … اسـتراتژیهای زمانبندی متمرکزی هستند که از طریق تکنیک انشعاب و حد١ و با توجه به میزان وابستگی کار به پردازنده، به تخصیص کارها به پـردازنده ها می پردازند. SADS با همپوشانی زمانبندی و اجرای کارها می کوشد تـا زمـان اجرای کل برنامه را کاهش دهد. در این مکانیزم قبل از انتساب یک کار بـه پـردازنده ای، پـردازنده هـا بـر اسـاس بـار جاری خود به ترتیب صعودی مرتب مـی شـوند. کـار به پردازنده ای انتساب داده می شود که کمترین میزان بار را داشته باشد. پس از هر انتساب بار پردازنده ها بهنگام میشود.[2,3]
اسلاید 14 :
مدل محاسباتی BSP
مـدل BSP تعمیمـی از مـدل PRAM اسـت کـه توسـط پروفسـور L. G. Valiant از هـاروارد در سـال ۰۹۹۱ بعـنوان یک مدل پل برای محاسبات موازی پیشنهاد شده است. در طول سالهای گذشته این مدل بوسیله پروفسور McCall و Valiant توسعه یافته است.[6]
مدل BSP شامل بخشهای زیر است:
مجموعهای از کامپیوترها که هر یک دارای حافظه محلی میباشند.
یک شبکه ارتباطی که پیامها را از نقطهای به نقطه دیگر انتقال میدهد.
مکانیزمی برای همزمانسازی همه یا گروهی از پردازنده ها.
بـرنامه هـای BSP بصـورت یـک رشته از ابرگام ها نوشته می شوند. هر ابرگام متشکل از سه بخش است: محاسبات روی داده های محلی، ارسال و دریافت پیغام بـه مـنظور دسترسـی به داده های غیر محلی و همگامسازی سدی٢ به منظور تکمیل همـه عملـیات ارتباطـی و از سرگیری محاسبات روی داده های محلی یا داده هایی که از طریق تبادل پیام به یک پردازنده رسیده اند.
اسلاید 15 :
مدل محاسباتی BSP
ارتـباطات در مـدل BSP بـه دو شـکل مـی توانـد صورت پذیرد: دسترسی به حافظـه دور بصـورت مسـتقیم یـا 3DRMA و دسترسـی بـه حافظه دور از طریق تـبادل پـیام یـا BSMP٤. ارتـباطات در مدل BSP نه کاملا بازدارنده٥ است و نه کـاملا غیر بازدارنده٦. پردازنده ها می توانند محاسبات خود را فورا بعد از برقراری ارتـباط ادامـه دهـند(غـیر بـازدارنده)، امـا باید منتظر شوند تا همه ارتباطات قبل از شروع ابرگام جدید انجام شوند(بازدارنده).
مـدل کارایـی BSP دارای چهـار پارامـتر اسـت کـه از آنهـا مـی تـوان بـرای پـیش بینـی زمان اجرای یک الگوریتم طراحی شده تحت BSP استفاده کرد. این چهار پارامتر را میتوان بصورت زیر تعریف کرد:
:p تعـداد پردازنده ها، :s سرعت پردازنده،:l تأخیر شبکه و به معنی کمترین تعداد ممکـن از گامهـای زمانی بین عملیات همزمانی است، :g نرخ راندمان ارتباطات و بعـبارت دیگر تعداد کل عملیات محلی انجام شده بوسیله همه پردازنده ها در یک ثانـیه، تقسـیم بـر تعدادکـل کلمـات انتقال داده شده توسط شبکه ارتباطی در یک ثانـیه اسـت. l و g تابعـی از پارامـتر p هسـتند. برای شرح این پارامترها بایستی h-relation معرفی شود. یک h-relation یک الگوی ارتباطی سراسری است به ایـن معـنا کـه هـر پردازنده می تواند حداکثر h واحد داده بفرستد یا دریافت کند. واحدهـا مـی توانند لغات یا پیامها باشند. هزینه انجام یک h-relation ، بصورت gh تعـریف شـده اسـت. تعـریف هزیـنه به این صورت بیان می شود که فرقی بین فرسـتادن m پـیام شـامل ۱ واحد داده، یا ۱ پیام شامل m واحد داده وجود ندارد. هزینه در هر دو حالت mgh است.
اسلاید 16 :
مدل محاسباتی BSP
هزینه یک برنامه BSP می تواند با استفاده از پارامترهای توصیف شده در بالا و برخـی اطلاعـات اضـافی پـیش بینـی شـود. یـک مـدل هزینه ساده در محاسبات موازی میتواند بصورت زیر بیان شود:[6]
Cs = max { wi } + max { hig } + l
که Cs هزینه یک ابرگام و wi زمان محاسبات پردازنده i در ابرگام است. hi
تعـداد واحدهـای داده که پردازنده i در طول ابرگام میفرستد یا دریافت میکند.
پارامـترهای w و g و l باید برحسب s (سرعت پردازنده) بیان شوند. مقادیر wi و hi مـی توانـند بـا انـدازه گـیری زمـان اسـتفاده شـده و تعـداد بایتهای فرستاده شده محاسـبه شـوند. همانطور که از رابطه بالا مشخص است، هزینه یک ابرگام بستگی به کندترین پردازنده، بیشترین میزان دادهای که یک پردازنده میفرستد یا دریافت مـی کـند و هزینه همگام سازی دارد. هزینه یک برنامه کامل BSP برابر با مجموع هزیـنه همـه ابـرگام هـا در بـرنامه است. با توجه با فرمول فوق مشخص می شود که فاکتورهایی که در ایجاد و طراحی برنامه های BSP مهم هستند، عبارتند از:[5]
محاسبات در هر ابرگام باید بین پردازنده ها متوازن باشد.
ارتـباطات بیـن همه پردازنده ها باید متوازن باشد تا از اختلافات بزرگ hi اجتناب شود.
بخاطر هزینه بالای همزمانی، تعداد ابرگامها باید به حداقل برسد.
اسلاید 17 :
الگوریتم پیشنهادی
در ایـن بخش یک زمانبند دینامیکی متمرکز برای مدل موازی BSP طراحی میگردد.
مدل کارها
سیستمی که الگوریتم پیشنهادی برای آن طراحی میشود دارای یک مجموعه از کارهـای نامتـناوب١، مستقل، قبضه نشدنی و بلادرنگ با طول عمر مؤکد است. منظور از کارهای نامتناوب، کارهای است که زمان ورود تصادفی دارند. کارهای تشـکیل دهـنده یـک برنامه ممکن است مستقل یا وابسته باشند. زمانبندی کارهای مسـتقل راحـت تـر اسـت، چـون اجـرای هـر کار تأثیری روی سایر کارها ندارد و کارهـا بـه هـر ترتیبـی مـیتوانـند اجـرا شوند. اما در کارهای وابسته ترتیب اجرای کارهـا در نتیجه کل سیستم مؤثر است، زیرا خروجی هر کار معمولا ورودی یک یـا چـند کـار دیگـر را تشکیل میدهد. کارهای سیستم از نوع قبضه نشدنی هستند یعنـی زمانـی که کاری شروع به اجرا کرد تا هنگامی که پایان نیافته و یا با وقفهای مواجـه نشـده، کنـترل پـردازنده را از دسـت نخواهد داد. کارهای اکیدا بلادرنگ کارهایـی هسـتند کـه اگر در مهلت مقرر اجرا نشوند، در کارایی کل سیستم تأثیر منفی بجا خواهند گذاشت.
اسلاید 18 :
طراحی الگوریتم
در طراحی الگوریتم از ایده های بکار گرفته شده در الگوریتم های Myopic
(در نظـر گرفتـن تعـدادی محـدود کـار در هـر بررسـی بـرای تخصـیص کـار بـه پـردازنده) و الگوریـتمهـای گـروه SADS (بکارگیری تابع تخصیص کار روی پـردازنده هـا بجـای کارهـا) و نـیز الگوریـتم هـای زمانبـندی توزیع شده(تخصیص تعـدادی کـار در هـر گـام زمانبندی به پردازنده ها بجای تخصیص یک کار) بهره گرفته شده است.
بـا شـروع کـار سیسـتم، کارهـای تشـکیل دهنده برنامه ایجاد شده و به ترتیب ورود به سیستم وارد صف کار پردازنده زمانبند میشود.
برای هر کار زمان اجرا و داده های مورد نیاز بطور تصادفی انتخاب می شوند. برای پیدا کردن یک زمانبندی امکانپذیر، از یک درخت جستجو و تکنیک انشعاب و حد استفاده میشود. روند پـیدا کـردن زمانبـندی بدیـن صـورت است که ابتدا بخشی از کارهای موجود در صـف کـار (مثلا K کار اول) بر اساس سه مشخصه زمان ورود، طول عمر و زمان پردازش (فرض می شود که پردازنده زمانبند هر سه زمان مورد نیاز را برای هر کار از طـریق پـیش پـردازش مـی دانـد) با استفاده از رابطه زیر بصورت صعودی مرتب میشوند.
(زمان پردازش + زمان ورود)- طول عمر علـت ایـنکه K کـار برای مرتب شدن انتخاب می شوند این است که در یک فـاز زمانبـندی تعداد محدودی کار می توانند زمانبندی شوند. بنابراین نیازی نیست کـه همـه کارهـا مرتـب شـوند. تعـداد کارهـا بـا توجـه بـه تعداد پردازنده ها تعیین میشود.
اسلاید 19 :
طراحی الگوریتم
بـرای هر پردازنده اجرایی، در حافظه محلی پردازنده زمانبند یک آرایه هزینه در نظـر گرفـته مـی شود. همچنین جدولی از داده های موجود در حافظه محلی هر پـردازنده، در حافظـه پـردازنده زمانبـند وجـود دارد. در اولین فاز زمانبندی، آرایه هزینه برای همه پردازنده های اجرایی مقدار صفر دارد. با تخصیص هر کار به یک پـردازنده، آرایـه هزیـنه بـرای آن پـردازنده بهنگام می شود. برای تخصیص کار به پردازنده، زمان اجرای کار روی همه پردازنده ها از رابطه زیر محاسبه میشود. آن تخصیص داده میشود. اگر هنگام بررسی کاری برای تخصیص به یک پردازنده، هیچ یک از پردازنده ها نتوانند آن کار را در موعد مقرر اجرا نمایند، تخصیص کار به پردازنده یک مرحله به عقب برمیگردد و کار قبلی به پردازنده دیگری که دومین زمان بهینه را برای اجرای کار داشته باشد، تخصیص داده و مراحل قبل مجددا دنبال میشوند. مسئله دیگری که باید به آن پرداخته شود مدت زمان گام زمانبندی است. یک گام زمانبندی به چند روش ممکن خاتمه پیدا کند.
در درجه اول یک گام زمانبندی ممکن است با رسیدن به انتهای صف کارها به پایان برسد. دومین علت برای خاتمه گام زمانبندی تمام شدن زمان تخصیص داده شده به زمانبندی است.
اسلاید 20 :
طراحی الگوریتم
این زمان با توجه به نرخ ورود کارها به سیستم، متوسط زمان پردازش آنها، بار روی پردازنده ها، کوتاهترین زمان بین اجرای کارهایی که در مرحله قبل زمانبندی شدهاند، تا اجرای کارهای جدید و کمترین زمان ممکن از لحظه ورود یک کار به صف کار پردازندهای تا آماده شدن آن کار برای اجرا، تعیین میشود. میتوان گفت این زمان برابر است با:
Qs(j) <= Min [Max [min-slack, min-load], k/λ ]
که
Qs(j) مدت زمان گام زمانبندی j ،k میانگین تعداد کارهای وارد شده در هر گام زمانبـندی، λ نـرخ ورود کارها به سیستم، min-load کمترین زمان ممکن برای پـردازنده هـا قـبل از اجـرای کارهـای جدید و min-slack کمترین زمان پس از انتساب یک کار به پردازندهای تا آماده شدن آن کار برای اجرا است. فاکتور /λ k بـرای وقتـی اسـت که تعداد زیادی کار بطور ناگهانی وارد سیستم می شوند. در چنیـن حالتـی λ افـزایش یافته و k ثابت است. بنابراین طول فاز زمانبندی کاهش مییابد تا کارها سریعتر به پردازنده ها اختصاص یابند.
