Pruning granularity: from irregular to regularدقة التقليم (Granularity): من غير المنتظم إلى المنتظم

Take a weight matrix with eight rows and eight columns, 64 weights in all, and decide to remove 24 of them. One way is to cross out rows 3, 4 and 7 completely. Another is to cross out 24 individual entries wherever the magnitude criterion of part 05 says they matter least. Both leave 40 weights and both reach a Sparsity of 24 / 64 = 37.5%. Everything else about them is different.

خذ مصفوفة أوزان من ثمانية صفوف وثمانية أعمدة، أي 64 وزنًا في المجموع، وقرّر حذف 24 منها. إحدى الطرق أن تشطب الصفوف 3 و4 و7 بالكامل. وطريقة أخرى أن تشطب 24 عنصرًا منفردًا أينما قال معيار المقدار (magnitude) في الجزء 05 إنها الأقل أهمية. كلتا الطريقتين تُبقي 40 وزنًا وكلتاهما تبلغ نسبة تفرّغ (sparsity) قدرها 24 / 64 = 37.5%. وكل ما عدا ذلك مختلف بينهما.

The unit you delete is the Pruning granularity. Deleting single weights is fine-grained, or unstructured, pruning. Deleting whole rows, columns, kernels or channels is coarse-grained, or structured, pruning. Two consequences pull in opposite directions as the unit grows. The number of masks you may choose from falls, which costs accuracy at a given Pruning ratio. The regularity of what survives rises, which is what lets ordinary hardware run the pruned layer faster.

الوحدة التي تحذفها هي دقة التقليم (pruning granularity). حذف أوزان منفردة هو التقليم الدقيق أو غير المنظَّم (fine-grained / unstructured pruning). وحذف صفوف أو أعمدة أو أنوية (kernels) أو قنوات كاملة هو التقليم الخشن أو المنظَّم (coarse-grained / structured pruning). كلما كبرت الوحدة ظهرت نتيجتان تشدّان في اتجاهين متعاكسين. عدد الأقنعة التي يمكنك الاختيار منها يقلّ، وهذا يكلّف دقة عند نسبة تقليم (pruning ratio) معيّنة. وانتظام ما يبقى يزداد، وهذا ما يسمح للعتاد العادي بتشغيل الطبقة المقلَّمة أسرع.

Counting the choicesعدّ الخيارات

The slide calls fine-grained pruning "more flexible" and coarse-grained pruning "a subset of the fine-grained case". Both statements can be made exact by counting masks. A mask is the set of positions you zero, and the pruning problem of part 01 searches over masks for the one with the lowest loss.

تصف الشريحة التقليم الدقيق بأنه "أكثر مرونة" والتقليم الخشن بأنه "مجموعة جزئية من حالة التقليم الدقيق". يمكن جعل العبارتين دقيقتين بعدّ الأقنعة. القناع (mask) هو مجموعة المواضع التي تصفّرها، ومسألة التقليم (pruning) في الجزء 01 تبحث بين الأقنعة عن القناع ذي أقل خسارة (loss).

Why irregular means hard to accelerateلماذا يعني عدم الانتظام صعوبة التسريع

Multiply a vector by the 5 x 8 survivor and nothing special happens. It is just a smaller dense matrix, and every BLAS routine, every tensor core and every microcontroller loop handles it at full speed. That is the slide's "easy to accelerate (just a smaller matrix!)". Now multiply by the 8 x 8 matrix with 24 holes. A dense routine still performs all 64 multiplies, 24 of them by zero, and gains nothing. To gain, you must store the 40 surviving values together with their positions, in a compressed sparse format, and let the hardware skip the zeros one by one. Mao et al. draw the same line: fine-grained sparsity scatters the tensor into isolated weights and needs custom accelerators such as EIE or SCNN to exploit it, while filter and channel sparsity is simple to accelerate on general-purpose processors because it "is equivalent to obtaining a smaller dense model" (Mao et al., 2017, section 2).

اضرب متجهًا في المصفوفة الباقية 5 x 8 ولن يحدث شيء خاص. إنها ببساطة مصفوفة كثيفة أصغر، وكل دالة BLAS وكل tensor core وكل حلقة على متحكم دقيق تعالجها بالسرعة الكاملة. هذا ما تعنيه الشريحة بعبارة "سهل التسريع (مجرد مصفوفة أصغر!)". الآن اضرب في المصفوفة 8 x 8 التي فيها 24 ثقبًا. الدالة الكثيفة ما زالت تنفّذ عمليات الضرب الـ64 كلها، منها 24 ضربًا في صفر، ولا تكسب شيئًا. لكي تكسب، يجب أن تخزّن القيم الـ40 الباقية مع مواضعها في صيغة متفرّغة مضغوطة (compressed sparse format)، وأن تدع العتاد يتخطى الأصفار واحدًا واحدًا. يرسم Mao et al. الخط نفسه: التفرّغ الدقيق يبعثر الموتّر إلى أوزان معزولة ويحتاج إلى مسرّعات مخصّصة مثل EIE أو SCNN للاستفادة منه، بينما تفرّغ المرشّحات والقنوات سهل التسريع على المعالجات العامة لأنه "يكافئ الحصول على نموذج كثيف أصغر" (Mao et al., 2017، القسم 2).

The gap is measurable. Wen et al. trained AlexNet with structured sparsity and reported average layer-wise speedups of the convolutional layers of 5.1x on CPU and 3.1x on GPU with off-the-shelf libraries, against 3.0x and 0.9x for non-structured l1 sparsity (Wen et al., 2016, Table 4). The fine-grained model had more zeros. The structured model ran faster.

الفجوة قابلة للقياس. درّب Wen et al. شبكة AlexNet بتفرّغ منظَّم وأبلغوا عن متوسط تسريع لكل طبقة في الطبقات الالتفافية قدره 5.1x على الـCPU و3.1x على الـGPU باستخدام مكتبات جاهزة، مقابل 3.0x و0.9x للتفرّغ غير المنظَّم بـl1 (Wen et al., 2016، الجدول 4). النموذج الدقيق كان فيه أصفار أكثر، لكن النموذج المنظَّم كان أسرع.

What the accuracy price looks likeكيف يبدو ثمن الدقة

Because coarse units search a smaller space, they lose a little accuracy at the same density (the fraction of weights kept). Mao et al. measured this on ImageNet with the same pipeline at every granularity. The differences are small between fine and vector grains and grow as the grain reaches whole kernels; pruning entire filters "loses nearly 1% validation accuracy at the very first pruning stage" on AlexNet (Mao et al., 2017).

لأن الوحدات الخشنة تبحث في فضاء أصغر، فإنها تخسر قليلًا من الدقة عند الكثافة نفسها (density، أي نسبة الأوزان المُبقاة). قاس Mao et al. ذلك على ImageNet بخط المعالجة نفسه عند كل مستوى دقة. الفروق صغيرة بين المستوى الدقيق ومستوى المتجهات وتكبر حين تصل الوحدة إلى أنوية كاملة؛ وتقليم مرشّحات كاملة "يخسر قرابة 1% من دقة التحقق في أول مرحلة تقليم" على AlexNet (Mao et al., 2017).

A linear layer's weight is a matrix, so its only structured units are rows and columns. A convolution weight is richer. Slide 17 draws one: three rows of kernels stacked vertically, two columns of kernels side by side, and each kernel a 3 x 3 grid. Count the cells and you get 3 x 2 x 3 x 3 = 54 weights.

وزن الطبقة الخطية مصفوفة، لذلك وحداته المنظَّمة الوحيدة هي الصفوف والأعمدة. أما وزن الالتفاف فأغنى. ترسم الشريحة 17 واحدًا منه: ثلاثة صفوف من الأنوية مكدّسة عموديًا، وعمودان من الأنوية متجاوران، وكل نواة شبكة 3 x 3. عُدّ الخلايا تحصل على 3 x 2 x 3 x 3 = 54 وزنًا.

Those four factors are the four dimensions of a convolution weight. The tensor has shape [c_o, c_i, k_h, k_w]: c_o output channels, also called filters; c_i input channels; and a kernel of height k_h and width k_w. Goodfellow, Bengio and Courville write the same object as a 4-D kernel tensor K whose element K[i, j, k, l] is the connection strength between output channel i and input channel j at a row offset of k and a column offset of l (Goodfellow et al., 2016, section 9.5). PyTorch stores Conv2d.weight with exactly the slide's ordering, (out_channels, in_channels / groups, kernel_size[0], kernel_size[1]) (PyTorch documentation).

هذه العوامل الأربعة هي الأبعاد الأربعة لوزن الالتفاف (dimensions of a convolution weight). شكل الموتّر [c_o, c_i, k_h, k_w]: c_o قنوات الإخراج، وتسمّى أيضًا المرشّحات (filters)؛ وc_i قنوات الإدخال؛ ونواة ارتفاعها k_h وعرضها k_w. يكتب Goodfellow وBengio وCourville الشيء نفسه على أنه موتّر نواة رباعي الأبعاد (4-D) اسمه K، عنصره K[i, j, k, l] هو قوة الاتصال بين قناة الإخراج i وقناة الإدخال j عند إزاحة صف قدرها k وإزاحة عمود قدرها l (Goodfellow et al., 2016، القسم 9.5). ويخزّن PyTorch Conv2d.weight بترتيب الشريحة نفسه تمامًا، (out_channels, in_channels / groups, kernel_size[0], kernel_size[1]) (توثيق PyTorch).

Slicing the tensor into unitsتقطيع الموتّر إلى وحدات

The reason the lecture stops to name the dimensions is that each way of slicing the tensor is a candidate pruning unit. Mao et al. name the slices with array notation, and reading them that way makes the counts automatic. Fix the output channel and you have a filter, a 3-D slab. Fix the output and input channel and you have one kernel, a 2-D grid. Fix a row inside that kernel and you have a 1-D vector. Fix everything and you have a single scalar weight (Mao et al., 2017, section 3.2).

السبب الذي يجعل المحاضرة تتوقف لتسمية الأبعاد هو أن كل طريقة لتقطيع الموتّر هي وحدة تقليم مرشّحة. يسمّي Mao et al. الشرائح بترميز المصفوفات، وقراءتها بهذه الطريقة تجعل العدّ تلقائيًا. ثبّت قناة الإخراج تحصل على مرشّح، وهو لوح ثلاثي الأبعاد (3-D). ثبّت قناتَي الإخراج والإدخال تحصل على نواة واحدة، وهي شبكة ثنائية الأبعاد (2-D). ثبّت صفًا داخل تلك النواة تحصل على متجه أحادي البعد (1-D). ثبّت كل شيء تحصل على وزن عددي واحد (Mao et al., 2017، القسم 3.2).

Two formulas do all the work. A filter holds c_i · k_h · k_w weights, because it has one kernel per input channel. An input channel holds c_o · k_h · k_w weights, because every filter has a kernel that reads it. In the slide these are 18 and 27, and it is easy to mix them up, so picture the grid: a filter is a row of kernels, an input channel is a column of kernels.

صيغتان تؤديان كل العمل. المرشّح يحوي c_i · k_h · k_w وزنًا، لأن فيه نواة واحدة لكل قناة إدخال. وقناة الإدخال تحوي c_o · k_h · k_w وزنًا، لأن كل مرشّح فيه نواة تقرأها. في الشريحة تساويان 18 و27، ومن السهل الخلط بينهما، لذلك تخيّل الشبكة: المرشّح صف من الأنوية، وقناة الإدخال عمود من الأنوية.

The same counts at a realistic scaleالعدّ نفسه على مقياس واقعي

Slide 17 is a toy so the picture fits. A VGG-style layer with 64 input and 64 output channels and 3 x 3 kernels has 64 x 64 x 9 = 36,864 weights, and the same slicing rules apply.

الشريحة 17 مثال مصغّر لكي تتسع الصورة. طبقة على نمط VGG فيها 64 قناة إدخال و64 قناة إخراج وأنوية 3 x 3 تحوي 64 x 64 x 9 = 36,864 وزنًا، وقواعد التقطيع نفسها تنطبق.

Removing a whole filter has a second effect that Li et al. spell out. The filter's output feature map disappears, so the next layer no longer receives that channel, and the corresponding kernels in the next layer's weight tensor disappear too. Pruning m of the n filters of a layer removes m / n of the compute in that layer and in the one after it (Li et al., 2017).

لحذف مرشّح كامل (filter pruning) أثر ثانٍ يوضّحه Li et al.. خريطة الخصائص (feature map) التي يخرجها المرشّح تختفي، فلا تعود الطبقة التالية تستقبل تلك القناة، وتختفي أيضًا الأنوية المقابلة لها في موتّر أوزان الطبقة التالية. تقليم m من المرشّحات الـn في طبقة يحذف m / n من الحساب في تلك الطبقة وفي التي تليها (Li et al., 2017).

Put the two previous ideas together and the lecture's central figure appears. Slide 18 takes the same 54-weight tensor and prunes it five times, once per unit, arranging the results on an axis from irregular to regular. Read from left to right, the holes grow from single cells, to fixed shapes inside kernels, to whole rows, to whole kernels, to an entire column of kernels.

اجمع الفكرتين السابقتين يظهر الشكل المركزي في المحاضرة. تأخذ الشريحة 18 الموتّر نفسه ذا الـ54 وزنًا وتقلّمه خمس مرات، مرة لكل وحدة، وترتّب النتائج على محور من غير المنتظم إلى المنتظم. اقرأ من اليسار إلى اليمين: تكبر الثقوب من خلايا منفردة، إلى أشكال ثابتة داخل الأنوية، إلى صفوف كاملة، إلى أنوية كاملة، إلى عمود كامل من الأنوية.

Every panel can be counted, and counting them shows something the picture hides: every panel removes between a third and two thirds of the weights, so the real difference between them is not how much Sparsity they reach but how the zeros are arranged. The fine-grained panel keeps 23 scattered weights. The pattern-based panel keeps exactly four cells in every kernel, and each kept shape is a Tetris piece (a T or an L of four cells). The vector-level panel keeps seven of the eighteen kernel rows. The kernel-level panel drops the first filter's right kernel and the second filter's left kernel. The channel-level panel drops the whole second input channel across all three filters, and what survives is a dense [3, 1, 3, 3] tensor.

كل لوحة يمكن عدّها، والعدّ يكشف شيئًا تخفيه الصورة: كل لوحة تحذف ما بين ثلث الأوزان وثلثيها، لذلك الفرق الحقيقي بينها ليس مقدار نسبة التفرّغ (sparsity) التي تبلغها بل طريقة ترتيب الأصفار. لوحة التقليم الدقيق (fine-grained) تُبقي 23 وزنًا متناثرًا. لوحة التقليم بالأنماط (pattern-based) تُبقي أربع خلايا بالضبط في كل نواة، وكل شكل مُبقى قطعة Tetris (حرف T أو L من أربع خلايا). لوحة مستوى المتجهات (vector-level) تُبقي سبعة من صفوف الأنوية الثمانية عشر. لوحة مستوى النواة (kernel-level) تُسقط النواة اليمنى للمرشّح الأول والنواة اليسرى للمرشّح الثاني. لوحة مستوى القناة (channel-level) تُسقط قناة الإدخال الثانية كاملة عبر المرشّحات الثلاثة، وما يبقى موتّر كثيف [3, 1, 3, 3].

The ladder, rung by rungالسلّم درجةً درجة

Mao et al. organise four grains (fine, vector, kernel, filter) by how many dimensions each unit spans. The slide keeps their order, inserts pattern-based pruning between fine-grained and vector-level, and shows the 3-D rung as an input channel instead of Mao's filter (Mao et al., 2017, section 3.2). At the bottom, fine-grained pruning removes 0-D scalars anywhere. Pattern-based pruning keeps a small catalogue of fixed shapes inside each kernel, which the slide calls "like Tetris": the hardware knows the finite set of masks in advance instead of facing arbitrary holes. Niu et al. describe it as "fine-grained pruning patterns inside the coarse-grained structures" and, by compiling specialised code per pattern, ran networks on mobile CPUs and GPUs up to 44.5x faster than TensorFlow Lite and up to 11.4x faster than TVM with no accuracy loss (Niu et al., 2020). Vector-level pruning removes 1-D rows, W[o, i, r, :], of a kernel. Kernel-level pruning removes 2-D kernels, W[o, i, :, :]. At the top, channel pruning removes a 3-D slab: on the slide, an input channel W[:, i, :, :] across every filter.

يرتّب Mao et al. أربعة مستويات (الدقيق، والمتجه، والنواة، والمرشّح) بحسب عدد الأبعاد التي تمتد عليها كل وحدة. تحافظ الشريحة على ترتيبهم، وتُدخل التقليم بالأنماط (pattern-based) بين المستوى الدقيق ومستوى المتجه، وتعرض الدرجة ثلاثية الأبعاد (3-D) على أنها قناة إدخال بدلًا من المرشّح عند Mao (Mao et al., 2017، القسم 3.2). في الأسفل، يحذف التقليم الدقيق قيمًا عددية 0-D في أي مكان. التقليم بالأنماط يحتفظ بفهرس صغير من الأشكال الثابتة داخل كل نواة، وتصفه الشريحة بأنه "مثل Tetris": يعرف العتاد مسبقًا المجموعة المحدودة من الأقنعة بدلًا من مواجهة ثقوب عشوائية. يصفه Niu et al. بأنه "أنماط تقليم دقيقة داخل البنى الخشنة"، وبتوليد شيفرة مخصّصة لكل نمط شغّلوا الشبكات على معالجات CPU وGPU في الهواتف أسرع بما يصل إلى 44.5x من TensorFlow Lite وبما يصل إلى 11.4x من TVM دون أي خسارة في الدقة (Niu et al., 2020). تقليم مستوى المتجه يحذف صفوفًا أحادية البعد (1-D) من النواة، W[o, i, r, :]. وتقليم مستوى النواة يحذف أنوية ثنائية الأبعاد (2-D)، W[o, i, :, :]. وفي الأعلى، يحذف تقليم القنوات لوحًا ثلاثي الأبعاد (3-D): في الشريحة هو قناة إدخال W[:, i, :, :] عبر كل المرشّحات.

The right-hand column is the practical half of the story. Only the channel and filter rungs run faster on unmodified dense libraries, because the tensor simply shrinks. Kernel and vector sparsity line up with 2-D and 1-D convolution primitives (Winograd, Eyeriss-style 1-D units), which makes custom hardware simpler, but Mao et al. note they are still hard to accelerate on general-purpose processors. Pattern-based pruning needs compiler support (PatDNN) or dedicated support such as NVIDIA's 2:4 sparse tensor cores, and fine-grained sparsity needs accelerators such as EIE (Mao et al., 2017, section 6).

العمود الأيمن هو النصف العملي من القصة. درجتا القناة والمرشّح فقط تعملان أسرع على المكتبات الكثيفة دون تعديل، لأن الموتّر يصغر ببساطة. تفرّغ النواة وتفرّغ المتجه يتوافقان مع عمليات الالتفاف الأساسية 2-D و1-D (Winograd، ووحدات 1-D على نمط Eyeriss)، وهذا يبسّط العتاد المخصّص، لكن Mao et al. يلاحظون أنهما ما زالا صعبَي التسريع على المعالجات العامة. التقليم بالأنماط يحتاج إلى دعم من المترجم (PatDNN) أو دعم مخصّص مثل نوى الموتّرات المتفرّغة (sparse tensor cores) بنمط 2:4 من NVIDIA، والتفرّغ الدقيق يحتاج إلى مسرّعات مثل EIE (Mao et al., 2017، القسم 6).

Try every rung on one tensorجرّب كل درجة على موتّر واحد

The simulator below holds a random [3, 2, 3, 3] tensor and lets you prune it with any of the six units, including the filter unit that Mao et al. list alongside channels. It groups the weights by the chosen unit, scores each group with the L1 or L2 magnitude that part 05 develops, zeros the weakest groups until the target is met, and reports what survives. Watch three things as you switch units: the achieved sparsity snaps to coarser steps, the index count collapses as units grow, and only the channel and filter units ever produce a smaller dense tensor.

المحاكي أدناه يحمل موتّرًا عشوائيًا [3, 2, 3, 3] ويسمح لك بتقليمه بأي من الوحدات الست، ومنها وحدة المرشّح التي يذكرها Mao et al. إلى جانب القنوات. يجمّع الأوزان بحسب الوحدة المختارة، ويقيّم كل مجموعة بمقدار L1 أو L2 الذي يطوّره الجزء 05، ويصفّر المجموعات الأضعف حتى يبلغ الهدف، ثم يعرض ما يبقى. راقب ثلاثة أشياء وأنت تبدّل الوحدات: نسبة التفرّغ المحقّقة تقفز بخطوات أخشن، وعدد الفهارس ينهار كلما كبرت الوحدات، ووحدتا القناة والمرشّح وحدهما تنتجان موتّرًا كثيفًا أصغر.

The energy argument from part 01 also runs along this axis. Mao et al. simulated the SCNN sparse accelerator on VGG-16 and found that, at the same density, vector-level sparsity needs 30 to 35% fewer output memory references than fine-grained sparsity. Neighbouring surviving weights in a row write to the same output address, so SCNN can skip the repeated read and write of that address (Mao et al., 2017, section 6 and Table 4). Since a DRAM access costs about two hundred times a multiply, fewer memory references is where the energy goes, not fewer multiplies.

حجة الطاقة من الجزء 01 تسري أيضًا على هذا المحور. حاكى Mao et al. المسرّع المتفرّغ SCNN على VGG-16 ووجدوا أنه عند الكثافة نفسها يحتاج تفرّغ مستوى المتجه إلى مراجع ذاكرة للمخرجات أقل بنسبة 30 إلى 35% من التفرّغ الدقيق. الأوزان الباقية المتجاورة في صف واحد تكتب إلى عنوان المخرج نفسه، فيستطيع SCNN تخطّي القراءة والكتابة المكررة لذلك العنوان (Mao et al., 2017، القسم 6 والجدول 4). وبما أن الوصول إلى DRAM يكلّف نحو مئتي ضعف عملية الضرب، فإن تقليل مراجع الذاكرة هو حيث تذهب الطاقة، لا تقليل عمليات الضرب.