แนวคิดของหน่วยความจำแคช

Cache - a safe place to store things

คำว่า ``แคช'' (Cache) ใช้เรียก ลำดับชั้นของหน่วยความจำ ที่อยู่ระหว่างโปรเซสเซอร์ และหน่วยความจำหลัก ซึ่งปัจจุบัน คำว่าแคชใช้แทนอุปกรณ์เก็บข้อมูลใดๆ ที่สามารถใช้ประโยชน์จากพื้นฐานของ Locality ซึ่งหน่วยความจำแคชใช้งานอย่างแพร่หลายในส่วนของโปรเซสเซอร์ประสิทธิภาพสูง ถึงโปรเซสเซอร์ขนาดเล็ก

รูป 7.4 แสดงถึงหน่วยความจำแคชอย่างง่าย ก่อนและหลังการเรียกข้อมูล $X_n$ ที่เมื่อเริ่มแรกไม่อยู่ในแคช ก่อนการเรียกใช้ข้อมูล แคชมีค่า $X_1, X_2, X_3, \ldots, X_{n-1}$ ในขณะที่ $X_n$ ไม่อยู่ในแคช เมื่อเกิดการ Miss ค่า $X_n$ จะถูกนำจากหน่วยความจำหลักข้ามาในแคช ต่อไป

Figure 7.4: การเรียกข้อมูลในหน่วยความจำแคชก่อน และหลังจากการเรียกค่า $X_n$ ที่เมื่อเริ่มแรกไม่อยู่ในแคช

จากรูป 7.4 มีคำถามสองประการที่จะต้องตอบได้แก่

1. จะรู้ได้อย่างไรว่าข้อมูลที่ต้องการอยู่ในแคช
2. จะทำอย่างไรเมื่อพบว่าข้อมูลอยู่ในแคช

วิธีการที่ง่ายที่สุดในการกำหนดตำแหน่งของแอดเดรส ของแต่ละ Word ในหน่วยความจำในแคช โดยใช้การคำนวณ $mod$ ของแอดเดรสในหน่วยความจำลงในแคช ซึ่งการทำการดังกล่าว เรียกว่า Direct Mapped ในโครงสร้างแคช มีการจัดสรรตำแหน่งเฉพาะในแคช สำหรับแอดเดรสหนึ่งๆ ในหน่วยความจำ โดยใช้สมการดังต่อไปนี้

$$(Block address) modulo (Number of cache blocks in the cache)$$ (7.1)

Figure 7.5: การทำ Direct Map บนแคชที่มี 8 ช่องและแสดงแอดเดรสของหน่วยความจำระหว่าง 0 ถึง 31 ที่มีการกำหนดให้ลงช่องเดียวกัน

วิธีการกำหนดตำแหน่งระหว่างแคชกับหน่วยความจำในลักษณะนี้มีข้อดีคือความง่ายของวิธีการ ในกรณีที่หน่วยความจำแคชมีขนาดเป็นเลขของสองยกกำลัง การทำการ modulo สามารถทำได้โดยตรงโดยการตัดบิตทางซ้ายของแอดเอรส มาใช้ในการอ้างอิงตำแหน่งในหน่วยความจำแคช รูป 7.5 แสดงแอดเครสของหน่วยความจำระหว่าง $1_{ten} (00001_{two})$ และ $29_{ten} (11101_{two})$ ที่ทำการเทียบกับตำแหน่ง $1_{ten}(001_{two})$ และ $5_{ten}(101_{two})$ สำหรับแคชขนาด 8 words

เนื่องจากในแต่ละตำแหน่งของแคชสามารถบรรจุแอดเดรสได้หลายตำแหน่งแทนที่กัน วิธีการที่จะทำให้ทราบว่าแอดเดรสดังกล่าวเป็นของตำแหน่งใด แสดงโดยค่าของ Tag โดยที่ Tag จะเก็บส่วนที่เหลือของแอดเดรสเพื่อสำหรับตรวจสอบว่าตำแหน่งนั้นเป็นของแอดเดรสใด โดยการรวม Tag และตำแหน่งอ้างอิงในแคชเข้าด้วยกัน ในรูป 7.5 Tag จะมีขนาด 2 บิตจาก 5 บิตที่แสดงแอดเดรส นอกจากนี้ยังมี Valid บิต สำหรับชี้ว่าในแคชมีข้อมูลที่มีตรงและสามารถใช้งานได้ เมื่อเริ่มแรกในการเปิดเครื่อง Valid บิตจะถูกตั้งค่าให้เป็น 0 เพื่อเมื่อถูกใช้งานจะได้นำค่ามาจากหน่วยความจำในลำดับต่อไป

Decimal address	Binary address	Hit or miss	Assigned cache block
of reference	of reference	in cache	(where found or placed
22	$10110_{two}$	miss	$(10110_{two} mod 8) = 110_{two}$
26	$11010_{two}$	miss	$(11010_{two} mod 8) = 010_{two}$
22	$10110_{two}$	hit	$(10110_{two} mod 8) = 110_{two}$
26	$11010_{two}$	hit	$(11010_{two} mod 8) = 010_{two}$
16	$10000_{two}$	miss	$(10000_{two} mod 8) = 000_{two}$
3	$00011_{two}$	miss	$(00011_{two} mod 8) = 011_{two}$
16	$10000_{two}$	hit	$(10000_{two} mod 8) = 000_{two}$
18	$10010_{two}$	miss	$(10010_{two} mod 8) = 010_{two}$

รูป 7.6 แสดงแอดเดรสที่แบ่งออกเป็น

• Cache Index สำหรับอ้างอิงแคชในการเลือก Block ที่เหมาะสม
• Tag Field สำหรับการเปรียบเทียบกับแอดเดรสในการระบุตำแหน่งที่ถูกต้อง

Figure 7.6: ในระบบแคชที่แสดงในรูป ส่วนล่างของแอดเดรสใช้เลือกตำแหน่งในแคช และเปรียบเทียบ tag ในการพิสูจน์

การอ้างอิงแคชประกอบกับ Tag ของ Block เป็นการระบบตำแหน่งของหน่วยความจำที่ต้องการใช้งาน เนื่องจากฟิลด์ index ใช้ในกาารอ้างอิง ขนาด $n$ บิตของ index สามารถอ้างอิงได้ Word จะมีการจัดเรียงเป็น 4 bytes โดยจะไม่ใช้สองบิตสุดท้ายในการทำงานเนื่องจากเป็น Byte Offset

จำนวนบิตในแคช ขึ้นอยู่กับขนาดของแคช และขนาดของแอดเดรส เนื่องจากแคชประกอบด้วยทั้ง Data และ Tag Block หนึ่งๆ สามารถมีขนาดตั้งแต่หนึ่ง Word ถึงหลายๆ Word ถ้าสมมุติให้ขนาดของแอดเดรสมีขนาด 32 บิต ในการอ้างอิงข้อมูลขนาดหนึ่ง Byte และ ขนาดของ Direct Mapping มีขนาดเท่ากับ $2^n$ Blocks ที่มีขนาด $2^m$ Words และ $2^(m+2)$ ไบท์ โดยขนาดของฟิลด์ Tag เท่ากับ $32-(n+m+2)$ บิต เนื่องจากใช้ $n$ บิต สำหรับ index และ m บิต สำหรับการอ้างอิง Word ในแต่ละ Block และ 2 บิตสำหรับการอ้างอิง Byte ใน Word ขนาดของแคชจึงเท่ากับ $2^n\times (m\times 32 +(32-n-m-2)+1) = 2^n\times (m\times 32 + 31 -n-m)$