Lecture 04-1 · Pruning and Sparsity I
المحاضرة 04-1 · التقليم والتناثر (Pruning and Sparsity I)
Pruning granularity spectrum
طيف دقة التقليم (granularity)
P1 MUSTGranularity is the size of the unit you delete. Small units give flexibility and compression; big units give regular structure and real speedup. Know which tensor dimension each level removes and be able to count it.
Granularity هي حجم الوحدة التي تحذفها. الوحدات الصغيرة تعطي مرونة وضغطاً أكبر، والوحدات الكبيرة تعطي بنية منتظمة وتسريعاً حقيقياً. اعرف أي بُعد من أبعاد tensor تحذفه كل درجة، وكن قادراً على عدّه.
Name the five levels in order from irregular to regular, say which dimension of [co, ci, kh, kw] each one removes, compute the sparsity of a small tensor after a given cut, and explain why fine-grained compresses more but coarse-grained runs faster.
سمِّ الدرجات الخمس بالترتيب من غير المنتظم إلى المنتظم، وقل أي بُعد من [co, ci, kh, kw] تحذفه كل درجة، واحسب sparsity لـ tensor صغير بعد قطع معيّن، واشرح لماذا يضغط fine-grained أكثر بينما يعمل coarse-grained أسرع.
Granularity on a 2D matrix
دقة التقليم على مصفوفة ثنائية الأبعاد
Slide 15 starts with an 8 × 8 FC weight matrix and prunes it two ways:
تبدأ الشريحة 15 بمصفوفة أوزان FC بحجم 8 × 8 وتحذف منها بطريقتين:
Fine-grained / unstructured
دقيق الحبيبات / غير مُهيكل (fine-grained / unstructured)
Any individual weight may be zeroed. More flexible pruning index choice, so it keeps the most important weights wherever they are. Hard to accelerate: the zeros are scattered irregularly, the matrix keeps its shape, and you need sparse formats with index overhead plus special hardware to skip them.
أي وزن مفرد يمكن جعله صفراً. اختيار مواضع الحذف أكثر مرونة، فيُبقي الأوزان الأهم أينما كانت. لكنه صعب التسريع: الأصفار مبعثرة بلا انتظام، والمصفوفة تحتفظ بشكلها، وتحتاج صيغ تخزين متفرقة مع كلفة إضافية للفهارس وعتاداً خاصاً لتخطيها.
Coarse-grained / structured
خشن الحبيبات / مُهيكل (coarse-grained / structured)
Whole rows are removed (in the slide, rows 3, 4 and 7 of 8). Less flexible: the allowed masks are a subset of the fine-grained ones. Easy to accelerate: delete the rows and you have "just a smaller matrix" (5 × 8), dense, which any hardware runs at full speed.
تُحذف صفوف كاملة (في الشريحة الصفوف 3 و4 و7 من 8). أقل مرونة: الأقنعة المسموحة مجموعة جزئية من أقنعة fine-grained. لكنه سهل التسريع: احذف الصفوف فيصبح لديك "مجرد مصفوفة أصغر" (5 × 8) كثيفة يشغّلها أي عتاد بسرعته الكاملة.
slide 15 structured example: 8 x 8 = 64 weights, remove 3 rows of 8 removed = 3 x 8 = 24 sparsity = 24 / 64 = 37.5 % result = dense 5 x 8 matrix (40 weights), no index storage needed
مثال الشريحة 15 المنتظم: 8 x 8 = 64 وزناً، نحذف 3 صفوف كل منها 8، فالمحذوف 24 والـ sparsity تساوي 24 / 64 = 37.5%، والنتيجة مصفوفة كثيفة 5 x 8 (40 وزناً) لا تحتاج تخزين فهارس.
Why "subset" matters
لماذا تهمّ كلمة "مجموعة جزئية" (subset)
Every structured mask (whole rows zero) is also a valid unstructured mask, but not the other way round. So the best fine-grained mask at a given sparsity is at least as good as the best coarse-grained one. Stated the way exams like it: at equal accuracy, fine-grained reaches equal or higher sparsity; at equal sparsity, fine-grained keeps equal or higher accuracy. What coarse buys back is speed, not compression.
كل قناع منتظم (صفوف كاملة صفرية) هو أيضاً قناع غير منتظم صالح، والعكس غير صحيح. إذن أفضل قناع fine-grained عند sparsity معيّنة جيد على الأقل مثل أفضل قناع coarse-grained. وبالصيغة التي تحبها الامتحانات: عند الدقة نفسها يصل fine-grained إلى sparsity مساوية أو أعلى، وعند sparsity نفسها يحتفظ بدقة مساوية أو أعلى. ما يكسبه coarse في المقابل هو السرعة، لا الضغط.
Convolution weights have four dimensions
أوزان الالتفاف لها أربعة أبعاد
Slide 16: a conv layer's weights have shape [co, ci, kh, kw]:
الشريحة 16: أوزان طبقة conv شكلها [co, ci, kh, kw]:
| Symbolالرمز | Meaningالمعنى | Slide 17 valueالقيمة في الشريحة 17 |
|---|---|---|
co | output channels, also called filtersقنوات الإخراج، وتُسمّى أيضاً المرشّحات (filters) | 3 |
ci | input channels (or just "channels")قنوات الإدخال (أو "القنوات" فقط) | 2 |
kh | kernel heightارتفاع النواة | 3 |
kw | kernel widthعرض النواة | 3 |
يعرّف الجدول الأبعاد الأربعة: co قنوات الخرج وتسمى أيضاً filters، وci قنوات الدخل، وkh وkw ارتفاع وعرض kernel. وفي مثال الشريحة 17 القيم هي 3 و2 و3 و3.
Slide 17's toy tensor is drawn as a grid of 3 rows (one per filter) by 2 columns (one per input channel), each cell a 3 × 3 kernel. Total weights: 3 × 2 × 3 × 3 = 54, in 6 kernels of 9. Four dimensions give more choices of what to group into a deletable unit than the 2D matrix did, which is the slide's closing point.
يُرسم tensor المثال في الشريحة 17 كشبكة من 3 صفوف (صف لكل filter) و2 عمود (عمود لكل قناة دخل)، وكل خلية kernel بحجم 3 × 3. مجموع الأوزان: 3 × 2 × 3 × 3 = 54، في 6 kernels كل منها 9. الأبعاد الأربعة تعطي خيارات أكثر مما تعطيه المصفوفة الثنائية لتجميع الأوزان في وحدة قابلة للحذف، وهذه هي النقطة الختامية للشريحة.
The spectrum
الطيف
Slide 18 lines up five granularities on an arrow from irregular to regular:
تصفّ الشريحة 18 خمس درجات من granularity على سهم من غير المنتظم إلى المنتظم:
مُعاد رسمه من الشريحة 18. كل لوحة هي tensor الكامل ذو 54 وزناً: الصفوف filters والأعمدة قنوات دخل، وكل مربع صغير وزن واحد. كلما اتجهت يميناً تكبر وحدة الحذف من وزن واحد إلى قناة كاملة، فتشكّل الأوزان الباقية كتلاً أكثر انتظاماً.
| Levelالمستوى | Unit deletedالوحدة المحذوفة | Weights per unitالأوزان في كل وحدة | In the 54 exampleفي مثال الـ 54 | Speedup storyقصة التسريع |
|---|---|---|---|---|
| Fine-grainedFine-grained (دقيق الحبيبات) | one weightوزن واحد | 1 | 1 | needs sparse hardware (EIE); best compressionيحتاج إلى عتاد للتناثر (EIE)؛ أفضل ضغط |
| Pattern-basedPattern-based (مبني على أنماط) | positions inside a kernel, chosen from a small set of fixed shapes ("like Tetris")مواقع داخل النواة، تُختار من مجموعة صغيرة من الأشكال الثابتة ("مثل Tetris") | variesمتغيّر | e.g. keep 4 of 9مثلاً إبقاء 4 من 9 | regular enough for compiler or hardware support; N:M (2:4) is a pattern of this kindمنتظم بما يكفي لدعم المترجم (compiler) أو العتاد؛ وN:M (2:4) نمط من هذا النوع |
| Vector-levelVector-level (على مستوى المتجه) | a row (or column) inside one kernelصف (أو عمود) داخل نواة واحدة | kw (or kh) | 3 | short dense vectors, partial regularityمتجهات كثيفة قصيرة، انتظام جزئي |
| Kernel-levelKernel-level (على مستوى النواة) | a whole kh × kw kernel, one (co, ci) pairنواة كاملة kh × kw، أي زوج واحد (co, ci) | khkw | 9 | skip whole 2D convolutionsتخطّي عمليات التفاف ثنائية الأبعاد كاملة |
| Channel-levelChannel-level (على مستوى القناة) | a whole input channel (all filters' slice for that ci), or a whole filterقناة إدخال كاملة (شريحة كل المرشّحات لتلك ci)، أو مرشّح كامل | cokhkw or cikhkwcokhkw أو cikhkw | 27 or 1827 أو 18 | layer becomes a smaller dense conv; fast everywhereتصبح الطبقة التفافاً كثيفاً أصغر؛ سريع في كل مكان |
يلخّص الجدول الدرجات الخمس: الوحدة المحذوفة، وعدد أوزانها بشكل عام، وعددها في مثال 54، وقصة التسريع. ما يجب أن تلاحظه: عمود "أوزان لكل وحدة" يكبر من 1 إلى 27 كلما اتجهت نحو المنتظم، والتسريع يتحول من "يحتاج عتاداً خاصاً" إلى "سريع في كل مكان". وفي مستوى القناة انتبه إلى أن حذف قناة دخل يكلّف cokhkw بينما حذف filter يكلّف cikhkw.
On slide 18 the channel-level panel removes the right-hand column, which is input channel 2: every filter loses its slice for that channel. Removing a filter (a row) is the output-channel version. Both are "channel pruning" in the broad sense, and both shrink the layer to a smaller dense conv. A removed filter also removes the matching input channel of the next layer, exactly like neuron pruning removed a row here and a column in the next layer.
في الشريحة 18 تحذف لوحة مستوى القناة العمود الأيمن، أي قناة الدخل الثانية: كل filter يفقد شريحته الخاصة بتلك القناة. أما حذف filter (صف) فهو النسخة الخاصة بقنوات الخرج. كلاهما "channel pruning" بالمعنى الواسع، وكلاهما يصغّر الطبقة إلى conv كثيفة أصغر. وfilter المحذوف يحذف أيضاً قناة الدخل المقابلة في الطبقة التالية، تماماً كما حذف neuron صفاً هنا وعموداً في الطبقة التالية.
Counting it: the 54-weight tensor
العدّ: الموتر ذو 54 وزناً
ثلاثة قطوع لوحدة واحدة على tensor الشريحة 17. الـ kernel خلية واحدة (filter مع قناة دخل)، وقناة الدخل عمود، والـ filter صف. الـ sparsity هي عدد المحذوف مقسوماً على 54.
Tensor [co, ci, kh, kw] = [3, 2, 3, 3], 54 weights. Compute the sparsity after each single cut.
Tensor [co, ci, kh, kw] = [3, 2, 3, 3] فيه 54 وزناً. احسب sparsity بعد كل قطع منفرد.
total = 3 x 2 x 3 x 3 = 54 one weight = 1 1/54 = 1.9 % one vector (row) = k_w = 3 3/54 = 5.6 % one kernel = k_h k_w = 9 9/54 = 16.7 % one filter = c_i k_h k_w = 18 18/54 = 33.3 % -> new shape [2, 2, 3, 3] one input chan. = c_o k_h k_w = 27 27/54 = 50.0 % -> new shape [3, 1, 3, 3]
Slide 18's kernel-level panel removes 2 of the 6 kernels: 2 × 9 = 18 of 54, sparsity 33.3 percent, yet the tensor shape does not change (each surviving filter still has 2 input-channel slots, one of them now empty for some filters). Slide 18's channel-level panel removes one whole input channel: 27 of 54, sparsity 50 percent, and the tensor genuinely becomes [3, 1, 3, 3].
لوحة kernel-level في الشريحة 18 تحذف 2 من 6 kernels: 2 × 9 = 18 من 54، أي sparsity 33.3%، ومع ذلك لا يتغير شكل tensor (كل filter باقٍ ما زال له خانتا قناة دخل، وإحداهما فارغة الآن في بعض filters). أما لوحة channel-level فتحذف قناة دخل كاملة: 27 من 54، أي sparsity 50%، ويصبح tensor فعلاً [3, 1, 3, 3].
Notice the same 33.3 percent sparsity can come from two kernels or from one filter. Only the filter cut changes the shape, so only it gives a dense speedup with no special support.
لاحظ أن sparsity نفسها (33.3%) يمكن أن تأتي من kernel اثنين أو من filter واحد. قطع filter وحده يغيّر الشكل، فهو وحده يعطي تسريعاً كثيفاً بدون دعم خاص.
"Drop a dimension, multiply the rest." The weights removed by one unit is the product of every dimension you did not fix. One filter fixes co, so it costs cikhkw. One input channel fixes ci, so it costs cokhkw. One kernel fixes both channels, so it costs khkw.
"ثبّت بُعداً، واضرب الباقي." عدد الأوزان التي تحذفها وحدة واحدة هو حاصل ضرب كل الأبعاد التي لم تثبّتها. الـ filter الواحد يثبّت co فكلفته cikhkw. وقناة الدخل الواحدة تثبّت ci فكلفتها cokhkw. والـ kernel الواحد يثبّت القناتين فكلفته khkw.
- Filter vs input channel. A filter is an output channel (index co) and holds cikhkw weights. An input channel (index ci) spans every filter and holds cokhkw. In the 54 example that is 18 vs 27; swapping them is the classic error.
Filter مقابل قناة الدخل. الـ filter قناة خرج (الفهرس co) ويحمل cikhkw وزناً. وقناة الدخل (الفهرس ci) تمتد عبر كل filters وتحمل cokhkw. في مثال 54 هذا 18 مقابل 27، والخلط بينهما هو الخطأ الكلاسيكي.
- Coarse = less compression, more speed. Not "coarse is better" or "fine is better". Fine wins on sparsity at a given accuracy; coarse wins on actual latency on ordinary hardware.
Coarse = ضغط أقل وسرعة أكبر. ليس "coarse أفضل" ولا "fine أفضل". Fine يفوز في sparsity عند دقة معيّنة، وcoarse يفوز في latency الفعلية على العتاد العادي.
- Order of the spectrum. Fine-grained, pattern-based, vector-level, kernel-level, channel-level. Pattern-based sits next to fine-grained, not at the regular end.
ترتيب الطيف. fine-grained، ثم pattern-based، ثم vector-level، ثم kernel-level، ثم channel-level. الـ pattern-based يجاور fine-grained، وليس عند الطرف المنتظم.
- Equal sparsity is not equal speed. Two kernels and one filter both give 33.3 percent in the example; only the filter cut shrinks the tensor shape.
Sparsity المتساوية لا تعني سرعة متساوية. kernel اثنان وfilter واحد كلاهما يعطي 33.3% في المثال، لكن قطع filter وحده يصغّر شكل tensor.
Check yourself
اختبر نفسك
A conv weight tensor has shape [co, ci, kh, kw] = [3, 2, 3, 3]. You remove one entire input channel. What is the resulting sparsity?
Tensor أوزان conv شكله [co, ci, kh, kw] = [3, 2, 3, 3]. حذفت قناة دخل كاملة. ما sparsity الناتجة؟
C. One input channel spans all filters: cokhkw = 3 × 3 × 3 = 27 of 54 weights, so 50 percent. B is what removing one filter gives (cikhkw = 18, 18/54). A is one kernel (9/54).
الجواب C. قناة الدخل الواحدة تمتد عبر كل filters: cokhkw = 3 × 3 × 3 = 27 من 54، أي 50%. الخيار B هو ما يعطيه حذف filter واحد (18/54). والخيار A هو kernel واحد (9/54).
Which ordering of slide 18's granularities runs from most irregular to most regular?
أي ترتيب لدرجات granularity في الشريحة 18 يمتد من الأكثر عشوائية إلى الأكثر انتظاماً؟
A. That is the slide's left-to-right order under the Irregular to Regular arrow. C is the same list reversed (regular to irregular). B swaps pattern and vector and also kernel and channel. D puts pattern-based before fine-grained.
الجواب A. هذا هو ترتيب الشريحة من اليسار إلى اليمين تحت سهم Irregular إلى Regular. الخيار C هو القائمة نفسها معكوسة. والخيار B يبدّل pattern مع vector وkernel مع channel. والخيار D يضع pattern-based قبل fine-grained.
Why does slide 15 call coarse-grained pruning "less flexible"?
لماذا تصف الشريحة 15 coarse-grained pruning بأنه "أقل مرونة"؟
D. Any whole-row mask is also a legal element-wise mask, but not the reverse, so coarse searches a smaller space. Consequence: at equal accuracy it reaches equal or lower sparsity. C is backwards: it is fine-grained that needs special hardware; coarse gives "just a smaller matrix". A and B are false.
الجواب D. أي قناع صفوف كاملة هو أيضاً قناع عناصر صالح، والعكس غير صحيح، فـ coarse يبحث في فضاء أصغر. والنتيجة: عند الدقة نفسها يصل إلى sparsity مساوية أو أقل. الخيار C معكوس: fine-grained هو الذي يحتاج عتاداً خاصاً، وcoarse يعطي "مجرد مصفوفة أصغر". والخياران A وB خطأ.
A layer has shape [64, 32, 3, 3]. How many weights does pruning one filter remove?
طبقة شكلها [64, 32, 3, 3]. كم وزناً يُحذف بحذف filter واحد؟
B. A filter is one output channel: cikhkw = 32 × 3 × 3 = 288. C is one input channel (cokhkw = 64 × 9 = 576), the classic swap. A is one kernel. D is co × ci, the number of kernels.
الجواب B. الـ filter قناة خرج واحدة: cikhkw = 32 × 3 × 3 = 288. الخيار C هو قناة دخل واحدة (64 × 9 = 576)، وهو الخلط الكلاسيكي. والخيار A هو kernel واحد. والخيار D هو co × ci أي عدد kernels.
You need a real latency reduction on a stock mobile CPU with no sparse kernels. Which granularity is the safe choice?
تحتاج تقليلاً فعلياً في latency على معالج هاتف عادي بدون sparse kernels. أي granularity هي الخيار الآمن؟
C. Removing channels shrinks the tensor to a smaller dense conv, which any hardware runs faster. A and B leave zeros scattered inside dense-shaped tensors, so without sparse support the zeros are still computed. D is wrong twice: kernel-level does not change the tensor shape, and fine-grained, not kernel-level, reaches the highest sparsity.
الجواب C. حذف القنوات يصغّر tensor إلى conv كثيفة أصغر يشغّلها أي عتاد أسرع. الخياران A وB يتركان أصفاراً مبعثرة داخل tensors بشكلها الكثيف، فبدون دعم للتفرّق تُحسب الأصفار. والخيار D خطأ مرتين: kernel-level لا يغيّر شكل tensor، وfine-grained وليس kernel-level هو الذي يصل إلى أعلى sparsity.