تمرین موازی!

http://stackoverflow.com/questions/12259044/limitations-of-work-item-load-in-gpu-cuda-opencl

اینجا جداً آدم باید بگه این داستان ادامه دارد...

دروغ سیزده؟

کار اون دوست عزیزی که منو ۲ روزه گذاشته سر کار عالیه. :|

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

من پیگیری می‌کنم که به سزای اعمالش برسه.

این هم برای محاسبه‌ی زمان برنامه:

http://www.cplusplus.com/reference/ctime/clock/

تابع‌های مربوط به خود کودا هم زمان را به میلی‌ثانیه برمی‌گردانند.

CPU بهتر از GPU؟

http://neilkemp.us/src/sse_tutorial/sse_tutorial.html

حس می‌کنم اشکال اینه که CPU ام خودش موازی می‌کنه چون مسأله ساده است! قسمت‌هایی که مربوط به آرایه‌ها و عملیات روی آنهاست بلوکی انجام میده خودش!

محاسبه زمان

http://www.cs.virginia.edu/~mwb7w/cuda_support/

http://will-landau.com/gpu/lectures/cudac-memory/cudac-memory.pdf

دقیقاً همین مثال تمرین ماست. طبیعتاً وقتی تعداد بیشتر میشه مشکل حافظه هم شدیدتر می‌شود. اینها چطوری توقع دارند ما به زمان بهتری برسیم؟؟

با توجه به این نمودار ما هیچ وقت به نتیجه بهتری نمی‌رسیم! (منبع سایت انویدیا اسلاید مرتب سازی)

البته ما توی قسمتی که محاسبات است هستیم ولی حجم محاسباتمان انقدر نیست که به کپی کردن حافظه بیارزد.

ولی در اینکه زمان محاسبات cpu را غلط اندازه می‌گیرد شکی نیست، چون به جای اینکه زمانش برای ماتریس ۱۰۰۰*۱۰۰۰ در حد ۱۶۶ ثانیه که دربیاد در حد میکروثانیه در میاد.

نه البته این با CPU کار نکرده.

تمرین پردازش موازی (برنامه نویسی)

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

http://en.wikipedia.org/wiki/CUDA

کسی می‌دونه مهلت تمرین کیه؟

stack overflow

Increase the Stack Reserve size in Project ‐> Properties ‐> Linker ‐> System ‐> Stack Reserve Size = 500000000

این بار که برنامه کودا ام رو اجرا کردم stack overflow داد! اگه شما هم برخوردید این کاری که بالا نوشتم بکنید!

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

با اون کتاب قبلی به جایی نمی‌رسید! (نتیجه منطقی بعد از یک هفته علافی)

http://moss.csc.ncsu.edu/~mueller/cluster/nvidia/0.8/NVIDIA_CUDA_Programming_Guide_0.8.2.pdf

مسأله الگوریتم تقریبی سال قبل

من داشتم حل تمرین‌های سال قبل را می‌نوشتم ولی انگار ذخیره نشده بود. سوال این بود که یک ماتریس ۰ و ۱ داریم می‌خواهیم ببینیم حالتی هست که ستون‌ها را جا به جا کنیم و همه‌ی ۱ ها کنار هم قرار بگیرند. (با integer programming حل کنید.)

حل من این بود که هر درایه ماتریس را یک متغیر می‌گیریم و مقادیر اولیه را به صورت قیود تساوی می‌گذاریم.

یک سری متغیر دیگر هم تعریف می‌کنیم که معادل جا به جا کردن هر دو ستون باشند.

برای اینکه یک‌ها کنار هم باشند هم باید متغیرهایی که تعریف کرده‌ایم به ازای یکی از حالت‌های تقسیم هر سطر به دو قسمت یک بخش ۱ داشته باشند. برای اینکه یکی از این شرط ها برقرار باشد می‌توانیم به ازای آنهایی که ۱ هستند یکی کم کنیم در این صورت حالت درست معادل ۰ می‌شود و اگر همه را در هم ضرب کنیم و صفر شود جواب دارد در غیر این صورت جواب ندارد.

سوال پردازش موازی

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

برش بیشینه با semidefinite programming

هر متغیر را با ۱ یا -۱ می‌گذاشتیم و اگر در دو دسته‌ی مختلف می‌افتادند جواب -۱ می‌شد در غیر این صورت ۱ می‌شد. آخر اثبات که سر کلاس ننوشتیم:

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