پردازش موازی

Parallel Processing

شماره درس: ۴۰۶۴۷ تعداد واحد: ۳
مقطع: کارشناسی ارشد نوع درس: نظری
پیش‌نیاز: – هم‌نیاز: –

اهداف درس

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

ریز مواد

  1. معرفی (۱ جلسه)
    • نیاز به پردازش موازی
    • انواع سیستم‌ها و پردازش موازی و واژه‌های علمی مورد استفاده
    • موانع پردازش موازی
    • پیچیدگی محاسبات موازی و رده‌ی NC
  2. آشنایی با الگوریتم‌های موازی (۲ جلسه)
    • چند مسئله‌ی ساده (انقباض موازی، محاسبه‌ی پیشوندی موازی، مرتب‌سازی، داده‌پراکنی)
    • چند معماری موازی (آرایه‌ی خطی، توری، ساختار درختی، گراف کامل)
    • حل مسئله‌های فوق بر روی هر ساختار و تحلیل آن (کران پایین الگوریتم‌ها)
    • آشنایی با» سیستم‌های تپنده (systolic) «و چند مسئله‌ی ساده (عملیات حسابی، محاسبات بیتی و کلمه‌ای، کانولوشن)
  3. مدل پی‌رَم (PRAM) و الگوریتم‌های پایه‌ای (۲ جلسه)
    • تعریف و فرضیات مدل پی‌رم
    • حل چند مسئله و تحلیل (داده‌پراکنی، انقباض و پیشوند موازی، ترتیب عناصر در لیست، ضرب ماتریس‌ها)
    • مسائل دیگر (انتخاب موازی، مرتب‌سازی، پوسته‌ی محدب نقاط)
  4. الگوریتم‌های موازی در سطح مدار (۴ جلسه)
    • قضیه‌ی retiming برای تبدیل مدارها و الگوریتم‌های هم‌گام به تپنده: استفاده از این قضیه در مسئله‌ی حل معادلات خطی، اجزای هم‌بند و بستار تراگذری
    • شبکه‌های مرتب‌ساز (Batcher، زوج‌-فرد)
    • جست‌وجو و عملیات بر روی فرهنگ‌داده‌ای
    • محاسبات پیشوندی، FFT
  5. الگوریتم‌های موازی مبتنی بر توری (۴ جلسه)
    • الگوریتم‌های مرتب‌سازی: Shearsort
    • الگوریتم‌های پردازش تصویر و هندسه‌ی محاسباتی
    • مسیردهی بسته‌ها (packet routing)
    • عملیات ماتریسی (حل معادلات خطی)
    • الگوریتم‌های گراف
  6. معماری‌های با قطر کم (خانواده‌ی فوق مکعب) (۴ جلسه)
    • ساختارهای» توری از درخت‌ها»، ابرمکعب، پروانه‌ای، برش‌تعویض
    • جادهی ساختارهای ساده در فوق مکعب
    • الگوریتم‌های مختلف (مرتب‌سازی، ماتریسی، …)
    • الگوریتم‌های گراف
    • مسیردهی و داده‌پراکنی
    • الگوریتم‌های نرمال بر روی این ساختارها
    • شبیه‌سازی الگوریتم‌های موازی از یک مدل به مدل دیگر
  7. مدل نگاشت-کاهش (Map-Reduce) مبتنی بر GPU (۲ جلسه)
  8. برنامه‌سازی چندریسه‌ای (۲ جلسه)

ارزیابی

  • آزمون: آزمون‌های میان‌نیم‌سال (۲۵ تا ۳۰ درصد نمره)، و پایان‌نیم‌سال (۳۰ درصد نمره)
  • تمرین: ۵ یا ۶ تمرین نظری (۱۵ تا ۲۰ درصد نمره)؛ ۲ تمرین عملی با استفاده از 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.