حل سوالهای باقیمانده از نمونه سوالهای پردازش موازی

سوالی که ماکسیمم را در مدل CRCW می‌خواست: n^2 پردازنده داریم که هر کدام مقدار i ام و j ام را مقایسه می‌کند و اگر اولی کمتر بود درایه‌ی متناظر آن را صفر می‌کند. عنصری که درایه‌ی متناظر آن ۱ است جواب است. می‌توانیم فرض کنیم مرحله بعد n پردازنده بیت متناظر را می‌خوانند و اگر ۱ بود جواب را در محل جواب می‌نویسند. که کل این کار O(1) زمان می‌برد.

سوال بعدی در مورد این بود که الگوریتمی داده شده بود و قرار بود ثابت کنیم 2n/p عنصر حداکثر عناصر هر پردازنده خواهد بود. دلیل آن این است که هر کدام از جداکننده‌های اولیه n/p2 عنصر را جدا می‌کردند و می‌دانیم در بدترین حالت می‌تواند جداکننده نهایی طوری با بقیه اختلاف داشته باشد که قبل از میانه بعدی باشد اما همه‌ی عددهای بین را شامل شود. در این حالت p*n/p2 عنصر بیشتر از کران پایین (که n/p است) داریم پس حداکثر تعداد عناصر 2n/p می‌شود.

حل دوم سوال ۱ میان ترم هندسه پیشرفته

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

هندسه ترکیبیاتی

*مسأله‌ی سیلوستر: تعدادی نقطه در صفحه داریم می‌شود همیشه خطی پیدا کرد که دقیقاً از ۲ تا نقطه بگذرد؟ (فرض کنید همه روی یک خط نیستند)

بله، اثبات: برهان خلف:

به ازای هر سه نقطه غیر هم خط فاصله‌ی یکی را از دو نقطه‌ی دیگر در نظر می‌گیریم و مینیمم این مجموعه را نقطه r و پاره‌خط pq می‌نامیم. نقطه‌ی دیگری که روی خط گذرنده از p و q است را s می‌نامیم. (چون می‌دانیم هر خطی طبق فرض خلف از دقیقاً دو نقطه نمی‌گذرد و اینجا p و q روی خط هستند پس از حداقل ۳ نقطه می‌گذرد.)

اگر پای عمود رسم شده از r روی pq بیفتد طبق نامساوی مثلث فاصله‌ی رأس نزدیک‌تر به s از rs کمتر از فاصله‌ی مینیمم است که این تناقض است.

اگر پای عمود رسم شده از r بیرون pq بیفتد طبق نامساوی مثلث فاصله‌ی رأس نزدیک‌تر به s از خط گذرنده از r و نقطه‌ی دورتر به s کمتر از فاصله‌ی مینیمم است که تناقض است.

*مسأله‌ی هاپکرافت: n نقطه و n خط داریم، حداکثر تعداد incidence ها چندتا است؟ (یعنی نقطه روی خط بیفتد و اگر یک نقطه روی تقاطع چند خط باشد چند بار شمرده می‌شود.)

کران ساده: خطوط را به m دسته‌ی n/m تایی تقسیم کنیم و در هر کدام می‌دانیم تعداد تقاطع‌ها حداکثر تعداد خط‌ها به توان ۲ است. از اینجا m طوری به دست می‌آید که O(n^3/2) وقوع (incidence) داریم. از روی جمع درجات=تعداد یالها*۲ می‌فهمیم چون هر وقوع معادل عبور یک خط از یک نقطه است که درجه آن نقطه را ۲ تا زیاد می‌کند.

کران بهتر:

O(n+x) که x تعداد تقاطع‌ها است. طبق crossing lemma (لم تقاطع)‌ تعداد یالهای O(n+n^2/3 x^1/3) است. با جایگذاری O(n^4/3) به دست می‌آید.

*مسأله‌ی اردوش: n نقطه داریم چند تا فاصله‌شان از هم دقیقاً ۱ است؟

دور هر نقطه دایره به شعاع ۱ می‌زنیم. همان اثبات مسأله‌ی هاپکرافت را می‌توانیم برای این مسأله به کار ببریم چون از خط بودن هیچ استفاده‌ای نکرده‌ایم.

استراتژی‌های حل مسأله

دیدم کتابش را برداشتم گفتم حالا چند مورد را از روی کتاب بگویم اتفاقی نمی‌افتد... :) این‌ها بیشتر قسمت‌هایی است که خودم دوست داشتم! :)

نزول نامتناهی: ایده مربوط به زمان فیثاغورث است که میگه اگر فرض کنیم یک مسأله در اعداد طبیعی جواب داشته باشه و از روی این جواب بشه نتیجه گرفت برای اعداد کوچکتری هم مسأله در اعداد طبیعی جواب دارد یعنی کلاً جواب ندارد چون اعداد طبیعی از پائین کران‌دار اند! :) یک جوری مثل شهود استقرا توی یه حالت خاصه ولی فکر کنم اون موقع هنوز استقرا نیومده بوده! :)

ناوردایی: مسأله مشخصاتی داره که با یک عمل ثابت می‌مونه. برای حل مسأله دو جور میشه از این استفاده کرد یکی اینکه بگیم ویژگی توی حالت‌های مجاز مسأله هست که توی حالت جواب نیست پس هیچ وقت به جواب نمی‌رسه. حالت دیگه اینه که بگیم مثلاً رشد تابع هدف مسأله ثابته. اگر مسأله هدفش یک تابع صعودی /نزولی باشه یعنی هر بار مقدارش زیاد/کم بشه. مثلاً تابع هدف میتونه تعداد حالت‌های مسأله باشه که محدوده یا هزینه‌ی مسأله باشه که کرانداره چون همه‌اش داره کم/زیاد میشه حداکثر به اندازه‌ی تعداد حالت‌ها (کران) تقسیم بر تغییری که هر بار میکنه تکرار برای رسیدن به جواب لازمه.

http://en.wikipedia.org/wiki/Invariant_(mathematics)

نظریه بازی‌ها: حالت‌های مسأله به دو دسته‌ی برد و باخت تقسیم می‌شوند که با یک گراف میشه نشون داد که با هر حرکت مثلاً از مجموعه برد به باخت میریم یا توی برد می‌مونیم. شبیه اتوماتاست بیشتر به نظرم (از این نظر که روی گرافش داریم می‌نویسیم که چه کاری باید انجام بشه).

رنگ‌آمیزی: من قبلاً با این مسأله حل کردم توی همین وبلاگ ولی اشاره به اسمش نکردم. یک سری ویژگی توی مسأله هستند که هر کدام را با یک رنگ مشخص می‌کنیم و بعد وقتی مسأله را حل می‌کنیم می‌توانیم با نگه داشتن هزینه‌ی هر کدام از رنگ‌ها (ویژگی‌ها) بدانیم اوضاع چطوریه! :) این را با اسم پارامتر ثابت می‌شناسند که هر کدام از رنگ‌ها یک پارامتر اند و تعداد اشیای هر رنگ مقدار آن پارامتر است.

*حالا اینها شاید خیلی هم درست نباشن و ادامه هم می‌دونم دارن ولی حالا دیگه این چیزی بود که من بلد بودم.

حل مسائل الگوریتمی با ماتریس

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

زنجیره مارکوف

simplex

حل رابطه بازگشتی با ماتریس (مثل فیبوناچی، فکر کنم قبلاً توضیح دادم.)

نظریه بازی‌ها: مثال در لینک زیر!

http://mathworld.wolfram.com/LightsOutPuzzle.html

یک پروژه‌ی پردازش تصویر هم داشتیم.

بقیه‌اش هم یادم نمیاد! :)

گذشته

چیز خیلی عجیبی بود که دیدم ۴ سال پیش داشتم در مورد motion planning می‌خوندم! (داشتم توی ایمیلم دنبال یه چیز دیگه می‌گشتم اینو دیدم!)

اصل اکسترمال

The extreme principle (or extremal principle) is a problem-solving technique that involves looking at objects with extreme properties, such as the largest or smallest element.

http://www.artofproblemsolving.com/Wiki/index.php/Extreme_principle

می‌خواستم بیشتر بنویسم دیدم خود کتاب بهتر گفته و توی این استراتژی‌های حل مسأله اصلاً خوب نگفته. :)

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

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

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

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

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

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

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

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

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

دو سوال جا افتاده از نمونه سوالات قبلی

Next two questions are on PRAM. (Linearly ordered means any two elements are comparable and they can be oredered from smaller to bigger)

Problem 6:  Let A=(a_1,a_2,...,a_n) be an array of elements drawn from a linearly ordered set. The suffix-minima problem is to compute for each i, where 1 <= i  <= n, the minimum element among {a_i,a_{i+1},...,a_n}. Develop an O(log n) time algorithm to compute suffix minima of A using a total of O(n) operations.

Problem 7: Given an array A=(a_1,a_2,...,a_n) where the elements come from a linearly ordered set S, and given two elements x,y in S, show how to store all the elements a_i from A that are between x and y in consecutive memory locations. 

Your algorithm should run in O(log n) time using O(n) operations. 

نمونه سوال موازی

مرجع:

http://people.scs.carleton.ca/~maheshwa/courses/4009COMP/outline.html

http://people.scs.carleton.ca/~maheshwa/courses/409/409.html

P1[10 Marks] Suppose a linear array consisting of n processors (labeled P_0 to P_{n-1}) contains

n natural numbers. You need to design an algorithm so that processor

P_0 outputs YES if all the input numbers are distinct, otherwise

it answers  NO. Justify why your algorithm is correct, its complexity and is it optimal?

هر پردازنده عدد خود را به پردازنده‌ی با اندیس یکی کمتر از خودش بفرستد و اگر تساوی رخ داد YES را به بعدی بفرستد. بدیهی است که در هر زمان بیش از یک عدد از یک لینک عبور نمی‌کند چون هر پردازنده فقط یک عدد دارد. بعد از n گام عدد پردازنده‌ی آخر به پردازنده‌ی اول رسیده است پس در این زمان اگر در پردازنده‌ی اول YES داشتیم یعنی جواب yes است و در غیر این صورت no است.

Question 2 (15 Marks) 

Design an algorithm for sorting N numbers on an O(log N)-processor linear array that is 100% efficient. (Assume that N/log N numbers are with each processor. Recall that efficiency is ratio of the running time of the best sequential algorithm to the work of parallel algorithm. Work of a parallel algorithm is the product of its running time and number of processors.)

جواب:

Efficiency = 1 ==> speed up = p = O(log n)

sort = O(n log n)

==> T_parallel = O(n)

اگر بخواهیم الگوریتم معمولی را با تعداد پردازنده‌ی کمتری اجرا کنیم (طبق راهنمایی سوال) داریم:

T_sort_1_processor (serial) = O( n / log n log (n/logn) ) = O(n)

سپس روی آن الگوریتم مرتب سازی زوج و فرد را اجرا می‌کنیم با فرض اینکه بیش از یک عدد در هر پردازنده هست. یعنی در هر عمل ابتدا لیست دو پردازنده را ادغام می‌کنیم و نیمه‌ی کمتر را به پردازنده سمت چپ و نیمه‌ی بیشتر را به پردازنده‌ی سمت راست می‌دهیم. مشابه مرتب سازی زوج و فرد این کار به تعداد پردازنده‌ها گام نیاز دارد که O(log n) است پس کل الگوریتم O(n) می‌شود و بهینه است.

Question 3 ( 15 Marks) Show that sorting the rows and then the columns of a mesh leaves the rows in sorted order. 

از قضیه صفر و یک استفاده می‌کنیم: اگر الگوریتمی مجموعه‌ای از ۰ و ۱ ها را درست مرتب کند، همه‌ی اعداد را درست مرتب می‌کند.

اگر در یک ستون مقدار سطر پایینی جایگزین سطر بالایی شود یعنی عنصر سطر بالایی ۱ و عنصر سطر پایینی صفر بوده است پس همه‌ی عناصر سطر بالایی که سطر پایینی برای آنها ۱ است جایگزین می‌شوند. در جهت عکس سمت چپ جا به جا می‌شود. در حالتی که اعداد دو سطر مساوی باشند بدیهی است که جابه‌جایی صورت نمی‌گیرد و اگر صورت بگیرد هم تأثیری ندارد.

P1[15 Marks] (Leftmost 1 problem) Let A be a Boolean array of size n.

a) Develp an T(n)=O(1) time (common) CRCW PRAM algorithm to find the smallest index k such that A(k) = 1. The total number of operations must be W(n)=O(n).

هر پردازنده‌ای که عدد یک دارد اندیس خود را در خانه‌ی حافظه‌ی جواب می‌نویسد ولی عدد کوچکتر در جواب نوشته می‌شود. چون نوشتن همزمان داریم می‌توانیم آن را با یک سربار لگاریتمی به مینیمم گرفتن تبدیل کنیم.

b) How fast can you solve this problem on CREW PRAM using O(n) operations.

به جواب قسمت قبل مراجعه شود.

P2[15 Marks] Suppose you are given n integers in the range [0...log n]. Develop an O(log n) time EREW PRAM sorting algorithm that uses O(n) operations.

با روش مرتب سازی سطلی عمل می‌کنیم. هر یک از این لگاریتم عدد متمایز را یک سطل می‌گیریم و تعداد عناصر هر سطل را به دست می‌آوریم. زمان لگاریتمی برای تبدیل افزایش همزمان که در ERCW است به EREW است. سپس جمع پیشوندی را حساب می‌کنیم و بازه‌ی هر کدام از اعداد در جواب به دست می‌آید سپس هر پردازنده بازه‌ی خود را نگاه می‌کند از بین این لگاریتم زوج عدد پیدا می‌کند و آن عدد را می‌نویسد. این راه حل در مدل CREW است که باعث می‌شود یک لگاریتم برای تبدیل آن به مدل EREW لازم شود.

P3[20 Marks] Show how you can compute the maximum of of n elements in O(1) parallel time using n^{1+c} processors, c is a constant and is a real number  > 0 (e.g c could be 0.25). Use Common-CRCW PRAM for this problem and look into accelarated cascading. Write down your algorithm in terms of Steps and analyze its complexity. 

هر کسی عدد خودش را در جواب می‌نویسد و ماکسیمم آنها باقی می‌ماند.

DETERMINISTIC SAMPLE SORT:

input: p processors (numbered 0 to p-1), each processor has an array of n/p items.

output: all p arrays are sorted GLOBALLY (p0 < p1 < p2 < ...)

ALGORITHM:

step 1: locally, each processor sorts its array sequentially (you may use C's quicksort).

step 2: locally, each processor picks p equally spaced elements; i.e. every (n/p^2)th element. These elemnts are called the "splitters".

step 3: all processors send their p splitters to proc. #0.

step 4: proc. #0 sorts all p^2 splitters and picks each p-th splitter, obtaining p-1 "global splitters".

step 5: proc. #0 broadcasts the p-1 global splitters to all processors.

step 6: For proc. #i let B(i,j) be the j-th bucket of its local data with respect to the global splitters; i.e. the local data between the (j-1)-th and j-th global splitter. Each processor #i computes its p buckets B(i,j), 0 <= j <= p-1, and sends (in 1 h-relation total) every B(i,j) to proc. #j.

step 7: Let b(j) be the union of B(0,j), B(1,j), B(2,j), ..., B(p-1,j); i.e. b(j) is the data received by proc. #j in step 6. Each proc. #j, locally (sequentially) sorts b(j).

Question 1 (20 MARKS):

Show that b(j) <= 2 n/p for all 0 <= j <= p-1.

Question 3 (15 Marks)  Refer to Lemma 3.3 on page 401 of Leighton's book. Show that if G_i can be embedded in G'_i with dilation d for 1<=i<=k, then G can be embedded in G' with dilation d.

Question 4 (15 Marks) Show that an N-node hypercube contains Theta(log N) edge-disjoint copies  of a sqrt(N)*sqrt(N) mesh.