Loading AI tools
מונח במדעי המחשב המציין עיבוד בו-זמני של מטלה מסוימת על ידי מספר מעבדים או מספר ליבות מוויקיפדיה, האנציקלופדיה החופשית
עיבוד מקבילי הוא מונח במדעי המחשב המציין עיבוד בו־זמני של מטלה מסוימת על ידי מספר מעבדים או מספר ליבות. המטלה מחולקת בין המעבדים כדי להגיע לתוצאות מהר יותר מבעיבוד טורי.
עיבוד מקבילי מבוסס על פיצול תהליך הפתרון של בעיה כלשהי למספר מטלות קטנות יותר, שאותן ניתן לבצע בו־זמנית, עם מידה מסוימת של תיאום.
המחשבים הראשונים היו מחשבים טוריים. בכל מחזור פעולה של המחשב בוצעה פעולה אחת, לדוגמה: הבא הוראה מהזיכרון, הבא מידע מהזיכרון, בצע פעולה אריתמטית, וכדומה. לחישוב הטורי מספר חסרונות:
המחשב לו מייחסים את התואר המחשב המקבילי הראשון לא התמודד עם בעיות משאבים, אלא עם בעיית אמינות. המחשב היה בנוי משלושה מעבדים שביצעו את אותה פעולה בו זמנית. בסיום כל פעולה השווה המחשב את תוצאות שלושת המעבדים, ובחר בתוצאה שנתנו רוב המעבדים. המחשב נבנה בפראג בשנות ה־50 של המאה ה־20 על ידי אנטונין סוובודה.
הטכנולוגיה של חישוב מקבילי התפתחה במשך שנים רבות תחת הקטגוריה של מחשבי העל, אך מאז שנות התשעים החלה חדירת הטכנולוגיה למגזר המסחרי והביתי.
סיווג מקובל למבני חישוב מקבילי הוא הסיווג של פלין (Flynn) מ־1972[1][2]:
כמו כן נהוג לסווג על פי ארכיטקטורת העיבוד:
אחד החוקים הבסיסיים בתכנות מקבילי קובע שההאצה משימוש בחישוב מקבילי על n מעבדים תמיד תהיה נמוכה מ־n, כלומר הפונקציה היא תמיד פחות מליניארית. הכלל נובע מחוק אמדאהל (Amdahl's law). כדי לקבל האצה כלשהי יש צורך לבנות אלגוריתם מקבילי, המחלק את המטלות על מספר מעבדים.
במקרים רבים האלגוריתם המקבילי יהיה שונה מהותית מכל אלגוריתם טורי לפתרון אותה מטלה, ואף ייתכן שיהיה לא יעיל במידה קיצונית על מחשב טורי.
כדי ליישם תכנות מקבילי יש לפרק את הבעיה לגורמים קטנים יותר. במצב האידיאלי החלוקה תהיה סימטרית - כלומר כל תת־בעיה זהה לבעיה הגדולה, פרט לכך שהיא פועלת על אוסף נתונים קטן יותר - חלק מאוסף הנתונים של הבעיה הגדולה. כך ניתן להפעיל את האלגוריתם על מספר משתנה של מעבדים ללא צורך לשנות אותו, תוך שיפור היעילות באופן יחסי למספר המעבדים (אך לא ליניארי).
במקרים אחרים מחלקים את הבעיה למספר בעיות שונות, כשכל אחת רצה על מעבד אחר. במקרה זה אין יתרון בהוספת מעבדים נוספים מעבר למספר תתי הבעיות.
רבים מהאלגוריתמים לפיכך בנויים ממספר שלבים:
במערכות ללא זיכרון משותף, הממשק לפירוק הבעיות וקבלת התוצאות מכל אחת מיחידות העיבוד מבוסס על העברת הודעות. MPI הוא תקן מקובל לעבודה במערכות מקביליות ללא זיכרון משותף.
במערכות מקביליות קיימת בעיה של אי־ודאות באשר לסדר הפעולות, היות שכל מעבד מבצע את התוכנית בקצב משלו. הבעיה עלולה ליצור טעויות אלגוריתמיות הנובעות מחוסר תיאום בין המעבדים.
נניח תוכנית הסופרת את מספר הפעולות שכלל המעבדים מבצעים. התוכנית תיראה כך:
במצב בו שני מעבדים רצים במקביל עלול לקרות המצב הבא:
כיוון שמעבד 2 קרא את הערך לפני שמעבד 1 הספיק להוסיף את מספר הפעולות שלו, התוצאה שנרשמת בזיכרון היא 3 במקום 6.
במחשבים מרובי מעבדים מוגדרות פעולות אטומיות. פעולות אלה מוגדרות כפעולות על תא זיכרון שבמהלכן לא יקרא מעבד אחר את תא הזיכרון או יכתוב אותו. למשל, ארכיטקטורה של מעבד או של חישוב יכולה להבטיח כי פעולת ה־increment (הוספת 1 לערך בזיכרון) וה־decrement (חיסור 1) תהיינה אטומיות.
מנגנונים אחרים לצורך טיפול בבעיות סנכרון הם מנעולים מסוגים שונים. כמו כן הומצאו אלגוריתמים חסרי נעילות, שיכולים לזהות ולהתגבר על בעיות סינכרון.
אחד המנגנונים הראשונים של מקביליות במערכות מחשב הוא ה"צינור". הוא מתבסס על כך שיחידות העיבוד של המחשב בנויות ממספר רכיבים בעלי תפקידים שונים:
פעולה בודדת של המעבד יכולה להיות מורכבת ממספר שלבים. למשל חיבור שני ערכים מהזיכרון מורכב מהשלבים:
כל שלב כזה מבוצע על ידי יחידה אחרת במעבד. הצינור משתמש בעיקרון פס הייצור מעולם התעשייה. היחידות במעבד יכולות להיות כמו עמדות בפס ייצור שפועלות במקביל. כך אפשר להביא את ההוראה הבאה מהזיכרון עוד בזמן ביצוע הפעולה האריתמטית שאינה מערבת רכיבי זיכרון, וכך ליצור צינור באורך 2:
למעשה ניתן היה להאיץ בתוכניות מסוימות את קצב הפעולה של המעבד פי 2 (במחשבים רבים צוואר הבקבוק היה פעולות מול הזיכרון). אחד היתרונות של שיטה זו הוא שיפור הביצועים ללא צורך בשינוי האלגוריתם. בהמשך הורחב הרעיון על ידי הפרדת המעבד ליחידות קטנות יותר, ואף הוספת יחידות זהות, כדי לאפשר צינורות ארוכים יותר. טכניקות אלה התפתחו למעבדים superscalar.
לצינורות יש מספר בעיות:
למרות החסרונות, הטכניקה התפתחה ונמצאת במרבית המעבדים המודרניים. היא אף הורחבה עם רעיונות נוספים:
בתכנות ישנם מצבים רבים בהם מתבצעות פעולות אריתמטיות זהות על פריטי מידע שונים (SIMD). כמו רבות מהשיטות המוזכרות פה הופיע הצורך לראשונה במחשבי־על ששימשו לסימולציות מדעיות מסובכות. פעולות אלה אופייניות כיום לפעולות גרפיות בתלת־ממד ואף בדו־ממד. לפיכך משולבות במעבד יחידות וקטוריות.
עקרון היחידה הווקטורית הוא שבמקום לפעול על פריט מידע בודד, נטען מהזיכרון אוסף של פריטים (וקטור), והפעולות מתבצעות בבת אחת על כל הפריטים.
בניגוד לצינורות, היחידות הווקטוריות הוסיפו אוסף פקודות מיוחדות למעבד שהיה צורך לעשות בהן שימוש כדי לנצל את היכולת. במעבדי אינטל הטכנולוגיה נקראה MMX, ובמעבדי IBM Power היא נקראה AltiVec. חסרונה העיקרי בכך שנדרשים מהדרים (קומפיילרים) מתוחכמים כדי לבצע וקטוריזציה עצמאית, או לחלופין התערבות מכוונת של המתכנת כדי להביא לשימוש ביחידות הווקטוריות.
בפעולות גרפיות פעולות וקטוריות הן מאוד נפוצות, ולפיכך יחידות וקטוריות (כמו גם צינורות) הפכו לחלק בלתי נפרד מכרטיסים גרפיים מודרניים, כאשר יצרן הכרטיס דואג ליישום הקוד הווקטורי לכל פעולה.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.