क्या किसी प्रोसेसर ने integer square root निर्देश लागू किया है?

 (retrocomputing.stackexchange.com)
1 पॉइंट द्वारा GN⁺ 2024-04-08 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • मुद्दा सामान्य floating-point sqrt का नहीं, बल्कि यह है कि क्या किसी CPU निर्देश या हार्डवेयर फीचर के रूप में integer square root दिया गया था; Nintendo DS का divider/square-rooter इससे मिलता-जुलता है, लेकिन यह native निर्देश नहीं है
  • Harris RTX 2000 Forth CPU और military-grade RTX 2010 उन उदाहरणों में गिने जाते हैं जिन्होंने multi-step square root निर्देश दिए; RTX 2000 में 1 setup और 15 step के बाद परिणाम मिलता था
  • इससे भी पुराना उदाहरण ENIAC है, जिसने 1946 में divider/square-rooter unit के जरिए decimal integer accumulator को नियंत्रित कर प्रति सेकंड अधिकतम 40 division या 3 square root ऑपरेशन किए
  • integer square root के लिए तेज integer multiplier और पर्याप्त precision चाहिए, इसलिए ऐतिहासिक CPU के लिए यह बोझिल था; ARMv8 के frsqrte/frsqrts की तरह अनुमान और iteration को अलग करके accuracy और speed को नियंत्रित करने का तरीका भी मौजूद है
  • Quake-style inverse square root अब आधुनिक हार्डवेयर पर सामान्यतः प्रदर्शन में बढ़त नहीं देता; table lookup, interpolation, Halley-श्रेणी iteration, और fixed-point divide-and-conquer जैसी तकनीकों का चयन implementation environment पर निर्भर करता है

प्रश्न का दायरा और Nintendo DS का मामला

  • प्रश्न यह देखता है कि क्या integer square root निर्देश को वास्तव में लागू करने वाला कोई प्रोसेसर था
  • floating-point square root निर्देश आम हैं, लेकिन integer-only square root निर्देश प्रश्नकर्ता ने नहीं देखे थे — सवाल इसी आधार से शुरू होता है
  • Nintendo DS में memory-mapped integer divider/square rooter था
    • ARM प्रोसेसर में FPU या hardware divider न होने के कारण यह 3D गणनाओं में मददगार था
    • लेकिन मुख्य बात यह है कि यह native processor instruction नहीं था

Harris RTX 2000 और RTX 2010

  • Harris RTX 2000 Forth CPU को multi-step square root निर्देश देने वाले उदाहरण के रूप में उद्धृत किया जाता है
  • इसका military-grade sibling RTX 2010 भी इसी तरह की क्षमता देता था
  • संबंधित सामग्री के लिए Stack Computers: RTX 2000 लिंक किया गया है
  • RTX2000 Family Programmer’s Reference Manual के अनुसार यह फीचर iterative square root के अधिक करीब था, जिसमें अंतिम मान पाने के लिए 1 setup निर्देश और 15 step निर्देश चलाने पड़ते थे
  • Ken Lyons का “A Fast Method for Finding an Integer Square Root” भी RTX2000 परिवार के hardware implementation और programming उदाहरणों पर चर्चा करने वाला स्रोत बताया गया है

ENIAC का divider/square-rooter unit

  • 1946 का ENIAC भी integer square root hardware के उदाहरण में आता है
  • उद्धृत विवरण के अनुसार ENIAC ने 4 accumulator को special multiplier unit से नियंत्रित करके प्रति सेकंड अधिकतम 385 multiplication किए
  • 5 accumulator special divider/square-rooter unit से नियंत्रित होते थे, जो प्रति सेकंड अधिकतम 40 division या 3 square root ऑपरेशन कर सकता था
  • ENIAC के accumulator decimal integer के रूप में काम करते थे

integer square root लागू करना कठिन क्यों है

  • एक उत्तर Newton-Raphson iteration से inverse square root निकालकर उसे मूल मान से गुणा करने को square root गणना का एक कुशल तरीका बताता है
  • यह तरीका “Quake method” के नाम से जाना जाता है, और आधुनिक CPU/GPU में इसे initial estimate निर्देश और iteration निर्देशों के रूप में सामान्यीकृत किया गया है
    • उदाहरण: ARMv8 का frsqrte
    • उदाहरण: ARMv8 का frsqrts
  • इस दृष्टिकोण की मुख्य सीमा यह है कि इसमें तेज multiplier चाहिए
    • floating-point sqrt के लिए तेज FP multiplier चाहिए, जो FPU में होता है
    • integer sqrt के लिए तेज integer multiplier चाहिए, लेकिन ऐतिहासिक रूप से अधिकांश CPU में ऐसा हार्डवेयर नहीं था
    • पर्याप्त precision के लिए इनपुट चौड़ाई से दोगुनी चौड़ाई वाला तेज multiplier भी चाहिए होता है
  • क्योंकि precision की मांग हमेशा समान नहीं होती, frsqrte और frsqrts की तरह estimate और iteration को अलग करने से इच्छित speed-accuracy tradeoff के अनुसार iteration की संख्या बदली जा सकती है

Quake तकनीक और आधुनिक sqrt implementation पर बहस

  • एक अन्य उत्तर कहता है कि Quake trick को सबसे कुशल मानना लंबे समय से सही नहीं है, और यह केवल कुछ खास हार्डवेयर पर कम-गुणवत्ता वाले float परिणामों के लिए लागू होता था
  • आधुनिक chips में native sqrt निर्देश कहीं अधिक तेज होते हैं, और अक्सर कुछ clock cycles में पूरे हो जाते हैं
  • और भी तेज तरीके के रूप में असमान अंतराल वाले मानों की table स्टोर करना, दो मानों को जल्दी लाना, interpolation करना, फिर base-2 exponent को shift करना, और जरूरत हो तो Newton-Raphson से बेहतर iteration एक बार चलाना सुझाया गया है
  • Halley-श्रेणी और अन्य iteration विधियाँ Newton-Raphson से तेज converge कर सकती हैं, लेकिन वास्तविक गति प्रत्येक ऑपरेशन की लागत पर निर्भर करती है
  • यदि दायरा केवल integer हो, जैसे 2^32, तो यही विचार fixed-point में लागू किया जा सकता है
    • hardware के लिए एक सरल तरीका divide and conquer बताया गया है
    • हर 8 bits को 256 fixed-point मानों की table से map करके, parallel lookup के बाद, 3 multiplication में से 2 को parallel चलाकर 32-bit मान निकाला और truncate किया जा सकता है
  • sqrt optimization पर शोध जारी है, और उदाहरण के रूप में INRIA HAL material प्रस्तुत किया गया है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-04-08
Hacker News टिप्पणियाँ

  • AArch64 NEON में URSQRTE instruction है, इसलिए यह मूल सवाल के जितना सोचा था उससे कहीं ज़्यादा करीब है
    अगर 32-bit value को fractional part के 32 bits वाले fixed-point integer के रूप में देखें, तो representation range 0 से 1-ε तक बराबर अंतराल में है और ε=2^-32 है
    URSQRTE एक approximate reciprocal square root निकालता है, फिर उसे आधे से divide करता है, और result को 0 से 1-ε range में clamp करता है
    fixed-point integer कड़ाई से integer नहीं है और approximate reciprocal square root भी square root नहीं है, लेकिन यह काफी करीब तक पहुँच सकता है
    संबंधित FRSQRTE कहीं ज़्यादा general instruction है, जो 32-bit floating point के लिए approximate reciprocal square root देता है

    • हैरानी होती है कि ऐसा कौन-सा काम है जिसमें इतना फायदा है कि इतनी complex instruction, जबकि उसे आसानी से सरल instructions में तोड़ा जा सकता है, फिर भी AArch64 में शामिल की गई

  • अगर सवाल है कि क्या single clock cycle में संभव है, तो बहुत बड़ी lookup table हो तो संभव है
    clock cycle के भीतर serial logic gates कितने चलाए जा सकते हैं, इस पर निर्भर करते हुए size घटाया भी जा सकता है
    उदाहरण के लिए 10000 का binary square root 100 के square root से काफी मिलता-जुलता है; बस zeros की संख्या अलग मानी जा सकती है

    • floating-point reciprocal square-root estimate instruction (frsqrte) आम तौर पर इसी तरह की table lookup से implement होता है, और mantissa के कुछ bits तथा exponent के least significant bit से index करता है
      precision आम तौर पर bf16 (ARM, RISC-V) या fp16 (x86) जैसी होती है, इसलिए अगर higher precision चाहिए तो बाद में Newton-Raphson iterations कुछ बार चलाए जाते हैं
    • input में bits की संख्या n हो, तो integer square root को केवल shifts और additions से n/2 iterations में calculate किया जा सकता है
      हर step में result n_old में नया bit set करना चाहिए या नहीं, यह n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2)) से calculate करते हैं
      फिर original operand से compare करके अगर यह छोटा या बराबर हो तो 1) result में bit set करते हैं और 2) n2_old को n2_new से update करते हैं
      उपयुक्त microcode instruction set और ALU हो तो n/2 या शायद n clock cycles में संभव है, और और optimize करने पर n को operand में सबसे बाएँ set bit के index तक घटाया जा सकता है
    • शायद बेवकूफ़ी भरा सवाल हो, लेकिन क्या बड़ी table lookup सच में एक clock cycle में खत्म होती है?
      अगर बड़ी lookup table है तो उसे memory से लाना पड़ेगा, तो cache और memory hierarchy की latency नहीं आएगी क्या?
    • ऐसे देखें तो लगता है जैसे दुनिया का कोई भी algorithm 1 clock cycle में चल सकता है
    • integer square root उम्मीद से इतना खराब नहीं है; greater/less lookup table में सिर्फ N^0.5 entries store करनी पड़ती हैं
      यानी हर answer N के लिए N^2 store करना
      16-bit integers के लिए यह practical है, 32-bit भी शायद संभव हो, लेकिन 64-bit के लिए मुश्किल है

  • अगर “processor” की definition को electromechanical devices तक फैलाएँ, तो Friden SRQ motor के अलावा एक भी electronic component के बिना, सिर्फ addition और shift से square root calculate कर सकता था
    decimal point की position manually align करनी पड़ती थी, इसलिए technically इसे integer operation भी कहा जा सकता है
    वीडियो: https://youtu.be/o44a1ao5h8w

  • 1 + 3 + 5 + ... + 2k + 1 sequence का उपयोग करके किसी भी integer का integer square root निकाला जा सकता है, नहीं?
    मूल रूप से उस sequence में मेरे number से छोटा या बराबर सबसे नज़दीकी term का k खोजने का तरीका है

    • idea समझा सकते हो?
      definition के हिसाब से algorithm तो सही है, लेकिन naive implementation 32-bit numbers पर भी बहुत slow होगा
      इस स्तर पर तो सीधे binary search करना कहीं तेज़ होगा
    • बेहतर तरीका शायद (x+y)^2=x^2+2xy+y^2 expansion और यह observation साथ में उपयोग करना है कि किसी भी base में 2n-digit number का square root अधिकतम n digits का होता है
      यह pen और paper से square root हाथ से calculate करने के common तरीके जैसा है
      इसे 8 bits करके process करें तो बस 8-bit number के square root की lookup table चाहिए
    • अगर आपका मतलब उस sequence को लगातार repeat करना है, तो input bit length के हिसाब से यह exponential time लेगा
    • यह उन classic कामों में से एक है जिन्हें embarrassingly parallel बनाना बहुत आसान है

  • नीचे वाले answer का यह हिस्सा मज़ेदार लगा:

    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 है कि अगर आप बहुत clever code लिखते हैं, तो बाद में आपको याद न रहने की संभावना काफी है कि वह code कैसे काम करता है

  • थोड़ा नीचे जाकर पढ़ना पड़ेगा, लेकिन answer ENIAC होना सच में मज़ेदार है

    • बहुत से लोग सोचते हैं कि उनके school में आने से पहले की हर चीज़ primitive थी और मुश्किल से चलती थी :)
      थोड़ा भी पढ़ें तो ठीक उल्टा दिखता है
      आज के ज़्यादातर clever ideas पहले ही 1940–60 के दशक के computers में इस्तेमाल हो चुके थे, और नए semiconductor chips में reuse हो रहे हैं
      pipelining, out-of-order execution, multiple cores जैसी चीज़ें भी ऐसी ही हैं
      पुराना hardware भले थोड़ा “rough” रहा हो, लेकिन architecture में बहुत clever techniques इस्तेमाल हुई थीं

  • 2 ^ (1/2 * Log2(X)) = sqrt(X)
    Log2(x) को leading zeros count से बदल दें तो बहुत rough approximation मिल सकती है
    Log(2) को बेहतर approximate करें तो answer के और करीब पहुँच सकते हैं

  • अगर nearest integer तक exact answer नहीं बल्कि बहुत rough approximation चाहिए, तो सबसे आगे वाले 1 bit की position के आधे जितना right shift कर दें
    लगभग हर processor में shift instruction होती है, और FLO (Find Leading One) या FFS (Find First Set) जैसी instructions भी इतनी common लगती हैं कि कहना मुश्किल है किनमें नहीं हैं
    कुछ uses में ऐसी बहुत rough approximation भी exact answer जितनी useful हो सकती है
    जैसे बाद की Newton-Raphson iterations के लिए सिर्फ एक suitable starting value चाहिए हो
    बेशक right-shift trick अधिक accurate square root calculation के initial value के रूप में भी ठीक है :P

    • क्या यहाँ DOOM वाली बात आ रही है?
      अब यह काफी famous internet story है, जिसमें Carmack और एक magical 32-bit number आते हैं
    • मज़ेदार तथ्य: FFS और उसका generalization FNS CUDA में हैं: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_...
      व्यक्तिगत रूप से मुझे पसंद आने वाला एक और CUDA hardware intrinsic log2 है

  • अगर याद सही है तो ज़्यादातर, शायद सभी fixed-point DSP में square-root instruction या helper instruction होती है

  • 6502 fans के लिए आधा-संबंधित और दिलचस्प square-root algorithms का exhaustive analysis: https://github.com/TobyLobster/sqrt_test