My Course

یادگیری های من در شریف!

My Course

یادگیری های من در شریف!

یادگیری های من در دوران تحصیل در رشته کامپیوتر در دانشگاه شریف.

مرتب سازی n عدد با کمتر از n پردازنده

دوشنبه, ۵ اسفند ۱۳۹۲، ۰۵:۲۳ ب.ظ

نکته ای که الان به ذهنم رسید اینه که همیشه دقت کنیم که اگر پردازنده پیچیده تر باشد و اعمال پیچیده تری را پشتیبانی کند به طور معمول کلاک بزرگتری دارد. ( زمان بین دو کلاک متوالی بیشتر است.)

در این روش شبیه سازی به سادگی هر پردازنده درشت دانه در G2 ، هر یک 4 پردازنده در G1 را شبیه سازی می کند. 

به طور کلی اگر با P1 پردازنده بخواهیم P2 پردازنده را شبیه سازی کنیم که P1 < P2  هر پردازنده در G2  می بایست عمل متناظر با  P/ P2  سقف را شبیه سازی کند. که در اینجا انتظار کاهش سرعت با همین نسبت را هم داریم زیرا هر گام در G1  تبدیل به   P/ P2  سقف  گام در G می شود. 

به عنوان مثال الگوریتم مرتب سازی آرایه خطی که قبلاً توضیح دادم با P  پردازنده با در نظر گرفتن اینکه هر گام در آرایه خطی با N پردازنده تبدیل به N / P گام در آرایه جدید می شود.  از مرتبه O ( N * N /P) خواهد بود.

با توجه به نکاتی که ذکر شد از اینجا به بعد به سادگی فرض می کنیم که اندازه شبکه از اندازه ورودی است. زیرا با استفاده از روش بالا به سادگی می توان با دانستن سایز شبکه الگوریتم را در شبکه هایی با اندازه کوچکتر از اندازه ورودی  نیز اجرا کرد.

با درک این نکته متوجه می شویم که الگوریتم های کارا در روش موازی را می توان به الگوریتم هایی با همان کارایی در روش ترتیبی تبدیل کرد. ( P = 1(

  • سمیه زارعی مرادی

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی