עיבוד מקבילי

מחשב העל המקבילי Blue Gene/P של IBM

עיבוד מקבילי הוא מונח במדעי המחשב המציין עיבוד בו־זמני של מטלה מסוימת על ידי מספר מעבדים או מספר ליבות. המטלה מחולקת בין המעבדים כדי להגיע לתוצאות מהר יותר מבעיבוד טורי.

עיבוד מקבילי מבוסס על פיצול תהליך הפתרון של בעיה כלשהי למספר מטלות קטנות יותר, שאותן ניתן לבצע בו־זמנית, עם מידה מסוימת של תיאום.

המניעים לעיבוד מקבילי

המחשבים הראשונים היו מחשבים טוריים. בכל מחזור פעולה של המחשב בוצעה פעולה אחת, לדוגמה: הבא הוראה מהזיכרון, הבא מידע מהזיכרון, בצע פעולה אריתמטית, וכדומה. לחישוב הטורי מספר חסרונות:

1. שימוש לא יעיל במשאבי המחשב, ובפרט המעבד. בזמן שהמעבד מחכה לנתונים מהזיכרון או מאמצעים חיצוניים, יחידות הלוגיקה והאריתמטיקה לא מתפקדות, ולהפך.
2. גבול טכנולוגי למהירות החישוב. כתוצאה ממגבלות פיזיקליות ומגבלות של טכניקות ייצור קיים גבול תאורטי ומעשי למהירות הביצוע של מטלות. היות שמספר הפעולות שמבוצעות באלגוריתם נתון הוא קבוע, וקיים חסם תחתון על זמן הפעולה, אזי לא ניתן להוריד את זמן ביצוע האלגוריתם מתחת לזמן זה.
3. לא ניתן להתמודד עם מספר בעיות בו זמנית. כלומר במחשב המשרת מספר משתמשים, כל משתמש נאלץ לחכות לכך שהמשתמש הקודם בתור יסיים את פעולתו.

המחשב לו מייחסים את התואר המחשב המקבילי הראשון לא התמודד עם בעיות משאבים, אלא עם בעיית אמינות. המחשב היה בנוי משלושה מעבדים שביצעו את אותה פעולה בו זמנית. בסיום כל פעולה השווה המחשב את תוצאות שלושת המעבדים, ובחר בתוצאה שנתנו רוב המעבדים. המחשב נבנה בפראג בשנות ה־50 של המאה ה־20 על ידי אנטונין סוובודה.

היסטוריה

המאה ה־20

• שנות ה־40 – מחשבים טוריים דיגיטליים ראשונים.
• שנות ה־50 – מחשב רב־מעבדים לצורך חסינות לתקלות (fault tolerance) - ה־SAPO של אנטונין סוובודה.
• שנות ה־60 – מערכות הפעלה תומכות בשיתוף זמנים (מאפשרות הרצת מספר תוכנות במקביל).
• שנות ה־60 – מחשבים מרובי מעבדים.
• שנות ה־70 – לידת רעיון אשכול המחשבים (computer cluster) - חיבור מחשבים ברשת לצורך חלוקת משימות.
• שנות ה־80 – מחשבים מרובי מעבדים מאסיביים (MPP) - מחשבים בעלי מספר גבוה של מעבדים (אלפים ומעלה).
• שנות ה־90 – כניסת טכנולוגיות של pipeline, superscalar ווקטוריזציה למעבדים במחשבים אישיים.

המאה ה־21

• צמיחת המעבדים מרובי הליבות.

הטכנולוגיה של חישוב מקבילי התפתחה במשך שנים רבות תחת הקטגוריה של מחשבי העל, אך מאז שנות התשעים החלה חדירת הטכנולוגיה למגזר המסחרי והביתי.

סיווג

סיווג מקובל למבני חישוב מקבילי הוא הסיווג של פלין (Flynn) מ־1972:

1. SISD: הוראה בודדת - יחידת מידע בודדת - Single Instruction - Single Data. מחשב טורי רגיל.
2. MISD: מספר הוראות - יחידת מידע בודדת - Multiple Instruction - Single Data. אין בשיטה זו שימוש אמיתי.
3. MIMD: מספר הוראות - יחידות מידע מרובות - Multiple Instruction - Multiple Data. חישוב מקבילי מרובה מעבדים רגילים.
4. SIMD: הוראה בודדת - יחידות מידע מרובות - Single Instruction - Multiple Data. היישומים הראשונים נקראו מערך מעבדים (Processor Array). היום נפוץ ביחידות וקטוריזציה.

כמו כן נהוג לסווג על פי ארכיטקטורת העיבוד:

1. ריבוי מעבדים במחשב בודד.
2. מחשוב אשכולות (cluster computing) - חיבור מספר מחשבים באמצעות רשת ליצירת "מחשב" מבוזר.
3. מחשוב סריגי (Grid Computing) - שימוש במשאבים פנויים של מחשבים המחוברים ברשת (לרוב ציבורית).
4. מבנה הזיכרון (במחשב הבודד):
   1. SMP - שימוש סימטרי בזיכרון (Symmetric MultiProcessing). כל המעבדים מחוברים לאותו מאגר זיכרון באופן שווה.
   2. NUMA - שימוש לא סימטרי בזיכרון (NonUniform Memory Access/Architecture). חלקים שונים של הזיכרון מחוברים בהעדפה למעבד מסוים, אך קיימת גישה משותפת לכל המעבדים. המודל המעשי המשמש בתעשייה הוא CC-NUMA.
   3. MPP - ריבוי מעבדים מסיבי (Massive Parallel Processing). מחשבים בעלי אלפי מעבדים, לא ניתן לעשות שימוש במאגר זיכרון בודד במצב זה.

טכניקות חישוב מקבילי

תכנות מקבילי

אחד החוקים הבסיסיים בתכנות מקבילי קובע שההאצה משימוש בחישוב מקבילי על n מעבדים תמיד תהיה נמוכה מ־n, כלומר הפונקציה היא תמיד פחות מליניארית. הכלל נובע מחוק אמדאהל (Amdahl's law). כדי לקבל האצה כלשהי יש צורך לבנות אלגוריתם מקבילי, המחלק את המטלות על מספר מעבדים.

במקרים רבים האלגוריתם המקבילי יהיה שונה מהותית מכל אלגוריתם טורי לפתרון אותה מטלה, ואף ייתכן שיהיה לא יעיל במידה קיצונית על מחשב טורי.

כדי ליישם תכנות מקבילי יש לפרק את הבעיה לגורמים קטנים יותר. במצב האידיאלי החלוקה תהיה סימטרית - כלומר כל תת־בעיה זהה לבעיה הגדולה, פרט לכך שהיא פועלת על אוסף נתונים קטן יותר - חלק מאוסף הנתונים של הבעיה הגדולה. כך ניתן להפעיל את האלגוריתם על מספר משתנה של מעבדים ללא צורך לשנות אותו, תוך שיפור היעילות באופן יחסי למספר המעבדים (אך לא ליניארי).

במקרים אחרים מחלקים את הבעיה למספר בעיות שונות, כשכל אחת רצה על מעבד אחר. במקרה זה אין יתרון בהוספת מעבדים נוספים מעבר למספר תתי הבעיות.

רבים מהאלגוריתמים לפיכך בנויים ממספר שלבים:

1. פירוק הבעיה לתתי בעיות.
2. פתרון תתי הבעיות על המעבדים השונים (ייתכן שבאופן רקורסיבי) ו"תפירת" תנאי שפה (נקודות חפיפה) ביניהם.
3. הרכבת הפתרונות.

ממשק העברת הודעות (MPI - Message Passing Interface)

במערכות ללא זיכרון משותף, הממשק לפירוק הבעיות וקבלת התוצאות מכל אחת מיחידות העיבוד מבוסס על העברת הודעות. MPI הוא תקן מקובל לעבודה במערכות מקביליות ללא זיכרון משותף.

סינכרון

במערכות מקביליות קיימת בעיה של אי־ודאות באשר לסדר הפעולות, היות שכל מעבד מבצע את התוכנית בקצב משלו. הבעיה עלולה ליצור טעויות אלגוריתמיות הנובעות מחוסר תיאום בין המעבדים.

דוגמה

נניח תוכנית הסופרת את מספר הפעולות שכלל המעבדים מבצעים. התוכנית תיראה כך:

1. קרא מהזיכרון את מספר הפעולות שבוצעו עד עתה.
2. הוסף למספר 3 (מספר הפעולות בתוכנית זו).
3. כתוב את הערך בחזרה לזיכרון.

במצב בו שני מעבדים רצים במקביל עלול לקרות המצב הבא:

1. מעבד 1 קורא את הערך 0.
2. מעבד 2 קורא את הערך 0.
3. מעבד 1 מוסיף לערך 3.
4. מעבד 2 מוסיף לערך 3.
5. מעבד 1 כותב את הערך 3 לזיכרון.
6. מעבד 2 כותב את הערך 3 לזיכרון.

כיוון שמעבד 2 קרא את הערך לפני שמעבד 1 הספיק להוסיף את מספר הפעולות שלו, התוצאה שנרשמת בזיכרון היא 3 במקום 6.

במחשבים מרובי מעבדים מוגדרות פעולות אטומיות. פעולות אלה מוגדרות כפעולות על תא זיכרון שבמהלכן לא יקרא מעבד אחר את תא הזיכרון או יכתוב אותו. למשל, ארכיטקטורה של מעבד או של חישוב יכולה להבטיח כי פעולת ה־increment (הוספת 1 לערך בזיכרון) וה־decrement (חיסור 1) תהיינה אטומיות.

מנגנונים אחרים לצורך טיפול בבעיות סנכרון הם מנעולים מסוגים שונים. כמו כן הומצאו אלגוריתמים חסרי נעילות, שיכולים לזהות ולהתגבר על בעיות סינכרון.

מקביליות בחומרה: "צינור" (pipeline)

אחד המנגנונים הראשונים של מקביליות במערכות מחשב הוא ה"צינור". הוא מתבסס על כך שיחידות העיבוד של המחשב בנויות ממספר רכיבים בעלי תפקידים שונים:

• יחידה לוגית לביצוע פעולות and, or, xor, וכדומה.
• יחידה אריתמטית לביצוע פעולות חיבור וחיסור של מספרים שלמים.
• יחידת גישה לזיכרון.
• יחידת פענוח הוראות של התוכנית.

פעולה בודדת של המעבד יכולה להיות מורכבת ממספר שלבים. למשל חיבור שני ערכים מהזיכרון מורכב מהשלבים:

• הבאת ההוראה "חבר" מהזיכרון.
• קריאת שני הערכים מהזיכרון.
• ביצוע הפעולה.
• כתיבת התוצאה לזיכרון.

כל שלב כזה מבוצע על ידי יחידה אחרת במעבד. הצינור משתמש בעיקרון פס הייצור מעולם התעשייה. היחידות במעבד יכולות להיות כמו עמדות בפס ייצור שפועלות במקביל. כך אפשר להביא את ההוראה הבאה מהזיכרון עוד בזמן ביצוע הפעולה האריתמטית שאינה מערבת רכיבי זיכרון, וכך ליצור צינור באורך 2:

• הבא את הוראה 1 מהזיכרון
• בצע את הפעולה האריתמטית של הוראה 1. בו־זמנית: הבא את הוראה 2 מהזיכרון.
• בצע את פעולה האריתמטית של הוראה 2. בו־זמנית: הבא את הוראה 3 מהזיכרון.

למעשה ניתן היה להאיץ בתוכניות מסוימות את קצב הפעולה של המעבד פי 2 (במחשבים רבים צוואר הבקבוק היה פעולות מול הזיכרון). אחד היתרונות של שיטה זו הוא שיפור הביצועים ללא צורך בשינוי האלגוריתם. בהמשך הורחב הרעיון על ידי הפרדת המעבד ליחידות קטנות יותר, ואף הוספת יחידות זהות, כדי לאפשר צינורות ארוכים יותר. טכניקות אלה התפתחו למעבדים superscalar.

לצינורות יש מספר בעיות:

1. זמן אתחול - הזמן שלוקח לצינור להתמלא, ובסוף להתרוקן. צינורות ארוכים עלולים להתברר כלא יעילים בגלל זמני האתחול והריקון הארוכים שלהם.
2. סיבוכיות פענוח - כדי שהמעבד יזהה אוטומטית את ההזדמנויות לצינורות נדרשים אלגוריתמים סבוכים בשלב פענוח ההוראות של התוכנית. הדבר כרוך בתקורה.
3. סיבוכיות המעבד - המיקרוקוד של המעבד הפך למסובך ביותר, וחשוף לטעויות.

למרות החסרונות, הטכניקה התפתחה ונמצאת במרבית המעבדים המודרניים. היא אף הורחבה עם רעיונות נוספים:

• חיזוי הסתעפות (Branch Prediction) - ישנן הוראות המפצלות את החישוב בהתאם לתנאי כלשהו. לכאורה לא ניתן להשתמש בצינור במקרה זה, אך המעבד יכול לנחש מאיזו הסתעפות להביא את ההוראות הבאות. אם מתברר כי הוא בחר לא נכונה הוא מבטל את החישובים המיותרים. במקרה של ניחוש נכון התקבל שיפור בביצועים.
• ביצוע שלא לפי הסדר (Out of order execution) - כדי להביא לניצול מיטבי של המעבד, הוא מנסה להריץ פקודות שמנצלות יחידות פנויות אף אם אלה אינן הפקודות הבאות סדרתית בתוכנית.

מקביליות בחומרה: יחידות וקטוריות

בתכנות ישנם מצבים רבים בהם מתבצעות פעולות אריתמטיות זהות על פריטי מידע שונים (SIMD). כמו רבות מהשיטות המוזכרות פה הופיע הצורך לראשונה במחשבי־על ששימשו לסימולציות מדעיות מסובכות. פעולות אלה אופייניות כיום לפעולות גרפיות בתלת־ממד ואף בדו־ממד. לפיכך משולבות במעבד יחידות וקטוריות.

עקרון היחידה הווקטורית הוא שבמקום לפעול על פריט מידע בודד, נטען מהזיכרון אוסף של פריטים (וקטור), והפעולות מתבצעות בבת אחת על כל הפריטים.

בניגוד לצינורות, היחידות הווקטוריות הוסיפו אוסף פקודות מיוחדות למעבד שהיה צורך לעשות בהן שימוש כדי לנצל את היכולת. במעבדי אינטל הטכנולוגיה נקראה MMX, ובמעבדי IBM Power היא נקראה AltiVec. חסרונה העיקרי בכך שנדרשים מהדרים (קומפיילרים) מתוחכמים כדי לבצע וקטוריזציה עצמאית, או לחלופין התערבות מכוונת של המתכנת כדי להביא לשימוש ביחידות הווקטוריות.

בפעולות גרפיות פעולות וקטוריות הן מאוד נפוצות, ולפיכך יחידות וקטוריות (כמו גם צינורות) הפכו לחלק בלתי נפרד מכרטיסים גרפיים מודרניים, כאשר יצרן הכרטיס דואג ליישום הקוד הווקטורי לכל פעולה.

ראו גם

• בקרת מקביליות
• סמפור (מדעי המחשב)
• את'ריום
• מחשב קוונטי
• מוח מטריושקה
• Concurrency (מדעי המחשב)

קישורים חיצוניים

מדיה וקבצים בנושא עיבוד מקבילי בוויקישיתוף

• עמי מרובקה, מחשוב ותיכנות מערכות מרובות-ליבות (ספר בעברית, הורדה בחינם מהאתר), 2016
• וידאו בעברית שמסביר את הקשיים במעבר מתכנות טורי למקבילי
• עיבוד מקבילי (מחשבים), דף שער בספרייה הלאומית
• עיבוד מקבילי, באתר MathWorld (באנגלית)