ลำดับชั้นหน่วยความจำและแคช
ลำดับชั้นหน่วยความจำจัดระเบียบการจัดเก็บข้อมูลออกเป็นระดับต่างๆ ได้แก่ รีจิสเตอร์, แคช, หน่วยความจำหลัก และหน่วยความจำสำรอง เพื่อให้ระดับที่เล็กและเร็วสามารถเก็บข้อมูลที่น่าจะถูกใช้งานมากที่สุด ทำให้โปรแกรมได้รับภาพลวงตาของหน่วยความจำที่มีทั้งขนาดใหญ่และรวดเร็ว
Definition
ลำดับชั้นหน่วยความจำคือการจัดเรียงเทคโนโลยีการจัดเก็บข้อมูลแบบแบ่งชั้นที่มีความเร็ว ต้นทุน และความจุที่แตกต่างกัน โดยมีการจัดการเพื่อให้ข้อมูลที่เข้าถึงบ่อยและล่าสุดอยู่ในระดับที่เร็วกว่าและเล็กกว่า ซึ่งที่สำคัญที่สุดคือแคช เพื่อลดเวลาการเข้าถึงโดยเฉลี่ย
Scope
ส่วนนี้ครอบคลุมถึงเหตุผลและวิธีการจัดระเบียบหน่วยความจำเป็นลำดับชั้นโดยใช้ประโยชน์จากหลักการความใกล้เคียงของการอ้างอิง (locality of reference) ซึ่งรวมถึงโครงสร้างแคช (การจัดวาง, การแทนที่ และนโยบายการเขียน), แคชหลายระดับ, ความสอดคล้องของแคชระหว่างโปรเซสเซอร์, หน่วยความจำเสมือนและการแปลที่อยู่, รวมถึงเทคโนโลยี DRAM และหน่วยความจำเกิดใหม่ที่อยู่เบื้องหลัง แม้ว่าจะมีความเกี่ยวข้องกับทั้งการประมวลผลของโปรเซสเซอร์เอง (สถาปัตยกรรมไมโครของโปรเซสเซอร์) และการจัดเก็บไฟล์และอุปกรณ์ขนาดใหญ่ (ระบบจัดเก็บและ I/O) แต่ส่วนนี้ไม่ครอบคลุมถึงเรื่องดังกล่าวโดยตรง
Sub-topics
Core questions
- เหตุใดหลักการความใกล้เคียงของการอ้างอิงจึงทำให้ลำดับชั้นหน่วยความจำแบบแบ่งชั้นมีประสิทธิภาพ?
- แคชถูกจัดระเบียบอย่างไรในแง่ของการจัดวาง, การเชื่อมโยง, การแทนที่ และนโยบายการเขียน?
- จะรักษาความสอดคล้องได้อย่างไรเมื่อแคชหลายตัวเก็บสำเนาของหน่วยความจำเดียวกัน?
- หน่วยความจำเสมือนแปลที่อยู่และให้การป้องกันและภาพลวงตาของหน่วยความจำขนาดใหญ่ได้อย่างไร?
- คุณลักษณะของ DRAM และหน่วยความจำเกิดใหม่ส่งผลต่อประสิทธิภาพของระบบอย่างไร?
Key concepts
- ความใกล้เคียงเชิงเวลาและเชิงพื้นที่
- แคชฮิตและแคชมิส
- การเชื่อมโยงและนโยบายการแทนที่
- write-through และ write-back
- แคชหลายระดับ
- ความสอดคล้องของแคช
- หน่วยความจำเสมือนและการแบ่งหน้า
- บัฟเฟอร์ค้นหาการแปล
- DRAM และแบนด์วิดท์หน่วยความจำ
- เวลาเข้าถึงหน่วยความจำเฉลี่ย
Key theories
- หลักการความใกล้เคียงของการอ้างอิง
- โปรแกรมมักจะนำข้อมูลที่เข้าถึงล่าสุดกลับมาใช้ซ้ำ (ความใกล้เคียงเชิงเวลา) และเข้าถึงที่อยู่ใกล้เคียงกัน (ความใกล้เคียงเชิงพื้นที่); ลำดับชั้นหน่วยความจำใช้ประโยชน์จากทั้งสองอย่างโดยการแคชบล็อกที่ใช้ล่าสุดและดึงข้อมูลที่อยู่ใกล้เคียงมาพร้อมกัน
- การแลกเปลี่ยนในการออกแบบแคช
- ประสิทธิภาพของแคชถูกควบคุมโดยอัตราการพลาด, ค่าปรับจากการพลาด และเวลาการเข้าถึงที่ตรงกัน และถูกปรับแต่งผ่านขนาด, ขนาดบล็อก, การเชื่อมโยง และนโยบายการแทนที่และการเขียน; การวิเคราะห์แบบคลาสสิกระบุการพลาดแบบบังคับ, การพลาดจากความจุ และการพลาดจากความขัดแย้งว่าเป็นเป้าหมายของการเลือกเหล่านี้
Mechanisms
เมื่อโปรเซสเซอร์ร้องขอข้อมูล แคชจะถูกตรวจสอบก่อน หากเกิดการเข้าถึงข้อมูลที่ตรงกัน (hit) ข้อมูลจะถูกส่งคืนอย่างรวดเร็ว แต่หากไม่ตรงกัน (miss) จะมีการดึงบล็อกข้อมูลจากระดับที่ต่ำกว่า และอาจมีการนำข้อมูลอื่นออกโดยใช้นโยบายการแทนที่ การเขียนข้อมูลจะถูกเผยแพร่โดยใช้กลไก write-through หรือ write-back และโปรโตคอลความสอดคล้องจะช่วยรักษาความสอดคล้องของแคชหลายตัว หน่วยความจำเสมือนจะเพิ่มขั้นตอนการแปลที่อยู่ — ผ่านตารางหน้า (page tables) และบัฟเฟอร์ค้นหาการแปล (translation lookaside buffer) — เพื่อจับคู่ที่อยู่ของโปรแกรมกับ DRAM ทางกายภาพ พร้อมทั้งบังคับใช้การป้องกัน
Clinical relevance
ลำดับชั้นหน่วยความจำมักเป็นปัจจัยหลักที่กำหนดประสิทธิภาพที่แท้จริง: เนื่องจากโปรเซสเซอร์เร็วกว่าหน่วยความจำหลักมาก พฤติกรรมของแคชและความใกล้เคียงของการอ้างอิงจึงมักมีความสำคัญมากกว่าความเร็วในการประมวลผลคำสั่งดิบ การจัดวางข้อมูลที่คำนึงถึงแคช, การแบ่งบล็อก และการดึงข้อมูลล่วงหน้า เป็นหัวใจสำคัญของการประมวลผลประสิทธิภาพสูง, ฐานข้อมูล และเคอร์เนลการเรียนรู้ของเครื่อง และจังหวะเวลาของแคชได้กลายเป็นแหล่งของช่องทางด้านความปลอดภัยแบบ side channel
History
Maurice Wilkes ได้เสนอแนวคิดแคช (ซึ่งเขาเรียกว่า 'หน่วยความจำรอง') ในปี 1965 และแคชได้ถูกนำมาใช้ในเครื่องจักรเชิงพาณิชย์ เช่น IBM System/360 Model 85 หน่วยความจำเสมือนมีต้นกำเนิดมาจากคอมพิวเตอร์ Atlas ในช่วงต้นทศวรรษ 1960 และได้รับการจัดรูปแบบโดยแบบจำลอง working-set ของ Denning การสำรวจของ Alan Jay Smith ในปี 1982 ได้รวบรวมความรู้เกี่ยวกับการออกแบบแคช และแคชหลายระดับรวมถึงโปรโตคอลความสอดคล้องที่ซับซ้อนได้กลายเป็นมาตรฐานเมื่อช่องว่างความเร็วระหว่างโปรเซสเซอร์กับหน่วยความจำกว้างขึ้น
Debates
- การจัดการความใกล้เคียงด้วยฮาร์ดแวร์เทียบกับซอฟต์แวร์
- มีความตึงเครียดอย่างต่อเนื่องระหว่างการแคชด้วยฮาร์ดแวร์ที่โปร่งใสกับการจัดการหน่วยความจำอย่างชัดเจน (scratchpads, การดึงข้อมูลล่วงหน้าด้วยซอฟต์แวร์): การแคชด้วยฮาร์ดแวร์เป็นแบบทั่วไปและง่ายต่อการเขียนโปรแกรม ในขณะที่การจัดการอย่างชัดเจนอาจคาดการณ์ได้และมีประสิทธิภาพมากกว่าสำหรับภาระงานเฉพาะทาง
Key figures
- Maurice Wilkes
- Alan Jay Smith
- Peter J. Denning
- John L. Hennessy
- David A. Patterson
Related topics
Seminal works
- hennessy2019
- smith1982cache
- patterson2020
Frequently asked questions
- เหตุใดแคชจึงมีประสิทธิภาพทั้งที่เล็กมากเมื่อเทียบกับหน่วยความจำหลัก?
- เนื่องจากโปรแกรมแสดงคุณสมบัติความใกล้เคียงของการอ้างอิง: ณ เวลาใดเวลาหนึ่ง โปรแกรมจะเข้าถึงชุดข้อมูลที่ใช้งานอยู่เพียงเล็กน้อยซ้ำๆ และการเข้าถึงจะกระจุกตัวอยู่ในที่อยู่ใกล้เคียงกัน ดังนั้น แคชขนาดเล็กที่เก็บชุดข้อมูลที่ใช้งานอยู่นั้นจึงสามารถตอบสนองคำขอส่วนใหญ่ได้
- ความแตกต่างระหว่างแคชกับหน่วยความจำเสมือนคืออะไร?
- ทั้งสองอย่างเป็นการย้ายข้อมูลระหว่างระดับที่เร็วกว่าและเล็กกว่า กับระดับที่ช้ากว่าและใหญ่กว่า แคช (จัดการโดยฮาร์ดแวร์) เก็บข้อมูลบล็อกของหน่วยความจำหลัก; หน่วยความจำเสมือน (จัดการร่วมกับระบบปฏิบัติการ) จะจับคู่ที่อยู่ของโปรแกรมกับหน่วยความจำทางกายภาพและแบ่งหน้าข้อมูลเข้าและออกจากดิสก์ พร้อมทั้งให้การป้องกันและพื้นที่ที่อยู่ที่มีขนาดใหญ่กว่า RAM ทางกายภาพ