Pentium में 3 से गुणा करने वाला जटिल dedicated circuit था

 (righto.com)
3 पॉइंट द्वारा GN⁺ 2025-03-04 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • 1993 के Intel Pentium में floating-point multiplication को तेज़ी से संभालने के लिए 3 गुना मान बनाने वाला dedicated ×3 circuit शामिल था, और सिर्फ़ इस छोटे circuit में ही हज़ारों transistor इस्तेमाल हुए
  • Pentium 64-bit multiplication में जोड़ने वाले terms को 64 से घटाकर 22 करने के लिए radix-8 multiplication इस्तेमाल करता है, लेकिन इस तरीके में ×3 multiple को तेज़ी से बनाना पड़ता है
  • ×3 calculation अपने-आप में x + 2x addition है, लेकिन बाकी multiplication stages इस result का इंतज़ार करती हैं, इसलिए carry lookahead और Kogge-Stone जैसी high-speed adder techniques की ज़रूरत होती है
  • circuit 8-bit blocks के 8 units और upper lookahead को मिलाने वाली hierarchical structure है, और overflow व rounding के लिए actual output 69-bit तक चौड़ा हो जाता है
  • लगभग 9000 transistors का एक ×3 circuit में इस्तेमाल होना दिखाता है कि Pentium generation में performance के लिए कितनी जटिल hardware optimization लगाई गई थी

Pentium ने अलग ×3 circuit क्यों रखा

  • Pentium का floating-point multiplier दो 64-bit numbers को radix-8 तरीके से multiply करता है
    • सामान्य binary multiplication हर bit पर 0 या multiplicand जोड़ता है, इसलिए 64-bit multiplication में 64 terms चाहिए होते हैं
    • radix-8 तरीका multiplier को 3-bit groups में बाँधकर 0~7 में से किसी एक से multiply करता है, इसलिए जोड़ने वाले terms 22 रह जाते हैं
  • 0~7 multiples में से कुछ hardware में अपेक्षाकृत सरलता से बनाए जा सकते हैं
    • ×2 को 1-bit left shift से handle किया जाता है
    • ×4 को 2-bit left shift से handle किया जाता है
    • ×6 और ×7 को Booth multiplication algorithm से अगले radix-8 digit के +1 और current digit के subtraction को combine करके handle किया जा सकता है
    • ×5 को ×8 में से ×3 घटाकर पाया जा सकता है
  • आखिर में मुश्किल multiple ×3 है, और Pentium इसे floating-point multiplier के अंदर dedicated circuit से solve करता है

साधारण addition bottleneck कहाँ बनता है

  • 3 गुना value input value और एक bit बाएँ shift की गई input value को जोड़कर बनाई जा सकती है
    • structure के हिसाब से यह x + 2x addition है
  • bottleneck addition process में carry propagation से पैदा होता है
    • ripple carry adder में lower bits से बना carry upper bits तक क्रम से पहुँचाना पड़ता है
    • ×3 result तैयार होने से पहले बाकी multiplication process शुरू नहीं हो सकती, इसलिए delay घटाना ज़रूरी है
  • Pentium carry को sequentially propagate करने के बजाय parallel calculate करने के लिए carry-lookahead adder इस्तेमाल करता है
    • हर bit पर carry generate और carry propagate signals बनते हैं
    • generate बताता है कि उस position पर carry बनता है
    • propagate बताता है कि incoming carry बाहर pass होता है
    • carry parallel में calculate हो जाए तो sum bits भी parallel में calculate किए जा सकते हैं

Kogge-Stone और 2-stage carry lookahead

  • carry lookahead को सीधे सरल तरीके से implement करने पर bit count बढ़ने के साथ circuit और wiring का burden बढ़ता है
    • bit position ऊपर जाने पर logic complex हो जाता है
    • बहुत inputs वाले gates electrical reasons से slow हो जाते हैं
  • Pentium 8-bit units में Kogge-Stone parallel prefix adder इस्तेमाल करता है
    • Kogge-Stone propagate/generate signals को range-wise merge करके carry को parallel calculate करता है
    • intermediate results reuse करके delay और circuit amount manage करता है
  • पूरे 64-bit को एक Kogge-Stone से process करने के बजाय इसे 2-stage hierarchical structure में बाँटा गया है
    • lower hierarchy में 8-bit Kogge-Stone circuits के 8 units हर block के अंदर carry calculate करते हैं
    • upper hierarchy हर 8-bit block को एक unit की तरह देखकर blocks के बीच carry calculate करती है
    • दोनों hierarchies को combine करके 64-bit sum के लिए ज़रूरी carry तेज़ी से उपलब्ध कराया जाता है
  • circuit को 64-bit के लिए माना जा सकता है, लेकिन असल में overflow prevention और rounding के लिए extra bits सहित 69-bit output बनाता है

carry-select से waiting time घटाना

  • हर 8-bit block में carry-select adder होता है
    • carry-in 0 होने पर और 1 होने पर sum, दोनों पहले से calculate किए जाते हैं
    • upper lookahead circuit actual carry-in बताता है तो multiplexer सही result चुनता है
  • यह तरीका ज़्यादा hardware इस्तेमाल करने के बदले time बचाता है
    • दो adders और result selection के लिए multiplexer चाहिए होता है
    • sum calculation और carry calculation को overlap करके total delay घटाया जाता है
  • सबसे lower 8-bit block में carry-in नहीं होता, इसलिए carry-select circuit की ज़रूरत नहीं होती
    • इस block के output bits XNOR gates से calculate होते हैं

8-bit block के अंदर क्या होता है

  • ×3 circuit का हर 8-bit block input lines को left adder और right path में बाँटता है
    • यह branching structure input value और एक bit left-shifted input value को जोड़कर ×3 implement करता है
  • block का upper part propagate/generate signals बनाने वाले circuit से बना है
    • ये signals 8-bit Kogge-Stone lookahead circuit में जाते हैं
    • Kogge-Stone part में हर bit position पर complexity अलग है, इसलिए यह repeating block जैसा नहीं बल्कि irregular दिखता है
  • block का lower part carry-select adder area है
    • दो sums पहले से calculate किए जाते हैं और carry-in के अनुसार multiplexer select करता है
    • carry-select adder block को surrounding circuits से संकरा layout किया गया है ताकि upper Kogge-Stone circuit के हिस्से के लिए जगह बने
  • हर block output bits को अगले multiplier circuit में भेजने से पहले driver circuit से amplify करता है

XNOR gates और transistor-level implementation

  • lower bit area के XNOR gates Pentium में multiplexer से implement किए गए हैं
    • Intel 386 ने XOR को AND-NOR gates से implement किया था, और Z-80 ने pass transistors इस्तेमाल किए थे, लेकिन Pentium का approach अलग है
  • संबंधित XNOR circuit चार inverters और pass-transistor multiplexer से बना है
    • input B multiplexer के दो inputs में से input A या inverted A को चुनता है
    • इससे XNOR function बनता है
  • chip photo analysis में upper दो metal layers हटाकर lower metal layer M1 और doped silicon areas देखे गए
    • polysilicon line जहाँ doped silicon को cross करती है, वह transistor gate बनता है
    • CMOS circuit ऊपर NMOS और नीचे PMOS transistors से बना होता है

BiCMOS output driver

  • ×3 circuit के output को high current की ज़रूरत होती है
    • हर ×3 signal floating-point multiplier के अंदर अधिकतम 22 terms को drive कर सकता है
    • destination circuit ×3 circuit से दूर हो सकता है
    • लंबी wiring और बहुत सारे transistor gates की वजह से capacitance बढ़ जाती है, और signal को तेज़ी से बदलने के लिए बड़ा current चाहिए होता है
  • Pentium ने एक ही chip पर bipolar transistor और CMOS को मिलाने वाली BiCMOS process इस्तेमाल की
    • Pentium ने signal delay को अधिकतम 35% घटाने के लिए BiCMOS circuits का व्यापक इस्तेमाल किया
    • Intel ने Pentium Pro, Pentium II, Pentium III, Xeon में भी BiCMOS इस्तेमाल किया
    • chip voltage घटने के साथ bipolar transistor का advantage कम हो गया, इसलिए BiCMOS अंततः इस्तेमाल से बाहर हो गया
  • ×3 circuit का driver ऐसी structure है जिसमें BiCMOS driver फिर दूसरे BiCMOS driver को drive करता है
    • high-current inverter के transistor gates बड़े होते हैं, इसलिए उन्हें drive करने के लिए intermediate stage चाहिए
    • छोटे signal को कई stages में बड़ा करने से total delay घट सकता है
  • BiCMOS driver का NPN transistor सामान्य MOS transistor से अलग बड़े box shape जैसा दिखता है
    • inverter output को high करने के लिए PMOS और low करने के लिए NMOS इस्तेमाल करने वाली standard CMOS structure अपनाता है
    • कुछ inverters strong high या strong low output देने के लिए asymmetric current characteristics के साथ design किए गए हैं

multiplication hardware से दिखती बढ़ती complexity

  • computer multiplication hardware का इतिहास 1950s तक जाता है
    • Booth multiplication technique 1951 में describe की गई थी
    • parallel multipliers 1960s के mid में Wallace और Dadda ने propose किए
  • शुरुआती microprocessors में hardware multiplication support limited था
    • 6502 जैसे processors में multiplication hardware नहीं था, इसलिए users को shift और addition से software implementation करना पड़ता था
    • Intel 8086 microcode से slow shift-and-add loop perform करता था
    • 386 में multiply unit शामिल था, लेकिन multiplication instruction में अधिकतम 41 clock cycles लगते थे
  • Pentium के समय तक लाखों transistors लगाए जा सकते थे, जिससे अधिक जटिल performance optimizations संभव हुईं
    • Pentium के floating-point multiplication में 3 clock cycles लगते हैं, और multiplication circuit उनमें से 2 cycles तक इस्तेमाल होता है
    • integer multiplication MUL 11 cycles के साथ काफ़ी धीमा है
    • 2008 की Nehalem microarchitecture ने floating-point multiplication time को 1 cycle तक घटा दिया
  • Pentium के ×3 multiplier में लगभग 9000 transistors हैं
    • यह 1976 के पूरे Z80 microprocessor से थोड़ा ज़्यादा है
    • ×3 circuit Pentium के floating-point unit में मौजूद floating-point multiplier का सिर्फ़ एक छोटा हिस्सा है

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

1 टिप्पणियां

 
GN⁺ 2025-03-04
Hacker News की राय

  • यह थोड़ा अलग मुद्दा है, लेकिन बहुत पहले ternary computer emulation पर काम करते समय मैंने 3 की घातों से division को bit shift और addition की series में बदलने वाला closed-form transformation खोजने की एक प्यारी-सी तरकीब इस्तेमाल की थी
    पहले देखें कि 1/3 - 1/2 = 2/6 - 3/6, यानी 1/3 = 1/2 - 1/2 (1/3) है
    इस equation को right-hand side में अनंत बार substitute करने पर 1/3 = -(-1/2)^N जैसा रूप मिलता है, और N की range 1..inf है
    सिर्फ 2 और 3 की घातों की pairs ही नहीं, दूसरे bases में भी कुछ ऐसा ही किया जा सकता है
    मतलब यह है कि 2 की घात के करीब वाले values के लिए सिर्फ adders और subtractors से fixed-time constant division circuit काफी आसानी से बनाया जा सकता है

    • कमाल है। ternary computer शायद three-state logic पर आधारित रहा होगा; क्या यह समझना सही होगा कि यह binary states encode करने वाले transistors या यहाँ तक कि vacuum tubes से भी कम reliable था?

  • Cinematronics arcade game processor में दो 12-bit accumulators होते हैं
    multiplication instruction इन दोनों को एक 24-bit value की तरह right shift करता है, और अगर least significant bit में 1 आता है तो memory contents add करता है
    इसलिए upper half को clear करके, lower half में एक value load करके, और दूसरे operand का memory address कैसे set किया जाता था यह मुझे याद नहीं, 1-bit multiplication को कई बार लगातार चलाया जाता था
    इससे 24-bit product मिल सकता है, लेकिन मैंने जो code देखा उसमें ज्यादातर 8 multiplications लगातार इस्तेमाल की गई थीं, और सबसे आम use game object coordinates को rotate करने के लिए 2x2 matrix multiplication था
    यह 1970s के mid में off-the-shelf 7400 series parts से बना था और peak throughput 5MIPS था

    • मुझे नहीं लगता कि एक multiplication ठीक-ठीक एक cycle की थी। तो 5MIPS भी जल्दी खर्च हो जाता होगा
      पिछले 20 सालों में मुझे fixed-point arithmetic करनी पड़ी है, और इससे पिछली generation के programmers के लिए सम्मान और बढ़ गया

  • carry lookahead, Kogge-Stone addition जैसी techniques के बारे में सुना हो सकता है—इस संदर्भ में Kogge का मतलब Peter Kogge है
    उन्होंने Stanford में PhD work किया, space shuttle से जुड़ा काम किया, वे IBM Fellow हैं, और पहले multicore CPU का आविष्कार करने वाले व्यक्ति हैं

    • यह तय है कि उनकी उपलब्धियाँ बहुत हैं, लेकिन पहले multicore CPU का आविष्कार किया जैसा phrase हटाने पर भी बात पूरी तरह सही रहेगी, और दुनिया शायद ऐसे phrases के बिना बेहतर होगी
      “multicore CPU” खुद, strict sense में, किसी एक invention से ज्यादा एक idea है। semiconductor history में एक stage पर पहुँचने के बाद यह काफी obvious और trivial idea भी है
      multicore CPU को सच में काम करने लायक बनाना trivial नहीं है, लेकिन वह भी कोई single invention नहीं है; और उस समय तक development teams इतनी बड़ी हो चुकी थीं कि कहना कि एक व्यक्ति ने सारे problems अकेले solve किए, उलटा अपमानजनक लगता है
      Kogge ने पहले multicore CPU development को lead किया हो सकता है, और दूसरे लोगों के feasible मानने से पहले उसे push करने वाले pioneer भी रहे होंगे, लेकिन किसी भी तरह वह उनका अकेले किया हुआ invention नहीं था
    • मेरी समझ में पहले multicore CPU की team को Kunle Olukotun ने lead किया था
    • एक और बात जोड़ूँ तो, Peter Kogge ने pipelined microarchitecture पर शुरुआती textbook लिखी थी, जिसे शुरुआती supercomputer vector processors कैसे design हुए यह सीखना चाहें तो पढ़ा जा सकता है: The Architecture of Pipelined Computers (1981)
    • Peter ने पहले हमारे lab के साथ advisory और collaboration किया था। वे remote sensing computation को sensors के ज्यादा करीब ले जाने वाले approach, आज की भाषा में edge computing, के समर्थक थे
      यह approach बौद्धिक रूप से काफी convincing है। अगर data को central computing तक ले जाने में latency या cost हो तो यह सही बैठता है, और हमारे case में space-based sensors होने से यह logic बनाया जा सकता था
      हालांकि मेरी जानकारी में यह processing style space-based processing systems में systematic तरीके से कभी adopt नहीं हुआ, और radar जैसे कई systems sensor के पास वाले hardware में temporary data reduction जरूर करते हैं
      वह connection बताने के लिए धन्यवाद

  • मैं author हूँ। सवाल हों तो जवाब दूँगा

    • बाद की machines में dedicated 3x multiplier का क्या हुआ, यह जानना चाहता हूँ। क्या वह किसी form में बना रहा, या strategy बदलने से बेकार हो गया?
    • Ken, क्या अब किताब निकालने का time नहीं हो गया?
    • शायद basic सवाल है, लेकिन क्या यह floating-point multiplication के लिए है? exponent भी add करने होते हैं, इसलिए असल में multiply होने वाला हिस्सा 64-bit से छोटा नहीं होता?
    • मेरी समझ धुंधली है, इसलिए अगर बहुत बेवकूफी भरा सवाल हो तो ignore कर दें, लेकिन अगर “×3 calculate कर सकते हैं तो ×8 से subtract करके ×5 मिल सकता है”, तो x4 को x7 से subtract करके x3 पाने जैसा क्यों नहीं कर सकते?

  • लगता है कुछ छूट रहा है
    अगर ×2 इतना आसानी से calculate हो सकता है कि 6x = 8x - 2x इस्तेमाल किया जा सके, और ×4 भी 4x = 4x के रूप में आसानी से calculate हो सकता है, तो समझ नहीं आता कि 3x को 2x + 1x के sum या 4x - 1x के difference से calculate करना उससे ज्यादा कठिन क्यों है
    और अगर ×6 किसी भी तरीके से आसानी से calculate हो सकता है, तो उस value को right shift करके ×3 क्यों नहीं बनाया जा सकता? extra step है, लेकिन वह extra step shift ही तो है

    • 64-bit multiplication में octal के हर digit के लिए एक, कुल 22 terms जोड़ने पड़ते हैं। primary-school multiplication याद कर लें
      हर term को calculate करना trivial होना चाहिए, इसलिए term पाने के लिए shift या sign inversion किया जा सकता है, लेकिन एक और addition नहीं किया जा सकता
      मुख्य बात यह है कि ×3 को एक बार पहले से calculate कर लें तो बाद में जरूरत वाले 22 terms में कहीं भी बस उसे डाल सकते हैं
      term के अंदर ×2 और ×1 डालकर ×3 नहीं बनाया जा सकता। ऐसा करने के लिए हर term में एक और adder चाहिए होगा
      दूसरे शब्दों में, जो चाहिए वह ×3 calculate करने वाला एक circuit है, 22 circuits नहीं
      ×6 वाले सवाल में, यह value term में negative ×2 डालकर, और conceptually अगले digit में 1 जोड़कर ×8 पाने के तरीके से calculate होती है। यह ×8 value एक बिल्कुल अलग term का हिस्सा है, इसलिए उसे right shift नहीं कर सकते
      numbers और sums बहुत इधर-उधर होते हैं, इसलिए जटिल है, लेकिन इस तरह देखने पर बात समझ आएगी

  • 3 गुना गुणा असल में एक आम operation है, खासकर address calculation में shift और addition से index को 3 से multiply करने के मामले बहुत होते हैं
    अगर इसे सीधे-सादे तरीके से implement करें तो latency काफी बढ़ जाती है। लेकिन इस circuit का इस्तेमाल करने पर LEA(Load Effective Address) instruction एक cycle में process हो सकता है, इसलिए इस पर इतना transistor budget खर्च करना काफी अच्छा चुनाव था

    • क्या यह circuit सचमुच वहीं इस्तेमाल होता है? लेख को समझने के हिसाब से यह circuit floating-point multiplication का हिस्सा है
    • समझ नहीं आ रहा कि मतलब क्या है
      LEA बस वह instruction है जो addressing mode द्वारा calculate किए गए address को उस address से data move करने के बजाय output operand में डालता है, और LEA जो address calculation कर सकता है, वे MOV instruction भी सभी कर सकता है
      x86 में MOV या LEA द्वारा इस्तेमाल होने वाला indexed addressing mode scale factor 3 support नहीं करता, सिर्फ 1, 2, 4, 8 जैसे 2 की powers support करता है। इसलिए address generation में 3 गुना multiplication इस्तेमाल करने की कोई जगह नहीं है
      लेख साफ कहता है कि 3 गुना multiplier floating-point multiplier का हिस्सा है

  • “यह ×3 multiplier लगभग 9000 transistors रखता है, जो पूरे Z80 microprocessor (1976) से थोड़ा ज्यादा है। याद रखें कि ×3 multiplier Pentium की floating-point unit के अंदर floating-point multiplier का एक छोटा हिस्सा है। यानी एक function का छोटा-सा टुकड़ा 17 साल पहले के पूरे microprocessor से ज्यादा complex है, और यह दिखाता है कि processor complexity कितनी जबरदस्त बढ़ी है।”
    ऐसी performance growth rate ने आज का software bloat पैदा किया। क्योंकि अगले साल की performance improvement algorithms और data-flow context/locality के बारे में critical तरीके से न सोचने की गलती को काफी हद तक ढक सकती थी
    आज, जितना मैंने पढ़ा है, हम silicon semiconductor technology और वर्तमान physics की समझ से reasonably जो किया जा सकता है, उसकी practical limits तक पहुंच चुके हैं। अब pendulum को उल्टी दिशा में चलना होगा, और computers को ज्यादा जोर से नहीं बल्कि ज्यादा smart तरीके से काम करना होगा

    • “वर्तमान physics की समझ से संभव practical limits” पर तो दशकों पहले ही पहुंच चुके थे
    • software bloat का hardware improvement की speed को पकड़ लेना Wirth's law के नाम से जाना जाता है: https://en.wikipedia.org/wiki/Wirth%27s_law
      हालांकि मुझे लगता है software bloat और तेजी से बढ़ रहा है
    • उल्टा, multiplier Z80 की तुलना में structure में कहीं ज्यादा regular है। Pentium का data path भी कई गुना wider है
    • function call का इतिहास: goto/jmp से instruction movement → vtable lookup → dictionary में hash और lookup → large language model चलाना
    • अच्छी बात है कि ज्यादातर applications में अभी भी improvement की काफी गुंजाइश है

  • “7 से multiply करने के बजाय, number का 8 गुना जोड़ते हैं और number घटाकर 7 गुना पाते हैं। ऐसा लग सकता है कि दो steps चाहिए, लेकिन left digit में 1 और multiply करने की trick से extra step के बिना 8 गुना coefficient मिल जाता है।”
    क्या इसका मतलब है कि main multiplier part में number डालने से पहले “next digit” में 1 जोड़ने वाला कोई adder है? वह खुद भी carry prediction circuit जैसा दिखता है
    यह कब जरूरी होता है, इस पर भी सोचने को मजबूर करता है: 7 = 8-1, 6 = 8-2, 5 = 8-3, 4 = 8-4
    आखिरी case के बारे में लेख ने नहीं कहा कि ऐसा करता है, लेकिन अगर 3-bit value के most significant bit से यह तय किया जाए कि next digit में 1 जोड़ना है या नहीं, तो शायद कुछ gates बचाए जा सकते हैं

  • ×3 circuit की जरूरत वाले radix-8 Booth multiplier को चुनना दिलचस्प है। यह maximum frequency बढ़ाने के लिए area/performance trade-off जैसा दिखता है, और यही काम ज्यादा pipelining से भी संभव रहा होगा, इसलिए लगता है latency cycle constraint रहा होगा

    • सही है, यह trade-off है। उस समय की कई दूसरी floating-point units radix-4 इस्तेमाल करती थीं, क्योंकि वे extra ×3 circuit से बच सकती थीं
      pipelining मुश्किल है, क्योंकि multiplication array को दो हिस्सों में बांटने के लिए कोई अच्छी जगह नहीं होती

  • https://github.com/EI2030/Low-power-E-Paper-OS/blob/master/P...
    8086: 29,000
    386: 275,000
    486: 12 लाख
    Pentium: 31 लाख
    मेरी याद के मुताबिक NSA 2000 के बाद किसी समय इस खेल में आई थी