مرتب سازی بر روی آرایه خطی

در هر گام، هر پردازنده:

1. ورودی را از همسایه سمت چپ دریافت می کند.

2. بافرش را بررسی می کند. 

3. محاسباتی را که PC تعیین می کند را انجام می دهد.

4. برای همسایگانش خروجی تولید می کند.

5. بافرش را به روز می کند.

زمان با استفاده از یک کلاک سراسری به گام ها تقسیم می شود. به ط.ریکه تمام آرایه به صورت همگام عمل کنند. به این مدل، Systolic Computation می گویند. دلیل این نام گذاری مشابهت جریان داده در این روش به جریان خون در بدن است. به آرایه مورد استفاده در این روش Systolic Array می گویند.

در این مدل برای مرتب سازی N عدد از یک آرایه N تایی استفاده می کنیم. برنامه تمام پردازنده ها بدون در نظر گرفتن جایگاه آنها در آرایه یکی است و تفاوتی نمی کند. 

الگوریتم در دو فاز انجام می شود. 

فاز 1 شامل گام های زیر است:

1. گرفتن ورودی از همسایه سمت چپ

2. مقایسه ورودی با عدد ذخیره شده

3. فرستادن عدد بزرگتر به عنوان خروجی به همسایه سمت راست.

4. ذخیره کردن عدد کوچکتر در بافر محلی

شکل زیر این فاز را نشان می دهد:

به راحتی می توان نشان داد که بعد از 2N-1 گام عدد iام در مکان iام آرایه ذخیره شده است. برای هر 

1 <= i <= N

بعد از N گام عدد Nام به خانه اول می رسد. اگر این عدد بزرگترین عدد باشد N-1 گام دیگر نیاز است تا این عدد به Nامین خانه آرایه برسد.  بنابراین بعد از 2N-1 گام مطمئن خواهیم بود که اعداد به درستی در خانه ها قرار گرفته اند.

پس از انجام فاز 1 اعداد به صورت مرتب شده در آرایه قرار گرفته اند. حالا می بایست اعداد به صورت مرتب شده به خروجی ارسال شوند. این عمل در فاز 2 انجام می شود.

برای این کار می توانیم از روش های زیر استفاده کنیم:

روش اول: به محض اینکه کلیه اعداد مرتب شدند، کلیه پردازنده ها به مد "بده چپ" سوئیچ کنند. ( محتوای حافظه شان را به پردازنده سمت چپ ارسال کنند)

روش دوم: در این روش لازم است هر پردازنده از جایگاه خودش در آرایه آگاه باشد و تعداد ورودی ها به خود را بشمارد. به محض اینکه این تعداد + شماره این پردازنده برابر شد با N+1 به مود "بده چپ " سوئیچ کند.

روش سوم:  در این روش سمت راست ترین پردازنده پردازنده ویژه ای است. و به محض دریافت داده داده خود را به سمت راست می فرستد. بقیه پردازنده ها نیز به محض دریافت ورودی از پردازنده سمت راست، داده ذخیره شده خود را به همسایه سمت چپ می فرستند.

روش چهارم: هر پردازنده به محض اینکه ورودی از پردازنده سمت چپ دریافت نکند داده ذخیره شده خود را به سمت چپ می فرستد.

اگرچه تمام روش هایی که در بالا ذکر شد خروجی را به صورت مرتب شده از انتهای سمت چپ آرایه به بیرون می فرستد با اینحال تمام این روشها قابل پیاده سازی و کارا نیستند. برای مثال روش 1 قابل پیاده سازی نیست به دلیل اینکه راهی وجود ندارد تا پردازنده های داخلی از پایان فاز 1 مرتب سازی مطلع شوند. زیرا به وسیله کنترل محلی و ارتباطات محلی ما قادر به برودکست دستور "بده چپ " نیستیم. 

البته برای اینکار می تونیم از یک کانتر داخلی استفاده کنیم که از 2N-1 شروع کنه و بعد از 2N-1کلاک دستور "بده چپ رو اجرا کنه. اما این روش مانند روش دوم به سخت افزار اضافی نیاز داره. اما در روش 3 و 4 بدون استفاده از کانتر یا آگاهی هر پردازنده از جایگاهش در آرایه و/یا N (اندازه ورودی) می توانند فاز 2 را انجام بدهند. 

روش سوم به دلیل نیاز به 4N-3 گام ، از نظر زمانی بهینه نیست. اما روش 4 با تنها 3N-1 گام می تواند ورودی را مرتب کند و خروجی مرتب شده را تحویل دهد. 

مهم :روش سوم برای فرستادن خروجی به 2N-1 گام نیاز دارد. در گام اول 5 از پردازنده آخر به راست فرستاده می شود. در گام بعدی 3 از پردازنده 4 به راست فرستاده می شود و 5 در پردازنده 4 ذخیره می شود. به همین ترتیب برای انتقال 5 به پردازنده اول 2N-2  مرحله نیاز است. و یک مرحله برای فرستادن 5 به خروجی که می شود 2N-1 مرحله.

ارزیابی کارایی الگوریتم: 

چندین روش برای ارزیابی کارایی الگوریتم های موازی وجود دارد. واضح ترین روش اندازه گیری زمان T و تعداد پردازنده ها P است. در مرتب سازی با آرایه خطی :

P=N , T= teta(N)

همچنین می توانیم مقایسه ای بین بهترین الگوریتم های ترتیبی و الگوریتم های موازی نیز داشته باشیم. به این منظور فاکتور تسریع را به صورت زیر تعریف می کنیم:

Speedup S of a parallel algorithm = Running Time of the Fastest seq. alg. /  Running Time of the Parallel alg.

In this case:  S = teta(lg N)

در صورتیکه میزان تسریع در الگوریتم موازی به مقدار زیر باشد می گوییم تسریع خطی داریم. البته در بعضی مسائل رسیدن به این میزان تسریع سخت است از جمله مسائل مرتب سازی.

S  = P or even S = teta( p )

یک الگوریتم موازی هیچگاه نمی تواند تسریعی بهتر از تسریع خطی داشته باشد. حداکثر مقدار P، S خواهد بود. 

اندازه گیری مهم دیگر برای الگوریتم های موازی میزان تلاش لازم است که به صورت زیر تعریف می شود:

w = T * P

for this case : W = teta( N² )

روش دیگری هم برای اندازه گیری فاکتور فوق وجود دارد که به صورت زیر تعریف می شود که N_i  ها در آن تعداد پردازنده های فعال در مرحله iام است. 

W = N₁+ N₂+ N₃+....

فاکتور کارایی برای الگوریتم های موازی می تواند به صورت های زیر تعریف شود که معادل هم هستند:

که در فرمول اول تاو همان زمان بهترین الگوریتم ترتیبی است. برای مثال کارایی برای الگوریتم فوق برابر است با :

E = tata( (lg N) /N )

آیا می توان بهترین سرعت با بهترین کارایی را به صورت همزمان داشت؟ خوشبختانه برای بسیاری از مسائل پاسخ این سؤال مثبت است. اگرچه در بعضی مسائل اینطور نیست و ما بسته به شرایط یکی را بر دیگری ترجیح خواهیم داد. 

برای مثال فرض کنید دو الگوریتم برای حل مسئله ای با سایز M داریم. الگوریتم اول در M گام با استفاده از M پردازنده مسئله را حل می کند و الگوریتم دوم با استفاده از M² پردازنده را با ^(1/2)M  گام ، مسئله را حل می کند. اگر ما M² پردازنده داشته باشیم و نیاز باشد تا الگوریتم را X بار اجرا کنیم، بهتر است از کدام الگوریتم استفاده کنیم؟؟؟ اگر ما M² پردازنده را به M پردازنده M تایی تقسیم و از الگوریتم اول استفاده کنیم  زمان مورد نیاز با معادله زیر به دست می آید:

اگر از الگوریتم دوم استفاده کنیم با زمان   X*M^(1/2)    مسئله حل می شود. بنابراین اگر X بزرگتر از رادیکال M باشد بهتر است از الگوریتم 1  و در غیر اینصورت از الگوریتم 2 استفاده کنیم.

می توانیم با کمی تغییر در تعاریف فاکتورهای تسریع و کارایی الگوریتم های موازی را با هر الگوریتم ترتیبی دلخواه مقایسه کنیم. 

بعدتر الگوریتمی معرفی می کنیم که با N پردازنده در زمان lg N مرتب سازی را انجام می دهدو تسریع خطی دارد. البته شبکه پردازنده ها در آن روش بسیار پیچیده تر از آرایه خطی است.