חישוב מקביל ומפורץ
ביצוע עבודה בסדר
- רוב התוכניות הפשוטות הן עוקבות: הן מבצעית צעד אחד, לאחריו הצעד הבא, ואחריו הצעד השלישי.
- המחשב מגמור צעד 1 לפני שהוא מתחיל בצעד 2.
- הדבר קל להבנה, אך עלול להיות איטי עבור משימות גדולות.
Sequential (one worker):
task A -> task B -> task C -> task D
|-------|--------|--------|--------|
total time = A + B + C + D
מחשוב מקביל
- מחשוב מקביל מפצל עבודה כך שמספר חלקים יוצאים לפועל בו-זמנות.
- למחשב מודרני ישנם מספר מעבדים (כמו כן נקראים ליבות) שיכולים לבצע כל אחד מהם עבודה.
- אם ארבעה עובדים לוקחים כל אחד משימה אחת, ארבע משימות יכולות להסתיים בערך בזמן של משימה אחת.
Parallel (four workers at once):
worker 1: task A
worker 2: task B
worker 3: task C
worker 4: task D
|--------|
total time ≈ the longest single task
האצת מהירות
- האצת מהירות שואלת: כמה פעמים גרסה מקבילה היא מהירה יותר?
- speedup = (זמן ברצף) / (זמן מקביל).
- דוגמה: משימה לוקחת 8 שניות ברצף, אך 2 שניות כשהיא מחולקת. speedup = 8 / 2 = 4 פעמים.
לא תמיד N פעמים מהיר יותר
- מספר מעבדים גדול יותר לא תמיד פירושו N פעמים מהיר יותר.
- חלקים מסוימים במשימה לא ניתן לחלק – הם חייבים להתרחש ברצף.
- כמו כן, חלוקת העבודה והשלבה מחדש של התוצאות לוקחות זמן נוסף.
Job = setup (must be in order) + main work (can split)
setup main work (split over 4)
|-----| |--------------------------------|
|--------| <- this part gets 4x
The setup part stays the same length.
מחשוב מפוזר
- מחשוב מפוזר משתמש במחשבים נפרדים רבים המשתפים פעולה דרך רשת.
- הם עשויים לשבת בחדרים, ערים או מדינות שונות.
- דוגמאות: רשת (רבות שרתים), עבודות נתונים גדולים המפורקות על אלפי מכונות, ופרויקטים מדעיים גדולים.
Distributed (computers cooperate over a network):
[computer 1] [computer 2] [computer 3]
\ | /
\ | /
shared network / job
Each computer does part of the work.
פשרות
- טוב: מערכות מקבילות ומפוזרות יכולות להיות הרבה מהירות יותר, ולטפל בעבודות ענק.
- קשה יותר: הקוד מורכב יותר; חלקים חייבים להיות מסונכרנים; התוצאות חייבות להיות משולבות.
- גבולות: ההתמרה מהירה נעצרת על ידי החלקים שאינם ניתנים לפיצול, ועל ידי השהיות רשת בין מחשבים.
מילים מפתח
- סדרתי: שלבים מתבצעים אחד אחרי השני, בסדר.
- מקביל: חלקים מתבצעים בו-זמנית על מספר מעבדים.
- התמרה מהירה: זמן סדרתי חלוקה בזמן מקביל.
- מפוזר: מספר מחשבים בודדים שותפים פעולה דרך רשת.
טעויות נפוצות
- התמרה מהירה מקבילה מועילה רק לעבודה שניתן לפצל לחלקים עצמאיים.
- כל מעבד נוסף מוסיף פחות ופחות מהירות.
כעת תנסו בעצמכם
- השתמש בנוסחאות ההתמרה המהירה כפונקציות קטנות.
- דגם עבודה שמורכבת מחלק הגדרה קבוע וחלק עבודה ניתן לפיצול. לחץ על בדיקת תשובה.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
משימה יש חלק setup שחייב להירץ בסדר, וחלק splittable ש-workers יכול לשיתף בו באותו זמן. כתוב parallel_time(setup, splittable, workers) שמחזיר את הזמן הכולל: ההכנה, בנוסף לחלק הניתן לפיצול מחולק בין העובדים. דוגמה: parallel_time(2, 8, 4) → 4.0 (2 + 8/4).
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב speedup(sequential, parallel) שמחזיר כמה פעמים מהר יותר הגרסה המקבילה: הזמן הרצף מחולק בזמן המקביל. דוגמה: speedup(8, 2) → 4.0.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 3/5 · 200 מטבעות + בונוס קטן בהשלמה הראשונה היום
גם עם עובדים ללא גבול, החלק setup עדיין לא ניתן לפיצול. כתוב max_speedup(setup, splittable) להמהירות האפשרית הטובה ביותר: זמן המשימה כולה מחולק בזמן ההכנה (עובדים אינסופיים מצמצמים את החלק הניתן לפיצול לכמעט אפס, ומשאירים רק את ההכנה). דוגמה: max_speedup(2, 6) → 4.0 ((2+6)/2).
לחץ על הרץ כדי לראות את התוצא כאן.