มีโปรเซสเซอร์ที่เคยใช้คำสั่งรากที่สองจำนวนเต็มหรือไม่?

 (retrocomputing.stackexchange.com)
1 คะแนน โดย GN⁺ 2024-04-08 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ประเด็นไม่ใช่ sqrt แบบเลขทศนิยมลอยตัวที่พบได้ทั่วไป แต่คือเคยมีกรณีที่ให้บริการ รากที่สองจำนวนเต็ม เป็นคำสั่ง CPU หรือฟังก์ชันฮาร์ดแวร์หรือไม่ โดย divider/square-rooter ของ Nintendo DS คล้ายกันแต่ไม่ใช่คำสั่งเนทีฟ
  • RTX 2000 Forth CPU ของ Harris และ RTX 2010 รุ่นเกรดทหาร ถูกยกเป็นกรณีที่มีคำสั่ง square root แบบหลายขั้นตอน โดย RTX 2000 มีโครงสร้างที่ได้ผลลัพธ์จาก setup 1 ครั้งและ step 15 ครั้ง
  • กรณีที่เก่ากว่านั้นคือ ENIAC ซึ่งในปี 1946 ใช้ divider/square-rooter unit ควบคุม decimal integer accumulator เพื่อทำการหารได้สูงสุด 40 ครั้งต่อวินาที หรือคำนวณรากที่สองได้ 3 ครั้งต่อวินาที
  • รากที่สองจำนวนเต็มต้องใช้ตัวคูณจำนวนเต็มที่เร็วและความแม่นยำเพียงพอ จึงเป็นภาระหนักสำหรับ CPU ในอดีต และยังมีแนวทางอย่าง frsqrte/frsqrts ของ ARMv8 ที่แยกการประมาณค่าและการวนซ้ำเพื่อปรับสมดุลความแม่นยำ·ความเร็ว
  • inverse square root แบบ Quake ไม่ได้มีข้อได้เปรียบด้านประสิทธิภาพโดยทั่วไปอีกต่อไปบนฮาร์ดแวร์สมัยใหม่ ส่วนการค้นตาราง·การอินเตอร์โพเลต·การวนซ้ำตระกูล Halley·divide and conquer แบบ fixed-point ล้วนเป็นตัวเลือกที่ขึ้นกับสภาพแวดล้อมการใช้งาน

ขอบเขตของคำถามและกรณีของ Nintendo DS

  • คำถามนี้ว่าด้วยว่าเคยมีโปรเซสเซอร์ที่ใช้งาน คำสั่งรากที่สองจำนวนเต็ม จริงหรือไม่
  • คำสั่ง square root สำหรับเลขทศนิยมลอยตัวพบได้ทั่วไป แต่เริ่มจากสมมติฐานว่าผู้ถามไม่เคยเห็นคำสั่ง square root เฉพาะจำนวนเต็ม
  • Nintendo DS มี integer divider/square rooter แบบ memory-mapped
    • เนื่องจากโปรเซสเซอร์ ARM ไม่มี FPU หรือ hardware divider จึงช่วยในการคำนวณ 3D
    • อย่างไรก็ตาม จุดสำคัญของคำถามคือสิ่งนี้ ไม่ใช่คำสั่งโปรเซสเซอร์เนทีฟ

Harris RTX 2000 และ RTX 2010

  • RTX 2000 Forth CPU ของ Harris ถูกกล่าวถึงว่าเป็นกรณีที่มีคำสั่ง square root แบบหลายขั้นตอน
  • RTX 2010 ซึ่งเป็นรุ่นพี่น้องเกรดทหาร ก็มีฟังก์ชันในตระกูลเดียวกัน
  • มีการเชื่อมโยงเอกสารที่เกี่ยวข้องคือ Stack Computers: RTX 2000
  • ตาม RTX2000 Family Programmer’s Reference Manual ฟังก์ชันนี้ใกล้เคียงกับ square root แบบวนซ้ำ โดยใช้วิธีรัน คำสั่ง setup 1 คำสั่ง และ คำสั่ง step 15 คำสั่ง เพื่อให้ได้ค่าสุดท้าย
  • “A Fast Method for Finding an Integer Square Root” ของ Ken Lyons ก็ถูกกล่าวถึงว่าเป็นเอกสารที่ว่าด้วยการใช้งานฮาร์ดแวร์และตัวอย่างการเขียนโปรแกรมในตระกูล RTX2000

divider/square-rooter unit ของ ENIAC

  • ENIAC ในปี 1946 ก็จัดเป็นกรณีของฮาร์ดแวร์รากที่สองจำนวนเต็มด้วย
  • ตามคำอธิบายที่ยกมา ENIAC ใช้ accumulator 4 ตัวที่ถูกควบคุมโดย multiplier unit พิเศษ เพื่อทำการคูณได้สูงสุด 385 ครั้งต่อวินาที
  • accumulator 5 ตัวถูกควบคุมโดย divider/square-rooter unit พิเศษ เพื่อประมวลผลการหารได้สูงสุด 40 ครั้งต่อวินาที หรือ การคำนวณรากที่สอง 3 ครั้ง ต่อวินาที
  • accumulator ของ ENIAC ทำงานเป็น decimal integer

เหตุผลที่การทำรากที่สองจำนวนเต็มทำได้ยาก

  • คำตอบหนึ่งอธิบายวิธีที่มีประสิทธิภาพในการคำนวณ square root ว่าให้หาค่า รากที่สองผกผัน ด้วยการวนซ้ำ Newton-Raphson แล้วคูณกลับกับค่าเดิม
  • วิธีนี้เป็นที่รู้จักในชื่อ “Quake method” และใน CPU กับ GPU สมัยใหม่มีกรณีที่ถูกทำให้เป็นรูปแบบทั่วไปด้วยคำสั่งประมาณค่าเริ่มต้นและคำสั่งวนซ้ำ
    • ตัวอย่าง: frsqrte ของ ARMv8
    • ตัวอย่าง: frsqrts ของ ARMv8
  • ข้อจำกัดสำคัญของแนวทางนี้คือจำเป็นต้องมี multiplier ที่เร็ว
    • sqrt แบบ floating-point ต้องใช้ FP multiplier ที่เร็ว และ FPU ก็มีสิ่งนี้
    • sqrt แบบจำนวนเต็มต้องใช้ integer multiplier ที่เร็ว แต่คำอธิบายคือในอดีต CPU ส่วนใหญ่ไม่มีฮาร์ดแวร์แบบนั้น
    • ยังมีเงื่อนไขเพิ่มเติมว่าหากต้องการความแม่นยำเพียงพอ ต้องมี multiplier ที่เร็วซึ่งมีความกว้างเป็นสองเท่าของความกว้างอินพุต
  • เนื่องจากข้อกำหนดด้านความแม่นยำไม่ได้เท่ากันเสมอไป การแยกการประมาณค่าและการวนซ้ำแบบ frsqrte กับ frsqrts จึงช่วยปรับจำนวนรอบวนซ้ำให้ตรงกับ จุดแลกเปลี่ยนระหว่างความเร็ว·ความแม่นยำ ที่ต้องการได้

เทคนิค Quake และข้อถกเถียงเรื่องการทำ sqrt สมัยใหม่

  • อีกคำตอบหนึ่งโต้แย้งว่าข้ออ้างที่ว่า Quake trick มีประสิทธิภาพที่สุดนั้นไม่ถูกต้องมานานแล้ว และจะใช้ได้เฉพาะเมื่ออยากได้ผลลัพธ์ float คุณภาพต่ำบนฮาร์ดแวร์บางประเภทเท่านั้น
  • บนชิปสมัยใหม่ คำสั่ง sqrt เนทีฟเร็วกว่ามาก และมักอยู่ในระดับ ไม่กี่ clock cycle
  • วิธีที่เสนอว่าเร็วกว่า คือเก็บตารางค่าที่มีระยะห่างไม่สม่ำเสมอ ดึงสองค่าออกมาอย่างรวดเร็วแล้วอินเตอร์โพเลต จากนั้น shift exponent ฐาน 2 และหากจำเป็นก็ใช้การวนซ้ำหนึ่งครั้งที่ดีกว่า Newton-Raphson
  • ตระกูล Halley และวิธีวนซ้ำหลายแบบสามารถลู่เข้าได้เร็วกว่า Newton-Raphson แต่ความเร็วจริงขึ้นกับต้นทุนของแต่ละการดำเนินการ
  • สำหรับช่วงที่เป็นจำนวนเต็มล้วน เช่น 2^32 สามารถใช้แนวคิดเดียวกันในรูปแบบ fixed-point ได้
    • มีการเสนอ divide and conquer เป็นวิธีง่าย ๆ สำหรับฮาร์ดแวร์
    • สามารถแมปแต่ละ 8 บิตไปยังตารางค่า fixed-point 256 ค่าแล้วค้นหาแบบขนาน จากนั้นทำการคูณ 3 ครั้ง โดย 2 ครั้งทำแบบขนาน เพื่อให้ได้ค่า 32 บิตแล้ว truncate
  • งานวิจัยด้านการปรับแต่ง sqrt ยังคงดำเนินต่อไป และมีการยก เอกสาร INRIA HAL เป็นตัวอย่าง

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

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

 
GN⁺ 2024-04-08
ความคิดเห็นจาก Hacker News

  • AArch64 NEON มีคำสั่ง URSQRTE จึงใกล้เคียงกับคำถามต้นทางกว่าที่คิด
    ถ้ามองค่าขนาด 32 บิตเป็นจำนวนเต็มแบบ fixed-point ที่มีส่วนเศษ 32 บิต ช่วงที่แทนได้จะเป็นค่าที่เว้นระยะเท่ากันตั้งแต่ 0 ถึง 1-ε โดยที่ ε=2^-32
    URSQRTE จะคำนวณค่า ส่วนกลับของรากที่สอง แบบประมาณ จากนั้นหารครึ่ง และ clamp ผลลัพธ์ให้อยู่ในช่วง 0 ถึง 1-ε
    จำนวนเต็มแบบ fixed-point ไม่ใช่จำนวนเต็มอย่างเคร่งครัด และส่วนกลับของรากที่สองแบบประมาณก็ไม่ใช่รากที่สอง แต่ก็ไปได้ใกล้พอสมควร
    FRSQRTE ที่เกี่ยวข้องกันเป็นคำสั่งที่ใช้งานทั่วไปกว่ามาก โดยให้ค่า reciprocal square root แบบประมาณสำหรับ floating-point 32 บิต

    • อยากรู้ว่างานแบบไหนที่ได้ประโยชน์มากพอจนใส่คำสั่งซับซ้อนแบบนั้นไว้ใน AArch64 ทั้งที่แยกเป็นคำสั่งที่ง่ายกว่านี้ได้ไม่ยาก

  • ถ้าถามว่าทำได้ใน clock cycle เดียวไหม ถ้ามี lookup table ขนาดใหญ่มากก็ทำได้
    ขนาดอาจลดลงได้บ้าง ขึ้นอยู่กับว่าในหนึ่ง clock cycle สามารถรัน logic gate แบบอนุกรมได้มากแค่ไหน
    เช่น รากที่สองแบบไบนารีของ 10000 ค่อนข้างคล้ายกับรากที่สองของ 100 แค่ต่างกันที่จำนวนศูนย์

    • คำสั่ง ประมาณค่าส่วนกลับของรากที่สอง สำหรับ floating-point (frsqrte) มักถูก implement ด้วยการ lookup table แบบนั้น โดย index ด้วยบิตบางส่วนของ mantissa และบิตล่างสุดของ exponent
      ความแม่นยำโดยรวมใกล้เคียงกับ bf16 (ARM, RISC-V) หรือ fp16 (x86) ดังนั้นถ้าต้องการความแม่นยำสูงขึ้นก็มักทำ Newton-Raphson iteration เพิ่มอีกสองสามรอบ
    • เมื่อจำนวนบิตของ input คือ n, รากที่สองแบบจำนวนเต็ม สามารถคำนวณได้ด้วยการวนซ้ำ n/2 ครั้งโดยใช้แค่ shift และ add
      ในแต่ละขั้นจะคำนวณว่าควรตั้งบิตใหม่ให้ผลลัพธ์ n_old หรือไม่ ด้วย n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2))
      จากนั้นเทียบกับ operand เดิม ถ้ามากกว่าหรือเท่ากับ ก็ 1) ตั้งบิตในผลลัพธ์ และ 2) อัปเดต n2_old เป็น n2_new
      ถ้ามีชุดคำสั่ง microcode และ ALU ที่เหมาะสม ก็ทำได้ใน n/2 หรืออาจเป็น n clock cycles และถ้าปรับให้ดีขึ้นอีกก็ลด n ลงเหลือถึง index ของบิตที่ติดอยู่ซ้ายสุดใน operand ได้
    • อาจเป็นคำถามโง่ ๆ แต่ lookup table ขนาดใหญ่มีกรณีที่เสร็จใน clock cycle เดียวจริง ๆ ไหม?
      ถ้าเป็น lookup table ขนาดใหญ่ก็น่าจะต้องดึงจากหน่วยความจำ ซึ่งจะมี latency จาก cache และ memory hierarchy ไม่ใช่หรือ
    • ถ้ามองแบบนั้น ฟังดูเหมือน algorithm อะไรก็รันได้ใน 1 clock cycle ทั้งนั้น
    • รากที่สองแบบจำนวนเต็มไม่ได้แย่อย่างที่คิด เพราะต้องเก็บแค่ N^0.5 รายการ ใน lookup table สำหรับมากกว่า/น้อยกว่า
      คือเก็บ N^2 สำหรับคำตอบ N ทุกตัว
      สำหรับจำนวนเต็ม 16 บิตทำได้จริง, 32 บิตก็อาจเป็นไปได้ แต่ 64 บิตคงไม่ไหว

  • ถ้าขยายคำจำกัดความของ “processor” ไปถึงอุปกรณ์ไฟฟ้ากลไก Friden SRQ สามารถคำนวณรากที่สองด้วยการบวกและ shift เพียงอย่างเดียว โดยไม่มีชิ้นส่วนอิเล็กทรอนิกส์เลยนอกจากมอเตอร์
    ต้องตั้งตำแหน่งจุดทศนิยมเองด้วยมือ ดังนั้นในเชิงเทคนิคจะเรียกว่าเป็นการคำนวณจำนวนเต็มก็ได้
    วิดีโอ: https://youtu.be/o44a1ao5h8w

  • ใช้ลำดับ 1 + 3 + 5 + ... + 2k + 1 ก็หาค่า รากที่สองแบบจำนวนเต็ม ของจำนวนเต็มใด ๆ ได้ไม่ใช่หรือ?
    โดยพื้นฐานคือหาค่า k ของพจน์ที่ใกล้ที่สุดในลำดับนั้นซึ่งน้อยกว่าหรือเท่ากับจำนวนของเรา

    • ช่วยอธิบายไอเดียได้ไหม?
      ตามนิยามก็เป็น algorithm จริง แต่ถ้า implement แบบตรงไปตรงมา แม้กับเลข 32 บิตก็ช้ามาก
      ระดับนี้ทำ binary search ไปเลยจะเร็วกว่ามาก
    • วิธีที่ดีกว่าอาจเป็นการใช้การกระจาย (x+y)^2=x^2+2xy+y^2 ร่วมกับข้อสังเกตว่า ไม่ว่าจะอยู่ในฐานใด รากที่สองของเลข 2n หลักจะมีได้มากสุด n หลัก
      เหมือนวิธีคำนวณรากที่สองด้วยมือบนกระดาษแบบทั่วไป
      ถ้าประมวลผลทีละ 8 บิต ก็ต้องมีแค่ lookup table สำหรับ รากที่สองของเลข 8 บิต เท่านั้น
    • ถ้าหมายถึงวนลำดับนั้นไปเรื่อย ๆ ก็จะใช้เวลา exponential time ตามความยาวบิตของ input
    • นี่เป็นตัวอย่างคลาสสิกของงานที่ parallelize ได้ง่ายจนน่าเขิน

  • ชอบตรงส่วนนี้ในคำตอบด้านล่าง:

    My implementation of square root using binary search, that doesn't depend on a multiplier. Only basic ALU instructions are used. It is vigorously undocumented. I have no idea what I wrote but it seems to work.
    เป็น reminder ที่ดีว่า ถ้าเขียนโค้ดฉลาด ๆ โอกาสสูงมากที่ภายหลังจะจำไม่ได้ว่าโค้ดนั้นทำงานอย่างไร

  • ต้องเลื่อนลงไปอ่านสักหน่อย แต่ขำจริงที่คำตอบคือ ENIAC

    • หลายคนคิดว่าทุกอย่างก่อนที่ตัวเองจะเข้าโรงเรียนนั้นดิบและแทบทำงานไม่ได้ :)
      แค่อ่านเพิ่มนิดเดียวก็จะเห็นว่าตรงกันข้ามเลย
      ไอเดียฉลาด ๆ ส่วนใหญ่ในปัจจุบันถูกใช้ในคอมพิวเตอร์ยุค 1940–60 มาแล้ว และกำลังถูกนำกลับมาใช้ในชิปเซมิคอนดักเตอร์รุ่นใหม่
      อย่าง pipelining, out-of-order execution, multi-core เป็นต้น
      ฮาร์ดแวร์ยุคเก่าอาจจะดู “หยาบ” ไปบ้าง แต่ในสถาปัตยกรรมมีเทคนิคที่เฉียบแหลมมาก ๆ ใช้อยู่

  • 2 ^ (1/2 * Log2(X)) = sqrt(X)
    ถ้าเปลี่ยน Log2(x) เป็น การนับจำนวน leading zeros ก็จะได้ค่าประมาณแบบหยาบมาก
    ถ้าประมาณ Log(2) ให้ดีขึ้น ก็เข้าใกล้คำตอบได้มากขึ้น

  • ถ้าไม่ต้องการคำตอบที่ถูกต้องเป๊ะถึงจำนวนเต็มที่ใกล้ที่สุด แต่เอาแค่ค่าประมาณหยาบมาก ๆ ก็แค่ right shift ไปครึ่งหนึ่งของตำแหน่งบิต 1 ตัวแรก
    แทบทุก processor มีคำสั่ง shift และคำสั่งอย่าง FLO (Find Leading One) หรือ FFS (Find First Set) ก็ดูเหมือนจะพบได้ทั่วไปจนไม่แน่ใจว่ามีที่ไหนไม่มีบ้าง
    ในบางการใช้งาน ค่าประมาณหยาบมากแบบนี้อาจมีประโยชน์พอ ๆ กับคำตอบที่ถูกต้อง
    เช่น เวลาต้องการแค่ค่าเริ่มต้นที่เหมาะสมสำหรับ Newton-Raphson iteration หลังจากนั้น
    แน่นอนว่า trick การ right shift ก็ใช้เป็นค่าเริ่มต้นสำหรับคำนวณรากที่สองที่แม่นยำขึ้นได้ดีเหมือนกัน :P

    • ตรงนี้จะมีเรื่อง DOOM โผล่มาไหม?
      ตอนนี้เป็นเรื่องเล่าบนอินเทอร์เน็ตที่ค่อนข้างดังแล้ว มี Carmack กับเลข 32 บิตมหัศจรรย์ปรากฏอยู่
    • เกร็ดน่าสนุกคือ FFS และเวอร์ชันทั่วไปของมันอย่าง FNS มีอยู่ใน CUDA: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_...
      hardware intrinsic ของ CUDA อีกตัวที่ผมชอบเป็นการส่วนตัวคือ log2

  • ถ้าจำไม่ผิด fixed-point DSP ส่วนใหญ่ หรืออาจจะทั้งหมด มีคำสั่งรากที่สองหรือคำสั่งช่วยสำหรับรากที่สอง

  • การวิเคราะห์แบบครบถ้วนของ algorithm รากที่สอง ที่กึ่งเกี่ยวข้องและน่าจะน่าสนใจสำหรับแฟน 6502: https://github.com/TobyLobster/sqrt_test