עיבוד מקבילי

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

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

הטכנולוגיה התפתחה במחשבי־על. מאז שנות ה־90 היא נכנסה גם למחשבים ביתיים.

סיווג נפוץ הוא של פלין משנת 1972:
SISD, הוראה אחת, נתון אחד. זהו מחשב טורי רגיל.
SIMD, הוראה אחת על הרבה נתונים. מתאים לחישובים זהים על וקטורים.
MIMD, הוראות רבות על נתונים רבים. זהו חישוב מקבילי קלסי.
MISD כמעט לא בשימוש מעשי.

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

סוגי זיכרון במערכות בודדות:
SMP, גישה סימטרית לזיכרון משותף לכל המעבדים.
NUMA, גישה לא סימטרית. חלקים מהזיכרון קרובים יותר למעבד מסוים.
MPP, מערכות עם אלפי מעבדים, ללא מאגר זיכרון יחיד.

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

במערכות ללא זיכרון משותף התקשורת בין המעבדים מבוססת על העברת הודעות.
MPI הוא תקן נפוץ להעברת הודעות במערכות כאלה.

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

נניח שיש ספירה משותפת, וכל מעבד מוסיף שלוש פעולות.
אם שני מעבדים קוראים את הערך 0 ואז כל אחד מוסיף 3, התוצאה תישאר 3 במקום 6.
זו בעיית סנכרון שנקראת race condition (תחרות על משאב).
במחשבים מרובי מעבדים קיימות פעולות אטומיות. פעולה אטומית (atomic) היא פעולה שלא ניתן להפריע לה באמצע.
מנגנונים נוספים הם מנעולים (locks) ושיטות חסרות נעילות שמאתרות בעיות סינכרון.

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

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

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

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

בשנות ה־50 נבנה מחשב עם שלושה מעבדים. הם השוו ביניהם כדי לוודא אמינות.
מאז הטכנולוגיה התפתחה והגיעה גם למחשבים ביתיים.

SISD, מחשב טורתי, עושה הוראה אחת על נתון אחד.
SIMD, הוראה אחת על הרבה נתונים. זה טוב לעיבוד תמונות.
MIMD, כמה הוראות על נתונים שונים. מתאים למחשבים מרובי מעבדים.

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

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

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

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