นโยบายการจัดวางแคชคือนโยบายที่กำหนดตำแหน่งที่สามารถวางบล็อกหน่วยความจำเฉพาะเมื่อเข้าสู่แคชของ CPUบล็อกหน่วยความจำไม่จำเป็นต้องวางไว้ที่ตำแหน่งใดก็ได้ในแคช อาจถูกจำกัดไว้ที่บรรทัดแคช เฉพาะ หรือชุดของบรรทัดแคช^{[ 1 ]}โดยนโยบายการจัดวางแคช^{[ 2 ] [ 3 ]}

มีนโยบายที่แตกต่างกันสามแบบสำหรับการจัดวางบล็อกหน่วยความจำในแคช ได้แก่ แบบแมปโดยตรง แบบเชื่อมโยงอย่างสมบูรณ์ และแบบเชื่อมโยงชุด เดิมทีพื้นที่ขององค์ประกอบแคชนี้ถูกอธิบายโดยใช้คำว่า "การแมปความสอดคล้อง" ^{[ 4 ]}

ในโครงสร้างแคชแบบแมปโดยตรง แคชจะถูกจัดระเบียบเป็นชุดหลายชุด^{[ 1 ]}โดยมีแคชไลน์เดียวต่อชุด ขึ้นอยู่กับที่อยู่ของบล็อกหน่วยความจำ แคชสามารถครอบครองแคชไลน์เดียวเท่านั้น แคชสามารถกำหนดกรอบเป็นเมทริกซ์คอลัมน์n × 1 ได้^{[ 5 ]}

• ชุดจะถูกกำหนดโดย บิต ดัชนี^{[ 1 ]}ที่ได้มาจากที่อยู่ของบล็อกหน่วยความจำ
• บล็อกหน่วยความจำจะถูกวางไว้ในชุดที่ระบุ และแท็ก^{[ 1 ]}จะถูกเก็บไว้ในฟิลด์แท็กที่เกี่ยวข้องกับชุด
• หากแคชไลน์ถูกใช้งานอยู่ก่อนแล้ว ข้อมูลใหม่จะเข้ามาแทนที่บล็อกหน่วยความจำในแคช

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

• นโยบายการจัดวางนี้ประหยัดพลังงาน เนื่องจากหลีกเลี่ยงการค้นหาผ่านแคชไลน์ทั้งหมด
• นโยบายการจัดหาบุคลากรและนโยบายการทดแทนนั้นเรียบง่าย
• สามารถใช้ฮาร์ดแวร์ที่เรียบง่ายและราคาประหยัดได้ เนื่องจากต้องตรวจสอบแท็กเพียงครั้งละหนึ่งแท็กเท่านั้น

• มีอัตราการเข้าถึงแคชที่ต่ำกว่า เนื่องจากมีแคชไลน์เพียงบรรทัดเดียวในชุด ทุกครั้งที่มีการอ้างอิงหน่วยความจำใหม่ไปยังชุดเดียวกัน แคชไลน์จะถูกแทนที่ ซึ่งทำให้เกิดการพลาดความขัดแย้ง^{[ 6 ]}

พิจารณาหน่วยความจำหลักขนาด 16 กิโลไบต์ ซึ่งจัดเรียงเป็นบล็อกขนาด 4 ไบต์ และแคชแบบ direct-mapped ขนาด 256 ไบต์ โดยมีขนาดบล็อก 4 ไบต์ เนื่องจากหน่วยความจำหลักมีขนาด 16 กิโลไบต์ เราจึงต้องการอย่างน้อย 14 บิตเพื่อใช้ในการแทนที่อยู่หน่วยความจำได้ อย่างเฉพาะ เจาะจง

เนื่องจากแต่ละบล็อกแคชมีขนาด 4 ไบต์ ดังนั้นจำนวนชุดข้อมูลทั้งหมดในแคชจึงเท่ากับ 256/4 ซึ่งเท่ากับ 64 ชุด

ที่อยู่ขาเข้าของแคชจะถูกแบ่งออกเป็นบิตสำหรับค่าออฟเซ็ตดัชนีและแท็ก

• ค่าออฟเซ็ตคือจำนวนบิตที่ใช้ในการกำหนดไบต์ที่จะเข้าถึงจากแคชไลน์ เนื่องจากแคชไลน์มีความยาว 4 ไบต์ จึงมีบิตออฟเซ็ต 2บิต
• ดัชนีหมายถึงบิตที่ใช้ในการกำหนดชุดของแคช มีทั้งหมด 64 ชุดในแคช และเนื่องจาก 2^6 = 64 จึงมีบิตดัชนีทั้งหมด 6 บิต
• แท็กจะสอดคล้องกับบิตที่เหลืออยู่ ซึ่งหมายความว่ามีบิตแท็กทั้งหมด 14 – (6+2) = 6 บิตที่ถูกจัดเก็บไว้ในฟิลด์แท็กเพื่อให้ตรงกับที่อยู่ในการร้องขอแคช

ด้านล่างนี้คือที่อยู่หน่วยความจำและคำอธิบายว่าแต่ละที่อยู่เชื่อมโยงกับแคชไลน์ใด:

1. ที่อยู่0x0000(แท็ก - 0b00_0000, ดัชนี – 0b00_0000, ออฟเซ็ต – 0b00) สอดคล้องกับบล็อก 0 ของหน่วยความจำและแมปไปยังชุด 0 ของแคช
2. ที่อยู่0x0004(แท็ก - 0b00_0000, ดัชนี – 0b00_0001, ออฟเซ็ต – 0b00) สอดคล้องกับบล็อกที่ 1 ของหน่วยความจำและแมปไปยังชุดที่ 1 ของแคช
3. ที่อยู่0x00FF(แท็ก – 0b00_0000, ดัชนี – 0b11_1111, ออฟเซ็ต – 0b11) สอดคล้องกับบล็อกที่ 63 ของหน่วยความจำและแมปไปยังชุดที่ 63 ของแคช
4. ที่อยู่0x0100(แท็ก – 0b00_0001, ดัชนี – 0b00_0000, ออฟเซ็ต – 0b00) ตรงกับบล็อกที่ 64 ของหน่วยความจำและแมปไปยังชุดที่ 0 ของแคช

ในแคชแบบเชื่อมโยงอย่างสมบูรณ์ แคชจะถูกจัดระเบียบเป็นชุดแคชเดียวที่มีหลายบรรทัดแคช บล็อกหน่วยความจำสามารถครอบครองบรรทัดแคชใดก็ได้ การจัดระเบียบแคชสามารถกำหนดเป็นเมทริกซ์แถว1 × m ได้ ^{[ 5 ]}

• แคชไลน์จะถูกเลือกตามบิตที่ถูกต้อง^{[ 1 ]}ที่เกี่ยวข้อง หากบิตที่ถูกต้องเป็น 0 บล็อกหน่วยความจำใหม่สามารถวางในแคชไลน์ได้ มิฉะนั้นจะต้องวางในแคชไลน์อื่นที่มีบิตที่ถูกต้องเป็น 0
• หากแคชเต็มแล้ว บล็อกหนึ่งจะถูกนำออกจากแคช และบล็อกหน่วยความจำใหม่จะถูกนำไปไว้ในบรรทัดแคชนั้น
• การขับไล่บล็อกหน่วยความจำออกจากแคชจะถูกตัดสินโดย นโยบาย การแทนที่^{[ 7 ]}

• ฟิลด์ Tag ของที่อยู่หน่วยความจำจะถูกเปรียบเทียบกับบิต Tag ที่เชื่อมโยงกับบรรทัดแคชทั้งหมด หากตรงกัน แสดงว่าบล็อกนั้นมีอยู่ในแคชและถือเป็น Cache Hit หากไม่ตรงกัน ถือเป็น Cache Miss และต้องดึงข้อมูลจากหน่วยความจำระดับล่างขึ้นมา
• โดยอิงตามค่าออฟเซ็ต ระบบจะเลือกไบต์และส่งกลับไปยังโปรเซสเซอร์

• โครงสร้างแคชแบบ Fully associative ช่วยให้เรามีความยืดหยุ่นในการวางบล็อกหน่วยความจำในบรรทัดแคชใดก็ได้ จึงทำให้สามารถใช้ประโยชน์จากแคชได้อย่างเต็มที่
• นโยบายการจัดวางข้อมูลช่วยให้ได้อัตราการเข้าถึงแคชที่ดีขึ้น
• ระบบนี้มีความยืดหยุ่นในการใช้งาน อัลกอริทึมการแทนที่ที่หลากหลายหากเกิดแคชพลาด

• นโยบายการจัดวางตำแหน่งนั้นใช้พลังงานสูง เนื่องจากวงจรเปรียบเทียบต้องทำงานตรวจสอบแคชทั้งหมดเพื่อค้นหาบล็อกที่ต้องการ
• วิธีนี้มีราคาแพงที่สุด เนื่องจากฮาร์ดแวร์สำหรับการเปรียบเทียบแบบเชื่อมโยงมีราคาสูง

ลองพิจารณาหน่วยความจำหลักขนาด 16 กิโลไบต์ ซึ่งจัดเรียงเป็นบล็อกขนาด 4 ไบต์ และแคชแบบเชื่อมโยงเต็มรูปแบบขนาด 256 ไบต์ โดยมีขนาดบล็อก 4 ไบต์ เนื่องจากหน่วยความจำหลักมีขนาด 16 กิโลไบต์ เราจึงต้องการอย่างน้อย 14 บิตเพื่อใช้ในการแทนที่อยู่หน่วยความจำได้อย่างเฉพาะเจาะจง

จำนวนเซ็ตทั้งหมดในแคชคือ 1 และแต่ละเซ็ตประกอบด้วยแคชไลน์จำนวน 256/4 = 64 ไลน์ เนื่องจากบล็อกแคชมีขนาด 4 ไบต์

ที่อยู่ขาเข้าของแคชจะถูกแบ่งออกเป็นบิตสำหรับค่าออฟเซ็ตและแท็ก

• ค่าออฟเซ็ต (Offset)คือจำนวนบิตที่ใช้ในการกำหนดไบต์ที่จะเข้าถึงจากแคชไลน์ ในตัวอย่างนี้ มีบิตออฟเซ็ต 2 บิต ซึ่งใช้ในการระบุตำแหน่งไบต์ทั้ง 4 ไบต์ของแคชไลน์
• แท็กจะสอดคล้องกับบิตที่เหลือ ซึ่งหมายความว่ามีบิตแท็ก 14 – (2) = 12 บิตซึ่งจะถูกเก็บไว้ในฟิลด์แท็กเพื่อให้ตรงกับที่อยู่ในการร้องขอแคช

เนื่องจากบล็อกหน่วยความจำใดๆ ก็สามารถแมปไปยังแคชไลน์ใดก็ได้ ดังนั้นบล็อกหน่วยความจำจึงสามารถใช้แคชไลน์ใดแคชไลน์หนึ่งได้ ขึ้นอยู่กับนโยบายการแทนที่

แคชแบบ Set-associative เป็นการประนีประนอมระหว่างแคชแบบ direct-mapped และแคชแบบ fully associative

แคชแบบเซตแอสโซซิเอทีฟสามารถจินตนาการได้ว่าเป็น เมทริกซ์ขนาด n × mโดยแคชจะถูกแบ่งออกเป็น 'n' เซต และแต่ละเซตประกอบด้วยแคชไลน์ 'm' บล็อกหน่วยความจำจะถูกแมปไปยังเซตใดเซตหนึ่งก่อน จากนั้นจึงถูกวางลงในแคชไลน์ใดก็ได้ในเซตนั้น

แคชประเภทต่างๆ ตั้งแต่แบบ direct-mapped ไปจนถึงแบบ fully associative เป็นความต่อเนื่องของระดับความสัมพันธ์แบบ set associativity (แคชแบบ direct-mapped เป็นแคชแบบ one-way set-associative และแคชแบบ fully associative ที่มีmไลน์แคชจะเป็นแคชแบบm -way set-associative)

แคชโปรเซสเซอร์จำนวนมากในการออกแบบในปัจจุบันเป็นแบบ direct-mapped, two-way set-associative หรือ four-way set-associative ^{[ 5 ]}

• ชุดข้อมูลถูกกำหนดโดยบิตดัชนีที่ได้มาจากที่อยู่ของบล็อกหน่วยความจำ
• บล็อกหน่วยความจำจะถูกวางไว้ในบรรทัดแคชที่ว่างอยู่ในชุดที่ระบุ และแท็กจะถูกจัดเก็บไว้ในฟิลด์แท็กที่เชื่อมโยงกับบรรทัดนั้น หากบรรทัดแคชทั้งหมดในชุดถูกใช้งานเต็มแล้ว ข้อมูลใหม่จะเข้ามาแทนที่บล็อกที่ระบุผ่านนโยบายการแทนที่

• ชุดข้อมูลถูกกำหนดโดยบิตดัชนีที่ได้มาจากที่อยู่ของบล็อกหน่วยความจำ
• บิตของแท็กจะถูกเปรียบเทียบกับแท็กของบรรทัดแคชทั้งหมดที่มีอยู่ในชุดที่เลือก หากแท็กตรงกับบรรทัดแคชใดๆ ก็ตาม ถือว่าเป็นแคชฮิต และระบบจะส่งคืนบรรทัดที่เกี่ยวข้อง หากแท็กไม่ตรงกับบรรทัดใดๆ เลย ถือว่าเป็นแคชมิส และระบบจะขอข้อมูลจากระดับถัดไปในลำดับชั้นของหน่วยความจำ

• นโยบายการจัดวางตำแหน่งเป็นการประนีประนอมระหว่างแคชแบบแมปโดยตรงและแคชแบบเชื่อมโยงอย่างสมบูรณ์
• มันมีความยืดหยุ่นในการใช้อัลกอริธึมทดแทนหากเกิดแคชพลาด

• นโยบายการจัดวางจะไม่ใช้บรรทัดแคชที่มีอยู่ทั้งหมดในแคชอย่างมีประสิทธิภาพ และประสบปัญหาการพลาดแคชเนื่องจากความขัดแย้ง

พิจารณาหน่วยความจำหลักขนาด 16 กิโลไบต์ ซึ่งจัดเรียงเป็นบล็อกขนาด 4 ไบต์ และแคชแบบ 2 ทาง set-associative ขนาด 256 ไบต์ โดยมีขนาดบล็อก 4 ไบต์ เนื่องจากหน่วยความจำหลักมีขนาด 16 กิโลไบต์ เราจึงต้องการอย่างน้อย 14 บิตเพื่อใช้ในการแทนที่อยู่หน่วยความจำได้อย่างเฉพาะเจาะจง

เนื่องจากแต่ละบล็อกแคชมีขนาด 4 ไบต์และเป็นแบบ 2-way set-associative ดังนั้นจำนวนชุดทั้งหมดในแคชจึงเท่ากับ 256/(4 * 2) ซึ่งเท่ากับ 32 ชุด

ที่อยู่ขาเข้าของแคชจะถูกแบ่งออกเป็นบิตสำหรับค่าออฟเซ็ต ดัชนี และแท็ก

• ค่าออฟเซ็ตคือจำนวนบิตที่ใช้ในการกำหนดไบต์ที่จะเข้าถึงจากแคชไลน์ เนื่องจากแคชไลน์มีความยาว 4 ไบต์ จึงมีบิตออฟเซ็ต 2บิต
• ดัชนีหมายถึงบิตที่ใช้ในการกำหนดชุดข้อมูลในแคช มีทั้งหมด 32 ชุดในแคช และเนื่องจาก 2^5 = 32 ดังนั้นจึงมีบิตดัชนีทั้งหมด 5 บิต
• แท็กจะสอดคล้องกับบิตที่เหลืออยู่ ซึ่งหมายความว่ามี 14 – (5+2) = 7 บิตที่ถูกเก็บไว้ในฟิลด์แท็กเพื่อให้ตรงกับที่อยู่ในการร้องขอแคช

ด้านล่างนี้คือที่อยู่หน่วยความจำและคำอธิบายว่าที่อยู่เหล่านั้นตรงกับแคชไลน์ใดในชุดใด:

1. ที่อยู่0x0000(แท็ก - 0b000_0000, ดัชนี – 0b0_0000, ออฟเซ็ต – 0b00) สอดคล้องกับบล็อก 0 ของหน่วยความจำและแมปไปยังชุด 0 ของแคช บล็อกดังกล่าวใช้พื้นที่ในบรรทัดแคชในชุด 0 ซึ่งกำหนดโดยนโยบายการแทนที่สำหรับแคช
2. ที่อยู่0x0004(แท็ก - 0b000_0000, ดัชนี – 0b0_0001, ออฟเซ็ต – 0b00) สอดคล้องกับบล็อกที่ 1 ของหน่วยความจำและแมปไปยังชุดที่ 1 ของแคช บล็อกดังกล่าวใช้พื้นที่ในบรรทัดแคชในชุดที่ 1 ซึ่งกำหนดโดยนโยบายการแทนที่สำหรับแคช
3. ที่อยู่0x00FF(แท็ก – 0b000_0001, ดัชนี – 0b1_1111, ออฟเซ็ต – 0b11) ตรงกับบล็อกที่ 63 ของหน่วยความจำและแมปไปยังชุดที่ 31 ของแคช บล็อกนี้ใช้พื้นที่ในบรรทัดแคชในชุดที่ 31 ซึ่งกำหนดโดยนโยบายการแทนที่สำหรับแคช
4. ที่อยู่0x0100(แท็ก – 0b000_0010, ดัชนี – 0b0_0000, ออฟเซ็ต – 0b00) สอดคล้องกับบล็อกที่ 64 ของหน่วยความจำและแมปไปยังชุดที่ 0 ของแคช บล็อกดังกล่าวใช้พื้นที่ในบรรทัดแคชในชุดที่ 0 ซึ่งกำหนดโดยนโยบายการแทนที่สำหรับแคช

มีการเสนอแผนการอื่นๆ เช่นแคชแบบเบี่ยงเบน [ ^{8 ] โดย}ที่ดัชนีสำหรับทาง 0 เป็นแบบตรง ดังที่กล่าวมาข้างต้น แต่ดัชนีสำหรับทาง 1 ถูกสร้างขึ้นด้วยฟังก์ชันแฮชฟังก์ชันแฮชที่ดีมีคุณสมบัติที่ว่าแอดเดรสที่ขัดแย้งกับการแมปแบบตรงมักจะไม่ขัดแย้งเมื่อแมปด้วยฟังก์ชันแฮช ดังนั้นจึงมีโอกาสน้อยที่โปรแกรมจะประสบปัญหาการพลาดความขัดแย้งจำนวนมากอย่างไม่คาดคิดเนื่องจากรูปแบบการเข้าถึงที่ผิดปกติ ข้อเสียคือความหน่วงแฝงเพิ่มเติมจากการคำนวณฟังก์ชันแฮช^{[ 9 ]}นอกจากนี้ เมื่อถึงเวลาที่จะโหลดบรรทัดใหม่และลบบรรทัดเก่า อาจเป็นเรื่องยากที่จะระบุว่าบรรทัดที่มีอยู่ใดถูกใช้งานน้อยที่สุดเมื่อเร็วๆ นี้ เนื่องจากบรรทัดใหม่ขัดแย้งกับข้อมูลที่ดัชนีต่างกันในแต่ละทาง การติดตาม LRUสำหรับแคชที่ไม่เบี่ยงเบนมักจะทำบนพื้นฐานต่อชุด อย่างไรก็ตาม แคชแบบเชื่อมโยงเบี่ยงเบนมีข้อได้เปรียบที่สำคัญเหนือแคชแบบเชื่อมโยงชุดทั่วไป^{[ 10 ]}

แคชแบบ set-associative ที่แท้จริงจะทดสอบวิธีการที่เป็นไปได้ทั้งหมดพร้อมกัน โดยใช้สิ่งที่คล้ายกับหน่วยความจำที่เข้าถึงได้ด้วยเนื้อหา (content-addressable memory ) ในขณะที่แคชแบบ pseudo-associative จะทดสอบแต่ละวิธีการที่เป็นไปได้ทีละวิธี ตัวอย่างของแคชแบบ pseudo-associative ได้แก่ แคชแบบ hash-rehash และแคชแบบ column-associative

ในกรณีทั่วไปของการค้นหาฮิตด้วยวิธีแรกที่ทดสอบ แคชแบบ pseudo-associative จะเร็วเท่ากับแคชแบบ direct-mapped แต่มีอัตราการพลาดเนื่องจากความขัดแย้งต่ำกว่าแคชแบบ direct-mapped มาก ซึ่งใกล้เคียงกับอัตราการพลาดของแคชแบบ fully associative ^{[ 9 ]}

• ความสัมพันธ์
• นโยบายการแทนที่แคช
• ลำดับชั้นของแคช
• นโยบายการเขียน
• การระบายสีแคช