نوار کناری
درس:۴۰۶۴۷
پردازش موازی
Parallel Processing
| شماره درس: ۴۰۶۴۷ | تعداد واحد: ۳ |
| مقطع: کارشناسی ارشد | نوع درس: نظری |
| پیش‌نیاز: – | هم‌نیاز: – |
اهداف درس
هدف اصلی از پردازش موازی انجام محاسبات یا طراحی مدارهای «تپنده» به‌کمک چندین پردازنده‌ی کوچک یا بزرگ است تا بتوان کارایی و تسریع بالایی را کسب کرد. دانش‌جویان در این درس، با مباحث نظری پردازش موازی و طراحی و تحلیل الگوریتم‌های موازی بر روی معماری‌های موازی مختلف و نیز مدل انتزاعی «پی‌رم» آشنا می‌شوند و نیز با برنامه‌نویسی موازیِ مبتنی بر پردازنده‌های گرافیکی GPU، مدل «نگاشت-کاهش » (Map-Reduce) و «چندریسه‌ای» آشنا می‌شوند و کار عملی انجام می‌دهند.
ریز مواد
- معرفی (۱ جلسه)
- نیاز به پردازش موازی [از کتاب‌های پرهامی و لایتون]
- انواع سیستم‌ها و پردازش موازی و واژه‌های علمی مورد استفاده
- موانع پردازش موازی
- پیچیدگی محاسبات موازی و رده‌ی NC
- آشنایی با الگوریتم‌های موازی [از کتاب‌های پرهامی و لایتون] (۲ جلسه)
- چند مسئله‌ی ساده (انقباض موازی، محاسبه‌ی پیشوندی موازی، مرتب‌سازی، داده‌پراکنی)
- چند معماری موازی (آرایه‌ی خطی، توری، ساختار درختی، گراف کامل)
- حل مسئله‌های فوق بر روی هر ساختار و تحلیل آن (کران پایین الگوریتم‌ها)
- آشنایی با» سیستم‌های تپنده (systolic) «و چند مسئله‌ی ساده (عملیات حسابی، محاسبات بیتی و کلمه‌ای، کانولوشن)
- مدل پی‌رَم (PRAM) و الگوریتم‌های پایه‌ای [از کتاب پرهامی] (۲ جلسه)
- تعریف و فرضیات مدل پی‌رم
- حل چند مسئله و تحلیل (داده‌پراکنی، انقباض و پیشوند موازی، ترتیب عناصر در لیست، ضرب ماتریس‌ها)
- مسائل دیگر (انتخاب موازی، مرتب‌سازی، پوسته‌ی محدب نقاط)
- الگوریتم‌های موازی در سطح مدار [از کتاب لایتون] (۴ جلسه)
- قضیه‌ی retiming برای تبدیل مدارها و الگوریتم‌های هم‌گام به تپنده: استفاده از این قضیه در مسئله‌ی حل معادلات خطی، اجزای هم‌بند و بستار تراگذری
- شبکه‌های مرتب‌ساز (Batcher، زوج-فرد)
- جست‌وجو و عملیات بر روی فرهنگ‌داده‌ای
- محاسبات پیشوندی، FFT
- الگوریتم‌های موازی مبتنی بر توری [از کتاب لایتون] (۴ جلسه)
- الگوریتم‌های مرتب‌سازی: Shearsort
- الگوریتم‌های پردازش تصویر و هندسه‌ی محاسباتی
- مسیردهی بسته‌ها (packet routing)
- عملیات ماتریسی (حل معادلات خطی)
- الگوریتم‌های گراف
- معماری‌های با قطر کم (خانواده‌ی فوق مکعب) [از کتاب لایتون] (۴ جلسه)
- ساختارهای» توری از درخت‌ها»، ابرمکعب، پروانه‌ای، برش‌تعویض
- جادهی ساختارهای ساده در فوق مکعب
- الگوریتم‌های مختلف (مرتب‌سازی، ماتریسی، …)
- الگوریتم‌های گراف
- مسیردهی و داده‌پراکنی
- الگوریتم‌های نرمال بر روی این ساختارها
- شبیه‌سازی الگوریتم‌های موازی از یک مدل به مدل دیگر
- مدل نگاشت-کاهش (Map-Reduce) مبتنی بر GPU (۲ جلسه)
- برنامه‌سازی چندریسه‌ای [از کتاب CLRS] (۲ جلسه)
ارزیابی
- آزمون: آزمون‌های میان‌نیمسال (۲۵ تا ۳۰ درصد نمره)، و پایان‌نیمسال (۳۰ درصد نمره)
- تمرین: ۵ یا ۶ تمرین نظری (۱۵ تا ۲۰ درصد نمره)؛ ۲ تمرین عملی با استفاده از GPU/CUDA (۱۵ درصد نمره)
- ارائه: ارائه مطالب اضافی (با نمره اضافی)
- پژوهش: به هر دانش‌جو مقاله‌ی عمیقی از مفاهیم درس داده می‌شود. او باید مقاله را بخواند و در انتهای درس در جلسه‌ای آن را ارائه نماید و نشان دهد که با جزئیات کامل آن‌را فهمیده است. اگر بر روی این موضوع کار پژوهشی جدی انجام دهید، امتیاز ویژه و اضافی خواهید گرفت (۱۵ درصد نمره).
مراجع
- F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, 1992.
- B. Parhami. Introduction to Parallel Processing: Algorithms and Architectures. Plenum Press, 2000.
- 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).
- T. Cormen, C. Leiserson, R. Rivest, and C. Stein (CLRS). Introduction to Algorithms. 3rd ed. MIT Press, 2009.
درس/۴۰۶۴۷.txt · آخرین ویرایش: 2019/12/26 01:59 (ویرایش خارجی)