דף הבית > תכנות > Parallels and Internals Shminternals

Parallels and Internals Shminternals

הלכתי לאחרונה למפגש במיקרוסופט רעננה בנושא Parallel Programming in Visual Studio 2010. המרצה היה סשה גולדשטיין. אז קודם כל קצת מחמאות: למיקרוסופט על האירועים האלה שמאורגנים היטב, מהחניה ועד המשובים; לסשה גולדשטיין על הרצאה ברמה גבוהה, בשפה ברורה ועם הרבה סבלנות.

ועכשיו לעניינים הטכניים עצמם.

נעים להכיר – System.Threading.Tasks

נתחיל מהקדמונת: החל מגירסה 4.0 של הדוט נט פריימוורק, מיקרוסופט הכניסו פנימה פיצ'רים חדשים בתחום ה Multi-Threading. הפיצ'רים האלה מאפשרים פיתוח נוח יותר ל Multi-Threading, ולמעשה כדאי יותר לקרוא לזה מיקבול משימות, מתוך הנחת יסוד שמשימה ו Thread זה לא אותו הדבר, למרות שיש קשר הדוק. את הפיצ'רים והמחלקות למיניהם אפשר למצוא ב namespace שנקרא System.Threading.Tasks. הרעיון הכללי של הפיצ'רים האלה הוא שהמפתחים לא יטריחו את עצמם יותר מדי סביב הפרטים הקטנים של המיקבול עצמו, ויוכלו למקבל משימות בקלות יחסית.

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

namespace Bronze.Lib
{
  public class SimpleAggregator
  {
    public int Sum(int[,] matrix)
    {
      var result = 0;
      for (var i = 0; i < matrix.GetLength(0); i++)
        for (var j = 0; j < matrix.GetLength(1); j++)
          result += matrix[i, j];
      return result;
    }
  }
}

פשוט וקל.

מקבילית המוחות

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

עכשיו, יש שתי גישות עיקריות לביצוע של הפתרון הזה:

1

מגדירים משתנה מספרי משותף, נניח sum, ומאתחלים אותו ל 0 (אפס). כל משימה תסכום את השורה שלה במטריצה, ותעדכן את ה sum הנ"ל לפי הסכום של השורה. התוצאה הסופית, אחרי שכל המשימות הסתיימו, תהיה ב sum.

הנה קצת פסודו-קוד לעניין זה:

1. common_sum = 0
2. Parallel: for each row in matrix:
  2.1 temp = sum(row)
  2.2 append temp to common_sum

הנקודה הכואבת יחסית בקוד הזה היא סעיף 2.2, שבו כל משימה מעדכנת את המשאב המשותף. מכיוון שזו סביבה של ריבוי משימות וככל הנראה גם ריבוי threads, הרי שיש לנו משאב משותף שיכול להתעדכן ע"י מספר threads במקביל. מקור לא אכזב ל data corruption. כדי להתגבר על זה, צריך לכתוב קוד של פעולת העדכון בצורה שתהיה thread-safe. ניתן להשיג את זה ע"י lock, ובמקרה הספציפי הזה, נוכל להשתמש גם ב Interlocked שיכול בפעולה אטומית להוסיף ערך למשתנה int.

בואו נראה את הקוד שמבצע את הגישה הראשונה, עם Interlocked:

using System.Threading;
using System.Threading.Tasks;

namespace Bronze.Lib
{
  public class ParallelWithInterlock
  {
    public int Sum(int[,] matrix)
    {
      var outerUpperBound = matrix.GetLength(0);
      var commonSum = 0;

      var innerUpperBound = matrix.GetLength(1);
      Parallel.For(0, outerUpperBound, i =>
      {
        var localSum = 0;
        for (var j = 0; j < innerUpperBound; j++)
          localSum += matrix[i, j];
        Interlocked.Add(ref commonSum, localSum);
      });

      return commonSum;
    }
  }
}

2

במקום להגדיר משתנה משותף ולהגן עליו באמצעי סנכרון שונים, נוכל להגדיר מערך שבו לכל משימה מוקצה תא משלה. הגישה לאיברי המערך היא thread-safe לפי הגדרה (אגב, יצא לי לחפור על זה פעם ב stackoverflow), ולכן כל משימה יכולה לעדכן את התא "שלה" במערך הנ"ל, מבלי לחשוש מ data corruption. בסוף התהליך סוכמים את כל איברי המערך, ובא לציון גואל. שימו לב, עיקר התחכום כאן הוא שהפקודה Parallel.For יוצרת משתנה אינדקס, ושולחת אותו כפרמטר ל delegate של המשימה המבצעת, וזה בדיוק האינדקס של התא ה"פרטי" של המשימה במערך המשותף. הנה הקוד שממחיש את זה:

using System.Linq;
using System.Threading.Tasks;

namespace Bronze.Lib
{
  public class ParallelAggregator
  {
    public int Sum(int[,] matrix)
    {
      var outerUpperBound = matrix.GetLength(0);
      var partialSums = new int[outerUpperBound];

      var innerUpperBound = matrix.GetLength(1);
      Parallel.For(0, outerUpperBound, i =>
      {
        partialSums[i] = 0;
        for (var j = 0; j < innerUpperBound; j++)
          partialSums[i] += matrix[i, j];
      });

      var result = partialSums.Sum();
      return result;
    }
  }
}

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

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

using System.Linq;
using System.Threading.Tasks;

namespace Bronze.Lib
{
  public class ParallelAggregatorWithLocalSum
  {
    public int Sum(int[,] matrix)
    {
      var outerUpperBound = matrix.GetLength(0);
      var partialSums = new int[outerUpperBound];

      var innerUpperBound = matrix.GetLength(1);
      Parallel.For(0, outerUpperBound, i =>
      {
        var localSum = 0;
        for (var j = 0; j < innerUpperBound; j++)
          localSum += matrix[i, j];
        partialSums[i] = localSum;
      });

      var result = partialSums.Sum();
      return result;
    }
  }
}

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

של מי ארוך יותר?

כתבתי תוכנית קטנה שמשווה את הביצועים, ויש יתרון מובהק בביצועים של ParallelAggregatorWithLocalSum (בוצע ב Release על הלפטופ שלי). היתרון אצלי במחשב הוא של 40%, כלומר המחלקה ParallelAggregatorWithLocalSum רצה ב 40% בממוצע מהר יותר מהמחלקה ParallelAggregator. לא יאמן. באותה תוכנית ניתן גם לראות שהביצועים של ParallelAggregatorWithLocalSum ושל ParallelWithInterlock ממש קרובים אחד לשני (לפעמים האחד מהיר יותר באחוז או שניים ולפעמים השני). את הקוד המלא אפשר להוריד מכאן. הנה גרף שממחיש את התוצאות של סכימת מטריצה עם 99 שורות ו 31841 עמודות:

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

סיכום ומסקנות

קודם כל, ה Parallel שמגיע עם דוט נט 4.0 מציע דרך נוחה יחסית למיקבול, ויש לו מספר יתרונות משלו כך שינצל בצורה טובה כל חומרה שהיא. כלומר, לא צריך לדאוג לגבי כמה ת'רדים באמת לפתוח כדי למקבל משימות – צריך רק לחשוב לוגית על פירוק למשימות, והמימוש של ה Parallel כבר ידאג למיקבול בפועל, תוך התייחסות לחומרה הנתונה. החזון הוא שלא נצטרך לשנות קוד ו/או קונפיגורציה כאשר אנחנו מריצים את הקוד הממוקבל שלנו בסביבת חומרה שונה (בין אם זו חומרה חזקה יותר ובין אם חלשה יותר).

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

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

ומסקנה נוספת: כל מי שחשב שדוט נט זו סביבה שבה אין צורך לדעת את ה internals – צודק רק ברוב המקרים. בחלק קטן (אבל משמעותי) מהמקרים כדאי מאוד לדעת מה קורה under-the-hood, רק כדי להפיק יותר מהסביבה הזו. יש עוד הרבה דוגמאות שממחישות כמה טוב לדעת את ה internals, והפוסט הזה מציג רק דוגמה אחת, כמובן. עם זאת, התחושה האישית שלי היא שבמיקרוסופט ניסו לכוון לשפה שהיא יותר high-level ממה שהתקבל בסופו של דבר. במילים אחרות, הציפיה של המפתחים שרק מגיעים לדוט נט היא שהם לא יצטרכו להתעסק עם tweakים כדי לכתוב קוד יעיל, ובסוף הם נאלצים להיכנס לפינות שהם לא חלמו עליהם, ושמרחיקות אותם מכתיבת קוד "נטו".
במילים פשוטות ובוטות יותר: פייר, התאכזבתי 🙂

כל הקוד בפוסט הזה ניתן להורדה מכאן.

מיקבול נעים!

קטגוריות:תכנות תגיות:, ,
  1. שי
    25 אוקטובר, 2010 מתוך 07:35 | #1

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

    שאלה בנושא: יש לי כרגע בעבודה SERVICE שעובר בלולאה על List עם חצי מיליון שורות ומייצר קובץ XML פיזי גדול מאוד, אני בונה את זה בעזרת XDocument.
    ניסיתי להחליף את ה-for הרגיל ב- Parallel.For וזה גרם לכך שהסדר של ה NODES בXML נהרס והסדר במקרה זה הוא כן קריטי, האם ניתן לפתור את זה?

  2. 25 אוקטובר, 2010 מתוך 09:24 | #2

    הבעיה שאתה מתאר בעדכון "איברים סמוכים במערך" נקראת False Sharing.
    הרעיון הוא שלמרות ש"נראה לנו" ששני איברים סמוכים במערך הם לוקאלים עבור כל ת'רד, ואין שיתוף ביניהם, בפועל זהו לא המצב מאחר וקיים סיכוי טוב שהם יושבים על אותו Cache Line (עבור מעבדי אינטל, בד"כ מדובר ב-64 בתים).
    בכל פעם שמעבד כותב למשתנה "הלוקאלי" שלו, הוא למעשה גורם ל-Invalidation של אותה שורה ב-Cache של המעבדים האחרים, מה שיגרום למעבד השני לסבול מ-Cache Miss.
    כך שבפועל, אפשר להבין שקיימת כאן פגיעה קשה בלוקאליות של הנתונים. אמנם קיימת לוקאליות "לוגית" של השדות, כשמסתכלים על איך אותם נתונים יושבים על החומרה, מבינים את האמת הכואבת.
    חיפוש קטן על הנושא יניב לא מעט תוצאות

  3. 25 אוקטובר, 2010 מתוך 09:31 | #3

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

    ארנון

  4. 25 אוקטובר, 2010 מתוך 15:24 | #4

    @שי
    אולי תוכל לבנות קודם Nodes ולהצמיד לכל Node את האינדקס שלו, ואח"כ תמיין ותמיר את זה ל XML שלם?

  5. 25 אוקטובר, 2010 מתוך 20:49 | #5

    @ארנון,
    הנקודה היא דווקא שיש כאן עניין עם internals שקשורים למקבול כלשהו (בין אם ב Parallels ובין אם בניהול ת'רדים ידני), ושצריך להכיר אותם.
    זה יכול לקרות גם בלי קשר לאבסטרקציה של המיקבול. וגם לא באופן בלעדי למערכים, כפי שמוצג בדוגמת הקוד בויקיפדיה.
    ולגבי WCF, באמת יש שם לא מעט צרות עם האבסטרקציה הזו של MS…

  6. 27 אוקטובר, 2010 מתוך 10:58 | #6

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

  1. אין הפניות עדיין.

Quantcast