การดึงข้อมูลแคชล่วงหน้าเป็นเทคนิคที่หน่วยประมวลผลกลาง (CPU) ใช้เพื่อเพิ่มประสิทธิภาพการทำงานโดยการดึงคำสั่งหรือข้อมูลจากหน่วยความจำหลักหรือหน่วยความจำที่ทำงานช้ากว่าไปยังหน่วยความจำเฉพาะที่ที่เร็วกว่าก่อนที่จะต้องการใช้งานจริง^{[ 1 ] [ 2 ]} CPU สมัยใหม่ส่วนใหญ่มีหน่วยความจำแคช ที่รวดเร็วและเฉพาะ ที่ซึ่งเก็บข้อมูลที่ดึงมาล่วงหน้าไว้จนกว่าจะต้องการใช้งาน แหล่งที่มาของการดำเนินการดึงข้อมูลล่วงหน้ามักจะเป็นหน่วยความจำหลักเนื่องจากลักษณะการออกแบบ การเข้าถึงหน่วยความจำแคชจึงมักจะเร็วกว่าการเข้าถึงหน่วยความจำหลักมาก การดึงข้อมูลล่วงหน้าสามารถทำได้ด้วยคำสั่งควบคุมแคช แบบไม่บล็อก การดึง ข้อมูล ล่วงหน้าขึ้นอยู่กับหลักการของความใกล้เคียงของข้อมูล

การดึงข้อมูลล่วงหน้าจากแคชสามารถดึงข้อมูลหรือคำสั่งเข้าไปในแคชได้

• การดึงข้อมูลล่วงหน้า (Data prefetching)คือการดึงข้อมูลก่อนที่จะมีความจำเป็นต้องใช้ เนื่องจากรูปแบบการเข้าถึงข้อมูลมีความสม่ำเสมอน้อยกว่ารูปแบบคำสั่ง การดึงข้อมูลล่วงหน้าอย่างแม่นยำจึงมักมีความท้าทายมากกว่าการดึงคำสั่งล่วงหน้า
• การดึงคำสั่ง ล่วงหน้า (Instruction prefetching)คือการดึงคำสั่งมาก่อนที่จะต้องนำไปประมวลผล ไมโครโปรเซสเซอร์หลักรุ่นแรกๆ ที่ใช้เทคนิคการดึงคำสั่งล่วงหน้า ได้แก่Intel 8086 (หกไบต์) และMotorola 68000 (สี่ไบต์) ในช่วงไม่กี่ปีมานี้ โปรเซสเซอร์ประสิทธิภาพสูงทั้งหมดใช้เทคนิคการดึงคำสั่งล่วงหน้าแล้ว

การดึงแคชล่วงหน้าสามารถทำได้โดยฮาร์ดแวร์หรือซอฟต์แวร์^{[ 3 ]}

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

• บัฟเฟอร์สตรีมได้รับการพัฒนาขึ้นโดยอิงตามแนวคิดของ "รูปแบบการมองล่วงหน้าหนึ่งบล็อก (OBL)" ที่เสนอโดยAlan Jay Smith ^{[ 1 ]}
• บัฟเฟอร์สตรีมเป็นหนึ่งในเทคนิคการดึงข้อมูลล่วงหน้าแบบฮาร์ดแวร์ที่ใช้กันทั่วไป เทคนิคนี้ได้รับการเสนอครั้งแรกโดยNorman Jouppiในปี 1990 ^{[ 6 ]}และมีการพัฒนาวิธีการนี้ในรูปแบบต่างๆ มากมายตั้งแต่นั้นมา^{[ 7 ] [ 8 ] [ 9 ]}แนวคิดพื้นฐานคือ ที่ อยู่ แคชพลาด (และ ที่อยู่ถัดไป kที่อยู่) จะถูกดึงไปยังบัฟเฟอร์แยกต่างหากที่มีความลึกkบัฟเฟอร์นี้เรียกว่าบัฟเฟอร์สตรีมและแยกจากแคช จากนั้นโปรเซสเซอร์จะใช้ข้อมูล/คำสั่งจากบัฟเฟอร์สตรีมหากที่อยู่ที่เกี่ยวข้องกับบล็อกที่ดึงมาล่วงหน้าตรงกับที่อยู่ร้องขอที่สร้างโดยโปรแกรมที่กำลังทำงานบนโปรเซสเซอร์ รูปด้านล่างแสดงการตั้งค่านี้:

• เมื่อใดก็ตามที่กลไกการดึงข้อมูลล่วงหน้าตรวจพบการพลาดในบล็อกหน่วยความจำ เช่น บล็อกAมันจะจัดสรรสตรีมเพื่อเริ่มต้นการดึงข้อมูลล่วงหน้าบล็อกถัดไปจากบล็อกที่พลาดไป หากบัฟเฟอร์สตรีมสามารถเก็บได้ 4 บล็อก โปรเซสเซอร์จะดึงข้อมูลล่วงหน้าA +1, A +2, A +3, A +4 และเก็บไว้ในบัฟเฟอร์สตรีมที่จัดสรรไว้ หากโปรเซสเซอร์ใช้A +1 ในครั้งต่อไป มันจะถูกย้าย "ขึ้น" จากบัฟเฟอร์สตรีมไปยังแคชของโปรเซสเซอร์ รายการแรกของบัฟเฟอร์สตรีมจะเป็นA +2 และต่อไปเรื่อยๆ รูปแบบการดึงข้อมูลล่วงหน้าบล็อกถัดไปนี้เรียกว่าการดึงข้อมูลล่วงหน้าแบบลำดับ (Sequential Prefetching ) ส่วนใหญ่จะใช้เมื่อต้องการดึงข้อมูลล่วงหน้าในตำแหน่งที่อยู่ติดกัน ตัวอย่างเช่น ใช้ในการดึงข้อมูลล่วงหน้าคำสั่ง
• กลไกนี้สามารถขยายขนาดได้โดยการเพิ่มบัฟเฟอร์สตรีมดังกล่าวหลายตัว ซึ่งแต่ละตัวจะรักษาสตรีมพรีเฟตช์แยกต่างหาก^{[ 10 ]}สำหรับการพลาดแต่ละครั้ง จะมีการจัดสรรบัฟเฟอร์สตรีมใหม่ และจะทำงานในลักษณะที่คล้ายคลึงกันดังที่ได้อธิบายไว้ข้างต้น
• ความลึกที่เหมาะสมของบัฟเฟอร์สตรีมขึ้นอยู่กับการทดลองกับเกณฑ์มาตรฐานต่างๆ^{[ 6 ]} และขึ้นอยู่กับ สถาปัตยกรรมไมโครส่วนที่เหลือที่เกี่ยวข้อง^{[ 11 ]}

การดึงข้อมูลล่วงหน้าประเภทนี้จะตรวจสอบความแตกต่างระหว่างที่อยู่ของหน่วยความจำที่เข้าถึง และมองหารูปแบบภายในความแตกต่างนั้น

ในรูปแบบนี้ การเข้าถึงหน่วยความจำที่ต่อเนื่องกันจะเกิดขึ้นกับบล็อกที่อยู่ ห่างกัน sแอดเดรส^{[ 3 ] [ 12 ]}ในกรณีนี้ ตัวดึงข้อมูลล่วงหน้าจะคำนวณค่าsและใช้เพื่อคำนวณแอดเดรสหน่วยความจำสำหรับการดึงข้อมูลล่วงหน้า ตัวอย่างเช่น ถ้าs = 4แอดเดรสที่จะดึงข้อมูลล่วงหน้าจะเป็นA +4

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

คลาสของพรีเฟตเชอร์นี้จะมองหาสตรีมการเข้าถึงหน่วยความจำที่ซ้ำกันเมื่อเวลาผ่านไป^{[ 15 ] [ 16 ]}ตัวอย่างเช่น ในสตรีมการเข้าถึงหน่วยความจำ N, A, B, C, E, G, H, A, B, C, I, J, K, A, B, C, L, M, N, O, A, B, C, ...; สตรีม A, B, C จะซ้ำกันเมื่อเวลาผ่านไป รูปแบบการออกแบบอื่นๆ ได้พยายามนำเสนอการใช้งานที่มีประสิทธิภาพมากขึ้น^{[ 17 ] [ 18 ]}

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

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

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

ข้อดีหลักประการหนึ่งของการดึงข้อมูลล่วงหน้าด้วยซอฟต์แวร์คือช่วยลดจำนวนแคชพลาดที่จำเป็น^{[ 3 ]}

ตัวอย่างต่อไปนี้แสดงการเพิ่มคำสั่งดึงข้อมูลล่วงหน้า (prefetch) เข้าไปในโค้ดเพื่อปรับปรุงประสิทธิภาพของแคช

ในการทำซ้ำครั้งต่อไป

สำหรับ( size_t i = 0 ; i < 1024 ; ++ i ) { array1 [ i ] *= 2 ; }

มีการเข้าถึง องค์ประกอบi^{ที่ i}ของอาร์เรย์array1ระบบสามารถดึงข้อมูลล่วงหน้าขององค์ประกอบที่คาดว่าจะถูกเข้าถึงในรอบการทำงานถัดไปได้โดยการแทรกคำสั่งดึงข้อมูลล่วงหน้าดังแสดงด้านล่าง:

สำหรับ( size_t i = 0 ; i < 1024 ; ++ i ) { prefetch ( array1 [ i + k ]); array1 [ i ] *= 2 ; }

ในที่นี้ ระยะการดึงข้อมูลล่วงหน้า (prefetch stride) kขึ้นอยู่กับสองปัจจัย คือ ค่าปรับจากการพลาดแคช (cache miss penalty) และเวลาที่ใช้ในการวนซ้ำหนึ่งรอบของลูป for ตัวอย่างเช่น หากการวนซ้ำหนึ่งรอบใช้เวลา 7 รอบ และค่าปรับจากการพลาดแคชคือ 49 รอบ ดังนั้น k ควรมีค่าเท่ากับ 49/7 = 7 ซึ่งหมายความว่าระบบควรดึงข้อมูลล่วงหน้า 7 องค์ประกอบ ในการวนซ้ำครั้งแรก ค่าของ k iจะเป็น 0 ดังนั้นระบบจึงดึงข้อมูลล่วงหน้าองค์ประกอบที่ 7 ด้วยการจัดเรียงนี้ การเข้าถึง 7 ครั้งแรก ( i= 0 → 6) จะยังคงเป็นการเข้าถึงพลาดแคช (ภายใต้สมมติฐานแบบง่ายๆ ว่าแต่ละองค์ประกอบของ k array1อยู่ในบรรทัดแคชที่แยกจากกัน)

• ในขณะที่การดึงข้อมูลล่วงหน้าด้วยซอฟต์แวร์ต้องอาศัยการแทรกแซงจากโปรแกรมเมอร์หรือคอมไพเลอร์การดึงข้อมูลล่วงหน้าด้วยฮาร์ดแวร์ต้องอาศัยกลไกฮาร์ดแวร์พิเศษ^{[ 3 ]}
• การดึงข้อมูลล่วงหน้าด้วยซอฟต์แวร์จะทำงานได้ดีเฉพาะกับลูปที่มีการเข้าถึงอาร์เรย์เป็นประจำเท่านั้น เนื่องจากโปรแกรมเมอร์ต้องเขียนโค้ดคำสั่งดึงข้อมูลล่วงหน้าด้วยตนเอง ในขณะที่ตัวดึงข้อมูลล่วงหน้าด้วยฮาร์ดแวร์จะทำงานแบบไดนามิกตามพฤติกรรมของโปรแกรมในระหว่างการทำงาน^{[ 3 ]}
• การดึงข้อมูลล่วงหน้าด้วยฮาร์ดแวร์ยังใช้ทรัพยากร CPU น้อยกว่าเมื่อเทียบกับการดึงข้อมูลล่วงหน้าด้วยซอฟต์แวร์^{[ 22 ]}อย่างไรก็ตาม การดึงข้อมูลล่วงหน้าด้วยซอฟต์แวร์สามารถลดข้อจำกัดบางประการของการดึงข้อมูลล่วงหน้าด้วยฮาร์ดแวร์ ซึ่งนำไปสู่การปรับปรุงประสิทธิภาพ^{[ 23 ]}

การดึงข้อมูลแคชล่วงหน้าสามารถประเมินได้จากตัวชี้วัดหลักสามประการ^{[ 3 ]}

อัตราการครอบคลุม คือ สัดส่วนของจำนวนการพลาดทั้งหมดที่ถูกกำจัดออกไปเนื่องจากการดึงข้อมูลล่วงหน้า กล่าวคือ

ความคุ้มครอง = ⁠การพลาดแคชถูกกำจัดด้วยการดึงข้อมูลล่วงหน้า/จำนวนแคชพลาดทั้งหมด⁠ ,

ที่ไหน

จำนวนแคชพลาดทั้งหมด = (แคชพลาดที่ถูกกำจัดโดยการดึงข้อมูลล่วงหน้า) + (แคชพลาดที่ไม่ได้ถูกกำจัดโดยการดึงข้อมูลล่วงหน้า)

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

ความแม่นยำในการดึงข้อมูลล่วงหน้า = ⁠การพลาดแคชถูกกำจัดด้วยการดึงข้อมูลล่วงหน้า/(การดึงข้อมูลแคชล่วงหน้าที่ไร้ประโยชน์) + (การลดการพลาดแคชด้วยการดึงข้อมูลล่วงหน้า)⁠

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

นิยามเชิงคุณภาพของความทันเวลาคือ ระยะเวลาที่ผ่านไปนับตั้งแต่การดึงข้อมูลล่วงหน้าจนถึงการอ้างอิงจริง ตัวอย่างเช่น เพื่อให้การดึงข้อมูลล่วงหน้ามีประโยชน์ในลูป forที่แต่ละรอบใช้เวลาสามรอบการทำงาน และการดึงข้อมูลล่วงหน้าใช้เวลาสิบสองรอบการทำงาน ระบบจะต้องเริ่มการดึงข้อมูลล่วงหน้า 12/3 = 4 รอบการทำงานก่อนที่จะใช้งานจริง เพื่อรักษาความทันเวลา

• ดึงข้อมูลล่วงหน้าเข้าคิว
• การดึงลิงก์ล่วงหน้า
• ตัวดึงข้อมูลล่วงหน้า
• คำสั่งควบคุมแคช