กลเม็ดเลขฐาน 2^51 (2017)

(chosenplaintext.ca)

1 คะแนน โดย GN⁺ 2025-05-31 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

ปัญหา carry (การทด) ที่เกิดขึ้นในการดำเนินการกับจำนวนเต็มขนาดใหญ่เป็นสาเหตุหลักที่ทำให้การทำงานแบบขนานทำได้ยาก
ในสถาปัตยกรรม x86 คำสั่ง adc สำหรับจัดการ carry ช้ากว่าคำสั่ง add ทั่วไป และการจัดการ carry แบบต่อเนื่องยังจำกัดการทำงานแบบขนาน
หากใช้ การแทนค่าแบบ Radix 2^51 จะสามารถหน่วงการแพร่ของ carry ออกไป ทำให้ทำการบวกได้มากขึ้นอย่างรวดเร็ว
จัดสรรให้แต่ละ limb (ค่าย่อย) ใช้เพียง 51 หรือ 52 บิต และใช้พื้นที่บิตด้านบนที่เหลือเป็นที่เก็บ carry ชั่วคราว
เทคนิคนี้แม้จะต้องใช้รีจิสเตอร์เพิ่มและมีต้นทุนในการแปลงค่าเพิ่มเติม แต่ในทางปฏิบัติกลับให้ประสิทธิภาพดีกว่าเลขฐาน 2^64

การบวกและการลบอย่างรวดเร็ว: ปัญหา carry

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

การจัดการ carry ในคอมพิวเตอร์

คอมพิวเตอร์ประมวลผลการบวกเป็นหน่วยของจำนวนเต็ม 64 บิต
แม้จะดูเหมือนว่าสามารถแบ่งจำนวนเต็ม 256 บิตออกเป็น 4 limb ขนาด 64 บิตแล้วประมวลผลการบวกแบบขนานได้ แต่ในความเป็นจริงต้องจัดการ overflow (carry) จึงจะได้ผลลัพธ์ที่ถูกต้อง
x86 มีคำสั่ง adc (add with carry) ที่ช่วยจัดการ carry โดยอัตโนมัติ

สาเหตุของประสิทธิภาพที่ลดลง

คำสั่ง adc ต้องใช้ค่าอินพุตเพิ่มเติมคือ carry flag จึงมีประสิทธิภาพต่ำกว่า add แบบธรรมดา
บนสถาปัตยกรรม Haswell นั้น add สามารถรันแบบขนานได้หลายพอร์ต ขณะที่ adc หลีกเลี่ยงการทำงานแบบอนุกรม (ตามลำดับ) ไม่ได้
โดยเฉพาะเมื่อใช้คำสั่ง SIMD (vpaddq เป็นต้น) การบวกแบบขนานที่ไม่มี carry จะเร็วกว่าอย่างมาก

แนวคิดการหน่วง carry (ตัวอย่างบนกระดาษ)

เพื่อลด carry สามารถขยายช่วงของหลักเลขได้ (เช่น จาก 0-9 เป็น 0-9, A-Z และ * รวม 37 หลัก) เพื่อให้บวกตัวเลขหลายตัวได้ชั่วคราวโดยไม่ต้องเกิด carry
วิธีนี้ทำให้สามารถทำการบวกหลายครั้งโดยไม่ต้องแพร่ carry และค่อยจัดการ carry ทีเดียวในตอนท้าย (normalization)
แนวคิดนี้แยกการสะสม carry ออกจากการแพร่ carry ทำให้จัดการ carry เฉพาะในขั้นตอนสุดท้าย
ในการคำนวณจริง หากค่ามากกว่าค่าฐานของหลัก ก็จะสะสมและสะท้อน carry ทีละลำดับจากทางขวา

การประยุกต์ใช้การหน่วง carry กับคอมพิวเตอร์ (กลเม็ด Radix 2^51)

เพื่อลดการแพร่ carry ในคอมพิวเตอร์ จึงใช้การแทนค่าแบบ radix 2^51
แทนที่จะแบ่ง 256 บิตเป็น 4 limb ขนาด 64 บิต ก็แบ่งเป็น 5 limb ที่มีขนาดละ 51~52 บิต
- บิตด้านบน 12~13 บิตของแต่ละ limb จะทำหน้าที่เป็นที่เก็บ carry ชั่วคราว
วิธีนี้ทำให้แต่ละ limb ยังคงอยู่ในช่วงค่า 2^64 ได้ และในการคำนวณจริง carry จะเกิดได้ยาก จึงสามารถทำหลายการคำนวณแบบขนานได้โดยไม่ต้องจัดการ carry
หลังการคำนวณต่อเนื่องประมาณ 2^13 ครั้ง จึงค่อยทำ normalization (ทำให้เป็นรูปแบบปกติ) หนึ่งครั้ง
บน CPU Haswell เมื่อใช้ radix 2^51 แล้ว สามารถทำการบวกธรรมดาที่ไม่มี carry ซ้ำหลายครั้ง ส่งผลให้ประสิทธิภาพดีขึ้นมากเมื่อเทียบกับ radix 2^64 ทั่วไป
การแพร่ carry เพื่อ normalization จะทำเพียงครั้งเดียวในตอนท้าย

ตัวอย่างโค้ด

แบ่งค่าเก็บในรีจิสเตอร์ 5 ตัว ทำให้สามารถบวกได้โดยไม่มี carry
การทำ normalization จะทำโดยดึงบิตบนของแต่ละ limb ไปบวกกับ limb ข้างเคียง และทำให้ค่า carry ของตัวเองเป็น 0 ซ้ำไปเรื่อย ๆ

การขยายไปสู่การลบ

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

บทสรุป

เทคนิคต้านทาน carry (หรือการหน่วง carry) แม้จะเพิ่มจำนวน limb และเพิ่มงานแปลงค่า แต่ก็ช่วยเพิ่มประสิทธิภาพโดยรวมของการคำนวณได้อย่างมากในทางปฏิบัติ
กลเม็ด Radix 2^51 ถูกใช้อย่างแพร่หลายในงานที่ต้องการสมรรถนะสูง เช่น การคำนวณจำนวนเต็มขนาดใหญ่และวิทยาการเข้ารหัสลับ
เทคนิคนี้เป็นแนวคิดสำคัญในการเพิ่มประสิทธิภาพของฮาร์ดแวร์และอัลกอริทึมจริง

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

GN⁺ 2025-05-31

ความคิดเห็นจาก Hacker News

ตอนเห็นตัวเลข 2^51 ตอนแรกนึกว่าเป็นเรื่องการเก็บจำนวนเต็มในชนิด double แต่ก็เพิ่งตระหนักว่าค่าจำนวนเต็มที่ double เก็บได้อย่างแม่นยำจริง ๆ คือ 2^53-1
AVX512 (และ AVX2 ก็ได้ในระดับหนึ่ง) มีสภาพแวดล้อมที่ทำให้การทำ addition แบบ 256 บิตมีประสิทธิภาพมากพอสมควร และยังมีข้อดีที่ใส่ตัวเลขลงในรีจิสเตอร์ได้มากขึ้นด้วย
ตัวอย่างตรงไปตรงมาคือทำงานแบบโค้ดด้านล่าง

__m256i s = _mm256_add_epi64(a, b);
const __m256i all_ones = _mm256_set1_epi64x(~0);
int g = _mm256_cmpgt_epu64_mask(a, s);
int p = _mm256_cmpeq_epu64_mask(s, all_ones);
int carries = ((g << 1) + p) ^ p;

__m256i ret = _mm256_mask_sub_epi64(s, carries, s, all_ones);

ถึงขั้นเห็นว่า throughput ดีขึ้นด้วย โดยดูตัวอย่างโค้ดจริงได้ที่ godbolt.org
และการขยายตรรกะนี้ไปสู่การบวก 512 บิตก็ทำได้ง่ายมาก

มีการชี้ให้เห็นด้วยว่า โดยเฉพาะบนสถาปัตยกรรม CPU ของ Intel บางรุ่น แค่ใช้คำสั่ง AVX512 ก็อาจทำให้คล็อกของโปรเซสเซอร์โดยรวมลดลง ส่งผลให้ประสิทธิภาพรวมไม่สม่ำเสมอหรืออาจช้าลงด้วยซ้ำ
ดูข้อมูลอ้างอิงที่เกี่ยวข้องได้จาก ลิงก์ stackoverflow
สำหรับคำถามว่า “ใช้ 12 บิตแทน 13 บิตไม่ได้หรือ?” ในที่นี้มีการละเลยการจัดการ carry ของบิตสูงสุด (limb) เพื่อให้เวลา overflow แล้วทำงานแบบ wraparound
ผลคือ limb สูงสุดจะถูกจัดสรร 52 บิต ทำให้มีข้อเสียคือพื้นที่เต็มเร็วกว่าลิมบ์อื่น แต่ก็ทำงานคล้ายการบวกจำนวนเต็มแบบไม่มีเครื่องหมายในภาษา C
จึงมีข้อเสนอว่า แล้วถ้าให้ limb บนสุดใช้ 64 บิต และอีกสี่ limb ที่เหลือใช้ 48 บิตล่ะ
แบบนี้จะสะสมการคำนวณได้มากขึ้นก่อน normalize และมีข้อดีเรื่องการจัดแนวตาม word เป็นต้น
คุณสมบัติด้านการจัดการ overflow ก็เหมือนเดิม
- ถ้าจัดสรร 64 บิตให้เฉพาะ limb บนสุด การบวก limb ของตัวเลขสองตัวจะ overflow เร็วเกินไป
  เช่นถ้าทั้งคู่มีค่า 2^63 ก็ overflow ทันที
  สำหรับเลขคณิตแบบ wraparound อาจไม่เป็นไร แต่ในกรณีทั่วไปถือว่าไม่เหมาะ
- ถ้าเป็นโครงสร้างแบบนี้ จะต้องใช้ 6 word ไม่ใช่ 5 word แบบในโพสต์ต้นฉบับ
  และยังต้องใช้คำสั่งมากขึ้นด้วย
- เป้าหมายคือการทำคณิตศาสตร์ 256 บิตให้เสร็จด้วยรีจิสเตอร์ 64 บิต 5 ตัว
  กล่าวคือการแบ่ง 256/5 = 51.2 บิตต่อ word จึงถือว่าเหมาะที่สุด
  ถ้าจำกัดเฉพาะ 256 บิตก็โอเค แต่ไม่ใช่ทางเลือกที่ดีที่สุดสำหรับไลบรารี big-int แบบทั่วไป
  เมื่อก่อนยังมีบริบทที่อยากใช้ carry หนึ่งตัวให้พอดีกับ 1 ไบต์ และในยุคที่ยังไม่มี barrel shifter ก็มักชอบใช้แค่ 56 จาก 64 บิตเพื่อให้จัดแนวได้ง่าย
  บน RISC-V ที่ไม่มีแฟลกในฮาร์ดแวร์ การถกเถียงเรื่องนี้ยิ่งสำคัญ
บน CPU x86 ยุคใหม่ (เช่น Intel Broadwell, AMD Ryzen) อาจเร็วกว่าได้ด้วยการใช้คำสั่ง Intel ADX แม้ในสถานการณ์ที่การแทนแบบ radix 2^51 เคยได้เปรียบตามธรรมเนียม (เช่น Curve25519)
เอกสารอภิปรายที่เกี่ยวข้อง
- The radix 2^51 trick (พฤศจิกายน 2022)
- The radix 2^51 trick (2017)
บทเรียนสำคัญคือ ถ้าการคำนวณต่าง ๆ เป็นอิสระต่อกัน การรันการคำนวณให้ขนานกันมากขึ้นอาจเร็วกว่าได้
ในทางกลับกัน ถ้ามี dependency จนต้องรันแบบลำดับ แม้จำนวนการคำนวณน้อยกว่าก็อาจช้ากว่า
แนวคิดนี้ใช้ได้ไม่ใช่แค่กับเลขจำนวนเต็มยาว แต่ยังประยุกต์ได้ในอีกหลายด้าน
- มีข้อเสนอให้แบ่งเป็นชังก์ 64 บิต แล้วรันล่วงหน้าสองกรณีแบบขนานตามว่าจะมี carry หรือไม่ จากนั้นค่อยเลือกผลลัพธ์ที่ถูกต้องตาม carry จริงในภายหลัง
  วิธีนี้ทำให้จำนวนครั้งของการบวกเพิ่มเป็นสองเท่า แต่ความเร็วการแพร่ของ carry จะดีขึ้นเป็นระดับ log(bits) แทนที่จะเป็นเชิงเส้น
- ส่วนที่ก่อนหน้านี้เข้าใจเทคนิคนี้ไม่ชัดคือ วิธีนี้โดยแก่นแล้วเปลี่ยนจากการให้ ripple carry ต้องทำ N-1 ครั้งเมื่อบวกค่า N ค่า ให้เหลือทำครั้งเดียว
  ตัวจัดการ carry เองจะซับซ้อนขึ้น แต่การบวกสามารถทำแบบขนานได้
  อย่างไรก็ตาม งานแบ่งเลขอินพุตออกเป็นหน่วยรีจิสเตอร์ 5 ตัวก็ต้องทำขนานได้ด้วย ไม่เช่นนั้นประสิทธิภาพรวมจะไม่มีนัยสำคัญ
- กฎนี้ขยายไปได้ถึงระดับซูเปอร์คอมพิวเตอร์หรือคลาวด์ที่มีจำนวนโหนดหลักหมื่น
  ถ้าใช้คอร์จำนวนมากได้ overhead ก็แทบมองข้ามได้
- NVidia ก็สนใจแนวคิดนี้ และได้ผลลัพธ์ที่ดีในหลายด้าน
แม้ HN จะมีแนวทางว่าไม่ควรใส่ความเห็นเพิ่มในชื่อเรื่อง แต่ก็ไม่ชอบชื่อแบบชวนคลิกที่เว่อร์เกินไป
คิดว่าถ้าจำกัดเป็น “radix 2^51 trick สำหรับการบวกจำนวนเต็ม 64 บิตแบบขนานโดยไม่มีการพึ่งพา carry บนสถาปัตยกรรม x86 บางส่วน” จะตรงกว่า
เสียดายที่ไม่ได้อ่านบทความนี้ให้เร็วกว่านี้สักไม่กี่เดือน เพราะน่าจะช่วยได้
เคยเจอกรณีที่ตอน encode/decode บัฟเฟอร์เป็นฐานเลขตามใจ การแพร่ของ carry ไปทั้งบัฟเฟอร์ทำให้อัลกอริทึมช้าลงมาก
สุดท้ายก็แก้โดยแบ่งเป็น chunk พร้อมเว้น 'พื้นที่เผื่อ' ไว้สำหรับจัดการ carry ซึ่งดูคล้ายกับทริกนี้
ในทางปฏิบัติคือเลือกยอมเสียบิตบางส่วนเพื่อแลกกับการลดปริมาณการคำนวณหรือแบนด์วิดท์เครือข่าย
เลยสงสัยว่าการจัดการ carry แบบนี้จะรวบไปรันเป็น post-processing ได้ด้วยหรือไม่
หวังว่าจะออกแบบให้ได้ข้อดีแทบทั้งหมดพร้อมกัน
จากประสบการณ์ที่เคยใช้แต่สภาพแวดล้อม x86_64 สิ่งนี้แสดงให้เห็นชัดว่า RISC-V ที่ไม่มี carry flag ก็ไม่ใช่แนวทางที่ผิดเสมอไป
- นอกจากวิธีนี้แล้ว ยังมีคำอธิบายถึงวิธีคง limb 64 บิตไว้และทำการบวกแบบปลอดภัยต่อ carry โดยใช้ตัวแปร uint64_t ทั้งหมด
  มีลำดับประมาณนี้
```
s0 += a0;
s1 += a1;
s2 += a2;
s3 += a3;
c0 = s0 < a0; // RISC-V sltu
c1 = s1 < a1;
c2 = s2 < a2;
if (s1 == -1) goto propagate0;
check_s2:
if (s2 == -1) goto propagate1;
add_carries:
s1 += c0;
s2 += c1;
s3 += c2;
goto done;
propagate0: c1 = c0; goto check_s2;
propagate1: c2 = c1; goto add_carries;
done:
```
ประเด็นสำคัญคือ เมื่อผลบวก (limb) ไม่ได้เป็นค่า 1 ทั้งหมด carry out ของ limb นั้นจะไม่ขึ้นกับ carry in แต่ขึ้นกับผลบวกจากค่าเดิมล้วน ๆ
แต่ถ้าค่าเป็น 1 ทั้งหมด จะได้ว่า carry out = carry in
ถ้าเป็นโครงสร้าง branch ที่แทบไม่ต้องพึ่งการทำนาย ก็สามารถรันขนานได้สมบูรณ์
ในเชิงความน่าจะเป็นจะช้าลงเพียง 1 ใน 2^64 แต่บนเครื่อง 4-wide เป็นต้นไปก็ไม่ได้ได้ประโยชน์มากนัก
อย่างไรก็ตาม บนเครื่อง 8-wide หรือโครงสร้าง 8-limb จะเห็นการเพิ่มประสิทธิภาพที่มีนัยสำคัญ
ไม่เหมาะกับ x86_64 แต่มีโอกาสใช้ได้กับเครื่อง 8-wide อย่างซีรีส์ Apple M*
ยังน่าจับตาบนโปรเซสเซอร์ RISC-V แบบ 8-wide เช่น Ascalon ของ Tenstorrent, Ventana, Rivos, XiangShan
และจะยิ่งได้ผลมากบนโครงสร้าง SIMD หรือสถาปัตยกรรมที่มีคำสั่ง shift/slideup แบบ 1-lane ที่เร็ว
- การบวกแบบ carry-save ไม่ได้เหนือกว่า add-with-carry เสมอไป
  อัลกอริทึม multi-word addition สองแบบนี้ใช้แทนกันไม่ได้และต่างก็มีข้อดีข้อเสียของตัวเอง
  เพราะฉะนั้นคำสั่ง ADC/SBB ควรถูกรวมเป็นพื้นฐานของ ISA และสามารถเก็บแฟลกไว้ในรีจิสเตอร์ได้ด้วย
  จุดอ่อนที่หนักกว่าของ RISC-V คือไม่มี integer overflow flag
  เวลาต้องตรวจจับ overflow ด้วยวิธีอ้อมในซอฟต์แวร์ ประสิทธิภาพจะตกมากกว่าการเลี่ยง carry bit เสียอีก
- การไม่มี carry flag บน RISC-V เป็นผลสืบเนื่องจากภาษา C เมิน binary carry flag
  ในทางปฏิบัติความถี่ในการใช้ carry flag ก็ต่ำกว่ามากจริง
- ไม่ได้มีแค่ฉันที่คิดว่า “ถ้า carry flag ช้าอยู่แล้ว แล้วดราม่า risc5 gmp ตอนนั้นมีไปทำไม?”
'Radix trick' นำไปใช้กับ data structure ได้ด้วย
ในหนังสือ 'Purely Functional Data Structures' ของ Okasaki ก็มีตัวอย่างที่น่าสนใจ