עיבוד מקבילי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Gnome-edit-clear.svg ערך זה זקוק לעריכה: ייתכן שהערך סובל מפגמים טכניים כגון מיעוט קישורים פנימיים, סגנון טעון שיפור או צורך בהגהה, או שיש לעצב אותו.
אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה.
מחשב העל המקבילי Blue Gene/P של IBM

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

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

המניעים לעיבוד מקבילי[עריכת קוד מקור | עריכה]

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

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

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

היסטוריה[עריכת קוד מקור | עריכה]

המאה ה-20

  • שנות ה-40 – מחשבים טוריים דיגיטליים ראשונים.
  • שנות ה-50 – מחשב שורד תקלות (fault tolerant) רב מעבדים - ה-SAPO של אנטונין סוובודה.
  • שנות ה-60 – מערכות הפעלה תומכות בשיתוף זמנים (מאפשרות הרצת מספר תוכנות במקביל).
  • שנות ה-60 – מחשבים מרובי מעבדים.
  • שנות ה-70 – לידת רעיון מחשבי 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 קורא את הערך.
  2. מעבד 2 קורא את הערך.
  3. מעבד 1 מוסיף לערך 3.
  4. מעבד 2 מוסיף לערך 3.
  5. מעבד 1 כותב את הערך לזיכרון.
  6. מעבד 2 כותב את הערך לזיכרון.

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

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

  • מנעולים מסוגים שונים.
  • מניעת גישה משותפת (mutex - Mutual Exclusion).

"צינור" (pipeline)[עריכת קוד מקור | עריכה]

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

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

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

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

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

  • הבא הוראה מהזיכרון
  • בצע פעולה אריתמטית. בו-זמנית: הבא הוראה מהזיכרון.
  • בצע פעולה אריתמטית. בו-זמנית: הבא הוראה מהזיכרון.

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

לצינורות היו מספר חסרונות עקריים:

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

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

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

יחידות וקטוריות[עריכת קוד מקור | עריכה]

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

וידאו בעברית שמסביר את הקשיים במעבר מתכנות טורי למקבילי