ابزار کاربر

ابزار سایت


درس:۴۰۶۴۷

پردازش موازی

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. برنامه‌سازی چندریسه‌ای [از کتاب CLRS] (۲ جلسه)

ارزیابی

  • آزمون: آزمون‌های میان‌نیمسال (۲۵ تا ۳۰ درصد نمره)، و پایان‌نیمسال (۳۰ درصد نمره)
  • تمرین: ۵ یا ۶‎ تمرین نظری (۱۵ تا ۲۰ درصد نمره)؛ ‎‎۲ تمرین عملی با استفاده از 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. Morgan Kaufmann, 2010 (supplementary text for multicore programming in CUDA).
  4. T‎. ‎Cormen‎, ‎C‎. ‎Leiserson‎, ‎R‎. ‎Rivest‎, and C‎. ‎Stein (CLRS). Introduction to Algorithms. 3rd ed. MIT Press‎, ‎‎2009‎.
درس/۴۰۶۴۷.txt · آخرین ویرایش: 2019/12/26 01:59 (ویرایش خارجی)