بایگانی ارديبهشت ۱۳۹۳ :: الگوریتم امروز

۶۱ مطلب در ارديبهشت ۱۳۹۳ ثبت شده است

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

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

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

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

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

۰ نظر

۰ ۱۹ ارديبهشت ۹۳ ، ۱۰:۵۶

سپیده آقاملائی

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

مرجع: (شامل اطلاعات محاسبه‌ی پهنای باند حافظه هم می‌شود.)

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

اینجا زمان تابع saxpy را می‌خواهیم اندازه بگیریم:

cudaEvent_t start, stop;
cudaEventCreate(&start);
cudaEventCreate(&stop);

cudaMemcpy(d_x, x, N*sizeof(float), cudaMemcpyHostToDevice);
cudaMemcpy(d_y, y, N*sizeof(float), cudaMemcpyHostToDevice);

cudaEventRecord(start);
saxpy<<<(N+255)/256, 256>>>(N, 2.0f, d_x, d_y);
cudaEventRecord(stop);

cudaMemcpy(y, d_y, N*sizeof(float), cudaMemcpyDeviceToHost);

cudaEventSynchronize(stop);
float milliseconds = 0;
cudaEventElapsedTime(&milliseconds, start, stop);