กำจัดการแยกทางของวาร์ป

วาร์ป คือเธรด 32 ตัวที่ทำงานตามคำสั่งเดียวกันพร้อมกัน เมื่อเส้นทางการทำงานของเธรดสอดคล้องกัน ฮาร์ดแวร์จะทำงานได้เต็มความเร็ว

หากเธรดในวาร์ปเลือกแขนงต่างกัน นั่นเรียกว่า การแยกเส้นทาง ฮาร์ดแวร์จะทำงานแต่ละเส้นทางตามลำดับ ทำให้บางเลนไม่ได้ทำงานและเสียรอบการทำงานไป

เวอร์ชันแบบง่ายใช้ tid % (2*s) เพื่อเลือกเธรดที่ทำงาน เธรดที่ทำงานและเธรดที่ว่างจะแทรกสลับกันภายในทุกวาร์ป วาร์ปแต่ละอันจึงเกิดการแยกเส้นทางอย่างมาก

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

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

ตอนนี้เธรดที่ทำงานอยู่จะ ต่อเนื่องกัน: tid 0,1,2,... ทำงานทั้งหมด ส่วนที่เหลือจะหยุดพัก วาร์ปทั้งวาร์ปจึงทำงานเต็มที่หรือว่างทั้งหมด

วาร์ปที่ทุกเลนว่างจะจบการทำงานโดยไม่ต้องทำงานใด ๆ ไม่มีการทำงานแบบอนุกรมแยกตามเลน ดังนั้นต้นทุนจากการแยกเส้นทางจึงหายไปเกือบทั้งหมด

ตัวร้ายที่ซ่อนอยู่คือเงื่อนไข การหาเศษ เงื่อนไขนี้กระจายเธรดที่ทำงานอยู่ไปทั่วแต่ละวาร์ป ซึ่งเป็นสาเหตุโดยตรงของการแยกเส้นทาง

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

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

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

ลองคิดดูว่าอะไรเป็นสาเหตุให้เกิดการแยกเส้นทางของวาร์ปในการลดรูปแบบพื้นฐาน

คุณกำจัดการแตกแขนงได้ด้วยการมอบงานให้กับ เธรดที่มี ID ต่ำที่สุด ทำให้วาร์ปทำงานทั้งหมดหรือหยุดทำงานทั้งหมด คณิตศาสตร์เหมือนเดิม แต่การลดค่าทำได้เร็วขึ้น ต่อไปคือความขัดแย้งของแบงก์ 🚀