نزدیک‌ترین همسایه تقریبی موازی

مرجع: کتاب هندسه محاسباتی موازی Akl S.G., Lyons K.

البته کتاب قدیمی است و نتایج هم احتمالاً قدیمی اند!

مرجع جدید موازی

http://laurel.datsi.fi.upm.es/_media/proyectos/gopac/programming_massively_parallel_processors.pdf

David B. Kirk and Wen-mei W. Hwu, Programming Massively Parallel Processors, A Hands-on Approach, Morgan Kaufmann, 2010 (supplementary for multicore programming in CUDA)

اصلاحیه تمرین موازی ۱

حل سوال ۱.۱۶۱ قسمت دوم: مربع‌های کوچک رادیکال n بر لگاریتم n هستند.

1.152. بدترین حالت این است که کل آن به صورت یک آرایه خطی مرتب شود که در حالت یکی در میان ۰ و ۱ بودن بیت‌ها رخ می‌دهد.

۱.۱۵۴. n گام برای حالت زیر:

000001

000001

000001

000001

جواب تمرین پردازش موازی

۳- از رابطه speed up استفاده کنید.

۱۱- bfs را اجرا کنید.

۲۶- هر سطر را جمع کنید و همزمان با یک واحد carry هم این کار را انجام دهید تا به مقدار s, p,g هر سطر برسید. کران پایین با قطر به دست می‌آید چون تغییر هر بیت در زمان موثر است.

۳۲- از تابع ماکسیمم به همراه پیشوند موازی استفاده کنید و جواب را با مقدار هر گره مقایسه کنید.

۳۴- مقدار zi, zi-1 را بر حسب z1,z0 به صورت ضرب ماتریسی بنویسید و پیشوند موازی را اجرا کنید.

۵۱- ماتریس توان‌های w را به دست بیاورید: سطر اول را با ضرب w در مقدار پردازنده قبلی به دست ‌آورید. سطر‌های بعد را با همین روش از روی سطر قبلی و سطر اول به دست آورید.

۶۰- تصویر آن قبلا در وبلاگ قرار داده شده است.

۶۵- مانند حالت آرایه خطی کار پردازنده‌های قبلی به صورت سریال انجام می‌شود. (slow down)

۸۴- برای انتشار بردار x از پیشوند موازی استفاده کنید.

۸۵- همان روش معمولی حذفی گاوس قابل قبول است. حالت یک سطر تمام صفر بینهایت جواب و حالت یک سطر به جز b صفر حالت بدون جواب است.

۱۱۲- الف) سقف ۱۱/۴=۳ باید در آن ضرب شود. ب) نیاز به ضرب هیچ مقداری نیست.

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

۱۱۷- مدار گفته شده را بدون تاخیرهای ورودی (نقطه‌ها) می‌کشیم و گراف حاصل را با retiming به systolic تبدیل می‌کنیم که به همان جواب قبلی باید برسد. برای قسمت دوم سوال تاخیر یکی بیشتر می‌شود.

۱۱۸- زمان broadcast از گره آخر به اول صفر است (در palindrome) و با این کار می‌توانیم تشخیص بدهیم که نوبت فرد است یا زوج و بر اساس آن یا یک مقدار را برای بقیه بفرستیم یا ورودی را شیفت بدهیم.

۱۱۹- همان الگوریتم مرتب سازی اول کتاب (مینیمم گیری و فرستادن به راست) را انجام می‌دهیم.

۱۲۷- در سطر بالا اندیس بزرگتر را به راست می‌فرستیم و در پایین اندیس بزرگتر را نگه می‌داریم و بقیه را به چپ می‌فرستیم. (بالا = a_i و پایین = b_i). سپس اعداد هر پردازنده را ضرب می‌کنیم و حاصل جمع را با کمک یالهای وزن صفر در زمان ۰ به دست می‌آوریم.

۱۴۲- بستار گراف را حساب می‌کنیم و اعداد زیر قطر را به بالای قطر می‌فرستیم و با مقدار قبلی and می‌کنیم و بقیه مثل مولفه همبندی گراف معمولی است.

۱۵۲- هر بار یک مربع در گوشه سمت چپ بالا مرتب شده است پس در مرحله n-ام کل اعداد مرتب شده‌اند.

۱۵۴- هر بار حداقل i عنصر مرتب می‌شوند پس حداکثر با دو بار اجرا همه مرتب می‌شوند (یکی از اول به آخر و یکی از آخر به اول). همان زمان قبلی.

۱۶۰- تعداد سطرهای کثیف نصف می‌شود پس زمان مرتب سازی هر بار نصف می‌شود و جمع آنها را حساب می‌کنیم. (حل در کتاب پرهامی و در وبلاگ آمده است.)

۱۶۱- با یک مستطیل به عرض داده شده و تعداد n پردازنده می‌توان این کار را انجام داد. برای تبدیل آن به مربع باید بلوک‌های متوالی آن را کنار هم بچینیم تا موازی مرتب کنند.

ادامه حل سوالهای موازی

سوال ۱.۱۶۱: در تحلیل سوال ۱.۱۶۰ مقدار r=sqrt(n log n) و p=n است. فقط باید مستطیل را روی مربع اجرا کنیم.

ضرب ماتریس روی شش وجهی (موازی)

جواب سوال ۱.۱۶۰ (تمرین موازی)

چون مطمئنم نمیشه این سوال رو حل کرد حلش رو میذارم!

اصلاحیه پست تمرین‌های سری اول پردازش موازی

این شکل جا مانده بود!

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

سوالهایی که از سر کلاس باقی موند: (قسمت حل نشده و راه‌حل دوم سوالها)

۱- سوال ۱.۲۳: کم کردن دو عدد در مبنای ۱ (بدون مکمل ۲)

Subtraction is similar, except that borrows, rather than carries, are propagated to the left. If the borrow extends past the end of the word it is said to have "wrapped around", a condition called an "end-around borrow". When this occurs, the bit must be subtracted from the right-most bit. This phenomenon does not occur in two's complement arithmetic.

  0000 0110      6
− 0001 0011     19
===========   ====
1 1111 0011    −12    —An end-around borrow is produced, and the sign bit of the intermediate result is 1.
− 0000 0001      1    —Subtract the end-around borrow from the result.
===========   ====
  1111 0010    −13    —The correct result (6 − 19 = -13)

منبع:

http://en.wikipedia.org/wiki/Ones'_complement

۲- تمرین ۱.۲۸ کتاب (هنوز جزو مسائل حل نشده است و من به عنوان اشکال پرسیدم!)

۳- در سوال ۱.۵۳ کتاب در مورد ارسال اطلاعات به دو طرف چه می‌توانیم بگوییم؟ (انگار ثابت شد که صورت سوال غلط است اگر ارسال اطلاعات پردازنده‌های مجاور را در نظر بگیریم.)

۴- ۱.۶۶: تعریف slow down (صفحه ۱۱ کتاب Leighton)

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

۵- ۱.۶۸ : یک ماتریس b-قطری پایین مثلثی داریم وارون آن را با یک آرایه پردازنده b*b به دست آورید.

صورت سوالهای تمرین موازی

تمرین ها دو تصویر هستند. :) برای اینکه نیاز به گشتن در کتاب نباشد همه را یکجا گذاشتم.

شکلها و سوالاتی که در تمرین ها به آنها ارجاع داده شده است: