TorchSparse: regular computation from irregular sparsityTorchSparse: حساب منتظم من تناثر غير منتظم

Keep the small example from part 11 in view. Five input points P0 to P4, five output points Q0 to Q4, a 3 x 3 kernel, so nine weight offsets from W(-1,-1) to W(1,1). The map for this layer has eleven tuples. Two of them belong to W(-1,-1), one to W(-1,0), five to W(0,0), one to W(1,0), two to W(1,1), and the other four offsets have no entry at all in this tiny cloud.

أبقِ المثال الصغير من الجزء 11 أمام عينيك. خمس نقاط إدخال من P0 إلى P4، وخمس نقاط إخراج من Q0 إلى Q4، وkernel بحجم 3 x 3، أي تسع إزاحات وزن من W(-1,-1) إلى W(1,1). الـ map لهذه الطبقة فيه أحد عشر ثلاثيًا (tuple). اثنان منها يخصّان W(-1,-1)، وواحد يخصّ W(-1,0)، وخمسة تخصّ W(0,0)، وواحد يخصّ W(1,0)، واثنان يخصّان W(1,1)، أما الإزاحات الأربع الباقية فليس لها أي مدخل إطلاقًا في هذه السحابة الصغيرة.

The existing GPU implementation walks that list one weight at a time. It is weight-stationary: pick an offset, hold its C_in x C_out matrix still, and stream every map entry for that offset through it. Take W(-1,0). Its only entry is (P1, Q3), so the engine copies the single feature row f1 into a buffer of shape 1 x C_in, multiplies it by W(-1,0) to get one partial sum of shape 1 x C_out, and adds that row into Q3. Now take W(0,0). With stride 1 every input point sits on top of its own output, so the centre map contains all five entries. The buffer is the whole 5 x C_in input, the matmul is full height, and five partial sums land one to one in Q0 to Q4. Then W(1,0) with only (P3, Q1), then W(1,1) with (P1, Q0) and (P4, Q3), a 2 x C_in buffer whose two results go to two different output rows.

يمرّ التنفيذ الحالي على الـ GPU على هذه القائمة وزنًا واحدًا في كل مرة. إنه weight-stationary (الوزن ثابت): اختر إزاحة، وثبّت مصفوفتها ذات الأبعاد C_in x C_out، ومرّر عبرها كل مدخلات الـ map الخاصة بهذه الإزاحة. خذ W(-1,0). مدخلها الوحيد هو (P1, Q3)، لذلك ينسخ المحرك صف الخصائص الوحيد f1 إلى buffer أبعاده 1 x C_in، ويضربه في W(-1,0) ليحصل على مجموع جزئي واحد أبعاده 1 x C_out، ثم يضيف هذا الصف إلى Q3. الآن خذ W(0,0). مع stride 1 تقع كل نقطة إدخال فوق نقطة الإخراج الخاصة بها، لذلك يحتوي الـ map المركزي على المدخلات الخمسة كلها. الـ buffer هو الإدخال الكامل 5 x C_in، وعملية الـ matmul بكامل الارتفاع، وتصل خمسة مجاميع جزئية واحدًا لواحد إلى Q0 حتى Q4. ثم W(1,0) ومعها (P3, Q1) فقط، ثم W(1,1) ومعها (P1, Q0) و(P4, Q3)، أي buffer أبعاده 2 x C_in تذهب نتيجتاه إلى صفّي إخراج مختلفين.

That is the whole rule, and it is the same three phases every time. The names are the ones the lecture and the paper use: gather, matmul, scatter. For each weight offset delta, gather the |M_delta| input rows named by the map into a contiguous buffer, run one dense matrix multiplication of the |M_delta| x C_in buffer by the C_in x C_out weight, and scatter-accumulate the |M_delta| x C_out partial sums into the output rows named by the map. Written as an update rule over the whole map:

هذه هي القاعدة كاملة، وهي المراحل الثلاث نفسها في كل مرة. الأسماء هي التي تستخدمها المحاضرة والورقة: gather, matmul, scatter. لكل إزاحة وزن delta، اجمع (gather) صفوف الإدخال الـ |M_delta| التي يسمّيها الـ map في buffer متصل، ونفّذ عملية ضرب مصفوفات كثيفة واحدة للـ buffer ذي الأبعاد |M_delta| x C_in في الوزن ذي الأبعاد C_in x C_out، ثم وزّع مع التجميع (scatter-accumulate) المجاميع الجزئية ذات الأبعاد |M_delta| x C_out على صفوف الإخراج التي يسمّيها الـ map. وبصيغة قاعدة تحديث على الـ map كله:

In three dimensions the loop is longer. A 3 x 3 x 3 kernel has 27 offsets, and slide 105 notes that the centre (0,0,0) is usually computed separately because, at stride 1, its map is simply the identity over all points, leaving 26 irregular offsets. Because point-cloud occupancy is dynamic sparsity, the maps are built at run time for every scan, so the engine cannot precompute a fixed schedule the way it could for pruned weights.

في الأبعاد الثلاثة تكون الحلقة أطول. الـ kernel بحجم 3 x 3 x 3 له 27 إزاحة، وتشير الشريحة 105 إلى أن المركز (0,0,0) يُحسب عادة بشكل منفصل لأن الـ map الخاص به عند stride 1 هو ببساطة التطابق (identity) على كل النقاط، فيبقى 26 إزاحة غير منتظمة. ولأن إشغال سحابة النقاط هو dynamic sparsity (تناثر ديناميكي)، تُبنى الـ maps وقت التشغيل لكل مسحة، فلا يستطيع المحرك أن يحسب مسبقًا جدولًا ثابتًا كما كان يمكنه مع الأوزان المقلّمة.

Why this wastes most of the GPUلماذا يهدر هذا معظم قدرة الـ GPU

The baseline is correct and simple, and Tang et al. measured exactly where it loses. Two bottlenecks share the blame. First, the matmuls are non-uniform. The paper reports that map sizes for different weights can differ by an order of magnitude and that most map sizes are small, so each launch is a short, narrow matrix that cannot fill the device: MinkUNet 0.5x on an RTX 2080 Ti in FP16 reaches 8.1 TFLOP/s, only about 30 percent device utilization, with the matmul phase taking 20 to 50 percent of runtime (Tang et al., MLSys 2022, section 3). NVIDIA's own cuBLAS guidance says the same thing from the other side: when the matrices are small, the small matrix size prevents the GPU from being fully utilized, and launching them one after another produces many kernels launched in sequence (NVIDIA Developer Blog).

خط الأساس صحيح وبسيط، وقد قاس Tang et al. بدقة أين يخسر. يتقاسم اللوم عنقا زجاجة. الأول أن عمليات الـ matmul غير متجانسة. تذكر الورقة أن أحجام الـ maps للأوزان المختلفة قد تختلف بمرتبة عشرية كاملة وأن معظمها صغير، فيصبح كل تشغيل مصفوفة قصيرة وضيقة لا تستطيع ملء الجهاز: MinkUNet 0.5x على RTX 2080 Ti بدقة FP16 يصل إلى 8.1 TFLOP/s، أي نحو 30% فقط من استغلال الجهاز، بينما تستهلك مرحلة الـ matmul من 20% إلى 50% من زمن التشغيل (Tang et al., MLSys 2022، القسم 3). وإرشادات cuBLAS من NVIDIA نفسها تقول الشيء ذاته من الجهة الأخرى: عندما تكون المصفوفات صغيرة فإن صغر حجمها يمنع الاستغلال الكامل للـ GPU، وتشغيلها واحدة تلو الأخرى ينتج عددًا كبيرًا من الـ kernels المُطلقة بالتتابع (NVIDIA Developer Blog).

Second, and larger, gather and scatter are memory-bound. Each one is a random access pattern over the feature tensor, bottlenecked by GPU memory bandwidth rather than by computation resources, and together they take 40 to 50 percent of runtime. Worse, because every offset gathers and scatters on its own, the data movement is completely separated from one offset to the next: a row like f1 that appears in the maps of W(-1,0), W(0,0) and W(1,1) is fetched three times from off-chip memory with nothing reused (Tang et al., MLSys 2022, section 3).

الثاني، وهو الأكبر، أن مرحلتي gather وscatter محدودتان بالذاكرة (memory-bound). كل منهما نمط وصول عشوائي على مصفوفة الخصائص، عنق الزجاجة فيه عرض نطاق ذاكرة الـ GPU لا موارد الحساب، ومعًا تستهلكان من 40% إلى 50% من زمن التشغيل. والأسوأ أنه لأن كل إزاحة تنفّذ gather وscatter وحدها، فإن نقل البيانات منفصل تمامًا من إزاحة إلى التي تليها: صف مثل f1 يظهر في الـ maps الخاصة بـ W(-1,0) وW(0,0) وW(1,1) يُجلب ثلاث مرات من الذاكرة خارج الشريحة دون أي إعادة استخدام (Tang et al., MLSys 2022، القسم 3).

Look at the same five features one more time, now the way TorchSparse runs them. The gather step still builds one buffer per offset, but adaptive grouping pads those buffers to a shared height, so the four small offsets become four buffers of exactly two rows each: {F0, F3} for W(-1,-1), {F1, pad} for W(-1,0), {F3, pad} for W(1,0) and {F1, F4} for W(1,1). Two of those rows are dashed: a pad, a row of zeros inserted so that every buffer has the same height. Because the four buffers now share a shape, one batched matrix multiplication (bmm, batch 4) runs all four at once. The centre weight W(0,0), whose buffer holds all five rows, runs as an ordinary matrix multiplication (mm). Partial sums PSUM 0 to PSUM 4 are scattered back with the same locality-aware access, and the two pad rows produce two blank partial-sum slots that nobody reads.

انظر إلى الخصائص الخمس نفسها مرة أخرى، لكن هذه المرة بالطريقة التي يشغّلها بها TorchSparse. ما زالت خطوة الـ gather تبني buffer واحدًا لكل إزاحة، لكن التجميع التكيفي يحشو هذه الـ buffers إلى ارتفاع مشترك، فتصبح الإزاحات الأربع الصغيرة أربعة buffers في كل منها صفّان بالضبط: {F0, F3} لـ W(-1,-1)، و{F1, pad} لـ W(-1,0)، و{F3, pad} لـ W(1,0)، و{F1, F4} لـ W(1,1). صفّان من هذه الصفوف مرسومان بخط متقطع: إنهما حشو (pad)، أي صف من الأصفار يُدرج كي يصبح لكل buffer الارتفاع نفسه. ولأن الـ buffers الأربعة صارت بالشكل نفسه، تشغّلها عملية ضرب مصفوفات مجمّعة واحدة (bmm، batch 4) دفعة واحدة. أما الوزن المركزي W(0,0)، الذي يحمل الـ buffer الخاص به الصفوف الخمسة كلها، فيعمل كعملية ضرب مصفوفات عادية (mm). تُوزَّع المجاميع الجزئية من PSUM 0 إلى PSUM 4 بالوصول نفسه المراعي للمحلية (locality-aware)، وينتج صفّا الحشو خانتين فارغتين من المجاميع الجزئية لا يقرؤهما أحد.

Those two dashed rows are the price. Two zero rows were multiplied for nothing so that five matmul launches became two. That is the entire idea of this concept, and the paper names it in the slide title: trading computation for regularity. The overview on slide 101 lists three techniques, locality-aware gather, adaptive grouping of the matmuls, and locality-aware scatter-accumulate. The first and last attack the memory-bound half of the runtime by reading and writing feature rows in an order that keeps neighbouring accesses close and by fusing and vectorizing them; the paper reports the cost of memory movement cut by 2.7x that way (Tang et al., MLSys 2022, abstract). The middle technique, grouping, is what the rest of this concept builds up.

هذان الصفّان المتقطعان هما الثمن. ضُرب صفّا أصفار بلا فائدة كي تصبح خمسة تشغيلات matmul تشغيلين فقط. هذه هي فكرة المفهوم كلها، والورقة تسمّيها في عنوان الشريحة: مقايضة الحساب بالانتظام (trading computation for regularity). تعرض النظرة العامة في الشريحة 101 ثلاث تقنيات: locality-aware gather، وadaptive grouping (التجميع التكيفي) لعمليات الـ matmul، وlocality-aware scatter-accumulate. الأولى والأخيرة تعالجان النصف المحدود بالذاكرة من زمن التشغيل بقراءة صفوف الخصائص وكتابتها بترتيب يُبقي عمليات الوصول المتجاورة قريبة من بعضها، وبدمجها وتحويلها إلى عمليات متجهة (vectorizing)، وتذكر الورقة أن كلفة نقل الذاكرة انخفضت بذلك بمقدار 2.7x (Tang et al., MLSys 2022، الملخص). أما التقنية الوسطى، التجميع، فهي ما يبنيه باقي هذا المفهوم.

The spectrum: separate, dense, groupedالطيف: منفصل، كثيف، مجمّع

Slides 102 to 104 draw seven weight offsets as seven columns of unequal height, one row per map entry, and put each execution strategy on two sliders: computation overhead and computation regularity. Separate computation, the baseline of the previous concept, launches one mm per column. Nothing is padded, so its overhead slider sits at best, but seven uneven kernels put its regularity at worst: many kernel calls, low device utilization. Dense convolution goes to the other end. Pad every column up to the tallest and run a single bmm with batch 7. Regularity is perfect, one launch, but the dashed rows now outnumber the real ones in the short columns, and overhead sits at worst. Computation with grouping refuses both extremes. The tallest column keeps its own mm. The four columns of similar height are padded by a total of two rows and run as one bmm with batch 4. The two shortest, equal already, form a bmm with batch 2. Slide 104 counts the cost: extra computation of 2 / 28, about 7 percent, for cutting seven launches to three.

ترسم الشرائح من 102 إلى 104 سبع إزاحات وزن على شكل سبعة أعمدة غير متساوية الارتفاع، صف لكل مدخل في الـ map، وتضع كل استراتيجية تنفيذ على مؤشرين: كلفة الحساب الإضافية (computation overhead) وcomputation regularity (انتظام الحساب). الحساب المنفصل، وهو خط الأساس في المفهوم السابق، يطلق عملية mm واحدة لكل عمود. لا شيء محشو، فمؤشر الكلفة الإضافية عنده في الأفضل، لكن سبعة kernels غير متساوية تضع انتظامه في الأسوأ: استدعاءات kernel كثيرة واستغلال منخفض للجهاز. الالتفاف الكثيف يذهب إلى الطرف الآخر: احشُ كل عمود حتى ارتفاع أطولها وشغّل عملية bmm واحدة بـ batch 7. الانتظام مثالي، تشغيل واحد، لكن الصفوف المتقطعة صارت أكثر من الحقيقية في الأعمدة القصيرة، والكلفة الإضافية في الأسوأ. أما الحساب مع التجميع فيرفض الطرفين. يحتفظ العمود الأطول بعملية mm خاصة به. تُحشى الأعمدة الأربعة المتقاربة في الارتفاع بصفّين إجمالًا وتعمل كعملية bmm واحدة بـ batch 4. والعمودان الأقصر، المتساويان أصلًا، يشكّلان bmm بـ batch 2. تحسب الشريحة 104 الكلفة: حساب إضافي قدره 2 / 28، أي نحو 7%، مقابل خفض سبعة تشغيلات إلى ثلاثة.

How the groups are chosenكيف تُختار المجموعات

Grouping only pays when the columns in a group really are similar, so the question becomes how similar is similar enough. TorchSparse answers with two auto-tuned parameters. The first, epsilon, is the tolerance of redundant computation. Walk the offsets in kernel order and scan them once with two pointers, extending the current group while the redundant computation ratio stays at or below epsilon and starting a new group the moment adding the next offset would exceed it (Tang et al., MLSys 2022, section 4.2.3). The groups are therefore contiguous runs of weight indices, which is why the red boxes on slide 105 sit side by side along the weight axis; the tuner below and the slide 104 figure instead order the offsets by map size first, a simplification that makes the pad rows easier to see.

لا يفيد التجميع إلا إذا كانت الأعمدة داخل المجموعة متشابهة فعلًا، فيصبح السؤال: ما مقدار التشابه الكافي؟ يجيب TorchSparse بمعاملين يُضبطان آليًا. الأول، epsilon، هو حد التسامح مع الحساب الزائد. امشِ على الإزاحات بترتيب الـ kernel وامسحها مرة واحدة بمؤشرين (two pointers)، فتمدّ المجموعة الحالية ما دامت redundant computation ratio (نسبة الحساب الزائد) أقل من epsilon أو مساوية لها، وتبدأ مجموعة جديدة في اللحظة التي تتجاوزها فيها إضافة الإزاحة التالية (Tang et al., MLSys 2022، القسم 4.2.3). لذلك تكون المجموعات سلاسل متصلة من أرقام الأوزان، وهذا سبب ظهور المربعات الحمراء في الشريحة 105 متجاورة على محور الأوزان؛ أما أداة الضبط أدناه وشكل الشريحة 104 فيرتّبان الإزاحات حسب حجم الـ map أولًا، وهو تبسيط يجعل صفوف الحشو أسهل رؤية.

The second parameter, S, is a workload threshold. A group runs as bmm only if its largest map is below S; otherwise it runs as mm, because bmm improves device utilization for small workloads but has little benefit once a single matmul is already large enough to fill the GPU. The two knobs contain the whole spectrum as special cases: epsilon = 1 with S unbounded is dense convolution, S = 0 is separate computation, and epsilon = 0 with S unbounded is what the paper calls symmetric grouping. That last case is free: for an odd kernel size at stride 1 the map for offset (a, b, c) has exactly the same size as the map for (-a, -b, -c), since every pair of neighbours appears once in each direction, so 26 offsets collapse into 13 groups of two with no padding at all, worth up to about 1.2x (Tang et al., MLSys 2022, section 4.2.2).

المعامل الثاني، S، عتبة لحجم العمل. لا تعمل المجموعة كـ bmm إلا إذا كان أكبر map فيها أقل من S؛ وإلا تعمل كـ mm، لأن bmm يحسّن استغلال الجهاز في الأحمال الصغيرة لكن فائدته ضئيلة حين تكون عملية matmul واحدة كبيرة بما يكفي لملء الـ GPU. يحتوي هذان المقبضان الطيف كله كحالات خاصة: epsilon = 1 مع S بلا حد هو الالتفاف الكثيف، وS = 0 هو الحساب المنفصل، وepsilon = 0 مع S بلا حد هو ما تسمّيه الورقة التجميع المتماثل (symmetric grouping). وهذه الحالة الأخيرة مجانية: مع kernel فردي الحجم وstride 1، يكون حجم الـ map للإزاحة (a, b, c) مساويًا تمامًا لحجم الـ map للإزاحة (-a, -b, -c)، لأن كل زوج من الجيران يظهر مرة في كل اتجاه، فتنضغط 26 إزاحة إلى 13 مجموعة من اثنتين دون أي حشو، بتسريع يصل إلى نحو 1.2x (Tang et al., MLSys 2022، القسم 4.2.2).

Try the knobs yourself. The tuner below starts from exactly this example, and rerolling draws new map sizes so you can watch which groups form as epsilon and S move.

جرّب المقابض بنفسك. تبدأ أداة الضبط أدناه من هذا المثال بالضبط، وإعادة السحب (reroll) ترسم أحجام maps جديدة كي ترى أي المجموعات تتشكل مع تحريك epsilon وS.

Measured: neither zero padding nor one group winsبالقياس: لا الحشو الصفري يفوز ولا المجموعة الواحدة

Slide 105 is the experiment that settles the question. On the first sparse convolution layer of MinkUNet on SemanticKITTI, the paper sweeps the number of groups from 26 (no padding, the separate baseline at 1.0x) down to 1 (fully dense). Going from 26 to 13 groups gives about 1.2x, the symmetric pairing. At 6 groups the speedup peaks near 1.5x. Then it collapses: 3 groups fall below the baseline and 1 group runs at about 0.35x, worse than doing nothing. The slide annotates the two slopes as increasing regularity helps improve latency, then padding overhead hurts latency (Tang et al., MLSys 2022, Figure 7).

الشريحة 105 هي التجربة التي تحسم السؤال. على أول طبقة التفاف متناثر في MinkUNet على SemanticKITTI، تمسح الورقة عدد المجموعات من 26 (بلا حشو، أي خط الأساس المنفصل عند 1.0x) نزولًا إلى 1 (كثيف بالكامل). الانتقال من 26 إلى 13 مجموعة يعطي نحو 1.2x، وهو الاقتران المتماثل. عند 6 مجموعات يبلغ التسريع ذروته قرب 1.5x. ثم ينهار: 3 مجموعات تهبط تحت خط الأساس، ومجموعة واحدة 1 تعمل بنحو 0.35x، أي أسوأ من عدم فعل أي شيء. تعلّق الشريحة على المنحدرين بأن زيادة الانتظام تحسّن زمن الاستجابة (latency)، ثم كلفة الحشو تضرّ به (Tang et al., MLSys 2022، الشكل 7).

The two bar charts under the curve explain why the answer is adaptive rather than fixed. They plot map size against weight index 1 to 27 for a MinkUNet layer on two datasets, with red boxes marking the groups the tuner chose. SemanticKITTI maps are large, mostly in the thousands, and the boxes are narrow: 10 groups. nuScenes maps are an order of magnitude smaller, hundreds rather than thousands, so each launch is even less able to fill the GPU and the tuner groups more aggressively: 8 groups with wider boxes (Tang et al., MLSys 2022, Figure 12). The right amount of padding is a property of the data, which is why it is searched per model and per dataset instead of fixed in code.

يشرح المخططان العموديان تحت المنحنى لماذا الجواب تكيفي لا ثابت. يرسمان حجم الـ map مقابل رقم الوزن من 1 إلى 27 لطبقة من MinkUNet على مجموعتي بيانات، مع مربعات حمراء تحدد المجموعات التي اختارتها أداة الضبط. الـ maps في SemanticKITTI كبيرة، معظمها بالآلاف، والمربعات ضيقة: 10 مجموعات. أما في nuScenes فالـ maps أصغر بمرتبة عشرية، بالمئات لا بالآلاف، فيكون كل تشغيل أقل قدرة على ملء الـ GPU، وتجمّع أداة الضبط بشكل أشد: 8 مجموعات بمربعات أعرض (Tang et al., MLSys 2022، الشكل 12). القدر الصحيح من الحشو خاصية من خصائص البيانات، ولهذا يُبحث عنه لكل نموذج ولكل مجموعة بيانات بدل أن يُثبَّت في الكود.

Slides 106 and 107 isolate the matmul phase and ask a sharp question: on an RTX 2080 Ti in FP16, how much did grouping actually buy? Three strategies are compared, the separate baseline, a fixed grouping with three hand-made groups per layer type padded to their maximum, and adaptive grouping. Each is reported twice, as throughput in TFLOP/s and as normalized speedup, and the two columns disagree in an instructive way.

تعزل الشريحتان 106 و107 مرحلة الـ matmul وتطرحان سؤالًا حادًا: على RTX 2080 Ti بدقة FP16، كم كسب التجميع فعلًا؟ تُقارَن ثلاث استراتيجيات: خط الأساس المنفصل، وتجميع ثابت (fixed grouping) بثلاث مجموعات مصنوعة يدويًا لكل نوع طبقة ومحشوة حتى حدها الأقصى، وadaptive grouping (التجميع التكيفي). تُعرض كل واحدة مرتين، كإنتاجية بوحدة TFLOP/s وكتسريع منسوب (normalized speedup)، والعمودان يختلفان بطريقة مفيدة للفهم.

On SemanticKITTI (MinkUNet 0.5x) adaptive grouping lifts throughput from 8.1 to 11.9 TFLOP/s and finishes 1.39x faster. Fixed grouping is the trap: it posts a higher throughput than the baseline, 8.7 TFLOP/s, yet is slower, 0.87x. On nuScenes (MinkUNet, three frames) the trap is sharper still. Fixed grouping reaches the best throughput of the whole table, 21.1 TFLOP/s, and adaptive grouping only 16.9, yet adaptive is the faster of the two at 1.54x against 1.50x. Slide 107 gives the reason in one line: fixed grouping introduced a large amount of redundant computation. TFLOP/s counts every multiply the tensor cores performed, pad rows included. A strategy can therefore look excellent on throughput while spending that throughput on zeros. Latency counts only the clock, and the paper's caption puts it precisely: as we trade FLOPs for regularity, TFLOP/s and speedup are non-proportional (Tang et al., MLSys 2022, Table 2). Device utilization for the matmul phase rose from about 30 percent to 44.2 percent with adaptive grouping.

على SemanticKITTI (MinkUNet 0.5x) يرفع التجميع التكيفي الإنتاجية من 8.1 إلى 11.9 TFLOP/s وينتهي أسرع بمقدار 1.39x. التجميع الثابت هو الفخ: يسجّل إنتاجية أعلى من خط الأساس، 8.7 TFLOP/s، ومع ذلك هو أبطأ، 0.87x. وعلى nuScenes (MinkUNet، ثلاثة إطارات) يصبح الفخ أوضح. يصل التجميع الثابت إلى أعلى إنتاجية في الجدول كله، 21.1 TFLOP/s، والتجميع التكيفي إلى 16.9 فقط، ومع ذلك فالتكيفي هو الأسرع بين الاثنين، 1.54x مقابل 1.50x. تعطي الشريحة 107 السبب في سطر واحد: التجميع الثابت أدخل كمية كبيرة من الحساب الزائد. فـ TFLOP/s يعدّ كل عملية ضرب نفّذتها الـ tensor cores، بما فيها صفوف الحشو. لذلك قد تبدو استراتيجية ممتازة في الإنتاجية بينما تنفق هذه الإنتاجية على أصفار. أما زمن الاستجابة (latency) فلا يعدّ إلا الساعة، وتعليق الورقة يقولها بدقة: حين نقايض FLOPs بالانتظام، لا يتناسب TFLOP/s مع التسريع (Tang et al., MLSys 2022، الجدول 2). وارتفع استغلال الجهاز في مرحلة الـ matmul من نحو 30% إلى 44.2% مع التجميع التكيفي.

End to end, with locality-aware gather and scatter included, the paper reports 1.6x over MinkowskiEngine and 1.5x over SpConv across seven models and three datasets, measured on GTX 1080 Ti, RTX 2080 Ti and RTX 3090, with up to 2.16x on segmentation models over MinkowskiEngine on the RTX 3090 (Tang et al., MLSys 2022, abstract and section 5). These figures are not on the slides; the slides show only the matmul ablation, so quote them as the paper's, and note that the MLSys 2022 evaluation used desktop GPUs only. The edge numbers come with the successor.

من البداية إلى النهاية (end to end)، ومع احتساب gather وscatter المراعيين للمحلية، تذكر الورقة تسريعًا 1.6x مقارنة بـ MinkowskiEngine و1.5x مقارنة بـ SpConv عبر سبعة نماذج وثلاث مجموعات بيانات، مقيسًا على GTX 1080 Ti وRTX 2080 Ti وRTX 3090، ويصل إلى 2.16x في نماذج التقطيع (segmentation) مقارنة بـ MinkowskiEngine على RTX 3090 (Tang et al., MLSys 2022، الملخص والقسم 5). هذه الأرقام ليست في الشرائح؛ فالشرائح تعرض تجربة الـ matmul فقط، لذلك انسبها إلى الورقة عند ذكرها، ولاحظ أن تقييم MLSys 2022 استخدم بطاقات GPU مكتبية فقط. أرقام الأجهزة الطرفية تأتي مع الخلف.

TorchSparse++: overlap memory with computationTorchSparse++: تداخل الذاكرة مع الحساب

Grouping fixed the matmul phase, but the baseline still has a structural flaw that no grouping removes: the three phases of gather, matmul and scatter run one after another. Gather must finish before the matmul starts, and the matmul must finish before scatter starts, three separate CUDA kernel calls in each iteration of the host loop. While the memory system is busy gathering, the tensor cores wait; while the tensor cores multiply, the memory system idles. The MICRO 2023 paper calls gather-GEMM-scatter fundamentally inefficient due to the lack of overlap between computation and memory access (Tang, Yang et al., MICRO 2023, section 2.2). The remedy in TorchSparse++ is to stop treating the phases as separate kernels.

أصلح التجميع مرحلة الـ matmul، لكن خط الأساس ما زال فيه عيب بنيوي لا يزيله أي تجميع: المراحل الثلاث gather, matmul and scatter تعمل واحدة بعد الأخرى. يجب أن تنتهي gather قبل أن تبدأ matmul، ويجب أن تنتهي matmul قبل أن تبدأ scatter، أي ثلاثة استدعاءات CUDA kernel منفصلة في كل دورة من حلقة المضيف (host loop). وبينما نظام الذاكرة مشغول بالجمع، تنتظر الـ tensor cores؛ وبينما تضرب الـ tensor cores، يبقى نظام الذاكرة خاملًا. تصف ورقة MICRO 2023 أسلوب gather-GEMM-scatter بأنه غير فعال جوهريًا بسبب غياب التداخل بين الحساب والوصول إلى الذاكرة (Tang, Yang et al., MICRO 2023، القسم 2.2). والعلاج في TorchSparse++ هو التوقف عن معاملة المراحل كـ kernels منفصلة.

Two fused dataflows already existed in other engines, and TorchSparse++ builds on both. Fetch-on-demand, used by MinkowskiEngine, merges gather, multiply and scatter into a single kernel that loads only the input rows it needs straight into shared memory, multiplies on chip and scatters results from registers, with zero redundant computation but heavy output write traffic, 4x to 10x more than the theoretical minimum of one write per output row, since each point has 4 to 10 neighbours and every partial sum is written back individually. Implicit GEMM, used by SpConv v2, is output-stationary: each thread block owns a tile of output rows, walks the nine (or 27) weights, and fetches the matching input rows on demand, the way im2col does for dense convolution. It writes each output once and hides memory latency by pipelining, so the loads for the next tile are already in flight while the tensor cores work on the current tile (Tang, Yang et al., MICRO 2023, section 2.2 and Figure 3). That in-kernel double buffering is the overlap the slide title refers to.

كان هناك أصلًا مساران مدمجان للبيانات (fused dataflows) في محركات أخرى، ويبني TorchSparse++ على كليهما. الأول fetch-on-demand (الجلب عند الطلب)، ويستخدمه MinkowskiEngine، ويدمج gather والضرب وscatter في kernel واحد يحمّل صفوف الإدخال التي يحتاجها فقط مباشرة إلى الذاكرة المشتركة (shared memory)، ويضرب على الشريحة، ويوزّع النتائج من المسجلات (registers)، بلا أي حساب زائد لكن مع حركة كتابة ثقيلة للإخراج، أكثر بـ 4x إلى 10x من الحد الأدنى النظري وهو كتابة واحدة لكل صف إخراج، لأن لكل نقطة من 4 إلى 10 جيران وكل مجموع جزئي يُكتب وحده. والثاني Implicit GEMM، ويستخدمه SpConv v2، وهو output-stationary (الإخراج ثابت): كل thread block يملك قطعة (tile) من صفوف الإخراج، ويمرّ على الأوزان التسعة (أو 27)، ويجلب صفوف الإدخال المطابقة عند الطلب، كما يفعل im2col في الالتفاف الكثيف. يكتب كل إخراج مرة واحدة ويخفي تأخر الذاكرة بالتنفيذ المتتابع (pipelining)، بحيث تكون عمليات تحميل القطعة التالية جارية بالفعل بينما تعمل الـ tensor cores على القطعة الحالية (Tang, Yang et al., MICRO 2023، القسم 2.2 والشكل 3). هذا التخزين المزدوج داخل الـ kernel (double buffering) هو التداخل الذي يشير إليه عنوان الشريحة.

The catch with implicit GEMM is a new kind of redundancy, and slide 109 shows it. Rows are output points B0 to B7, columns are the nine weights, and a grey cell is a real multiply because the input neighbour A_j exists. Threads in a warp execute in lockstep, so if any row in a thread block needs a weight, every row in that block runs it. The red cells are those wasted lockstep multiplies: 12 in the vanilla layout. Row reordering sorts the outputs by their neighbour bitmask so rows with similar patterns share a block, cutting the count to 10. Column splitting then divides the loop over the nine weights into three parts, each sorted on its own, so a row is grouped with different neighbours for different weight subsets: 8. The paper's own example runs 34 to 26 to 22 multiplies and reports that bitmask sorting can cut redundancy by up to 3x (Tang, Yang et al., MICRO 2023, Figures 5, 6 and 10). The fused kernel keeps its overlap; these two reorderings trim what it pays for it.

المشكلة في implicit GEMM نوع جديد من التكرار، والشريحة 109 تعرضه. الصفوف هي نقاط الإخراج من B0 إلى B7، والأعمدة هي الأوزان التسعة، والخلية الرمادية عملية ضرب حقيقية لأن الجار A_j في الإدخال موجود. الـ threads في الـ warp تنفّذ بخطوة متزامنة (lockstep)، فإذا احتاج أي صف في الـ thread block وزنًا ما، نفّذه كل صف في ذلك الـ block. الخلايا الحمراء هي عمليات الضرب المهدرة بسبب التزامن: 12 في الترتيب الأصلي (vanilla). إعادة ترتيب الصفوف (row reordering) ترتّب الإخراج حسب قناع الجيران (bitmask) بحيث تتشارك الصفوف ذات الأنماط المتشابهة block واحدًا، فينخفض العدد إلى 10. ثم يقسم تقسيم الأعمدة (column splitting) الحلقة على الأوزان التسعة إلى ثلاثة أجزاء، كل جزء مرتّب وحده، فيُجمع الصف مع جيران مختلفين لمجموعات أوزان مختلفة: 8. ومثال الورقة نفسها ينتقل من 34 إلى 26 إلى 22 عملية ضرب، وتذكر أن الترتيب بالـ bitmask قد يخفض التكرار حتى 3x (Tang, Yang et al., MICRO 2023، الأشكال 5 و6 و10). يحتفظ الـ kernel المدمج بتداخله، وهاتان الطريقتان في إعادة الترتيب تقلّصان ما يدفعه ثمنًا لذلك.

Writing such kernels by hand is expensive. SpConv v2 needed more than 40,000 lines re-implementing CUTLASS. TorchSparse++ therefore contributes two components, both drawn on slide 108. The Sparse Kernel Generator produces the fused, pipelined kernels automatically at under a tenth of that engineering cost, adapting dense GEMM templates to sparse gather (dense-to-sparse adaptation) and static shapes to run-time maps (static-to-dynamic adaptation). The Sparse Autotuner widens the design space (gather-GEMM-scatter with grouping, fetch-on-demand, implicit GEMM, and their tile and split parameters) and tunes a configuration per group of layers rather than per layer, so the search stays cheap (Tang, Yang et al., MICRO 2023, sections 3 and 4).

كتابة مثل هذه الـ kernels يدويًا مكلفة. احتاج SpConv v2 إلى أكثر من 40,000 سطر لإعادة تنفيذ CUTLASS. لذلك يقدّم TorchSparse++ مكوّنين، كلاهما مرسوم في الشريحة 108. الأول Sparse Kernel Generator (مولّد الـ kernels المتناثرة)، وينتج الـ kernels المدمجة المتتابعة آليًا بأقل من عُشر تلك الكلفة الهندسية، بتكييف قوالب GEMM الكثيفة مع الجمع المتناثر (dense-to-sparse adaptation) وتكييف الأشكال الثابتة مع الـ maps التي تُبنى وقت التشغيل (static-to-dynamic adaptation). والثاني Sparse Autotuner (الضابط الآلي المتناثر)، ويوسّع فضاء التصميم (gather-GEMM-scatter مع التجميع، وfetch-on-demand، وimplicit GEMM، ومعاملات الـ tile والتقسيم الخاصة بها) ويضبط إعدادًا لكل مجموعة من الطبقات لا لكل طبقة، كي يبقى البحث رخيصًا (Tang, Yang et al., MICRO 2023، القسمان 3 و4).

Reading the A100 column the other way round, TorchSparse++ is 2.9x faster than MinkowskiEngine, 3.3x faster than SpConv 1.2.1, 2.2x faster than TorchSparse and 1.7x faster than SpConv 2.3.5, the four numbers the paper's abstract reports. The Orin column is the one that matters for this course: on the Jetson Orin edge GPU, the strongest baseline, SpConv 2.3.5, sits at 0.80, so TorchSparse++ is 1.25x faster on average, with a consistent 1.3x to 1.4x on detection workloads (Tang, Yang et al., MICRO 2023, section 5). The chart also shows training columns and a TF32 column; the same engine covers all of them.

بقراءة أرقام A100 بالاتجاه المعاكس، يكون TorchSparse++ أسرع بمقدار 2.9x من MinkowskiEngine، و3.3x من SpConv 1.2.1، و2.2x من TorchSparse، و1.7x من SpConv 2.3.5، وهي الأرقام الأربعة التي يذكرها ملخص الورقة. وأرقام Orin هي المهمة لهذا المقرر: على الـ GPU الطرفي Jetson Orin، يقف أقوى خط أساس، SpConv 2.3.5، عند 0.80، فيكون TorchSparse++ أسرع بمقدار 1.25x في المتوسط، مع تسريع ثابت من 1.3x إلى 1.4x في أحمال الكشف (detection) (Tang, Yang et al., MICRO 2023، القسم 5). ويعرض المخطط أيضًا أعمدة للتدريب وعمودًا لـ TF32؛ والمحرك نفسه يغطيها كلها.

One more step remains beyond software. Every engine in this part still spends time building the maps themselves, a hashing or sorting problem the GPU is not shaped for. Part 13 moves that step into hardware with PointAcc, whose mapping unit produces the tuples with merge sort.

تبقى خطوة أخرى أبعد من البرمجيات. كل محرك في هذا الجزء ما زال يقضي وقتًا في بناء الـ maps نفسها، وهي مسألة hashing أو ترتيب لم يُصمَّم الـ GPU لها. ينقل الجزء 13 هذه الخطوة إلى العتاد مع PointAcc، الذي تنتج وحدة الربط (mapping unit) فيه الثلاثيات باستخدام merge sort.