صورت سوالهای تمرین ۴ موازی

تمرین موازی ۴ و ۵

HW4

From Leighton's

1.190

2.6

2.16

2.24

2.36

2.50

2.51

Deadline: 17/3/93  

HW5

From Parhami's

13.8

13.11

14.5

14.8

14.9

14.11

15.8

​Deadline: Final exam

جواب سوال سر کلاس موازی

صورت سوال را قبلاً گذاشتم اما تا الآن وقت نکرده بودم جوابش را بگذارم: (منبع ویکیپدیا)

In unweighted bipartite graphs[edit]

Matching problems are often concerned with bipartite graphs. Finding a maximum bipartite matching^[3] (often called a maximum cardinality bipartite matching) in a bipartite graph is perhaps the simplest problem.

The Augmenting path algorithm finds it by finding an augmenting path from each x ∈ X to  and adding it to the matching if it exists. As each path can be found in  time, the running time is . This solution is equivalent to adding a super source  with edges to all vertices in , and a super sink  with edges from all vertices in , and finding amaximal flow from  to . All edges with flow from  to  then constitute a maximum matching.

An improvement over this is the Hopcroft–Karp algorithm, which runs in  time. Another approach is based on the fast matrix multiplication algorithm and gives  complexity,^[4] which is better in theory for sufficiently dense graphs, but in practice the algorithm is slower.^[5]

Parallel Programming with Microsoft Visual C++

http://msdn.microsoft.com/en-us/library/gg675934.aspx

نظریه پردازش موازی

https://wiki.cites.illinois.edu/wiki/display/cs498tpc/Theory+of+Parallel+Computing

تمرین موازی!

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

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