تمرین های لایتون - 1.1
شنبه, ۳ اسفند ۱۳۹۲، ۰۸:۵۴ ق.ظ
1- اگر کار یک الگوریتم T-مرحله ای را به صورت N1+...+NT که Ni تعداد پردازنده های به کار رفته در مرحله i هستند تعریف کنیم، چقدر کار توسط فاز 1 الگوریتم مرتب سازی آرایه خطی با N پردازنده (قسمت 1.1.1 کتاب) مصرف شده است؟ نتیجه چقدر فرق می کند اگر از تعریف استاندارد W=PT برای کار استفاده کنیم؟
به جای این کار رتبه عنصر را به دست می آوریم. درخت ماکسیمم اعداد را می سازیم. مقدار هر گره میانی را به فرزندان آن می فرستیم و آن فرزندی که مقدارش با مقدار گره پدرش مساوی است، به اعداد زیردرختش می فرستد که رتبه خودشان را به اندازه ی زیر درخت کناری اضافه کنند. (توانی از 2).
هر بار ماکسیمم اعداد را با گرفتن ماکسیمم دو به دوی اعداد به دست می آوریم (از پایین به بالا) بعد به پایین ارسال می کنیم و به هر برگی به جز برگی که آن عدد ذخیره شده یکی اضافه می کنیم. این عدد را علامت می زنیم که در ماکسیمم گیری بعدی آن را حساب نکنیم. وقتی ماکسیمم نامشخص شد (یعنی هیچ عددی نبود یا فقط یک عدد بود) الگوریتم تمام شده است.
با این کار رتبه ی اعداد به دست می آید و زمانی که می برد O(N log N) است.
حل:
1+2+2+3+...+N+N=2*(1+...+N)-1 = N(N+1)-1 = N^2+N-1
W=PT=N*(2N-1) = 2N^2-N
difference: 2N^2-N-N^2-N+1=N^2-2N+1=(N-1)^2
2- دو الگوریتم برای حل مساله با اندازه M را در نظر بگیرید که یکی با M قدم روی یک ماشین با M پردازنده اجرا می شود و دیگری با sqrt(M) قدم روی یک ماشین با M^2 پردازنده اجرا می شود. کدام الگوریتم کاراتر است؟ فرض کنید که هزینه استفاده از ماشین P-پردازنده ای برای T گام، T^aP^b است که a و b ثابت هستند و P=M یا P=M^2 است. برای کدام مقادیر a و b الگوریتم اول برای استفاده ارزان تر است؟ برای کدام مقادیر a و b الگوریتم دوم ارزان تر است؟
efficiency = time_best_sequential/work_parallel = time_best_sequential/(T*P) = S/P
S = time_best_sequential/time_parallel
---------
T_best=time best sequential
E1 = T_best/(M*M)
E2 = T_best/(sqrt(M)*M^2)
E2 < E1
پس الگوریتم اول کاراتر است.
cost1 = M^a*M^b = M^(a+b)
cost2 = sqrt(M)^a*M^2b = M^(a/2+2b)
cost1 <= cost2 ==> a+b <= a/2+2b ==> a/2 <= b
پس اگر a<=2b باشد ماشین اول ارزانتر است و در غیر این صورت ماشین دوم. (حالت a=2b مساویند.)
3- دو الگوریتم برای حل مساله با اندازه M را در نظر بگیرید که یکی با M قدم روی یک ماشین با M پردازنده اجرا می شود و دیگری با sqrt(M) قدم روی یک ماشین با M^2 پردازنده اجرا می شود. کدام الگوریتم روی یک ماشین N-پردازنده ای سریعتر اجرا می شود؟ (راهنمایی: جواب شما به اندازه نسبی N و M بستگی دارد و باید از این حقیقت استفاده کنید که یک ماشین N-پردازنده ای می تواند کار یک ماشین P-پردازنده ای را شبیه سازی کند و سرعت P/N برابر می شود).
اگر N<M باشد می توانیم برنامه اول را روی ماشین N-پردازنده ای اجرای کنیم و سرعت به این صورت خواهد شد:
S = T_best_seq/M ==> S' = N/M*S = N/M*t_best_seq/M = N*t_best_seq/M^2
اگر N < M^2 باشد می توانیم برنامه دوم را روی ماشین N-پردازنده ای اجرا کنیم و سرعت به این صورت خواهد شد:
S = T_best_seq/sqrt(M) ==> S'=N/M^2*t_best_seq/sqrt(M) = N*t_best_seq/(M^2*sqrt(M))
پس جواب:
اگر N<M: الگوریتم اول بهتر است چون speed up بیشتری دارد.
اگر M<N<M*sqrt(M): الگوریتم اول بهتر است چون
S1=M*t_best_seq/M^2 = t_best_seq/M
S2 <= M*sqrt(M)*t_best_seq/(M^2*sqrt(M)) = t_best_seq/M = S1
اگر M*sqrt(M) <N<M^2: الگوریتم دوم بهتر است چون
S2 >= M*sqrt(M)*t_best_seq/(M^2*sqrt(M)) = t_best_seq/M = S1
اگر M^2 < N: الگوریتم دوم بهتر است چون
S2 = M^2*t_best_seq/(M^2*sqrt(M)) = t_best_seq/sqrt(M)
4- دو الگوریتم برای حل مساله با اندازه M را در نظر بگیرید که یکی با M قدم روی یک ماشین با M پردازنده اجرا می شود و دیگری با sqrt(M) قدم روی یک ماشین با M^2 پردازنده اجرا می شود. اگر نیاز داشته باشیم الگوریتم X بار اجرا شود و یک ماشین N-پردازنده ای داشته باشیم. روی مقادیر X و M و N شرط بگذارید و مشخص کنید کدام بهتر است؟
Time = S*T*X
T1 = M
T2 = sqrt(M)
پس جواب:
اگر N < M باشد، الگوریتم دوم زمان کمتری دارد.
Time1 = N*t_best_seq/M^2 * M = N*t_best_seq/M
Time2 = N*t_best_seq/(M^2*sqrt(M)) * sqrt(M) = N*t_best_seq/M^2
اگر M<N<M^2): الگوریتم دوم چون زمان کمتری دارد.
Time1 = t_best_seq/M * M = t_best_seq
Time2 = N*t_best_seq/(M^2*sqrt(M)) * sqrt(M) = N*t_best_seq/M^2 < t_best_seq
اگر M^2 < N باشد، هر دو مثل هم کار می کنند.
Time1 = t_best_seq/M * M = t_best_seq
Time2 = t_best_seq/sqrt(M) * sqrt(M) = t_best_seq
کلا مقدار X تاثیری ندارد.
5- چه چیزهای دیگری ممکن است باعث شوند در طراحی الگوریتم موازی سرعت مهمتر از کارایی باشد؟ (راهنمایی: فرض کنید اندازه باتری یک موشک را دارید با الگوریتم موازی کنترل می کنید.)
کاربردهای real time
6- الگوریتمی برای مرتب کردن N عدد روی مدل آرایه خطی با P پردازنده با کارایی teta( log N / N) بدهید (برای P < N) با استفاده از روشی که در قسمت 1.1.1 گفته شد.
E = T_best_serial / work_parallel = T_best_serial / T_parallel * P = log N / N
T_best_serial = N log N
==> T_parallel = N^2 / P = N * N/P
یعنی همان الگوریتم 1.1.1 را با همان روشی که گفته شد (که N/P پردازنده کار هر پردازنده را انجام بدهند) جواب می دهد. برای این کار هر پردازنده حافظه ای به اندازه N/P عدد دارد و هر کدام عملیات N/P پردازنده متوالی از مدل اولیه را انجام می دهند، که اینجا می شود مرتب کردن N/P عدد متوالی.
7- الگوریتمی برای مرتب کردن N عدد روی یک درخت دودویی کامل با O(log N) پردازنده بدهید که کارایی آن teta(1) باشد. (می توانید فرض کنید که هر پردازنده می تواند O(N/ log N) عدد را نگه دارد و می توانید از این حقیقت استفاده کنید که یک مرتب کننده ترتیبی (معمولی، غیر موازی) می تواند M عدد را در O(M log M) مرحله مرتب کند. می توانید در هر گره ای هم ورودی/خروجی داشته باشید.)
E = N log N / (T_parallel * log N) = 1 ==> T_parallel = O(N)
مشابه روشی که برای مرتب کردن بیت ها انجام دادیم عمل می کنیم. یک درخت دودویی روی اعداد می سازیم و اول پر ارزش ترین بیت را مرتب می کنیم و بعد از بین آنهایی که بیت پر ارزش مساوی دارند، بیت های بعدی را مقایسه می کنیم. برای این کار مشابه کاری که در prefix sum انجام دادیم و یک | اضافه کردیم عمل می کنیم و حاصل عملیات اعداد قبل از فاصله را در نظر نمی گیریم (اینجا یعنی جا به جا نمی کنیم).
کاری که گفته شد به O(N) پردازنده نیاز دارد. ما O(log N) پردازنده داریم. پس می توانیم همین کار را انجام بدهیم، فقط N/log N کاهش سرعت داریم.
N processor version: S = N log N / N = log N
log N processor version: S = N / log N * log N = N
8- (سوال ستاره دار): الگوریتمی برای مرتب کردن N عدد روی یک آرایه خطی O(log N)-پردازنده ای بدهید که کارایی teta(1) داشته باشد.
E = N log N / (T_parallel * log N) ==> T_parallel = N
اگر از درخت استفاده نکنیم و بخواهیم مرتب سازی را به روش سوال قبل انجام بدهیم، می توانیم در مرحله اول بیت های پر ارزشتر را مقایسه کنیم و مرتب سازی انجام بدهیم و در مرحله i-ام بیت های i ام را. این کار O(N) طول می کشد. (چون سمت چپ ترین عدد باید بتواند به سمت راست ترین مکان برسد و در هر مرحله هم حداکثر یک خانه جا به جا می شود).
9- یک مدل ترکیبی موازی/ترتیبی را برای محاسبه در نظر بگیرید که در آن یک آرایه خطی P-پردازنده ای داریم (که هر پردازنده O(1) حافظه محلی دارد) که به یک پردازنده با حافظه ی O(N) وصل است. نشان دهید که برای مرتب کردن N عدد به O( N log N / log P) مرحله نیاز است (با این مدل برای N >= P).
اگر پردازنده های میانی O(N/P) حافظه داشتند می توانستیم همان الگوریتم 1.1.1 را اجرا کنیم و زمان آن همین می شد. از آنجایی که این کار امکان پذیر نیست، چون حافظه های پردازنده های میانی O(1) هستند، باید از حافظه ی پردازنده ی آخر استفاده کنیم. اگر هر پردازنده هر بار ماکسیمم عدد خودش و عدد ورودی را به راست بفرستند (الگوریتم 1.1.1) و در پردازنده ی آخر این اعداد را قرار بدهیم، P عدد بزرگتر در آخرین مکانهای پردازنده آخر و P عدد بعد از آنها در P مکان حافظه ی بعدی هستند و ... . حالا هر دسته از این P عدد را در پردازنده های آرایه خطی می ریزیم و مرتب می کنیم. کل اعداد مرتب می شوند و زمان لازم به صورت زیر خواهد بود:
N+N/P * P = 2N ==> O(N)
10- (ستاره دار): نشان دهید که N عدد k-بیتی را چطور در O(N+k) مرحله روی یک آرایه N*N مرتب کنیم که k می تواند بزرگتر از N باشد.
الگوریتم 1.1.1 جواب می دهد و اگر مقایسه را در نظر نگیریم O(N) است و برای مقایسه ی K بیت هم O(K) در نظر بگیریم، کلا O(Nk) می شود. به جای این کار یک bit mask درست می کنیم که در سطر i-ام k/N بیت i-ام را مقایسه کند و به ردیف پایین اعلام می کند که عدد را به پردازنده سمت راستش بفرستند. زمان این کار O(k) می شود. با انجام این کار برای N مرحله کل اعداد مرتب می شوند و زمان الگوریتم O(N+k) خواهد شد.
11- ثابت کنید قطر هر گراف N-راسی که حداکثر درجه ی هر راس آن d است، حداقل (log N) / (log d) است.
قطر = حداکثر عمق bfs
در هر عمق dfs حداکثر d شاخه تولید می شود، پس حداکثر تعداد گره ها N = d^diameter
==> log (N,d) < diameter ==> log N / log d <= diameter
12- از مساله 11 استفاده کنید تا نشان دهید که هر شبکه با اتصالهای ثابت در هر پردازنده، حداقل omega(log N) مرحله برای محاسبه x1#x2#...#xN نیاز دارد که xi ها 0 و 1 اند. (علامت # را xor در نظر بگیرید.)
چون عمل xor بین دو عدد حداکثر محاسبه ای است که انجام می دهیم، d=2 است پس طبق قضیه قبل قطر از log N بیشتر مساوی است و چون قطر کران پایین برای زمان است پس حل مساله Omega(log N) است.
13- یک الگوریتم ساده و یک مدل شبکه برای حل مساله 12 با همان کران بدهید.
مدل درختی و الگوریتم هم xor هر دو عدد را به پدر آنها بدهد.
14- ثابت کنید که عرض دو نیم کننده (bisection width) برای یک توری M * N حداقل min( M,N) است برای هر MوN.
با رسم یک خط عمودی یا افقی، اگر عرض بیشتر بود افقی و اگر طول بیشتر بود عمودی، روی M/2 یا N/2 می توانیم این کار را انجام بدهیم.
15- نشان دهید چطور می توان N عدد k-بیتی را روی یک درخت دودویی کامل بخش 1.1.4 با زمان O(2^k log N) قدم بیتی مرتب کرد؟
نگاه کنید به جواب سوال 7.
16- (ستاره دار): توضیح دهید چرا کران داده شده در مساله 1.15 را نمی توان بهبود داد وقتی k <= 1/2 log n؟
#nodes = O(log N)
max # swaps in a depth = max # numbers in a node = O(2^k)
k <= 1.2 log n ==> 2^k <= sqrt(n) ==> #swaps = O(n)
17- نشان دهید هر الگوریتمی برای مرتب کردن N عدد log N بیتی روی یک درخت دودویی کامل با N برگ حداقل omega(N) قدم بیتی زمان می برد.
اگر اعداد ما به ترتیب عکس مرتب شده باشند و هر دو عدد حداکثر 2 بیت مساوی داشته باشند، به حداقل N قدم نیاز داریم. (مقایسه یا جابه جایی)
18- (ستاره دار): نشان دهید هر الگوریتمی برای مرتب کردن N عدد k بیتی روی درخت دودویی کامل به حداقل omega(kN) قدم بیتی نیاز دارد، اگر k >= (1+epsilon) log N باشد. (برای ثابت مثبت اپسیلون)
مثال سوال 17 را در نظر بگیرید و از اصل لانه کبوتری استفاده کنید. برای تمایز دادن بین اعداد حداقل به k/(log N) عمل نیاز داریم پس کلا زمان kN را حداقل نیاز داریم.
19- (سوال دوستاره دار!): نشان دهید که محاسبه میانه N عدد روی یک درخت دودویی کامل O(log^3 N) مرحله نیاز دارد.
در هر گره میانی مقدار مینیمم و ماکسیمم فرزندان آن را نگه می داریم و مقدار فرزندانی که به گره بالاتر فرستاده شده اند را پاک می کنیم. با این کار دیگر مقدار تکراری نخواهیم داشت. اگر اعداد فرد باشند، عدد مرحله آخر که در ریشه است و اگر زوج باشند میانگین دو عدد مرحله آخر که در ریشه هستند را به عنوان جواب بر می گردانیم. چون در هر گام 2 عدد حذف می شوند، کلا O(log N) گام لازم است.
20- نشان دهید چگونه هر مجموعه ای از N عدد را در O(N) گام کلمه ای روی یک درخت دودویی کامل با N برگ مرتب کنیم.
الگوریتم سوال 19 را اجرا می کنیم ولی در ریشه حافظه ی بیشتری می گیریم و اعداد مراحل قبل را نگه می داریم. اگر نخواهیم حافظه ی بیشتر استفاده کنیم، به هر گره یک حافظه اضافه می کنیم و مقادیر را به جایگاه درست آنها می فرستیم (می توانیم در ریشه یک شمارنده بگذاریم تا رتبه ی هر عنصر و در نتیجه مکان جدید آن را مشخص کند).
21- نشان دهید چطور مجموعه ای از N عدد را در O(N) گام کلمه ای روی هر شبکه درختی با درجه محدود (bounded) مرتب کنیم و فقط از کنترل محلی استفاده کنیم.
الگوریتم سوال قبل را اجرا کنیم. در هر گام حداقل 1 عدد مرتب می شود پس به بیشتر از N گام نیاز نداریم.
22- توضیح دهید که کران سوال 1.21 نمی تواند بهبود داده شود، مهم نیست چه شبکه درختی استفاده شود. (مرتب کردن بسته ها در شبکه)
به دلیل اینکه عرض درخت ثابت است، N/width از مرتبه O(N) خواهد بود.
