חישוב מקבילי ומבוזר/ארכיטקטורות מקביליות

רשתות קישוריות (Interconnection networks)

שימושים של רשתות קישוריות

• חיבור מעבדים לזיכרון משותף
• חיבור מעבדים זה לזה

סוגי מדיה של קישוריות

• מדיום משותף (Shared medium)
• מדיום מועבר (Switched medium)

מדיה משותפת לעומת מועברת

• With shared medium, one message is sent & all processors listen
• With switched medium, multiple messages are possible.

מדיה משותפת

• מאפשר שליחת הודעות רק בזמן.
• הודעות משודרות לכול.
• כל מעבד "מקשיב" לכל הודעה.
• התנגשויות דורשות שליחה חוזרת של בהודעות.
• האת'רנט הוא דוגמא.

מדיה מועברת

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

טופולוגיות רשת מעברתית (Switch Network Topologies)

• צופה על הרשת המעברתית (switched network) כגרף.
• קודקודים = מעבדים (processors) או מתגים (switches).
• קשתות = נתיבי תקשורת (communication paths).
• שני סוגים של טופולוגיות: ישיר (Direct), עקיף (Indirect).

מספר המתגים (Number of switches)

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

שני סוגים של טופולוגיות

טופולוגיה ישירה (Direct Topology)

• היחס בין צמתי המתג (switch) לצמתי המעבד (processor) הוא 1:1.
• כל צומת מתג (switch) מחוברת ל: צומת מעבד 1, לפחות צומת מתג אחר 1.

טופולוגיה עקיפה (Indirect Topology)

• היחס בין צמתי מתג (switch) לצמתי מעבד (processor) הוא מעל 1:1.

מונחים להערכה – טופולוגיות העברה (Switch Topologies)

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

המספר המינימאלי של קשתות בין צמתי מתג שיש להסירן על מנת לחלק את הרשת לשני חצאים.

• • • רוחב חצייה גבוה הוא רצוי.
    • באלגוריתמים הדורשים כמויות גדולות של תנועת נתונים, הגודל של הנתונים מחולק ברוחב החצייה ומעמיד חסם תחתון על המורכבות של אלגוריתם.
    • למעשה צריך להוכיח מה הוא רוחב החצייה של רשת, וזו יכול להיות חישוב די קשה.
  • קשתות פר צומת (edges per node)
    • זה הכי טוב אם המספר המרבי של קשת\צומת יהיה מספר קבוע ועצמאי של גודל הרשת, וזה יאפשר ארגון של המעבדים ושינוי למספר גדול יותר של מצתים.
    • דרגה (Degree) היא המספר המרבי של קשתות פר צומת.
    • אורך קשת קבועה?
    • למדרגיות, זה יהיה כי טוב אם הצמתים והקשתות יוכלו להוביל למרחב תלת מימדי.
  • אורך הקשת קבועה (constant edge length)
• אנחנו מגדירים את המאפיינים האלה על מנת לראות כיצד הם משפיעים על בחירת אלגוריתם.
• אז נוכל לחקור מספר טופולוגיות שונות ולראות כיצד מאפיינים אלה מוערכים.
• מספר מתגים פשוט חבורים למתגים אחרים.

הערכת טופולוגיות העברה (Evaluating Switch Topologies)

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

• קוטר (Diameter)
• רוחב חצייה (Bisection width)
• מספר הקשתות/צומת - החיבוריות (Number of edges/node)
• אורך קשת קבועה (Constant edge length)

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

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

טופולוגיה טבעתית וטופולוגיה בעלת חיבוריות מלאה

• הטופלוגיה הטבעתית, היא טופלוגיה מינימלית, יש לה ערוץ תיקשורת אחד, הטבעת. זו טופולוגיה זולה ופשוטה לבנייה: יכולת השדרוג שלה הוא לינארי, יכולת השרידות נמוכה (דרגת החיבוריות 2), הרוחב פס מוגבל והוא 2 (משום שאת החתך המפצל את הצמתים לשתי קבוצות שוות בערך חוצות שתי קשתות), הקוטר הוא די ארוך n/2 ומספר המתגים הנחוץ הוא n.
• הטופלוגיה מסוג חיבוריות מלאה, היא טופלוגיה מקסימלית, כול צומת מחוברת לכל צומת אחרת באופן ישיר. מספר הקשתות הוא רב, ${\frac {n(n-1)}{2}}$, וכך גם מספר המתגים, $n^{2}$. טופולוגיה זו היא מאוד יקרה ומסובכת לבנייה. ולכן, לא נעשה בה שימוש במערכות מקביליות. היא מוצגת כאן בעיקר לצורך השוואה לטופולוגיות האחרות.

רשת Mesh דו-מימדית

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

הערכת ביצועי 2D Mesh

מניחים שהרשת היא ריבוע n = number of processes

• קוטר (Diameter): $\Theta (2(n^{\frac {1}{2}}-1))$: המרחק הגדול ביותר בין שני צמתי מתג.
• רוחב חצייה (Bisection width): $\Theta (n^{\frac {1}{2}})$: המספר המינימאלי של קשתות בין צמתי מתג שיש להסירן על מנת לחלק את הרשת לשני חצאים
• מספר הקשתות פר מתג: 4 (הדרגה של הצומת, ראו שרטוט)
• אורך הקשת קבועה? כן

2D Meshes

• שתי טופולוגיות רשת להן מבנה גיאומטרי של סריג דו ממדי.
• הטופולוגיה המתוארת מימין קרויה טורוס (Torus) והיא הרחבה של הטופולוגיה הסטנדרטית המתוארת משמאל.
• ההרחבה נעשית על ידי הוספת - קשתות המחברות בין הצמתים המנוגדים המצויים על גבולות הסריג.
• הרחבה זו משפרת את הרוחב פס ואת הקוטר פי שניים בערך הרוחב פס גדל מ-${\sqrt {n}}$ ל-$2{\sqrt {n}}$ והקוטר קטן מ-$2{\sqrt {n-1}}$ ל-${\sqrt {n}}$.
• בשתי הטופולוגיות מספר המתגים זהה, וערכו שווה למספר הצמתים, n. החיבוריות ברמת הצומת היא 2 עבור הסריג הסטנדרטי, ו-4 במקרה של הטורוס.
• מאפיין נוסף ובולט של טופולוגית הסריג הדו ממדי הוא הצורך לשמר את - הגיאומטריה הריבועית בעת שדרוג.

רשת עץ בינארי (Network Tree Binary)

• טופולוגיה עקיפה (Indirect topology)
• $n=2^{d}$ processor nodes, $2n-1$ switches
• where d = 0, 1, ... is the number of levels

i.e. $2^{3}=8$ processors on bottom and 2(n) – 1 = 2(8) – 1 = 15 switches

הערכת רשת עץ בינארי

• קוטר - המרחק הגדול ביותר בין שני צמתי מתג: $2\log {n}$.
• רוחב חצייה - המספר המינימאלי של קשתות בין צמתי מתג שיש להסירן על מנת לחלק את הרשת לשני חצאים: 1
• מספר הקשתות/צומת: 3
• אורך קשת קבוע? לא

• בטופולוגית עץ הצמתים כולם נמצאים בעלי העץ, והמתגים שמספרם כפול ממספר הצמתים משרים מבנה של עץ.
• על-מנת לשדרג רשת מבוססת טופולוגית עץ יש צורך להכפיל את מספר הצמתים.
• הרוחב פס הוא גרוע וערכו הוא 1 .הדבר נובע מכך ששורש העץ מהווה צוואר בקבוק בכל מה שקשור לתעבורה בין שני חלקי העץ. בנוסף לכך, שורש העץ מהווה נקודת תורפה בכל מה שנוגע לשרידות של הטופולוגיה. אם צומת השורש יוצא מכלל פעולה, שני חצאי העץ לא יכולים לתקשר ביניהם.
• לעומת זאת, הקוטר של טופולוגית עץ הוא מצוין, וערכו הוא: $2\log {n}$.

רשת על-עצית (Hypertree Network)

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

(a) מן "החזית" נראה כמו עץ k-ary של הגובה d (לדוגמא 4-ary tree of height 2) (b) מן "הצד" נראה כמו עץ בינארי במהופך בגובה d (c) רשת מלאה

הערכת 4-ary Hypertree

• A 4-ary hypertree has $n=4^{d}$ processors
• General formula for k-ary hypertree is $n=k^{d}$
• קוטר: $2\log {n}$
• רוחב חצייה: $2^{d+1}$, לדוגמא $2^{d+1}=2^{3}=8$
• מספר קצוות / צומת: 6
• אורך קצה קבוע? לא

רשת מסוג Crossbar ו-butterfly

• שתי טופולוגיות רשת שייעודם אינו מסתכם רק ביצירת תקשורת בין צמתים ברשת, אלא הן גם מאפשרות תקשורת בין הליבות לזיכרון משותף.
• טופולוגית הרשת crossbar היא טופולוגיה מאוד נפוצה במערכות מקביליות המונות עשרות אחדות של ליבות. טופולוגיה זו מאפשרת למתג באופן ישיר בין כל זוג צמתים. בנוסף לכך, הרוחב פס שלה הוא מעולה וערכו n, ואילו הקוטר הוא מיטבי. אולם לגמישות הזו יש מחיר בדמות $n^{2}$ מתגים הנדרשים לשם כך.
• טופולוגית רשת butterfly היא רשת ניתוב מהירה ופשוטה. הרוחב פס שהיא מציעה הוא רחב וערכו 2/n, ואילו הקוטר קצר וערכו $\log {n}$. עלות כל היתרונות מסתכמת במספר לא מבוטל של מתגים הדרושים לשם כך, $n(\log {n}+1)$, בנוסף לעלות שדרוג גבוהה המחייבת את הכפלת מספר הצמתים.

רשת "פרפרים"(Butterfly Network)

• טופולוגיה עקיפה
• $n=2^{d}$ processor nodes connected by $n(\log {n}+1)$ switching nodes

A $2^{3}=8$ processor butterfly network with 8*4=32 switching nodes

ביבליוגרפיה

• Selim Akl, The Design and Analysis of Parallel Algorithms, Prentice Hall, 1989 (earlier textbook).
• G. C. Fox, What Have We Learnt from Using Real Parallel Machines to Solve Real Problems? Technical Report C3P-522, Cal Tech, December 1989. (Included in part in more recent books co-authored by Fox.)
• A. Grama, A. Gupta, G. Karypis, V. Kumar, Introduction to Parallel Computing, Second Edition, 2003 (first edition 1994), Addison Wesley.
• Harry Jordan, Gita Alaghband, Fundamentals of Parallel Processing: Algorithms, Architectures, Languages, Prentice Hall, 2003, Ch 1, 3-5.
• F. Thomson Leighton; Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes; 1992; Morgan Kaufmann Publishers.
• Gregory Pfsiter, In Search of Clusters: The ongoing Battle in Lowly Parallelism, 2 nd Edition, Ch 2. (Discusses details of some serious problems that MIMDs incur).
• Michael Quinn, Parallel Programming in C with MPI and OpenMP, McGraw Hill,2004 (Current Textbook), Chapter 2.
• Michael Quinn, Parallel Computing: Theory and Practice, McGraw Hill, 1994, Ch. 1,2
• Sayed H. Roosta, “Parallel Processing & Parallel Algorithms: Theory and Computation” , Springer Verlag, 2000, Chpt 1.
• Wilkinson & Allen, Parallel Programming: Techniques and Applications, Prentice Hall, 2 nd Edition, 2005, Ch 1-2.