Lecture 04-2 · Pruning and Sparsity II

المحاضرة 04-2 · التقليم والتناثر (Pruning and Sparsity II)

EIE: sparse weights, sparse activations, shared weights

EIE: أوزان متناثرة، وتنشيطات متناثرة، وأوزان مشتركة

Slides 53–60 الشرائح 53–60 P1 MUST

Pruning removes 90 percent of the multiplications on paper, but a CPU or GPU barely gets faster. EIE is the hardware that turns the zeros into real speed and energy: it never stores a zero weight and never broadcasts a zero activation.

Pruning يحذف 90% من عمليات الضرب على الورق، لكن CPU أو GPU بالكاد يصبح أسرع. EIE هو العتاد الذي يحوّل الأصفار إلى سرعة وطاقة حقيقيتين: لا يخزّن وزناً صفرياً أبداً، ولا يبثّ activation صفرياً أبداً.

High exam risk احتمال عالٍ في الامتحان

Expect three things: the three savings with their numbers (90% static, 70% dynamic, 4-bit; 10x and 5x, 3x, 8x), the static versus dynamic distinction, and a small matrix-vector product split over N PEs where you count the multiplications EIE actually performs.

توقّع ثلاثة أشياء: التوفيرات الثلاثة بأرقامها (90% static و70% dynamic و4-bit؛ 10x و5x ثم 3x ثم 8x)، والفرق بين static وdynamic، وضرب مصفوفة في متجه صغير موزّع على N من PEs تَعُدّ فيه عمليات الضرب التي ينفذها EIE فعلاً.

Why pruning alone is not enough, slides 53 to 55

لماذا لا يكفي التقليم وحده، الشرائح 53 إلى 55

Slide 53 closes the five questions of pruning (what, granularity, criterion, ratio, fine-tuning). The question left is: on what hardware? The EIE paper timed AlexNet's FC6 layer (4096 x 9216), pruned to 91 percent zeros, against the dense version using the vendors' best dense and sparse kernels.

الشريحة 53 تُغلق أسئلة pruning الخمسة (ما هو، granularity، criterion، ratio، fine-tuning). والسؤال المتبقي: على أي عتاد؟ قاس بحث EIE طبقة FC6 في AlexNet (4096 x 9216) بعد تقليمها إلى 91% أصفار، مقارنةً بالنسخة الكثيفة، باستخدام أفضل kernels كثيفة ومتفرقة من الشركات المصنعة.

PlatformالمنصةBatchBatchDenseكثيفSparseمتناثرSparse vs denseالمتناثر مقابل الكثيف
Core i7-5930k CPUمعالج Core i7-5930k CPU17516.2 μs3066.5 μs2.5x fasterأسرع بـ 2.5x
Titan X GPUTitan X GPU1541.5 μs134.8 μs4.0x fasterأسرع بـ 4.0x
Titan X GPUTitan X GPU6419.8 μs94.6 μs4.8x slowerأبطأ بـ 4.8x

Removing 91 percent of the work should give about 11x. It gives 2.5x and 4x, and at batch 64 the sparse kernel is slower than dense. A general-purpose core cannot skip a zero for free: it reads an index, computes an address, gathers a scattered activation and takes a cache miss, and that bookkeeping costs more than the multiply it saved. Fewer FLOPs is not fewer microseconds.

حذف 91% من العمل يُفترض أن يعطي نحو 11x. لكنه يعطي 2.5x و4x فقط، وعند batch 64 يصبح الـ sparse kernel أبطأ من الكثيف. المعالج العام لا يستطيع تخطي الصفر مجاناً: يقرأ index، ويحسب عنواناً، ويجمع activation متناثراً، ويتعرض لـ cache miss، وهذه المحاسبة تكلّف أكثر من عملية الضرب التي وفّرها. قلّة FLOPs لا تعني قلّة الميكروثواني.

Slide 54 names three systems and the sparsity each exploits: EIE (weight sparsity and activation sparsity in FC layers), the NVIDIA sparse tensor core (structured 2:4 weight sparsity), and TorchSparse with PointAcc (activation sparsity of point clouds). Slide 56 is Han's paradigm: train, compress (prune, quantize, Huffman), then run on an engine built for the compressed form. Compression and hardware were designed together.

الشريحة 54 تذكر ثلاثة أنظمة ونوع التفرّق الذي يستغله كل منها: EIE (تفرّق الأوزان وتفرّق activations في طبقات FC)، وNVIDIA sparse tensor core (تفرّق أوزان منظم 2:4)، وTorchSparse مع PointAcc (تفرّق activations في point clouds). والشريحة 56 هي منهج Han: درّب، ثم اضغط (prune وquantize وHuffman)، ثم شغّل على محرّك مبني للصيغة المضغوطة. الضغط والعتاد صُمّما معاً.

EIE in one line, slide 57

EIE في سطر واحد، الشريحة 57

EIE (Efficient Inference Engine, Han et al., ISCA 2016) is the first DNN accelerator for sparse, compressed models. Against the baselines on nine FC and LSTM layers at batch 1 it is 189x faster and 24,000x more energy efficient than a CPU, and 13x faster and 3,400x more energy efficient than a GPU. The evaluated design has 64 PEs at 800 MHz.

EIE (Efficient Inference Engine، Han et al., ISCA 2016) هو أول مسرّع DNN للنماذج المتفرقة والمضغوطة. مقارنةً بالمعايير على تسع طبقات FC وLSTM عند batch 1 فهو أسرع بـ 189x وأكفأ طاقياً بـ 24,000x من CPU، وأسرع بـ 13x وأكفأ طاقياً بـ 3,400x من GPU. التصميم المُقيَّم فيه 64 PEs بتردد 800 MHz.

Sparse weight

أوزان متناثرة (Sparse weight)

90% static sparsity. Rule: 0 x A = 0. 10x less computation, 5x less memory.

تفرّق 90% static. القاعدة: 0 x A = 0. حساب أقل بـ 10x، وذاكرة أقل بـ 5x.

Sparse activation

تنشيطات متناثرة (Sparse activation)

70% dynamic sparsity. Rule: W x 0 = 0. 3x less computation. No memory saving claimed.

تفرّق 70% dynamic. القاعدة: W x 0 = 0. حساب أقل بـ 3x. ولا يُدّعى أي توفير في الذاكرة.

Weight sharing

مشاركة الأوزان (Weight sharing)

4-bit weights. Rule: 2.09, 1.92 => 2. 8x less memory. No computation saving claimed.

أوزان 4-bit. القاعدة: 2.09, 1.92 => 2. ذاكرة أقل بـ 8x. ولا يُدّعى أي توفير في الحساب.

Where each number comes from. Keeping 10% of the weights means 1/0.1 = 10x fewer multiplies. Keeping 30% of the activations means 1/0.3 = 3.3, rounded to 3x. Shared weights are 4-bit indices into a 16-entry codebook instead of 32-bit floats, so 32/4 = 8x. Two weights 2.09 and 1.92 both snap to the same centroid 2 and are stored as the same index.

من أين يأتي كل رقم. إبقاء 10% من الأوزان يعني ضرباً أقل بـ 1/0.1 = 10x. وإبقاء 30% من activations يعني 1/0.3 = 3.3، تُقرَّب إلى 3x. والأوزان المشتركة هي indices من 4-bit إلى codebook من 16 قيمة بدلاً من 32-bit floats، إذن 32/4 = 8x. والوزنان 2.09 و1.92 كلاهما ينجذب إلى المركز نفسه 2 ويُخزّنان بالـ index نفسه.

bi = ReLU( Σj ∈ Xi ∩ Y S[Iij] · aj )

في الصيغة: Xi هي أعمدة الصف i غير الصفرية (ثابتة)، وY هي مواقع activations غير الصفرية (متغيرة)، وS هو codebook من 16 قيمة، وIij هو index من 4-bit. الجمع يمر فقط على الأزواج غير الصفرية في الطرفين.

The sum runs only over Xi ∩ Y: columns where both the weight and the activation are nonzero. That is the 10x and the 3x. The weight appears as a codebook lookup S[Iij]: that is the 8x.

الجمع يمر فقط على Xi ∩ Y: الأعمدة التي يكون فيها الوزن وactivation كلاهما غير صفري. هذا هو 10x و3x. والوزن يظهر كقراءة من codebook أي S[Iij]: وهذا هو 8x.

Why memory drops 5x, not 10x

لماذا تنخفض الذاكرة 5x وليس 10x

A nonzero stored without its neighbors must carry its position. EIE stores each surviving weight with a 4-bit relative index next to its 4-bit value, so half of every stored entry is bookkeeping. The 10x from sparsity becomes 5x in memory. Computation keeps the full 10x because the index is read but never multiplied.

القيمة غير الصفرية المخزّنة بدون جيرانها يجب أن تحمل موقعها. يخزّن EIE كل وزن باقٍ مع relative index من 4-bit بجانب قيمته من 4-bit، فنصف كل مُدخَل مخزّن هو معلومات محاسبية. لذلك يصبح 10x من التفرّق 5x في الذاكرة. أما الحساب فيحتفظ بـ 10x كاملة لأن الـ index يُقرأ ولا يُضرب.

Worked مثال محلول 
100 weights, dense 32-bit                 100 x 32      = 3200 bits
10 survive, value + same-width index      10 x (32+32)  =  640 bits   3200/640 =  5x  (sparsity)
4-bit code + 4-bit index                  10 x (4+4)    =   80 bits    640/80  =  8x  (sharing)
total                                                   3200/80 = 40x = 5 x 8

Static versus dynamic

الثابت مقابل الديناميكي

Static sparsity is fixed once pruning and fine-tuning finish: the set Xi is the same for every input, so the storage format can be built offline with every zero weight already removed. Dynamic sparsity is created by ReLU for each input: a different image gives a different set of negative pre-activations, so Y changes every inference and must be detected at run time. The 70% is an average, not a mask you can store.

Static sparsity ثابتة بمجرد انتهاء pruning وfine-tuning: المجموعة Xi نفسها لكل مدخل، فيمكن بناء صيغة التخزين مسبقاً مع حذف كل الأوزان الصفرية. أما dynamic sparsity فينشئها ReLU لكل مدخل: صورة مختلفة تعطي مجموعة مختلفة من pre-activations السالبة، فتتغير Y في كل استدلال ويجب اكتشافها وقت التشغيل. ونسبة 70% متوسط، وليست قناعاً يمكن تخزينه.

Parallelization: rows interleaved, activations broadcast, slides 58 to 60

التوازي: صفوف متداخلة بالتناوب، وتنشيطات تُبث للجميع، الشرائح 58 إلى 60

With N PEs, PEk holds every row i with i mod N = k, plus the outputs bi of those rows. Rows are dealt round-robin like cards: PE0 gets rows 0, 4, 8 and so on. Each PE stores only the nonzeros of its rows in its own SRAM.

مع N من PEs، يحمل PEk كل صف i يحقق i mod N = k، مع مخرجات bi لتلك الصفوف. تُوزَّع الصفوف بالتناوب كأوراق اللعب: PE0 يأخذ الصفوف 0 و4 و8 وهكذا. وكل PE يخزّن فقط القيم غير الصفرية من صفوفه في ذاكرة SRAM الخاصة به.

The central control unit scans a for the next nonzero aj and broadcasts the pair (aj, j) to all PEs. Each PE multiplies aj by its nonzeros in column j and accumulates into its own bi. The broadcast is needed because a column cuts across every PE's rows. A zero activation is never broadcast, so its whole column is skipped for all PEs in one decision. Since each bi belongs to exactly one PE, there is no reduction between PEs.

وحدة التحكم المركزية تمسح a بحثاً عن القيمة غير الصفرية التالية aj وتبثّ الزوج (aj, j) إلى كل PEs. كل PE يضرب aj في قيمه غير الصفرية في العمود j ويجمع في bi الخاص به. البث ضروري لأن العمود يقطع صفوف كل PEs. والـ activation الصفري لا يُبثّ أبداً، فيُتخطى عموده كاملاً لكل PEs بقرار واحد. وبما أن كل bi يتبع PE واحداً فقط، فلا حاجة لأي reduction بين PEs.

a = 0 j=0 2 j=1 0 j=2 1 j=3 PE0 row 0 1 3 0 -2 PE1 row 1 0 0 5 0 PE2 row 2 0 -1 0 1 PE3 row 3 0 0 0 0 PE0 row 4 0 0 2 -3 PE1 row 5 6 0 0 0 PE2 row 6 0 0 0 2 PE3 row 7 0 -4 0 0 b before ReLU after ReLU = → b0 = 4 b0 = 4 b1 = 0 b1 = 0 b2 = -1 b2 = 0 b3 = 0 b3 = 0 b4 = -3 b4 = 0 b5 = 0 b5 = 0 b6 = 2 b6 = 2 b7 = -8 b7 = 0 dense 8 x 4 = 32 MACs, EIE does 7 columns 0 and 2 never broadcast, row i lives in PE (i mod 4)
The slide 58 figure with numbers. Row colors show the owning PE (i mod 4). Columns 0 and 2 are struck through because a0 = a2 = 0. Filled boxes are the 7 weights actually multiplied; outlined boxes are stored but never read for this input.
شكل الشريحة 58 بالأرقام. ألوان الصفوف تبيّن PE المالك (i mod 4). العمودان 0 و2 مشطوبان لأن a0 = a2 = 0. المربعات المملوءة هي الأوزان الـ 7 التي تُضرب فعلاً، والمربعات المحددة بإطار فقط مخزنة لكنها لا تُقرأ أبداً لهذا المدخل.
Worked: count the multiplications مثال محلول: عُدّ عمليات الضرب

a = (0, 2, 0, 1). Nonzeros: w00 = 1, w01 = 3, w03 = −2, w12 = 5, w21 = −1, w23 = 1, w42 = 2, w43 = −3, w50 = 6, w63 = 2, w71 = −4 (11 of 32). Four PEs.

a = (0, 2, 0, 1). القيم غير الصفرية: w00 = 1, w01 = 3, w03 = −2, w12 = 5, w21 = −1, w23 = 1, w42 = 2, w43 = −3, w50 = 6, w63 = 2, w71 = −4 (11 من 32). أربعة PEs.

a0 = 0  skip column 0 (w00, w50 never read)
broadcast (2, j=1):  PE0 b0 += 3 x 2 = 6     PE2 b2 += -1 x 2 = -2
                     PE3 b7 += -4 x 2 = -8   PE1 idle             3 MACs
a2 = 0  skip column 2 (w12, w42 never read)
broadcast (1, j=3):  PE0 b0 += -2 x 1 -> 4   PE0 b4 += -3 x 1 = -3
                     PE2 b2 += 1 x 1 -> -1   PE2 b6 += 2 x 1 = 2   4 MACs
b      = (4, 0, -1, 0, -3, 0, 2, -8)
ReLU b = (4, 0,  0, 0,  0, 0, 2,  0)
MACs: dense 8 x 4 = 32, EIE 3 + 4 = 7   per PE: 3, 0, 3, 1

Notice the uneven per-PE load (3, 0, 3, 1): the busiest PE sets the pace, which is the load-balance problem the activation queue solves on the next page.

لاحظ الحِمل غير المتساوي لكل PE (3, 0, 3, 1): أكثر PE انشغالاً يحدد الإيقاع، وهذه هي مشكلة load balance التي تحلّها activation queue في الصفحة التالية.

Exam trap فخ امتحاني

Static is weights, dynamic is activations. Weight zeros are fixed after pruning; activation zeros come from ReLU and change per input. Do not swap them. Rows are partitioned, activations are broadcast. Each PE does not get a quarter of a; every PE hears every nonzero aj. What is split is the weight matrix, by interleaved rows (i mod N), not by contiguous blocks or by columns. Finally, sparse weights save 5x memory, not 10x, because of the index.

Static للأوزان، وdynamic للـ activations. أصفار الأوزان ثابتة بعد pruning؛ وأصفار activations تأتي من ReLU وتتغير مع كل مدخل. لا تخلط بينهما. الصفوف تُقسَّم، وactivations تُبثّ. لا يأخذ كل PE ربع a؛ بل كل PE يسمع كل aj غير صفري. المُقسَّم هو مصفوفة الأوزان، بصفوف متناوبة (i mod N)، لا بكتل متتالية ولا بأعمدة. وأخيراً، الأوزان المتفرقة توفر 5x في الذاكرة لا 10x بسبب الـ index.

Memory trick حيلة للحفظ

"10, 3, 8: skip, skip, shrink." Skip zero weights (10x compute), skip zero activations (3x compute), shrink the survivors to 4 bits (8x memory). And "deal rows, shout activations": rows are dealt like cards, activations are shouted to everyone.

"10, 3, 8: تخطَّ، تخطَّ، صغّر." تخطَّ الأوزان الصفرية (10x حساب)، وتخطَّ activations الصفرية (3x حساب)، وصغّر الباقي إلى 4 bits (8x ذاكرة). وتذكّر: "وزّع الصفوف، وانادِ بالـ activations": الصفوف تُوزَّع كالأوراق، وactivations يُنادى بها للجميع.

Check yourself

اختبر نفسك

A 91% sparse AlexNet FC6 is run with cuSPARSE on a Titan X at batch 64. Compared with the dense GEMV, it is:

طبقة FC6 في AlexNet بتفرّق 91% تُشغَّل بـ cuSPARSE على Titan X عند batch 64. مقارنةً بـ GEMV الكثيف، فهي:

C. 94.6 μs sparse against 19.8 μs dense. At batch 64 the dense kernel uses the GPU's full width while the sparse kernel pays for indexing and gathers. B is the batch 1 result; A is the arithmetic promise that general-purpose hardware cannot deliver.

الجواب C. 94.6 μs للمتفرق مقابل 19.8 μs للكثيف. عند batch 64 يستخدم الـ kernel الكثيف كامل عرض GPU بينما يدفع المتفرق ثمن الفهرسة والتجميع. والخيار B هو نتيجة batch 1؛ وA هو الوعد الحسابي الذي لا يحققه العتاد العام.

Which of EIE's three savings is dynamic?

أي التوفيرات الثلاثة في EIE هو dynamic؟

B. ReLU zeroes whichever pre-activations are negative for this input, so the zero pattern changes every inference. Pruned weights and the codebook are fixed at deployment, which makes A and C static.

الجواب B. ReLU يُصفّر أي pre-activations سالبة لهذا المدخل، فيتغير نمط الأصفار في كل استدلال. أما الأوزان المقلّمة وcodebook فثابتة عند النشر، ما يجعل A وC من نوع static.

Why does 90% weight sparsity cut EIE's memory by only 5x while cutting computation by 10x?

لماذا يخفض تفرّق الأوزان بنسبة 90% ذاكرة EIE بـ 5x فقط بينما يخفض الحساب بـ 10x؟

A. A 4-bit relative index sits next to each 4-bit value, so each survivor costs twice its value bits: 10x / 2 = 5x. The index is read but never multiplied, so compute keeps 10x. B confuses this with the rare padding zero.

الجواب A. يوجد relative index من 4-bit بجانب كل قيمة من 4-bit، فكل وزن باقٍ يكلف ضعف بتات قيمته: 10x / 2 = 5x. الـ index يُقرأ ولا يُضرب، فيحتفظ الحساب بـ 10x. والخيار B يخلط ذلك بالـ padding zero النادر.

With 4 PEs and interleaved rows, which rows does PE1 own in a 12-row matrix?

مع 4 PEs وصفوف متناوبة، أي الصفوف يملكها PE1 في مصفوفة من 12 صفاً؟

D. PEk owns row i when i mod N = k, so 1 mod 4, 5 mod 4 and 9 mod 4 are all 1. A and C are contiguous blocks, which EIE does not use; B partitions by column, but in EIE columns are reached through broadcast.

الجواب D. يملك PEk الصف i عندما i mod N = k، و1 mod 4 و5 mod 4 و9 mod 4 كلها تساوي 1. والخياران A وC كتل متتالية لا يستخدمها EIE؛ وB تقسيم بالأعمدة، بينما في EIE يُوصل إلى الأعمدة عبر البث.

In the worked 8 x 4 example with a = (0, 2, 0, 1), how many multiplications does EIE perform?

في مثال 8 x 4 المحلول مع a = (0, 2, 0, 1)، كم عملية ضرب ينفذ EIE؟

B. Only nonzero weights in the broadcast columns 1 and 3: three in column 1 and four in column 3. A is the dense count, C counts every stored nonzero including columns 0 and 2, and D is the dense count of the two nonzero columns.

الجواب B. فقط الأوزان غير الصفرية في العمودين المبثوثين 1 و3: ثلاثة في العمود 1 وأربعة في العمود 3. والخيار A هو العدد الكثيف، وC يعدّ كل قيمة غير صفرية مخزّنة بما فيها العمودان 0 و2، وD هو العدد الكثيف للعمودين غير الصفريين.