Increase the Stack Reserve size in Project ‐> Properties ‐> Linker ‐> System ‐> Stack Reserve Size = 500000000
این بار که برنامه کودا ام رو اجرا کردم 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
مرجع: (شامل اطلاعات محاسبهی پهنای باند حافظه هم میشود.)
دریافت
حجم: 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);
راهنمای شروع به کار با کودا
حجم: 1.54 مگابایت
لیست کارت گرافیکهایی که کودا را پشتیبانی میکنند.
حجم: 195 کیلوبایت
تنظیمات ویژوال استدیو برای کار با کودا
حجم: 424 کیلوبایت
آموزش کودا با سی
حجم: 2.26 مگابایت
لیست آموزشهای مربوط به کودا
حجم: 156 کیلوبایت
برنامه جمع برداری با کودا
حجم: 2.5 کیلوبایت
سوالی که ماکسیمم را در مدل CRCW میخواست: n^2 پردازنده داریم که هر کدام مقدار i ام و j ام را مقایسه میکند و اگر اولی کمتر بود درایهی متناظر آن را صفر میکند. عنصری که درایهی متناظر آن ۱ است جواب است. میتوانیم فرض کنیم مرحله بعد n پردازنده بیت متناظر را میخوانند و اگر ۱ بود جواب را در محل جواب مینویسند. که کل این کار O(1) زمان میبرد.
سوال بعدی در مورد این بود که الگوریتمی داده شده بود و قرار بود ثابت کنیم 2n/p عنصر حداکثر عناصر هر پردازنده خواهد بود. دلیل آن این است که هر کدام از جداکنندههای اولیه n/p2 عنصر را جدا میکردند و میدانیم در بدترین حالت میتواند جداکننده نهایی طوری با بقیه اختلاف داشته باشد که قبل از میانه بعدی باشد اما همهی عددهای بین را شامل شود. در این حالت p*n/p2 عنصر بیشتر از کران پایین (که n/p است) داریم پس حداکثر تعداد عناصر 2n/p میشود.
۱- الف) الگوریتم ادغام دو آرایه در مدل PRAM را بنویسید و نوع مدل آن را بگویید و تحلیل کنید.
ب) الگوریتم merge sort را در مدل PRAM بنویسید و نوع مدل آن را بگویید و تحلیل کنید.
۲- یک مدار systolic برای ضرب دو عدد بنویسید. از مدل کلمهای استفاده کردید یا بیتی؟ روش را توضیح بدهید.
۳- یک لیست پیوندی داده شده است که در آرایه ذخیره شده است. تعداد دورهای آن را پیدا کنید. *
۴- الف) ثابت کنید الگوریتمی که در مراحل متوالی سطرها و ستونها را در یک جهت مرتب میکند نمیتواند دادهها را به صورت مارپیچی مرتب کند. (روی مش)
ب) نشان دهید اگر به مش لینکهایی از پردازنده آخر سطر قبل به سطر بعد وصل کنیم میتوان الگوریتم قسمت الف را طوری اصلاح کرد که اعداد را مرتب کند.
۵- یک الگوریتم برای مسألهی ترافیک (پیدا کردن مسیر که ماکسیمم وزن یالهای آن مینیمم باشد برای هر دو رأس) بدهید و مدار تپنده (systolic) متناظر آن را بکشید.
* در مورد سوال ۳ من پرسیدم که دورها یال تکراری دارند یا نه و گفتند که لیست تکرار ندارد و یک مثال هم گفتند که A-->B-->C-->B داریم. این نتیجه میدهد که دورها یال تکراری نداشته باشند.
Next two questions are on PRAM. (Linearly ordered means any two elements are comparable and they can be oredered from smaller to bigger)
Problem 6: Let A=(a_1,a_2,...,a_n) be an array of elements drawn from a linearly ordered set. The suffix-minima problem is to compute for each i, where 1 <= i <= n, the minimum element among {a_i,a_{i+1},...,a_n}. Develop an O(log n) time algorithm to compute suffix minima of A using a total of O(n) operations.
Problem 7: Given an array A=(a_1,a_2,...,a_n) where the elements come from a linearly ordered set S, and given two elements x,y in S, show how to store all the elements a_i from A that are between x and y in consecutive memory locations.
Your algorithm should run in O(log n) time using O(n) operations.
مرجع:
http://people.scs.carleton.ca/~maheshwa/courses/4009COMP/outline.html
http://people.scs.carleton.ca/~maheshwa/courses/409/409.html
P1[10 Marks] Suppose a linear array consisting of n processors (labeled P_0 to P_{n-1}) contains
n natural numbers. You need to design an algorithm so that processor
P_0 outputs YES if all the input numbers are distinct, otherwise
it answers NO. Justify why your algorithm is correct, its complexity and is it optimal?
هر پردازنده عدد خود را به پردازندهی با اندیس یکی کمتر از خودش بفرستد و اگر تساوی رخ داد YES را به بعدی بفرستد. بدیهی است که در هر زمان بیش از یک عدد از یک لینک عبور نمیکند چون هر پردازنده فقط یک عدد دارد. بعد از n گام عدد پردازندهی آخر به پردازندهی اول رسیده است پس در این زمان اگر در پردازندهی اول YES داشتیم یعنی جواب yes است و در غیر این صورت no است.
Question 2 (15 Marks)
Design an algorithm for sorting N numbers on an O(log N)-processor linear array that is 100% efficient. (Assume that N/log N numbers are with each processor. Recall that efficiency is ratio of the running time of the best sequential algorithm to the work of parallel algorithm. Work of a parallel algorithm is the product of its running time and number of processors.)
جواب:
Efficiency = 1 ==> speed up = p = O(log n)
sort = O(n log n)
==> T_parallel = O(n)
اگر بخواهیم الگوریتم معمولی را با تعداد پردازندهی کمتری اجرا کنیم (طبق راهنمایی سوال) داریم:
T_sort_1_processor (serial) = O( n / log n log (n/logn) ) = O(n)
سپس روی آن الگوریتم مرتب سازی زوج و فرد را اجرا میکنیم با فرض اینکه بیش از یک عدد در هر پردازنده هست. یعنی در هر عمل ابتدا لیست دو پردازنده را ادغام میکنیم و نیمهی کمتر را به پردازنده سمت چپ و نیمهی بیشتر را به پردازندهی سمت راست میدهیم. مشابه مرتب سازی زوج و فرد این کار به تعداد پردازندهها گام نیاز دارد که O(log n) است پس کل الگوریتم O(n) میشود و بهینه است.
Question 3 ( 15 Marks) Show that sorting the rows and then the columns of a mesh leaves the rows in sorted order.