2^51 radix ट्रिक (2017)

 (chosenplaintext.ca)
1 पॉइंट द्वारा GN⁺ 2025-05-31 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • बड़े integer addition को आम तौर पर 64-bit limb में बाँटकर प्रोसेस किया जाता है, लेकिन carry propagation होने पर आधुनिक CPU के parallel execution का फायदा ठीक से इस्तेमाल करना मुश्किल हो जाता है
  • x86 का adc पिछले operation के carry flag पर निर्भर करता है और instruction chain को serialize कर देता है, इसलिए Intel Haswell जैसी architecture में भी bottleneck बनता है जहाँ कई add parallel में execute हो सकते हैं
  • radix 2^51 representation 256-bit value को चार 2^64 digits के बजाय पाँच 2^51 digits में बाँटता है, और हर limb के बचे हुए upper bits को intermediate carry storage के रूप में इस्तेमाल करता है
  • यह carry को हटाने का तरीका नहीं है; बल्कि कई additions के दौरान propagation को delay करके आखिरी normalization step में एक साथ handle करता है
  • Haswell पर एक simple benchmark में, conversion cost शामिल करने के बाद भी तीन additions से ही यह radix 2^64 method से तेज था, और repetitions बढ़ने पर इसका फायदा भी बढ़ता गया

बड़े integer addition में carry bottleneck क्यों बनता है

  • कागज पर long addition 1s place से, यानी दाएँ से बाएँ की ओर किया जाता है
    • क्योंकि हर digit का result दाईं तरफ के digit से आने वाले carry पर निर्भर करता है
    • अगर बाएँ से add करें, तो बाद में पैदा हुए carry के कारण पहले से calculate किए गए आगे के digit result को फिर से सुधारना पड़ेगा
  • बड़े integer addition पर भी यही constraint लागू होता है
    • अगर 256-bit integers x और y को चार 64-bit limbs में बाँटें, तो समान position वाले limbs को add किया जा सकता है
    • lower limb में overflow हो तो उस 1 को higher limb में carry करना पड़ता है
  • x86 का adc इसी propagation को handle करने वाली instruction है
    • यह पिछले operation में overflow हुआ या नहीं, इसे देखकर जरूरत पड़ने पर 1 add करता है
    • सही 256-bit addition lowest limb से add, adc, adc, adc के क्रम में आगे बढ़ता है

आधुनिक CPU पर adc धीमा क्यों पड़ता है

  • adc की execution cost आम तौर पर साधारण add से ज्यादा होती है
    • adc carry flag नाम का तीसरा input इस्तेमाल करता है, इसलिए यह add से अधिक complex है
    • यह add जितना अक्सर इस्तेमाल नहीं होता, इसलिए CPU designers के पास adc performance optimize करने में chip area लगाने का कम incentive होता है
  • बड़ा issue instruction dependency है
    • Intel Haswell पर single add execute होने में 1 cycle लगता है
    • ideal conditions में Haswell एक cycle में अधिकतम 4 add execute कर सकता है
    • Haswell में 8 execution ports हैं, जिनमें से 4 integer add execute कर सकते हैं
  • चार independent add आसानी से parallel execute हो सकते हैं
    • इसके उलट, adc chain में हर instruction पिछली instruction के carry flag output पर निर्भर करती है
    • CPU इन instructions को parallelize नहीं कर पाता और इन्हें क्रम से execute करना पड़ता है
  • SIMD में loss और बड़ा हो जाता है
    • vpaddq चार 64-bit additions एक साथ करता है
    • Haswell एक cycle में दो vpaddq execute कर सकता है
    • carry handling के लिए यह parallelism छोड़ना पड़े, तो performance advantage कम हो जाता है

कागजी addition से carry delay को समझना

  • decimal place values को बनाए रखते हुए, अगर हर place में आ सकने वाले characters को बढ़ा दें, तो carry को delay किया जा सकता है
    • सामान्य 0-9 के बजाय A-Z, * तक जोड़कर कुल 37 characters इस्तेमाल किए जाते हैं
    • लेकिन radix खुद 37 नहीं है; यह अभी भी decimal place values ही रखता है
  • किसी digit के 9 से ऊपर चले जाने पर भी तुरंत carry करना जरूरी नहीं रह जाता
    • 29 + 1 को 30 लिखा जा सकता है, लेकिन 2A, 1K, U जैसे भी represent किया जा सकता है
    • अगर दोनों numbers के हर digit 9 या उससे कम पर normalized हैं, तो addition के दौरान carry को टाला जा सकता है
  • यह हर input पर हमेशा लागू नहीं होता
    • 9 + W जैसे case में, जहाँ पहले से ही बड़ी digit value मौजूद है, carry की जरूरत होती है
    • normalized numbers को अधिकतम चार तक add करने पर भी carry के बिना represent किया जा सकता है
  • आखिर में फिर से सामान्य decimal representation में normalize करना होता है
    • दाईं ओर से हर digit में कितने 10 मौजूद हैं, यह calculate किया जाता है
    • उतना current digit से घटाकर next digit में carry किया जाता है
  • मुख्य बात carry propagation को खत्म करना नहीं, बल्कि उसे intermediate computation के दौरान store करके अंत में एक बार propagate करना है

कंप्यूटर में radix 2^51 representation

  • 256-bit value को चार 2^64 limbs में बाँटने पर हर limb 0 से 2^64−1 तक value रख सकता है
    • यह हर limb को base 2^64 की digit की तरह देखने का तरीका है
  • hardware की 64-bit integer range को बढ़ाया नहीं जा सकता, इसलिए radix का size घटाया जाता है
    • 256-bit value को चार 2^64 digits के बजाय पाँच 2^51 digits में बाँटा जाता है
    • हर limb अभी भी 64-bit integer के रूप में store होता है, लेकिन actual value केवल 51 या 52 bits इस्तेमाल करती है
  • बचे हुए upper bits intermediate carry storage बन जाते हैं
    • हर limb में original number के 51 या 52 bits आते हैं
    • बाकी 12 या 13 bits computation के दौरान पैदा हुए carry को रखते हैं
  • यह technique cryptography literature में radix 2^51 representation कहलाती है
  • normalized number होने पर, 2^64 संभावित limb values के भीतर upper 13-bit overflow की चिंता किए बिना अधिकतम 2^13 values add की जा सकती हैं

52-bit top limb और normalization

  • top limb को 52 bits allocate किए जाते हैं
    • बाकी limbs 51 bits इस्तेमाल करते हैं
    • top limb के carry को ignore किया जाता है ताकि 2^256−1 से ऊपर जाने पर value wrap हो जाए
    • यह C में सामान्य fixed-size unsigned integer addition के overflow पर wrap होने जैसा है
  • radix 2^51 addition code adc chain का इस्तेमाल नहीं करता और पाँच add स्वतंत्र रूप से execute करता है
    • चार 2^64 limb method की तुलना में add की संख्या 4 से बढ़कर 5 हो जाती है
    • बदले में carry flag dependency नहीं रहती, इसलिए parallel execution संभव होता है
  • normalization step में हर limb के upper bits निकालकर अगले higher limb में add किए जाते हैं
    • shr 51 से carry part extract किया जाता है
    • and 0x0007FFFFFFFFFFFF से केवल lower 51 bits रखे जाते हैं
    • top limb को and 0x000FFFFFFFFFFFFF से साफ किया जाता है
  • normalization, delay किए गए carry propagation को अंत में perform करने वाला step है
    • intermediate additions में carry flag dependency नहीं बनाई जाती
    • अंत में हर limb को फिर से allowed range के अंदर fit किया जाता है

Performance results और subtraction extension

  • simple benchmark में radix 2^51 addition ने Haswell CPU पर faster results दिखाए
    • radix 2^51 representation में conversion और वापस आने की cost भी इसमें शामिल थी
    • सिर्फ तीन additions के बाद ही यह radix 2^64 addition से तेज था
    • additions की संख्या बढ़ने पर saving effect भी साथ-साथ बढ़ता गया
  • यही idea subtraction तक भी extend किया जा सकता है
    • subtraction में carry negative carry बन जाता है
  • subtraction support करने के लिए limb को unsigned के बजाय signed integer की तरह treat किया जाता है
    • हर digit value positive या negative हो सकती है
    • हर limb positive carry और negative carry, दोनों store कर सकता है
  • इस change की cost है
    • हर limb का top bit sign bit के रूप में reserve होता है
    • normalizations के बीच किए जा सकने वाले operations की संख्या 2^13 से घटकर 2^12 हो जाती है
  • data को ज्यादा registers में बाँटने और operations की संख्या बढ़ने के बावजूद, carry dependency घटाने से overall performance improve हो सकती है

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

1 टिप्पणियां

 
GN⁺ 2025-05-31
Hacker News टिप्पणियाँ

  • यह जिज्ञासा है कि सबसे ऊपर वाले limb को 64-बिट और बाकी चार limb को 48-बिट each रखकर काम क्यों नहीं किया जा सकता
    normalization से पहले ज़्यादा additions जमा किए जा सकते हैं, और अगर instruction set में उपयोगी सुविधाएँ हों तो splitting/normalization के समय word alignment का भी फ़ायदा लिया जा सकता है, और overflow की विशेषताएँ भी समान लगती हैं

    • अगर लक्ष्यों में से एक 5 64-बिट registers के साथ 256-बिट arithmetic करना है, तो हर word में 256/5 = 51.2 बिट का उपयोग होता है, इसलिए यह कुछ हद तक आदर्श layout जैसा लगता है
      सामान्य-purpose big integer library के लिए यह शायद optimal न हो, और पहले के समय में arbitrary bit shifts को efficiently करने वाला barrel shifter नहीं होता था, इसलिए carry के लिए ठीक 1 byte छोड़कर 64 बिट में से 56 बिट का उपयोग करना बेहतर रहा होगा
      RISC-V में flags नहीं होते, इसलिए यह चर्चा काफ़ी प्रासंगिक है
    • encoded दो संख्याओं के सबसे ऊपरी limb को जोड़ने पर बहुत जल्दी overflow हो जाता है
      उदाहरण के लिए अगर दोनों 2^63 हों तो तुरंत सीमा पार हो जाती है, और wrapping arithmetic में यह ठीक हो सकता है, लेकिन सामान्य स्थिति में यह उपयुक्त नहीं है
    • ऐसा करने पर 256-बिट value को रखने के लिए मूल तरीके के 5 words नहीं बल्कि 6 words चाहिए होंगे, इसलिए addition instructions भी बढ़ जाएँगे

  • AVX512, और कुछ हद तक AVX2 से भी, 256-बिट addition काफ़ी efficiently implement की जा सकती है, और registers में अधिक संख्याएँ रखने का लाभ भी मिलता है
    यह _mm256_add_epi64, comparison masks, और carry masks के संयोजन से किया जा सकता है, और throughput भी बेहतर दिखता है: https://godbolt.org/z/e7zETe8xY
    इसे 512-बिट addition में बदलना भी आसान है, और उस स्थिति में सुधार और बड़ा होगा

    • खासकर कुछ Intel architectures में, AVX512 instructions का थोड़ा भी उपयोग पूरे processor clock को नीचे ला सकता है, जिससे कुल मिलाकर performance अस्थिर हो सकती है या और धीमी भी पड़ सकती है
      https://stackoverflow.com/questions/56852812/simd-instructio...

  • काफ़ी नए x86 CPU, जैसे Intel Broadwell या AMD Ryzen, पर ADX का उपयोग भी किया जा सकता है, और Curve25519 जैसी स्थितियों में जहाँ radix 2^51 representation पारंपरिक रूप से फ़ायदेमंद थी, वहाँ भी आजकल यह तेज़ हो सकता है
    [1] https://en.wikipedia.org/wiki/Intel_ADX

  • संबंधित पोस्ट के रूप में radix 2^51 trick पर पुराने threads भी हैं
    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

  • मुख्य बात यह है कि operations की संख्या ज़्यादा होने पर भी, अगर वे अधिकतर independent हों, तो उन्हें parallel में चलाकर तेज़ी मिल सकती है
    इसके उलट, operations कम हों लेकिन data dependency के कारण serial execution करना पड़े, तो वह धीमा हो सकता है; यह विचार long integer arithmetic से कहीं अधिक व्यापक रूप से लागू होता है

    • एक दूसरा तरीका यह है कि सामान्य 64-बिट chunks का उपयोग किया जाए, लेकिन हर addition को carry होने और carry न होने, दोनों स्थितियों के लिए parallel में speculative execution करके, निचली digit addition के carry परिणाम के आधार पर सही वाला चुना जाए
      additions की संख्या दोगुनी हो जाती है, लेकिन carry propagation time को linear की जगह log(bits) तक घटाया जा सकता है
    • जो हिस्सा पूरी तरह समझ नहीं आया, वह यह था कि यहाँ दिखाई गई तकनीक का फ़ोकस N values को जोड़ते समय ripple carry को N-1 बार की बजाय सिर्फ़ एक बार होने देना लगता है
      carry operation अधिक जटिल हो जाती है, लेकिन वास्तविक additions को parallel किया जा सकता है
      लेकिन चूँकि शुरुआत में input numbers को 5-register bundles में बाँटना ही पड़ता है, तो कुल लाभ पाने के लिए क्या उस splitting को भी parallelizable नहीं होना चाहिए?
    • Nvidia इस सामान्य विचार पर काम कर रहा है, और कुछ क्षेत्रों में काफ़ी promising नतीजे देता दिखता है
    • यह नियम multi-node supercomputer या cloud तक भी फैलता है
      अगर 10,000 cores उपलब्ध हों, तो overhead नगण्य हो सकता है

  • जिसने केवल x86_64 पर काम किया है, वह यह बहुत अच्छी तरह दिखाता है कि RISC-V द्वारा carry flag को छोड़ देना ग़लत निर्णय नहीं था

    • 64-बिट limb बनाए रखते हुए भी इसे दूसरे तरीके से किया जा सकता है
      मुख्य insight यह है कि जब तक किसी विशेष limb position का sum पूरा 1s न हो, उस position से बाहर जाने वाला carry, आने वाले carry पर निर्भर नहीं करता, बल्कि सिर्फ़ इस पर निर्भर करता है कि उस position की मूल addition ने carry बनाया था या नहीं
      अगर sum पूरा 1s हो, तो बाहर जाने वाला carry आने वाले carry के बराबर होता है
      अगर इसे ऐसे conditional branches के रूप में व्यक्त किया जाए जिन्हें लगभग हमेशा not-taken के रूप में predict किया जाता है, तो इस मान्यता पर कि कई conditional branches को एक ही clock cycle में not-taken के रूप में predict किया जा सकता है, हर instruction block पूरी तरह parallel में चल सकता है
      2^64 में एक बार यह बहुत धीमे तरीके से execute होगा
      4-wide machine पर 4-limb numbers के लिए adc पर कोई लाभ नहीं, लेकिन 8-wide machine पर 8-limb numbers के लिए फ़ायदा दिखना शुरू होता है
      मौजूदा x86_64 पर शायद इसका ज़्यादा लाभ न हो, लेकिन 8-wide M1 समेत Apple M series में संभावना है, और Arm ISA की वजह से workaround मुश्किल हो सकता है
      अगर Tenstorrent का 8-wide RISC-V Ascalon इस साल के अंत या 2026 की शुरुआत में आता है, तो Ventana, Rivos, XiangShan आदि के साथ इसे वास्तव में परखा जा सकेगा
      अगर तेज़ 1-lane shift उपलब्ध हो, तो यह wide SIMD में और बेहतर काम करता है; RISC-V में इसे slideup कहा जाता है
    • अभी भी कई सामान्य स्थितियाँ ऐसी हैं जहाँ carry-save addition, add-with-carry से बदतर है
      multi-word addition के ये दोनों algorithms एक-दूसरे के विकल्प नहीं हैं; इनके उपयोग अलग हैं, इसलिए एक ठीक-ठाक ISA में ADC/SBB instructions होते हैं और उनकी अतिरिक्त लागत भी बहुत कम होती है
      dedicated flag register अनिवार्य नहीं है, और कुछ ISA ज़रूरत पड़ने पर carry/borrow flags को general-purpose registers में रखते हैं
      RISC-V में carry का न होना सबसे बुरी बात नहीं है; उससे भी बुरा यह है कि integer overflow flag नहीं है
      जिन programs के बारे में दावा किया जाता है कि वे safely लिखे गए हैं, उनके लिए integer overflow detection आवश्यक है, और इसे software से workaround करने पर achievable performance, carry की अनुपस्थिति के workaround की तुलना में कहीं अधिक गिरती है
    • यह प्रवाह अंततः C द्वारा carry flag की उपेक्षा से आया, और व्यवहार में इसका उपयोग carry के लिए लगभग बंद हो गया
    • अगर carry flag वैसे भी धीमा है, तो “RISC-V GMP विवाद आख़िर था क्या?” यह सोचने वाला मैं अकेला नहीं था

  • यह radix trick data structures पर भी लागू होती है
    Okasaki की किताब 『Purely Functional Data Structures』 में इसका एक अच्छा उदाहरण है

  • काश मैंने यह पोस्ट कुछ महीने पहले देखी होती
    मैं किसी arbitrary radix में buffer को encode/decode करने की कोशिश कर रहा था, और बहुत देर से इस निष्कर्ष पर पहुँचा कि carry buffer के अंत तक propagate हो सकता है और इस वजह से algorithm बहुत धीमा हो जाता है
    अंत में समाधान में भी इस trick जैसी बात थी: buffer को chunks में बाँटना और carry संभालने के लिए extra space छोड़ना
    यह बिल्कुल वैसा नहीं था; मैंने थोड़ा waste bits रखा, ताकि storage space या network bandwidth बहुत थोड़ा अधिक लगे लेकिन computation कम हो जाए
    सोचता हूँ कि अगर carry को इस तरह जमा करके बाद के चरण में resolve किया जाए, तो क्या दोनों फ़ायदे एक साथ मिल सकते हैं, हालाँकि यह शायद सिर्फ़ आशा भर हो

  • HN guidelines के हिसाब से title नहीं बदलना चाहिए, यह बात समझता हूँ, लेकिन छोटे दावे को बहुत बड़ा बनाकर पेश करने वाले clickbait titles पसंद नहीं आते
    इस लेख का शीर्षक कुछ ऐसा होना चाहिए था: “कुछ x86 architectures पर carry dependency से pipeline को धीमा किए बिना 64-बिट integers को parallel में जोड़ने की radix 2^51 trick”