การระบุแอดเดรสตามลำดับ

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

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

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

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

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

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

ในแต่ละขั้นจะมีเพียงเธรดครึ่งล่างเท่านั้นที่ทำงาน ซึ่งเขียนเป็น tid < s วิธีนี้ทำให้เธรดที่ทำงานอยู่เรียงต่อเนื่องกัน และวาร์ปก็ไม่เกิดการแตกแขนงเช่นกัน

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

คุณยังคงต้องเรียกใช้ __syncthreads หลังแต่ละขั้น เธรดต้องมองเห็นการเขียนของระดับก่อนหน้า ก่อนจะอ่านข้อมูลสำหรับระดับถัดไป

เมื่อระยะก้าวลดลงครึ่งหนึ่งจนเข้าใกล้ศูนย์ ผลรวมย่อยทั้งหมดจะถูกรวมเข้าที่ data[0] จากนั้นเธรด 0 จะเขียนผลลัพธ์ของบล็อกนั้นกลับไปยังหน่วยความจำส่วนกลาง

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

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