การจัดระเบียบและนโยบายแคช

การจัดระเบียบแคชเกี่ยวข้องกับวิธีการที่แคชแมปบล็อกหน่วยความจำไปยังที่เก็บข้อมูล — การจัดวางและการเชื่อมโยง — และนโยบายที่ควบคุมการแทนที่และการเขียน ซึ่งทั้งหมดนี้ร่วมกันกำหนดความถี่ที่แคชจะพบข้อมูล (cache hit) และวิธีการโต้ตอบกับหน่วยความจำหลัก

Definition

การจัดระเบียบและนโยบายแคชคือทางเลือกเชิงโครงสร้างและการจัดการของแคช — ตำแหน่งที่สามารถวางบล็อกได้ บล็อกใดจะถูกนำออกเมื่อเกิด miss และวิธีการส่งผ่านข้อมูลการเขียนไปยังระดับที่ต่ำกว่า — ซึ่งควบคุมอัตราการพบข้อมูล (hit rate) และพฤติกรรมของแคช

Scope

หัวข้อนี้ครอบคลุมการออกแบบภายในของแคชเดี่ยว: การจัดวางแบบ direct-mapped, set-associative และ fully associative; นโยบายการแทนที่ เช่น LRU และการประมาณค่า; นโยบายการเขียน (write-through เทียบกับ write-back) และ write-allocation; ขนาดบล็อก; และการจำแนกประเภทของ miss ออกเป็น compulsory, capacity และ conflict ไม่รวมถึงความสอดคล้องกันของแคชหลายตัว (cache coherence protocols) และการแปลที่อยู่ (หน่วยความจำเสมือนและการแบ่งหน้า)

Core questions

• การจัดวางแบบ direct-mapped, set-associative และ fully associative แตกต่างกันอย่างไรในด้านต้นทุนและพฤติกรรมความขัดแย้ง?
• นโยบายการแทนที่ใดที่ควรนำบล็อกออกเมื่อเกิด miss และจะประมาณค่าได้อย่างไรโดยมีต้นทุนต่ำ?
• นโยบาย write-through และ write-back แตกต่างกันอย่างไรในด้านปริมาณการรับส่งข้อมูลและความซับซ้อน?
• miss ถูกจำแนกอย่างไร และการเปลี่ยนแปลงการออกแบบใดที่ช่วยลดแต่ละประเภท?

Key concepts

• แคชแบบ direct-mapped
• แคชแบบ set-associative
• แคชแบบ fully associative
• การแทนที่แบบ least-recently-used (LRU)
• write-through เทียบกับ write-back
• write-allocate
• ขนาดบล็อก (line)
• compulsory, capacity และ conflict misses

Key theories

โมเดล Three Cs miss

Cache misses สามารถจัดหมวดหมู่ได้เป็น compulsory (การเข้าถึงครั้งแรก), capacity (แคชมีขนาดเล็กเกินไปสำหรับชุดการทำงาน) และ conflict (associativity น้อยเกินไป) ซึ่งเป็นกรอบการทำงานที่เชื่อมโยงพารามิเตอร์การออกแบบแต่ละตัว — ขนาด, ขนาดบล็อก, associativity — กับ miss ที่ลดลง

Mechanisms

ที่อยู่หน่วยความจำจะถูกแบ่งออกเป็นฟิลด์ tag, index และ offset โดย index จะเลือกชุดข้อมูล (set) ส่วน tag จะระบุบล็อกภายในชุดนั้น และ associativity จะกำหนดจำนวนบล็อกที่ใช้ชุดข้อมูลร่วมกัน เมื่อเกิด miss แคชจะดึงบล็อกและนำบล็อกอื่นออกตามนโยบายการแทนที่ที่เลือกไว้ (มักจะเป็นการประมาณค่าของ least-recently-used) การเขียนจะอัปเดตหน่วยความจำหลักทันที (write-through) หรือทำเครื่องหมายบล็อกว่าสกปรก (dirty) และเลื่อนการอัปเดตออกไป (write-back)

Clinical relevance

การจัดระเบียบแคชควบคุมประสิทธิภาพที่มีประสิทธิผล เนื่องจากค่าปรับเมื่อเกิด miss นั้นมีขนาดใหญ่เมื่อเทียบกับการพบข้อมูล (hit) โปรแกรมเมอร์ปรับปรุงพฤติกรรมของแคชผ่านการจัดวางข้อมูล การบล็อก และรูปแบบการเข้าถึงที่เพิ่มความเป็นท้องถิ่น (locality) ในขณะที่สถาปนิกปรับแต่ง associativity, ขนาดบล็อก และนโยบายการเขียนเพื่อรักษาสมดุลระหว่างอัตราการพบข้อมูลกับพื้นที่ พลังงาน และแบนด์วิดท์

History

วิลค์สเสนอหน่วยความจำรอง (แคช) ในปี 1965 และแคชก็ถูกนำมาใช้ในเชิงพาณิชย์ในไม่ช้า การสำรวจของอลัน เจย์ สมิธในปี 1982 ได้สังเคราะห์การวัดผลอย่างกว้างขวางเกี่ยวกับการจัดวาง การแทนที่ และนโยบายการเขียน ซึ่งสร้างคำศัพท์ในการออกแบบที่ยังคงใช้มาจนถึงปัจจุบัน โมเดล Three-Cs ในภายหลังได้ให้วิธีการที่มีโครงสร้างในการให้เหตุผลเกี่ยวกับสาเหตุและการแก้ไขปัญหา miss

Key figures

• Maurice Wilkes
• Alan Jay Smith
• John L. Hennessy
• David A. Patterson

Seminal works

• smith1982cache
• hennessy2019

Frequently asked questions

แคชแบบ write-through และ write-back แตกต่างกันอย่างไร?

แคชแบบ write-through จะอัปเดตทั้งแคชและหน่วยความจำหลักในการเขียนทุกครั้ง ทำให้หน่วยความจำเป็นปัจจุบันอยู่เสมอ แต่สร้างปริมาณการรับส่งข้อมูลมากขึ้น แคชแบบ write-back จะอัปเดตเฉพาะแคช โดยทำเครื่องหมายบล็อกว่าสกปรก (dirty) และเขียนลงหน่วยความจำเมื่อถูกนำออกเท่านั้น ซึ่งช่วยลดปริมาณการรับส่งข้อมูล แต่ต้องแลกมาด้วยการจัดการข้อมูลเพิ่มเติม

ทำไมจึงใช้แคชแบบ set-associative แทนที่จะเป็น direct-mapped?

แคชแบบ direct-mapped อนุญาตให้แต่ละบล็อกมีตำแหน่งเดียวเท่านั้น ดังนั้นบล็อกที่แมปไปยังช่องเดียวกันจะเกิดความขัดแย้ง การเชื่อมโยงแบบ set-associativity ทำให้แต่ละบล็อกมีตำแหน่งที่เป็นไปได้หลายตำแหน่งภายในชุดข้อมูล ซึ่งช่วยลด conflict misses แต่ต้องแลกมาด้วยฮาร์ดแวร์เปรียบเทียบที่มากขึ้นและ hit ที่ช้าลงเล็กน้อย