حل 2_15 وزیرانی

البته اصل حل مربوط به یک سوال دیگر در کتاب WS بود اما فکر کنم این سوال هم همین طوری حل می شود. (حداقل می دانم سوالهایی که حل آنها در این دو کتاب نیامده در امتحان هم نمی آید!)

تمرین های فصل 2 WS (زمانبندی کارها) 2.1,2.3

2- فرض مساله را به صورت زیر می نویسیم

OPT/3 < w_1 <= w_2 <=...<=w_m

الگوریتم LPT هم کارها را به ترتیب از زمان اجرای زیاد به کم انجام می دهد. می خواهیم ثابت کنیم این کار به جواب بهینه می رسد.

از فرض داده شده می فهمیم به هر پردازنده حداکثر 2 کار می رسد. جواب بهینه جوابی است که زوج کارهایی که به یک پردازنده داده می شوند، جمعشان مینیمم شود. اگر تعداد پردازنده ها از نصف کارها بیشتر باشد که کارهای با زمان طولانی تر به تنهایی روی یک پردازنده اجرا می شوند و کارهای با زمان کمتر هر دو تا روی یک پردازنده اجرا می شوند. پردازنده هایی که به آنها دو کار داده شده است، باید طوری باشند که جمع این دو کار مینیمم شود. برای این کار بهترین کار این است که کار با بیشترین زمان و کمترین زمان را با هم به یک پردازنده بدهیم.

3- الگوریتم زمانبندی لیست کارها را به ترتیبی دلخواه در یک لیست می گذارد و کار بالای لیست را به اولین پردازنده ای که بیکار شد می دهد. اثبات آن به اثبات جستجوی محلی ارجاع داده شده بود.

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

حل المسائل وست

کتاب نظریه گراف است ولی من تا همین الآن که اتفاقی حل المسائلش را دیدم نمی دانستم حل المسائل دارد.

دریافت
حجم: 3.35 مگابایت

استفاده از تجانس برای پیدا کردن نزدیک ترین همسایه در ابعاد بالا

http://aidblab.cse.iitm.ac.in/cs625/6.FastMap.pdf

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

مقاله پردازش موازی

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

یادآوری

به من یادآوری کنید که به استادم یادآوری کنم که به بچه ها یادآوری کنند که سر ارائه ی من بیایند.

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

min-wise independent hashing

http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/BroderCFM-minwise.pdf

مرجع هندسه محاسباتی پیشرفته

خودم این را پیدا کرده بودم اما نمی دانم چرا قبلا نگذاشته بودمش.

دریافت
حجم: 409 کیلوبایت

انتشار (broadcast) - موازی

در پست قبل گفتیم که:

راهنمایی حل سوال:

فرض کنید می خواهیم از host داده ای را برای همه ی پردازنده ها broadcast کنیم. با یک bfs از host روی گراف (فعلا یالهای را بدون جهت در نظر می گیریم) می زنیم و یال با وزن 0 اضافه می کنیم. از آنجایی که گراف اولیه systolic بوده است و درخت (bfs) دور ندارد، پس دور با وزن 0 نداریم و گراف جدید semi-systolic است و با روش گفته شده می توانیم آن را systolic کنیم.

ثابت می کنیم که با 2 برابر کردن وزن یالها حتما می توانیم این گراف را systolic کنیم. برای این کار کافی است نشان دهیم که حداکثر نصف یالهای هر دور وزن 0 دارند. = حداکثر نصف یالهای هر دور از درخت bfs آمده اند. هر یال bfs عمق را یکی زیاد می کند و هر یال غیر bfs عمق را حداکثر یکی کم می کند. چون یک دور است باید از همان راسی که شروع کرده به همان برگردد پس تعداد یالهای bfs از غیر bfs کمتر مساوی است.

(تا آخر 1.4.5)

تبدیل مدار semi-systolic به systolic

اگر مداری چیزی را همزمان برای همه ی پردازنده ها بفرستد یا همزمان مقدار تعدادی پردازنده را جمع کند و ... . (خلاصه همزمان یک سری کار روی همه انجام بدهد) دیگر مدار ما systolic نیست. اگر بتوان چنین مداری را به systolic تبدیل کرد به این مدار semi-systolic می گویند و در ادامه شرایط آن و نحوه ی تبدیل آن را نشان می دهیم.

مدار بالا در مدل میلی است (یعنی مقدار خروجی علاوه بر رجیسترها از مدار هم می آید. (خط چین ها از مدار می آیند.)

گراف متناظر آن به صورت زیر است: (همان طور که زیر شکل نوشته شده تعداد بافرها را وزن یالها می گیریم و پردازنده ها راسها هستند.)

اگر گرافی که به دست می آید دور صفر نداشته باشد (دوری که همه ی یالهای آن وزن صفر داشته باشند) می توانیم آن را به systolic تبدیل کنیم.

مرحله اول: همه ی بافرها را چند برابر کنیم، با این کار عملکرد مدار تغییر نمی کند و فقط تاخیر ایجاد می شود. در گراف همه ی یالها در یک عدد ضرب می شوند. عددی را برای این کار انتخاب می کنیم که همه ی دورها وزنشان از تعداد یالهایشان بیشتر یا مساوی باشد؛ که بعدا بتوانیم با ایجاد تاخیر در گره ها یالهای با وزن صفر را از بین ببریم. (چون کلا مشکل ما این است که یک سری کار همزمان با هم دارند انجام می شوند.)

مرحله دوم: با عمل lagging در گره ها تاخیر ایجاد کنیم. (شکل زیر)

می خواهیم ثابت کنیم که هر مداری که این شرط (نبود دور صفر) را داشته باشد (semi-systolic باشد)، می توانیم با یک دنباله از عملیات قبل به یک مدار systolic تبدیل کنیم.

اثبات: اینکه با انجام عملیات lagging شرط semi-systolic بودن به هم نمی خورد تقریبا بدیهی است. می خواهیم ثابت کنیم که حتما با دنباله ای از عملیات lagging می توانیم از S به S' برسیم.

استقرا: پایه استقرا همان حالت اولیه است که با 0 عمل lagging به یک مدار semi-systolic می رسیم (خود S!)

فرض استقرا: برای تعداد توابع lagging کمتر از L مدار semi-systolic بماند.

حکم استقرا: برای L تابع lag مدار semi-systolic است.

اگر گره ای باشد که lag آن مثبت باشد و درجه ی همه ی یالهای خروجی آن ناصفر باشد می توان روی آن یک عمل lag انجام داد. با این کار یکی از تعداد عملیات lag لازم کم می شود و L-1 عمل lag طبق فرض استقرا مدار را semi-systolic می کند.

اگر چنین گره ای نباشد، یعنی همه ی راسهای با lag مثبت یال خروجی صفر دارند. می دانیم با طی هر یال با وزن صفر از یک راس با lag مثبت به راس دیگری با lag مثبت می رسیم، چون اگر یک سر آن وزن یال را کم می کند دیگری باید آن را اضافه کند وگرنه به یال با وزن منفی می رسیم. پس اگر یک راس مثبت یال صفر داشته باشد آن یال به یک راس مثبت دیگر می رود، با دنبال کردن یالهای به وزن صفر خروجی راسهای با lag مثبت یک دور به وجود می آید که وزن آن صفر است که با فرض semi-systolic بودن S (نه S') در تناقض است. (چون ثابت کردیم وزن دورهای S' و S برابرند.)

برای lag منفی هم مشابه همین استدلال را می توانیم انجام بدهیم.

(پایان اثبات)

باید مقادیر رجیسترهایی که جا به جا می کنیم را هم اصلاح کنیم.

حالا می خواهیم تابع lag را به دست بیاوریم.

اثبات:

تابع بالایعنی کوتاهترین مسیر از هر گره تا host در گراف G-1 تابع lag مورد نظر است. ثابت می کنیم این تابع مدار را systolic می کند.

مثال: برای سوال palindrome که در ابتدای متن گفته شد، باید وزن یالهای گراف را در 2 ضرب کنیم شرایط semi-systolic را پیدا می کند و با استفاده از قضیه قبل مدار زیر به دست می آید.

راهنمایی حل سوالات آخر فصل با این روش!