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

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

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

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

000001

000001

000001

000001

اصلاحیه 5

روی جواب تمرین هندسه اصلاحیه داده شد.

سوال ۸ تمرین الگوریتم تقریبی

سوال ۳.۵ وزیرانی

حل: (سوال آخر)

http://dcg.epfl.ch/files/content/sites/dcg/files/Courses/Combinatorial%20Optimization%202012/ProblemSet11Solutions.pdf

سوال ۷ تمرین الگوریتم تقریبی

این سوال ۳.۶ WS هم هست. جواب:

http://www.diku.dk/OLD/undervisning/2005v/404/approx_path.pdf

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

۳- از رابطه 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 پردازنده می‌توان این کار را انجام داد. برای تبدیل آن به مربع باید بلوک‌های متوالی آن را کنار هم بچینیم تا موازی مرتب کنند.

جواب تمرین هندسه محاسباتی پیشرفته (تمرین ۲)

جوابهای خودم اند.

۱- الف) همان کوئری درخت چهارتایی را می‌زنیم با این تفاوت که در حالتی که قبلاً نقطه را بر‌می‌گرداندیم این‌بار جعبه شامل آن را بر‌می‌گردانیم و در خط آخر الگوریتم که جواب را بر‌می‌گردانیم مینیمم جوابهای دو قسمت را بر‌می‌گردانیم.

ب) قسمت اول: نسبت مساحت قسمتی که مرکز دایره می‌تواند در آن قرار بگیرد به کل خانه را حساب می‌کنیم و این احتمال مورد نظر است.

قسمت دوم: با قسمت قبل و به دست آوردن i با کمک شرط خاتمه به احتمال مورد نظر می‌رسیم.

ج) احتمال مورد نظر کمتر از مکعب شامل دایره به مرکز نقطه کوئری و شعاع بهینه است. نسبت حجم توپ و مکعب شامل توپ ثابت است پس احتمال مورد نظر از مرتبه نسبت مکعب محیطی توپ و مکعب خانه داده شده است.

د) جستجوی دودویی+اجرای الگوریتم

ه) جمع مقادیر قسمت قبل است. رابطه‌ی آن قبلاً آورده شده است.

۲- الف) حداکثر ۴ نوار اطراف (راست چپ بالا و پایین) خطا ایجاد می‌کنند پس با قرار دادن ۴*اپسیلون به جای اپسیلون به جواب می‌رسیم. (حکم را در تعداد نقاط هر خانه ضرب کنید.)

ب) روش merge & reduce را به کار ببرید. لگاریتمی بودن را با فرض داشتن n حل کنید.

ج) اپسیلون خلاصه را بسازید و طبق قسمت ب تقریب به دست می‌آید.

*مهلت تحویل تمرین: سه‌شنبه

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

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

به مناسبت پایان تعطیلات نوروزی و ددلاین تمرینات

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

ارائه‌ی الگوریتم تقریبی

پیچیدگی پارامتری

دریافت

حجم: 134 کیلوبایت

اسپارس کردن (خلاصه سازی گراف)

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