سیستم های چندین پردازنده ای

سیستم های چندین پردازنده ای

اسلاید 1: سیستم های چندین پردازنده ایفصل اول1. سیستم های چندپردازنده ای2. سیستم های چند کامپیوتری3. سیستم های توزیع شده

اسلاید 2: سیستم های چندین پردازنده ایشکل(a) سیستم چند پردازند های را نشان می دهد که به آن مدل حافظه ی اشتراکی نیز می گویند.شکل(b) سیستم چند کامپیوتری را نشان می دهد که به آن مدل تبادل پیام نیز گفته می شود.شکل(c) سیستم توزیع شده در یک شبکه گسترده را نشان می دهد.

اسلاید 3: سیستم چند پردازنده ایتعریف: سیستم چند پردازند ه ای یک سیستم کامپیوتری است که از دو یا چند پردازنده CPU شکل گرفته و آنها دسترسی کامل به حافظه ی اشتراکی RAMدارند.

اسلاید 4: سخت افزار سیستم چندپردازنده ایچند پردازنده ای مبتنی بر باس

اسلاید 5: سخت افزار سیستم چندپردازنده ایچندپردازنده ای با دسترسی یکنواخت(UMA) به کمک سوئیچ Crossbar

اسلاید 6: سخت افزار سیستم چندپردازنده ایچندپردازنده ای با دسترسی یکنواخت(UMA) با استفاده از شبکه های راهگزینی چند طبقه ای را به کمک با سوئیچ های 2×2 می سازند. شکل(a) یک سوئیچ 2×2 و شکل(b) فرمت پیام های ارسالی در این سیستم را نشان می دهد.

اسلاید 7: سخت افزار سیستم چندپردازنده ایشبکه راهگزینی امگا

اسلاید 8: سخت افزار سیستم چندپردازنده ایمشخصات سیستم های چندپردازندای با دسترسی غیریکنواخت(NUMA)1. فقط یک فضای آدرس برای تمامی پردازند ها وجود دارد.2. دسترسی به حافظه راه دور فقط توسط فرمان های LOAD و STORE انجام می گیرد.3. دسترسی به حافظه راه دور کندتر از حافظه ی محلی است.

اسلاید 9: سخت افزار سیستم چندپردازنده ایشکل(a) نمونه ای از سخت افزار NUMA با 256 گرهشکل(b) فلیدهای آدرس حافظه ی 32 بیتی شکل(c) مشخصات دارکتوری در گره 36 ام

اسلاید 10: انواع سیستم های عامل چندپردازنده ایهر پردازنده CPU به طور مجزا سیستم عامل مربوط به خود را دارد.Bus

اسلاید 11: انواع سیستم های عامل چندپردازنده ایچندپردازنده ای ارباب برده(Master Slave)Bus

اسلاید 12: انواع سیستم های عامل چندپردازنده ایچندپردازنده ای متقارن (SMP)Bus

اسلاید 13: همزمانی سیستم های چندپردازنده ای متقارندستورالعمل اتمیک TSL روی چندپردازنده ای درست عمل نمی کند، لذا برای عملکرد درست باید این دستور در یک سیکل اجرا شود یا با اجرای آن باس را بتواند قفل کند.

اسلاید 14: همزمانی سیستم های چندپردازنده ای متقارنجهت جلوگیری از پدیده cash thrashing می توانیم از چند lock برای کنترل ناحیه ی بحرانی استفاده کنیم

اسلاید 15: روش های زمانبندی چندپردازنده ایزمانبندی پروسس های مستقلاشتراک زمانیLPTRLPTزمانبندی thread هااشتراک مکانیGangزمانبندی پروسس های وابستهالگوریتم های که به کمک گراف وظایف زمانبدی را انجام می دهند

اسلاید 16: زمانبندی پروسس های مستقل: اشتراک زمانیدقت کنید که در این زمانبندی از یک ساختمان داده همانند صف ساده یا اولویت دار استفاده می کند.

اسلاید 17: زمانبندی پروسس های مستقل: LPTاولویت زمانبندی در الگوریتم LPT (Longest Processing Time) طولانی ترین زمان اجرایی پروسس ها است. بنابراین پروسس ها را بر طبق زمان اجرایی آن ها به صورت نزولی مرتب نموده و به ترتیب پردازنده های خالی به آنها اختصاص داده می شود.زمابندی LPT انحصاری میباشد.

اسلاید 18: زمانبندی پروسس های مستقل: LPTمثا ل : در یک سیستم 3 پردازنده ای 10 وظیفه (پروسس) با زمان اجرایی به صورت لیست زیر داریم : ET={ 12 , 8 , 10 , 5 , 11 , 7 , 9 , 6 , 3 , 2 } T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 الف) زمانبندی این 10 وظیفه (Task) را با الگوریتم LPT انجام داده و با نمودار Gantt رسم نموده و زمان پایان اجرای آنها را بدست آوریدب) افزایش سرعت این سیستم چند پردازنده ای را نسبت به تک پردازنده ای بدست آورید.

اسلاید 19: زمانبندی پروسس های مستقل: RLPTاولویت زمانبندی در الگوریتم LPT (Reverse LPT) طولانی زمان اجرایی پروسس ها است. اولویت این الگوریتم برعکس LPT است.زمابندی RLPT نیز انحصاری میباشد.

اسلاید 20: زمانبندی پروسس های مستقل: RLPTمثا ل : در یک سیستم 3 پردازنده ای 10 وظیفه (پروسس) با زمان اجرایی به صورت لیست زیر داریم : ET={ 12 , 8 , 10 , 5 , 11 , 7 , 9 , 6 , 3 , 2 } T1 T2 T3 T4 T5 T6 T7 T8 T9 T10الف) زمانبندی این 10 وظیفه (Task) را با الگوریتم RLPT انجام داده و با نمودار Gantt رسم نموده و زمان پایان اجرای آنها را بدست آوریدب) افزایش سرعت این سیستم چند پردازنده ای را نسبت به تک پردازنده ای بدست آورید.

اسلاید 21: زمانبندی thread ها: اشتراک مکانیدر زمانبندی اشتراک مکانی همزمان چند thread وابسته به یک پروسس روی یک مجموعه پردازنده CPU زمانبندی می شوند.

اسلاید 22: زمانبندی thread ها: اشتراک مکانیمشکل زمانبندی اشتراک مکانی ارتباط بین thread ها است.در شکل فوق thread های A0 و A1 در دو فاز متفاوت زمانبندی شده و زمان ارتباط بین آنها معادل با دو برش زمانی یا 200ms است.

اسلاید 23: زمانبندی thread ها: Gangزمانبندی Gangگروه بندی thread های وابسته در یک واحد(Gang)تمامی اعضای یک گروه Gang باید همزمان روی پرازنده های مختلف CPU به صورت اشتراک زمانی زمان بندی شوند.تمامی اعضای یک Gang باید در برش های زمانی یکسان همزمان با هم شروع به اجرا شوند و هم زمان با هم اجرای آنها خاتمه یابد.

اسلاید 24: زمانبندی thread ها: Gangزمانبندی Gang برای یک مجموعه thread روی یک سیستم چندپردازنده ای با شش پردازنده به صورت غیر انحصاری با برش های زمانی واحد.

اسلاید 25: زمانبندی پروسس های وابسته: نمودار زمانبندی

اسلاید 26: زمانبندی پروسس های وابسته:بدون هزینه ارتباطیوابستگی پروسس ها(وظایف) را گراف وظایف مشخص می کند.گراف وظیفه شامل n پروسس (وظیفه) می باشد.سیستم چندپردازنده ای شامل m پردازنده است.هزینه ارتباطی بین پردازنده ها صفر استهدف زمانبندی کاهش زمان کل اجرایی پروسس ها است.

اسلاید 27: زمانبندی پروسس های وابسته Scheduling In-Forests/Out-Forests Task Graphsالگوریتم:سطوح گره های گراف از بالا به پایین محاسبه شده و به عنوان اولویت زمانبدی گره ها در نظر گرفته می شود.موقعی که پردازنده ای در دسترس باشد آن به گره (پروسس) آماده با بالاترین اولویت اختصاص می یابد.

اسلاید 28: زمانبندی پروسس های وابسته Scheduling In-Forests/Out-Forests Task Graphsمثالمثال: زمانبندی گراف وظیفه روی چهار پردازنده

اسلاید 29: زمانبندی پروسس های وابسته Scheduling Interval Ordered Tasksالگوریتم:مقدار تمامی successor های هر گره گراف به عنوان اولویت زمانبدی گره ها در نظر گرفته می شود. گره های وابسته به هر گره در گراف را successor های آن گره تعریف می کنند.موقعی که پردازنده ای در دسترس باشد، آن به گره (پروسس) آماده با بالاترین اولویت اختصاص می یابد.

اسلاید 30: زمانبندی پروسس های وابسته Scheduling Interval Ordered Tasksمثال: زمانبندی گراف وظیفه روی سه پردازنده

اسلاید 31: زمانبندی پروسس های وابسته:با هزینه ارتباطیگراف وظیفه شامل n پروسس (وظیفه) می باشد.سیستم چندپردازنده ای شامل m پردازنده است.هزینه ارتباطی بین وظیفه ها که روی دو پردازنده مختلف زمانبندی می شوند غیر صفر است و مقدار آن روی یال های گراف مشخص می شود.هزینه ارتباطی بین وظیفه ها که روی یک پردازنده یکسان زمانبندی می شوند، صفر است و در زمانبندی باید به این نکته دقت شود.هدف زمانبندی کاهش زمان کل اجرایی پروسس ها است.

اسلاید 32: زمانبندی پروسس های وابسته:با هزینه ارتباطیزمانبندی روی یک پردازنده با الگوریتم های زمانبندی HLFET و MCP

اسلاید 33: زمانبندی پروسس های وابسته:با هزینه ارتباطیزمانبندی روی دو پردازنده با الگوریتم زمانبندی DSC

اسلاید 34: زمانبندی پروسس های وابسته:با هزینه ارتباطیزمانبندی روی دو پردازنده با الگوریتم زمانبندی MD

اسلاید 35: زمانبندی پروسس های وابسته:با هزینه ارتباطیمثال: زمانبندی گراف وظیفه با الگوریتم های MCP، ِDCP، DSC و Genetic

اسلاید 36: زمانبندی پروسس های وابسته:با هزینه ارتباطی

اسلاید 37: زمانبندی پروسس های وابسته:با هزینه ارتباطیمثال: زمانبندی گراف وظیفه با الگوریتم های MCP، HLFET، DSC و MD

اسلاید 38: ارزیابی کارایی سیستم چندپردازنده ای p : تعداد پردازنده ها W(p): کار انجام شده توسط p پردازنده T(p): زمان اجرایی با p پردازندهT(1) = W(1); T(p)  W(p)داریم: S(p)Speedup = T(1) / T(p) E(p)Efficiency = T(1) / [p T(p)] R(p)Redundancy = W(p) / W(1) U(p)Utilization = W(p) / [p T(p)] Q(p)Quality = T3(1) / [p T2(p) W(p)]

اسلاید 39: ارزیابی کارایی سیستم چندپردازنده ایمثال: گراف وظیفه ی شکل زیر را در نظر بگیرید. اگر هزینه ارتباطی گره ها صفر باشد و زمان اجرایی پروسس ها یکسان باشد:الف) پارامترهای T(1) ، T(p) و W(p) رابدست آورید.ب) پارامترهای کارایی S(p) ، E(p)، U(p)، R(p) و Q(p) را بدست آورید.W(1) = 13T(1) = 13T() = 8

اسلاید 40: ارزیابی کارایی سیستم چندپردازنده ایمثال: جمع 16 عدد روی یک سیستم 8 پردازنده ای با هزینه ارتباطی و بدون هزینه ارتباطیZero-time communicationE(8) = 15 / (8  4) = 47% S(8) = 15 / 4 = 3.75R(8) = 15 / 15 = 1Q(8) = 1.76Unit-time communicationE(8) = 15 / (8  7) = 27% S(8) = 15 / 7 = 2.14R(8) = 22 / 15 = 1.47Q(8) = 0.39

اسلاید 41: ارزیابی کارایی سیستم چندپردازنده ای(آرایه خطی مرتب سازی)Fig. 2.10 Odd-even transposition sort on a linear array.T(1) = W(1) = p log2 pT(p) = pW(p)  p2/2S(p) = log2 p (Minsky’s conjecture?)R(p) = p/(2 log2 p)