حد پایین برای الگوریتم های موازی

دلیل 1 : پهنای باند کم ورودی و خروجی - اگر آرایه K*N بیتی بدین صورت استفاده شود که تنها از روشی که گفته شد ورودی وارد آرایه و خارج شود، برای هر کدام N گام طول می کشد. البته برای حالتی که هر یک از پروسسورها پورت ورودی و خروجی داشته باشد دیگر این بحث مطرح نیست!

دلیل 2 : بزرگترین قطر- قطر یک شبکه بیشترین فاصله بین هر جفت پروسسورهاست. فاصله بین یک جفت از پروسسورها کمترین تعداد سیم هایی است که برای رسیدن از یکی از آنها به دیگری باید طی شود. برای مثال بیشترین قطر در آرایه K*N برابر است با K+N-2. قطر یک شبکه اغلب حد پایین برای زمان لازم برای انجام یک محاسبه مفید است. این به این دلیل است که نتیجه محاسبات انجام شده توسط یکی از پردازنده ها لازم باشد که توسط دیگری استفاده شود. اگر کمترین فاصله بین اینپنین دو پردازنده d باشد، حداقل d گام لازم است برای تعامل بین این دو پردازنده. در مورد الگوریتم مرتب سازی نتایج محاسبه بالاترین پردازنده سمت چپ تأثیر میذاره روی مقدار ذخیره شده در پایین ترین پردازنده سمت راست. از این رو انتظار داریم که هر الگوریتم مرتب سازی در این شبکه برای انجام فاز 1 حداقل نیاز به N+K-2 گام نیاز داشته باشد.

اینجا یک مثال داره کتاب که سپیده توضیح داده. مرسی!

دلیل 3 : پایین بودن عرض دو قسمتی - عرض دو قسمتی یک شبکه حداقل تعداد سیم هایی است که باید از شبکه حذف شود تا به دو قسمت یکسان ( یا با یک تفاوت) تبدیل شود. برای مثال عرض دو قسمتی در آرایهK*N برابر است با min(K,N) یا min(K,N)+1 بسته به اینکه max(K,N) c زوج باشد یا فرد. در حقیقت min(K,N)+1 یک حد بالا برای عرض دو قسمتی است. به هر حال عرض دوقسمتی اغلب  یک فاکتور حیاتی در تعیین سرعت یک شبکه برای انجام محاسبات است. دلیل این است که در اغلب مسائل داده های ذخیره و/یا محاسبه شده در یکی از نیمه ها توسط نیمه دیگر برای کامل شدن محاسبات مورد استفاده قرار می گیرد. 

به عنوان مثال فرض کنید که در مسئله آرایه K*N ، ما N عدد K بیتی را در پردازنده ها بارگذاری کرده ایم. و می خواهیم با یک الگوریتم مرتب سازی به طوری عدد ها را مرتب کنیم که عدد iام در ستون iام در قرار بگیرد. دور از تصور نیست که N/2 عدد بزرگتر در N/2 ستون اول قزاز داشته باشد. بنابراین K*N/2 بیت بایستی از نیمه اول به نیمه دوم منتقل شود. و چون عرض دو قسمتی آرایه K است بنابراین حدپایین N/2 گام برای هر الگوریتم مرتب سازی در این آرایه خواهیم داشت. 

با توجه به اطلاعاتی که در این پست داده شد می توانیم در صورتی که به یک توپولوژی خاص شبکه محدود باشیم در مورد یک الگوریتم تصمیم بگیریم که آیا بهینه است یا خیر.

:)