Majid Al-RaimiEIE: the first accelerator for sparse, compressed networksEIE: أول مسرّع للشبكات المتناثرة والمضغوطة

COE 592Lecture 4.2المحاضرة 4.2Part 07الجزء 07

EIE: the first accelerator for sparse, compressed networksEIE: أول مسرّع للشبكات المتناثرة والمضغوطة

Why sparsity needs hardware support, Han's co-design paradigm, and how EIE exploits weight sparsity, activation sparsity and weight sharing by splitting a sparse matrix-vector product across processing elements.لماذا يحتاج التناثر إلى دعم من العتاد، ونموذج التصميم المشترك (co-design) لـHan، وكيف يستغل EIE تناثر الأوزان وتناثر التنشيطات ومشاركة الأوزان بتقسيم ضرب مصفوفة متناثرة في متجه على عناصر المعالجة (PE).

Conceptsالمفاهيم
3
Slidesالشرائح
53-60
Readingمدة القراءة
18 min18 دقيقة
Understoodما فهمته
0/3 conceptsمفاهيم

Why this part mattersلماذا يهمّ هذا الجزء

Parts 02 to 06 chose pruning ratios and recovered accuracy. They never asked the uncomfortable question: after you remove 90 percent of the weights, is the network actually faster? On a GPU the honest answer is often no, and sometimes it is slower. This part explains why, and shows what hardware must do for pruning to become speed and energy.

The vehicle is EIE, the Efficient Inference Engine from Han et al. at ISCA 2016, the first accelerator built to run directly on a pruned, quantized model. You will learn its three sources of savings with the exact numbers on the slide, why one of them is dynamic and the other two static, and how a sparse matrix-vector product is split across processing elements so that zero weights are never stored and zero activations are never multiplied. This is the bridge to the M:N tensor cores and point-cloud engines later in the lecture, to the exam question "explain EIE's three savings and its PE dataflow", and to any research project that deploys a pruned model on an embedded accelerator.

اختارت الأجزاء من 02 إلى 06 نسب الـ pruning واستعادت الدقة. لكنها لم تطرح السؤال المحرج: بعد أن تحذف 90 percent من الأوزان، هل تصبح الشبكة أسرع فعلًا؟ على الـ GPU الجواب الصادق غالبًا لا، وأحيانًا تصبح أبطأ. يشرح هذا الجزء السبب، ويبيّن ما الذي يجب أن يفعله العتاد حتى يتحول الـ pruning إلى سرعة وتوفير في الطاقة.

الأداة هنا هي EIE، أي Efficient Inference Engine من Han وزملائه في ISCA 2016، وهو أول مسرّع (accelerator) بُني ليعمل مباشرة على نموذج مُقلَّم ومُكمَّم (pruned, quantized). ستتعلم مصادر توفيره الثلاثة بالأرقام الدقيقة الموجودة على الشريحة، ولماذا أحدها ديناميكي (dynamic) والآخران ثابتان (static)، وكيف يُقسَّم ضرب مصفوفة متناثرة في متجه (sparse matrix-vector product) على وحدات المعالجة (processing elements) بحيث لا تُخزَّن الأوزان الصفرية أبدًا ولا تُضرب التفعيلات الصفرية أبدًا. هذا هو الجسر إلى M:N tensor cores ومحركات السحب النقطية (point-cloud engines) لاحقًا في المحاضرة، وإلى سؤال الامتحان "explain EIE's three savings and its PE dataflow" (اشرح مصادر التوفير الثلاثة في EIE وتدفق البيانات بين وحدات المعالجة)، وإلى أي مشروع بحثي ينشر نموذجًا مُقلَّمًا على مسرّع مدمج (embedded accelerator).

By the end you canفي نهاية هذا الجزء ستستطيع

  1. Explain, with the EIE paper's Table IV numbers, why fine-grained sparsity gives little or even negative speedup on CPUs and GPUs.اشرح، بأرقام Table IV من ورقة EIE، لماذا يعطي التناثر الدقيق (fine-grained sparsity) تسريعًا ضئيلًا أو حتى سالبًا على الـ CPU والـ GPU.
  2. Name the three systems on slide 54 and the kind of sparsity each one exploits.سمِّ الأنظمة الثلاثة على الشريحة 54 ونوع التناثر الذي يستغله كل منها.
  3. State EIE's three sources of savings with their sparsity or bit width and their computation and memory factors, and explain the 5x versus 10x gap.اذكر مصادر التوفير الثلاثة في EIE مع نسبة التناثر أو عرض البتات (bit width) لكل منها ومعاملَي التوفير في الحساب والذاكرة، واشرح الفرق بين 5x و10x.
  4. Distinguish static from dynamic sparsity and say why ReLU makes activation sparsity dynamic.ميّز بين التناثر الثابت (static) والتناثر الديناميكي (dynamic)، وبيّن لماذا يجعل ReLU تناثر التفعيلات ديناميكيًا.
  5. Draw the 8 x 4 example: assign rows to PEs round-robin, broadcast the nonzero activations, and count the multiplications that actually happen.ارسم مثال 8 x 4: وزّع الصفوف على وحدات المعالجة (PEs) بالتناوب (round-robin)، وابثّ التفعيلات غير الصفرية، وعُدّ عمليات الضرب التي تحدث فعلًا.

Sparsity on paper versus sparsity in silicon: why Han built an engineالتناثر على الورق مقابل التناثر في العتاد: لماذا بنى Han محركًا خاصًا

Take AlexNet's FC6 layer, a 9216 x 4096 matrix that Han's Pruning left 91 percent zeros. Feed it one input vector. The EIE paper timed exactly this layer on a desktop CPU and a Titan X GPU, once with the dense matrix and once with the sparse one stored in a compressed format and run through the vendor's sparse kernels (MKL and cuSPARSE). The results are the whole motivation for this part.

خذ طبقة FC6 في AlexNet، وهي مصفوفة 9216 x 4096 جعل الـ pruning الذي طبّقه Han نسبة 91 percent منها أصفارًا. مرّر إليها متجه إدخال واحدًا. قاست ورقة EIE زمن هذه الطبقة بالذات على CPU مكتبي وعلى Titan X GPU، مرة بالمصفوفة الكثيفة (dense) ومرة بالمصفوفة المتناثرة مخزّنة بصيغة مضغوطة ومنفّذة عبر نوى التناثر التي توفرها الشركات المصنّعة (MKL وcuSPARSE). هذه النتائج هي الدافع الكامل لهذا الجزء.

PlatformالمنصةBatchحجم الدفعة (Batch)Dense matrixالمصفوفة الكثيفةSparse matrixالمصفوفة المتناثرةSparse versus denseالمتناثرة مقارنة بالكثيفة
Core i7-5930k CPUCore i7-5930k CPU117516.2 μs7516.2 μs3066.5 μs3066.5 μs2.5x fasterأسرع بـ 2.5x
GeForce Titan X GPUGeForce Titan X GPU11541.5 μs541.5 μs134.8 μs134.8 μs4.0x fasterأسرع بـ 4.0x
GeForce Titan X GPUGeForce Titan X GPU646419.8 μs19.8 μs94.6 μs94.6 μs4.8x slowerأبطأ بـ 4.8x
EIE, 64 PEsEIE، 64 PEs11runs only the sparse formيشغّل الصيغة المتناثرة فقط30.3 μs30.3 μs248x vs dense CPU248x مقارنة بالـ CPU الكثيف
AlexNet FC6, one layer, wall-clock time from EIE Table IV (Han et al., 2016)طبقة FC6 في AlexNet، طبقة واحدة، الزمن الفعلي من Table IV في ورقة EIE (Han et al., 2016)

Removing 91 percent of the multiplications bought only 2.5x on the CPU and 4x on the GPU, not the 11x the arithmetic promises. Worse, once the GPU batches 64 inputs so that the dense kernel can use its full width, the sparse kernel falls 4.8x behind. The paper's summary is blunt: "the irregular pattern caused by compression hinders the effective acceleration on CPUs and GPUs". A general-purpose core cannot skip a zero for free. It has to read an index, compute an address, gather a scattered activation and suffer the cache miss, and that bookkeeping costs more than the multiply it avoided. Custom accelerators before EIE did no better: sparse matrix-vector (SpMV) engines from scientific computing handle the static zeros in the weights but not the run-time zeros in the activations, and DNN accelerators of the day "must expand the network to dense form" before they can run it.

حذف 91 percent من عمليات الضرب لم يكسب سوى 2.5x على الـ CPU و4x على الـ GPU، لا الـ 11x التي يعد بها الحساب. والأسوأ أنه حين يجمع الـ GPU دفعة من 64 inputs حتى تستغل النواة الكثيفة كامل عرضها، تتأخر النواة المتناثرة بمقدار 4.8x. خلاصة الورقة صريحة: "the irregular pattern caused by compression hinders the effective acceleration on CPUs and GPUs"، أي أن النمط غير المنتظم الناتج عن الضغط يعيق التسريع الفعلي على الـ CPUs والـ GPUs. النواة عامة الغرض (general-purpose core) لا تستطيع تخطي الصفر مجانًا. عليها أن تقرأ فهرسًا، وتحسب عنوانًا، وتجمع (gather) تفعيلًا مبعثرًا، وتتحمل إخفاق الذاكرة المخبئية (cache miss)، وكلفة هذه المحاسبة أكبر من كلفة عملية الضرب التي تجنبتها. ولم تكن المسرّعات المخصصة قبل EIE أفضل حالًا: محركات ضرب المصفوفة المتناثرة في متجه (SpMV) القادمة من الحوسبة العلمية تتعامل مع الأصفار الثابتة في الأوزان لكنها لا تتعامل مع الأصفار التي تظهر وقت التشغيل في التفعيلات، ومسرّعات الشبكات العصبية (DNN accelerators) في ذلك الوقت "must expand the network to dense form"، أي يجب أن تعيد توسيع الشبكة إلى الصيغة الكثيفة قبل أن تشغّلها.

Why memory is the real enemyلماذا الذاكرة هي العدو الحقيقي

Operation (45 nm)العملية (45 nm)EnergyالطاقةRelative to SRAM readنسبةً إلى قراءة SRAM
32-bit SRAM readقراءة SRAM بعرض 32-bit5 pJ5 pJ1x1x
32-bit DRAM readقراءة DRAM بعرض 32-bit640 pJ640 pJ128x128x
32-bit float multiplyضرب أعداد عائمة (float) بعرض 32-bit3.7 pJ3.7 pJabout 0.7xنحو 0.7x
Energy per operation in the 45 nm process the paper uses for its estimates (EIE Table I)الطاقة لكل عملية في تقنية 45 nm التي تستخدمها الورقة لتقديراتها (Table I في EIE)

The table is the second half of the argument, the one that decides whether a model can run on a phone at all: the 128x gap between an on-chip and an off-chip read dwarfs the multiply itself. A network with one billion connections evaluated at 20 Hz spends 20 x 10^9 x 640 pJ = 12.8 W on DRAM traffic alone, far past any mobile power budget. The lesson that Deep Compression drew from this is that the goal is not fewer FLOPs but a model small enough to live entirely in SRAM: AlexNet shrinks from 240 MB to 6.9 MB and VGG-16 from 552 MB to 11.3 MB, both with no loss of accuracy. Once the whole model fits on chip, every weight read is the cheap kind.

الجدول هو النصف الثاني من الحجة، وهو الذي يقرر هل يمكن تشغيل النموذج على هاتف أصلًا: الفجوة البالغة 128x بين القراءة من داخل الشريحة (on-chip) والقراءة من خارجها (off-chip) تتضاءل أمامها كلفة الضرب نفسه. شبكة فيها مليار وصلة تُقيَّم بتردد 20 Hz تستهلك 20 x 10^9 x 640 pJ = 12.8 W على حركة DRAM وحدها، وهذا أبعد بكثير من أي ميزانية طاقة لجهاز محمول. الدرس الذي استخلصه Deep Compression من هذا هو أن الهدف ليس تقليل عدد الـ FLOPs بل الوصول إلى نموذج صغير بما يكفي ليعيش بالكامل في الـ SRAM: ينكمش AlexNet من 240 MB إلى 6.9 MB، وVGG-16 من 552 MB إلى 11.3 MB، وكلاهما دون أي خسارة في الدقة. وما إن يتسع النموذج كله داخل الشريحة حتى تصبح كل قراءة للأوزان من النوع الرخيص.

This is the point at which the five questions of the outline slide (what pruning is and how to formulate it, which granularity, which criterion, what ratio per layer, and how to fine-tune) hand over to a sixth that the outline never lists: on what hardware. All five are now answered, in lecture 04-1 and in parts 02 to 06 here, and the constraint ||W_P||_0 <= N has produced a model with few nonzeros. The rest of the lecture is about turning that small N into small time and small energy.

عند هذه النقطة تسلّم الأسئلة الخمسة في شريحة المخطط (ما هو الـ pruning وكيف نصوغه، وأي granularity، وأي معيار (criterion)، وأي نسبة لكل طبقة، وكيف نجري الـ fine-tuning) الراية إلى سؤال سادس لا يذكره المخطط أبدًا: على أي عتاد؟ الأسئلة الخمسة أُجيب عنها كلها الآن، في المحاضرة 04-1 وفي الأجزاء من 02 إلى 06 هنا، والقيد ||W_P||_0 <= N أنتج نموذجًا فيه عدد قليل من القيم غير الصفرية. بقية المحاضرة تدور حول تحويل هذا الـ N الصغير إلى زمن قصير وطاقة قليلة.

Han's paradigm: co-design the compression and the engineنموذج Han: تصميم الضغط والمحرك معًا (co-design)

Slide 56 draws the conventional flow as training on a server, then a big network shipped to a phone for slow, power-hungry inference. The proposed flow inserts a model compression stage between them and replaces the phone's generic processor with accelerated inference. The labels under each stage are five papers by the same group, and reading them as a set is the fastest way to see that compression and the engine were designed together. Neither is useful alone: a compressed model on a GPU gives the Table IV numbers above, and an engine for sparse models with nothing sparse to run is idle silicon. Together they deliver what the slide calls fast and power efficient: EIE with 64 PEs at 800 MHz draws about 600 mW and beats both baselines on the same nine FC and LSTM benchmarks by the margins below.

ترسم الشريحة 56 المسار التقليدي هكذا: تدريب على خادم، ثم شبكة كبيرة تُشحن إلى الهاتف لاستدلال (inference) بطيء ومستهلك للطاقة. أما المسار المقترح فيُدخل مرحلة ضغط النموذج (model compression) بينهما، ويستبدل المعالج العام في الهاتف باستدلال مُسرَّع (accelerated inference). العناوين تحت كل مرحلة هي خمس أوراق من المجموعة البحثية نفسها، وقراءتها كمجموعة واحدة هي أسرع طريقة لترى أن الضغط والمحرك صُمّما معًا. لا فائدة لأيّ منهما وحده: النموذج المضغوط على GPU يعطي أرقام Table IV أعلاه، والمحرك المخصص للنماذج المتناثرة دون شيء متناثر يشغّله ليس إلا سيليكونًا عاطلًا. معًا يحققان ما تسميه الشريحة سريعًا وموفرًا للطاقة (fast and power efficient): يستهلك EIE بـ 64 PEs عند 800 MHz نحو 600 mW، ويتفوق على كلا خطّي الأساس (baselines) في معايير الاختبار التسعة نفسها لطبقات FC وLSTM بالفوارق المبيّنة أدناه.

EIE versusEIE مقارنة بـSpeedupالتسريعEnergy efficiencyكفاءة الطاقة
Core i7-5930k CPUCore i7-5930k CPU189x189x24,000x24,000x
Titan X GPUTitan X GPU13x13x3,400x3,400x
EIE against the two baselines on the nine FC and LSTM benchmarks (Han et al., 2016)EIE مقارنة بخطّي الأساس على معايير الاختبار التسعة لطبقات FC و LSTM (Han et al., 2016)
The conventional lane ships the full network to a generic processor. The proposed lane clamps it down through pruning, quantization and Huffman coding, then hands the small model to an engine built for it.المسار التقليدي يشحن الشبكة كاملة إلى معالج عام. أما المسار المقترح فيضغطها عبر الـ pruning والـ quantization وترميز Huffman، ثم يسلّم النموذج الصغير إلى محرك مبني خصيصًا له.

The five paper labels on slide 56عناوين الأوراق الخمس على الشريحة 56

ICLR 2017, under TrainingICLR 2017، تحت Training
DSD: dense-sparse-dense training, a regularizer that prunes and regrows during training to reach a better dense modelDSD: تدريب dense-sparse-dense، وهو أسلوب تنظيم (regularizer) يقلّم الأوزان ثم يعيد إنباتها أثناء التدريب للوصول إلى نموذج كثيف أفضل
NeurIPS 2015, under Model CompressionNeurIPS 2015، تحت Model Compression
Learning both Weights and Connections: train, prune, retrain, giving 9x fewer AlexNet and 13x fewer VGG-16 parameters without accuracy lossLearning both Weights and Connections: درّب، ثم قلّم، ثم أعد التدريب، فتقل معاملات AlexNet بـ 9x ومعاملات VGG-16 بـ 13x دون خسارة في الدقة
ICLR 2016 best paper, under Model Compressionأفضل ورقة في ICLR 2016، تحت Model Compression
Deep Compression: pruning, trained quantization with a k-means codebook, then Huffman coding; AlexNet 240 MB to 6.9 MB (35x), VGG-16 552 MB to 11.3 MB (49x)Deep Compression: الـ pruning، ثم quantization مُدرَّب بقاموس k-means، ثم ترميز Huffman؛ AlexNet من 240 MB إلى 6.9 MB (35x)، وVGG-16 من 552 MB إلى 11.3 MB (49x)
ISCA 2016, under Accelerated InferenceISCA 2016، تحت Accelerated Inference
EIE: the ASIC that runs directly on the pruned, codebook-quantized weightsEIE: الـ ASIC الذي يعمل مباشرة على الأوزان المُقلَّمة والمُكمَّمة بالقاموس (codebook-quantized)
FPGA 2017 best paper, under Accelerated Inferenceأفضل ورقة في FPGA 2017، تحت Accelerated Inference
ESE: the same idea for sparse LSTMs on a Xilinx XCKU060 FPGA, 20x compression and 282 GOPS with load-balance-aware pruningESE: الفكرة نفسها لشبكات LSTM المتناثرة على Xilinx XCKU060 FPGA، بضغط 20x و282 GOPS مع pruning يراعي توازن الحمل (load-balance-aware pruning)

Three systems, three kinds of sparsityثلاثة أنظمة وثلاثة أنواع من التناثر

Slide 54 lists the hardware this section covers, and each entry targets a different sparsity. EIE exploits Weight sparsity and Activation sparsity at the same time, which is what made it the first of its kind. The NVIDIA sparse tensor core accepts only structured M:N sparsity, trading flexibility for a dense-friendly pattern. TorchSparse and PointAcc exploit activation sparsity of a very different origin: point clouds are mostly empty space, so the zeros are in the input, not in the weights.

تعرض الشريحة 54 العتاد الذي يغطيه هذا القسم، وكل عنصر فيها يستهدف نوعًا مختلفًا من التناثر. يستغل EIE الـ weight sparsity (تناثر الأوزان) والـ activation sparsity (تناثر التفعيلات) في الوقت نفسه، وهذا ما جعله الأول من نوعه. أما الـ tensor core المتناثر من NVIDIA فلا يقبل إلا الـ M:N sparsity المنتظم (structured)، مقايضًا المرونة بنمط يلائم العتاد الكثيف. ويستغل TorchSparse وPointAcc تناثر تفعيلات ذا أصل مختلف تمامًا: السحب النقطية (point clouds) في معظمها فضاء فارغ، لذلك تكون الأصفار في المُدخل لا في الأوزان.

Roadmap for the rest of the lecture, from slide 54خريطة بقية المحاضرة، من الشريحة 54

EIE (Han et al., ISCA 2016)
Weight sparsity plus activation sparsity in fully connected layers, on a custom ASIC. This part and parts 08 and 09.تناثر الأوزان مع تناثر التفعيلات في الطبقات المتصلة بالكامل (fully connected)، على ASIC مخصص. هذا الجزء والجزءان 08 و09.
NVIDIA Tensor Core (Ampere)
M:N weight sparsity, specifically 2:4: two of every four consecutive weights must be zero, and the hardware skips the matching activations. Part 10.تناثر أوزان من نوع M:N، وتحديدًا 2:4: يجب أن يكون وزنان من كل أربعة أوزان متتالية صفرًا، ويتخطى العتاد التفعيلات المقابلة لهما. الجزء 10.
TorchSparse and PointAccTorchSparse و PointAcc
Activation sparsity of point clouds, where most voxels are empty, handled by sparse convolution on GPUs and on a custom accelerator. Parts 11 to 13.تناثر التفعيلات في السحب النقطية (point clouds)، حيث معظم الـ voxels فارغة، ويُعالَج بالـ sparse convolution على الـ GPUs وعلى مسرّع مخصص. الأجزاء من 11 إلى 13.

Recall

Why does a 91 percent sparse FC6 layer run only 2.5x faster on a CPU, and slower than dense on a GPU at batch 64?لماذا تعمل طبقة FC6 المتناثرة بنسبة 91 percent أسرع بـ 2.5x فقط على الـ CPU، وأبطأ من النسخة الكثيفة على الـ GPU عند batch 64؟

The zeros are removed from the arithmetic but the surviving weights are scattered irregularly. A CPU or GPU must read indices, gather activations and take cache misses for each one, which costs more than the multiplies it skips. At batch 64 the dense kernel fills the GPU's wide units while the sparse kernel cannot, so it is 4.8x slower.
الأصفار تُزال من الحساب لكن الأوزان الباقية تبقى مبعثرة بشكل غير منتظم. على الـ CPU أو الـ GPU أن يقرأ الفهارس ويجمع التفعيلات ويتحمل إخفاقات الذاكرة المخبئية (cache misses) لكل واحد منها، وهذا يكلّف أكثر من عمليات الضرب التي يتخطاها. وعند batch 64 تملأ النواة الكثيفة الوحدات العريضة في الـ GPU بينما لا تستطيع النواة المتناثرة ذلك، فتصبح أبطأ بـ 4.8x.

Recall

Name the three systems on slide 54 and the sparsity each exploits.سمِّ الأنظمة الثلاثة على الشريحة 54 ونوع التناثر الذي يستغله كل منها.

EIE: weight sparsity plus activation sparsity in fully connected layers. NVIDIA Tensor Core: M:N (2:4) structured weight sparsity. TorchSparse and PointAcc: activation sparsity of point clouds through sparse convolution.
EIE: تناثر الأوزان مع تناثر التفعيلات في الطبقات المتصلة بالكامل (fully connected). NVIDIA Tensor Core: تناثر أوزان منتظم (structured) من نوع M:N (2:4). TorchSparse وPointAcc: تناثر تفعيلات السحب النقطية (point clouds) عبر الـ sparse convolution.

Three sources of savings: sparse weights, sparse activations, shared weightsثلاثة مصادر للتوفير: أوزان متناثرة، وتفعيلات متناثرة، وأوزان مشتركة

Look at one fully connected layer of AlexNet, FC7, a 4096 x 4096 matrix of 16.8 M weights that occupies 64 MB in 32-bit floating point. A dense engine stores all 16.8 M values and performs 16.8 M multiply-accumulate operations (MACs) for every input. After Deep Compression, the EIE paper reports that only 9% of the weights survive, about 35% of the input activations are nonzero, and 3% of the original FLOPs remain. EIE reaches that 3 percent by combining three savings that the slide states in round numbers.

انظر إلى طبقة واحدة متصلة بالكامل (fully connected) في AlexNet، هي FC7، مصفوفة 4096 x 4096 فيها 16.8 M وزن تشغل 64 MB بصيغة الفاصلة العائمة 32-bit. المحرك الكثيف يخزّن كل القيم الـ 16.8 M وينفّذ 16.8 M عملية ضرب وتجميع (multiply-accumulate، أي MACs) لكل مُدخل. بعد Deep Compression تذكر ورقة EIE أن 9% فقط من الأوزان تبقى، وأن نحو 35% من تفعيلات الإدخال غير صفرية، وأن 3% فقط من الـ FLOPs الأصلية تبقى. يصل EIE إلى هذه الـ 3 percent بالجمع بين ثلاثة مصادر للتوفير تذكرها الشريحة بأرقام مقرّبة.

Each full bar is the dense cost. On hover the sparse-weight bar shrinks to a tenth, the sparse-activation bar to a third and the weight-sharing bar to an eighth, with the rule of thumb behind each.كل شريط كامل يمثل الكلفة الكثيفة. عند تمرير المؤشر ينكمش شريط الأوزان المتناثرة إلى العُشر، وشريط التفعيلات المتناثرة إلى الثلث، وشريط مشاركة الأوزان إلى الثُّمن، مع القاعدة التقريبية التي وراء كل منها.
SourceالمصدرSparsity or bitsالتناثر أو عدد البتاتComputation savingالتوفير في الحسابMemory savingالتوفير في الذاكرةRule of thumbالقاعدة التقريبية
Sparse weightالأوزان المتناثرة90% static sparsityتناثر ثابت بنسبة 90%10x less computationحساب أقل بـ 10x5x less memory footprintذاكرة أقل بـ 5x0 x A = 00 x A = 0
Sparse activationالتفعيلات المتناثرة70% dynamic sparsityتناثر ديناميكي بنسبة 70%3x less computationحساب أقل بـ 3xnone claimed on the slideلا تذكر الشريحة أي توفيرW x 0 = 0W x 0 = 0
Weight sharingمشاركة الأوزان4-bit weightsأوزان 4-bitnone claimed on the slideلا تذكر الشريحة أي توفير8x less memory footprintذاكرة أقل بـ 8x2.09, 1.92 => 22.09, 1.92 => 2
The three savings as stated on slide 57مصادر التوفير الثلاثة كما تذكرها الشريحة 57

The first column is Weight sparsity. Pruning zeroed about 90 percent of the matrix, so a product 0 x A is known to be zero without looking at A. An engine that never stores those weights skips their multiplications for free, hence 10x less computation. The second column is Activation sparsity. About 70 percent of the input vector is zero because it came out of a ReLU, so W x 0 is also known without looking at W. Skipping those columns removes another factor of roughly 1 / 0.3 = 3.3, which the slide rounds to 3x, and the paper measures that skipping them saves about 65 percent of the computation cycles. The third column is Weight sharing: the surviving weights are not stored as32-bit floats but as 4-bit indices into a per-layer codebook of 2^4 = 16 shared values, which is where the crossed-out 2.09, 1.92 => 2 comes from. Both weights snap to the same centroid and are stored as the same index, and 32 / 4 is the 8x memory saving.

العمود الأول هو الـ weight sparsity (تناثر الأوزان). جعل الـ pruning نحو 90 percent من المصفوفة أصفارًا، لذا فحاصل الضرب 0 x A معروف أنه صفر دون النظر إلى A. والمحرك الذي لا يخزّن تلك الأوزان أبدًا يتخطى عمليات ضربها مجانًا، ومن هنا جاء الحساب الأقل بـ 10x. العمود الثاني هو الـ activation sparsity (تناثر التفعيلات). نحو 70 percent من متجه الإدخال أصفار لأنه خرج من ReLU، لذا فـ W x 0 معروف أيضًا دون النظر إلى W. تخطي تلك الأعمدة يزيل معاملًا آخر قدره تقريبًا 1 / 0.3 = 3.3، تقرّبه الشريحة إلى 3x، وتقيس الورقة أن تخطيها يوفّر نحو 65 percent من دورات الحساب. العمود الثالث هو الـ weight sharing (مشاركة الأوزان): الأوزان الباقية لا تُخزَّن كأعداد عائمة 32-bit بل كفهارس 4-bit تشير إلى قاموس (codebook) خاص بكل طبقة يضم 2^4 = 16 قيمة مشتركة، ومن هنا جاءت العبارة المشطوبة 2.09, 1.92 => 2. كلا الوزنين ينجذبان إلى المركز (centroid) نفسه ويُخزَّنان بالفهرس نفسه، و32 / 4 هو توفير الذاكرة البالغ 8x.

bi=ReLU(∑j∈Xi∩YS[Iij] aj)b_i = \mathrm{ReLU}\Big(\sum_{j \in X_i \cap Y} S[I_{ij}]\, a_j\Big)
EIE's compressed layer (paper eq. 3): X_i is the static set of nonzero columns in row i, Y the dynamic set of nonzero activations, S the 16-entry codebook, I_ij the 4-bit indexالطبقة المضغوطة في EIE (المعادلة 3 في الورقة): X_i هي المجموعة الثابتة للأعمدة غير الصفرية في الصف i، وY المجموعة الديناميكية للتنشيطات غير الصفرية، وS دفتر الرموز ذو 16 مدخلًا، وI_ij الفهرس ذو 4 بتات

The formula packs all three savings into one line. The sum runs only over X_i ∩ Y, the columns that are nonzero in both the weight row and the activation vector, which is the 10x and the 3x. Each weight appears as S[I_ij], a codebook lookup, which is the 8x. The two computation factors multiply to 10 x 3 = 30x, which is why the paper can describe 102 GOPS (giga operations per second) of work on the compressed network as about 3 TOPS (tera operations per second) on the uncompressed one. The 8x from the codebook is a memory factor and does not reduce the operation count.

تجمع المعادلة مصادر التوفير الثلاثة في سطر واحد. المجموع يمر فقط على X_i ∩ Y، أي الأعمدة غير الصفرية في صف الأوزان وفي متجه التفعيلات معًا، وهذا هو الـ 10x والـ 3x. ويظهر كل وزن على شكل S[I_ij]، أي بحث في القاموس، وهذا هو الـ 8x. معاملا الحساب يتضاعفان إلى 10 x 3 = 30x، ولهذا تستطيع الورقة أن تصف 102 GOPS (مليار عملية في الثانية) من العمل على الشبكة المضغوطة بأنها تعادل نحو 3 TOPS (تريليون عملية في الثانية) على الشبكة غير المضغوطة. أما الـ 8x القادمة من القاموس فهي معامل ذاكرة ولا تقلل عدد العمليات.

Why memory shrinks 5x and not 10xلماذا تنكمش الذاكرة 5x لا 10x

The one number that trips students is the 5x. Ten percent of the weights survive, so why not 10x less memory? Because a nonzero that is stored without its neighbors must carry its position. EIE stores each surviving weight together with a 4-bit relative index (the number of zeros since the previous nonzero in the column), a scheme explained fully in part 08 under Compressed sparse column (CSC). The retrospective on the paper states it directly: "the weight and index are both 4bit giving a 50% storage overhead". Half of every stored entry is bookkeeping, so the 10x from sparsity is halved to 5x. Computation keeps its full 10x, since the index is read but never multiplied.

الرقم الذي يُربك الطلاب هو الـ 5x. تبقى عشرة بالمئة من الأوزان، فلماذا لا تقل الذاكرة 10x؟ لأن القيمة غير الصفرية التي تُخزَّن دون جيرانها يجب أن تحمل موقعها معها. يخزّن EIE كل وزن باقٍ مع فهرس نسبي (relative index) بعرض 4-bit (عدد الأصفار منذ القيمة غير الصفرية السابقة في العمود)، وهي طريقة تُشرح بالكامل في الجزء 08 تحت compressed sparse column. والمراجعة اللاحقة للورقة (retrospective) تقولها مباشرة: "the weight and index are both 4bit giving a 50% storage overhead"، أي أن الوزن والفهرس كلاهما 4bit مما يعطي كلفة تخزين إضافية قدرها 50%. نصف كل مُدخل مخزَّن هو محاسبة، لذا فالـ 10x القادمة من التناثر تُنصَّف إلى 5x. أما الحساب فيحتفظ بالـ 10x كاملة، لأن الفهرس يُقرأ لكنه لا يُضرب أبدًا.

Worked exampleمثال محلول

From 3200 bits to 80 bitsمن 3200 بت إلى 80 بت

  1. Dense storageالتخزين الكثيف

    100 weights in 32-bit floating point occupy 100 x 32 = 3200 bits.
    100 وزن بصيغة الفاصلة العائمة 32-bit تشغل 100 x 32 = 3200 bits.

  2. Prune to 10 percent, keep full precisionقلّم إلى 10 percent مع الحفاظ على الدقة الكاملة

    10 survivors, each with a 32-bit value plus a 32-bit position: 10 x 64 = 640 bits. That is 3200 / 640 = 5x, which is the slide's sparsity row: the index costs as much as the value.
    10 أوزان باقية، لكل منها قيمة 32-bit وموقع 32-bit: 10 x 64 = 640 bits. وهذا يعني 3200 / 640 = 5x، وهو صف التناثر على الشريحة: الفهرس يكلّف بقدر ما تكلّف القيمة.

  3. Add weight sharingأضف مشاركة الأوزان

    Weight sharing drops the value to a 4-bit codebook index (32 / 4 = 8x). EIE also keeps the position the same width as the value, a 4-bit relative index, so the index overhead stays at 2x and the 5x from step 2 holds: 10 x (4 + 4) = 80 bits. Relative to the 640-bit step this is 8x, the slide's weight-sharing row.
    مشاركة الأوزان تُنزل القيمة إلى فهرس قاموس بعرض 4-bit (32 / 4 = 8x). ويُبقي EIE الموقع أيضًا بعرض القيمة نفسه، أي فهرسًا نسبيًا بعرض 4-bit، فتبقى كلفة الفهرس الإضافية 2x ويبقى الـ 5x من الخطوة 2 صحيحًا: 10 x (4 + 4) = 80 bits. ومقارنة بخطوة الـ 640-bit هذا يساوي 8x، وهو صف مشاركة الأوزان على الشريحة.

  4. 40x overall40x إجمالًا

    3200 / 80 = 40x, which is exactly 5 x 8. The decomposition assumes the index is as wide as the value, which is how EIE stores it: the slide assigns the index overhead to the sparsity factor and the bit-width gain to the sharing factor, and the two multiply.
    3200 / 80 = 40x، وهو بالضبط 5 x 8. هذا التفكيك يفترض أن الفهرس بعرض القيمة نفسه، وهذه هي طريقة تخزين EIE له: تنسب الشريحة كلفة الفهرس الإضافية إلى معامل التناثر، والمكسب من عرض البتات إلى معامل المشاركة، والمعاملان يتضاعفان.

Static versus dynamicالثابت (static) مقابل الديناميكي (dynamic)

The italic words on the slide, static and dynamic, are the conceptual core of this part and the key to Static versus dynamic sparsity. The paper defines X_i as the set of columns where row i of W is nonzero and Y as the set of indices where a is nonzero, then says: "The set X_i is fixed for a given model. The set Y varies from input to input." Weight zeros are decided once, when pruning and Fine-tuning finish, so the storage format can be laid out offline with every zero already gone. Activation zeros are made fresh by ReLU for every input, since a different image produces a different set of negative pre-activations. No format can remove them in advance; the engine must find them at run time, which is the job of the Leading non-zero detection unit in part 08.

الكلمتان المائلتان على الشريحة، static وdynamic، هما اللب المفاهيمي لهذا الجزء ومفتاح فهم static versus dynamic sparsity. تعرّف الورقة X_i بأنها مجموعة الأعمدة التي يكون فيها الصف i من W غير صفري، وY بأنها مجموعة الفهارس التي يكون فيها a غير صفري، ثم تقول: "The set X_i is fixed for a given model. The set Y varies from input to input."، أي أن المجموعة X_i ثابتة لنموذج معيّن بينما تتغير Y من مُدخل لآخر. أصفار الأوزان تتحدد مرة واحدة، عند انتهاء الـ pruning والـ fine-tuning، لذا يمكن ترتيب صيغة التخزين مسبقًا (offline) وقد أُزيل منها كل صفر. أما أصفار التفعيلات فيصنعها ReLU من جديد لكل مُدخل، لأن صورة مختلفة تنتج مجموعة مختلفة من القيم السالبة قبل التفعيل (pre-activations). لا توجد صيغة تستطيع إزالتها مسبقًا؛ على المحرك أن يجدها وقت التشغيل، وهذه مهمة وحدة الـ leading non-zero detection في الجزء 08.

What the two words on the slide meanمعنى الكلمتين على الشريحة

Static sparsity (weights)التناثر الثابت (الأوزان)
The set X_i of columns where row i has a nonzero is fixed once pruning and fine-tuning finish. It can be encoded offline into the storage format and never changes from input to input.المجموعة X_i من الأعمدة التي يحمل فيها الصف i قيمة غير صفرية تثبت بمجرد انتهاء الـ pruning والـ fine-tuning. يمكن ترميزها مسبقًا (offline) في صيغة التخزين، ولا تتغير أبدًا من مُدخل لآخر.
Dynamic sparsity (activations)التناثر الديناميكي (التفعيلات)
The set Y of indices where a_j is nonzero depends on this input: ReLU zeroed whatever came out negative. It must be detected at run time by scanning the vector.المجموعة Y من الفهارس التي يكون فيها a_j غير صفري تعتمد على هذا المُدخل بالذات: صفّر ReLU كل ما خرج سالبًا. يجب اكتشافها وقت التشغيل بمسح المتجه.

The four factors behind the paper's 28,800x energy figureالمعاملات الأربعة وراء رقم الطاقة 28,800x في الورقة

SRAM instead of DRAMSRAM بدلًا من DRAM
120x120x
Weight sparsityتناثر الأوزان
10x10x
Weight sharingمشاركة الأوزان
8x8x
Skipped activationsالتفعيلات المتخطّاة
3x3x
Productحاصل الضرب
120 x 10 x 8 x 3 = 28,800x120 x 10 x 8 x 3 = 28,800x

Quick checkاختبار سريع

Which of EIE's savings is dynamic, meaning it depends on the input at run time?أيّ مصادر التوفير في EIE ديناميكي، أي يعتمد على المُدخل وقت التشغيل؟

Quick checkاختبار سريع

Why does 90 percent weight sparsity cut EIE's memory only 5x while cutting computation 10x?لماذا يقلل تناثر الأوزان بنسبة 90 percent ذاكرة EIE بـ 5x فقط بينما يقلل الحساب بـ 10x؟

Recall

State EIE's three sources of savings with the numbers on slide 57.اذكر مصادر التوفير الثلاثة في EIE بالأرقام الموجودة على الشريحة 57.

Sparse weights, 90 percent static sparsity, 10x less computation and 5x less memory. Sparse activations, 70 percent dynamic sparsity, 3x less computation. Weight sharing with 4-bit weights, 8x less memory.
الأوزان المتناثرة: تناثر ثابت بنسبة 90 percent، وحساب أقل بـ 10x وذاكرة أقل بـ 5x. التفعيلات المتناثرة: تناثر ديناميكي بنسبة 70 percent، وحساب أقل بـ 3x. مشاركة الأوزان بأوزان 4-bit: ذاكرة أقل بـ 8x.

Recall

Why is activation sparsity called dynamic while weight sparsity is static?لماذا يُسمّى تناثر التفعيلات ديناميكيًا بينما تناثر الأوزان ثابت؟

Weight zeros are fixed once pruning and fine-tuning finish, so the set X_i is known before deployment. Activation zeros come from ReLU acting on this input, so the set Y changes from input to input and must be detected at run time.
أصفار الأوزان تثبت بمجرد انتهاء الـ pruning والـ fine-tuning، لذا تكون المجموعة X_i معروفة قبل النشر (deployment). أما أصفار التفعيلات فتأتي من ReLU وهو يعمل على هذا المُدخل بالذات، لذا تتغير المجموعة Y من مُدخل لآخر ويجب اكتشافها وقت التشغيل.

Interleaving rows across PEs and broadcasting only the nonzero activationsتوزيع الصفوف بالتناوب على وحدات المعالجة وبث التفعيلات غير الصفرية فقط

Slides 58 to 60 show the same small figure three times, and it is worth working it with real numbers before reading the rule. The input is a = (0, a1, 0, a3), the weight matrix is 8 x 4 with eleven nonzeros, and there are four processing elements. Give the symbols values: a = (0, 2, 0, 1), and in the matrix w00 = 1, w01 = 3, w03 = -2, w12 = 5, w21 = -1, w23 = 1, row 3 empty, w42 = 2, w43 = -3, w50 = 6, w63 = 2, w71 = -4. The colors on the slide say who owns what: row 0 is PE0, row 1 is PE1, row 2 is PE2, row 3 is PE3, and row 4 wraps around to PE0 again.

تعرض الشرائح من 58 إلى 60 الشكل الصغير نفسه ثلاث مرات، ويستحق أن تحلّه بأرقام حقيقية قبل قراءة القاعدة. المُدخل هو a = (0, a1, 0, a3)، ومصفوفة الأوزان بحجم 8 x 4 فيها إحدى عشرة قيمة غير صفرية، وهناك أربع processing elements (وحدات معالجة). أعطِ الرموز قيمًا: a = (0, 2, 0, 1)، وفي المصفوفة w00 = 1، w01 = 3، w03 = -2، w12 = 5، w21 = -1، w23 = 1، والصف 3 فارغ، w42 = 2، w43 = -3، w50 = 6، w63 = 2، w71 = -4. الألوان على الشريحة تبيّن من يملك ماذا: الصف 0 لـ PE0، والصف 1 لـ PE1، والصف 2 لـ PE2، والصف 3 لـ PE3، ثم يلتف الصف 4 عائدًا إلى PE0 من جديد.

Worked exampleمثال محلول

Two broadcasts, seven multiplicationsبثّان وسبع عمليات ضرب

  1. Scan a for its first nonzeroامسح a بحثًا عن أول قيمة غير صفرية

    a0 = 0, so column 0 is skipped for every PE at once. The first nonzero is a1 = 2, and the controller broadcasts the pair (2, j = 1) to all four PEs.
    a0 = 0، لذا يُتخطّى العمود 0 لكل الـ PEs دفعة واحدة. أول قيمة غير صفرية هي a1 = 2، فيبثّ المتحكم (controller) الزوج (2, j = 1) إلى الـ PEs الأربع.

  2. Each PE works column 1 of its own rowsكل PE يعالج العمود 1 من صفوفه

    PE0 holds w01 = 3: b0 += 3 x 2 = 6. PE2 holds w21 = -1: b2 += -2. PE3 holds w71 = -4: b7 += -8. PE1 has no nonzero in column 1 and does nothing.
    PE0 يحمل w01 = 3: b0 += 3 x 2 = 6. PE2 يحمل w21 = -1: b2 += -2. PE3 يحمل w71 = -4: b7 += -8. ليس لدى PE1 أي قيمة غير صفرية في العمود 1 فلا يفعل شيئًا.

  3. Scan on and broadcast a3تابع المسح وابثّ a3

    a2 = 0, so column 2 is skipped, and with it w12 and w42, which are never read. The next nonzero is a3 = 1, broadcast as (1, j = 3).
    a2 = 0، لذا يُتخطّى العمود 2، ومعه w12 وw42 اللذان لا يُقرآن أبدًا. القيمة غير الصفرية التالية هي a3 = 1، وتُبثّ على شكل (1, j = 3).

  4. Each PE works column 3كل PE يعالج العمود 3

    PE0: b0 += -2 x 1, giving 4; and b4 += -3 x 1 = -3. PE2: b2 += 1 x 1, giving -1; and b6 += 2 x 1 = 2. PE1 and PE3 have nothing in column 3.
    PE0: b0 += -2 x 1، فيصبح 4؛ وb4 += -3 x 1 = -3. PE2: b2 += 1 x 1، فيصبح -1؛ وb6 += 2 x 1 = 2. ليس لدى PE1 وPE3 شيء في العمود 3.

  5. ReLU inside each PEReLU داخل كل PE

    b = (4, 0, -1, 0, -3, 0, 2, -8) becomes (4, 0, 0, 0, 0, 0, 2, 0). The negative rows 2, 4 and 7 are the ones the slide draws as -b2, -b4, -b7 and zeroes after ReLU.
    b = (4, 0, -1, 0, -3, 0, 2, -8) يصبح (4, 0, 0, 0, 0, 0, 2, 0). الصفوف السالبة 2 و4 و7 هي التي ترسمها الشريحة على شكل -b2 و-b4 و-b7 ثم أصفارًا بعد ReLU.

  6. 7 multiplications instead of 327 عمليات ضرب بدلًا من 32

    The dense product needs 8 x 4 = 32 MACs. EIE performs 7, a 4.6x reduction, stores 11 weights instead of 32, and never touches columns 0 and 2.
    الضرب الكثيف يحتاج 8 x 4 = 32 عملية MAC. أما EIE فينفّذ 7 فقط، أي تقليل بمقدار 4.6x، ويخزّن 11 وزنًا بدلًا من 32، ولا يلمس العمودين 0 و2 أبدًا.
The 8 x 4 matrix with rows colored by PE. On hover the zero activations dim and strike through, columns 1 and 3 light up, each nonzero weight sends its product along its own row into b, and ReLU zeroes the three negative rows.مصفوفة 8 x 4 صفوفها ملوّنة حسب الـ PE. عند تمرير المؤشر تخفت التفعيلات الصفرية ويُشطب عليها، ويضيء العمودان 1 و3، وكل وزن غير صفري يرسل حاصل ضربه على طول صفه إلى b، ثم يصفّر ReLU الصفوف السالبة الثلاثة.
PEPERows ownedالصفوف التي يملكهاNonzero weights storedالأوزان غير الصفرية المخزّنةMACs performedعمليات MAC المنفّذةOutputs before ReLUالمُخرجات قبل ReLU
PE0PE00, 40, 4553 (w01, w03, w43)3 (w01, w03, w43)b0 = 4, b4 = -3b0 = 4, b4 = -3
PE1PE11, 51, 5220 (columns 0 and 2 skipped)0 (العمودان 0 و2 متخطّيان)b1 = 0, b5 = 0b1 = 0, b5 = 0
PE2PE22, 62, 6333 (w21, w23, w63)3 (w21, w23, w63)b2 = -1, b6 = 2b2 = -1, b6 = 2
PE3PE33, 73, 7111 (w71)1 (w71)b3 = 0, b7 = -8b3 = 0, b7 = -8
Totalالمجموع8 rows8 صفوف11 of 3211 من 327 of 32 dense MACs7 من 32 عملية MAC كثيفةReLU keeps b0 = 4 and b6 = 2يُبقي ReLU على b0 = 4 وb6 = 2
What each PE stores and does in the worked exampleما يخزّنه كل PE وما ينفّذه في المثال المحلول

The rule: interleave rows, broadcast activationsالقاعدة: وزّع الصفوف بالتناوب، وابثّ التفعيلات

The paper states the partition in one sentence: with N PEs, "PE_k holds all rows W_i, output activationsb_i, and input activations a_i for which i (mod N) = k". Rows are dealt out round-robin like cards, so PE0 gets rows 0, 4, 8 and so on. Each PE keeps only the nonzeros of its rows, in its own CSC arrays and its own SRAM, so no PE ever sees the full matrix and no zero weight is stored anywhere. That is the rule of thumb 0 x A = 0 made physical. On the left of slide 58 the same idea appears as hardware: a grid of identical PEs wired to one central control unit that does the scanning and broadcasting (the slide draws 16; the EIE configuration evaluated in the paper uses 64).

تذكر الورقة التقسيم في جملة واحدة: مع N من الـ PEs، "PE_k holds all rows W_i, output activations b_i, and input activations a_i for which i (mod N) = k"، أي أن PE_k يحمل كل الصفوف W_i وتفعيلات الإخراج b_i وتفعيلات الإدخال a_i التي تحقق i (mod N) = k. تُوزَّع الصفوف بالتناوب (round-robin) كما تُوزَّع أوراق اللعب، فيحصل PE0 على الصفوف 0 و4 و8 وهكذا. يحتفظ كل PE بالقيم غير الصفرية من صفوفه فقط، في مصفوفات CSC الخاصة به وفي ذاكرة SRAM الخاصة به، لذا لا يرى أي PE المصفوفة كاملة أبدًا ولا يُخزَّن أي وزن صفري في أي مكان. هذه هي القاعدة التقريبية 0 x A = 0 وقد تجسّدت في العتاد. وعلى يسار الشريحة 58 تظهر الفكرة نفسها كعتاد: شبكة من PEs متطابقة موصولة بوحدة تحكم مركزية واحدة تتولى المسح والبث (ترسم الشريحة 16؛ أما إعداد EIE الذي قيّمته الورقة فيستخدم 64).

PE(i)=i mod N,bi=ReLU(∑j∈YWij aj),Y={ j:aj≠0 }\mathrm{PE}(i) = i \bmod N, \qquad b_i = \mathrm{ReLU}\Big(\sum_{j \in Y} W_{ij}\, a_j\Big),\quad Y = \{\, j : a_j \neq 0 \,\}
Row ownership and the per-PE accumulation over nonzero activations onlyملكية الصفوف والمراكمة لكل PE على التنشيطات غير الصفرية فقط

The dataflow follows from the ownership. The paper describes it as "scanning vector a to find its next non-zero value a_j and broadcasting a_j along with its index j to all PEs. Each PE then multiplies a_j by the non-zero elements in its portion of column W_j, accumulating the partial sums in accumulators for each element of the output activation vector b." The broadcast is necessary because a_j lives in a column, and a column cuts across every PE's rows: any of the four might hold a nonzero in column j, and only the PE that owns row i is allowed to update b_i. The reward is that every output belongs to exactly one PE, so there is no reduction step between PEs at the end. The paper weighs this explicitly among three ways to partition the matrix and concludes that distributing rows gives "full locality for vector b. The drawback is that vector a needs to be broadcast". The broadcast is cheap: a is about 4 K long and about 30 percent dense, so around 1.2 K broadcasts per layer, each followed by many cycles of local work, and FIFOs decouple the controller from the PEs so the broadcast is not on the critical path.

تدفق البيانات (dataflow) ينتج مباشرة عن هذه الملكية. تصفه الورقة هكذا: "scanning vector a to find its next non-zero value a_j and broadcasting a_j along with its index j to all PEs. Each PE then multiplies a_j by the non-zero elements in its portion of column W_j, accumulating the partial sums in accumulators for each element of the output activation vector b."، أي مسح المتجه a لإيجاد قيمته غير الصفرية التالية a_j وبثّ a_j مع فهرسه j إلى كل الـ PEs، ثم يضرب كل PE القيمة a_j في العناصر غير الصفرية في حصته من العمود W_j، ويجمّع المجاميع الجزئية في مُجمِّعات (accumulators) لكل عنصر من متجه تفعيلات الإخراج b. الـ broadcast (البث) ضروري لأن a_j يقابل عمودًا، والعمود يقطع صفوف كل الـ PEs: أيٌّ من الأربعة قد يحمل قيمة غير صفرية في العمود j، ووحده الـ PE الذي يملك الصف i مسموح له بتحديث b_i. والمكافأة أن كل مُخرَج ينتمي إلى PE واحد بالضبط، فلا حاجة إلى خطوة اختزال (reduction) بين الـ PEs في النهاية. توازن الورقة هذا صراحةً بين ثلاث طرق لتقسيم المصفوفة وتخلص إلى أن توزيع الصفوف يعطي "full locality for vector b. The drawback is that vector a needs to be broadcast"، أي محلية كاملة للمتجه b، وعيبها أن المتجه a يجب أن يُبثّ. والبث رخيص: طول a نحو 4 K وكثافته نحو 30 percent، أي قرابة 1.2 K عملية بث لكل طبقة، تتبع كلًّا منها دورات كثيرة من العمل المحلي، وطوابير FIFO تفصل المتحكم عن الـ PEs حتى لا يقع البث على المسار الحرج (critical path).

Zero activations, the Activation sparsity of the previous concept, are handled by the scan itself. A zero is never broadcast, so its whole column is skipped for all N PEs in one decision, which is W x 0 = 0 made physical and what slide 60 highlights by boxing a0 = 0. In part 08 that scan is the Leading non-zero detection unit, and the word "logically" on slide 59 is a reminder that the tidy 8 x 4 grid is the logical view only. Physically PE0 holds a compressed slice with five entries and never sees the zeros that the figure draws.

التفعيلات الصفرية، أي الـ activation sparsity من المفهوم السابق، يعالجها المسح نفسه. الصفر لا يُبثّ أبدًا، لذا يُتخطّى عموده كاملًا لكل الـ N من الـ PEs بقرار واحد، وهذه هي W x 0 = 0 وقد تجسّدت في العتاد، وهي ما تبرزه الشريحة 60 بوضع إطار حول a0 = 0. في الجزء 08 يكون هذا المسح هو وحدة الـ leading non-zero detection، وكلمة "logically" (منطقيًا) على الشريحة 59 تذكير بأن شبكة 8 x 4 المرتبة هي العرض المنطقي فقط. فعليًا يحمل PE0 شريحة مضغوطة فيها خمسة مُدخلات، ولا يرى أبدًا الأصفار التي يرسمها الشكل.

SimulatorمحاكيEIE sparse matrix-vector stepper: four PEs, one broadcast at a timeمتتبع ضرب المصفوفة المتناثرة في المتجه في EIE: أربع وحدات PE، وبث واحد في كل مرة
Click any weight to step it through 0, 2, -3, 1 (other values reset to 0), and any activation through 0, 1, 2, 3. Editing resets the broadcast schedule.انقر أي وزن لتنقله عبر 0, 2, -3, 1 (القيم الأخرى تعود إلى 0)، وأي تنشيط لتنقله عبر 0, 1, 2, 3. أي تعديل يعيد ضبط جدول البث.
a
no broadcast yetلا بث بعد
row 0 PE0
b00ReLU0
row 1 PE1
b10ReLU0
row 2 PE2
b20ReLU0
row 3 PE3
b30ReLU0
row 4 PE0
b40ReLU0
row 5 PE1
b50ReLU0
row 6 PE2
b60ReLU0
row 7 PE3
b70ReLU0
  • PE0rows 0, 4الصفوف 0, 4idle this broadcastخاملة في هذا البث5 stored5 مخزّنة0 MACs so far0 MACs حتى الآن
  • PE1rows 1, 5الصفوف 1, 5idle this broadcastخاملة في هذا البث2 stored2 مخزّنة0 MACs so far0 MACs حتى الآن
  • PE2rows 2, 6الصفوف 2, 6idle this broadcastخاملة في هذا البث3 stored3 مخزّنة0 MACs so far0 MACs حتى الآن
  • PE3rows 3, 7الصفوف 3, 7idle this broadcastخاملة في هذا البث1 stored1 مخزّنة0 MACs so far0 MACs حتى الآن
MACsMACs7 of 324.6x fewer than denseأقل بـ 4.6x من الحالة الكثيفة
Weights stored11 of 32zeros are never written to SRAMالأصفار لا تُكتب في SRAM أبدًا
Columns skipped2 of 4zero activations never broadcastالتنشيطات الصفرية لا تُبث أبدًا
Busiest PEأكثر PE انشغالا3 vs 1.75imbalance 1.7x across 4 PEsعدم توازن 1.7x عبر 4 PEs

Row i belongs to PE (i mod 4), so each output b_i is accumulated inside exactly one PE and no result ever crosses between PEs. The controller scans a for its next nonzero, broadcasts that value with its column index, and every PE multiplies it by the nonzero weights it holds in that column. A zero activation means the whole column is skipped for all four PEs at once, and a zero weight was never stored, so neither rule of thumb costs a cycle. The imbalance readout shows the price: whichever PE holds the most nonzeros in the broadcast column sets the pace.الصف i ينتمي إلى PE (i mod 4)، لذا يُجمَّع كل خرج b_i داخل PE واحدة بالضبط ولا تنتقل أي نتيجة بين وحدات PE. يفحص المتحكم المتجه a بحثًا عن القيمة غير الصفرية التالية، ويبثها مع فهرس عمودها، فتضربها كل PE في الأوزان غير الصفرية التي تحملها في ذلك العمود. التنشيط الصفري يعني تخطي العمود كله في الوحدات الأربع معًا، والوزن الصفري لم يُخزَّن أصلًا، فلا تكلف أي من القاعدتين دورة واحدة. ويُظهر مؤشر عدم التوازن الثمن: الوحدة التي تحمل أكثر القيم غير الصفرية في عمود البث هي التي تحدد الإيقاع.

Why interleave rather than blockلماذا التوزيع بالتناوب لا بالكتل

The paper weighs three partitions (Section VII-A). Splitting by columns gives each a_j to one PE but needs a reduction across PEs and becomes unbalanced because a is 70 percent zero. 2D blocks need both a broadcast and a reduction. Splitting by rows keeps each b_i local and costs only one broadcast per column. Dealing rows out round-robin (rather than in contiguous blocks, a choice the paper does not justify explicitly) spreads each column's nonzeros across PEs. The small example already shows the residual problem: column 3 gives PE0 and PE2 two multiplications each while PE1 and PE3 get none, and over the whole product PE1 does nothing at all. The busiest PE sets the pace of every broadcast. This is the Load balance issue that the activation queue in part 08 softens by letting PEs run ahead, and that ESE later attacked at pruning time.

توازن الورقة بين ثلاثة تقسيمات (Section VII-A). التقسيم حسب الأعمدة يعطي كل a_j لـ PE واحد، لكنه يحتاج إلى اختزال (reduction) عبر الـ PEs ويصبح غير متوازن لأن 70 percent من a أصفار. والكتل ثنائية الأبعاد (2D blocks) تحتاج إلى بث واختزال معًا. أما التقسيم حسب الصفوف فيُبقي كل b_i محليًا ولا يكلّف إلا بثًا واحدًا لكل عمود. وتوزيع الصفوف بالتناوب (round-robin) بدلًا من كتل متجاورة، وهو اختيار لا تبرره الورقة صراحةً، ينشر القيم غير الصفرية في كل عمود على الـ PEs. والمثال الصغير يُظهر بالفعل المشكلة المتبقية: العمود 3 يعطي PE0 وPE2 عمليتي ضرب لكل منهما بينما لا يحصل PE1 وPE3 على شيء، وعلى امتداد الضرب كله لا يفعل PE1 شيئًا على الإطلاق. الـ PE الأكثر انشغالًا يحدد إيقاع كل عملية بث. هذه هي مشكلة الـ load balance (توازن الحمل) التي يخففها طابور التفعيلات (activation queue) في الجزء 08 بالسماح للـ PEs بأن تسبق غيرها، والتي عالجها ESE لاحقًا وقت الـ pruning.

Quick checkاختبار سريع

In EIE, how are the rows of the weight matrix assigned to processing elements?في EIE، كيف تُوزَّع صفوف مصفوفة الأوزان على وحدات المعالجة (processing elements)؟

Quick checkاختبار سريع

The central control unit finds a nonzero activation a_j. What does EIE do with it?تجد وحدة التحكم المركزية قيمة تفعيل غير صفرية a_j. ماذا يفعل EIE بها؟

Recall

In EIE with N PEs, which PE holds row i, and what happens when the controller finds a nonzero a_j?في EIE مع N من الـ PEs، أي PE يحمل الصف i، وماذا يحدث حين يجد المتحكم قيمة غير صفرية a_j؟

PE (i mod N). The controller broadcasts a_j with its index j to all PEs; each PE multiplies it by the nonzero weights in its slice of column j and accumulates into its own b_i. Zero activations are never broadcast, so their columns are skipped.
الـ PE (i mod N). يبثّ المتحكم a_j مع فهرسه j إلى كل الـ PEs؛ ويضربه كل PE في الأوزان غير الصفرية في حصته من العمود j ويجمّع النتيجة في b_i الخاص به. التفعيلات الصفرية لا تُبثّ أبدًا، لذا تُتخطّى أعمدتها.

Recall

Which layers did EIE accelerate, and which did it not?أي الطبقات سرّعها EIE، وأيها لم يسرّعها؟

Fully connected layers of AlexNet and VGG-16 and the LSTM matrices of NeuralTalk, all matrix-vector products at batch size 1. It does not run convolutions.
الطبقات المتصلة بالكامل في AlexNet وVGG-16 ومصفوفات LSTM في NeuralTalk، وكلها عمليات ضرب مصفوفة في متجه عند batch size 1. ولا يشغّل الـ convolutions.

Recapالخلاصة

If you remember nothing elseإن لم تتذكر شيئاً آخر فتذكّر هذا

  • Pruning alone leaves gains on paper: a 91 percent sparse AlexNet FC6 runs only 2.5x faster on a CPU and 4x on a Titan X at batch 1, and slower than dense at batch 64.الـ pruning وحده يترك المكاسب على الورق: طبقة FC6 في AlexNet المتناثرة بنسبة 91 percent تعمل أسرع بـ 2.5x فقط على الـ CPU وبـ 4x على Titan X عند batch 1، وأبطأ من النسخة الكثيفة (dense) عند batch 64.
  • Han's paradigm: train, compress (prune, quantize, Huffman), then run on an engine that computes directly on the compressed form (NeurIPS 2015, ICLR 2016, ISCA 2016, FPGA 2017).نموذج Han: درّب، ثم اضغط (pruning ثم quantization ثم Huffman)، ثم شغّل على محرك يحسب مباشرة على الصيغة المضغوطة (NeurIPS 2015، ICLR 2016، ISCA 2016، FPGA 2017).
  • EIE was the first accelerator for sparse, compressed networks: 189x faster and 24,000x more energy efficient than a CPU, 13x and 3,400x versus a GPU, 102 GOPS on compressed work equal to 3 TOPS dense, 64 PEs at 800 MHz, 600 mW.كان EIE أول مسرّع للشبكات المتناثرة المضغوطة: أسرع بـ 189x وأكفأ في الطاقة بـ 24,000x من الـ CPU، و13x و3,400x مقارنة بالـ GPU، و102 GOPS على العمل المضغوط تعادل 3 TOPS على الشبكة الكثيفة، بـ 64 PEs عند 800 MHz واستهلاك 600 mW.
  • Three savings: sparse weights (90 percent static) 10x compute and 5x memory; sparse activations (70 percent dynamic) 3x compute; weight sharing (4-bit) 8x memory. Rules of thumb 0 x A = 0 and W x 0 = 0.ثلاثة مصادر للتوفير: الأوزان المتناثرة (90 percent ثابت) توفر 10x في الحساب و5x في الذاكرة؛ التفعيلات المتناثرة (70 percent ديناميكي) توفر 3x في الحساب؛ مشاركة الأوزان (4-bit) توفر 8x في الذاكرة. القاعدتان التقريبيتان: 0 x A = 0 و W x 0 = 0.
  • Static sparsity is fixed after training; dynamic sparsity is created by ReLU per input and must be detected at run time.التناثر الثابت يتحدد نهائيًا بعد التدريب؛ أما التناثر الديناميكي فيصنعه ReLU لكل مُدخل على حدة ويجب اكتشافه وقت التشغيل.
  • Rows are interleaved, PE_k holds rows i with i mod N = k, so every output stays local; nonzero activations are broadcast with their index and zero activations skip whole columns.الصفوف موزعة بالتناوب، فالـ PE_k يحمل الصفوف i التي تحقق i mod N = k، لذا يبقى كل مُخرَج محليًا؛ وتُبثّ التفعيلات غير الصفرية مع فهرسها، والتفعيلات الصفرية تجعل أعمدة كاملة تُتخطّى.
  • EIE targets matrix-vector products in FC and LSTM layers at batch size 1, not convolutions.يستهدف EIE ضرب المصفوفة في المتجه في طبقات FC و LSTM عند batch size 1، وليس الـ convolutions.

Sourcesالمصادر