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

۱- الف) الگوریتم ادغام دو آرایه در مدل PRAM را بنویسید و نوع مدل آن را بگویید و تحلیل کنید.

ب) الگوریتم merge sort را در مدل PRAM بنویسید و نوع مدل آن را بگویید و تحلیل کنید.

۲- یک مدار systolic برای ضرب دو عدد بنویسید. از مدل کلمه‌ای استفاده کردید یا بیتی؟ روش را توضیح بدهید.

۳- یک لیست پیوندی داده شده است که در آرایه ذخیره شده است. تعداد دورهای آن را پیدا کنید. *

۴- الف) ثابت کنید الگوریتمی که در مراحل متوالی سطرها و ستون‌ها را در یک جهت مرتب می‌کند نمی‌تواند داده‌ها را به صورت مارپیچی مرتب کند. (روی مش)

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

۵- یک الگوریتم برای مسأله‌ی ترافیک (پیدا کردن مسیر که ماکسیمم وزن یالهای آن مینیمم باشد برای هر دو رأس) بدهید و مدار تپنده (systolic) متناظر آن را بکشید.

* در مورد سوال ۳ من پرسیدم که دورها یال تکراری دارند یا نه و گفتند که لیست تکرار ندارد و یک مثال هم گفتند که A-->B-->C-->B داریم. این نتیجه می‌دهد که دورها یال تکراری نداشته باشند.