تمرین های فصل 1.2 لیتون
23- نشان دهید چطور الگوریتم جمع carry-lookahead را تغییر دهیم تا یک عدد N بیتی را از یک عدد دیگر در زمان 2logN+2 قدم بیتی کم کند. می توانید از مکمل 2 استفاده کنید اما خروجی باید با فرمت ورودی باشد.
خود carry look ahead :
برای اینکه فرمت ورودی به هم نخورد، عملگر را از اول تعریف می کنیم:
1-1 = 0 , 0-0 = 0 ==> propagate (p)
0-1=1, carry(-1) ==> generate (g)
1-0 = 1 ==> stop (s)
بقیه مراحل الگوریتم مثل قبل است.
24- یک درخت دودویی کامل N-برگی داده شده است که هر برگ حافظه O(log N) بیتی دارد. نشان دهید چطور دو عدد N log N بیتی را روی این درخت با O( log N) قدم بیتی جمع کنیم. کارایی این الگوریتم چقدر است؟
تعداد برگها N/2 است پس در هر برگ log N/(N/2) = 2 log N بیت از جواب قرار می گیرد. carry ایجاد شده در هر برگ مثل سوال قبل محاسبه می شود.
E = T_best_serial/W_parallel = N log N / (log N * N) = 1
25- نشان دهید چطور یک الگوریتم موازی پیشوندی (parallel prefix) را روی یک درخت سه تایی انجام دهیم. تعمیم الگوریتم برای درخت d-تایی چطور خواهد بود؟ (d>3)
در هر گره باید به صورت سریال عملیات را روی فرزندان انجام بدهیم. عمق درخت لگاریتم در مبنای d خواهد شد ولی زمان محاسبه سریال d عنصر هم در زمان ضرب می شود که در کل همان مرتبه لگاریتمی است.
26- چقدر طول می کشد که دو عدد N بیتی را روی یک آرایه sqrt(N)*sqrt(N) ضرب کنیم؟
با روش مارپیچی (که سطرهای زوج را صعودی و سطرهای فرد را نزولی مرتب می کردیم و بعد ستونها را صعودی مرتب می کردیم و تکرار) بار اول نصف کمتر و بیشتر اعداد مشخص می شد و همین کار تکرار می شد. کلا log (sqrt(N)) = O(log N) بار تکرار لازم است هر بار یک مرتب کردن هم داریم که O(sqrt(N)) طول می کشد پس کلاً O(sqrt(N) log(N)) زمان می خواهد.
27- الگوریتم پیشوندی موازی (parallel prefix) قسمت 1.2.2 را تغییر دهید تا پسوند حساب کند.
فاز اول تغییری نمی کند، فاز دوم را به جای اینکه سمت چپ ترین مسیر را به همه ی زیر درخت های سمت راست بفرستیم، سمت راست ترین مسیر را به همه ی زیردرخت های چپ می فرستیم.
شکل پیشوندی: (آخرین شکل: هر گره از بالا پسوند سمت راستی را می گیرد و مقدار خودش را به اول آن اضافه می کند.)
28- مساله توزیع داده شامل توزیع مقدار مشخصی داده بین مجموعه ای از پردازنده ها است. به ما مقدار عمق درخت دودویی (D) و m مقدار v1,...,vm داده شده است. هر برگ درخت یا شامل یک درخواست ri برای مقدار i-ام است یا خود مقدار v_i. به علاوه ما فرض می کنیم همه درخواستهای مقدار i بلافاصله بعد از خود مقدار i آمده اند. مثلا در شکل 1-119. مساله توزیع vi به هر برگ متقاضی آن است. نشان دهید چطور این کار در O(D) گام ممکن است، اگر در ابتدای کار ندانیم کدام برگ ها درخواست اند و کدام برگ ها مقادیر هستند.
(راهنمایی: از پیشوند موازی استفاده کنید.)
(الآن به ذهنم رسید یک سری از حل های قبلی باید غلط باشند چون من بیشتر از یک داده از یک لینک رد می کردم!!)
اول کران پایین را برای این مساله حساب می کنیم:
bisection width = 2 ==> lower_bound1 = 2m/2 = O(2*2^d/2) = O(2^d)
diameter = 2d ==> lower_bound2 = 2d
==> lower bound = max(m,2d)
به ازای d>5 مقدار کران پایین مساله برای درخت دودویی کامل از O(d) که سوال خواسته است بیشتر می شود. پس با عملیات کلمه ای این مساله حل نمی شود.
باید از ایده ای مشابه مرتب سازی استفاده کنیم، در آنجا کاری که می کردیم به این کار خیلی شبیه بود، فقط از اول جای نهایی اعداد را می دانستیم که اینجا می توانیم آن را با عملیات پیشوندی موازی به صورت بیتی به دست بیاوریم. یک عدد m بیتی بگیریم که هر بیت آن بودن یک درخواست را نشان می دهد و برای محاسبه ی مقدار ریشه آن را or کنیم. در هر زیردرختی فقط مقداری را می فرستیم که درخواست شده باشد و این کار را هم به صورت بیتی انجام می دهیم. ؟؟ یادم نیست در مرتب سازی چطور اعداد را جا به جا می کردیم؟!
29- دو مساله پیشوندی با N ورودی داده شده اند، نشان دهید چطور آنها می توانند به صورت یک مساله پیشوندی موازی (اما پیچیده تر) حل شوند.
هر بار در هر پردازنده دو تا مقدار نگه داریم که هر کدام مربوط به یکی از مسائل است.
30- نشان دهید چطور مقایسه دو عدد N بیتی می تواند توسط محاسبه پیشوندی موازی انجام شود.
عملگر مقایسه را روی زیرمجموعه های دو عدد انجام می دهیم و هر عددی که پیشوند آن بزرگتر بود بزرگتر است. (چون پیشوند رقمهای پرارزش است).
31- نشان دهید که الگوریتم دو مرحله ای زیر پیشوندها را روی درخت دودویی حساب می کند. در ورودی i-امین برگ xi را ذخیره می کند. در فاز حرکت به سمت بالا هر گره میانه مقدار فرزند چپ خود را ذخیره می کند و concat مقادیر فرزندانش را به پدرش می فرستد. در فاز حرکت به سمت پایین هر گره میانی مقداری که از پدرش دریافت کرده به فرزند چپش می فرستد و concat مقدار پدرش را با مقدار خودش را به فرزند راستش می فرستد. (شکل 1-120)
