חישוב מקבילי ומבוזר/נושאים בתכנות מקבילי 1

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

מקביליות

כאשר ניתן לבצע שתי הצהרות במקביל

• על מעבד אחד

statement 1;
statement 2;

• על שני מעבדים:

מעבד 1:

statement1;

מעבד 2:

statement2;

הנחת יסוד

מעבדים מבצעים עיבודים באופן עצמאי: אין שליטה/בקרה על סדר ביצוע בין המעבדים. "Processors execute independently: no control over order of execution between processors"

אפשרות 1

מעבד 1	מעבד 2
statement1;
	statement2;

אפשרות 2

מעבד 1	מעבד 2
	statement2;
statement1;

סדר הביצוע שלהם לא חייב להיות משנה! במילים אחרות

statement1; statement2;

חייב להיות שווה ערך ל:

statement2; statement1;

דוגמאות

a = 1;
b = 2;

ניתן לבצע את שתי ההצהרות במקביל.

a = 1;
b = a;

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

a = f(x);
b = a;

לא יכול להיות נבון לשנות את התכנית?

b = a;
a = 1;

לא ניתן לבצע את ההצהרות במקביל.

a = 1;
a = 2;

לא ניתן לבצע את ההצהרות במקביל.

תלויות מידע (Data Dependencies)

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

תלות אמתית (True Dependence)

יהיו S1, S2 הצהרות. יש ל-S2 תלות אמתית ב- S1 אם ורק אם S2 קורא ערך שנכתב על ידי S1. דוגמא: בדוגמא זו ההוראה S1 כותבת ל-A את הערך 5 הנקרא מיד לאחר מכן על ידי S2.

S1: A = 5
S2: B = A

לתלות זו שמות נוספים בספרות: Flow dependency וגם read-after-write (RAW) dependency

אנטי-תלות (תלות נגדית) (Anti-dependence)

יש ל-S2 אנטי-תלות (או תלות נגדית) ב-S1 אם ורק אם S2 כותבת ערך שנקרא על ידי S1 דוגמא: בדוגמא זו ההוראה S1 קוראת את התוכן של A המוחלף מיד לאחר מכן בערך 5 בהשמה המתבצעת ב-S2.

S1: B = A
S2: A = 5

לתלות זו שמות נוספים בספרות: Name dependency וגם write-after-read (WAR) dependency

תלות פלט (Output Dependence)

ל-S2 יש תלות פלט ב- S1 אם ורק אם S2 כותבת משתנה שנכתב על ידי S1 (כלומר S1 ו-S2 כותבות לאותו משתנה). דוגמא: כאן ההוראות S1 ו-S2 כותבות ערכים שונים לאותו משתנה.

S1: A = 6
S2: A = 5

לתלות זו שם נוסף בספרות: write-after-write (WAW) dependency

מסקנה

S1 ו-S2 יכולים להתבצע במקביל אם ורק אם אין תלות בין S1 ו-S2. תלות מסוימת ניתן להסיר.

סיכום

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

תלות בלולאות (Loop Dependence)

נאמר שישנה תלות בין הוראה S1 להוראה S2 בלולאות מקוננות אם ורק אם ישנן שתי איטרציות i ו-j המקיימות:

1. j ≤ i וקיים מסלול (רצף הוראות) מ-S1 ל-S2 בגוף הלולאה.
2. ההוראה S1 ניגשת למקום M בזיכרון באיטרציה i, וההוראה S2 ניגשת למקום M בזיכרון באיטרציה j, ולפחות אחת מהגישות האלה היא פעולת כתיבה.

תלות בין הוראות באיטרציות שונות בלולאה קרויה: loop-carried dependence תלות בין הוראות של אותה איטרציה קרויה: non-loop-carried dependence

דוגמאות

רוב המקביליות מתרחשת בלולאות

for (i=0; i<100; i++)
a[i] = i;

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

for(i=0; i<100; i++) {
a[i] = i;
b[i] = 2*i;
}

איטרציות והצהרות יכולים להתבצע במקביל.

for(i=0;i<100;i++) a[i] = i;
for(i=0;i<100;i++) b[i] = 2*i;

איטרציות ולולאות יכולים להתבצע במקביל.

for(i=0; i<100; i++)
a[i] = a[i] + 100;

יש תלות בעצמו. הלולאה היא עדיין ניתנת למיקבול.

for( i=0; i<100; i++ )
a[i] = f(a[i-1]);

התלות בדוגמא זו נובעת מכך שבאיטרציה i הכתיבה ל-a[i] אינה יכולה להתבצע כול עוד האיטרציה הקודמת 1-i לא הסתיימה. תלות בין a[i] and a[i-1]. חזרות הלולאה אינן מקביליות. איטרציות הלולאה אינן ניתנות למיקבול.

תלות-ביצוע לולאה (Loop-carried Dependence)

• תלות-ביצוע לולאה היא תלות שקיימת רק אם ההצהרות הם חלק מביצוע של לולאה.
• אחרת, אנחנו קוראים לזה תלות לולאה עצמאית (loop-independent dependence).
• תלות-ביצוע לולאה מונעת איטרקציית לולאה במקביל (loop iteration parallelization).

דוגמאות

for(i=0; i<100; i++ )
for(j=0; j<100; j++ )
a[i][j] = f(a[i][j-1]);

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

for( j=0; j<100; j++ )
for( i=0; i<100; i++ )
a[i][j] = f(a[i][j-1]);

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

printf(“a”);
printf(“b”);

להצהרות יש תלויות פלט נסתרות בשל זרם הפלט.

a = f(x);
b = g(x);

להצהרות יכולות להיות תלויות נסתרות אם עדכון של f ו-g מעדכן את אותו משתנה.

• בדוגמא זו אין ביכולתנו להצהיר בוודאות שלא קיימת תלות בין ההוראות, אלא אם נדע במדויק מה הפונקציות f ו-g מבצעות. כול זאת, משום שיתכן שמאחורי הקלעים פונקציות אלה עושות שימוש במשתנים משותפים.
• למשל, הפונקציה ()rand הנקראת ברצף מחזירה סידרה פסאודו-אקראית של מספרים. אם פונקציה זו נקראת על ידי שני תהליכונים במקביל, אזי אפשר - שרמת האקראיות של סדרות המספרים שנקבל תרד באופן משמעותי. הסיבה לכך היא שפונקציה זו איננה thread safe.
• כלומר, הפונקציה ()rand עושה שימוש במשתנה גלובלי נסתר מאחורי הקלעים שאליו שני התהליכונים ניגשים לקריאה וכתיבה בו זמנית.

for(i=0; i<100; i++)
a[i+10] = f(a[i]);

קיימת תלות בין ... ,a[20] ,a[10] קיימת תלות בין... ,a[21] ,a[11] … אפשריים מספר ביצועים מקביל.

for( i=1; i<100; i++) {
a[i] = …;
... = a[i-1];
}

• קיימת תלות בין a[i] ו-a[i-1].
• ביצוע מקבילי מלא בלתי אפשרי
• ביצוע מקבילי צינורי (pipelined) אפשרי

for (i=1; i<N; i+=2) {
a[i] = a[i] + a[i-1];
}

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

for( i=0; i<100; i++ )
a[i] = f(a[indexa[i]]);

• לא ניתן להגיד בוודאות.
• המקביליות תלויה בידע משתמש של ערכים ב-[]indexa
• משתמש יכול להגיד, מהדר לא יכול.

בצד

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

תזכורת

• סדר הצהרות לא חייב להיות משנה.
• הצהרות חייבות להיות ללא יחסי תלות.
• תלויות מסוימות ניתן להסיר.
• תלויות מסוימות עשויות שלא להיות מובנות מאליהן.

טכניקות להסרת תלויות

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

דוגמא להסרת תלויות ע"י openMP

for (i=0; i<N-1; i++) {
x = b[i] + c[i];
a[i] = a[i+1] + x;
}

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

1. על המשתנה x בין ההוראות של אותה איטרציה (flow dependence).
2. המשתנה x בין שתי איטרציות עוקבות (anti dependence).
3. על המשתנה, x המופיע בשורה השנייה, בין שתי איטרציות עוקבות (output dependence).
4. על המשתנה a[i+1] בין שתי איטרציות עוקבות (anti dependence).

#pragma omp parallel for shared (a, tmp)
for (i=0; i<N-1; i++) {
tmp[i] = a[i+1];
{
#pragma omp parallel for shared (a, tmp) private (x)
for (i=0; i<N-1; i++) {
x = b[i] + c[i];
a[i] = tmp[i] + x;
{

• הרעיון הוא לפרק את הלולאה לשתי לולאות נפרדות, ותוך כדי כך להסיר את התלויות.
• הלולאה הראשונה בונה מערך tmp שיכיל את כול איברי המערך a כשהם מוסטים שמאלה באיבר אחד.
• הלולאה השניה עושה שימוש במערך tmp ,ובכך מסירה את התלות מעל a[i+1].
• התלויות על המשתנה x מוסרות באחת על ידי הפיכתו למשתנה פרטי המוקצה בכול תהליכון.

קונפליקטים ותנאי מרוץ

תנאי מירוץ (Race condition)

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

דוגמאות

Consider an example: (Initially x =0)
P1: x = x + 1
P2: x = x + 2
• Case:
• P1 executes first, x=3
• P2 executes first, x=3
• P1 and P2 read at the same time, P1 writes before
P2, x=2 (x=2 כתב P2 , x=1 כתב P1)
• P1 and P2 read at the same time, P2 writes before
P1, x=1 (x=1 כתב P1 , x=2 כתב P2)
• Data Race!
• P1 and P2 read and write at the same time, Conflict!

Global MinValue = 10; // initialization
Thread-0 (Core 0)            Thread-1 (Core 1)
MinValue = Min(MinValue, 0); MinValue = Min(MinValue, 1);

Global MinValue = 10; // initialization
Thread-0 (Core 0)                Thread-1 (Core 1)
Reg1 = MinValue                  ...
Reg2 = 0                         Reg1 = MinValue 
if (Reg2 < Reg1) MinValue = Reg2 Reg2 = 0
...                              if (Reg2 < Reg1) MinValue = Reg2

מנעול (Locks) וחבק (Deadlock)

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

שתיים מהבעיות המאתגרות שאיתן על המתכנת להתמודד הם:

• מצבי קיפאון (deadlocks)
• מזעור התקורה הכרוכה בהפעלת מנגנוני נעילה וסינכרון.

חבק (Deadlock)

כל ישות מחכה למשאב המוחזק על ידי ישות אחרת; אין שחרור של אף אחד עד שהוא מקבל את מה שהוא מחכה לו.

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

• מניעה הדדית (mutual exclusion): תהליכון יכול לאחוז בזמן נתון אך ורק במשאב אחד.
• החזק והמתן (hold and wait): כול תהליכון אוחז במשאב/ים, וממתין לשיחרורם של משאב/ים המצויים בידי תהליכון אחר.
• העדר הפקעה (no preemption): משאב אינו יכול להיות משוחרר מתהליכון האוחז בו (אלא אם אותו תהליכון מרפה מאחיזתו בו).
• המתנה מעגלית (circular wait): תהליכון T1 אוחז במשאב M1 ,המבוקש על ידי תהליכון T2 האוחז במשאב M2 המבוקש על ידי T1.

פתרונות למצבי קיפאון

שיכפול משאבים

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

מנעול

• אם לא ניתן להשתמש בשיכפול משאבים כדי להימנע ממצבי קיפאון, אזי יש לדאוג לכך שרכישת האחיזה במנעולים תעשה באותו סדר.
• למשל, אפשר להימנע ממצב קיפאון אם שתי הפונקציות WORK1, WORK0 יבקשו לרכוש את המנעולים באותו הסדר, תחילה את המנעול lck0 ולאחריו את lck1.

איפשור והיחלצות

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

מיפוי (Mapping) ותזמון (Scheduling)

• עיצוב תוכנית מקבילית תחת ההנחה שחלוקת עומס העבודה באופן שווה בין הליבות, טרם ביצועה, מבטיח שכול הליבות תסיימנה את עבודתן יחד, איננה עומדת במבחן.
• במציאות. הכשל הטמון בהנחה אופטימית זו נעוץ בהנחות מוטעות נוספות המובלעות בה, כמו למשל: שלכל ליבה אותה מהירות, שהליבות הן הומוגניות, שכמות העבודה ידועה מראש טרם ביצועה, שאין תקורה הכרוכה בתקשורת בין הליבות בזמן ריצה, ושלא קיימת תלות בין הנתונים המבוזרים בין הליבות השונות. מסתבר שבהרבה מאוד מקרים אין הדבר כך.
• האסטרטגיה הדואגת לחלק את עומס העבודה באופן שווה בין הליבות השונות על מנת להשיג זמן ריצה מינימלי נקראת איזון עומסים (Load Balancing).
• אסטרטגיה זו משתלבת יחד עם שתי בעיות נוספות: בעיית המיפוי (mapping problem) ובעיית התיזמון (scheduling problem).

המיפוי והתזמון כרוכים בפעילויות הבאות:

• בחירת (Select) קבוצה של משאבים שעליה ניתן לתזמן את המשימה/ות של היישום.
• להקצות (Assign) משימות ליישום/ים, לחישוב המשאבים.
• להפיץ נתונים (Data Distribute) או לאתר נתונים לחישוב.
• להזמין משימות (Tasks Order) על משאבי מחשוב.
• להזמין תקשורת (Communication Order) בין משימות.

4 שלבים ביצירת תכנית מקבילית

• החלוקה של חישוב במשימות (Partition of computation in tasks)
• תקשורת של גישה לנתונים (Communication of data access, synch)
• מצבר של משימות לתהליכים (Agglomerate of tasks to processes)
• מיפוי תהליכים למעבדים (Mapping processes to processors)

מטרות

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

מיפוי סטטי ודינמי

• שיטות סטטיות ליצור חלוקה לפני הביצוע.

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

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

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

איזון עומסים (Load Balancing)

בעיית עומסי לא מאוזנים

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

איזון עומסים

• איזון עומסים היא אסטרטגיה לחלק יישומים כך ש:

כל המעבדים יבצעו כמות שווה של עבודה. כל המעבדים יסיימו בסכום שווה בערכים של זמן. זה באמת זמן איזון (time-balancing). ייתכן שיידרשו כמויות שונות של זמן כדי לעשות כמויות עבודה מקבילות.

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

תזמון (Scheduling)

תזמון יישום

הזמנה והקצאה של משימות/תקשורת/נתונים למעבדים. לדוגמא: יישום ממוקד למדוד את הביצועים, למשל: זמן ביצוע מינימאלי.

תזמון עבודה

הזמנה והקצאה של מקומות עבודה על ה-MPP (massively parallel processing) לדוגמא: מערכת ממוקדת מדידת הביצועים, למשל: ניצולת מעבד, תפוקה.

תזמון כנופיה (Gang scheduling)

שיטה להקצות אוסף של משימות על MPP.

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

קבוצת תזמון משימות

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