הצגת המקור של הדף "חישוב מקבילי ומבוזר/נושאים בתכנות מקבילי 2"

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

=== דוגמאות ===
#
<syntaxhighlight lang="LanguageName">
f() { a = 1; b = 2; c = 3;}
g() { d = 4; e = 5; f = 6; }
main() { f(); g(); }
</syntaxhighlight>
* אין תלויות בין f ל-g.
* לכן, f ו-g יכולים לרוץ במקביל.

#
<syntaxhighlight lang="LanguageName">
f() { a = 1; b = 2; c = 3; }
g() { a = 4; b = 5; c = 6; }
main() { f(); g(); }
</syntaxhighlight>
* קיימות תלויות תלויות בין 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) עתידי לא לחסום.

==== דוגמאות ====
#
<syntaxhighlight lang="LanguageName">
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(); }
</syntaxhighlight>

* wait(x) חוסם אלא אם כן מתרחש signal(x).
* signal(x) לא חוסם, אבל גורם ל-wait(x) לבטל את החסימה, או גורם ל-wait(x) עתידי לא לחסום.
#
<syntaxhighlight lang="LanguageName">
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;
</syntaxhighlight>
* הביצוע הוא מקבילי (בעיקר) ונכון.
* התלויות הן "מכוסות" על ידי סנכרון.

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

==== דוגמאות ====
#
<syntaxhighlight lang="LanguageName">
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(); }
</syntaxhighlight>

#
<syntaxhighlight lang="LanguageName">
for( i=1; i<100; i++ ) {
a[i] = …;
…;
… = a[i-1];
}
</syntaxhighlight>
תלות-ביצוע לולאה (Loop-carried dependence), לא מקבילי.
<syntaxhighlight lang="LanguageName">
for( i=...; i<...; i++ ) {
a[i] = …;
signal(e_a[i]);
…;
wait(e_a[i-1]);
… = a[i-1];
}
</syntaxhighlight>
* שימו לב שכאן זה לא חשוב איזה חזרות (iterations) מוקצות לאיזה מעבד (processor).
* זה לא משנה לנכונות, אבל זה כן חשוב לביצועים.
* משימה מחזורית היא כנראה הטובה ביותר.
#
<syntaxhighlight lang="LanguageName">
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] );
</syntaxhighlight>
* לולאה ראשונה ניתנת להפעילה במקביל.
* הצהרה האמצעית היא רציפה.
* לולאה שנייה ניתנת להפעילה במקביל.
* אנחנו נצטרך לעשות עצירת ביצוע מקבילה אחרי הלולאה ראשונה ולהתחיל שוב בתחילת הלולאה השנייה.
* שתי דרכים (סטנדרטית) לעשות את זה:
** 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 נוספת, אזי תהליך המקבול שצוין לעיל חוזר על עצמו.
=== דוגמא ===
#
<syntaxhighlight lang="LanguageName">
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();
</syntaxhighlight>
#
<syntaxhighlight lang="LanguageName">
sum = 0.0;
for( i=0; i<100; i++ ) sum += a[i];
</syntaxhighlight>
* לאיטרציות תלות בסכום (sum).
* לא ניתן לבצע מקביליות.
<syntaxhighlight lang="LanguageName">
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];
</syntaxhighlight>

== צמצום (רדוקציה) (Reduction) ==
* דפוס זה נפוץ מאוד.
* להרבה מערכות תכנות מקבילות יש תמיכה מפורשת בזה, הנקרא צמצום (reduction).
<syntaxhighlight lang="LanguageName">
sum = reduce( +, a, 0, 100 );
</syntaxhighlight>
=== דוגמא לרדוקציה ===
* נדון בתוכנית המחשבת בקירוב את הערך של π באמצעות אינטגרציה נומרית, תוך שימוש ב-trapezoid rule. לחישוב השטח מתחת לעקומה 4/(1+x^2) בקטע [0,1]. לשם כך, מחולק הקטע ל-num_subintervals מקטעים ברוחב 1/num_subintervals.
* האלגוריתם מחשב את שטחו של כל מקטע, כאשר גובה המקטע מתייחס לנקודת המפגש של האנך היוצא מאמצע המקטע והעקומה. סכום שטחי המקטעים הוא, בקירוב טוב, השטח שמתחת לעקומה.
* ככל שמספר המקטעים רב יותר, השטח מדויק יותר, ולכן גם הערך של π מדויק יותר. הפיתוח המתמטי הבא יבהיר את הקשר בין חישוב האינטגרל לערך π:
<math>\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</math>

<syntaxhighlight lang="LanguageName">
#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;
}
</syntaxhighlight>

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