การทำนายสาขาคืออะไร?

ในโปรแกรมคอมพิวเตอร์เกือบทุกโปรแกรม มีโค้ดบางส่วนที่แยกย่อยเป็นพาธ ตัวอย่างเช่น คำสั่ง if-then-else มีสองผลลัพธ์ที่เป็นไปได้ คำสั่งเหล่านี้ไม่ได้นำเสนอปัญหาใดๆ ต่อโปรเซสเซอร์ตามลำดับ เนื่องจาก CPU ประมวลผลทุกคำสั่งตามลำดับ แบรนช์เป็นปัญหาใหญ่สำหรับตัวประมวลผลแบบไปป์ไลน์ เนื่องจากมีการดำเนินการคำสั่งหลายคำสั่งพร้อมกัน

สถานการณ์

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

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

เหตุใดจึงเป็นปัญหา

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

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

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

ปัญหานี้ได้รับการแก้ไขแล้วอย่างไร

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

หากตัวทำนายสาขาทำผิดพลาด คุณต้องล้างไปป์ไลน์และเริ่มประมวลผลผลลัพธ์จริง สิ่งนี้ส่งผลให้มีบทลงโทษด้านประสิทธิภาพที่แย่กว่าการไม่ได้ทำอะไรเลยและเพียงแค่รอผลเท่านั้น เพื่อให้ได้ประสิทธิภาพที่ดีที่สุด สิ่งสำคัญคือต้องตรวจสอบให้แน่ใจว่าตัวทำนายสาขามีความแม่นยำมากที่สุด มีหลากหลายแนวทางในเรื่องนี้

จับคู่รหัส

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

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

ตัวทำนายสาขาแบบไดนามิก

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

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

รูปแบบการติดตาม

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

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

บทสรุป

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

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