Computer System Cache Memory

כבר דיברנו על ה memory gap כלומר שיש פער בין מהירות הזכרונות והוא ימשיך להשאר בזמן הקרוב. כמו כן גם מבחינת עלות הרבה יותר קשה להביא את הזכרונות שמחוץ ל cpu לרמה של ה cpu.


נשאלת השאלה כיצד נבנה זכרון שהוא יחסית מהיר וזול.

Principle of Locality

התכונה של מקומיות אומרת שלתוכניות יש נטייה להשתמש שוב ושוב באותן הכתובות ל data ובאותן הכתובות לנתונים.
המשמעות של אותן הכתובות מתחלקת ל 2 :

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

מקומיות במרחב:
אם אני ניגש לכתובת מסויימת בזכרון אז סביר להניח שבזמן קצר אגש לכתובות סמוכות.

דוגמה קלאסית היא

sum = 0;
for (i = 0; i < n; i++) 
	sum += a[i];
return sum;

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

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

האם לקוד הבא יש לוקליות טובה?

int sumarray(int a[M][M]) 
{
	int i,j,sum=0;
	for(j=0 ; j < M ; j++) 
		for (i=0 ; i<M; i++)
			sum+= a[i][j];
	return sum;
}

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

התיקון אם כן הוא להחליף את סדר הלולאות

int sumarray(int a[M][M]) 
{
	int i,j,sum=0;
	for(i=0 ; i < M ; i++) 
		for (j=0 ; j<M; j++)
			sum+= a[i][j];
	return sum;
}

caching and memory hierarchies

הרעיון הוא שבהינתן שתכונה של לוקליות נשמרת וקיימת אזי אותו מנגנון של הירכיית זכרון יעבוד יותר טוב בשבלנו.
זה מנגנון שפועל גם בתוכנה וגם בחומרה והוא נובע בין היתר בגלל הmemory gap , ככל שנבנה טכנולוגיות מהירות יותר אנחנו נשלם יותר עבור יחידת זכרון וגם בפרט יש לטכנולוגיות כאלה פחות קיבולת.

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

באמצעות המנגנון הזה נוכל לקבל את ההירכייה הבאה

caches

המטמון הוא זכרון קטן ומהיר שמשמש בתחנת ביניים של חלקי מידע ברכיבי זכרון כבדים יותר.
מהגרף למעלה אנחנו מסיקים שהרמה ה$k$ היא מנגנון cache לרמה ה$k+1$ . בגלל זה ב מבנה התוכנית באסמבלי הסברנו שהרבה יותר מהר לרשום ל register ולקרוא מ register מאשר לכתוב למחסנית כי בסוף נעשה שימוש גבוה במנגנון ה cache הנ״ל.

התוצר הסופי היא בריכת זכרון ״זול״ אבל שמחזיק מידע ממקום של זכרון ״יקר״

מה שיקרה זה שהרמה ה$k-1$ תקבל את הערך של הכתובת $8$ הרבה יותר מהר מאשר כתובת כמו $10$. חשוב לציין שהמידע מועתק מהרמה הk+1 לרמה הk הם לא מחוברים אחד לשני.

השאלה היא איך שומרים את המידע בcache בצורה נכונה ואיך המידע מועתק...
באופן מופשט אם נבקש למשל את הכתובת $4$ אז הרמה הk תפנה לרמה ה $k+1$ ותעתיק אותה לרמה ה$k$ ואם אין מקום תחליף את אחד הכתובות השמורות בכתובת $4$ .

general caching concepts

נניח שהתוכנית צריכה אובייקט $d$ שנמצא בבלוק זכרון כלשהו $b$ . הסיבה שמדברים בבלוקים היא שהcache מביא גם כתובות סמוכות ולא רק כתובת בודדת כלומר בלוק של כתובות וכך גם יש שמירה של חסכון במרחב בנוסף לחסכון בזמן.

בלוק מסומן עם * ובמקרה של התמונה למעלה הוא בעצם מסמל את הכתובות שבאותה שורה עם 4 כלומר $4,5,6,7$

מספר מונחים כלליים שנרצה להגדיר
cache hit - התוכנית מוצאת את $b$ ברמה ה$k$ של המטמון.
cache miss - $b$ לא נמצא ברמה ה$k$ של המטמון ולכן ה $k-cache$ חייב לייבא את זה מהרמה ה$k+1$ .

נשים לב שאם הרמה ה$k$ מלאה אז צריך להחליף בלוק כלשהו קיים באחד חדש שהרגע משכנו, מי זה יהיה? לכך יש שתי policies:
א) placement policy - איפה נשים את הבלוק החדש? $b\text{ mod }4$
ב) replacement policy - איזה מהבלוקים נוריד במצב שבו אין מקום? LRU = least recently used

types of cache miss

א) cold miss - כאשר ה cache לא נטען בנתונים ואין בו כתובת בכלל (למידע שנמצא בכתובת אין משמעות) , מצב זה קורה למשל כשהמחשב נדלק. מנגנון ה cache מטפל בזה באמצעות flag שקובע האם המידע ולידי או לא.
ב) conflict miss - מצב שבו המקום שנרצה למקם את הבלוק שלנו מאוכלס על ידי מידע אחר. נשים לב שהמיקום הוא לפי ה placement policy. כלומר הקונפליקט בא לידי ביטוי לא בגלל שאין מקום ברמה ה$k$ אלא בגלל שהplacement policy ממקם באותו הבלוק, שהוא תפוס.
ג) capacity miss - מצב שבוא אין מקום ברמה הk למקם בלוק חדש. הרמה ה$k$ תפוסה לגמרי.

המטרה שלנו היא כמה שפחות misses במהלך כתיבת הקוד

זכרונות המטמון בחומרה

זכרונות אלו מבוססי SRAM ומנוהלים אוטומטי על ידי החומרה.

Hardware Memory Management

נרצה להבין איך הדבר בא לידי ביטוי בחומרה.
כל רמה ב cache בחומרה מחולקת לsets שבכל set יש שורות , ובכל שורה יש metadata על המידע ואת המידע עצמו.

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

Addressing caches

בהינתן כתובת $A$ נרצה להבין את המנגנון של ה cache לחלוקת הכתובת על מנת למצוא אותה במקום המתאים ב cache.
החלוקה על הכתובת תיראה ככה

הword בכתובת $A$ תהיה ב cache אם הtag הנ״ל שווה לtag בset המתאים לפי הביטים האמצעיים. הb bits הימנים קובעים היכן המילה עצמה מתחילה בזכרון המטמון מתחילת הבלוק של המידע כלומר בלי לספור את הvalid וה tag.
שאלה מתבקשת היא למה ה s bits נמצאים באמצע...
נשים לב שספר הסטים הוא $2^s$ בידיוק מהסיבה ש s ביטים אמצעיים צריכים לקבוע את מספר הset ולכן יש $2^s$ ערכים אפשריים לדבר.

המסקנה הישירה מזה היא שאותה הכתובת תמיד תגיע לאותו המקום, שיטה זאת נקראת direct mapping .

Direct-Mapped Cache

שיטת מטמון הפשוטה ביותר , מוגדרת כשורה אחת ל set.

כעת בהינתן כתובת מסויימת $A$ , נשתמש ב s bits בחלוקה כדי ללכת ל set הנכון. כעת נשתמש ב t-bits כדי לבצע line matching כלומר האם בשורה שאנחנו נמצאים עליה נמצא הtag המתאים שנמצא בכתובת (במקרה הזה יש רק שורה אחת).
במידה והביטים בtag הם נכונים אז הכתובת לפי ה b-bits מתאימה ונוכל להשתמש בה (כמובן במידה וה valid ביט דולק).

נשים לב שהדוגמה כאן היא offset של 4 ביטים, אבל הקריאה היא ביחס ל word כלומר הoffset ייתן לנו את הבייט הראשון מבין מספר הבייטים שמייצגים word בחומרה שלנו. בעצם offset של 4 ביטים מאפשר $2^4=32$ ערכים עבור הoffset ב bytes. כלומר יש לנו ב 32 בייטים בdata שזה בעצם 8 words בהנחה ש word הוא 4 בייטים (יכול להיות גם 2 בייטים למשל בx86).

כמו כן הסיבה שיש בכלל את byte offset היא שיכול להיות באותה שורה מספר words שונים מכתובות סמוכים בשביל המקומיות במרחב.

נסתכל על הדוגמה הבאה :
עבור $C=8$ כלומר גודל הcache הוא 8 בייטים עם החלוקה הבאה $B=2,S=4,E=1$ , כלומר: 2 בייטים בdata בשורה, 4 סטים ושורה אחת בכל סט.
כאשר המחשב דלוק והcache ריק המטמון ייראה ככה:

כעת נרצה להכניס את הכתובות הבאות

כלומר כתובות של 4 ביטים. נגדיר שהחלוקה היא

המשמעות היא שכל כתובת תחולק באופן כזה שנוכל לקבל את כל המיפוי המתאים ב״טבלה״ למעלה. למשל $s=2$ בגלל שיש 4 sets ולכן הערכים האפשריים הם $00,01,10,11$. כמו כן $b$ יקבע איזה word אנחנו מחפשים ב data מבין שתי הword שיכולים להכנס בבלוק אחד של מידע, זה בגלל שיש שתי ערכים אפשריים שקובעים את ה offset .
נשים לב שמספר הכתובות שניתן לכסות בארבעה ביטים הם 16 ולכן בוודאות לא נוכל לכסות את כל הכתובות האלה ברמה הזאת של הcache
נסמן את הכתובות האפשריות כ $M=16$ .

נתחיל מלהכניס את $0$ , כמובן שנקבל cold miss כי הכל נקי, לכן נביא אותו מהרמה מתחת ומהחלוקה של 0 נקבל

נשים לב שיש גם את $M[0],M[1]$ בגלל הלוקליות במרחב ובקריאה ל $0001$ נקבל cache hit ישר.
כעת בקריאה של 13 נקבל cold miss גם כן ויתקיים

גם כאן הבאנו את הכתובת לידו, כי הייתה אפשרות להביא כיוון שבdata יש שתי בלוקים. נשים לב שכל הבלוקים עולים כמסה אחת ואנחנו יודעים איך לגשת בגלל החלוקה של כתובת הזכרון.
כעת כשנוסיף את 8 נקבל conflict miss, כי הset שלה הוא 00 ולמרות שיש 2 שורות ריקות הplacement policy דורש ש8 יהיה בשורה הזאת (לפי ה tag) נקבל miss. במקרה של direct mapping נקבל דריסה של הערכים בסט הראשון.

נשים לב לחסרון משמעותי בשיטה הזאת, במצב שבו נקרא ל 0,8 שוב ושוב נקבל תמיד conflict miss ונשלם על זה בביצועים בגלל שיש רק שורה אחת אפשרית בdirect mapping.

לסיכום השלבים:

1.   Set selection – במצב זה המטמון מחלק את s (האינדקסים שמציינים את הסט). הוא מתייחס אליהם כunsigned שמתאים למספר של סט מסויים. כלומר נתייחס למטמון כמערך חד מימדע של סטים, כשהביטים של הסט מציינים את האינדקס במערך.

2.   Line Matching – כעת צריך להבין אם עותק של המילה נמצא בתוך אחת השורות בסט. בdirect-mapped cache, יש רק שורה אחת ולכן נבדוק את התג שלה ואת הvalid bit.
אם גם הvalid bit וגם הtag מתאים, אז יש hit. אחרת יש miss.

3.  Word extraction – מחולק ל-2, לפי hit או miss:
a.     אם יש hit, נבצע Word Selection – לפי הביטים של הblock offset נדע מה הבית הראשון במילה המבוקשת. שכן אנחנו כבר יודעים שהמידע נמצא במטמון. גם כאן נוכל להתייחס לבלוק כמערך של בתים, והביטים האלו הם האינדקס במערך.

b.  אם יש miss, נבצע Line Replacement – נצטרך לבקש את הבלוק המבוקש מהרמה הבאה בהיררכית הזיכרון ולשמור את הבלוק החדש באחת השורות בסט לפי הביטים של הסט. אם הסט מלא, נצטרך להחליף את אחת השורות. בdirect-mapped cache, יש רק שורה אחת ולכן נחליף אותה.

למה להשתמש ב ביטים האמצעיים כאינדקס?

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

• שאם היינו משתמשים בMSB וb-1 הביטים אחריו כביטים שקובעים את הset, היינו מקבלים miss ברוב המקרים כי תמיד היינו הולכים לset ה0 בקפיצות של כתובות שקרובות אחת לשנייה.

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

Set Associative Caches

מאופיין על ידי יותר משורה אחת ל set

יש צורך להשוות את ה tag בצורה קפדנית יותר, כדי לבדוק האם אכן כתובת נמצאת בset כלשהו או לא.
נשים לב שאין להתסכל על הבדיקה כלולאה כיוון שהבדיקה זאת נעשה ברמת החומרה במקביל
כעת ההשוואה מתבצע מול מספר שורות, נשאלת השאלה איזה מנגנון כדאי להשתמש כאשר tag איננו שווה לאף אחת מהשורות?
כמובן שהדבר שצריך לעשות בראש ובראשונה הוא לבדוק האם יש שורה שהvalid bit שלה כבוי ובמידה וכן מיד נמקם בשורה הזאת.
אם זה לא המצב, נשתמש בעקרון LRU, כיוון שזה ממומש ברמת החומרה והתכנון של הcache יש לתכנן פרט זה בקפידה אבל אין תשובה נכונה לאיך לממש את זה.

כעת נתאר את אותן הפעולות עבור מצב זה:

1.     Set selection – באותו אופן כמו בdirect-mapped cache, הביטי של הסט מייצגים את מספרו.

2.     Line matching and Word selection – לבצע מציאת שורה יותר קשה, מכיוון שזה מכריח לבדוק את התגים והvalid bits של מספר שורות כדי לגלות אם המילה נמצאת בסט.
לצורך ההסבר נגדיר זיכרון אסוציאטיבי – זיכרון שמורכב מזוגות של מפתח וערך (key, value pair). נתייחס לassociative cache בתור זיכרון אסוציאטיבי קטן כשהמפתחות הן שרשור של הביטים של התג והvalid bit והערכים הם התוכן של הבלוקים.
לכן בעצם נבצע חיפוש בזיכרון האסוציאטיבי אם קיים המפתח המבוקש, כלומר אם אחת מהשורות מתאימה גם בתג וגם בvalid bit. במידה וכן, לפי הblock offset נמצא את המילה המבוקשת בתוך השורה.

3.     Line Replacement – אם המילה המבוקשת לא נמצאת באחת מהשורות בסט, יש לנו כמובן cache miss. אם יש שורה פנויה בסט, את הבלוק מהרמה הבאה בהיררכית הזיכרון נטען לשורה הפנויה. אם אין שורות פנויות אז נצטרך להחליט איזו שורה לפנות וכאן יש מספר אופציות:
a. נבחר באופן רנדומלי
b. ניקח את הLeast Frequently Used – LFU, כלומר את השורה שניגשנו אליה הכי פחות פעמים בפרק זמן מסויים.
c. ניקח את ה LRU- כלומר השורה שניגשנו אליה הכי מזמן מבין השורות בסט.

לוקליות במרחב כאשר ה block size גדול מ1

כפי שאמרנו ה cache block בכל set בנוי באופן כזה שיהיה לו מקום ליותר מword אחד כל פעם. על מנת שנוכל להביא כתובות שקרובים יותר. נרצה שבלוק יוכל להכיל כמה שיותר words סמוכים.

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

write to cache

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

write-hit

נחלק את המצבים שבהם הצלחנו לכתוב ל 2:
א) write-through : אם כותבים למטמון ברמה ה k אז כל רמה כותבת לרמות מתחתיה את הערך החדש.
ב) write-back : הרמה שעליה נכתב הערך החדש לא תרד למטה עד שלא צריך להחליף את כל השורה של הזכרון. כלומר עד שהתקבל miss כלשהו. זה דורש מאיתנו להוסיף לכל שורה flag נוסף שנקרא dirty bit שקובע האם המידע בשורה שונה מהרמה שמתחתיה כדי לדעת האם יש צורך בעת החלפת שורה לשנות את הערך ברמה מתחת.

write miss

מצב זה יקרה כאשר נרצה לכתוב לכתובת שבכלל לא נמצאת ב cache.
א) write allocate : במצב של miss על cache נקרא קודם את הערך מהזכרון (נמשיך לחפש ברמות עד שנמצא את הכתובת) לcache ולאחר שנקרא אותו לרמה הזאת נשכתב עליו את הערך הדרוש ולא נעדכן למטה.

ב) no-write-allocate : המשכת תהליך הכתיבה למטה עד לרמה שבה זה נמצא. כלומר העברה תהליך הכתיבה במצב של miss לרמה מתחת והעברת האחריות אליה.

בחומרה הטיפוסים הנפוצים יותר הם -
write through + no-write-allocate
write-back + write allocate

Intel Pentium Cache Hierarchy

ניתן לראות שהם השתמשו ב set עם ארבע שורות עם write through עבור הdata ועל ה instruction בכל שורה.
למה יש הפרדה בין הכתובות לdata?
הכתובות של שניהם הם בתחומים שונים לגמרי ולכן נקבל לוקליות מאוד נמוכה, ההפרדה מבטיחה לוקליות גבוהה בעיקר בתחום ה instructions.

Intel Core i7 Cache Hierarchy

נשים לב שהדוגמאות והמבנה שאנחנו מראים פה מיועד למחשבי desktop ויכול להיות שבמחשבים לייעודים שונים יש מבנה שונה אבל העקרונות זהים.
ישנם סוגים נוספים של associative mapping למשל Full Associative Mapping אבל ההתנהגות היא דומה עם יתרונות וחסרונות אחרים.

חישוב גודל ה cache

בהינתן בלוק בגודל $b$ מילים + $w$ ביטים שמייצגים גודל של כתובת ומילה ונרצה שבcache יהיה $2^n$ מילים. יתקיים:

כאשר:
א) $bw$ זה הביטים הדרושים בשביל כל המילים בdata.
ב) הביטוי בסוגריים מייצג את מספר הביטים הדרושים בשביל הtag -

המילה שממנה מחסירים מייצגת את כל הכתובת, הביטוי $\frac{bw}{8}$ מייצג את מספר ה words בביטים שיש בכל שורה ונרצה לתרגם את זה לבייטים על ידי חלוקה ב8. כלומר מספר הבייטים שיש בdata שמייצגים את המילים. הפעלת ה$\log$ על הביטוי הזה תיתן את ה byte-offset כלומר כמה בייטים דרושים לייצוג כל המילים האלה, מוסיפים לזה $n$ כמספר הבייטים הדרושים לייצוג $2^n$ סטים.

ג) בסוף מוסיפים אחד בישביל הvalid bit.

Cache friendly code

מודדים ביצועים של מטמון לפי מספר מדדים:
1.     Miss rate – החלק של הקריאות לזיכרון בזמן הרצת תוכנית (או חלק מתוכנית) שנגמר בmiss. מחושב לפי כמות misses חלקי כמות references (הפניות לזיכרון).
2.     Hit rate – החלק של הקריאות שהצליח, כלומר היה hit. מחושב על ידי 1-miss rate (המשלים לו).
3.     Hit time – הזמן שלוקח להעביר מילה שנמצאת במטמון למעבד – כולל את הזמן של הset selection, line identification וword selection. עבור הL1 למשל, הוא סדר גודל של מספר clock cycles.
4.  Miss penalty – כל זמן נוסף שלוקח בגלל miss.

The memory mountain

גרף הממדל טוב משיכה של מידע מהזכרון כתלות במספר האיברים במערך ובקפיצות שעושים בין איברים:

ניתן לראות עם כן שיש השפעה של ה stride ושל גודל המערך על המקומיות בזמן ובמרחב שלנו. ככל שהקפיצות גדולות יותר אנחנו נקפוץ לאיבר שלא הגיע למטמון בmiss הקודם ולכן נקבל miss שוב. כמו כן ככל שהמידע גדול יותר ככה אני מבטיח שלא יהיה לכולו מקום מטמון ולכן גם אם אני ניגש לכל האיברים באותו קצב בוודאות יהיו איברים שאצטרך ללכת לזכרון הראשי עבורם מה שפוגע במקומיות הזמן.

טיפים לקוד מהיר יותר שמסתמכים על מקומיות
1.     כשיש לולאות מקוננות, להתמקד בלולאות הפנימיות כי שם רוב פעולות החישוב והגישות לזיכרון לרוב יקרו.
2.     להשתמש במקומיות מרחב על ידי קריאה עוקבת של מידע (כלומר נעדיף stride-1).
3.     למקסם מקומיות זמן בכך שנשתמש במידע ככל הניתן אחרי שהוא כבר נקרא לזיכרון.