22906 אלגוריתמים מקביליים
22906 אלגוריתמים מקביליים
4 נקודות זכות
שיוך: תואר שני / מדעי המחשב
תנאי קבלה: קבלה לתואר שני במדעי המחשב.1
פיתוח הקורס: פרופ' גדי טאובנפלד, ד"ר עמוס ישראלי
השימוש העיקרי באלגוריתמים מקביליים הוא לצורך פתרון מהיר של בעיות, על-ידי שימוש בכמה מעבדים העובדים ביחד. המעבדים הם בדרך כלל מאותו סוג, רצים באותה מהירות, וממוקמים במרחק קטן זה מזה. הצורך בפתרונות מהירים ובפתרון בעיות הצורכות זמן חישוב גדול במיוחד קיים בכמה תחומים, כגון: עיבוד תמונות, חיפוש בבסיסי נתונים גדולים, פתרון בעיות אופטימיזציה, ייצור ממוחשב, חיזוי מזג אוויר, סימולציה של מערכות גדולות וכדומה.
ישנם כמה הבדלים בין המושג 'חישוב מקבילי' (שהוא נושא קורס זה) לבין המושג 'חישוב מבוזר' (שהוא הנושא של קורס אחר באוניברסיטה הפתוחה). בחישוב מקבילי מניחים בדרך כלל מודל סינכרוני (מהירות כל המעבדים זהה), ומתמקדים בפיתוח אלגוריתמים (מקביליים) לפתרון של בעיות קיימות, כאלה המהירים מאלגוריתמים סדרתיים לפתרון אותן בעיות. כאשר משתמשים במושג חישוב מבוזר מניחים בדרך כלל מודל א-סינכרוני (שבו לא מניחים דבר על המהירות היחסית של המעבדים השונים), ומתמקדים בפיתוח אלגוריתמים לפתרון של בעיות הנוצרות עקב הביזור, כגון: תיאום ושיתוף בין המעבדים.
בשנים האחרונות מתבצע מחקר בסיס רב, העוסק בהגדרת מושגים בסיסיים ומודלים פורמליים ובפיתוח טכניקות בסיסיות ואלגוריתמים עבור התחום החדש, יחסית, של החישוב המקבילי. מטרת הקורס היא לסקר חלק מהתוצאות של מחקר זה. בין היתר יילמדו טכניקות בסיסיות, יוצגו אלגוריתמים מקביליים לבעיות שונות, כאלה שיעילים יותר מאלגוריתמים סדרתיים, ולגבי כמה בעיות יוכח שלא קיימים אלגוריתמים מקביליים שיעילים לפתרונן יותר מאלה הסדרתיים. הקורס מתמקד בבסיס התאורטי של התחום, ואינו נוגע כלל בנושאים כגון מבנה מחשבים מקביליים ושפות תכנות.
חומר הלימוד
הקורס מתבסס על פרקים מתוך הספר:
J. Jaja, An Introduction to Parallel Algorithms (Addison Wesley, 1992).
הפרקים שיילמדו מהספר הם אלה:
פרק 1: מבוא; פרק 2: טכניקות בסיסיות;
פרק 3: רשימות ועצים; פרק 4: חיפוש, מיזוג ומיון (סעיפים 4.1, 4.2, 4.3.1 ו-4.4 בלבד); פרק 5: גרפים (סעיפים 5.1 ו-5.2 בלבד); פרק 10: מגבלות (סעיפים 10.1 ו-10.5 בלבד).
1סטודנט שאינו עומד בתנאי הקבלה יכול, במקרים מסוימים, להירשם לקורס. לפרטים נוספים עיינו בסעיף קבלה לקורסים בודדים בתכנית הלימודים לתואר שני במדעי המחשב.