حل مسائل 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  را ساده و حافظه را کوچک فرض می کنیم. 

کتاب های مفید برای پیش مطالعه

1. T. Cormen, C. Leiserson,  and R. Rivest. Introduction to Algorithms. MIT Press/McGraw Hill, Cambridge, MA, 1990

2. R. Graham, D. Knuth, and O. Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, Reading, MA,1989.

3. S. Maurer and A. Ralston. Discrete Algorithmic Mathematics. Addison-Wesley, Reading, MA, 1991

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

درس الگوریتم های تقریبی

Instructor : Mohammad Ali Abam

Text Books : 

1- V. Vazirani, Approximation Algorithms, Springer-Verlag, 2001. [V]

2- D. Williamson and D. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011. [WS]

درس پردازش موازی

Instructor : Mohammad Ghodsi

Text Books : 

1- Leighton, F.T., {\sl Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes,} Morgan Kaufmann, 1992. 
2- B. Parhami, {\sl Introduction to Parallel Processing: Algorithms and Architectures,} Plenum Press, 2000.
3- David B. Kirk and Wen-mei W. Hwu, Programming Massively Parallel Processors, A Hands-on Approach, Morgan  aufmann, 2010 (supplementary for multicore programming in CUDA)