ทริกฐาน 2^51 (2017)

 (chosenplaintext.ca)
1 คะแนน โดย GN⁺ 2025-05-31 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • การบวกจำนวนเต็มขนาดใหญ่มักทำโดยแบ่งออกเป็น limb ขนาด 64 บิต แต่เมื่อเกิดการแพร่กระจายของตัวทด จะใช้ประโยชน์จากการประมวลผลแบบขนานของ CPU สมัยใหม่ได้ไม่เต็มที่
  • adc ของ x86 พึ่งพา carry flag จากการดำเนินการก่อนหน้า ทำให้เชนคำสั่งถูกทำให้เป็นลำดับต่อเนื่อง จึงกลายเป็นคอขวดแม้บนสถาปัตยกรรมอย่าง Intel Haswell ที่สามารถรัน add หลายคำสั่งแบบขนานได้
  • การแทนค่าแบบ radix 2^51 แบ่งค่า 256 บิตออกเป็นหลักฐาน 2^51 จำนวนห้าหลัก แทนที่จะเป็นหลักฐาน 2^64 จำนวนสี่หลัก และใช้บิตส่วนบนที่เหลือของแต่ละ limb เป็นพื้นที่เก็บตัวทดระหว่างทาง
  • ไม่ใช่วิธีที่กำจัดตัวทด แต่เป็นการ หน่วงการแพร่กระจาย ระหว่างการบวกหลายครั้ง แล้วค่อยจัดการทั้งหมดพร้อมกันในขั้นตอน normalization สุดท้าย
  • ในเบนช์มาร์กง่าย ๆ บน Haswell แม้รวมต้นทุนการแปลงแล้ว ก็เร็วกว่า radix 2^64 ตั้งแต่ การบวกสามครั้ง เป็นต้นไป และยิ่งจำนวนรอบเพิ่มขึ้น ประโยชน์ก็ยิ่งมากขึ้น

ทำไมตัวทดจึงเป็นคอขวดในการบวกจำนวนเต็มขนาดใหญ่

  • การบวกยาวบนกระดาษทำจากหลักหน่วย โดยไล่จากขวาไปซ้าย
    • เพราะผลลัพธ์ของแต่ละหลักขึ้นอยู่กับ ตัวทด ที่ส่งมาจากหลักทางขวา
    • หากบวกจากซ้ายก่อน ตัวทดที่เกิดขึ้นทีหลังอาจทำให้ต้องกลับไปแก้ผลลัพธ์ของหลักหน้าที่คำนวณไปแล้ว
  • การบวกจำนวนเต็มขนาดใหญ่ก็มีข้อจำกัดแบบเดียวกัน
    • หากแบ่งจำนวนเต็ม 256 บิต x และ y ออกเป็น limb ขนาด 64 บิตสี่ตัว ก็สามารถบวก limb ที่อยู่ตำแหน่งเดียวกันเข้าด้วยกันได้
    • ถ้า limb ต่ำเกิด overflow จะต้องส่งค่า 1 นั้นต่อไปยัง limb ที่สูงกว่า
  • adc ของ x86 คือคำสั่งที่จัดการการแพร่กระจายนี้
    • มันดูว่าการดำเนินการก่อนหน้า overflow หรือไม่ และบวก 1 เพิ่มเมื่อจำเป็น
    • การบวก 256 บิตที่ถูกต้องจึงเรียงจาก limb ต่ำสุดเป็น add, adc, adc, adc

โครงสร้างที่ทำให้ adc ช้าบน CPU สมัยใหม่

  • โดยทั่วไป adc มีต้นทุนการรันสูงกว่า add ปกติ
    • adc ใช้อินพุตที่สามคือ carry flag จึงซับซ้อนกว่า add
    • เนื่องจากถูกใช้น้อยกว่า add ผู้ออกแบบ CPU จึงมีแรงจูงใจน้อยกว่าในการทุ่มพื้นที่ชิปเพื่อปรับประสิทธิภาพ adc
  • ปัญหาที่ใหญ่กว่าคือ การพึ่งพากันของคำสั่ง
    • บน Intel Haswell คำสั่ง add เดี่ยวใช้เวลา execute 1 cycle
    • ภายใต้เงื่อนไขที่เหมาะสม Haswell สามารถ execute add ได้สูงสุด 4 คำสั่งต่อ cycle
    • Haswell มี execution port 8 พอร์ต และในนั้นมี 4 พอร์ตที่สามารถ execute add จำนวนเต็มได้
  • add อิสระสี่คำสั่งมักรันแบบขนานได้ง่าย
    • ในทางกลับกัน เชน adc แต่ละคำสั่งพึ่งพาเอาต์พุต carry flag ของคำสั่งก่อนหน้า
    • CPU ไม่สามารถทำให้คำสั่งเหล่านี้ขนานกันได้ และต้อง execute ตามลำดับ
  • ใน SIMD การสูญเสียยิ่งมากขึ้น
    • vpaddq ทำการบวก 64 บิตสี่รายการพร้อมกัน
    • Haswell สามารถ execute vpaddq ได้สองคำสั่งต่อ cycle
    • หากต้องทิ้งความขนานนี้เพื่อจัดการตัวทด ประโยชน์ด้านประสิทธิภาพก็ลดลง

การหน่วงตัวทดเมื่อมองผ่านการบวกบนกระดาษ

  • หากยังคงค่าประจำหลักแบบฐาน 10 ไว้ แต่ขยายชุดอักขระที่ใส่ในแต่ละหลักได้ ก็สามารถหน่วงตัวทดได้
    • ใช้อักขระทั้งหมด 37 ตัว โดยเพิ่ม A-Z และ * แทนที่จะมีแค่ 0-9 ตามปกติ
    • แต่ตัวฐานเองไม่ใช่ฐาน 37 ยังยังคงเป็น ค่าประจำหลักแบบฐาน 10
  • เมื่อหลักหนึ่งเกิน 9 ก็ไม่จำเป็นต้องทดทันที
    • 29 + 1 เขียนเป็น 30 ได้ แต่ก็แทนได้เป็น 2A, 1K หรือ U เช่นกัน
    • หากแต่ละหลักของตัวเลขสองจำนวนถูก normalize ให้อยู่ไม่เกิน 9 อยู่แล้ว ก็สามารถเลื่อนการทดระหว่างการบวกออกไปได้
  • ไม่ได้ใช้ได้กับอินพุตทุกแบบเสมอไป
    • หากมีค่าหลักที่ใหญ่อยู่แล้ว เช่น 9 + W ก็จำเป็นต้องทด
    • สำหรับตัวเลขที่ normalize แล้ว สามารถบวกได้สูงสุดสี่จำนวนโดยไม่ต้องทด
  • ท้ายที่สุดต้อง normalize กลับเป็นการแทนค่าแบบฐาน 10 ปกติ
    • คำนวณจากด้านขวาว่าแต่ละหลักมีค่า 10 อยู่กี่ชุด
    • ลบจำนวนนั้นออกจากหลักปัจจุบัน แล้วส่งต่อไปยังหลักถัดไป
  • แก่นสำคัญไม่ใช่การกำจัดการแพร่กระจายของตัวทด แต่คือการ เก็บไว้ระหว่างการคำนวณกลางทาง แล้วค่อยแพร่กระจายครั้งเดียวตอนท้าย

การแทนค่า radix 2^51 ในคอมพิวเตอร์

  • หากแบ่งค่า 256 บิตออกเป็น limb ฐาน 2^64 สี่ตัว แต่ละ limb จะมีค่าได้ตั้งแต่ 0 ถึง 2^64−1
    • นี่คือการมองแต่ละ limb เป็น หลักของฐาน 2^64
  • เนื่องจากไม่สามารถขยายช่วงจำนวนเต็ม 64 บิตของฮาร์ดแวร์ได้ จึงลดขนาดของฐานลง
    • แบ่งค่า 256 บิตออกเป็น หลักฐาน 2^51 ห้าหลัก แทนที่จะเป็นหลักฐาน 2^64 สี่หลัก
    • แต่ละ limb ยังคงเก็บเป็นจำนวนเต็ม 64 บิต แต่ค่าจริงใช้เพียง 51 บิตหรือ 52 บิต
  • บิตส่วนบนที่เหลือกลายเป็นพื้นที่เก็บตัวทดระหว่างทาง
    • แต่ละ limb เก็บ 51 บิตหรือ 52 บิตของตัวเลขเดิม
    • อีก 12 บิตหรือ 13 บิตที่เหลือใช้บรรจุตัวทดที่เกิดขึ้นระหว่างการคำนวณ
  • เทคนิคนี้ในวรรณกรรมด้านคริปโตกราฟีเรียกว่า radix 2^51 representation
  • หากเป็นจำนวนที่ normalize แล้ว ภายในค่าที่เป็นไปได้ 2^64 ค่าของ limb จะยังไม่ต้องกังวลเรื่อง overflow ของ 13 บิตบน จนกว่าจะบวกรวมกันถึง 2^13 ค่า

limb สูงสุด 52 บิตและการ normalize

  • limb สูงสุดจัดสรรไว้ 52 บิต
    • limb อื่น ๆ ใช้ 51 บิต
    • ตัวทดของ limb สูงสุดจะถูกละทิ้ง เพื่อให้กรณีที่เกิน 2^256−1 ถูกจัดการแบบวนกลับ
    • เหมือนกับวิธีที่การบวกจำนวนเต็ม unsigned ขนาดปกติใน C วนกลับเมื่อ overflow
  • โค้ดบวก radix 2^51 ไม่ใช้เชน adc แต่ execute add ห้าคำสั่งอย่างเป็นอิสระ
    • จำนวน add เพิ่มจาก 4 เป็น 5 เมื่อเทียบกับวิธี limb ฐาน 2^64 สี่ตัว
    • แต่ไม่มีการพึ่งพา carry flag จึงรันแบบขนานได้
  • ในขั้นตอน normalization จะดึงบิตส่วนบนของแต่ละ limb ออกมาแล้วบวกเข้ากับ limb ถัดไปที่สูงกว่า
    • ใช้ shr 51 เพื่อดึงส่วน carry ออกมา
    • ใช้ and 0x0007FFFFFFFFFFFF เพื่อเหลือไว้เฉพาะ 51 บิตล่าง
    • limb สูงสุดจัดระเบียบด้วย and 0x000FFFFFFFFFFFFF
  • normalization คือขั้นตอนสุดท้ายที่ทำการแพร่กระจายตัวทดที่หน่วงไว้
    • ระหว่างการบวกกลางทางจะไม่สร้างการพึ่งพา carry flag
    • สุดท้ายปรับแต่ละ limb ให้กลับเข้าไปอยู่ในช่วงที่อนุญาต

ผลด้านประสิทธิภาพและการขยายไปสู่การลบ

  • ในเบนช์มาร์กง่าย ๆ การบวก radix 2^51 ให้ผลเร็วกว่าเมื่อรันบน CPU Haswell
    • รวมต้นทุนการแปลงเข้าและออกจากการแทนค่า radix 2^51 แล้ว
    • แค่ การบวกสามครั้ง ก็เร็วกว่า radix 2^64 แล้ว
    • ยิ่งจำนวนครั้งของการบวกเพิ่มขึ้น ผลประหยัดก็เพิ่มตามไปด้วย
  • แนวคิดเดียวกันนี้ขยายไปใช้กับการลบได้ด้วย
    • ในการลบ ตัวทดจะกลายเป็น negative carry
  • หากต้องรองรับการลบ ต้องปฏิบัติกับ limb เหมือนเป็นจำนวนเต็ม signed ไม่ใช่ unsigned
    • ค่าประจำแต่ละหลักอาจเป็นบวกหรือลบได้
    • แต่ละ limb สามารถเก็บได้ทั้ง carry บวกและ carry ลบ
  • การเปลี่ยนแปลงนี้มีต้นทุนตามมา
    • บิตสูงสุดของแต่ละ limb ถูกสงวนไว้เป็นบิตเครื่องหมาย
    • จำนวนการดำเนินการที่ทำได้ระหว่างการ normalize ลดจาก 2^13 เหลือ 2^12
  • แม้จะต้องแบ่งข้อมูลลงในรีจิสเตอร์มากขึ้นและจำนวนการดำเนินการเพิ่มขึ้น แต่หากลด การพึ่งพาตัวทด ได้ ประสิทธิภาพโดยรวมก็อาจดีขึ้น

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-05-31
ความคิดเห็นบน Hacker News

  • สงสัยว่าทำไม่ได้หรือ ถ้าให้ limb ระดับบนสุดเป็น 64 บิต และ limb ที่เหลืออีกสี่ตัวเป็นตัวละ 48 บิต
    จะสะสมการบวกได้มากขึ้นก่อน normalize และถ้าชุดคำสั่งมีฟีเจอร์ที่เป็นประโยชน์ ก็อาจใช้ประโยชน์จากการจัดแนว word ตอนแยกและ normalize ได้ แถมลักษณะ overflow ก็ดูเหมือนเดิม

    • ถ้าหนึ่งในเป้าหมายคือการทำงาน 256 บิตด้วย รีจิสเตอร์ 64 บิต 5 ตัว ก็เท่ากับใช้ 256/5 = 51.2 บิตต่อ word จึงดูเป็นการจัดวางที่ค่อนข้างเหมาะที่สุด
      สำหรับไลบรารีจำนวนเต็มขนาดใหญ่แบบทั่วไป อาจไม่ใช่ตัวเลือกที่ดีที่สุด และในอดีตคงไม่มี barrel shifter ที่ทำ arbitrary bit shift ได้มีประสิทธิภาพ จึงน่าจะดีกว่าที่จะใช้ 56 บิตจาก 64 บิต โดยเหลือไว้พอดี 1 ไบต์สำหรับ carry
      RISC-V ไม่มี flag ดังนั้นประเด็นนี้จึงค่อนข้างเกี่ยวข้อง
    • ถ้าบวก limb ระดับบนสุดของตัวเลขที่เข้ารหัสสองตัว จะ overflow เร็วเกินไป
      เช่น ถ้าทั้งคู่เป็น 2^63 ก็ล้นทันที และแม้อาจใช้ได้กับ arithmetic แบบ wrapping แต่ไม่ถูกต้องในกรณีทั่วไป
    • ถ้าทำแบบนั้น จะต้องใช้ 6 word เพื่อเก็บค่า 256 บิต ไม่ใช่ 5 word แบบในบทความต้นฉบับ ดังนั้นจำนวนคำสั่งบวกก็จะเพิ่มขึ้นด้วย

  • ด้วย AVX512 และในระดับหนึ่ง AVX2 ก็สามารถทำ การบวก 256 บิต ได้ค่อนข้างมีประสิทธิภาพ และยังมีข้อดีที่ใส่ตัวเลขในรีจิสเตอร์ได้มากขึ้นด้วย
    ใช้การผสม _mm256_add_epi64, comparison mask และ carry mask โดย throughput ก็ดูดีกว่า: https://godbolt.org/z/e7zETe8xY
    การเปลี่ยนเป็นการบวก 512 บิตก็ไม่ยาก และตอนนั้นส่วนที่ดีขึ้นน่าจะมากกว่า

    • โดยเฉพาะในสถาปัตยกรรม Intel บางรุ่น แค่ใช้คำสั่ง AVX512 แม้เพียงเล็กน้อย ก็อาจทำให้ clock ของโปรเซสเซอร์ทั้งตัวลดลง ส่งผลให้ประสิทธิภาพขึ้น ๆ ลง ๆ หรือช้าลงได้
      https://stackoverflow.com/questions/56852812/simd-instructio...

  • บน x86 CPU ที่ใหม่พอ เช่น Intel Broadwell หรือ AMD Ryzen ก็อาจใช้ ADX ได้ และในสถานการณ์อย่าง Curve25519 ที่การแทนค่า radix 2^51 เคยได้เปรียบแบบดั้งเดิม ทุกวันนี้อาจเร็วกว่าได้
    [1] https://en.wikipedia.org/wiki/Intel_ADX

  • บทความที่เกี่ยวข้องคือเธรดเก่า ๆ เรื่อง radix 2^51 trick
    The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 - พฤศจิกายน 2022
    The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 - พฤษภาคม 2020

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

    • อีกแนวทางหนึ่งคือใช้ ชิ้นส่วน 64 บิต ตามปกติ แต่ execute การบวกแต่ละครั้งแบบคาดเดาขนานทั้งกรณีมี carry และไม่มี carry แล้วเลือกฝั่งที่ถูกต้องตามผล carry ของการบวกตำแหน่งต่ำกว่า
      จำนวนการบวกจะเพิ่มเป็นสองเท่า แต่สามารถลดเวลาการ propagate carry จากเชิงเส้นเป็น log(bits) ได้
    • ส่วนที่ยังไม่ค่อยเข้าใจคือ เทคนิคที่แสดงตรงนี้ดูเหมือนจะเน้นทำให้เวลาบวกค่า N ตัว ripple carry เกิดแค่ครั้งเดียว ไม่ใช่ N-1 ครั้ง
      การทำ carry ซับซ้อนกว่า แต่สามารถ parallelize การบวกจริงได้
      แต่ตั้งแต่แรกก็ต้องแบ่งตัวเลขอินพุตเป็น ชุดรีจิสเตอร์ 5 ตัว อยู่แล้ว ถ้าอยากได้ประโยชน์โดยรวม การแบ่งนั้นก็ควร parallelize ได้ด้วยไม่ใช่หรือ
    • Nvidia กำลังเจาะแนวคิดทั่วไปนี้อยู่ และดูเหมือนจะให้ผลที่มีอนาคตดีพอสมควรในบางสาขา
    • กฎนี้ขยายไปถึงซูเปอร์คอมพิวเตอร์หลายโหนดหรือคลาวด์ได้ด้วย
      ถ้าใช้ 10,000 คอร์ ได้ overhead ก็ถือว่าน้อยจนมองข้ามได้

  • แสดงให้เห็นได้ดีมากว่าคนที่ทำงานกับ x86_64 อย่างเดียว เห็นว่าการที่ RISC-V ตัด carry flag ออกไปนั้นไม่ได้ผิด

    • ยังสามารถทำอีกแบบได้โดยคง limb 64 บิตไว้
      insight สำคัญคือ ตราบใดที่ผลรวมในตำแหน่ง limb หนึ่งไม่ได้เป็น 1 ทั้งหมด carry ที่ออกจากตำแหน่งนั้นจะไม่ขึ้นกับ carry ที่เข้ามา แต่ขึ้นกับว่าการบวกดั้งเดิมในตำแหน่งนั้นสร้าง carry หรือไม่เท่านั้น
      ถ้าผลรวมเป็น 1 ทั้งหมด carry ที่ออกไปจะเท่ากับ carry ที่เข้ามา
      ถ้าแสดงสิ่งนี้เป็น conditional branch ที่ถูกทำนายว่า not-taken แทบเสมอ ภายใต้สมมติฐานว่าสามารถทำนาย conditional branch หลายตัวเป็น not-taken ได้ใน clock cycle เดียวกัน แต่ละบล็อกคำสั่งก็สามารถรันขนานกันได้เต็มที่
      ทุก ๆ 2^64 ครั้งจะมีครั้งหนึ่งที่รันช้ามาก
      สำหรับเครื่อง 4-wide กับตัวเลข 4-limb จะไม่ได้เปรียบกว่า adc แต่ถ้าเป็นเครื่อง 8-wide กับตัวเลข 8-limb ก็เริ่มได้ประโยชน์มากขึ้น
      ใน x86_64 ปัจจุบันอาจไม่ได้ช่วยมากนัก แต่ใน Apple M series ที่ M1 ก็เป็น 8-wide มีความเป็นไปได้ และอาจทำทางอ้อมได้ยากเพราะ Arm ISA
      ถ้า Tenstorrent 8-wide RISC-V Ascalon ออกมาช่วงปลายปีนี้หรือต้นปี 2026 ก็คงได้ตรวจสอบจริงพร้อมกับ Ventana, Rivos, XiangShan และรายอื่น ๆ
      ถ้ามี 1-lane shift ที่เร็ว ก็จะทำงานได้ดีขึ้นใน SIMD กว้าง ๆ ด้วย และใน RISC-V เรียกสิ่งนี้ว่า slideup
    • ยังมีกรณีทั่วไปอีกมากที่ carry-save addition แย่กว่า add-with-carry
      อัลกอริทึมการบวกหลาย word ทั้งสองแบบแทนที่กันไม่ได้และมี use case ต่างกัน ดังนั้น ISA ที่ดีควรมีคำสั่ง ADC/SBB และต้นทุนเพิ่มก็เล็กน้อย
      ไม่จำเป็นต้องมี flag register เฉพาะด้วยซ้ำ บาง ISA จะเก็บ flag carry/borrow ไว้ในรีจิสเตอร์ทั่วไปเมื่อจำเป็น
      การไม่มี carry ใน RISC-V ไม่ใช่คุณสมบัติที่แย่ที่สุด สิ่งที่แย่กว่าคือไม่มี integer overflow flag
      โปรแกรมที่อ้างว่าเขียนอย่างปลอดภัยจำเป็นต้องตรวจจับ integer overflow แต่ถ้าเลี่ยงด้วยซอฟต์แวร์ จะทำให้ประสิทธิภาพที่ทำได้ลดลงยิ่งกว่าการเลี่ยงการไม่มี carry มาก
    • กระแสนี้สุดท้ายสืบเนื่องมาจากการที่ C ตัด carry flag ออกไป และในโลกจริงมันแทบไม่ได้ถูกใช้เพื่อ carry แล้ว
    • ถ้า carry flag ช้าอยู่แล้ว ไม่ได้มีแค่ผมที่คิดว่า “ดราม่า RISC-V GMP นั่นมันอะไรกันแน่?”

  • radix trick นี้นำไปใช้กับโครงสร้างข้อมูลได้ด้วย
    มีตัวอย่างที่ดีในหนังสือ 『Purely Functional Data Structures』 ของ Okasaki

  • ถ้าได้เห็นบทความนี้เมื่อไม่กี่เดือนก่อนก็คงดี
    ตอนพยายาม encode/decode buffer ด้วย radix ใด ๆ ก็ตาม ผมมาถึงข้อสรุปช้าเกินไปว่า carry อาจ propagate ไปถึงท้าย buffer ได้ และนั่นทำให้อัลกอริทึมช้าลงมาก
    สุดท้ายวิธีแก้ก็มีส่วนคล้าย trick นี้ คือแบ่ง buffer เป็น chunk และเหลือ พื้นที่เผื่อ ไว้จัดการ carry
    ไม่ได้เหมือนกันเป๊ะ ๆ โดยใช้บิตที่เสียเปล่าเล็กน้อย แลกกับการใช้พื้นที่เก็บข้อมูลหรือ bandwidth เครือข่ายเพิ่มขึ้นนิดเดียว เพื่อลดการคำนวณ
    สงสัยว่าถ้ารวบ carry แบบนี้ไว้แล้วค่อยแก้ในขั้นตอนหลัง จะได้ทั้งสองทางหรือเปล่า แต่อาจเป็นแค่ความหวังก็ได้

  • รู้ว่า guideline ของ HN บอกว่าอย่าแก้ชื่อเรื่อง แต่ไม่ชอบ ชื่อพาดหัวเรียกคลิก ที่ขยายข้ออ้างเล็ก ๆ ให้กว้างเกินไป
    ชื่อบทความนี้ควรเป็นประมาณ “radix 2^51 trick สำหรับบวกจำนวนเต็ม 64 บิตแบบขนานโดยไม่ทำให้ pipeline ช้าลงเพราะ carry dependency บนสถาปัตยกรรม x86 บางรุ่น”