مرتب سازی n عدد با کمتر از n پردازنده
نکته ای که الان به ذهنم رسید اینه که همیشه دقت کنیم که اگر پردازنده پیچیده تر باشد و اعمال پیچیده تری را پشتیبانی کند به طور معمول کلاک بزرگتری دارد. ( زمان بین دو کلاک متوالی بیشتر است.)
در این روش شبیه سازی به سادگی هر پردازنده درشت دانه در G2 ، هر یک 4 پردازنده در G1 را شبیه سازی می کند.
به طور کلی اگر با P1 پردازنده بخواهیم P2 پردازنده را شبیه سازی کنیم که P1 < P2 هر پردازنده در G2 می بایست عمل متناظر با P1 / P2 سقف را شبیه سازی کند. که در اینجا انتظار کاهش سرعت با همین نسبت را هم داریم زیرا هر گام در G1 تبدیل به P1 / P2 سقف گام در G2 می شود.
به عنوان مثال الگوریتم مرتب سازی آرایه خطی که قبلاً توضیح دادم با P پردازنده با در نظر گرفتن اینکه هر گام در آرایه خطی با N پردازنده تبدیل به N / P گام در آرایه جدید می شود. از مرتبه O ( N * N /P) خواهد بود.
با توجه به نکاتی که ذکر شد از اینجا به بعد به سادگی فرض می کنیم که اندازه شبکه از اندازه ورودی است. زیرا با استفاده از روش بالا به سادگی می توان با دانستن سایز شبکه الگوریتم را در شبکه هایی با اندازه کوچکتر از اندازه ورودی نیز اجرا کرد.
با درک این نکته متوجه می شویم که الگوریتم های کارا در روش موازی را می توان به الگوریتم هایی با همان کارایی در روش ترتیبی تبدیل کرد. ( P = 1(
- ۹۲/۱۲/۰۵