การนับแคชที่ขาดหายไปในโครงสร้างข้อมูล

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

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

สมมติว่ามีคอมพิวเตอร์รุ่นธรรมดาที่หน่วยความจำของคอมพิวเตอร์ประกอบด้วยแคช L1, แคช L2 และหน่วยความจำหลัก เราดำเนินการทางคณิตศาสตร์และตรรกะโดยใช้ ALU ใน data resident ใน register (R)

นี่คือบล็อกไดอะแกรมของมัน -

จากไดอะแกรม เรายังสามารถรับความรู้เกี่ยวกับขนาดของหน่วยความจำและแคชได้อีกด้วย หน่วยความจำหลักนั้นโดยทั่วไปแล้วมีหลายร้อยหรือหลายพัน MB โดยที่แคช L2 เป็นเพียงเศษเสี้ยวของ MB และแคช L1 คือ KB บางส่วน ขนาดรีจิสเตอร์เป็นบิต เมื่อเรารันโปรแกรม ข้อมูลทั้งหมดในหน่วยความจำ หากเราเพิ่มการดำเนินการบางอย่างเช่น ADD หมายเลขแรกจะถูกเก็บไว้ในรีจิสเตอร์ ข้อมูลในรีจิสเตอร์จะถูกเพิ่ม จากนั้นผลลัพธ์จะถูกเขียนลงในหน่วยความจำ

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