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

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