cutting lemma

Lazy caterer's sequence

http://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence

Geometric Combinatorics (MIT)

http://ocw.mit.edu/courses/mathematics/18-319-geometric-combinatorics-fall-2005/

چندریسه‌ای+مرتب سازی روی پروانه

من یک جمله توی دفترم دارم که هر ریسه‌ای می‌تواند ۲ تا ریسه‌ی دیگر بسازد که به نظرم غلطه. الآن که با کتاب چک کردم درسته که هر دو مثالی که زده برای حالت‌های با ۲ تا نخ بوده ولی هیچ محدودیتی روی تعدادش نگذاشته. در نتیجه من بیخودی این حالت را حساب کردم. :|

مثال فیبوناچی هم طبیعتاً ربطی به این قضایا نداره چون اون خودش رابطه بازگشتی‌اش حل کردنش به صورت موازی O(n) زمان می‌خواهد. (طول مسیر بحرانی)

-------

برای مرتب سازی روی مدل پروانه‌ای هم bitonic sort را نوشتم در حالی که به خاطر اینکه روی پروانه داریم اجرا می‌کنیم ترتیبش یک جور دیگه باید باشه که من سر جلسه هر کاری کردم بهتر از اون نشد. توی کتاب هم گفته به صورت بازگشتی این کار را انجام می‌دهیم و اصلاً معلوم نیست چطوری این کار را کرده. :|

--------

فکر کنم هدف سوال ۲ هم این بود که حلقه موازی بنویسیم نه اینکه مثل من کل مسأله را در زمان log n حل کنیم! :) :|

سوالات پایان ترم پردازش موازی

۱- multithreaded programming

الف) برنامه‌ی ترانهاده‌ی ماتریس و اثبات درستی آن

ب) اگر بعد از هر فراخوانی زیرمسأله یک sync بگذاریم چه می‌شود؟

۲- یک برنامه چندریسه‌ای بنویسید که اعداد را به دو قسمت کمتر مساوی میانگین و بیشتر از میانگین تقسیم کند اما ترتیب اعداد ورودی را به هم نزند.

۳- در برنامه‌ی MST موازی قسمت های زیر را چه کسی برای چی در چه زمانی و ... انجام می‌داد؟

الف) P(i) = P(P(i)

ب) L(i) = L(P(i))

۴- مسیریابی:

الف) مثالی بزنید که 2n/3 بافر نیاز داشته باشد. (قسمت هر پردازنده در صورت سوال غلط بود)

ب) آن را با مرتب سازی حل کنید. زمان؟

ج) آن را با پیش پردازش حل کنید. زمان؟

۵- الگوریتم parallel prefix را برای مدل hypercube بنویسید.

۶- مرتب سازی روی مدل پروانه‌ای/hypercube را بنویسید.

مرتب سازی روی شبکه پروانه‌ای

من به طرز خنده‌داری نوشتم دو تا درخت داریم به جای پروانه! :)

ساختمان داده‌های متحرک

http://www.cs.duke.edu/~pankaj/publications/slides/kinetic-range.pdf

پروپوزال

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

برنامه تابستان دانشجوهای ارشد

Mesh of Trees

ما بهترین مدلی که داریم شبیه PRAM یک گراف دوبخشی کامل است که هر رأس از هر بخش را به هر رأس از بخش دیگر وصل می‌کند. دلیل ادغام پردازنده‌های ریشه در MOT هم همین است که گراف K_(N,N) معادل N پردازنده باشد که هر کدام به N پردازنده‌ی دیگر وصل هستند. دلیل اینکه از درخت به جای گره‌ها استفاده می‌کنیم این است که در غیر این صورت درجه‌ی رأسها به شدت زیاد می‌شود.

پس از اینجا می‌فهمیم که برای طراحی الگوریتم برای MOT باید ابتدا PRAM آن را طراحی کنیم بعد آن را به MOT تبدیل کنیم.