تمرین های موازی

From Leighton:

1.3

1.11

1.26

1.32

1.34

1.51

1.60

1.65

1.84

1.85

1.112

1.117

1.118

1.119

1.127

1.142

1.161

1.160

1.154

1.152

کتاب پردازش موازی (جدید)

http://www-users.cs.umn.edu/~karypis/parbook

تحلیل مرتب سازی موازی با رابطه بازگشتی

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-895-theory-of-parallel-systems-sma-5509-fall-2003/lecture-notes/lecture2.pdf

خود درس هم اسلایدها و توضیحات جالبی داشت.

جواب سوال سمیه!

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

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

x 0 0 ... 0

0 1 1 ... 1

0 0 0 ... 0

...

1 0 0 ... 0

همه ی اعداد به جز عدد اولی با هم مساویند. حالا گفته است که بیت آخر جواب آرایه مرتب شده اگر x=0 باشد 1 است و اگر x=1 باشد 0 است. یعنی باید مقدار پردازنده 1و1 به پردازنده ی k,N برسد. که این یعنی قطر شبکه را طی کند.

http://mycourse.blog.ir/1392/12/05/%D8%AD%D8%AF-%D9%BE%D8%A7%DB%8C%DB%8C%D9%86-%D8%A8%D8%B1%D8%A7%DB%8C-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D9%87%D8%A7%DB%8C-%D9%85%D9%88%D8%A7%D8%B2%DB%8C

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

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

انتشار (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 را پیدا می کند و با استفاده از قضیه قبل مدار زیر به دست می آید.

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

محاسبه وارون ماتریس

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

روش حذفی گاوس

می توان با استفاده از نیمه ی بالایی یک مش مساله را حل کرد. دلیل درستی آن این است که ما برای محاسبه ی xi می خواهیم یک سطر مقدار i-امین عنصر آن ناصفر باشد و مقدار بقیه عناصر آن صفر باشد. به دلیل اینکه به محض اینکه سطر مورد نظر را پیدا کردیم xi را حساب می کنیم، ترتیب عناصر به هم نمی خورد. همچنین برای سطرهای قبلی هم مشکلی پیش نمی آید، چون درایه ی iام آنها خود به خود صفر بوده است و نیازی به اینکه ما آن را صفر کنیم نیست.

وبلاگ سمیه!

درس های موازی و تقریبی را دارد!

mycourse.blog.ir