HN परिचय: matrix multiplication में multiplications की संख्या आधी करने वाली तकनीक

 (github.com/trevorpogue)
3 पॉइंट द्वारा GN⁺ 2024-03-17 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • यह repository GEMM और deep learning hardware accelerators में कम hardware resources या कम execution time के साथ वही matrix multiplication result निकालने वाले systolic array architecture को verify करने के लिए source code है
  • प्रस्तावित तरीका कुछ matrix multiplications को सस्ते low-bitwidth additions से बदलता है, और इसका लक्ष्य समान performance के लिए जरूरी multipliers को आधा करना या प्रति MAC unit performance बढ़ाना है
  • results समान compute platforms पर बने state-of-the-art accelerators की तुलना में CNN inference में अधिकतम 3× speedup, प्रति multiplier/clock multiplication throughput 2× से अधिक, कम area और high clock frequency हासिल करते हैं
  • scope dense matrix multiplication और इसे मुख्य रूप से इस्तेमाल करने वाली fully-connected layers, CNN, RNN, attention layers/transformer models तक है, और मुख्यतः fixed-point/quantized inference में मौजूदा तरीकों जैसा ही output बनाता है
  • architecture को मौजूदा systolic array जैसी functionality और interfaces बनाए रखने के लिए design किया गया है, इसलिए बिना extra preprocessing या postprocessing के मौजूदा accelerator system के MXU को replace करके integrate किया जा सकता है

Project का उद्देश्य और परिणाम

  • Algebraic Enhancements for GEMM & AI Accelerators में GEMM और deep learning hardware accelerator systems का source code शामिल है
  • यह system hardware में प्रस्तावित या अभी तक पर्याप्त रूप से explore न किए गए efficient matrix multiplication algorithms को implement करने वाले systolic array architectures को verify करने के लिए इस्तेमाल होता है
  • लक्ष्य समान output को कम hardware resources या कम execution time में compute करना है
  • प्रस्तुत performance इस प्रकार है
    • उसी प्रकार के compute platform पर implement किए गए state-of-the-art accelerators की तुलना में CNN inference में अधिकतम 3× तेज
    • conventional limit 1 से अधिक mults/multiplier/clock cycle 2× से ज्यादा
    • कम area और high clock frequency

Papers और PhD thesis में verified architectures

  • Fast Inner-Product Algorithms and Architectures for Deep Neural Network Accelerators
    • matrix multiplication और deep learning hardware architectures में समान performance हासिल करने के लिए जरूरी multipliers को आधा करता है
    • वैकल्पिक inner-product algorithm multiplications के आधे हिस्से को सस्ते low-bitwidth additions से बदलता है
    • प्रस्तावित systolic array को मौजूदा systolic array systems में replacement के रूप में लगाया जा सकता है, और बाकी system की functionality या design बदले बिना प्रति MAC unit performance को 2× बढ़ा सकता है
    • सार्वजनिक full text: https://arxiv.org/abs/2311.12224
  • Karatsuba Matrix Multiplication and its Efficient Custom Hardware Implementations
    • Karatsuba multiplication को matrix multiplication तक extend करने वाला KMM प्रस्तावित करता है
    • integer matrix multiplication complexity घटाता है, और matrix multiplication व deep learning accelerators में area या execution time में सुधार देने वाली custom hardware implementations प्रस्तुत करता है
    • सार्वजनिक full text: https://arxiv.org/abs/2501.08889
  • Strassen Multisystolic Array Hardware Architectures
    • Strassen के fast matrix multiplication algorithm के लिए पहली efficient custom hardware implementation प्रस्तुत करता है
    • deep learning accelerators में state-of-the-art performance हासिल करता है
    • सार्वजनिक full text: https://arxiv.org/abs/2502.10063
  • Algebraic Enhancements for Systolic Arrays PhD thesis
    • ऊपर के तीन तरीकों, deep learning acceleration, algebraic enhancements, प्रस्तुत deep learning accelerator system design और future work को cover करती है
    • Online: https://macsphere.mcmaster.ca/handle/11375/30640

MAC/multiplier प्रति performance क्यों बढ़ाई जाती है

  • deep learning models का अधिकांश compute work आमतौर पर matrix multiplication में map किया जा सकता है, जो multiply-accumulate operations की श्रृंखला से बना होता है
  • अतिरिक्त algebraic innovation न हो तो deep learning accelerator का throughput प्रति clock cycle किए जा सकने वाले MAC operations की अधिकतम संख्या तक सीमित रहता है
  • deep learning accelerators में कई MAC units होते हैं, इसलिए multipliers और MAC units GEMM और deep learning accelerators में hardware area का बड़ा हिस्सा लेने वाले compute resources बन जाते हैं
  • accelerator का throughput सीधे उस multipliers की संख्या से सीमित हो सकता है जिसे hardware budget support कर सकता है
    • FPGA implementation में MAC unit instantiate करने वाले DSP units, LUTs और registers से पहले कम पड़ सकते हैं
  • यह project matrix multiplication algorithms और custom hardware implementations में algebraic enhancement apply करके इस सीमा से आगे जाने की दिशा explore करता है

Scope और constraints

  • प्रस्तावित systolic array hardware architecture dense matrix multiplication acceleration को बेहतर करता है
  • इसका उपयोग उन DNN models और layers में किया जा सकता है जो मुख्य रूप से matrix multiplication में decompose होते हैं
    • fully-connected layer
    • CNN
    • RNN
    • attention layer और transformer model
  • अधिकांश योगदान fixed-point data types और quantized neural network inference पर केंद्रित हैं
    • कुछ fixed-point concepts भविष्य में floating point तक extend किए जा सकते हैं
    • fixed-point data types इस्तेमाल होने के कारण प्रस्तुत algorithms और hardware architectures मौजूदा algorithms/architectures जैसा ही output generate करते हैं
    • numerical stability में कोई बदलाव नहीं है
  • results FPGA पर verify किए गए हैं, लेकिन प्रस्तावित architectures general हैं और अधिकांश improvements custom integrated circuit और FPGA implementations दोनों पर लागू हो सकते हैं
  • architecture systolic array-based है
    • यह Google TPU जैसे GEMM और deep learning acceleration designs में इस्तेमाल होने वाला efficient design type है
    • कुछ concepts भविष्य में non-systolic array designs तक extend किए जा सकते हैं
    • मौजूदा systolic array जैसी ही functionality और interfaces बनाए रखता है
    • algebraic enhancement systolic array के अंदर पूरी तरह self-contained है, इसलिए extra preprocessing या postprocessing steps की जरूरत नहीं है

Performance results preview

  • [1] और [3] के architectures को combine करने वाले synthesis और performance results समान compute platforms पर state-of-the-art accelerators की तुलना में ये हासिल करते हैं

    • CNN inference में अधिकतम 3× तेज

    • mults/multiplier/clock cycle 2× अधिक

Accelerator system structure

  • source code में implemented deep learning accelerator system [1]-[4] में proposed systolic arrays को host और verify करने के लिए इस्तेमाल होता है
  • system implementation non-sparse DNN model के fixed-point/quantized input inference के लिए specialized है
    • convolutional layer
    • fully-connected layer
    • pooling layer
  • सभी DNN layers hardware में पूरी तरह accelerated हैं
  • एक single hardware design arbitrary layer dimensions और kernel sizes वाले ML model को accelerate कर सकता है
  • input bitwidth और systolic array dimension parameters के रूप में set किए जा सकते हैं
  • यह general GEMM accelerator के रूप में भी highly optimized है

मुख्य blocks

  • Matrix Multiply Unit / MXU

    • matrix multiplication करने वाला systolic array architecture शामिल करता है
    • [1]-[4] के प्रत्येक method में proposed अलग-अलग systolic array/MXU को system के MXU की जगह replace किया जाता है

  • GEMM Unit

    • MXU, SRAM, addition logic शामिल करता है
    • matrix tiles को accumulate करके arbitrary size matrices के GEMM execution को संभव बनाता है

  • Post-GEMM Unit

    • matrix multiplication output पर neural network-specific functions perform करता है
    • bias addition, quantization के लिए inter-layer rescaling, activation, padding, pooling शामिल हैं

  • Memory Unit

    • layer activations रखने वाला on-chip SRAM और memory access control logic शामिल करता है
    • data duplication या delay के बिना convolution को GEMM में in-place map करने वाले efficient caching और memory access hardware algorithms implement करता है
    • SRAM memory और control को half या quarter clock rate पर चलाते हुए full clock rate पर नया data output करने वाला memory partitioning scheme इस्तेमाल करता है, जिससे overall system frequency और power improve होते हैं

  • Off-chip DDR DRAM

    • weights store करने के लिए इस्तेमाल होता है

  • RxTx Unit

    • host से जुड़ने वाले PCIe interface को handle करता है

  • Instruction Unit

    • host द्वारा भेजे गए accelerator instructions decode करता है
    • single hardware design में arbitrary layer dimensions और kernel sizes वाले ML model को accelerate करने में सक्षम बनाता है

Source code structure

  • compiler
    • Python ML model description को accelerator instructions में parse करने वाला compiler
    • PCIe driver से interface करके accelerator पर model execution शुरू करने, results और performance counters पढ़ने, और correctness test करने वाला code शामिल है
  • rtl
    • synthesizable SystemVerilog accelerator RTL
  • sim
    • verification के लिए simulation environment setup scripts
  • tests
    • Python और cocotb में लिखे गए UVM testbench source code
  • utils
    • project में इस्तेमाल किए गए additional Python packages और development utility scripts
  • rtl/top/define.svh और rtl/top/pkg.sv
    • कई configurable parameters शामिल करते हैं
    • FIP_METHOD systolic array type define करता है, जिनमें baseline, FIP, FFIP [1] आदि examples हैं
    • SZI और SZJ systolic array की height और width define करते हैं
    • LAYERIO_WIDTH और WEIGHT_WIDTH input bitwidth define करते हैं
  • rtl/arith
    • mxu.sv और mac_array.sv शामिल करता है
    • FIP_METHOD value के आधार पर baseline और proposed कुछ systolic array architectures FIP, FFIP [1] का RTL रखता है

Additional documentation

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

1 टिप्पणियां

 
GN⁺ 2024-03-17
Hacker News की टिप्पणियाँ

  • यह काफ़ी शानदार लग रहा है, लेकिन इसमें पेंच क्या है? उदाहरण के लिए, यह पहले से accelerators में implement क्यों नहीं है, यह जानने की जिज्ञासा है
    क्या यह सचमुच बस भुला दिया गया algorithm है, या फिर accelerator बनाने की लागत आदि को प्रभावित करने वाली कोई पाबंदी है?

    • यह सिर्फ़ एक software algorithm नहीं, बल्कि hardware architecture optimization है
      इसका फ़ायदा लेने के लिए algorithm के dimensions के हिसाब से hardware बनाना पड़ेगा, और वह काफ़ी महँगा फ़ैसला है
    • अगर यह fixed-point matrix multiplication accelerator हो, तो कोई ख़ास पेंच नहीं है; मैं इसे बस नज़रअंदाज़ किया गया algorithm मानूँगा
      यह Winograd के algorithm पर आधारित है, और संयोग से Winograd ने बाद में CNN acceleration में बहुत मशहूर हुआ एक अलग algorithm भी प्रस्तावित किया था, इसलिए संभव है कि इस algorithm पर कम ध्यान गया हो। हालाँकि, यह सिर्फ़ अटकल है
    • matrix multiplication algorithms बहुत हैं और हर एक के अपने बड़े फायदे-नुकसान हैं
      बात हमेशा accuracy, runtime, scalability के बीच संतुलन की होती है, और floating-point में इस तरीके की accuracy ख़राब हो सकती है
    • यह पूरी तरह भुलाया नहीं गया है
      UMAC जैसे pseudo-inner-product आधारित Wegman-Carter authenticators में यह कुछ हद तक अब भी मौजूद है। पृष्ठभूमि के लिए [1] का chapter 3 देख सकते हैं
      [1] https://cr.yp.to/antiforgery/pema-20071022.pdf
    • मैंने बस सरसरी तौर पर देखा है, इसलिए अगर मैं ग़लत हूँ तो सुधार दें, लेकिन मेरी समझ में यह matrix multiplication का replacement नहीं, बल्कि AI/ML में दिखने वाले linear systems के लिए काफ़ी अच्छे नतीजे देने वाला एक approximation method है
      उस उपयोग के लिए तो यह काफ़ी ठीक लगता है

  • इससे मुझे 2018 की याद आ गई, जब मैंने कुछ ऐसा ही करने की कोशिश की थी, लेकिन PhD applications सब reject हो गईं और बात वहीं रुक गई
    https://github.com/ixaxaar/pytorch-dni
    यहाँ का concept एक कदम आगे जाता है, और external network से backpropagation को replicate करने की कोशिश करता है, साथ ही यह दावा भी करता है कि दिमाग़ सच में शायद ऐसा ही करता हो

    • मुझे इनके बीच का connection समझ नहीं आ रहा
      यह काम matrix multiplication का low-level optimization है, जबकि लिंक किया गया repository backpropagated gradients को किसी सस्ते estimate से replace करने की कोशिश जैसा लगता है। दोनों के बीच समानता क्या है, यह जानना चाहूँगा
    • यह मुझे no free lunch जैसी स्थिति लगती है
      gradients को इस तरह approximate करके जो समय बचता है, क्या वह gradient accuracy के नुकसान की वजह से ज़्यादा training iterations की ज़रूरत पड़ने में खत्म नहीं हो जाएगा?
    • तकनीकी चर्चा से अलग, मुझे यह जानने की उत्सुकता है कि वह architecture GIF किससे बनाया गया था। काफ़ी अच्छा दिखता है

  • यह सच में दिलचस्प है और पढ़ने लायक है। जो लोग comments में यह लेकर उलझन में हैं कि यह बेहतर क्यों है, उनके लिए कहूँ तो यह paper FPGA या ASIC जैसे hardware पर matrix multiplication pipeline को synthesize करने की बात कर रहा है
    CPU या GPU पर addition और multiplication का समय आम तौर पर काफ़ी समान होता है, इसलिए फ़र्क़ उतना महसूस नहीं होता, लेकिन multiplication unit कहीं ज़्यादा transistor घेरते हैं। अगर circuit की complexity घटाई जाए, तो speed और parallel throughput बढ़ सकते हैं, जबकि power और wiring complexity कम हो सकती है। यह approach efficient sparse matrix multiplication accelerators के लिए खास तौर पर उपयोगी हो सकती है
    matrix multiplication में multiplication हटाने का एक और बढ़िया तरीका दूसरा semiring इस्तेमाल करना है [1]। उदाहरण के लिए, Tropical Semiring [2] multiplication को addition से, और addition को min या max से बदल देता है। यह अब भी matrix multiplication ही है, लेकिन binary operations बदले हुए रूप में। अपेक्षाकृत नया क्षेत्र Tropical Algebra [3] अभी काफ़ी सक्रिय और समृद्ध शोध का विषय है, और इसका उपयोग कई optimization समस्याओं तथा neural network optimization research [4] में हो रहा है
    यह तरीका hardware synthesis के लिए भी अच्छा बैठता है, क्योंकि अधिकांश FPGA configurable logic blocks एक clock में add/min/max कर सकते हैं, जबकि efficient multiplication के लिए fixed dedicated on-chip hardware multipliers चाहिए होते हैं
    semiring से जुड़ा एक और तरीका, जिससे multiplication को कुशलता से हटाया जा सकता है, Log Semiring [5] का उपयोग है। Markov chain जैसी स्थितियों में जब probabilities को लगातार multiply करना पड़ता है, तो संख्याएँ जल्दी बहुत छोटी हो जाती हैं और floating-point precision गिर जाती है। पहले log लेकर scaling करने पर multiplication addition बन जाता है, और addition x + log1p(exp(y - x)) बन जाता है
    [1] https://en.wikipedia.org/wiki/Semiring
    [2] https://en.wikipedia.org/wiki/Tropical_semiring
    [3] https://en.wikipedia.org/wiki/Tropical_geometry
    [4] https://proceedings.mlr.press/v80/zhang18i/zhang18i.pdf
    [5] https://en.wikipedia.org/wiki/Log_semiring

    • [4] वाला paper सच में बेहद आकर्षक है
      मैं इस क्षेत्र में लगभग शुरुआती हूँ, लेकिन ऐसा लगता है कि यह दिखाता है कि लगभग सभी ReLU networks को दो tropical polynomials के tropical ratio के रूप में व्यक्त किया जा सकता है, और इसलिए surface visualization जैसे geometric principles से उनका विश्लेषण किया जा सकता है। बाद की नई research में भी इसे cite किया गया है: https://scholar.google.com/scholar?cites=1003719112553620451... जानने की उत्सुकता है कि वहाँ कोई सार्थक प्रगति हुई है या नहीं
    • वाह, Unified Algebra तो ठीक यही विषय कवर करता है
      http://www.cs.toronto.edu/~hehner/UA.pdf
    • log लेकर संख्याओं को scale करने से multiplication addition बन जाता है और addition x + log1p(exp(y - x)) बन जाता है, लेकिन log number system में addition/subtraction, multiplication की तुलना में काफ़ी महँगे होते हैं
      खासकर अगर सही rounding result तक की चिंता करनी हो, तो ज़रूरी hardware lookup tables काफ़ी बड़े हो जाते हैं
    • log लेकर multiplication को addition में बदलने का तरीका क्या दशकों से इस्तेमाल हो रही GF(2^x) की approach जैसा ही नहीं है?
      मेरे दिमाग़ में आने वाली एकमात्र सीमा field का size है
    • कुछ हद तक संबंधित चीज़ number-theoretic transform है
      https://ieeexplore.ieee.org/abstract/document/1451721

  • यह कि यह वास्तव में काम करता है, काफ़ी हैरान करने वाला है
    आम तौर पर multiplication इस्तेमाल करना है या addition, यह पहचानने की लागत, सीधे multiplication करने से ही धीमी पड़ती है। खासकर तब, जब बहुत बड़ी मात्रा में काम parallel में किया जा रहा हो

    • सोच रहा हूँ कि OpenBLAS और cuBLAS की तुलना में यह कितना अच्छा होगा

  • यह दिलचस्प है कि 1968 में ईजाद की गई प्रक्रिया अब तक इस उद्देश्य के लिए इस्तेमाल नहीं हुई

    • GF(2^x) के लिए भी पिछली सदी के मध्य तक किसी को नहीं पता था कि उसका उपयोग कहाँ होगा
      अरे हाँ, पिछली सदी के मध्य तक तो computer science खुद भी लगभग मौजूद नहीं थी

  • अगर आपको matrix multiplication के sub-cubic time algorithms के पीछे की mathematical theory में रुचि है, तो यहाँ से शुरू कर सकते हैं: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
    अनुमान है कि हर real j > 0 के लिए कोई n मौजूद है, ऐसा कि किसी भी n x n matrices की जोड़ी को O(n^(2+j)) steps में multiply किया जा सकता है
    फ़िलहाल 2+j = w = 2.3728596 सिद्ध है, यानी j > 0.3728596 के लिए

    • पक्का नहीं कि यह कथन सही है
      अगर शुरुआत “हर j के लिए कोई n मौजूद है” से होती है, तो बाद के वाक्य में n और j constants बन जाते हैं। तब यह सिर्फ़ यही कहता है कि constant-size matrices को constant time में multiply किया जा सकता है। तकनीकी रूप से सही है, लेकिन लगता है कि इरादा इससे ज़्यादा मज़बूत दावा करने का था
    • समय के साथ प्रगति करना और कठिन होता दिख रहा है
      शायद j=1/e पर जाकर यह रुक जाए। इसे मैं अनुमान भी नहीं कहूँगा, बस मौजूदा मान के पास का एक सुविधाजनक constant है। अगर गणित हमारे साथ ऐसा मज़ाक करे तो काफ़ी मज़ेदार होगा
    • यह अनुमान लगाना कि यह किसी भी j > 0 के लिए सही होगा, काफ़ी साहसी है
      आप ऐसा क्यों सोचते हैं, इसकी कोई intuition साझा कर सकते हैं?

  • यह README इस बात को समझाने में सचमुच बहुत खराब है कि सुधार क्या है और गुणा की संख्या आधी कैसे की जाती है
    Big O रनटाइम क्या है? क्या यह ज्ञात optimal bounds को बदलता है?
    चित्र भी बिखरे हुए हैं और यह approach तेज़ या बेहतर क्यों है, यह लगभग समझाया ही नहीं गया। इसलिए PDF तक क्लिक करने का मन नहीं होता
    अगर आप प्रोजेक्ट की विश्वसनीयता बढ़ाना चाहते हैं, तो वास्तव में क्या हो रहा है इसे ईमानदारी और स्पष्टता से समझाना, और लोगों को बढ़ा-चढ़ाकर प्रचार जैसी छवियों से खींचने के बजाय साफ़ explanation और diagrams देना बेहतर होगा। यह समझना मुश्किल है कि यह बहुत बड़ी breakthrough है या मामूली बात। दुर्भाग्य से, यह AI hype का फायदा उठाने की एक जानबूझकर की गई कोशिश जैसा भी लग सकता है। जिस विकल्प पर मैं ज़्यादा भरोसा करना चाहूँगा, वह यह है कि लेखक को बस इसे सुधारकर बेहतर context देना चाहिए

    • “Big O रनटाइम क्या है?” के बारे में, गुणा को आधा करने का दावा Big O को प्रभावित नहीं करता
      पेपर(https://arxiv.org/abs/2311.12224) में गुणा की संख्या आधी करने वाला गणित समझना मुश्किल नहीं है। पारंपरिक matrix multiplication वाले equation 2 और equation 3~6 पढ़ लेना काफ़ी है
      जैसा विज्ञापित किया गया है, गुणा को आधा करने के बदले बहुत सारे addition/subtraction जोड़ना पड़ता है, यह काफ़ी स्पष्ट दिखता है। उसके बाद वे algorithm को बेहतर vectorize करते हैं, और जैसा अक्सर ऐसे काम में होता है, चीज़ें जल्दी जटिल हो जाती हैं
      मुख्य चिंता numerical stability है
    • README ज़्यादा कुछ नहीं समझाता, लेकिन पेपर की introduction खुद काफ़ी सुलभ है
      जहाँ तक यह कितना groundbreaking है, मैं इसे area-constrained fixed-point accelerators पर सीधे लागू किए जा सकने वाले एक साफ़ constant-factor improvement के रूप में देखूँगा। यह सब कुछ रातोंरात नहीं बदल देता, लेकिन यह भी नहीं कि इसका कोई महत्व ही नहीं है। अच्छा काम है
    • मैं elitist सुनाई नहीं देना चाहता, लेकिन मुझे इस comment की बात बिल्कुल समझ नहीं आ रही
      अगर कोई Big O notation को इतना भी नहीं समझता कि “गुणा को आधा करना” Big O को नहीं बदलता, तो फिर वह यह सवाल क्यों पूछ रहा है, यह मुझे समझ नहीं आता