INT 601 Computer System Concept
Section 3 (3b) Computer Memory
Cache เป็นหน่วยความจำชนิดหนึ่งที่มีความเร็วในการ access และtransfer data ได้สูงถือได้ว่าเป็นส่วนประกอบสำคัญของ memory hierarchy หน้าที่หลักๆ ก็คือ เก็บพักข้อมูลที่ซีพียูใช้งานบ่อยๆ จะได้ค้นหาได้เร็ว โดยที่ไม่จำเป็นที่จะต้องไปค้นหาจากข้อมูลทั้งหมด
CACHE is SRAM: static ram สามารถ refresh เมื่อสั่งให้ refresh เท่านั้น จะไม่ refresh อัตโนมัติ
ตำแหน่งของ CACHE
-อยู่บน CPU chip และอยู่บน Mother Board
-มันจะวางตัวเป็นคนกลางระหว่าง CPU กับ Main memory
Level ของ CACHE
Level 1 on CPU chip- High speed equal to CPU and small.เรียกว่า internal cache
Level 2 on mother board – Higher speed and smaller than main memory (SDRAM) But lower speed and bigger than Level 1. เรียกว่า External cache
ขนาดของ cache เล็กกว่า main memory
ราคา cache สูงกว่า main memory
Cache ไม่ได้มีข้อมูลเป็นของตัวเอง คัดลอกจาก main memory มาเก็บไว้ที่ตัวเอง เลือกคัดลอกเฉพาะที่ซีพียูใช้บ่อยๆ นอกจากนี้ยังต้องเดาใจซีพียูด้วย มันลอกมาทั้ง block จาก main memory แต่ซีพียูมาแค่ word เดียว ที่มันต้องทำอย่างนี้เพราะมันเดาว่า CPU ทำงานแบบ sequential execution มันก็เลยลอกมาทั้ง block เพราะในแต่ละ block จะมี offset word address ที่เรียงต่อกัน
Cache ติดต่อกับ main Memory อย่างไร
- จะติดต่อกันผ่านบัส
- การถ่ายโอนข้อมูลในรูแบบของ block
- ขนาดของ Line /slot / page ที่เก็บข้อมูลบน cache กับบน main memory จะเท่ากัน เช่น 1 block บน main memory มี 10 words บน Line /slot / page ก็ควรจะมีอย่างน้อยเท่ากับ 10 words เช่นกัน มีน้อยก็เก็บไม่พอสิ ล้น
- แต่ละ block ที่คัดลอกไปไว้ที่ cache จะมีหลาย words และแต่ละ words ที่อยู่บน block ก็สามารถถูกดึงไปใช้งานโดยซีพียู (ก็ที่อุตส่าห์ไปก๊อบเค้ามาก็เอาไว้บริการซีพียูนี่แหละ ถ้าให้มันไปค้นเองที่ main memory ต้องใช้เวลานาน รอไม่ไหวหรอก ซีพียูเค้าใจร้อน คอขวดบานเลย)
- ที่บอกว่า cache ทำงานเร็วเนี่ยะ เป็นส่วนของฮาร์ดแวร์เค้าล้วนๆ นะ ไม่เกี่ยวกับซอฟต์แวร์หรอกนะ OS
- ถ้าหาบน cache ไม่เจอข้อมูลก็ไปค้นต่อใน main memory นะ ก็ยกหน้าที่ให้ cache controller เค้านะ ถ้าเจอแล้วก็จัดส่งให้ซีพียูเค้าไปแล้วก็คัดลอกมาเก็บที่ cache ด้วย ทำไปพร้อมๆ กันเลยล่ะ
หลักการทำงานคร่าวๆ ระหว่าง CPU CACHE และ main memory จะเริ่มต้นจาก CPU ส่ง request ไปยัง cache โดยจะส่งเป็น word address ไปให้ cache และ cache controller จะทำการค้าหาถ้าเจอเลย เรียกว่า cache hit และหากไม่เจอ เรียกว่า cache miss ซึ่งอัตราส่วนระหว่าง cache hit/cache miss เรียกว่า hit ratio ถ้า hit ratio สูงแสดงว่ามีประสิทธิภาพดี
กรณีค้นแล้วเจอเลย ก็จะทำการ fetch address word และส่งให้ซีพียู
หากไม่เจอ cache controller ก็จะไปค้นที่ main memory เมื่อเจอแล้วก็จะคัดลอกมาไว้ที่ cache และทำการส่งไปให้ CPU พร้อมๆ กัน
เมื่อมองขนาดระหว่าง cache กับ main memory นั้นต่างกันอย่างมาก ในหนึ่ง block ของ main memory จะประกอบไปด้วย k words ซึ่งขนาดของ main memory จะเท่ากับ จำนวน block ทั้งหมดบน main memory คูณกับ จำนวน k words/block
ขนาดของ block data ที่คัดลอกจาก main memory จะถูกเก็บบน line ของ cache ซึ่งจะมีขนาดเท่ากับ block และจะมีการแปะ tag ให้กับแต่ละ line เพื่อบอกที่มาของ block จาก main memory
ปัจจัยในการออกแบบ cache
ขนาดของแคช (cache size)
· ให้แคชมีขนาดเล็กเพียงพอที่จะทำให้ราคาเฉลี่ยต่อบิตมีความใกล้เคียงกับราคาของหน่วยความจำหลัก
· ให้มีขนาดใหญ่เพียงพอ เพื่อให้ค่าเฉลี่ยของเวลาในการเข้าถึงข้อมูลใกล้เคียงกับระยะเวลาในการเข้าถึงข้อมูลของแคช โดยไปเพิ่มจำนวนของ gates ที่เกี่ยวข้องกับการค้นหาตำแหน่งข้อมูลในแคช ผลที่เกิดขึ้นทำให้แคชมีขนาดใหญ่ขึ้น ทำงานช้าลง และเนื้อที่บนแผงวงจรก็เป็นส่วนหนึ่งที่บังคับขนาดของแคช ให้มีขนาดที่จำกัด เนื่องจากประสิทธิภาพของแคช มีความเกี่ยวข้องอย่างใกล้ชิดกับลักษณะของงาน จึงเป็นไปได้ยากที่จะคำนวณขนาดที่เหมาะสมที่สุดของแคชสำหรับในทุกกรณี
การทำ Mapping ระหว่าง cache และ main memory จะมีผลต่อประสิทธิภาพของ cache
รูปแบบการแทนที่บน Line ของ cache
การเขียนข้อมูลบน Cache
ขนาดของ Block
จำนวนและชนิดของ Cache
Mapping functions มีด้วยกัน 3 รูปแบบ คือ Direct Mapping, Association mapping และ set association
1. Direct Mapping
เป็นวิธีการที่ง่าย ตรงไปตรงมา
แต่ละ Block บน main memory จะว่างบน line เฉพาะตามสมาการ
I = j mod C
เมื่อ I คือ line number ที่ block j จาก main memory วาง
ตัวอย่างเช่น
บน Main memory มีจำนวน block ทั้งหมด 64 blocks ซึ่งแต่ละ block สามารถใช้ block address จำนวน 6 bit ในการระบุตำแหน่ง ได้มาจากสองยกกำลังหกเท่ากับ 64
Block 0 มี address เท่ากับ 0 0 0 0 0 0
Block 1 มี address เท่ากับ 0 0 0 0 0 1
Block 2 มี address เท่ากับ 0 0 0 0 1 0
Block 3 มี address เท่ากับ 0 0 0 0 1 1
“
Block 63 มี address เท่ากับ 1 1 1 1 1 0
และบน cache มี 4 lines สามารถระบุตำแหน่งได้ 2 bit ก็แสดงว่าต้องทำการ mod ระหว่าง ตำแหน่ง block กับจำนวน line บน cache เช่น block 0 จะเท่ากับ 0/4 เหลือเศษ 0 , block 1 จะเท่ากับ 1/4 เหลือเศษ 1 , block 2 จะเท่ากับ 2/4 เหลือเศษ 2 , block 3 จะเท่ากับ 3/4 เหลือเศษ 3 เป็นต้น โดยเศษที่เหลือจะใช้เป็นตัวระบุตำแหน่ง line ที่ block ลำดับนั้นจะไปวาง ซึ่งวิธีนี้ก็จะมี block ที่มี address เดียวกันบน cache จำนวนมาก หาก main memory มีขนาดใหญ่กว่า cache มากๆ หรือตัว cache เองมีขนาดเล็กมาก หากสังเกตดีๆ เศษที่เหลือจากการหารจะเท่ากับ 2 bit สุดท้ายของแต่ละ block address
การทำ direct mapping จะแบ่ง block address ของ main memory ออกเป็น 3 ส่วนด้วยกันคือ tag ID, Line ID, และ word ID (offset)
Word ID จะบอกตำแหน่งของแต่ละ word ใน cache line ที่ถูกอ่าน
Line ID จะบอก ตำแหน่งของตำแหน่งอ้างอิง
Tag จะเก็บใน cache ไปพร้อมๆกับข้อมูล word ในแต่ละ line
ข้อดีของ direct mapping
ทำงานง่าย
ติดตั้งง่าย
ไม่แพง
ข้อเสียของ direct mapping
direct mapping จะมีปัญหาเรื่อง locality of reference ซึ่งเกิดจากกำหนด reference line number จากการ mod ทำให้ block address เกิดการ fixed location อาจเกิดปัญหาการเรียกใช้งาน block address ที่วางบน line เดียวกัน มาใช้งานพร้อมกัน จะทำให้เกิดภาวะ swap in /swap out ทำให้ main memory ทำงานช้าลงจากการกำหนดตำแหน่งคงที่ หากเกิดมีการอ้างอิงถึงข้อมูลจากสองบล็อก (หรือมากกว่า) ที่อยู่ในตำแหน่งที่ต่างกันในหน่วยความจำหลัก แต่ บังเอิญอยู่ในตำแหน่งเดียวกันในแคชแล้ว ข้อมูลทั้งสองบล็อกนั้นจะต้องสลับเปลี่ยนกันถูกคัดลอกเข้ามาไว้ในแคชที่ ตำแหน่งเดียวกันเสมอ ทั้งๆที่แคชส่วนอื่นอาจไม่มีข้อมูลอยู่เลยก็ได้ ปรากฏการณ์นี้เรียกว่า “trashing”
ตัวอย่างการคำนวณ
Memory size 16 MB = 2^24 จะสามารถระบุตำแหน่งโดยใช้ 24 bits address
Cache size 16 K line แต่ละ line มี 4 bytes แสดงว่า word id สามารถระบุตำแหน่งโดยใช้ 4=2^2 จำนวนบิตเท่ากับ 2 และระบุตำแหน่ง line number บน cache ได้เท่ากับ 16k = 2^14 ก็ใช้ 14 bits
ขนาดของ line = block ; ซึ่งมีขนาดของบิตที่ใช้ระบุตำแหน่งเท่ากับ 16MB = 2^24 จะใช้ 24 bits address
Block address 24 bits = Tag ? bits + Line id 14bits + Word id 2 bits
Tag = 24-14-2 = 8 bits
direct mapping
Associative Mapping
จะเป็นการแก้ปัญหา เรื่อง การไม่ยืดหยุ่นของ Direct mapping เกี่ยวกับ locality of reference โดยจะไม่มี field ของ Line ID มีเฉพาะ Tag กับ Word ID ส่วนของ line number จะมีไม่ได้ใช้ในการค้นหาอีก ซึ่งจะทำให้ Tag มีความยาวมากขึ้นเท่ากับ block address เพราะต้องใช้ระบุตำแหน่งที่มาของ block จึงทำให้ line มีความยาวมากขึ้น ความยาวของ line ยาวกว่าdirect mapping เมื่อพิจารณากรณี cache มีขนาดใหญ่ขึ้นจะทำให้การทำงานช้าลง
หลักการทำงาน
เมื่อซีพียูส่ง word address มาที่ cache และ cache controller จะแบ่ง field ออกเป็นสองส่วน โดยส่วนแรกจะเป็น tag และส่วนที่สอง word id
ลำดับแรกจะทำการเปรียบเทียบ tag บน line ซึ่งจะทำงานแบบขนานกัน โดย cache จะมี comparator เท่ากับจำนวน line บน cache เมื่อ hit cache ก็จะทำการค้น word ต่อไปและส่งให้ซีพียู แต่ถ้า miss cache จะไปค้นที่ main memory และส่งให้ซีพียู พร้อมกับคัดลอกมาไว้ที่ cache การจะเลือกว่าจะวางไว้ที่ line ใดนั้น ส่วนใหญ่จะเลือก line ที่ไม่ค่อยได้ใช้หรือมีโอกาสถูกใช้น้อยที่สุดในระยะเวลาอันใกล้
ข้อดีของ Associative mapping
ทำงานได้เร็วเนื่องจากมีการทำงานแบบขนานกันไป
มีความยืดหยุ่นเรื่องของการวางตำแหน่ง Block address บน line
ข้อเสียของ Associative mapping
ค่าใช้จ่ายสูงเนื่องจากจำนวนของ Comparator มากเท่ากับจำนวน line
เปลือง Memory เนื่องจาก line มีความยาวมาก
Set associative mapping
เนื่องจากต้องการแก้ไขข้อด้อยของแต่ละวิธีข้างต้น จึงนำข้อดีของแต่ละวิธีมาผสมผสานกัน
หลักการทำงาน
บน Cache จะแบ่ง line ออกเป็นกลุ่มๆ เรียกว่า set ซึ่งแต่ละ set จะมีจำนวน Line แตกต่างกัน จำนวน line ที่อยู่ในกลุ่มก็เอาไว้เรียกชื่อ เช่น 2-way set associative mapping คือหนึ่ง set มี 2 line เป็นต้น
การแบ่ง Word address โดย cache controller ก็จะแบ่งออกเป็น 3 field คล้ายกับ direct mapping เพียงเปลี่ยนส่วนของ line id เป็น set id ซึ่งหลักการในการระบุตำแหน่งการวาง block address จะเหมือนกัน เพียงแต่จากจำนวน line มาเป็น mod ด้วย จำนวน set แทน
Line number = Block addr. Mod Set
Block addr 8 และ cache set 4 set (จำนวนเซตบนแคชทั้งหมด)
Line number = 8 mod 4 =0 ( 8/4 เหลือเศษ 0 ; line number = 0)
ลำดับถัดไป เมื่อค้นหา set id ได้แล้ว ก็จะทำการค้นหา tag ด้วยการใช้ associative search โดย cache controller จะมี comparator เท่ากับจำนวน line ใน set ของ cache ค้นหาแบบขนานกันไป ถ้า hit cache ก็ส่งข้อมูลให้ซีพียู แต่ถ้า miss cache ก็ไปค้นใน main memory เมื่อเจอก็ส่งให้ซีพียู และคัดลอกมาไว้ที่ cache บน set เดิมที่ค้นไม่เจอ แต่จะแทนที่ตามแบบของ association mapping อาจจะใช้ line replacement algorithm ตามความเหมาะสม
ตัวอย่างการคำนวณ
Memory size 16 MB = 2^24 จะสามารถระบุตำแหน่งโดยใช้ 24 bits address
Cache size 16 K line เป็น 4-way set association mapping แต่ละ line มี 4 bytes แสดงว่า word id สามารถระบุตำแหน่งโดยใช้ 4=2^2 จำนวนบิตเท่ากับ 2 ขนาดของ line = block ; ซึ่งมีขนาดของบิตที่ใช้ระบุตำแหน่งเท่ากับ 16MB = 2^24 จะใช้ 24 bits address
Block address 24 bits = Tag ? bits + Set id ? bits + Word id 2 bits
Set = 16K/4 = 4K = 2^12 ; Set id = 12 bits
Tag = 24-12-2 = 10 bits
Line replacement algorithms
กรณีที่ Association mapping หรือ set association mapping ที่ line บน cache เต็ม จะต้องมีวิธีในการแทนที่เมื่อต้องการใช้ข้อมูล ซึ่งปัญหานี้ไม่เกิดกับ direct mapping เนื่องจากแต่ละ block ถูกกำหนดตำแหน่งการวางไว้แล้ว
การแทนที่นั้นมีรูปแบบต่างๆ ประกอบด้วย 4 แบบ ดังนี้
1. Least recently used (LRU) หมายถึงการแทนที่ตรงตำแหน่งที่มีอายุมากที่สุดบนแคช ปัญหาคือเราจะทราบได้อย่างไรว่า ไลน์ไหนเก่าที่สุด ต้องมีการบันทึกหรือให้ข้อมูลการทำงานของแต่ละไลน์เพิ่มเติมเพื่อเป็นการตัดสินใจ
2. First In First Out (FIFO) หมายถึงการทำงานแบบคิว มาก่อนออกก่อน ซึ่งการทำงานแบบนี้ไม่สนับสนุน hit rate และไม่เหมาะกับลักษณะโปรแกรมในปัจจุบัน ถึงแม้จะตรงตามหลักการของ Von Nuemann ก็ตาม
3. Least Frequently used (LFU) หมายถึงตำแหน่งมีความถี่ในการใช้งานน้อยสุดจะถูกแทนที่ แต่เอาเข้าจริงๆ แล้วยากในทางปฏิบัติ เนื่องจากต้องมีการเก็บข้อมูลโดยใช้ตัวนับ ซึ่งจะต้องใช้หน่วยความจำ และต้องมีการออกแบบเพื่อให้สามารถเก็บข้อมูลให้เพียงพอ เพราะปัญหาคือการเก็บข้อมูลไม่เพียงพอทำให้ไม่สามารถเปรียบเทียบหาตัวที่ค่าการใช้งานน้อยที่สุดได้
4. Random หมายถึงการสุ่ม ซึ่งไม่การันตี hit rate เลย
ไม่มีความคิดเห็น:
แสดงความคิดเห็น