חישוב CPE

[white shadow 3]

חישוב CPE

הי.
משהו שלא סגור לי עד הסוף ולא כ"כ מצאתי איפה בספר הלימוד הנושא הזה נכנס...

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

for (i=0; i<array_size; ++i) {
   x+=A[i];
   y+=A[i];
}

אז לפי הבנתי, ממה שהיה כתוב, חיבור CPE של הקטע הזה (לא כל התוכנית) במקרה הזה הוא שצריך להסתכל על "מרווח הזמן" שעבר בין 2 איטרציות (נניח ואני מצייר לי 3-4 איטרציות עוקבות), ואת זה לחלק במספר האלמנטים ש"טיפלתי בהם" (לדוגמא, חיברתי) בטווח הזמן הזה

בתרשים שלי שמתי את 2 פעולות ה-add באותה יחידת זמן, שכן אפשר לחשב את x ואת y ביחד באותו הזמן, שכן תוצאה של האחד אינה תלויה בתוצאה של השניה ולכן צריך "לחכות" לו וקיבלתי תמונת מצב שבה יש לי 1 מחזורי שעון בין כל 2 איטרציות עוקבות....אז ה-CPE יוצא לי 1/2? זאת נשמעת לי תוצאה לא כ"כ הגיונית

תודה!

 

[white shadow 3]

בהמשך לזה..מצורפת תמונה

נתחיל משאלת בסיסית יותר:
האם המצב המתואר בצד שמאל הוא אפשרי (2 add-ים במקביל) או שאין כזה דבר וזה נעשה כמו בצד ימין?

 

[BravoMan]

לחלק במספר אלמנטים?

אני לא בטוח אם שנינו מתכוונים לאותו דבר כשאנו כותבים CPE, אבל אם כן, תמצא תשובה מפורטת וטובה כאן:
http://stackoverflow.com/questions/10419316/how-to-determine-cpe-cycles-per-element
&nbsp
ספציפית: חיבור של 2 int ואפילו יותר במקביל, בטיק אחד בהחלט אפשרי.
זה נקרא SIMD וקיים זמן רב.
https://en.wikipedia.org/wiki/SIMD

 

[Javali]

אפשרי מאוד

מה שאתה מתאר בצד שמאל יכול לקרות וגם קורה.

מעבדי אינטל מבצעים בין 3 ל-4 פעולות חיבור במקביל. (תלוי במודל.) ראה נספח C במדריך לאופטימיזציה שלהם

 

[white shadow 3]

מה שהראו לנו זה

שאם אני נניח מצייר כמה איטרציות עוקבות, כמו בתמונה, ואם המרווח בין איטרציות (מבחינת מחזורי שעון) הוא קבוע אז ניתן להסתכל על זמן אחד בין איטרציות, לראות כמה אלמנטים חושבו בו ואז לקחת את הזמן ולחלק במספר האלנטים, כלומר אם במחזור שעון אחד חישבתי 2 אלמנטים אז ה-CPE של הלולאה יהיה 1/2

מצד שני אני (חושב ש) יכול להגיד שאני רוצה למדוד "זמן ממוצע" ל-3 איטרציות עוקבות, ואז סה"כ מההתחלה עד הסוף עברו 6 מחזורי שעון, בהם חישבתי 6 אלמנטים, אז זה יוצא 1

מצד שלישי אני יכול להגיד שבכל 5 מחזורי שעון מחושבים 4 איברים ואז יותא 1.25

מצד רביעי - אני מניח שאין משמעות מיוחדת למספר "3" (באיטרציות), כך שהייתי יכול לצייר גם 4,5,...,700 איטרציות עוקבות והייתי יכול לקבל תוצאות שונות לחישובים האלה..

ובגדול, שורה תחתונה - אני לא כ"כ מבין מה דרך החישוב המקובלת לעניין הזה כאשר מבקשים לצייר "X איטרציות עוקבות ולחפש את ה-CPE של התוכנית" (הנתונה למעלה, עם ה-sum הזה שמתבצע עבור x ועבור y..)

 

[Javali]

מצטער

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

 

[selalerer]

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

גם זה כמובן, רק את העבודה עם המעבד בלי שום קשר ל-cache misses, שלא לדבר על IO ממש.
&nbsp
נראה לי לא שווה את המאמץ

 

[Javali]

שווה זה תלוי למי

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