The baseline: gather, matmul, scatter per offset

خط الأساس: gather ثم matmul ثم scatter لكل إزاحة

For each weight offset δ (27 in 3D, 9 in 2D): gather the |M_δ| input rows named by the map into a buffer, run one matmul (|M_δ| x C_in) by (C_in x C_out), then scatter-accumulate the partial sums into the output rows.

لكل إزاحة وزن δ (27 في ثلاثة أبعاد، 9 في بعدين): اجمع (gather) صفوف الدخل الـ |M_δ| المذكورة في map في buffer، ونفّذ matmul واحداً (|M_δ| x C_in) في (C_in x C_out)، ثم وزّع مع الجمع (scatter-accumulate) النتائج الجزئية في صفوف الخرج.

• Gather and scatter are random memory accesses, bandwidth bound, and take 40 to 50 percent of runtime.

  gather وscatter وصول عشوائي للذاكرة، محكوم بعرض النطاق، ويستهلكان 40 إلى 50% من زمن التشغيل.

• Matmuls are dense but small and uneven across offsets: about 30 percent GPU utilization.

  الـ matmuls كثيفة لكنها صغيرة وغير متساوية بين الإزاحات: نحو 30% فقط من استغلال GPU.

Grouping: trade FLOPs for regularity

التجميع: نقايض FLOPs بالانتظام

Pad offsets with similar map sizes to the same height and run them as one batched matmul (bmm). Three points on a spectrum:

احشُ الإزاحات ذات أحجام map المتقاربة إلى نفس الارتفاع، ونفّذها كـ batched matmul (bmm) واحد. ثلاث نقاط على طيف:

• Separate: one matmul per offset. Zero padding, many tiny kernels.

  منفصل: matmul لكل إزاحة. لا حشو، لكن نوى صغيرة كثيرة.

• Dense batching: pad every offset to the largest, one bmm. Most regular, but so much wasted compute that it loses.

  تجميع كثيف: احشُ كل إزاحة إلى أكبرها، bmm واحد. الأكثر انتظاماً، لكن الحساب المهدور كبير لدرجة أنه يخسر.

• Adaptive grouping: group neighbours while the redundant ratio stays under a tolerance ε; run any offset above a size threshold S alone. About 6 groups on SemanticKITTI beat both 26 and 1, about 1.5x.

  adaptive grouping: اجمع الإزاحات المتجاورة ما دامت نسبة الحساب الزائد تحت تسامح ε، ونفّذ أي إزاحة فوق عتبة الحجم S وحدها. نحو 6 مجموعات على SemanticKITTI تتفوق على 26 وعلى 1، بنحو 1.5x.

redundant ratio of group G:   r = 1 - (sum of |M_δ| in G) / (|G| x max |M_δ| in G)

نسبة الحساب الزائد للمجموعة G هي واحد ناقص (مجموع الصفوف الحقيقية) مقسوماً على (عدد الإزاحات في المجموعة مضروباً في أكبر حجم فيها).

map sizes: W0,0 = 100; others 40 40 38 38 12 12 11 11     real rows = 302

separate   9 launches, 302 rows, 0 pad
dense      1 bmm (batch 9) padded to 100: 900 rows, 598 pad
           r = 1 - 302/900 = 66.4%
adaptive   W0,0 alone (mm)            100 rows
           {40,40,38,38} pad to 40    160 rows, 4 pad, r = 1 - 156/160 = 2.5%
           {12,12,11,11} pad to 12     48 rows, 2 pad, r = 1 - 46/48  = 4.2%
           3 launches, 308 rows, 6 pad (1.9%)

لاحظ أن fixed grouping يسجّل TFLOP/s أعلى في الحالتين لكنه أبطأ: على SemanticKITTI هو 8.7 مقابل 8.1 ومع ذلك 0.87x، وعلى nuScenes هو 21.1 مقابل 16.9 لـ adaptive ومع ذلك أبطأ قليلاً.

End to end, TorchSparse is 1.6x faster than MinkowskiEngine and 1.5x faster than SpConv, also cutting memory movement cost by 2.7x through better gather and scatter.

على مستوى النظام كاملاً، TorchSparse أسرع بـ 1.6x من MinkowskiEngine وبـ 1.5x من SpConv، ويقلّص كلفة حركة الذاكرة بـ 2.7x عبر تحسين gather وscatter.

PointAcc: build the map with a merge sort

PointAcc: بناء الخريطة بـ merge sort

Building the map means finding, for every offset δ, every pair with P = Q + δ. A GPU or a naive accelerator uses a hash table, which in parallel hardware needs an O(N²) crossbar and random SRAM reads. PointAcc instead shifts every input by -δ, merge-sorts the shifted inputs with the outputs, and reads off equal neighbours as map entries: |I| + |O| - 1 comparisons, two sequential streams.

بناء map يعني إيجاد كل زوج يحقق P = Q + δ لكل إزاحة δ. يستخدم GPU أو مسرّع بسيط جدول hash، وهو في العتاد المتوازي يحتاج crossbar بحجم O(N²) وقراءات SRAM عشوائية. أما PointAcc فيزيح كل دخل بـ -δ، ثم يدمج المدخلات المزاحة مع المخرجات بـ merge sort، ويقرأ الجيران المتساوين كمدخلات map: |I| + |O| - 1 مقارنة، بتدفقين تسلسليين.

The merge-sort mapping unit is 1.4x faster and up to 14x smaller than a hash-table unit at equal parallelism. Overall PointAcc reaches geomean 3.7x, 53x and 90x speedup over an RTX 2080Ti GPU, a Xeon plus TPU V3, and a Xeon Gold CPU (energy savings 22x, 210x and 176x; the slide prints 193x for the last).

وحدة الربط بـ merge sort أسرع بـ 1.4x وأصغر حتى 14x من وحدة جدول hash عند نفس التوازي. وإجمالاً يحقق PointAcc متوسطاً هندسياً للتسريع 3.7x و53x و90x مقارنة بـ RTX 2080Ti وXeon + TPU V3 وXeon Gold (وتوفير طاقة 22x و210x و176x، والشريحة تطبع 193x للأخير).

Lecture summary (slide 114)

ملخص المحاضرة (الشريحة 114)

This lecture covered automated ways to find pruning ratios (sensitivity analysis, AMC, NetAdapt) and system and hardware support for different granularities: EIE for weight plus activation sparsity, Ampere tensor cores for M:N, TorchSparse and PointAcc for point-cloud activation sparsity. Next: numeric data types, the basic concept of quantization, and common quantization methods.

غطّت هذه المحاضرة الطرق الآلية لإيجاد نسب التقليم (sensitivity analysis وAMC وNetAdapt)، ودعم الأنظمة والعتاد لمستويات الدقة المختلفة: EIE لتناثر الأوزان والتنشيطات، وtensor cores من جيل Ampere لنمط M:N، وTorchSparse وPointAcc لتناثر تنشيطات point cloud. التالي: أنواع البيانات العددية، والمفهوم الأساسي للـ quantization، وطرقه الشائعة.