Sparse inputs and sparse convolutionالمدخلات المتناثرة والالتفاف المتناثر

Start with a number. Voxelize an outdoor LiDAR frame into a regular 3D grid and count how many cells hold at least one point. PointAcc (Lin et al., MICRO 2021) reports that outdoor point clouds usually have a density below 0.01 percent, while a conventional CNN takes in a 100 percent dense image. That is the ~0.01% written above the sparse column of the slide. Indoor scans and single objects sit below 1 percent. Even after ReLU, an ImageNet network still keeps about half of its activations nonzero, so an image is up to four orders of magnitude denser than a LiDAR scan.

ابدأ برقم. حوّل إطار LiDAR خارجيًا إلى شبكة 3D منتظمة من الـ voxels، وعُدّ كم خلية تحتوي على نقطة واحدة على الأقل. تذكر PointAcc (Lin et al., MICRO 2021) أن كثافة السحب النقطية الخارجية عادةً أقل من 0.01 percent، بينما تستقبل الـ CNN التقليدية صورة كثيفة بنسبة 100 percent. هذه هي قيمة ~0.01% المكتوبة فوق عمود الـ sparse في الشريحة. أما المسوح الداخلية والأجسام المفردة فكثافتها أقل من 1 percent. وحتى بعد ReLU، تبقي شبكة ImageNet نحو نصف تفعيلاتها غير صفرية، لذلك قد تكون الصورة أكثف من مسح LiDAR بما يصل إلى أربع رتب عشرية (orders of magnitude).

The roadmap places this under activation sparsity, next to EIE and the M:N tensor cores, and that is correct as far as it goes: the zeros are in the data, not the weights. But the source is different in a way that changes everything downstream. ReLU zeros and pruned weight zeros land wherever the arithmetic puts them. Point-cloud zeros are the empty air between surfaces. PointAcc calls this sparsity "fundamentally different" because "the sparsity pattern is constrained by the physical objects in the real world", and draws the consequence that matters here: the nonzero points should never dilate during computation. In the vocabulary of part 07 it is still dynamic, since every frame has a new pattern, but it is a pattern with geometric meaning.

تضع خريطة الطريق هذا الموضوع تحت activation sparsity، بجانب EIE وأنوية الـ tensor من نوع M:N، وهذا صحيح إلى حد ما: الأصفار موجودة في البيانات لا في الأوزان. لكن مصدرها مختلف بطريقة تغيّر كل ما يأتي بعدها. أصفار ReLU وأصفار الأوزان المقلّمة (weight) تقع حيثما تضعها العمليات الحسابية، أما أصفار السحابة النقطية فهي الهواء الفارغ بين الأسطح. تصف PointAcc هذا التناثر بأنه "مختلف جوهريًا" (fundamentally different) لأن "نمط التناثر مقيّد بالأجسام الفيزيائية في العالم الحقيقي"، وتستنتج النتيجة المهمة هنا: يجب ألا تتمدد النقاط غير الصفرية أبدًا أثناء الحساب. وبمصطلحات الجزء 07 يبقى هذا التناثر dynamic، لأن لكل إطار نمطًا جديدًا، لكنه نمط له معنى هندسي.

What a dense convolution does to empty spaceماذا يفعل الالتفاف الكثيف بالفراغ

Now apply an ordinary 3 x 3 convolution to a grid with a single active cell. The kernel window touches that cell from nine different positions, so nine outputs become nonzero. Apply a second layer and the nine become twenty-five. Graham, Engelcke and van der Maaten (CVPR 2018) state the rule in d dimensions: a single active site becomes 3^d active sites after one convolution and 5^d after two. In 3D that is 1, then 27, then 125. They name it the submanifold dilation problem, because a surface (a 2D submanifold in 3D space) thickens into a slab and the sparsity that made the input cheap is gone within a few layers.

الآن طبّق التفافًا عاديًا بحجم 3 x 3 على شبكة فيها خلية نشطة واحدة. نافذة النواة تلمس تلك الخلية من تسعة مواقع مختلفة، لذلك تصبح تسعة مخرجات غير صفرية. طبّق طبقة ثانية فتصبح التسعة خمسًا وعشرين. يصوغ Graham وEngelcke وvan der Maaten (CVPR 2018) القاعدة في d أبعاد: موقع نشط واحد يصبح 3^d مواقع نشطة بعد التفاف واحد، و5^d بعد التفافين. في 3D يعني ذلك 1 ثم 27 ثم 125. ويسمّونها submanifold dilation problem (مشكلة تمدد الـ submanifold)، لأن السطح (وهو submanifold ثنائي الأبعاد داخل فضاء ثلاثي الأبعاد) يتضخم إلى لوح سميك، ويختفي خلال بضع طبقات التناثر الذي جعل المدخل رخيصًا.

The slide shows the same effect on a small grid you can check by eye. The input is 4 rows by 5 columns with four active cells at rows and columns (1, 1), (2, 2), (2, 4) and (3, 3). Each active cell activates every output its 3 x 3 window touches, clipped to the grid: nine for the first two points, six each for the two that sit against an edge. The union of those windows is 17 of 20 cells, exactly the orange region drawn on the conventional side. Only (0, 3), (0, 4) and (3, 0) stay empty, and a second layer would fill those too.

تعرض الشريحة الأثر نفسه على شبكة صغيرة يمكنك التحقق منها بالنظر. المدخل 4 صفوف في 5 أعمدة، وفيه أربع خلايا نشطة عند (الصف، العمود) (1, 1) و(2, 2) و(2, 4) و(3, 3). كل خلية نشطة تنشّط كل مخرج تلمسه نافذتها 3 x 3، مع قصّ ما يخرج عن حدود الشبكة: تسعة لكل من النقطتين الأوليين، وستة لكل من النقطتين الملاصقتين للحافة. اتحاد هذه النوافذ هو 17 خلية من 20، وهي بالضبط المنطقة البرتقالية المرسومة في الجانب التقليدي (conventional). لا يبقى فارغًا إلا (0, 3) و(0, 4) و(3, 0)، وطبقة ثانية ستملؤها أيضًا.

The fix: compute only where an input existsالحل: احسب فقط حيث يوجد مدخل

Sparse convolution, in the submanifold form the deck uses, changes one rule. An output site is computed if and only if the input site at the same coordinate is active. Graham et al. define it exactly that way: the filter size is odd, the input is padded so the output keeps the input's size, and an output is active only when the central site of its receptive field is active. TorchSparse writes the same fact as a set equation, P_in = P_out, against the dense case where P_in is only a subset of P_out. On the slide grid the sparse side stays at four orange cells, and after a hundred layers it would still be four.

الالتفاف المتناثر (Sparse convolution)، بصيغة الـ submanifold التي تستخدمها الشرائح، يغيّر قاعدة واحدة: يُحسب موقع المخرج إذا وفقط إذا كان موقع المدخل عند الإحداثي نفسه نشطًا. هكذا يعرّفه Graham et al. تمامًا: حجم المرشح (filter) فردي، ويُحشى المدخل (padding) بحيث يحافظ المخرج على حجم المدخل، ولا يكون المخرج نشطًا إلا إذا كان الموقع المركزي في مجال استقباله (receptive field) نشطًا. وتكتب TorchSparse الحقيقة نفسها كمعادلة مجموعات، P_in = P_out، مقابل الحالة الكثيفة حيث P_in مجرد مجموعة جزئية من P_out. على شبكة الشريحة يبقى الجانب المتناثر عند أربع خلايا برتقالية، وبعد مئة طبقة سيبقى أربعًا.

The pair of ring images at the bottom of the slide comes from two different figures of the Graham papers. The left ring is Figure 2 of the CVPR 2018 paper (Figure 1 of the 2017 arXiv version): a thin curve pushed through two ordinary 3 x 3 convolutions has smeared into a grey band. The right ring is Figure 3 of the CVPR 2018 paper: the submanifold receptive field centred on one active site, drawn in green, with the empty sites it ignores in red, so the ring stays a ring. That is the whole motivation in one picture: the operator must respect the geometry, or the geometry disappears.

صورتا الحلقة أسفل الشريحة مأخوذتان من شكلين مختلفين في أوراق Graham. الحلقة اليسرى هي الشكل 2 في ورقة CVPR 2018 (الشكل 1 في نسخة arXiv لعام 2017): منحنى رفيع مرّ عبر التفافين عاديين بحجم 3 x 3 فتلطّخ وأصبح شريطًا رماديًا. والحلقة اليمنى هي الشكل 3 في ورقة CVPR 2018: مجال الاستقبال في الـ submanifold متمركزًا على موقع نشط واحد، مرسومًا بالأخضر، والمواقع الفارغة التي يتجاهلها بالأحمر، فتبقى الحلقة حلقة. هذا هو الدافع كله في صورة واحدة: يجب أن يحترم المعامل الهندسة، وإلا اختفت الهندسة.

Why a whole part on one operator? TorchSparse's introduction lists the stakes. All top five segmentation submissions on SemanticKITTI and nine of the top ten on nuScenes are built on sparse convolution, yet the operator is not supported by TensorRT or TVM, and the best library of the day ran MinkowskiNet at 8 FPS on a GTX 1080Ti, a desktop GPU far above anything on an embedded board. The gap between what the algorithm avoids and what the hardware delivers is the research territory of parts 12 and 13.

لماذا جزء كامل لمعامل واحد؟ مقدمة TorchSparse تسرد ما على المحك. كل الحلول الخمسة الأولى في التقسيم الدلالي (segmentation) على SemanticKITTI، وتسعة من العشرة الأولى على nuScenes، مبنية على الالتفاف المتناثر، ومع ذلك لا يدعم TensorRT ولا TVM هذا المعامل، وأفضل مكتبة في وقتها شغّلت MinkowskiNet بسرعة 8 FPS على GTX 1080Ti، وهي GPU مكتبية أقوى بكثير من أي شيء على لوحة مدمجة. الفجوة بين ما تتجنبه الخوارزمية وما يقدمه العتاد هي الميدان البحثي للجزأين 12 و13.

Follow the boxed point P0 at row 1, column 1 through a 3 x 3 convolution. A 3 x 3 kernel is not one weight; it is nine weight matrices, one per tap, each of shape C_in x C_out. TorchSparse writes them as W_δ for each offset δ in {-1, 0, 1}^2. The deck names them W_(dx,dy), with dx the row offset and dy the column offset, and the visual and simulator below use the same labels. Every time P0 lands in an output's window, exactly one of those nine matrices multiplies its feature vector, and which one depends only on where the output sits relative to P0.

تتبّع النقطة المؤطّرة P0 في الصف 1 والعمود 1 عبر التفاف 3 x 3. النواة 3 x 3 ليست وزنًا واحدًا، بل تسع مصفوفات أوزان، واحدة لكل نقرة (tap)، وشكل كل منها C_in x C_out. تكتبها TorchSparse على شكل W_δ لكل إزاحة δ في {-1, 0, 1}^2. وتسميها الشرائح W_(dx,dy)، حيث dx إزاحة الصف وdy إزاحة العمود، والرسم والمحاكي أدناه يستخدمان التسميات نفسها. كلما وقعت P0 داخل نافذة أحد المخرجات، تضرب مصفوفة واحدة فقط من هذه المصفوفات التسع متجه خصائصها (feature vector)، وأيّ مصفوفة منها يعتمد فقط على موقع المخرج بالنسبة إلى P0.

The deck's convention, consistent across all nine slides, is that the input P sits at the output Q shifted by the offset: P = Q + (dx, dy) in (row, column). The first entry on the slide makes it concrete. Output Q0 is the top-left corner of P0's window at (0, 0), so P0 = Q0 + (1, 1) and the weight is W_(1,1). The centre entry, where Q4 is P0's own position, uses W_(0,0). The bottom-right corner at (2, 2) uses W_(-1,-1).

الاصطلاح في الشرائح، وهو ثابت عبر الشرائح التسع كلها، أن المدخل P يقع عند المخرج Q مزاحًا بمقدار الإزاحة: P = Q + (dx, dy) بترتيب (الصف، العمود). المدخل الأول في الشريحة يوضح ذلك. المخرج Q0 هو الزاوية العلوية اليسرى من نافذة P0 عند (0, 0)، لذلك P0 = Q0 + (1, 1) والوزن هو W_(1,1). والمدخل المركزي، حيث Q4 هو موقع P0 نفسه، يستخدم W_(0,0). والزاوية السفلية اليمنى عند (2, 2) تستخدم W_(-1,-1).

The map is the computationالخريطة هي الحساب

Each such relation is one tuple, and the list of all of them is what the slides call the maps, written (In, Out, Wgt). TorchSparse defines the map for a layer as the set M = {(p_j, q_k, W_δ)} and describes the whole layer as one loop: iterate over the map and, for each entry, accumulate the input feature vector times the entry's weight matrix into the output feature vector. That is the update rule printed at the bottom-left of every slide in this run.

كل علاقة من هذا النوع ثلاثية واحدة (tuple)، وقائمتها كاملة هي ما تسميه الشرائح الخرائط (maps)، وتُكتب (In, Out, Wgt). تعرّف TorchSparse خريطة الطبقة بأنها المجموعة M = {(p_j, q_k, W_δ)}، وتصف الطبقة كلها بحلقة واحدة: مرّ على الخريطة، ولكل مدخل اجمع حاصل ضرب متجه خصائص المدخل في مصفوفة وزن ذلك المدخل داخل متجه خصائص المخرج. هذه هي قاعدة التحديث المطبوعة أسفل يسار كل شريحة في هذه السلسلة.

Read the indicator as the map-building test. For each output q_k and each offset δ, look up the coordinate s·q_k + δ. If an input point p_j sits there, the triple (p_j, q_k, W_δ) joins the map; if not, nothing is added and nothing is computed. TorchSparse's Algorithm 1 is exactly this double loop with a hash-table lookup on coordinates. The heading of the slides now reads correctly: a sparse convolution is a sparse set of dense matrix multiply-accumulates, and the sparsity lives entirely in which tuples exist.

اقرأ دالة المؤشر (indicator) على أنها اختبار بناء الخريطة. لكل مخرج q_k ولكل إزاحة δ، ابحث عن الإحداثي s·q_k + δ. إذا كانت هناك نقطة مدخل p_j، ينضم الثلاثي (p_j, q_k, W_δ) إلى الخريطة؛ وإلا فلا يُضاف شيء ولا يُحسب شيء. الخوارزمية 1 في TorchSparse هي بالضبط هذه الحلقة المزدوجة مع بحث في جدول تجزئة (hash table) على الإحداثيات. والآن يصبح عنوان الشرائح مفهومًا: الالتفاف المتناثر مجموعة متناثرة من عمليات ضرب وتجميع مصفوفات كثيفة (dense matrix multiply-accumulates)، والتناثر كله يكمن في أي الثلاثيات موجودة.

Nine entries become twoتسعة مدخلات تصبح اثنين

Now compare the two columns of the slide for P0. The conventional column lists one entry per tap, nine in all, because every cell of P0's window is an output that a dense layer computes. The sparse column applies the submanifold rule from the previous concept: an output must itself be an input position. Inside P0's window only two cells qualify, P0's own position and (2, 2), where P1 sits. So the map keeps exactly two tuples and marks the other seven "No compute".

قارن الآن بين عمودي الشريحة للنقطة P0. العمود التقليدي يسرد مدخلًا لكل نقرة، تسعة في المجموع، لأن كل خلية في نافذة P0 مخرج تحسبه الطبقة الكثيفة. أما العمود المتناثر فيطبق قاعدة الـ submanifold من المفهوم السابق: يجب أن يكون المخرج نفسه موقع مدخل. داخل نافذة P0 تتأهل خليتان فقط: موقع P0 نفسه، و(2, 2) حيث تقع P1. لذلك تحتفظ الخريطة بثلاثيتين بالضبط وتضع على السبع الأخرى علامة "No compute".

Costing the whole grid, not just P0حساب كلفة الشبكة كلها، لا P0 وحدها

The slide follows one point, so extend it to all four. Conventionally each point contributes one entry per in-grid tap: 9 for P0, 9 for the point at (2, 2), 6 for (2, 4) against the right edge and 6 for (3, 3) against the bottom, 30 in total. The submanifold map has one centre entry per point plus one entry for every ordered pair of points within one step of each other. Three such pairs exist, (1, 1) with (2, 2), (2, 2) with (3, 3) and (2, 4) with (3, 3), each counted in both directions, giving 4 + 6 = 10 entries. Each entry is a (1 x C_in)(C_in x C_out) product, so with C_in = C_out = 64 an entry costs 4,096 MACs.

تتتبع الشريحة نقطة واحدة، فلنوسّع ذلك إلى النقاط الأربع. في الطريقة التقليدية تساهم كل نقطة بمدخل لكل نقرة داخل الشبكة: 9 للنقطة P0، و9 للنقطة عند (2, 2)، و6 للنقطة (2, 4) الملاصقة للحافة اليمنى، و6 للنقطة (3, 3) الملاصقة للحافة السفلى، أي 30 في المجموع. أما خريطة الـ submanifold ففيها مدخل مركزي واحد لكل نقطة، إضافة إلى مدخل لكل زوج مرتب من النقاط تفصل بينهما خطوة واحدة. توجد ثلاثة أزواج كهذه: (1, 1) مع (2, 2)، و(2, 2) مع (3, 3)، و(2, 4) مع (3, 3)، وكل زوج يُحسب في الاتجاهين، فيكون المجموع 4 + 6 = 10 مدخلات. كل مدخل حاصل ضرب (1 x C_in)(C_in x C_out)، لذلك مع C_in = C_out = 64 يكلّف المدخل الواحد 4,096 MACs.

Two lessons hide in that table. Zero-skipping alone, the trick EIE relied on, already removes most of the work on this grid, but it still writes the dilated 17-cell output and so the next layer starts from 17 points instead of 4. The submanifold map is the only row whose cost stays proportional to the number of points layer after layer. On a real LiDAR frame with hundreds of thousands of points in a grid of billions of voxels, the fully dense row is not merely slow; it does not fit in memory.

في هذا الجدول درسان. تخطي الأصفار وحده (zero-skipping)، وهي الحيلة التي اعتمد عليها EIE، يزيل بالفعل معظم العمل على هذه الشبكة، لكنه ما زال يكتب مخرجًا متمددًا من 17 خلية، فتبدأ الطبقة التالية من 17 نقطة بدلًا من 4. خريطة الـ submanifold هي الصف الوحيد الذي تبقى كلفته متناسبة مع عدد النقاط طبقة بعد طبقة. وفي إطار LiDAR حقيقي فيه مئات الآلاف من النقاط داخل شبكة من مليارات الـ voxels، لا يكون الصف الكثيف بالكامل بطيئًا فحسب، بل لا يتسع في الذاكرة أصلًا.

Slide 95 closes the P0 story with a count, nine matrix multiplications against two, and slide 96 asks the practical question: how does a GPU run a list of tuples? Take its workload, a 5 x 5 grid with five points P0 at (1, 1), P1 at (2, 2), P2 at (2, 4), P3 at (3, 2) and P4 at (4, 3). Its map has eleven entries, and the box on the slide lists them not in point order but sorted by weight offset. That ordering is the whole idea.

تختم الشريحة 95 قصة P0 بعدد: تسع عمليات ضرب مصفوفات مقابل اثنتين، ثم تطرح الشريحة 96 السؤال العملي: كيف تنفّذ الـ GPU قائمة من الثلاثيات؟ خذ حِمل العمل فيها: شبكة 5 x 5 فيها خمس نقاط، P0 عند (1, 1)، وP1 عند (2, 2)، وP2 عند (2, 4)، وP3 عند (3, 2)، وP4 عند (4, 3). خريطتها فيها أحد عشر مدخلًا، والمربع في الشريحة لا يسردها بترتيب النقاط بل مرتبة حسب إزاحة الوزن. وهذا الترتيب هو الفكرة كلها.

Running the update rule one entry at a time means eleven vector-matrix products, each a single row of C_in values against a C_in x C_out matrix. TorchSparse notes that the utilization of matrix-vector multiplication is rather low on a GPU, whose tensor cores want tall matrices on both sides. The escape is to notice that entries sharing the same offset share the same matrix. Stack their input rows into one contiguous matrix, multiply it by that one W_δ, and you have turned several vector-matrix products into one matrix-matrix product. Grouping by output or by input would not work: entries with the same output use different weights, and so do entries with the same input.

تنفيذ قاعدة التحديث مدخلًا مدخلًا يعني أحد عشر حاصل ضرب متجه في مصفوفة، كل منها صف واحد من C_in قيمة مقابل مصفوفة C_in x C_out. تلاحظ TorchSparse أن نسبة استغلال ضرب المصفوفة في المتجه منخفضة جدًا على الـ GPU، التي تريد أنوية الـ tensor فيها مصفوفات طويلة على الجانبين. والمخرج هو ملاحظة أن المدخلات التي تشترك في الإزاحة نفسها تشترك في المصفوفة نفسها. رصّ صفوف مدخلاتها في مصفوفة واحدة متصلة في الذاكرة، واضربها في تلك الـ W_δ الواحدة، وبذلك تحوّل عدة حواصل ضرب متجه في مصفوفة إلى حاصل ضرب واحد لمصفوفة في مصفوفة. التجميع حسب المخرج أو حسب المدخل لا ينجح: المدخلات التي تشترك في المخرج نفسه تستخدم أوزانًا مختلفة، وكذلك المدخلات التي تشترك في المدخل نفسه.

Five of the nine offsets have entries, so this layer launches five matmuls with 2, 1, 5, 1 and 2 rows. The other four offsets have empty maps and launch nothing. Notice too that P2 at (2, 4) has no neighbour within one step, so it appears only in the W_(0,0) group: an isolated point costs exactly one entry.

خمس من الإزاحات التسع لها مدخلات، لذلك تطلق هذه الطبقة خمس عمليات matmul بعدد صفوف 2 و1 و5 و1 و2. الإزاحات الأربع الأخرى خرائطها فارغة ولا تطلق شيئًا. ولاحظ أيضًا أن P2 عند (2, 4) ليس لها جار على بعد خطوة واحدة، لذلك لا تظهر إلا في مجموعة W_(0,0): النقطة المعزولة تكلّف مدخلًا واحدًا بالضبط.

Gather, matmul, scatterالتجميع، ثم ضرب المصفوفات، ثم التوزيع (gather, matmul, scatter)

The pipeline on slide 96 is the gather, matmul, scatter flow that every existing GPU implementation follows, written out for the highlighted offset W_(-1,-1). Its two entries are (P0, Q1) and (P3, Q4). Gather copies rows P0 and P3 out of the 5 x C_in input feature matrix into a 2 x C_in buffer. Matmul multiplies that buffer by the C_in x C_out weight to produce a 2 x C_out partial sum. Scatter adds row one into output Q1 and row two into Q4, which is the pair of equations under the figure: f1 = f1 + f0 x W_(-1,-1) and f4 = f4 + f3 x W_(-1,-1). Then the next offset takes its turn with its own rows.

خط المعالجة في الشريحة 96 هو تدفق gather, matmul, scatter الذي يتبعه كل تنفيذ موجود على الـ GPU، مكتوبًا للإزاحة المظللة W_(-1,-1). مدخلاها هما (P0, Q1) و(P3, Q4). التجميع (Gather) ينسخ الصفين P0 وP3 من مصفوفة خصائص المدخل 5 x C_in إلى ذاكرة مؤقتة 2 x C_in. ثم يضرب الـ Matmul هذه الذاكرة المؤقتة في مصفوفة الوزن C_in x C_out لينتج مجموعًا جزئيًا 2 x C_out. ثم يضيف التوزيع (Scatter) الصف الأول إلى المخرج Q1 والصف الثاني إلى Q4، وهذا هو زوج المعادلتين تحت الشكل: f1 = f1 + f0 x W_(-1,-1) وf4 = f4 + f3 x W_(-1,-1). ثم تأتي الإزاحة التالية بصفوفها الخاصة.

The slide's heading calls this weight-stationary: the weight matrix for one offset stays put while the gathered rows stream through it, and a separate matmul runs for each different weight. TorchSparse's Algorithm 2 is literally a loop over offsets that performs gather, matmul and scatter for each. The rule book in Graham et al. is the same design described from the sparse-convolution side: for each row (j, k) in the rule for offset i, multiply row j of the input matrix by W^i and add it to row k of the output, which they note runs efficiently on a GPU precisely because it is a matrix-matrix multiply-add. SECOND (Yan et al., 2018) moved the rule generation itself from a CPU hash table to the GPU, since the CPU version was slow and required data transfer between CPU and GPU on every layer.

يسمي عنوان الشريحة هذا الأسلوب weight-stationary: تبقى مصفوفة الوزن الخاصة بإزاحة واحدة ثابتة في مكانها بينما تتدفق عبرها الصفوف المجمّعة، وتُنفَّذ عملية matmul منفصلة لكل وزن مختلف. الخوارزمية 2 في TorchSparse هي حرفيًا حلقة على الإزاحات تنفّذ gather وmatmul وscatter لكل منها. و"كتاب القواعد" (rule book) عند Graham et al. هو التصميم نفسه موصوفًا من جهة الالتفاف المتناثر: لكل صف (j, k) في قاعدة الإزاحة i، اضرب الصف j من مصفوفة المدخل في W^i وأضفه إلى الصف k من المخرج، ويلاحظون أن هذا يعمل بكفاءة على الـ GPU تحديدًا لأنه عملية ضرب وجمع مصفوفة في مصفوفة. ثم نقل SECOND (Yan et al., 2018) توليد القواعد نفسه من جدول تجزئة على الـ CPU إلى الـ GPU، لأن نسخة الـ CPU كانت بطيئة وتتطلب نقل بيانات بين الـ CPU والـ GPU في كل طبقة.

A symmetry you can check on the slideتناظر يمكنك التحقق منه على الشريحة

Look at the row counts again: W_(-1,-1) and W_(1,1) both have two rows, W_(-1,0) and W_(1,0) both have one. That is not luck. If (P, Q, W_δ) is an entry, then P and Q are both points and Q = P + (-δ), so (Q, P, W_(-δ)) is also an entry. TorchSparse section 4.2.1 proves this one-to-one correspondence for any odd kernel at stride 1, and the (0, 0) map is special for a second reason: every point maps to itself, so it needs no gather and no scatter at all. Part 12 builds its first optimization on exactly this pairing, and the simulator above reports the check on every grid you draw.

انظر إلى أعداد الصفوف مرة أخرى: W_(-1,-1) وW_(1,1) لكل منهما صفان، وW_(-1,0) وW_(1,0) لكل منهما صف واحد. هذا ليس مصادفة. إذا كان (P, Q, W_δ) مدخلًا، فإن P وQ كلتاهما نقطتان وQ = P + (-δ)، لذلك يكون (Q, P, W_(-δ)) مدخلًا أيضًا. يثبت القسم 4.2.1 في TorchSparse هذا التقابل واحد لواحد لأي نواة فردية عند stride يساوي 1، وخريطة (0, 0) مميزة لسبب ثانٍ: كل نقطة ترتبط بنفسها، لذلك لا تحتاج أي gather ولا أي scatter على الإطلاق. يبني الجزء 12 أول تحسين له على هذا الاقتران بالضبط، والمحاكي أعلاه يعرض هذا الفحص على كل شبكة ترسمها.

• Entries: for stride 1 with an odd kernel, count(δ) = count(-δ), and the (0, 0) map has exactly one entry per point.المدخلات: عند stride يساوي 1 ونواة فردية، count(δ) = count(-δ)، وخريطة (0, 0) فيها مدخل واحد بالضبط لكل نقطة.
• Matmuls per layer: the number of offsets whose map is non-empty, at most K^D.عدد عمليات الـ matmul في الطبقة: عدد الإزاحات التي خريطتها غير فارغة، وهو على الأكثر K^D.
• MACs per layer: total entries times C_in x C_out, independent of how the entries are grouped. Grouping changes utilization and data movement, never the arithmetic count.عدد الـ MACs في الطبقة: إجمالي المدخلات مضروبًا في C_in x C_out، ولا يعتمد على طريقة تجميع المدخلات. التجميع يغيّر نسبة الاستغلال ونقل البيانات، ولا يغيّر أبدًا عدد العمليات الحسابية.