نوشتن همزمان نخ‌ها در حافظه اشتراکی

برای تمرین موازی لازم دارید:

http://www.bu.edu/pasi/files/2011/07/Lecture31.pdf

تمرین برنامه نویسی موازی

حواستان باشد که اگر در حافظه اشتراکی توسط دو نخ همزمان چیزی نوشته شود مقدارش صفر می‌شود!

سوالهای پایان ترم هندسه محاسباتی پیشرفته (هندسه ترکیبیاتی)

من اول معذرت می‌خواهم که موضوع هندسه ترکیبیاتی را در وبلاگ جدا کردم و یک عده پیدا نکرده بودند.

دوم اینکه کیفیت سوالهایی که می‌ذارم روز به روز داره کمتر میشه این سری توی اتوبوس نوشتم و عکس گرفتم. :)

شباهت مهدکودک و زندگی دانشجوهای ارشد/دکتری

توضیحات تمرین پردازش موازی

داده آزمون برای برنامه‌ی پردازش موازی

این یک حالت همیشه زنده از بازی زندگی است (یک بلوک ۲*۲ از خانه‌های زنده) که اینجا مثلاً برای زمان ۱۰ امتحان شده است که آخرین عدد فایل است (در یک خط جدا نوشته شده) و می‌توانید آن را عوض کنید. درست کردن فایل تست برای مسأله کار سختی نیست ولی گفتم اگر کسی خواست..

نمونه‌ی ۱۰۰*۱۰۰:

دریافت
حجم: 19.7 کیلوبایت

نمونه‌ی ۱۰۰۰*۱۰۰۰:

دریافت
حجم: 1.91 مگابایت

Formann 91 Map Labeling

این قسمت سر کلاس درس داده نشد اما جالب بود به همین دلیل اینجا می‌نویسم.

با توجه به شرط‌های موازی بودن با محورهای مختصات و داشتن یک رأس روی نقاط ورودی، به ازای هر نقطه ۴ مستطیل ممکن داریم.

در حالت کلی گفتیم که مسأله NP-hard است اما اگر اجازه دهیم دو مستطیل از مستطیل‌ها مجاز باشند حل می‌شود.

یکی از این دو حالت مجاز را با xi و دیگری را با xi' نشان می‌دهیم (برای هر نقطه pi). در نتیجه تقاطع دو مستطیل به صورت یک عبارت با دو جمله نشان داده می‌شود. پس به مسأله‌ی 2-SAT تبدیل می‌شود و در زمان خطی از مرتبه تعداد تقاطع‌های مستطیل‌ها حل می‌شود.

لم ۱: اگر مستطیلی بیشتر از ۲۴ مستطیل دیگر را قطع کند جواب نداریم.

نتیجه: تعداد تقاطع مستطیل‌ها ثابت است پس از مرتبه O(n^2) تقاطع داریم. (انتخاب دو مستطیل متقاطع * ۲۴) که این حالت می‌تواند اتفاق بیفتد:

اگر تعداد تقاطع‌های مستطیل‌ها p تا باشد، می‌توان در زمان O(n log n + p) آنها را پیدا کرد و حالت جواب نداشتن را تشخیص داد.

برای این مسأله الگوریتم O(n log^2 n) ارائه شده است و برای حالت خاص آن که مربع‌های هم‌اندازه باشد الگوریتم O(n lg n) وجود دارد.

*الگوریتم برای حالت کلی:

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

*تحلیل:

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

لم: تعداد مربع‌هایی که نقطه‌ای در آنها نیست و مربع حول یک نقطه را قطع می‌کنند حداکثر ۲ است.

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

با توجه به اینکه حداکثر ۲ مربع حول یک نقطه می‌توانند شامل نقطه باشند و لم قبل ثابت می‌شود.

زمان اجرا: در حالت عادی باید O(n^2) شود اما با استفاده از یک sweep که O(n log n) زمان می‌برد و محاسبه‌ی جواب 2-SAT در هر گام که O(n) زمان می‌برد، اگر جوابها را تا پایان رویدادها حساب کنیم و بعداً با باینری سرچ جواب بهینه را پیدا کنیم، می‌توانیم زمان کل الگوریتم را به O(n lg n) برسانیم.

*تعمیم:

با یک تبدیل آفین می‌توان آن را به حالت‌های دیگر هم تعمیم داد.

*اثبات NP-complete بودن:

مسأله‌ی 3-SAT را به این مسأله تبدیل می‌کنیم. نقاط را طوری می‌چینیم که فقط دو مستطیل مجاز داشته باشند که به این حالت‌ها xi و x'i می‌گوییم. در نتیجه برای نقاط مجاور آنها هم جواب به صورت یکتا معلوم می‌شود که به آن هم یک متغیر نسبت می‌دهیم. در نتیجه به ازای هر نقطه متغیر دو قطر و متغیر مستطیل‌های خود آن را باید در نظر بگیریم که در کل ۳ تا متغیر می‌شود. پس اینکه تصمیم بگیریم که n نقطه را می‌توان با مستطیل‌ها پوشاند NP-complete است.

Game of Life

یادتون هست وقتی که کتاب‌های صفر و یک مد شده بودند. (یک ربطی به فیزیک داشت و ما می‌خواندیم که بگوییم خوانده‌ایم.)

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

من ایمیل زدم درخواست دادم مهلتش تمدید بشود الآن تا ۵شنبه وقت دارد.

postdoc

k-level

نسخه‌ی متحرک: یک سری نقطه‌ی متحرک روی یک خط داریم که سرعت آنها ثابت است (در نتیجه معادله‌ی زمان مکان آنها خطی است) می‌خواهیم ببینیم نفر k-ام چند بار عوض می‌شود.

x=vt+x0

متناظر با در نظر گرفتن نمودارهای آنها و بررسی جا به جا شدن‌ها است. (k-level) یعنی قسمتی از نمودار که k خط زیر آن هستند. پس تعداد نقاط k-level تعداد تغییرهای نفر k-ام است.

حالت‌های خاص:

یک مجموعه خط داریم، lower envelope آنها چند یال دارد؟ 1-level را می‌توان در زمان O(n) حساب کرد. (با linear programming)

به طور مشابه برای n-level یا upper envelope.

دوگان مسأله:

دوگان خط‌ها را می‌گیریم یک مجموعه نقطه به دست می‌آید. هر نقطه جواب هم تبدیل به یک خط می‌شود که باید k نقطه یک طرف آن باشند. تعداد تغییرهای نفر k-ام برابر است با تعداد خط‌هایی که این خاصیت را دارند، به شرطی که دقیقاً خط گذرنده از دو نقطه را در نظر بگیریم.

جواب:

بین هر دو رأس k-level که زاویه محدب دارند، حداکثر می‌توانند همه‌ی خطوط زیر آن بیایند که یک زنجیره محدب با O(k) ضلع می‌سازد.

هر نقطه را به صورت یک رأس و هر خطی که k نقطه را از بقیه جدا می‌کند یک یال در نظر می‌گیریم. (طبق تعریف دقیقاً از دو نقطه می‌گذرد.)

نتیجه: هر خط عمودی O(k) یال گراف را قطع می‌کند.

هدف ما پیدا کردن همه‌ی یالهای گراف است. n/m خط عمودی رسم می‌کنیم که بین هر کدام m نقطه باشد. هر خط حداکثر O(k) یال را قطع می‌کند. درون هر ناحیه حداکثر m^2 یال داریم (گراف کامل). پس در کل داریم:

|E| = O(n/m * m^2 + n/m*k)

m = sqrt(k) ==> |E| = O(n sqrt(k))

که m بالا حالتی که دو جمله مساوی می‌شوند و |E| ماکسیمم می‌شود.

بهبود:

تعداد کل تقاطع‌های یالهای گراف O(n^2) است. تعداد نقاط n است پس تعداد خط‌های گذرنده از آنها n^2 است پس تعداد تقاطع‌های ممکن n^4 است که اتفاق نمی‌افتد.

*** اینجا به قسمتی می‌رسیم که کلاً در کلاس بحث نشد و آن این است که چطور زنجیره‌های محدب ساخته می‌شوند؟

از منفی بینهایت شروع می‌کنیم و خط با i-امین بزرگترین شیب را طی می‌کنیم. تنها تقاطع k-level با k-chain در رأسهای محدب است، چون دو یال مجاور یک رأس مشترک بین k-level و k-chain حتماً در k-level نیستند.

ویژگی‌های زنجیره‌های محدب:

۱- همه‌ی رأسهای k-level با یک رأس محدب پوشانده می‌شوند و برعکس. (رأس جدید نداریم)

۲- زنجیره‌های محدب رأسهای مجزا و غیرتکراری دارند.

۳- همه‌ی arrangement (چیدمان) خطوط زیر k-level را می‌پوشانند. در نتیجه همه‌ی رأسهای چیدمان که زیر k-level هستند نقاط تقاطع دو زنجیره محدب هستند.

۴- همه‌ی خطوطی که در ساخت زنجیره‌ی i-ام نقش دارند lower envelopeشان همان رأسهای زنجیره را دارد.

***

حالا از اینجا نتیجه می‌شود که اگر دو یال تقاطع داشته باشند، نقطه‌ی تقاطع آنها در دوگان خطی است که مماس بر زنجیره‌های گذرنده از آن نقطه‌ها است که نتیجه می‌دهد که هر دوی آنها در یک زنجیره محدب هستند اما این در فضای اولیه به معنی داشتن رأس مشترک است (تقاطع در رأس) که می‌دانستیم وجود ندارد. (تناقض)

پس حداکثر تعداد تقاطع‌های هر دو یال به اندازه‌ی تعداد مماس‌های مشترک این زنجیره‌ها است که اگر بین همه‌ی حالت‌ها جمع کنیم همان تعداد رأسهای چیدمان خطوط است که O(n^2) است. (به صورت دقیق‌تر O(nk) است)

اثبات: حالا با استفاده از لم تقاطع داریم:

O(n+n^2/3 x^1/3) = O(n+n^2/3*(nk)^1/3) = O(nk^1/3) = O(n^4/3)

چون تعداد رأسهای گراف n تا است که تعداد نقاط است و تعداد تقاطع‌های آن هم O(nk) است که از روی دوگان آن که چیدمان خطوط بود به دست آوردیم.

-----------------------------------------------------------------

مسائل مرتبط:

*تعداد یالهای level های کمتر مساوی k چندتا است؟ (در جزوه اشتباهی گفته شده رأسها)

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

جواب واقعی O(nk) است که (برای چیدمان) می‌گوید هر رأس حداکثر j^2 تا تقاطع دارد (j تعداد levelها) که کلاً O(nk) رأس دارد (چون هر level حداکثر n تا خط دارد و کلاً k تا level داریم) پس در کل O(nkj^2) است که O(n k^1/3 j^2/3) را می‌دهد. (برای اثبات آن از یک قضیه دیگر خارج از مقاله کمک گرفته بود.)

پس جواب درست این سوال که برای k=j خواسته است O(nk) است.

--------------------------------------------------------------

روش کلارکسون:

از probabilistic method استفاده می‌کنیم که اثبات قضیه با استفاده از احتمال است و اندازه‌ی k-level را حساب می‌کنیم. در زیرگراف تصادفی به دست آمده اندازه‌ی k-level برابر O(nk) به دست می‌آید که با جایگذاری در crossing lemma (لم تقاطع) به O(nk^1/3) می‌رسیم.

(کلاً چیزی از مقاله‌اش سر در نیاوردم)