یک مثال از کتاب پرهامی

مسئله تهیه لیستی از اعداد اول در فاصله تعریف شده برای عدد داده شده N>0 می باشد. 

[1..N]

یک الگوریتم ساده برای انجام اینکار استفاده از روش غربال   Eratosthenes می باشد. بدین صورت که با لیستی از اعداد به صورت 1,2,3,..,N  که به صورت یک بردار که با 00..1000 مقدار دهی شده است نمایش می دهیم. در هر گام  عدد بعدی m که علامتدار نشده است (عددی که بیت مربوطه اش در بردار برابر 0 است. ) اول است. با پیدا کردن این عدد، شروع به حذف مضارب این عدد که با m² شروع می شود، می کنیم. زمانی که m²>n شود محاسبات تمام می شود و تمام اعدادی که با 0 علامتگذاری شده اند اول هستند. 

شکل زیر گام های محاسبات را برای N=30 نشان می دهد. 

در شکل بالا پیاده سازی این الگوریتم در تک پردازنده دیده می شود. متغیر عدد اول جاری با عدد 2 مقدار دهی اولیه می شود و در گام های بعدی آخرین عدد اولی که تا به حال پیدا شده است را در این متغیر نگه داری می کنیم. برای هر عدد اولی که پیدا می کنیم متغیر index  با مقدار مربع این عدد مقدار دهی می شود. و سپس با مقدار عدد اول جاری افزایش می یابد تا تمام ضرایب این عدد را علامتگذاری کند. 

شکل زیر اولین راه حل ما برای اجرای موازی این الگوریتم با P پردازنده را نشان می دهد. لیست اعداد و عدد اول جاری (the current prime) را در یک حافظه اشتراکی ذخیره می کنیم. که برای همه پردازنده ها قابل دسترسی است. 

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

در نتیجه این تقسیم کار به صورت خودکار انجام می شود. در شکل زیر فعالیت های یک پردازنده را در این روش شرح می دهد. برای n=1000 , p>=1  , p<= 3 

دقت کنید که در این روش حل موازی افزایش پردازنده ها بیشتر از 3 زمان محاسبات را کاهش نخواهد داد. زیرا کار پردازنده اول 500 استپ زمان نیاز خواهد داشت. 

تلاش بعدی ما با تقسیم داده کار می کند بدین صورت که بردار بیتی که نماینده n عدد صحیح هستند به p تا قطعه مساوی تقسیم می کنیم. که هر قطعه در یک حافظه خصوصی یک پردازنده ذخیره می شود. فرض می کنیم که P<= sqrt(n  به طوریکه هر عدد اولی که در لیست باقی خواهد ماند در قطعه مربوط به پردازنده اول نیز ضرایبی خواهد داشت. پردازنده اول نقش هماهنگ کننده خواهد داشت: این پردازنده مسئول پیدا کردن عدد اول بعدی و برودکست آن به پردازنده های دیگر است. و آن ها سپس شروع به علامت زدن ضرایب در زیر لیست خودشان هستند. کل زمان مربوط به این الگوریتم به دو بخش تقسیم می شود: زمان برودکست اعداد اول به پردازنده ها و زمان صرف شده توسط پردازنده های برای علامتگذاری اعداد درون لیست. 

اشتباه در عکس 35-1 کتاب لایتون

فکر می کنم در این عکس باید ترتیب X_i ها برعکس باشه تا نتیجه ضرب در پردازنده ها ظاهر بشه.

Prefix Computation

مسئله محاسبه نقلی با رشته های s, p , g  به طور خلاصه تر می تواند با Prefix Computation بیان شود. به صورت دقیق تر X_i نشاندهنده مقدار s,p,g برای iامین بیت از سمت راست جمع است. 

ضمن این باید چک کنیم که عملگر باینری در این محاسبات می بایستی شرکت پذیر باشد. 

کافیست جدول بالا را چک کنیم. هر مسئله ای که بتوان عملگر دودویی به طریقی که در اینجا تعریف شد برایش تعریف کنیم را می توان با همین روش و با یک درخت باینری کامل در 2D + 1 گام حل کرد. که D عمق درخت باینری است.

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

بخش 1-2-1 جمع صحیح با الگوریتم پیش بینی نقلی

این الگوریتم جمع دو عدد N-bit  در1 + lg N * 2 گام با درخت N برگی کامل. و افزایش سرعت زیاد نسبت به روش ترتیبی با N گام. 

به سادگی با یک پردازنده می توان دو عدد N بیتی را در N+1 جمع کرد.

در نگاه اول به نظر میاد که نمیشه اینکار رو سریع تر از N گام انجام داد. اما با کمی هوشمندی و درخت دودویی کامل می توان اینکار را سریع تر انجام داد. با روش پیش بینی نقلی می توان با 1 + lg N * 2  میتوان دو عدد N بیتی  را جمع زد.

نکته کلیدی در این روش در این است که نتیجه جمع دو بیت آیا نقلی را stop ، generate، یا propagate می کند. برای مثال جفت {0 , 0} بیت نقلی را STOP  می کند. { 0 , 1 } بیت نقلی را propagate و { 1 , 1 } بیت نقلی را generate  می کند. 

در این روش نقلی ورودی از بیت i ام برابر است با سمت چپ ترین غیر p بیت های سمت راست. 

در این ساختار محاسبه آخرین carry  گام های مورد نیاز برابر 1 + lg N * 2 خواهد بود. در این روش در هر گام مقدار نود داخلی برابر سمت چپ ترین غیر P خواهد بود. 

هر نود داخلی علاوه بر اینکه ورودی های خودش را از پسرانش دریافت می کند. مقدار فرزند سمت راست را به جای مقدار سمت چپ قرار داده و مقدار سمت راست را حذف می کند. و همینطور این پروسه ادامه پیدا می کند تا به یک برگ برسیم. و هر پردازنده برگ منتظر اولین ورودی non-p خود میماند. 

حل مسائل 1-1

برای نمایش مطلب باید رمز عبور را وارد کنید

الگوریتم مرتب سازی شمارشی:

الگوریتم مرتب سازی شمارشی:

مسئله مرتب سازی N-K bit عدد باینری را روی درخت باینری کامل در نظر بگیرید. فرض کنید هر یک از برگ ها شامل یک آرایه خطی K cellی از پردازنده های بیتی است. و ریشه شامل log N cell آرایه خطی از پردازنده های بیتی است و هر یک از پردازنده های داخلی درخت نیز یک پردازنده بیتی ساده هستند.همچنین هر یک از برگ ها در آغاز با یکی از اعداد باینری بارگذاری شده اند. و مرتب سازی زمانی کامل می شود که iامین عدد در iامین برگ قرار بگیرد. 

برای مثال شکل زیر محتویات پردازنده های برگ را برای مرتب سازی اعداد 7و 5 و 1و 4 نشان می دهد. قطر شبکه  در این مثال برابر 2logN+2K-2  و پهنای باند ورودی و خروجی برابر NK است زیرا ما فرض کردیم که NK بیت همزمان در پردازنده ها ظاهر می شوند. و عرض دو قسمتی شبکه 1 است اگر logN=1 باشد و در غیر اینصورت برابر 2 است. و به وضوح مشخص است که مهمترین فاکتور محدود کننده در این الگوریتم عرض دو قسمتی است. در بدترین حالت ممکن است نیاز باشد NK بیت بین دو قسمت رد و بدل شود. و این باعث می شود که هر الگوریتم مرتب سازی در این شبکه در بدترین حالت Big omega(NK) باشد. قعلاً این را بدون اثبات می پذیریم که اگر Kبرای بعضی ebsilonهای مشخص بزرگتر از مقدار زیر باشد این بحث صحیح است. 

(1+ebsilon) * log N

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

سلام

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

همانطور که بعدها خواهیم دید روش سوم در پست قبلی که با 3N+K-4 گام مرتب سازی N عدد را انجام می داد نه از لحاظ سرعت و نه از نظر کارایی بهینه نیست. روش دیگری وجود دارد که با تعداد کمتر پردازنده مرتب سازی را در زمان کمتری انجام می دهد. اما شبکه مورد استفاده برای این الگوریتم بسیار پیچیده تر از شبکه مورد استفاده در روش های قبلی است. 

اگر خودمان را به شبکه K*N که قبلاً شرح دادیم محدود کنیم روش سوم در پست قبلی بهینه است. دلیل این موضوع این است که هر الگوریتم روی شبکه K*N از مرتبه Big Omega(K+N) است. 

مرتب سازی در مدل بیتی

الگوریتمی که در روش مرتب سازی آرایه خطی توضیح داده شد مبتنی بر مدل کلمه ای (word model)  بود. و ما تعداد گام های کلمه ای را میشمردیم. اما در دنیای واقعی روش کلمه ای روش مناسبی نخواهد بود اگر کلمه ها بسیار بزرگ باشند و یا اگر ما بخواهیم تعداد ترانزیستورها و گیت های مورد نیاز برای ساخت شبکه را بدانیم. در نتیجه روش بیتی روش دقیق تر و واقعی است و استفاده گسترده تری دارد.

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

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

مرتب سازی با آرایه خطی که پیشتر توضیح دادم، از N پردازنده برای مرتب سازی N  عدد استفاده می کرد. 

اگر از P پردازنده برای مرتب سازی N عدد استفاده کنیم که P<N چه باید بکنیم؟

جواب های بسیاری برای این سؤال وجود دارد. برای مثال اگر در اینجا حافظه پردازنده ها از O(1) باشد نمی توانیم N عدد را مرتب کنیم با این شرط که P = o( N) زیرا به هر حال برای مرتب سازی می بایست بتتوانیم N عدد قبل از خروجی را بفرستیم، ذخیره و مقایسه کنیم. حتی کوچکترین عدد. در نتیجه هر پردازنده در این مدل بایستی N/P از اعداد را ذخیره کند.

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

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

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

یک آرایه خطی مثال ساده ای از fixed-connection network است. هر پردازنده در این آرایه pc  و بافر مخصوصی دارد. پیچیدگی PC و میزان حافظه ممکن است متفاوت باشد. اما برای سادگی ما PC  را ساده و حافظه را کوچک فرض می کنیم.