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

תזכורת: מקבילות

שתי הצהרות או שני חזרות לולאה (loop iterations) יכולות לרוץ במקביל או שהן לא יכולות. כאשר מסתכלים על כל תוכניות, חלקים מסוימים יכולים לרוץ במקביל, חלקים אחרים לא.

דוגמאות

f() { a = 1; b = 2; c = 3;}
g() { d = 4; e = 5; f = 6; }
main() { f(); g(); }

• אין תלויות בין f ל-g.
• לכן, f ו-g יכולים לרוץ במקביל.

f() { a = 1; b = 2; c = 3; }
g() { a = 4; b = 5; c = 6; }
main() { f(); g(); }

• קיימות תלויות תלויות בין f ל-g.
• לכן, f ו-g לא יכולים לרוץ במקביל.
• התלות היא בין משימות ל-a ,משימות ל-b, ומשימות ל-c.
• אין תלות אחרת.
• לכן, אנחנו צריכים רק לאכוף התלויות האלה.

סנכרון (Synchronization)

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

סוגי סנכרון

ישנם שלושה סוגי סנכרון מרכזיים:

• מחסום (Barrier)
  • נקודה בעת הביצוע, אשר אליה צריכות להגיע כל המטלות המעורבות בפעולה (בד"כ).
  • כל מטלה מבצעת את קטע הקוד שלה, עד שהיא מגיעה למחסום, ואז נאלצת לחכות עד שכל המטלות האחרות יגיעו למחסום (נחסמת/נעצרת).
  • כאשר המטלה האחרונה מגיעה למחסום, כל המטלות הינן מסונכרנות.
• סמפור/מנעול (Lock/Semaphore)
  • מנגנון אשר ניתן להפעיל על מספר כלשהו של מטלות (לא בהכרח על כולן).
  • המנגנון משמש בדר"כ על מנת להגן על גישה לזיכרון משותף, ומוגדרים קטעים קריטיים, אשר "מוגנים" בעזרת המנגנון הנ"ל.
  • כאשר מטלה מסוימת נכנסת לביצוע, ולשימוש בזיכרון המשותף, עד שהיא לא סיימה לטפל בו ושחררה את המנגנון, אף מטלה אחרת לא יכולה לגשת ולפעול על הזיכרון הנ"ל.
  • המנגנון הנ"ל יכול להיות חוסם (כל מטלה הרוצה לגשת, נכנסת להמתנה), ויכול להיות לא חוסם (המטלה פשוט ממשיכה, מבלי לגשת למידע המשותף).
• תקשורת מסונכרנת (Synchronous communication operations)
  • מנגנון זה הוא בין מטלות אשר רוצות לתקשר אחת עם השנייה.
  • כאשר מטלה מסוימת רוצה לתקשר עם מטלה אחרת, מבוצע תיאום בין שתיהן. למשל, המקבל "מודיע" שהוא מוכן לקבל הודעות.

התקני סנכרון (Synchronization Facility)

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

דוגמאות

f() { a = 1; b = 2; c = 3; }
g() { a = 4; b = 5; c = 6; }
main() { f(); g(); }

f() {a = 1; signal(e_a); b = 2; signal(e_b); c = 3; signal(e_c); }
g() {wait(e_a); a = 4; wait(e_b); b = 5; wait(e_c); c = 6; }
main() { f(); g(); }

• wait(x) חוסם אלא אם כן מתרחש signal(x).
• signal(x) לא חוסם, אבל גורם ל-wait(x) לבטל את החסימה, או גורם ל-wait(x) עתידי לא לחסום.

a = 1;       wait(e_a);
signal(e_a);
b = 2;       a = 4;
signal(e_b); wait(e_b);
c = 3;       b = 5;
signal(e_c); wait(e_c);
             c = 6;

• הביצוע הוא מקבילי (בעיקר) ונכון.
• התלויות הן "מכוסות" על ידי סנכרון.

אודות סנכרון

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

דוגמאות

f() { a=1; b=2; c=3; }
g() { d=4; e=5; a=6; }
main() { f(); g(); }
f() { a=1; signal(e_a); b=2; c=3; }
g() { d=4; e=5; wait(e_a); a=6; }
main() { f(); g(); }

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

תלות-ביצוע לולאה (Loop-carried dependence), לא מקבילי.

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

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

for( i=0; i<100; i++ ) a[i] = f(i);
x = g(a);
for( i=0; i<100; i++ ) b[i] = x + h( a[i] );

• לולאה ראשונה ניתנת להפעילה במקביל.
• הצהרה האמצעית היא רציפה.
• לולאה שנייה ניתנת להפעילה במקביל.
• אנחנו נצטרך לעשות עצירת ביצוע מקבילה אחרי הלולאה ראשונה ולהתחיל שוב בתחילת הלולאה השנייה.
• שתי דרכים (סטנדרטית) לעשות את זה:
  • fork() - join()
  • חסימת סנכרון (barrier synchronization)

תהליכים ב-Unix/Linux

קריאת המערכת ()fork

• תחביר: pid_t fork();
• פעולה: מעתיקה את תהליך האב לתהליך הבן וחוזרת בשני התהליכים
  • קוד זהה (ומיקום בקוד)
  • זיכרון זהה (משתנים וערכיהם, חוצצים)
  • סביבה זהה (קבצים פתוחים, file descriptors, ספרית עבודה נוכחית)
• פרמטרים: אין
• ערך מוחזר:
  • במקרה של כישלון: -1 לאב (אין בן)
  • במקרה של הצלחה: לבן מוחזר 0 ולאב מוחזר ה-pid של הבן
  • הערך של pid הוא משתנה מסוג t_pid, בד"כ int.

The pid_t data type represents process IDs

קריאת המערכת ()wait המקביל ל-()join

• תחביר: pid_t wait(int *status);
• פעולה: גורמת לתהליך הקורא להמתין עד אשר אחד מתהליכי הבן שלו יסיים
• פרמטרים:
  • status – מצביע למשתנה בו יאוחסן סטטוס הבן שסיים
• ערך מוחזר:
  • אם אין בנים, או שכל הבנים כבר סיימו וכבר בוצע להם ()wait - חזרה מיד עם ערך -1
  • אם יש בן שסיים ועדיין לא בוצע לו ()wait (תהליך zombie) חזרה מייד עם ה-pid של הבן הנ"ל ועם סטטוס הסיום שלו. מאקרו-ים שונים מאפשרים לקבל מתוך הסטטוס מידע על הבן. למשל WEXITSTATUS (status) יתן את ערך הסיום של בן שסיים (הערך שהעביר כארגומנט ל-()exit).
  • אחרת – המתנה עד שבן כלשהו יסיים

סנכרון Fork-Join

• ()fork גורם להיווצרות של מספר התהליכים ולריצתם במקביל.
• ()join גורם לכל התהליכים הללו לחכות עד שכולם הסתיימו.

מודל Fork-Join

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

דוגמא

fork();
for( i=...; i<...; i++ ) a[i] = f(i);
join();
x = g(a);
fork();
for( i=...; i<...; i++ ) b[i] = x + h( a[i] );
join();

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

• לאיטרציות תלות בסכום (sum).
• לא ניתן לבצע מקביליות.

for( i=0; i<...; i++ ) sum[i] = 0.0;
fork();
for( j=…; j<…; j++ ) sum[i] += a[j];
join();
sum = 0.0;
for( i=0; i<...; i++ ) sum += sum[i];

צמצום (רדוקציה) (Reduction)

• דפוס זה נפוץ מאוד.
• להרבה מערכות תכנות מקבילות יש תמיכה מפורשת בזה, הנקרא צמצום (reduction).

sum = reduce( +, a, 0, 100 );

דוגמא לרדוקציה

• נדון בתוכנית המחשבת בקירוב את הערך של π באמצעות אינטגרציה נומרית, תוך שימוש ב-trapezoid rule. לחישוב השטח מתחת לעקומה 4/(1+x^2) בקטע [0,1]. לשם כך, מחולק הקטע ל-num_subintervals מקטעים ברוחב 1/num_subintervals.
• האלגוריתם מחשב את שטחו של כל מקטע, כאשר גובה המקטע מתייחס לנקודת המפגש של האנך היוצא מאמצע המקטע והעקומה. סכום שטחי המקטעים הוא, בקירוב טוב, השטח שמתחת לעקומה.
• ככל שמספר המקטעים רב יותר, השטח מדויק יותר, ולכן גם הערך של π מדויק יותר. הפיתוח המתמטי הבא יבהיר את הקשר בין חישוב האינטגרל לערך π:

$\int _{0}^{1}{\frac {4}{1+x^{2}}}dx=4\times \left[\arctan(x)\right]_{x=0}^{1}=4\times \left[\arctan(1)-\arctan(0)\right]=4\times \left[{\frac {\pi }{4}}-0\right]=\pi$

#include <omp.h>
int num_subintervals = 10000000;
double subinterval;

int main(int argc, char* argv[]) {
    int i;
    double x, pi, area = 0.0;

    subinterval = 1.0 / num_subintervals;
    omp_set_num_threads(4);

    #pragma omp parallel for reduction(+:area) private(x)
    for (i = 1; i <= num_subintervals; i++) {
        x = (i - 0.5) * subinterval;
        area = area + 4.0 / (1.0 + x * x);
    }
    pi = subinterval * area;
}

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

סיכום על סנכרון

• מבני סנכרון רבים ושונים קיימים בדגמי תכנות שונים.
• תלות צריכה להיות "מכוסה" על ידי סנכרון מתאים.
• הסנכרון הוא לעתים קרובות יקר.