HN Tanıtım: Çarpma sayısını yarıya indiren matris çarpımı

 (github.com/trevorpogue)
3 puan yazan GN⁺ 2024-03-17 | 1 yorum | WhatsApp'ta paylaş
  • Bu depo, GEMM ve derin öğrenme donanım hızlandırıcılarında aynı matris çarpımı sonucunu daha az donanım kaynağı veya daha kısa çalışma süresiyle hesaplayan systolic array mimarisini doğrulamak için kullanılan kaynak kodlarını içerir
  • Önerilen yöntem, bazı matris çarpımlarını daha düşük maliyetli düşük bit genişlikli toplama işlemleriyle değiştirir; aynı performans için gereken multiplier sayısını yarıya indirmeyi veya MAC birimi başına performansı artırmayı hedefler
  • Sonuçlar, benzer bilgi işlem platformlarındaki en yeni hızlandırıcılara kıyasla CNN çıkarımında 3×’e kadar hızlanma, multiplier/clock başına 2×’ten fazla çarpma işleme hacmi, düşük alan ve yüksek saat frekansı elde edildiğini gösterir
  • Kapsam; dense matrix multiplication ve bunu ağırlıklı olarak kullanan fully-connected layer, CNN, RNN, attention layer/transformer model’leri içerir; ağırlıklı olarak sabit noktalı ve kuantize çıkarımda mevcut yöntemlerle aynı çıktıyı üretir
  • Mimari, mevcut systolic array ile aynı işlev ve arayüzleri koruyacak şekilde tasarlandığından, ek ön işleme veya son işleme olmadan mevcut hızlandırıcı sistemlerde MXU’nun değiştirilmesi yoluyla entegre edilebilir

Projenin amacı ve sonuçları

  • Algebraic Enhancements for GEMM & AI Accelerators, GEMM ve derin öğrenme donanım hızlandırıcı sistemlerinin kaynak kodunu içerir
  • Bu sistem, önerilen veya henüz yeterince araştırılmamış verimli matris çarpımı algoritmalarını donanımda uygulayan systolic array mimarilerini doğrulamak için kullanılır
  • Amaç, aynı çıktıyı daha az donanım kaynağıyla veya daha kısa çalışma süresiyle hesaplamaktır
  • Sunulan performans sonuçları şunlardır
    • Aynı tür bilgi işlem platformunda uygulanmış en yeni hızlandırıcılara kıyasla CNN çıkarımında 3×’e kadar daha hızlı
    • conventional limit olan 1’i aşan mults/multiplier/clock cycle 2×’ten fazla
    • Düşük alan ve yüksek saat frekansı

Makalelerde ve doktora tezinde doğrulanan mimariler

MAC ve multiplier başına performansı artırma nedeni

  • Derin öğrenme modellerindeki hesaplama işlerinin çoğu genellikle matrix multiplication olarak eşlenebilir; bu da multiply-accumulate işlemlerinin ardışık dizisinden oluşur
  • Ek algebraic innovation olmadığında, derin öğrenme hızlandırıcılarının işleme hacmi clock cycle başına yapılabilecek MAC işlemi sayısının üst sınırıyla kısıtlanır
  • Derin öğrenme hızlandırıcıları çok sayıda MAC unit içerdiğinden, multiplier ve MAC unit’ler GEMM ve derin öğrenme hızlandırıcılarında donanım alanını büyük ölçüde kaplayan compute resource’lara dönüşme eğilimindedir
  • Accelerator işleme hacmi, donanım bütçesinin kaldırabileceği multiplier sayısıyla doğrudan sınırlanabilir
    • FPGA uygulamalarında, MAC unit örnekleyen DSP unit’leri LUT ve register’lardan önce tükenebilir
  • Bu proje, matrix multiplication algoritmalarına ve custom hardware uygulamalarına algebraic enhancement uygulayarak bu sınırı aşma yönünü araştırır

Kapsam ve kısıtlar

  • Önerilen systolic array donanım mimarisi, dense matrix multiplication hızlandırmasını iyileştirir
  • Ağırlıklı olarak matrix multiplication’a ayrıştırılan DNN model ve layer’larında kullanılabilir
    • fully-connected layer
    • CNN
    • RNN
    • attention layer ve transformer model
  • Katkıların çoğu sabit noktalı veri tiplerine ve kuantize sinir ağı çıkarımına odaklanır
    • Bazı sabit noktalı kavramlar gelecekte floating point’e genişletilebilir olabilir
    • Sabit noktalı veri tipleri kullanıldığından, sunulan algoritmalar ve donanım mimarileri mevcut algoritma ve mimarilerle aynı çıktıyı üretir
    • numerical stability’de değişiklik yoktur
  • Sonuçlar FPGA’da doğrulanmış olsa da önerilen mimariler geneldir ve iyileştirmelerin çoğu hem custom integrated circuit hem de FPGA uygulamalarına uygulanabilir
  • Mimari systolic array tabanlıdır
    • Google TPU gibi GEMM ve derin öğrenme hızlandırma tasarımlarında kullanılan verimli bir tasarım türüdür
    • Bazı kavramlar gelecekte non-systolic array tasarımlarına genişletilebilir olabilir
    • Mevcut systolic array ile aynı işlevleri ve arayüzleri korur
    • algebraic enhancement, systolic array içinde tamamen self-contained olduğundan ek ön işleme veya son işleme adımı gerektirmez

Performans sonuçlarına ön bakış

  • [1] ve [3]’teki mimarileri birleştiren sentez ve performans sonuçları, benzer bilgi işlem platformlarındaki en yeni hızlandırıcılarla karşılaştırıldığında şunları elde eder

    • CNN çıkarımında 3×’e kadar daha hızlı

    • mults/multiplier/clock cycle 2× daha yüksek

Hızlandırıcı sistem yapısı

  • Kaynak kodda uygulanan derin öğrenme hızlandırıcı sistemi, [1]-[4]’te önerilen systolic array’leri host etmek ve doğrulamak için kullanılır
  • Sistem uygulaması, non-sparse DNN model’lerinin sabit noktalı ve kuantize girdilerle çıkarımına özelleştirilmiştir
    • convolutional layer
    • fully-connected layer
    • pooling layer
  • Tüm DNN layer’ları donanımda tamamen hızlandırılır
  • Tek bir donanım tasarımında arbitrary layer dimensions ve kernel sizes’a sahip ML model’leri hızlandırılabilir
  • input bitwidth ve systolic array dimension parametre olarak ayarlanabilir
  • Genel amaçlı bir GEMM accelerator olarak da yüksek derecede optimize edilmiştir

Ana bloklar

  • Matrix Multiply Unit / MXU

    • Matris çarpımı yapan systolic array mimarisini içerir
    • [1]-[4]’teki her yöntemin önerdiği farklı systolic array/MXU, sistemdeki MXU yerine takılır

  • GEMM Unit

    • MXU, SRAM ve addition logic içerir
    • matrix tile’ları biriktirerek keyfi boyutlu matrislerde GEMM yürütülmesini mümkün kılar

  • Post-GEMM Unit

    • matrix multiplication çıktısı üzerinde neural network-specific function gerçekleştirir
    • bias ekleme, quantization için inter-layer rescaling, activation, padding ve pooling içerir

  • Memory Unit

    • layer activation’larını tutan on-chip SRAM ve memory access control logic içerir
    • data duplication veya delay olmadan convolution’ı GEMM’e in-place eşleyen verimli caching ve memory access hardware algoritmaları uygular
    • SRAM memory ve control’ü half veya quarter clock rate’te çalıştırırken full clock rate’te yeni veri çıkaran bir memory partitioning scheme kullanarak genel system frequency ve power’ı iyileştirir

  • Off-chip DDR DRAM

    • weights depolamak için kullanılır

  • RxTx Unit

    • host’a bağlanan PCIe interface’ten sorumludur

  • Instruction Unit

    • host tarafından gönderilen accelerator instruction’ları decoding eder
    • Tek bir donanım tasarımında arbitrary layer dimensions ve kernel sizes’a sahip ML model’lerini hızlandırmayı mümkün kılar

Kaynak kod yapısı

  • compiler
    • Python ML model description’ını accelerator instruction’a ayrıştıran compiler
    • PCIe driver ile arayüz kurarak accelerator’da model execution başlatan, sonuçları ve performance counter’ları okuyan ve correctness’ı test eden kodu içerir
  • rtl
    • Sentezlenebilir SystemVerilog accelerator RTL
  • sim
    • Doğrulama için simulation environment kurulum script’leri
  • tests
    • Python ve cocotb ile yazılmış UVM testbench kaynak kodu
  • utils
    • Projede kullanılan ek Python package’ları ve geliştirme amaçlı utility script’leri
  • rtl/top/define.svh ve rtl/top/pkg.sv
    • Birçok configurable parameter içerir
    • FIP_METHOD, systolic array type’ını tanımlar; baseline, FIP, FFIP [1] vb. örneklerdir
    • SZI ve SZJ, systolic array’in height ve width değerlerini tanımlar
    • LAYERIO_WIDTH ve WEIGHT_WIDTH, input bitwidth’ü tanımlar
  • rtl/arith
    • mxu.sv ve mac_array.sv dosyalarını içerir
    • FIP_METHOD değerine göre baseline ve önerilen bazı systolic array mimarileri olan FIP, FFIP [1] için RTL içerir

Ek belgeler

İlgili okumalar

1 yorum

 
GN⁺ 2024-03-17
Hacker News yorumları

  • Oldukça havalı görünüyor; acaba püf noktası ne? Örneğin neden hâlihazırda hızlandırıcılara uygulanmamış, merak ediyorum.
    Gerçekten sadece unutulmuş bir algoritma mı, yoksa hızlandırıcı üretim maliyetini vb. etkileyen kısıtlar mı var, merak ediyorum.

    • Bu basit bir yazılım algoritması değil, donanım mimarisi optimizasyonu.
      Fayda görmek için algoritmanın boyutlarına uygun donanım üretmek gerekiyor; bu da maliyetli bir karar.
    • Sabit noktalı matris çarpma hızlandırıcısı ise özel bir püf noktası yok; bence sadece gözden kaçmış bir algoritma.
      Winograd’ın algoritmasına dayanıyor; tesadüfen Winograd daha sonra CNN hızlandırmada çok ünlü hâle gelen ayrı bir algoritma da önerdiği için bu algoritma daha az ilgi görmüş olabilir. Tabii bu sadece bir tahmin.
    • Matris çarpma için birçok algoritma var ve her birinin artıları eksileri büyük.
      Her zaman doğruluk, çalışma süresi ve ölçeklenebilirlik arasında bir denge söz konusu; bu yöntemin kayan noktalı hesaplamada doğruluğunun kötü olma ihtimali var.
    • Tamamen unutulmuş değil.
      UMAC gibi sözde iç çarpım tabanlı Wegman-Carter doğrulayıcılarının içinde bir ölçüde yaşamaya devam ediyor. Arka plan için [1]’in 3. bölümüne bakılabilir.
      [1] https://cr.yp.to/antiforgery/pema-20071022.pdf
    • Üstünkörü göz attım; yanılıyorsam düzeltin ama bunu matris çarpmanın yerine geçen bir şey değil, AI/ML’de görülen türden doğrusal sistemlerde oldukça iyi sonuç veren bir yaklaşım yöntemi olarak anladım.
      O kullanım için yeterince iyi olabilir gibi geliyor.

  • 2018’de benzer bir şey denemeye çalışıp doktora başvurularımın hepsi reddedilince bırakmıştım; aklıma o geldi.
    https://github.com/ixaxaar/pytorch-dni
    Buradaki fikir bir adım daha ileri gidip geri yayılımı harici bir ağla kopyalamaya çalışıyor ve beynin gerçekten böyle yapma olasılığı olduğunu savunuyor.

    • Bağlantıyı pek göremiyorum.
      Bu çalışma matris çarpmanın düşük seviyeli bir optimizasyonu; bağlantısını verdiğiniz depo ise geri yayılmış gradyanları daha ucuz bir tahminle değiştirmeye çalışıyor gibi görünüyor. İkisi arasındaki benzerlik nedir, merak ediyorum.
    • Bu durum bana bedava öğle yemeği yok ilkesine yakın geliyor.
      Gradyanları böyle yaklaştırarak kazanılan zaman, gradyan doğruluğundaki kayıp yüzünden daha fazla eğitim iterasyonu gerekince ortadan kalkacak gibi; öyle değil mi?
    • Teknik tartışmadan bağımsız olarak, o mimari GIF’ini neyle yaptığını merak ediyorum. Güzel görünüyor.

  • Gerçekten ilginç ve okumaya değer. Yorumlarda bunun neden daha iyi olduğunu karıştıranlar için: makale, FPGA veya ASIC gibi donanımlarda matris çarpımı hattı sentezlemekten bahsediyor
    CPU veya GPU’larda toplama ve çarpma süreleri genel olarak benzer olduğu için farkı hissetmek zor olabilir; ancak çarpma birimleri çok daha fazla transistör kaplar. Devre karmaşıklığını azaltmak hızı ve paralel iş hacmini artırabilir, güç tüketimini ve kablolama karmaşıklığını düşürebilir. Bu yaklaşım özellikle verimli seyrek matris çarpımı hızlandırıcıları için faydalı olabilir
    Matris çarpımında çarpmayı ortadan kaldırmanın bir başka güzel yolu da farklı bir yarıhalka (semiring) kullanmaktır [1]. Örneğin Tropical Semiring [2], çarpmayı toplamaya, toplamayı da min veya max işlemine dönüştürür. Bu hâlâ matris çarpımıdır, sadece ikili işlemler değişmiştir. Nispeten yeni bir alan olan Tropical Algebra [3] araştırmaları şu sıralar oldukça aktif ve zengindir; çeşitli optimizasyon problemlerinde ve sinir ağı optimizasyonu araştırmalarında [4] kullanılıyor
    Bu yöntem de donanım sentezine çok uygundur; çünkü çoğu FPGA yapılandırılabilir mantık bloğu bir saat çevriminde add/min/max yapabilirken, verimli çarpma için sabit, özel yonga içi donanım çarpıcıları gerekir
    Çarpmayı verimli biçimde ortadan kaldırmanın ilişkili başka bir yarıhalka yolu da Log Semiring [5] kullanmaktır. Markov zincirlerinde olduğu gibi olasılıkları art arda çarpmak gerekiyorsa sayılar hızla çok küçülür ve kayan nokta doğruluğu düşer. Önce logaritma alıp ölçeklerseniz çarpma toplama olur, toplama ise x + log1p(exp(y - x)) hâline gelir
    [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]’teki makale gerçekten büyüleyici
      Bu alanda neredeyse acemiyim, ama görünüşe göre neredeyse her ReLU ağının iki tropical polinomun tropical oranı olarak ifade edilebildiğini ve bu nedenle yüzey görselleştirmesi gibi geometrik ilkelerle analiz edilebildiğini gösteriyor. Daha yeni çalışmalarda da atıf almış: https://scholar.google.com/scholar?cites=1003719112553620451... Burada anlamlı bir ilerleme olup olmadığını merak ediyorum
    • Vay, Unified Algebra tam olarak bununla ilgileniyor
      http://www.cs.toronto.edu/~hehner/UA.pdf
    • Logaritma alıp sayıları ölçekleyince çarpmanın toplamaya, toplamanın da x + log1p(exp(y - x)) hâline gelmesi kısmında, logaritmik sayı sisteminde toplama/çıkarma çarpmadan çok daha pahalıdır
      Özellikle doğru yuvarlanmış sonucu da önemsiyorsanız gereken donanım arama tabloları epey büyür
    • Logaritma alarak çarpmayı toplamaya dönüştürme yöntemi, onlarca yıldır kullanılan GF(2^x) yaklaşımıyla aynı değil mi?
      Aklıma gelen tek sınır alanın boyutu
    • Bir ölçüde ilgili olarak sayı kuramsal dönüşüm var
      https://ieeexplore.ieee.org/abstract/document/1451721

  • Bunun gerçekten çalışmasına şaşırdım
    Genelde çarpma mı toplama mı kullanılacağını algılamanın maliyeti, doğrudan çarpma yapmaktan daha yavaştır. Özellikle çok büyük miktarda işi paralel yürütürken bu daha da böyledir

    • OpenBLAS ve cuBLAS ile karşılaştırıldığında nasıl olur merak ediyorum

  • 1968’de icat edilen bir prosedürün şimdiye kadar bu amaçla kullanılmamış olması ilginç

    • GF(2^x)’in de geçen yüzyılın ortalarına kadar nerede kullanılacağını kimse bilmiyordu
      Ha, şimdi düşününce bilgisayar bilimi de geçen yüzyılın ortalarına kadar neredeyse yoktu zaten

  • Matris çarpımındaki alt-kübik zaman algoritmalarının arkasındaki matematik teorisiyle ilgileniyorsanız buradan başlayabilirsiniz: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
    Her gerçek j > 0 için, herhangi iki n x n matrisin O(n^(2+j)) adımda çarpılabileceği bir n’nin var olduğu varsayılıyor
    Şu anda 2+j = w = 2.3728596, yani j > 0.3728596 için kanıtlanmış durumda

    • Bu ifadenin doğru olduğundan emin değilim
      “Her j için bir n vardır” diye başlayınca sonraki cümlede n ve j sabit olur. O zaman sadece sabit boyutlu matrislerin sabit zamanda çarpılabileceğini söylemiş olursunuz. Teknik olarak doğru, ama sanırım daha güçlü bir iddia kastediliyordu
    • Zaman geçtikçe ilerleme daha da zorlaşıyor gibi görünüyor
      Belki de j=1/e’de tabana vurur. Buna varsayım bile demezdim; sadece mevcut değerin yakınlarında duran kullanışlı bir sabit. Matematik bize böyle bir oyun oynarsa epey komik olurdu
    • Bunun keyfi j > 0 için geçerli olacağını öngörmek oldukça cesurca
      Neden böyle düşünüldüğüne dair sezgiyi paylaşabilir misiniz?

  • Bu README, iyileştirmenin ne olduğunu ve çarpma sayısını nasıl yarıya indirdiğini gerçekten kötü açıklıyor.
    Big O çalışma süresi ne oluyor? Bilinen en iyi sınırı değiştiriyor mu?
    Görseller de dağınık ve bu yaklaşımın neden hızlı ya da iyi olduğunu neredeyse hiç açıklamıyor. Bu yüzden PDF’ye tıklamak bile içimden gelmiyor.
    Projenin güvenilirliğini artırmak istiyorlarsa, gerçekte ne olduğunu dürüst ve net biçimde açıklayıp insanları abartılı reklamla çekmeye çalışıyormuş gibi duran görseller yerine açık açıklamalar ve diyagramlar sunmaları iyi olur. Bunun devasa bir atılım mı yoksa önemsiz bir şey mi olduğunu ayırt etmek zor. Ne yazık ki yapay zeka furyasından yararlanmaya yönelik bilinçli bir tercih gibi de hissettiriyor. İnanmayı daha çok tercih edeceğim alternatif ise yazarın sadece düzeltme yapması ve bağlamı daha iyi vermesi gerektiği yönünde.

    • “Big O çalışma süresi ne?” sorusuna gelince, iddia çarpma sayısını yarıya indirmek olduğu için Big O’yu etkilemez.
      Makaledeki (https://arxiv.org/abs/2311.12224) çarpma sayısını yarıya indiren matematiği anlamak zor değil. Geleneksel matris çarpımı olan Denklem 2 ile Denklem 3–6’yı okumak yeterli.
      Reklamı yapıldığı gibi çarpma sayısını yarıya indirmenin karşılığında çok sayıda toplama/çıkarma eklediği açık görünüyor. Sonrasında algoritmayı daha iyi vektörleştiriyorlar; bu tür işlerde genelde olduğu gibi hızla karmaşıklaşıyor.
      Ana endişe sayısal kararlılık.
    • README pek açıklayıcı değil, ama makalenin kendi giriş bölümü oldukça erişilebilir.
      Çığır açıcı olup olmadığına gelince, alan kısıtı olan sabit noktalı hızlandırıcılara doğrudan uygulanabilecek temiz bir sabit katsayı iyileştirmesi olarak görüyorum. Her şeyi bir gecede değiştirmez, ama hiçbir şey değil de değil. Güzel bir çalışma.
    • Elitist görünmek istemem ama bu yorumun ne demek istediğini hiç anlamıyorum.
      “Çarpma sayısını yarıya indirmek”in Big O’yu değiştirmeyeceğini bilmeyecek kadar Big O gösterimini anlamıyorsanız, bunu neden sorduğunuzu anlamıyorum.