עיבוד מקבילי – הבדלי גרסאות

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

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