Majid Al-RaimiPointAcc, the lecture summary and referencesPointAcc وملخص المحاضرة والمراجع

COE 592Lecture 4.2المحاضرة 4.2Part 13الجزء 13

PointAcc, the lecture summary and referencesPointAcc وملخص المحاضرة والمراجع

PointAcc builds the sparse convolution map in hardware with a merge-sort based mapping unit, then the lecture closes with what was covered and what quantization brings next.يبني PointAcc خريطة الالتفاف المتناثر في العتاد بوحدة ربط قائمة على الفرز بالدمج (merge sort)، ثم تُختتم المحاضرة بما غُطّي وما يقدمه التكميم (quantization) لاحقًا.

Conceptsالمفاهيم
4
Slidesالشرائح
110-115
Readingمدة القراءة
24 min24 دقيقة
Understoodما فهمته
0/4 conceptsمفاهيم

Why this part mattersلماذا يهمّ هذا الجزء

Every accelerator in this lecture so far assumed the hard part was the multiply. PointAcc is the case where it is not. When the input is a point cloud, the network spends most of its time deciding which inputs multiply which weights, and that decision has to be remade for every frame because the sparsity is in the data. Your embedded work will hit the same wall the moment your inputs stop being dense grids.

افترض كل مسرّع في هذه المحاضرة حتى الآن أن الجزء الصعب هو عملية الضرب. أما PointAcc فهو الحالة التي لا يكون فيها الأمر كذلك. عندما يكون الدخل سحابة نقطية (point cloud)، تقضي الشبكة معظم وقتها في تحديد أي المدخلات يُضرب في أي الأوزان، ويجب إعادة هذا القرار لكل إطار (frame) لأن التناثر موجود في البيانات نفسها. وعملك في الأنظمة المدمجة سيصطدم بالجدار نفسه في اللحظة التي تتوقف فيها مدخلاتك عن كونها شبكات كثيفة (dense grids).

This closing part does three things. It shows how PointAcc turns map construction into a sorting problem the hardware can stream, with the five-point example from slides 111 and 112 worked out to the last tuple. It reads the results slide the way the paper intends, with the right baselines. Then it folds the whole lecture into one table, so that the exam question "which system exploits which sparsity" has a single place to be answered from, and it checks the reference slide against what the deck actually cited.

يقوم هذا الجزء الختامي بثلاثة أشياء. أولًا، يبيّن كيف يحوّل PointAcc بناء الخريطة إلى مسألة فرز يستطيع العتاد معالجتها كتدفق متسلسل (stream)، مع حل مثال النقاط الخمس من الشريحتين 111 و112 حتى آخر ثلاثية. ثانيًا، يقرأ شريحة النتائج كما تقصدها الورقة، مع خطوط الأساس الصحيحة. ثالثًا، يجمع المحاضرة كلها في جدول واحد، بحيث يكون لسؤال الامتحان «أي نظام يستغل أي نوع من التناثر» مكان واحد يُجاب منه، ثم يراجع شريحة المراجع مقابل ما استشهدت به الشرائح فعلًا.

By the end you canفي نهاية هذا الجزء ستستطيع

  1. Explain why building the (In, Out, Wgt) map dominates point-cloud inference and why a hash table is a poor fit for silicon.اشرح لماذا يستهلك بناء خريطة (In, Out, Wgt) معظم وقت الاستدلال على السحب النقطية (point cloud)، ولماذا لا يناسب جدول التجزئة (hash table) السيليكون.
  2. Run the shift, merge sort, compare, emit procedure by hand on a five-point cloud and recover the tuples on slides 111 and 112.نفّذ إجراء الإزاحة ثم الفرز بالدمج (merge sort) ثم المقارنة ثم الإخراج يدويًا على سحابة من خمس نقاط، واستخرج الثلاثيات (tuples) نفسها التي في الشريحتين 111 و112.
  3. Read slide 113 correctly: the three baselines, the geometric means, and why the TPU column swings so widely.اقرأ الشريحة 113 قراءة صحيحة: خطوط الأساس (baselines) الثلاثة، والمتوسطات الهندسية، ولماذا يتأرجح عمود TPU هذا التأرجح الكبير.
  4. Map every sparsity type of this lecture to the system that exploits it and the granularity it needs.اربط كل نوع من أنواع التناثر (sparsity) في هذه المحاضرة بالنظام الذي يستغله وبالحبيبية (granularity) التي يحتاجها.
  5. State what the next lecture adds (numeric types, the idea of quantization, its common methods) and spot the references the deck cites but never lists.اذكر ما تضيفه المحاضرة التالية (أنواع البيانات العددية، وفكرة التكميم (quantization)، وطرقه الشائعة)، وحدّد المراجع التي تستشهد بها الشرائح دون أن تدرجها في القائمة.

The roadmap on slide 110 puts PointAcc in the last row, next to TorchSparse, under the heading activation sparsity. Read the row as a pair: TorchSparse is the software answer to sparse inputs, and PointAcc is the hardware answer to the same inputs. Both start from the Sparse convolution of part 11, where a layer is driven by maps of (In, Out, Wgt) tuples and each tuple contributes f_out = f_out + f_in × W_wgt.

خريطة الطريق في الشريحة 110 تضع PointAcc في الصف الأخير، بجانب TorchSparse، تحت عنوان تناثر التفعيلات (activation sparsity). اقرأ الصف كزوج: TorchSparse هو الحل البرمجي للمدخلات المتناثرة، وPointAcc هو الحل العتادي للمدخلات نفسها. وكلاهما ينطلق من الالتفاف المتناثر (sparse convolution) في الجزء 11، حيث تُقاد الطبقة بـخرائط (maps) من ثلاثيات (In, Out, Wgt)، وتساهم كل ثلاثية بـ f_out = f_out + f_in × W_wgt.

What changes between the two is where the time goes. On a GPU, the multiplies are batched into matmuls and run well once the map exists. Building the map is the problem. A point cloud has dynamic sparsity: which coordinates are occupied depends on the scene, so the map cannot be precomputed and must be rebuilt on every input. The PointAcc paper measures that cost on PointNet++-based networks and reports that more than half of the total runtime on general-purpose hardware goes to mapping operations, and that existing neural accelerators simply do not support them, so a TPU has to ship the coordinates back to its host CPU, where data movement then takes 60 to 90 percent of the runtime (Lin et al., 2021, section 3).

ما يتغير بين الاثنين هو أين يذهب الوقت. على GPU، تُجمَّع عمليات الضرب في عمليات ضرب مصفوفات (matmul) وتعمل جيدًا بمجرد وجود الخريطة. المشكلة هي بناء الخريطة. فالسحابة النقطية لها تناثر ديناميكي (dynamic sparsity): الإحداثيات المشغولة تعتمد على المشهد، لذلك لا يمكن حساب الخريطة مسبقًا ويجب إعادة بنائها مع كل دخل. تقيس ورقة PointAcc هذه التكلفة على شبكات مبنية على PointNet++، وتذكر أن أكثر من نصف زمن التشغيل الكلي على العتاد العام يذهب إلى عمليات الربط (mapping)، وأن مسرّعات الشبكات العصبية الحالية لا تدعمها أصلًا، فيضطر TPU إلى إرسال الإحداثيات إلى المعالج المضيف (host CPU)، حيث يستهلك نقل البيانات عندها 60 to 90 percent من زمن التشغيل (Lin et al., 2021, section 3).

The pairing rule, and how to turn it into an equality testقاعدة الاقتران، وكيف نحوّلها إلى اختبار تساوٍ

A 3 × 3 kernel has nine weight offsets, W−1,−1 through W1,1. Input point p contributes to output point q through offset δ exactly when p sits at q + δ. On a GPU the natural code is a loop over outputs that asks a hash table "is there an input at q + δ?". PointAcc rewrites the same condition so that no lookup is needed.

النواة (kernel) بحجم 3 × 3 لها تسع إزاحات للأوزان، من W−1,−1 إلى W1,1. نقطة الدخل p تساهم في نقطة الخرج q عبر الإزاحة δ إذا وفقط إذا كانت p واقعة عند q + δ. على GPU يكون الكود الطبيعي حلقة على المخرجات تسأل جدول تجزئة: «هل يوجد دخل عند q + δ؟». أما PointAcc فيعيد صياغة الشرط نفسه بحيث لا يحتاج إلى أي بحث في جدول (lookup).

p=q+δ  ⟺  p−δ=qp = q + \delta \iff p - \delta = q
Map condition for weight offset δ. PointAcc tests the right-hand side as an equality after shifting every input by −δ.شرط الخريطة لإزاحة الوزن δ. تختبر PointAcc الطرف الأيمن بوصفه مساواة بعد إزاحة كل مدخل بمقدار −δ.

Subtract δ from every input coordinate and the question becomes "which shifted inputs land on an output coordinate?", which is a set intersection. If both sets are sorted, an intersection is found by merging them and looking at adjacent elements: any input and output that coincide must end up side by side. This is why slide 112 adds (−1, −1) to the inputs for W1,1 and slide 111 adds (1, 1) for W−1,−1. The shift is always −δ, so the sign flips relative to the offset name.

اطرح δ من كل إحداثي دخل، فيصبح السؤال: «أي المدخلات المُزاحة تقع على إحداثي خرج؟»، وهذا تقاطع مجموعتين (set intersection). إذا كانت المجموعتان مرتبتين، نجد التقاطع بدمجهما والنظر إلى العناصر المتجاورة: أي دخل وخرج متطابقين لا بد أن ينتهيا متجاورين. لهذا تضيف الشريحة 112 القيمة (−1, −1) إلى المدخلات من أجل W1,1، وتضيف الشريحة 111 القيمة (1, 1) من أجل W−1,−1. الإزاحة دائمًا −δ، لذلك تنقلب الإشارة مقارنةً باسم الإزاحة.

Shifted inputs (teal) and outputs (light) slide into one sorted strip. Nine comparators check adjacent cells, the two that see equal coordinates fill in, and the map entries for W1,1 drop out.المدخلات المُزاحة (باللون الأزرق المخضر) والمخرجات (باللون الفاتح) تنزلق إلى شريط واحد مرتب. تسعة مقارنات (comparators) تفحص الخلايا المتجاورة، فتمتلئ الاثنتان اللتان تريان إحداثيات متساوية، وتظهر مدخلات الخريطة الخاصة بـ W1,1.

Worked exampleمثال محلول

Finding the pairs for W1,1 on slide 112إيجاد الأزواج الخاصة بـ W1,1 في الشريحة 112

  1. Shiftالإزاحة

    The inputs are P0 (1,1), P1 (2,2), P2 (2,4), P3 (3,2), P4 (4,3). With stride 1 the outputs Q0 to Q4 sit at the same five coordinates. For δ = (1, 1) add (−1, −1) to every input: (0,0) (1,1) (1,3) (2,1) (3,2).
    المدخلات هي P0 (1,1) وP1 (2,2) وP2 (2,4) وP3 (3,2) وP4 (4,3). ومع خطوة (stride) تساوي 1 تقع المخرجات Q0 إلى Q4 عند الإحداثيات الخمسة نفسها. من أجل δ = (1, 1) أضف (−1, −1) إلى كل دخل: (0,0) (1,1) (1,3) (2,1) (3,2).
  2. Merge sortالفرز بالدمج

    Both lists are already sorted by x then y, so one pass merges them: P0 (0,0), Q0 (1,1), P1 (1,1), P2 (1,3), P3 (2,1), Q1 (2,2), Q2 (2,4), Q3 (3,2), P4 (3,2), Q4 (4,3).
    القائمتان مرتبتان مسبقًا حسب x ثم y، لذلك يكفي مرور واحد لدمجهما: P0 (0,0)، Q0 (1,1)، P1 (1,1)، P2 (1,3)، P3 (2,1)، Q1 (2,2)، Q2 (2,4)، Q3 (3,2)، P4 (3,2)، Q4 (4,3).
  3. Compare neighborsمقارنة الجيران

    Ten cells give nine adjacent comparisons. Two of them are equal across owners: positions 2 and 3 (Q0 and P1, both (1,1)) and positions 8 and 9 (Q3 and P4, both (3,2)).
    عشر خلايا تعطي تسع مقارنات متجاورة. اثنتان منها متساويتان بين مالكين مختلفين (دخل وخرج): الموضعان 2 و3 (Q0 وP1، وكلاهما (1,1))، والموضعان 8 و9 (Q3 وP4، وكلاهما (3,2)).
  4. Emit tuplesإخراج الثلاثيات

    (P1, Q0, W1,1) and (P4, Q3, W1,1). Check against the rule: P1 = (2,2) = Q0 + (1,1) and P4 = (4,3) = Q3 + (1,1).
    (P1, Q0, W1,1) و(P4, Q3, W1,1). تحقّق منهما بالقاعدة: P1 = (2,2) = Q0 + (1,1) وP4 = (4,3) = Q3 + (1,1).
  5. Resultالنتيجة

    Two map entries out of 25 possible input-output pairs, found with 9 comparators and zero random memory accesses.
    مدخلان في الخريطة من أصل 25 زوجًا ممكنًا بين الدخل والخرج، عُثر عليهما بـ 9 مقارنات ودون أي وصول عشوائي إلى الذاكرة.
PositionالموضعOwnerالمالكCoordinateالإحداثيEqual neighborالجار المتساوي
11P0P00,00,0noلا
22Q0Q01,11,1yes, with 3نعم، مع 3
33P1P11,11,1yes, with 2نعم، مع 2
44P2P21,31,3noلا
55P3P32,12,1noلا
66Q1Q12,22,2noلا
77Q2Q22,42,4noلا
88Q3Q33,23,2yes, with 9نعم، مع 9
99P4P43,23,2yes, with 8نعم، مع 8
1010Q4Q44,34,3noلا
The merged strip on slide 112, position by positionالشريط المدموج في الشريحة 112، موضعًا بموضع

Slide 111 runs the identical procedure for the opposite corner of the kernel. The table below puts the two passes side by side. Notice the symmetry: the pairs for W1,1 are the pairs for W−1,−1 with the roles of input and output exchanged, P1 with Q0 against P0 with Q1. That is exactly what p = q + δ predicts, because if p = q + δ then q = p − δ, and with the input and output clouds sharing coordinates the same two points swap places.

تنفّذ الشريحة 111 الإجراء نفسه تمامًا للزاوية المقابلة من النواة. الجدول أدناه يضع المرورين جنبًا إلى جنب. لاحظ التناظر: أزواج W1,1 هي أزواج W−1,−1 نفسها مع تبادل دوري الدخل والخرج، أي P1 with Q0 مقابل P0 with Q1. وهذا بالضبط ما تتنبأ به p = q + δ، لأنه إذا كان p = q + δ فإن q = p − δ، وبما أن سحابتي الدخل والخرج تتشاركان الإحداثيات، تتبادل النقطتان نفسهما مكانيهما.

W1,1 (slide 112)W1,1 (الشريحة 112)W−1,−1 (slide 111)W−1,−1 (الشريحة 111)
Offset δالإزاحة δ (offset)(1, 1)(1, 1)(−1, −1)(−1, −1)
Shift applied to inputsالإزاحة المضافة إلى المدخلات (shift)+ (−1, −1)+ (−1, −1)+ (1, 1)+ (1, 1)
Shifted inputs P0 to P4المدخلات المُزاحة P0 إلى P4(0,0) (1,1) (1,3) (2,1) (3,2)(0,0) (1,1) (1,3) (2,1) (3,2)(2,2) (3,3) (3,5) (4,3) (5,4)(2,2) (3,3) (3,5) (4,3) (5,4)
Merged orderالترتيب بعد الدمجP0 Q0 P1 P2 P3 Q1 Q2 Q3 P4 Q4P0 Q0 P1 P2 P3 Q1 Q2 Q3 P4 Q4Q0 Q1 P0 Q2 Q3 P1 P2 Q4 P3 P4Q0 Q1 P0 Q2 Q3 P1 P2 Q4 P3 P4
Equal neighborsالجيران المتساويانQ0 = P1, Q3 = P4Q0 = P1, Q3 = P4Q1 = P0, Q4 = P3Q1 = P0, Q4 = P3
Tuples emittedالثلاثيات الناتجة(P1, Q0, W1,1), (P4, Q3, W1,1)(P1, Q0, W1,1), (P4, Q3, W1,1)(P0, Q1, W−1,−1), (P3, Q4, W−1,−1)(P0, Q1, W−1,−1), (P3, Q4, W−1,−1)
Slides 112 and 111: the same five points under two offsetsالشريحتان 112 و111: النقاط الخمس نفسها تحت إزاحتين
SimulatorمحاكيMapping unit: shift, merge sort, compare neighbors, emit tuplesوحدة الربط: أزح، ادمج بالترتيب، قارن الجيران، أخرج الثلاثيات
input point cloud (5 of 8)سحابة نقاط الإدخال (5 من 8)
weight offsetإزاحة الوزن
output cloudسحابة الخرج
shifted inputs, each point plus (-1, -1) for W1,1الإدخالات المزاحة، كل نقطة مضافًا إليها (-1, -1) لـ W1,1
  • P00,0
  • P11,1
  • P21,3
  • P32,1
  • P43,2
output pointsنقاط الخرج
  • Q01,1
  • Q12,2
  • Q22,4
  • Q33,2
  • Q44,3
merged, sorted by x then y, equal neighbors highlightedمدموجة ومرتبة حسب x ثم y، مع إبراز الجيران المتساوين
  • P00,0
  • Q01,1
  • P11,1
  • P21,3
  • P32,1
  • Q12,2
  • Q22,4
  • Q33,2
  • P43,2
  • Q44,3
(In, Out, Wgt) emittedالثلاثيات (In, Out, Wgt) الناتجة
  • (P1, Q0, W1,1)
  • (P4, Q3, W1,1)
Map entriesمدخلات الخريطة2of 25 candidate pairsمن أصل 25 زوجًا مرشحًا
Comparators9inputs plus outputs minus oneالإدخالات زائد المخرجات ناقص واحد
Random reads avoidedالقراءات العشوائية التي تم تجنبها5one hash probe per output pointاستعلام تجزئة واحد لكل نقطة خرج
Output pointsنقاط الخرج5same as the inputsمثل الإدخالات

Input p and output q pair up for offset δ exactly when p = q + δ, so subtracting δ from every input turns the search into an equality test. The merge reads the two sorted strips once, head against head, and the only checks are between adjacent cells of the merged strip, which is why the comparator count is the strip length minus one. A hash table would instead probe a random address once per output point. With stride 2 the output coordinates are quantized to the stride grid by clearing the low log2(ts) bits, which the same unit separates from kernel mapping.يقترن الإدخال p بالخرج q للإزاحة δ عندما يكون p = q + δ بالضبط، لذا فطرح δ من كل إدخال يحول البحث إلى اختبار تساوٍ. يقرأ الدمج الشريطين المرتبين مرة واحدة، رأسًا مقابل رأس، ولا تجري المقارنات إلا بين الخلايا المتجاورة في الشريط المدموج، ولهذا يساوي عدد المقارِنات طول الشريط ناقص واحد. أما جدول التجزئة فيستعلم عنوانًا عشوائيًا مرة لكل نقطة خرج. ومع الخطوة 2 تُكمَّم إحداثيات الخرج إلى شبكة الخطوة بمسح أدنى log2(ts) من البتات، وهي عملية تفصلها الوحدة نفسها عن ربط النواة.

Why a hash table is the wrong tool for siliconلماذا جدول التجزئة أداة خاطئة للسيليكون

The GPU library that PointAcc compares against builds its maps with a hash table, and on a GPU that is a reasonable choice: memory is large and random access is cheap enough. Neither holds on chip. The paper puts two numbers on it. First, a hash table sized for a real point cloud at a sensible load factor can reach 160 MB, which no accelerator can hold in SRAM. Second, to serve N lookups in parallel the SRAM needs an N-by-N crossbar so that any lane can reach any bank, and that crossbar grows as O(N²) in area (Lin et al., 2021, section 4.1).

مكتبة GPU التي يقارن PointAcc نفسه بها تبني خرائطها بجدول تجزئة، وهذا خيار معقول على GPU: الذاكرة كبيرة والوصول العشوائي رخيص بما يكفي. ولا يصح أي من الأمرين على الشريحة (on chip). وتضع الورقة رقمين على ذلك. أولًا، جدول التجزئة المصمم لسحابة نقطية حقيقية بمعامل تحميل (load factor) معقول قد يصل إلى 160 MB، وهذا ما لا يستطيع أي مسرّع حمله في SRAM. ثانيًا، لخدمة N عملية بحث على التوازي تحتاج SRAM إلى مصفوفة توصيل (crossbar) بحجم N في N حتى يصل أي مسار (lane) إلى أي بنك (bank)، وتنمو مساحة هذه المصفوفة بمقدار O(N²) (Lin et al., 2021, section 4.1).

Merging has neither problem. The Mapping Unit feeds window-sized chunks of the two sorted lists to a fixed-size bitonic merger, a parallel comparator network, and a forwarding loop carries leftover elements into the next cycle, so the lists are read in order and never probed at random. Detecting the intersection is just as local: the paper describes feeding each pair of adjacent elements of the merged array to a comparator that checks whether their coordinates are equal. With |I| shifted inputs and |O| outputs the strip has |I| + |O| cells and |I| + |O| − 1 adjacent comparisons, all independent, so they can run in a single cycle. The Mapping unit builds this from a bitonic sorting network feeding a merger of fixed length, and the paper reports that at the same parallelism the merge-sort design is 1.4x faster than the hash-table design while saving up to 14x in area (Lin et al., 2021, section 4.1).

الدمج لا يعاني من أي من المشكلتين. وحدة الربط (Mapping Unit) تغذّي دمّاجًا بيتونيًا (bitonic merger) ثابت الحجم، وهو شبكة مقارنات متوازية، بمقاطع بحجم النافذة من القائمتين المرتبتين، وتحمل حلقة تمرير (forwarding loop) العناصر المتبقية إلى الدورة التالية، فتُقرأ القوائم بالترتيب ولا يُبحث فيها عشوائيًا أبدًا. واكتشاف التقاطع محلي بالقدر نفسه: تصف الورقة تغذية كل زوج من العناصر المتجاورة في المصفوفة المدموجة إلى مقارن يتحقق من تساوي إحداثياتهما. مع |I| دخلًا مُزاحًا و|O| خرجًا، يحتوي الشريط على |I| + |O| خلية و|I| + |O| − 1 مقارنة متجاورة، كلها مستقلة، فيمكن تنفيذها في دورة واحدة. تبني وحدة الربط (mapping unit) ذلك من شبكة فرز بيتونية (bitonic sorting network) تغذّي دمّاجًا ثابت الطول، وتذكر الورقة أن تصميم الفرز بالدمج، عند التوازي نفسه، أسرع بمقدار 1.4x من تصميم جدول التجزئة ويوفّر ما يصل إلى 14x من المساحة (Lin et al., 2021, section 4.1).

comparisons per offset=∣I∣+∣O∣−1\text{comparisons per offset} = |I| + |O| - 1
Adjacent comparisons on a merged strip of |I| shifted inputs and |O| outputs. Nine on slide 112.مقارنات متجاورة على شريط مدموج من |I| مدخلًا مُزاحًا و|O| مخرجًا. تسع مقارنات في الشريحة 112.
Hash tableجدول التجزئةMerge sortالفرز بالدمج
Memory access patternنمط الوصول إلى الذاكرةRandom probes, one per output point per offsetاستعلامات عشوائية، واحد لكل نقطة خرج ولكل إزاحةTwo sequential streams, read onceتدفقان متسلسلان، يُقرأ كل منهما مرة واحدة
Parallel read hardwareعتاد القراءة المتوازيةN-by-N crossbar, O(N²) areaمصفوفة توصيل (crossbar) بحجم N في N، ومساحتها O(N²)Fixed-size bitonic merger with a forwarding loopدمّاج بيتوني (bitonic merger) ثابت الحجم مع حلقة تمرير (forwarding loop)
On-chip storageالتخزين على الشريحةTable can reach 160 MB at realistic load factorsقد يصل الجدول إلى 160 MB عند معاملات تحميل واقعيةSorted coordinate lists, no tableقوائم إحداثيات مرتبة، دون جدول
Result at equal parallelismالنتيجة عند التوازي نفسهBaselineخط الأساس (baseline)1.4x faster, up to 14x less areaأسرع بمقدار 1.4x، ومساحة أقل بما يصل إلى 14x
Hash table versus merge sort as the mapping engine (Lin et al., 2021, section 4.1)جدول التجزئة مقابل الفرز بالدمج كمحرك للربط (Lin et al., 2021, section 4.1)

One sorting unit, four point-cloud operationsوحدة فرز واحدة، وأربع عمليات على السحب النقطية

The reason PointAcc calls this block a mapping unit rather than a convolution helper is that sorting turns out to be the common core of every irregular operation a point-cloud network needs. Kernel mapping is an equality after a shift. Building the output cloud under a stride s is quantizing coordinates to the stride grid and then deduplicating, which sorting does by putting duplicates next to each other. Farthest point sampling picks the point with the largest distance, a top-1 of a ranking. k-nearest-neighbor search is a top-k of the same ranking, and ball query is a threshold on the sorted distances. The paper lists these as the operations the single ranking-based unit implements (Lin et al., 2021, sections 2.1 and 4.1). Flip the simulator above to stride 2 to see the output construction case: the five inputs collapse to fewer outputs before any offset is tried.

السبب في أن PointAcc يسمي هذه الكتلة وحدة ربط لا مساعد التفاف، هو أن الفرز يتبيّن أنه النواة المشتركة لكل عملية غير منتظمة تحتاجها شبكة السحب النقطية. ربط النواة (kernel mapping) هو تساوٍ بعد إزاحة. وبناء سحابة الخرج مع خطوة s هو تكميم الإحداثيات إلى شبكة الخطوة ثم إزالة التكرار، والفرز يفعل ذلك بوضع المكررات بجانب بعضها. وأخذ العينات بأبعد نقطة (farthest point sampling) يختار النقطة ذات المسافة الأكبر، أي أعلى عنصر (top-1) في ترتيب. والبحث عن أقرب k جيران (k-nearest-neighbor) هو أعلى k عناصر (top-k) في الترتيب نفسه، واستعلام الكرة (ball query) هو عتبة على المسافات المرتبة. وتدرج الورقة هذه العمليات على أنها ما تنفّذه الوحدة الواحدة القائمة على الترتيب (Lin et al., 2021, sections 2.1 and 4.1). غيّر المحاكي أعلاه إلى خطوة 2 لترى حالة بناء الخرج: تنهار المدخلات الخمسة إلى مخرجات أقل قبل تجربة أي إزاحة.

Recall

State the condition that makes input p and output q a pair for offset δ, and say what PointAcc does to turn it into an equality test.اذكر الشرط الذي يجعل الدخل p والخرج q زوجًا للإزاحة δ، وقل ماذا يفعل PointAcc لتحويله إلى اختبار تساوٍ.

p = q + δ. PointAcc shifts every input by −δ, merge-sorts the shifted inputs with the outputs, and reads every equal adjacent pair as a map entry.
p = q + δ. يزيح PointAcc كل دخل بمقدار −δ، ثم يفرز بالدمج المدخلات المُزاحة مع المخرجات، ويقرأ كل زوج متجاور متساوٍ على أنه مدخل في الخريطة.

Recall

For W−1,−1 on slide 111, which tuples come out, and why does the shift carry a plus sign?بالنسبة لـ W−1,−1 في الشريحة 111، ما الثلاثيات الناتجة، ولماذا تحمل الإزاحة إشارة موجبة؟

(P0, Q1, W−1,−1) and (P3, Q4, W−1,−1). The shift is −δ, and −(−1, −1) = (1, 1).
(P0, Q1, W−1,−1) و(P3, Q4, W−1,−1). الإزاحة هي −δ، و−(−1, −1) = (1, 1).

Recall

Give two reasons a hash table is a poor mapping unit on chip.أعطِ سببين يجعلان جدول التجزئة وحدة ربط سيئة على الشريحة.

Table size (up to 160 MB for a real point cloud) and random parallel reads, which need an N-by-N crossbar of O(N²) area.
حجم الجدول (حتى 160 MB لسحابة نقطية حقيقية)، والقراءات المتوازية العشوائية التي تحتاج إلى مصفوفة توصيل N في N مساحتها O(N²).

Quick checkاختبار سريع

For weight offset W1,1, the PointAcc mapping unit adds which vector to every input coordinate?بالنسبة لإزاحة الوزن W1,1، أي متجه تضيفه وحدة الربط في PointAcc إلى كل إحداثي دخل؟

Quick checkاختبار سريع

A parallel hash table is rejected as the mapping unit mainly because it needsيُستبعد جدول التجزئة المتوازي كوحدة للربط أساسًا لأنه يحتاج إلى

Slide 113 is a pair of bar charts with three baselines, and the baselines matter more than the bars. Red is an NVIDIA RTX 2080Ti, the server GPU that already runs TorchSparse-style code well. Dark grey is an Intel Xeon Skylake host paired with a TPU V3, a dense-matmul accelerator that has to send every mapping operation back to the host. Light grey is an Intel Xeon Gold 6130 CPU alone. The right-most group, GeoMean, is the geometric mean across the eight networks, so no single network dominates the average.

الشريحة 113 زوج من المخططات الشريطية بثلاثة خطوط أساس، وخطوط الأساس أهم من الأعمدة نفسها. الأحمر هو NVIDIA RTX 2080Ti، وهو GPU خوادم يشغّل كود على نمط TorchSparse جيدًا أصلًا. والرمادي الداكن هو معالج مضيف Intel Xeon Skylake مقترن بـ TPU V3، وهو مسرّع لضرب المصفوفات الكثيفة يضطر إلى إرسال كل عملية ربط إلى المضيف. والرمادي الفاتح هو معالج Intel Xeon Gold 6130 وحده. والمجموعة في أقصى اليمين، GeoMean، هي المتوسط الهندسي عبر الشبكات الثماني، فلا تهيمن شبكة واحدة على المتوسط.

Geometric means from slide 113 on a log axis: 3.7x, 53x and 90x speedup, then 22x, 210x and 176x energy saving over the GPU, the TPU system and the CPU. The last bar uses the paper's 176x where the slide prints 193x.المتوسطات الهندسية من الشريحة 113 على محور لوغاريتمي: تسريع 3.7x و53x و90x، ثم توفير طاقة 22x و210x و176x مقارنةً بـ GPU ونظام TPU و CPU. العمود الأخير يستخدم قيمة الورقة 176x بينما تطبع الشريحة 193x.

Start with the GeoMean row and read the two charts together. Against the GPU, PointAcc is 3.7x faster and 22x more energy efficient. Against the TPU system it is 53x faster and saves 210x energy. Against the CPU it is 90x faster and saves 176x (the slide prints 193x, see the errata below). The paper's abstract leads with the GPU pair, 3.7x and 22x over an RTX 2080Ti, evaluated on eight models across four applications (Lin et al., 2021).

ابدأ بصف GeoMean واقرأ المخططين معًا. مقارنةً بـ GPU، يكون PointAcc أسرع بمقدار 3.7x وأكفأ في الطاقة بمقدار 22x. ومقارنةً بنظام TPU يكون أسرع بمقدار 53x ويوفّر 210x من الطاقة. ومقارنةً بـ CPU يكون أسرع بمقدار 90x ويوفّر 176x (تطبع الشريحة 193x، انظر تصحيح الشريحة أدناه). ويبدأ ملخص الورقة بزوج GPU: 3.7x و22x مقارنةً بـ RTX 2080Ti، مع تقييم على ثمانية نماذج عبر أربعة تطبيقات (Lin et al., 2021).

NetworkالشبكةSpeedup vs 2080Tiالتسريع مقارنةً بـ 2080TiSpeedup vs TPU V3التسريع مقارنةً بـ TPU V3Speedup vs Gold 6130التسريع مقارنةً بـ Gold 6130Energy vs 2080Tiالطاقة مقارنةً بـ 2080TiEnergy vs TPU V3الطاقة مقارنةً بـ TPU V3Energy vs Gold 6130الطاقة مقارنةً بـ Gold 6130
PointNetPointNet3.73.7272712712718181,3191,319172172
PointNet++ (c)PointNet++ (c)2.82.811311397971414169169119119
PointNet++ (ps)PointNet++ (ps)2.82.83737828225259999152152
DGCNNDGCNN3.73.73.43.46565272738389191
F-PointNet++F-PointNet++3.73.72692691311311616682682394394
PointNet++ (s)PointNet++ (s)4.74.788881061064545161161221221
MinkNet(i)MinkNet(i)8.38.310210294943636324324268268
MinkNet(o)MinkNet(o)2.42.4717151511313127127139139
GeoMeanGeoMean3.73.7535390902222210210193 (paper: 176)193 (في الورقة: 176)
Every number printed on slide 113 (speedup and energy saving, higher is better for PointAcc)كل رقم مطبوع في الشريحة 113 (التسريع وتوفير الطاقة، والأعلى أفضل لـ PointAcc)

The network names encode the benchmark. The PointNet++ suffixes are (c) classification, (ps) part segmentation and (s) semantic segmentation. F-PointNet++ is the frustum detector built on PointNet++. MinkNet(i) and MinkNet(o) are MinkowskiUNet on an indoor dataset (S3DIS) and an outdoor dataset (SemanticKITTI), the two sparse-convolution workloads closest to part 11 (Lin et al., 2021, Table 2).

أسماء الشبكات تشير إلى معيار القياس (benchmark). لواحق PointNet++ هي (c) للتصنيف (classification)، و(ps) لتقسيم الأجزاء (part segmentation)، و(s) للتقسيم الدلالي (semantic segmentation). وF-PointNet++ هو كاشف المخروط الناقص (frustum detector) المبني على PointNet++. وMinkNet(i) وMinkNet(o) هما MinkowskiUNet على مجموعة بيانات داخلية (S3DIS) ومجموعة بيانات خارجية (SemanticKITTI)، وهما أقرب أحمال الالتفاف المتناثر إلى الجزء 11 (Lin et al., 2021, Table 2).

Why the TPU column swings from 3.4x to 269xلماذا يتأرجح عمود TPU من 3.4x إلى 269x

The GPU column is flat, between 2.4x and 8.3x, because a GPU handles both the mapping and the matmuls in the same memory. The TPU column ranges from 3.4x on DGCNN to 269x on F-PointNet++, and the spread is the lesson of the whole part. The paper attributes the gain over the TPU mainly to supporting mapping operations on chip (Lin et al., 2021, section 5.2). The paper does not break that number down per network, so the following is a reading of the chart, not a quoted result. DGCNN's neighbor search is a pairwise-distance computation in feature space, recomputed inside every EdgeConv layer, and a dense matmul unit already runs that well, so it has the least mapping work to move on chip. F-PointNet++ and the segmentation variants of PointNet++ are dominated by sampling, neighbor search and gathering, exactly the operations the TPU must hand back to the host, so removing that round trip is worth two orders of magnitude.

عمود GPU مستوٍ تقريبًا، بين 2.4x و8.3x، لأن GPU يتعامل مع الربط وضرب المصفوفات في الذاكرة نفسها. أما عمود TPU فيتراوح من 3.4x على DGCNN إلى 269x على F-PointNet++، وهذا التفاوت هو درس الجزء كله. تنسب الورقة المكسب مقارنةً بـ TPU أساسًا إلى دعم عمليات الربط على الشريحة (Lin et al., 2021, section 5.2). ولا تفصّل الورقة هذا الرقم لكل شبكة، لذا فما يلي قراءة للمخطط وليس نتيجة منقولة. البحث عن الجيران في DGCNN هو حساب مسافات زوجية في فضاء الخصائص، يُعاد حسابه داخل كل طبقة EdgeConv، ووحدة ضرب المصفوفات الكثيفة تنفّذ ذلك جيدًا أصلًا، فيكون لديه أقل قدر من عمل الربط الذي يُنقل إلى الشريحة. أما F-PointNet++ ونسخ التقسيم من PointNet++ فتهيمن عليها عمليات أخذ العينات والبحث عن الجيران والجمع (gathering)، وهي بالضبط العمليات التي يجب على TPU إعادتها إلى المضيف، لذلك فإن إزالة هذه الرحلة ذهابًا وإيابًا تساوي رتبتين عشريتين من التحسين.

Recall

Slide 113 prints 193 for the CPU energy GeoMean. Using the definition of a geometric mean and the eight per-network bars, how would you check it?تطبع الشريحة 113 القيمة 193 لـ GeoMean طاقة CPU. باستخدام تعريف المتوسط الهندسي والأعمدة الثمانية لكل شبكة، كيف تتحقق منها؟

Multiply the eight CPU energy values (172, 119, 152, 91, 394, 221, 268, 139) and take the eighth root, or average their logarithms. The result is 176, matching the paper and not the slide.
اضرب قيم طاقة CPU الثماني (172، 119، 152، 91، 394، 221، 268، 139) وخذ الجذر الثامن، أو خذ متوسط لوغاريتماتها. الناتج 176، وهو يطابق الورقة لا الشريحة.

Recall

Quote PointAcc's geometric-mean speedup and energy saving over the RTX 2080Ti, and name the other two baselines on slide 113.اذكر التسريع وتوفير الطاقة بالمتوسط الهندسي لـ PointAcc مقارنةً بـ RTX 2080Ti، وسمِّ خطّي الأساس الآخرين في الشريحة 113.

3.7x speedup and 22x energy saving. The other baselines are an Intel Xeon Skylake with a TPU V3 and an Intel Xeon Gold 6130.
تسريع 3.7x وتوفير طاقة 22x. وخطا الأساس الآخران هما Intel Xeon Skylake مع TPU V3، وIntel Xeon Gold 6130.

Quick checkاختبار سريع

On slide 113, what is PointAcc's speedup on DGCNN over the Xeon Skylake plus TPU V3 system, the smallest entry in that column?في الشريحة 113، ما تسريع PointAcc على DGCNN مقارنةً بنظام Xeon Skylake مع TPU V3، وهو أصغر قيمة في ذلك العمود؟

Slide 114 compresses the lecture into two bullets: automated ways to find pruning ratios, and system and hardware support for different granularities. Those two bullets are two separate questions from the five that opened the deck. The first asks how much to remove from each layer. The second asks how the zeros you created turn into time and energy actually saved. Neither is worth much without the other.

تضغط الشريحة 114 المحاضرة في نقطتين: طرق مؤتمتة لإيجاد نسب التقليم (pruning ratios)، ودعم الأنظمة والعتاد للحبيبيات المختلفة. هاتان النقطتان سؤالان منفصلان من الأسئلة الخمسة التي افتُتحت بها الشرائح. الأول يسأل كم نزيل من كل طبقة. والثاني يسأل كيف تتحول الأصفار التي صنعتها إلى وقت وطاقة موفّرين فعلًا. ولا قيمة كبيرة لأي منهما دون الآخر.

Left ladder: three ways to choose per-layer ratios. Right ladder: four systems that turn zeros into savings. Both lead to the next lecture, which shrinks the bits of the weights that remain.السلّم الأيسر: ثلاث طرق لاختيار النسب لكل طبقة. السلّم الأيمن: أربعة أنظمة تحوّل الأصفار إلى توفير. وكلاهما يؤدي إلى المحاضرة التالية، التي تقلّص عدد بتات الأوزان المتبقية.

Thread one: choosing the ratioالخيط الأول: اختيار النسبة

Sensitivity analysis prunes one layer at a time across a sweep of ratios, plots accuracy against ratio, and reads each layer's rate where its curve crosses an accuracy threshold. It is cheap and transparent, and its weakness is that it ignores Layer interaction: the compounding loss when many layers are pruned together, which is why its per-layer rates are only a starting point. AMC (AutoML for Model Compression) replaces the human with a DDPG agent that sees a layer embedding and emits a continuous sparsity ratio, rewarded by accuracy under a FLOPs or latency budget. NetAdapt keeps a rule instead of a policy: cut latency by a fixed step, choose the layer whose short-term fine-tuned accuracy is highest, consult a measured latency lookup table rather than FLOPs, repeat until the budget is met, then long-term fine-tune. Whichever chooses the ratios, Fine-tuning and Iterative pruning are what recover the accuracy afterwards.

تحليل الحساسية (sensitivity analysis) يقلّم طبقة واحدة في كل مرة عبر مجموعة من النسب، ويرسم الدقة مقابل النسبة، ويقرأ معدل كل طبقة عند النقطة التي يعبر فيها منحناها عتبة الدقة (accuracy threshold). وهو رخيص وشفاف، ونقطة ضعفه أنه يتجاهل تفاعل الطبقات (layer interaction): الخسارة المتراكمة عندما تُقلَّم طبقات كثيرة معًا، ولهذا فإن معدلاته لكل طبقة ليست إلا نقطة بداية. أما AMC فيستبدل الإنسان بوكيل DDPG يرى تمثيلًا (embedding) للطبقة ويُخرج نسبة تناثر متصلة، ويُكافأ بالدقة تحت ميزانية من FLOPs أو زمن الاستجابة (latency). وNetAdapt يحتفظ بقاعدة بدلًا من سياسة: اخفض زمن الاستجابة بخطوة ثابتة، واختر الطبقة التي تكون دقتها بعد الضبط الدقيق قصير المدى (short-term fine-tuning) هي الأعلى، واستعن بجدول بحث (lookup table) لزمن الاستجابة المقيس بدلًا من FLOPs، وكرّر حتى تتحقق الميزانية، ثم طبّق الضبط الدقيق طويل المدى (long-term fine-tuning). وأيًّا كان من يختار النسب، فإن الضبط الدقيق (fine-tuning) والتقليم التكراري (iterative pruning) هما ما يستعيد الدقة بعد ذلك.

Thread two: making the zeros payالخيط الثاني: جعل الأصفار مُربحة

A pruned weight is only free if the hardware skips it. EIE (Efficient Inference Engine) skips two kinds at once: static Weight sparsity stored in CSC form across an array of processing elements, and dynamic activation sparsity caught by leading non-zero detection so that a zero activation is never broadcast. NVIDIA Ampere tensor cores accept 2:4 sparsity only, and in return the Sparse tensor core uses the two-bit metadata to select operands and doubles math throughput (Mishra et al., 2021). TorchSparse handles the sparsity of point-cloud inputs in software by trading a little padding for regular batched matmuls through Adaptive grouping, and TorchSparse++ overlaps the gather and scatter with compute. PointAcc moves the same problem into hardware, with the merge-sort mapping unit of the previous concept. The granularity is the thread joining all four: the finer the sparsity, the more bookkeeping the system must do to skip it, and the coarser the sparsity, the more the pruning method must give up to fit the pattern.

الوزن المقلَّم لا يكون مجانيًا إلا إذا تخطّاه العتاد. EIE يتخطى نوعين معًا: تناثر الأوزان (weight sparsity) الثابت المخزّن بصيغة CSC عبر مصفوفة من عناصر المعالجة (processing elements)، وتناثر التفعيلات الديناميكي الذي يُلتقط بـكشف أول قيمة غير صفرية (leading non-zero detection) بحيث لا يُبث تفعيل صفري أبدًا. وأنوية NVIDIA Ampere الموترية لا تقبل إلا تناثر 2:4، وفي المقابل تستخدم النواة الموترية المتناثرة (sparse tensor core) البيانات الوصفية ذات البتين لاختيار المعاملات (operands) وتضاعف إنتاجية الحساب (Mishra et al., 2021). ويتعامل TorchSparse مع تناثر مدخلات السحب النقطية برمجيًا، مقايضًا قليلًا من الحشو (padding) بعمليات ضرب مصفوفات منتظمة ومجمّعة عبر التجميع التكيفي (adaptive grouping)، ويُداخل TorchSparse++ عمليتي الجمع والتوزيع (gather وscatter) مع الحساب. وينقل PointAcc المسألة نفسها إلى العتاد، بوحدة الربط القائمة على الفرز بالدمج من المفهوم السابق. والحبيبية (granularity) هي الخيط الذي يربط الأربعة: كلما كان التناثر أدق، زادت المحاسبة التي يجب أن يقوم بها النظام لتخطيه، وكلما كان التناثر أخشن، زاد ما يجب أن تتنازل عنه طريقة التقليم لتلائم النمط.

SparsityالتناثرWhere it comes fromمصدرهGranularity neededالحبيبية المطلوبةSystemالنظامMechanismالآلية
Fine-grained weightتناثر الأوزان الدقيق (fine-grained)Pruning, staticالتقليم، ثابتIrregular, individual weightsغير منتظم، على مستوى الأوزان المفردةEIEEIECSC storage, PE array, weight sharing, skip zero weightsتخزين CSC، ومصفوفة عناصر معالجة (PE array)، ومشاركة الأوزان (weight sharing)، وتخطي الأوزان الصفرية
M:N weight (2:4)تناثر الأوزان M:N (2:4)Pruning with a pattern, staticالتقليم وفق نمط، ثابت2 nonzeros in every 4 along a rowقيمتان غير صفريتين في كل 4 على امتداد الصفNVIDIA Ampere sparse tensor coresأنوية NVIDIA Ampere الموترية المتناثرة2-bit metadata selects the paired activations, 2x math throughputبيانات وصفية (metadata) من بتين تختار التفعيلات المقابلة، وإنتاجية حساب مضاعفة 2x
Activation (ReLU zeros)تناثر التفعيلات (أصفار ReLU)ReLU at run time, dynamicدالة ReLU أثناء التشغيل، ديناميكيElement levelعلى مستوى العنصرEIEEIELeading non-zero detection, never broadcast a zeroكشف أول قيمة غير صفرية (leading non-zero detection)، وعدم بث أي صفر أبدًا
Activation (sparse point-cloud inputs)تناثر التفعيلات (مدخلات السحب النقطية المتناثرة)Data occupancy, dynamicإشغال البيانات، ديناميكيPoint (coordinate) levelعلى مستوى النقطة (الإحداثي)TorchSparse (software), PointAcc (hardware)TorchSparse (برمجيات)، وPointAcc (عتاد)Maps plus gather, matmul, scatter with adaptive grouping; merge-sort mapping unitخرائط مع الجمع ثم ضرب المصفوفات ثم التوزيع (gather, matmul, scatter) بالتجميع التكيفي (adaptive grouping)؛ ووحدة ربط بالفرز بالدمج
Sparsity types in this lecture and the systems that exploit themأنواع التناثر في هذه المحاضرة والأنظمة التي تستغلها

The bridge to the next lectureالجسر إلى المحاضرة التالية

Pruning removes weights. Quantization shrinks the ones that stay. Slide 114 sets the order for the next lecture: first the numeric data types modern computer systems actually offer, then the basic concept of neural network quantization, then the common quantization methods. The two techniques are complementary in the deep compression sense: after pruning left AlexNet with a ninth of its connections, quantizing and coding the survivors is what pushed the total to 35x in Han et al.'s pipeline, and both will show up together in the memory and energy arguments of the next lecture (Han, Mao and Dally, 2016).

التقليم يزيل الأوزان. والتكميم يقلّص الأوزان التي تبقى. تحدد الشريحة 114 ترتيب المحاضرة التالية: أولًا أنواع البيانات العددية التي توفرها أنظمة الحاسوب الحديثة فعلًا، ثم المفهوم الأساسي لتكميم الشبكات العصبية، ثم طرق التكميم الشائعة. والتقنيتان متكاملتان بمعنى الضغط العميق (deep compression): بعد أن ترك التقليم شبكة AlexNet بتُسع وصلاتها، كان تكميم الأوزان الباقية وترميزها هو ما دفع الإجمالي إلى 35x في خط معالجة Han et al.، وستظهر التقنيتان معًا في حجج الذاكرة والطاقة في المحاضرة التالية (Han, Mao and Dally, 2016).

Recall

Name the three automated ways to find pruning ratios from this lecture and one weakness of the first.سمِّ الطرق المؤتمتة الثلاث لإيجاد نسب التقليم في هذه المحاضرة، ونقطة ضعف واحدة للأولى.

Sensitivity analysis, AMC and NetAdapt. Sensitivity analysis sweeps one layer at a time and so ignores layer interaction.
تحليل الحساسية، وAMC، وNetAdapt. تحليل الحساسية يمسح طبقة واحدة في كل مرة، ولذلك يتجاهل تفاعل الطبقات.

Recall

Which two topics open the next lecture before the quantization methods?ما الموضوعان اللذان تبدأ بهما المحاضرة التالية قبل طرق التكميم؟

Numeric data types in modern computer systems, then the basic concept of neural network quantization.
أنواع البيانات العددية في أنظمة الحاسوب الحديثة، ثم المفهوم الأساسي لتكميم الشبكات العصبية.

Quick checkاختبار سريع

Which system on slide 55 is paired with M:N weight sparsity?أي نظام في الشريحة 55 يقترن بتناثر الأوزان M:N؟

Slide 115 lists nineteen references. Read as a map of the lecture they fall into six groups: foundations of model compression and energy (items 1, 2, 4, 5, 6), pruning criteria (3, 12, 13, 15), structured and channel pruning (7, 10, 11, 14, 16, 17), automated ratio search (9), hardware support (8), and one-shot pruning of large language models (18), with Prof. Han's TinyML course (19) as the source the whole deck follows. The Sources block at the end of this part gives a link for each one that has an archival home.

تدرج الشريحة 115 تسعة عشر مرجعًا. وإذا قرأتها كخريطة للمحاضرة فهي تنقسم إلى ست مجموعات: أسس ضغط النماذج والطاقة (البنود 1, 2, 4, 5, 6)، ومعايير التقليم (3, 12, 13, 15)، والتقليم المهيكل وتقليم القنوات (7, 10, 11, 14, 16, 17)، والبحث المؤتمت عن النسب (9)، ودعم العتاد (8)، والتقليم دفعة واحدة (one-shot) لنماذج اللغة الكبيرة (18)، مع مقرر TinyML للبروفيسور Han (19) بوصفه المصدر الذي تتبعه الشرائح كلها. وكتلة المصادر في نهاية هذا الجزء تعطي رابطًا لكل مرجع له موطن أرشيفي.

Where the references land in this lectureأين تقع المراجع في هذه المحاضرة

Foundationsالأسس
Deng et al. 2020 survey; Horowitz 2014 on the energy of memory access; Han et al. 2015; Han's Stanford thesis; Walsh 2013 on Huttenlocher's synapse countsالمسح الذي أعدّه Deng et al. 2020؛ وHorowitz 2014 عن طاقة الوصول إلى الذاكرة؛ وHan et al. 2015؛ وأطروحة Han في Stanford؛ وWalsh 2013 عن أعداد المشابك العصبية لدى Huttenlocher
Criteriaمعايير التقليم
LeCun et al. 1989 Optimal Brain Damage; Molchanov et al. 2017 and 2019 Taylor ranking; Wang's first-order Taylor noteLeCun et al. 1989 Optimal Brain Damage؛ والترتيب بمتسلسلة تايلور (Taylor ranking) لدى Molchanov et al. في 2017 و2019؛ ومذكرة Wang عن تايلور من الرتبة الأولى
Structured pruningالتقليم المهيكل
Mao et al. on granularity; Wen et al. 2016; Liu et al. 2017 Network Slimming; Hu et al. Network Trimming; He et al. 2017 channel pruning; Luo et al. 2017 ThiNetMao et al. عن الحبيبية؛ وWen et al. 2016؛ وLiu et al. 2017 Network Slimming؛ وHu et al. Network Trimming؛ وتقليم القنوات لدى He et al. 2017؛ وLuo et al. 2017 ThiNet
Automationالأتمتة
He et al. 2018 AMCHe et al. 2018 AMC
Hardwareالعتاد
NVIDIA Ampere and TensorRT sparsity blogتدوينة NVIDIA عن التناثر في Ampere وTensorRT
Large modelsالنماذج الكبيرة
Frantar and Alistarh 2023 SparseGPTFrantar and Alistarh 2023 SparseGPT
Courseالمقرر
Prof. Han's TinyML course (MIT 6.5940)مقرر TinyML للبروفيسور Han (MIT 6.5940)

The list is also worth checking against the slides themselves, because several of the papers this lecture leaned on hardest are cited in slide footers but never make it to the reference page. Every hardware system in the second half of the deck is in that position. If you cite from this lecture in your own writing, take the references from the Sources below rather than from slide 115.

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

Recall

Which two hardware papers from this lecture are missing from the reference slide?ما ورقتا العتاد في هذه المحاضرة الغائبتان عن شريحة المراجع؟

EIE (Han et al., ISCA 2016) and PointAcc (Lin et al., MICRO 2021). NetAdapt, Mishra et al. 2021 and TorchSparse are missing too.
EIE (Han et al., ISCA 2016) وPointAcc (Lin et al., MICRO 2021). كما أن NetAdapt وMishra et al. 2021 وTorchSparse غائبة أيضًا.

Recapالخلاصة

If you remember nothing elseإن لم تتذكر شيئاً آخر فتذكّر هذا

  • Sparse convolution pairs input p with output q for offset δ exactly when p = q + δ. PointAcc tests this as an equality after shifting every input by −δ.الالتفاف المتناثر (sparse convolution) يقرن الدخل p بالخرج q عبر الإزاحة δ إذا وفقط إذا كان p = q + δ. ويختبر PointAcc هذا الشرط كتساوٍ بعد إزاحة كل دخل بمقدار −δ.
  • The mapping unit merge-sorts the shifted inputs with the outputs. Equal adjacent neighbors are map entries, found with |I| + |O| − 1 local comparisons and no random SRAM reads.وحدة الربط (mapping unit) تفرز بالدمج المدخلاتِ المُزاحة مع المخرجات. والجيران المتجاوران المتساويان هم مدخلات الخريطة، ويُعثر عليهم بعدد |I| + |O| − 1 من المقارنات المحلية دون أي قراءة عشوائية من SRAM.
  • On slide 112, W_1,1 yields (P1, Q0) and (P4, Q3). On slide 111, W_-1,-1 yields (P0, Q1) and (P3, Q4). The two lists are the same pairs with roles swapped.في الشريحة 112، تعطي W_1,1 الزوجين (P1, Q0) و(P4, Q3). وفي الشريحة 111، تعطي W_-1,-1 الزوجين (P0, Q1) و(P3, Q4). والقائمتان هما الأزواج نفسها مع تبادل الأدوار.
  • A parallel hash table needs an O(N²) crossbar and a table that can reach 160 MB. The merge-sort unit is 1.4x faster and up to 14x smaller at equal parallelism.جدول التجزئة المتوازي يحتاج إلى مصفوفة توصيل (crossbar) بحجم O(N²) وجدول قد يصل إلى 160 MB. أما وحدة الفرز بالدمج فأسرع بمقدار 1.4x وأصغر بما يصل إلى 14x عند التوازي نفسه.
  • One ranking kernel also serves farthest point sampling, kNN and ball query. Stride downsampling uses coordinate quantization instead.نواة ترتيب (ranking) واحدة تخدم أيضًا أخذ العينات بأبعد نقطة (farthest point sampling) وبحث kNN واستعلام الكرة (ball query). أما تقليل الدقة بالخطوة (stride downsampling) فيستخدم تكميم الإحداثيات بدلًا من ذلك.
  • PointAcc geomean: 3.7x, 53x and 90x speedup and 22x, 210x and 176x energy saving (slide 113 prints 193x for the last one) over an RTX 2080Ti, a Xeon Skylake plus TPU V3, and a Xeon Gold 6130.المتوسط الهندسي لـ PointAcc: تسريع 3.7x و53x و90x، وتوفير طاقة 22x و210x و176x (تطبع الشريحة 113 القيمة 193x للأخير) مقارنةً بـ RTX 2080Ti، وXeon Skylake مع TPU V3، وXeon Gold 6130.
  • Ratio methods: sensitivity analysis, AMC, NetAdapt. Systems: EIE (weight plus activation), Ampere tensor cores (M:N), TorchSparse and PointAcc (activation sparsity from sparse inputs).طرق تحديد النسب: تحليل الحساسية (sensitivity analysis)، وAMC، وNetAdapt. والأنظمة: EIE (الأوزان مع التفعيلات)، وأنوية Ampere الموترية (M:N)، وTorchSparse وPointAcc (تناثر التفعيلات الناتج عن المدخلات المتناثرة).
  • Next lecture: numeric data types, the basic concept of quantization, common quantization methods.المحاضرة التالية: أنواع البيانات العددية، والمفهوم الأساسي للتكميم، وطرق التكميم الشائعة.
  • Slide 115 omits NetAdapt, EIE, Mishra et al. 2021, TorchSparse, TorchSparse++ and PointAcc, and dates Hu et al. to 2017 when the paper appeared in 2016.تُغفل الشريحة 115 كلًا من NetAdapt وEIE وMishra et al. 2021 وTorchSparse وTorchSparse++ وPointAcc، وتؤرّخ Hu et al. بعام 2017 مع أن الورقة ظهرت عام 2016.

Sourcesالمصادر