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

 (chosenplaintext.ca)
1 पॉइंट द्वारा GN⁺ 2025-05-31 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • बड़े integer arithmetic में होने वाली carry समस्या ऑपरेशनों की parallelization को कठिन बनाने वाला एक प्रमुख कारण है
  • x86 architecture में carry हैंडल करने के लिए adc instruction, सामान्य add instruction की तुलना में धीमा होता है, और लगातार carry प्रोसेसिंग parallel execution को सीमित करती है
  • Radix 2^51 representation का उपयोग करने पर carry propagation को टाला जा सकता है, जिससे अधिक additions तेज़ी से किए जा सकते हैं
  • हर limb (आंशिक मान) को केवल 51 या 52 bits दिए जाते हैं, और बची हुई ऊपरी bit space को carry के अस्थायी स्टोरेज के रूप में इस्तेमाल किया जाता है
  • यह तकनीक अतिरिक्त register उपयोग और conversion cost के बावजूद, व्यवहार में 2^64 radix की तुलना में बेहतर performance देती है

तेज़ addition और subtraction: carry समस्या

  • बड़े integer addition में, जैसे इंसान हाथ से अंकों के हिसाब से carry संभालता है, वैसे ही कंप्यूटर के लिए भी carry की वजह से addition algorithm को parallelize करना कठिन होता है
  • मूल रूप से हम दाईं ओर (निचले digit) से एक-एक करके जोड़ते हैं, और हर digit पर बनने वाले carry को बाईं ओर (ऊपरी digit) तक ले जाते हैं
  • अगर हम बाईं ओर से addition शुरू करें, तो पिछला carry अगले digit के operation को प्रभावित करता है, इसलिए operation order को parallelize नहीं किया जा सकता

कंप्यूटर में carry हैंडलिंग

  • कंप्यूटर 64-bit integer units में addition प्रोसेस करता है
  • 256-bit integer को 64-bit के 4 limbs में बाँटकर addition को parallel में प्रोसेस किया जा सकने जैसा लगता है, लेकिन वास्तव में सही परिणाम के लिए overflow (carry) को संभालना पड़ता है
  • x86 में carry को अपने-आप संभालने वाला adc (add with carry) instruction मौजूद है

performance गिरने के कारण

  • adc instruction को carry flag नाम का एक अतिरिक्त input चाहिए, इसलिए साधारण add की तुलना में इसकी performance कम होती है
  • Haswell architecture के आधार पर, add कई ports पर parallel execution कर सकता है, जबकि adc के लिए serial (क्रमिक) execution लगभग अनिवार्य हो जाता है
  • खासकर SIMD instructions (vpaddq आदि) का उपयोग करते समय, carry के बिना parallel addition कहीं तेज़ होता है

carry को टालने का विचार (कागज़ पर उदाहरण)

  • carry को कम करने के लिए, digit range को बढ़ाकर (जैसे: 0-9 से 0-9, A-Z, * तक कुल 37 digits) अस्थायी रूप से बिना carry के कई संख्याएँ जोड़ी जा सकती हैं
  • ऐसा करने पर carry propagation के बिना कई additions किए जा सकते हैं, और अंत में एक बार में carry को साफ़ (normalization) किया जा सकता है
  • यह अवधारणा carry accumulation और propagation को अलग करती है और केवल अंतिम चरण में carry processing करने देती है
  • वास्तविक operation में, अगर कोई मान digit base से बड़ा हो जाए, तो दाईं ओर से क्रमशः carry को जोड़ते हुए लागू किया जाता है

carry delay का कंप्यूटर में उपयोग (Radix 2^51 ट्रिक)

  • कंप्यूटर में carry propagation घटाने के लिए radix 2^51 representation का उपयोग किया जाता है
  • 256 bits को 64-bit के 4 limbs की जगह, 51~52 bits वाले 5 limbs में बाँटा जाता है
    • हर limb के ऊपरी 12~13 bits carry के अस्थायी स्टोरेज की तरह काम करते हैं
  • इस तरीके में हर limb 2^64 value range के भीतर रहता है, लेकिन वास्तविक operation में carry आसानी से पैदा नहीं होता, इसलिए कई operations बिना carry के parallel में किए जा सकते हैं
  • लगभग 2^13 लगातार operations के बाद एक बार normalization की ज़रूरत पड़ती है
  • Haswell CPU के आधार पर, radix 2^51 लागू करने के बाद carry के बिना साधारण additions कई बार चलाकर सामान्य radix 2^64 की तुलना में performance काफ़ी बेहतर हो जाती है
  • normalization के लिए carry propagation अंत में केवल एक बार किया जाता है

code उदाहरण

  • मानों को 5 registers में बाँटकर रखा जाता है, जिससे carry के बिना addition संभव होता है
  • normalization में हर limb के ऊपरी bits निकाले जाते हैं, उन्हें बगल वाले limb में जोड़ा जाता है, और अपने carry मान को 0 करने की प्रक्रिया दोहराई जाती है

subtraction तक विस्तार

  • subtraction पर भी इसी तरह का तरीका लागू किया जा सकता है
  • इस स्थिति में carry नकारात्मक भी हो सकता है, इसलिए limb को signed integer की तरह माना जाता है
  • limb का सबसे ऊपरी bit sign bit के रूप में आवंटित होता है, इसलिए addition की तुलना में एक बार में प्रोसेस किए जा सकने वाले operations की संख्या थोड़ी कम हो जाती है

निष्कर्ष

  • carry delay तकनीक, limbs की संख्या बढ़ने और conversion work जुड़ने के बावजूद, कुल operation performance को वास्तव में काफ़ी बेहतर बनाती है
  • Radix 2^51 ट्रिक बड़े integer arithmetic, cryptography जैसे उच्च performance की मांग वाले क्षेत्रों में व्यापक रूप से उपयोग होती है
  • यह तकनीक वास्तविक hardware/algorithm performance को optimize करने का एक महत्वपूर्ण विचार है

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

1 टिप्पणियां

 
GN⁺ 2025-05-31
Hacker News की राय

  • 2^51 संख्या देखकर पहले लगा कि बात double टाइप में integer स्टोर करने की है, लेकिन फिर समझ आया कि जिन मानों तक Integer को double में ठीक-ठीक रखा जा सकता है, वह 2^53-1 है

  • AVX512 (और कुछ हद तक AVX2 भी) में 256-बिट addition को काफ़ी कुशल तरीके से लागू करने का माहौल मिलता है, और ज़्यादा संख्याएँ registers में रखी जा सकती हैं
    सीधा उदाहरण नीचे दिए गए कोड जैसा है

__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-बिट addition तक बढ़ाना भी बहुत आसान है

  • खासकर कुछ Intel CPU आर्किटेक्चर में सिर्फ AVX512 instructions इस्तेमाल करने भर से पूरे processor की clock नीचे आ सकती है, जिससे कुल performance असंगत या उल्टा धीमी भी हो सकती है
    संदर्भ stackoverflow लिंक में देखा जा सकता है

  • “13 बिट की जगह 12 बिट क्यों नहीं?” इस सवाल पर, यहाँ सबसे ऊपरी bit (limb) की carry handling को नज़रअंदाज़ किया गया है ताकि overflow होने पर wraparound तरीके से काम हो
    इसका नतीजा यह है कि सबसे ऊपरी limb को 52 बिट दिए जाते हैं, इसलिए उसमें बाकी limbs की तुलना में जगह जल्दी खत्म होने की कमी है, लेकिन व्यवहार C भाषा में unsigned integer addition जैसा रहता है
    तो फिर सुझाव यह आता है कि सबसे ऊपरी limb को 64 बिट और बाकी चार limbs को 48 बिट-48 बिट क्यों न दिया जाए
    ऐसा करने पर normalization से पहले ज़्यादा operations जमा किए जा सकते हैं, और word alignment जैसी सुविधाएँ भी मिलती हैं
    overflow handling के गुण भी वही रहते हैं

    • अगर सिर्फ सबसे ऊपरी limb को 64 बिट दिए जाएँ, तो दो संख्याओं के limbs जोड़ते ही overflow बहुत जल्दी हो जाएगा
      उदाहरण के लिए अगर दोनों का मान 2^63 हो तो तुरंत overflow
      wraparound arithmetic में तो यह ठीक है, लेकिन सामान्य मामलों में यह व्यावहारिक नहीं

    • ऐसी बनावट में OP की तरह 5 नहीं बल्कि 6 words चाहिए होंगे
      instructions भी ज़्यादा लगेंगी

    • लक्ष्य यह है कि 256-बिट गणित को 5 64-बिट registers में संभाला जाए
      यानी हर word के लिए 256/5 = 51.2 बिट का बँटवारा आदर्श है
      अगर मामला सिर्फ 256 बिट तक सीमित हो तो ठीक है, लेकिन सामान्य big-int library के लिए यह सर्वोत्तम नहीं
      पहले के दौर में एक carry के लिए ठीक 1 byte बचाने का संदर्भ था, और barrel shifter न होने के समय alignment के लिए 64 में से 56 बिट ही इस्तेमाल करना बेहतर माना जाता था
      RISC-V में hardware flags नहीं होते, इसलिए यह चर्चा और महत्वपूर्ण हो जाती है

  • आधुनिक x86 CPU (जैसे Intel Broadwell, AMD Ryzen) में Intel ADX instructions का उपयोग करके 2^51 radix representation उन स्थितियों में भी तेज़ हो सकती है जहाँ पारंपरिक तौर पर इसकी बढ़त थी, जैसे Curve25519

  • संबंधित चर्चा सामग्री

  • मुख्य सीख यह है कि अगर operations एक-दूसरे से स्वतंत्र हों, तो ज़्यादा operations को parallel चलाना वास्तव में तेज़ हो सकता है
    इसके विपरीत, अगर dependencies के कारण उन्हें क्रम से चलाना पड़े, तो operations कम होने पर भी चीज़ें धीमी हो सकती हैं
    यह विचार सिर्फ long integer arithmetic तक सीमित नहीं, कई क्षेत्रों में लागू होता है

    • 64-बिट chunks में बाँटकर carry हो या न हो, इन दोनों संभावनाओं के लिए दो cases पहले से parallel में चलाने, और बाद में असली carry के हिसाब से सही परिणाम चुनने का सुझाव
      इस तरीके में additions की संख्या दोगुनी हो जाती है, लेकिन propagation की गति linear के बजाय log(bits) स्तर तक तेज़ हो जाती है

    • इस तकनीक में जो बात पहले समझ नहीं आई, वह यह थी कि मूल रूप से ripple carry, N मानों को जोड़ते समय N-1 बार चलता है, और यह तरीका उसे सिर्फ एक बार चलाता है
      carry handling ज़्यादा जटिल हो जाती है, लेकिन addition parallel की जा सकती है
      हाँ, input numbers को 5-register units में बाँटने का काम भी parallel होना चाहिए, तभी कुल efficiency सार्थक बनेगी

    • यह नियम दसियों हज़ार nodes वाले supercomputer या cloud स्तर तक भी बढ़ाया जा सकता है
      अगर बहुत सारे cores उपलब्ध हों, तो overhead नगण्य हो सकता है

    • इस विचार में NVidia की भी रुचि है और कई क्षेत्रों में अच्छे परिणाम मिल रहे हैं

  • शीर्षक में राय नहीं जोड़नी चाहिए, यह HN guideline है, लेकिन बहुत बढ़ा-चढ़ाकर clickbait शीर्षक रखना भी पसंद नहीं
    “कुछ x86 आर्किटेक्चरों में carry dependency के बिना 64-बिट integer parallel addition संभव करने वाली radix 2^51 trick” जैसा सीमित शीर्षक ज़्यादा सटीक लगता है

  • अफ़सोस है कि यह लेख कुछ महीने पहले पढ़ लिया होता तो मदद मिलती
    buffer को मनचाहे radix में encode/decode करते समय carry पूरे buffer में फैल जाती थी और algorithm बहुत धीमा हो जाता था
    आख़िर में 'खाली जगह' छोड़कर उसे chunks में बाँटकर carry संभाली, और यह trick उससे मिलती-जुलती लगती है
    व्यवहार में कुछ bits बर्बाद करने के बदले computation या network bandwidth बचाने का तरीका चुना
    जिज्ञासा है कि क्या इस तरह की carry handling को भी post-processing में समेटा जा सकता है
    उम्मीद यही है कि इससे लगभग सारे फायदे मिल सकें

  • x86_64 माहौल में ही काम करने के अनुभव के बाद, यह साफ़ दिखता है कि RISC-V में carry flag न होना ज़रूरी नहीं कि गलत डिज़ाइन हो

    • इस तरीके के अलावा 64-बिट limbs बनाए रखते हुए, सबको uint64_t variables के रूप में carry-safe addition करने का तरीका भी समझाया गया
      प्रवाह कुछ ऐसा है
    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:

    अहम बात यह है कि जब addition का परिणाम (limb) all-ones न हो, तो उस limb का carry-out carry-in पर निर्भर नहीं करता, बल्कि सिर्फ मूल addition result पर निर्भर करता है
    जबकि मान all-ones हो तो carry-out = carry-in
    अगर branch structure ऐसी हो कि prediction लगभग ज़रूरी न पड़े, तो इसे पूरी तरह parallel चलाया जा सकता है
    संभावना के हिसाब से 2^64 में सिर्फ 1 बार यह धीमा पड़ता है, लेकिन 4-wide machine जैसी जगहों पर बड़ा फ़ायदा नहीं
    8-wide machine या 8-limb संरचना में यह अर्थपूर्ण performance gain दे सकता है
    x86_64 पर यह उतना उपयुक्त नहीं, लेकिन Apple M* series जैसी 8-wide machines पर इसकी उपयोगिता हो सकती है
    Tenstorrent के 8-wide RISC-V Ascalon processor, Ventana, Rivos, XiangShan आदि में भविष्य की संभावना दिखती है
    SIMD संरचना और तेज़ 1-lane shift (slideup) instruction वाली architectures में इसका असर और बढ़ेगा

    • carry-save addition हमेशा add-with-carry से बेहतर नहीं होती
      multi-word addition की ये दो किस्में एक-दूसरे की जगह नहीं ले सकतीं, दोनों के अपने फायदे-नुकसान हैं
      इसलिए ADC/SBB instructions का ISA में मूल रूप से होना ठीक है, और register-आधारित flags storage भी संभव हो सकता है
      RISC-V की अधिक गंभीर कमी यह है कि उसमें integer overflow flag नहीं है
      overflow detection के लिए software workaround चाहिए हो, तो उसका performance नुकसान carry bit workaround से कहीं ज़्यादा होता है

    • RISC-V में carry flag का न होना इस बात से निकला कि C भाषा ने binary carry flag को अनदेखा किया
      व्यवहार में carry flag का उपयोग काफ़ी कम होता है

    • सिर्फ मुझे ही ऐसा नहीं लगा कि “अगर carry flag वैसे भी धीमा है, तो risc5 gmp विवाद क्यों था?”

  • 'Radix trick' को data structures पर भी लागू किया जा सकता है
    Okasaki की किताब 'Purely Functional Data Structures' में भी एक दिलचस्प उदाहरण है