یادتون هست وقتی که کتاب‌های صفر و یک مد شده بودند. (یک ربطی به فیزیک داشت و ما می‌خواندیم که بگوییم خوانده‌ایم.)
حالا این پروژه‌ی موازی را دیدم یادم افتاد. :)) به درد نخورتر از این چیزی ندیده‌ام! :) تا جایی که یادم است قرار بود پروژه مفید و کاربردی باشد...
من ایمیل زدم درخواست دادم مهلتش تمدید بشود الآن تا ۵شنبه وقت دارد.
۱- multithreaded programming
الف) برنامه‌ی ترانهاده‌ی ماتریس و اثبات درستی آن
ب) اگر بعد از هر فراخوانی زیرمسأله یک sync بگذاریم چه می‌شود؟
۲- یک برنامه چندریسه‌ای بنویسید که اعداد را به دو قسمت کمتر مساوی میانگین و بیشتر از میانگین تقسیم کند اما ترتیب اعداد ورودی را به هم نزند.
۳- در برنامه‌ی MST موازی قسمت های زیر را چه کسی برای چی در چه زمانی و ... انجام می‌داد؟
الف) P(i) = P(P(i)
ب) L(i) = L(P(i))
۴- مسیریابی:
الف) مثالی بزنید که 2n/3 بافر نیاز داشته باشد. (قسمت هر پردازنده در صورت سوال غلط بود)
ب) آن را با مرتب سازی حل کنید. زمان؟
ج) آن را با پیش پردازش حل کنید. زمان؟
۵- الگوریتم parallel prefix را برای مدل hypercube بنویسید.
۶- مرتب سازی روی مدل پروانه‌ای/hypercube را بنویسید.
من به طرز خنده‌داری نوشتم دو تا درخت داریم به جای پروانه! :)
ما بهترین مدلی که داریم شبیه PRAM یک گراف دوبخشی کامل است که هر رأس از هر بخش را به هر رأس از بخش دیگر وصل می‌کند. دلیل ادغام پردازنده‌های ریشه در MOT هم همین است که گراف K_(N,N) معادل N پردازنده باشد که هر کدام به N پردازنده‌ی دیگر وصل هستند. دلیل اینکه از درخت به جای گره‌ها استفاده می‌کنیم این است که در غیر این صورت درجه‌ی رأسها به شدت زیاد می‌شود.
پس از اینجا می‌فهمیم که برای طراحی الگوریتم برای MOT باید ابتدا PRAM آن را طراحی کنیم بعد آن را به MOT تبدیل کنیم.
در سوال ۱.۵۰ به الگوریتم ۱.۵.۵ ارجاع داده شده است که به صورت زیر است:
الگوریتم closure را با رابطه‌ی زیر اجرا می‌کنیم:
