الگوریتم‌های موازی

Parallel Algorithms

مقطع: تحصیلات تکمیلی گرایش: الگوریتم‌ها و محاسبات
نوع درس: نظری تعداد واحد: ۳
پیش‌نیاز: – هم‌نیاز: –

هدف کلی

هدف اصلی از پردازش موازی انجام محاسبات یا طراحی مدارهای «تپنده» به‌کمک چندین پردازنده‌ی کوچک یا بزرگ است تا بتوان کارایی و تسریع بالایی را کسب کرد. دانشجویان در این درس، با مباحث نظری پردازش موازی و طراحی و تحلیل الگوریتم‌های موازی بر روی معماری‌های موازی مختلف، و نیز مدل انتزاعی «پی‌رم» آشنا می‌شوند و نیز با برنامه‌نویسی موازی مبتنی بر پردازنده‌های گرافیکی، مدل نگاشت-کاهش و محاسبات چندریسه‌ای آشنا می‌شوند و کار عملی انجام می‌دهند.

سرفصل‌ها

  1. آشنایی با الگوریتم‌های موازی
  2. الگوریتم‌های موازی برای مسائل مقدماتی
  3. مدل پی‌رَم (PRAM) و الگوریتم‌های پایه‌ای
  4. الگوریتم‌های موازی در سطح مدار
  5. شبکه‌های مرتب‌سازی
  6. الگوریتم‌های موازی مبتنی بر توری
  7. الگوریتم‌های گراف
  8. معماری‌های با قطر کم (خانواده‌ی فوق مکعب)
  9. مدل نگاشت-کاهش مبتنی بر GPU
  10. برنامه‌سازی چندریسه‌ای

ارزیابی پیشنهادی

  • آزمون: آزمون‌های میان‌ترم (۲۵ تا ۳۰ درصد نمره)، و پایان‌ترم (۳۰ درصد نمره)
  • تمرین: ۵ یا ۶ تمرین نظری (۱۵ تا ۲۰ درصد نمره)؛ ۲ تمرین عملی با استفاده از GPU/CUDA (۱۵ درصد نمره)
  • پژوهش: مطالعه یک مقاله و ارائه (۱۵ درصد نمره).

منابع پیشنهادی

  1. F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, 1992.
  2. B. Parhami. Introduction to Parallel Processing: Algorithms and Architectures. Plenum Press, 2000.
  3. D.B. Kirk and W.W. Hwu. Programming Massively Parallel Processors: A Hands-on Approach. 2nd Edition, Morgan Kaufmann, 2012. (supplementary text for multicore programming in CUDA.)
  4. T. Cormen, C. Leiserson, R. Rivest, and C. Stein (CLRS). Introduction to Algorithms. 4th Edition, MIT Press, 2022.