What K-means saves at runtime, and the road to linear quantizationماذا يوفر K-means وقت التشغيل، والطريق إلى التكميم الخطي

Follow one weight of the running example through inference. The top-left weight was 2.09. In storage it is now the 2-bit index 3. When the convolution needs it, the hardware reads 3, looks up entry 3 of the Codebook, gets the FP32 value 2.00, and hands 2.00 to an ordinary floating-point multiplier, which multiplies it by an FP32 input activation. The 2-bit form existed only between the disk and the lookup.

تابع وزنًا واحدًا من المثال الجاري عبر الاستدلال. الوزن في أعلى اليسار كان 2.09. في التخزين أصبح الآن الفهرس ذا 2-bit وقيمته 3. عندما يحتاجه الالتفاف (convolution)، يقرأ العتاد 3، ويبحث عن المدخل 3 في codebook، فيحصل على القيمة 2.00 بصيغة FP32، ويسلّم 2.00 إلى ضارب عادي بالفاصلة العائمة، فيضربه في تفعيل دخل (input activation) بصيغة FP32. صيغة 2-bit لم توجد إلا بين القرص وعملية البحث.

Slide 42 draws this as a small dataflow graph. At the bottom sit the quantized weights and the float codebook. They enter a decode block on an edge labelled uint. Every edge after decode is labelled float: decoded weights and float inputs enter Conv, a float bias is added, ReLU runs, and float outputs leave. The two bullets under the figure state the consequence plainly: the weights are decompressed using a lookup table during runtime inference, and K-means-based weight quantization only saves the storage cost of the model, because all the computation and memory access are still floating point.

ترسم الشريحة 42 هذا كمخطط صغير لتدفق البيانات (dataflow). في الأسفل تجلس الأوزان المكمَّمة و الـ codebook العائم. يدخلان كتلة decode عبر حافة مكتوب عليها uint. كل حافة بعد decode مكتوب عليها float: الأوزان المفكوكة والمدخلات العائمة تدخل Conv، ثم يُضاف bias عائم، ثم يعمل ReLU، وتخرج مخرجات عائمة. النقطتان تحت الشكل تصرّحان بالنتيجة بوضوح: الأوزان يُفك ضغطها باستخدام جدول بحث (lookup table) أثناء الاستدلال وقت التشغيل، وتكميم الأوزان المبني على K-means يوفّر كلفة تخزين النموذج فقط، لأن كل الحسابات والوصول إلى الذاكرة ما زالت بالفاصلة العائمة.

So what does it save? Bytes moved, not operationsإذن ماذا يوفّر؟ البايتات المنقولة، لا العمليات

"Only storage" sounds like a small win until you remember where the energy goes. EIE's Table I (Han et al., ISCA 2016, 45 nm) puts a 32-bit DRAM read at 640 pJ and an FP32 multiply at 3.7 pJ. A model whose weights live off chip spends far more energy fetching them than multiplying them. If the stored form is what crosses the DRAM bus, and the lookup happens on chip, then the indexes are what get fetched and the saving in traffic equals the saving in storage.

"التخزين فقط" تبدو مكسبًا صغيرًا حتى تتذكر أين تذهب الطاقة. الجدول I في ورقة EIE (Han et al., ISCA 2016، بتقنية 45 nm) يضع قراءة 32-bit من DRAM عند 640 pJ وعملية ضرب FP32 عند 3.7 pJ. النموذج الذي تعيش أوزانه خارج الشريحة يصرف طاقة في جلبها أكثر بكثير مما يصرفه في ضربها. فإذا كانت الصيغة المخزّنة هي ما يعبر ناقل DRAM، وكان البحث في الجدول يحدث على الشريحة، فالفهارس هي ما يُجلب، ويكون التوفير في النقل مساويًا للتوفير في التخزين.

Read the slide's phrase "memory access is still floating point" with this in mind. The off-chip weight traffic does shrink, because indexes are fetched and decoded on chip. What stays floating point is everything the datapath touches after decode: the decoded weights fed to the multipliers, the input and output activations (which K-means never quantizes), the partial sums and the bias. Deep Compression itself notes that the forward pass has "one level of indirection" through the weight table, and that standard sparse libraries such as cuSPARSEand MKL did not support this indirect lookup, so speedups needed custom kernels or custom hardware. EIE is that hardware: it stores 4-bit indexes and expands each one through a table lookup before its arithmetic unit uses it.

اقرأ عبارة الشريحة "الوصول إلى الذاكرة ما زال بالفاصلة العائمة" وهذا في ذهنك. نقل الأوزان من خارج الشريحة يتقلّص فعلًا، لأن الفهارس هي ما يُجلب ثم تُفك على الشريحة. ما يبقى بالفاصلة العائمة هو كل ما يلمسه مسار البيانات (datapath) بعد decode: الأوزان المفكوكة التي تُغذّى إلى الضوارب، وتفعيلات الدخل والخرج (التي لا يكمّمها K-means أبدًا)، والمجاميع الجزئية، والـ bias. ورقة Deep Compression نفسها تذكر أن التمرير الأمامي فيه "مستوى واحد من الإحالة غير المباشرة" (one level of indirection) عبر جدول الأوزان، وأن مكتبات المصفوفات المتناثرة القياسية مثل cuSPARSE و MKL لم تكن تدعم هذا البحث غير المباشر، فكانت التسريعات تحتاج إلى نوى (kernels) مخصّصة أو عتاد مخصّص. و EIE هو ذلك العتاد: يخزّن فهارس 4-bit ويوسّع كل واحد منها عبر بحث في جدول قبل أن تستخدمه وحدته الحسابية.

Take the stored integer 1 from the top-left of slide 43's third matrix. Subtract -1, giving 2. Multiply by 1.07, giving 2.14. The original weight was 2.09. Now take the integer -2 just to its right: -2 - (-1) = -1, times 1.07 is -1.07, against an original -0.98. No table was consulted. The value came out of one subtraction and one multiplication, the same rule for every weight.

خذ العدد الصحيح المخزَّن 1 من أعلى يسار المصفوفة الثالثة في الشريحة 43. اطرح منه -1 فتحصل على 2. اضرب في 1.07 فتحصل على 2.14. الوزن الأصلي كان 2.09. الآن خذ العدد الصحيح -2 الذي على يمينه مباشرة: -2 - (-1) = -1، مضروبًا في 1.07 يساوي -1.07، مقابل قيمة أصلية -0.98. لم نستشر أي جدول. القيمة خرجت من عملية طرح واحدة وعملية ضرب واحدة، بالقاعدة نفسها لكل وزن.

That rule is Linear quantization, the second column of approaches from part 04. It is an affine map from integers to reals with two parameters, a scale S and a zero point Z:

تلك القاعدة هي linear quantization (التكميم الخطي)، العمود الثاني من النُّهج في الجزء 04. إنها تحويل تآلفي (affine) من الأعداد الصحيحة إلى الأعداد الحقيقية بمعاملين: مقياس (scale) S ونقطة صفر (zero point) Z:

With 2-bit signed integers (Two's complement, range -2 to 1) the four possible values are evenly spaced, one scale step apart. Here is the whole decode table for the example.

مع أعداد صحيحة بإشارة بحجم 2-bit (two's complement، المدى من -2 إلى 1) تكون القيم الأربع الممكنة متساوية التباعد، تفصل بين كل اثنتين خطوة مقياس واحدة. هذا جدول الفك الكامل للمثال.

Notice the colours on slide 43: the integer matrix uses the same four colour groups as the K-means clustering, and the integers are simply the K-means indexes shifted down by two (index 3 becomes 1, index 0 becomes -2). The grouping is the same; what changed is the meaning of the integer. In K-means it pointed into a table; here it is a number on a scaled number line. This is the Fixed-point number idea from part 01 generalised: a fixed-point value is an integer times a power-of-two scale, and a linearly quantized value is an offset integer times an arbitrary real scale.

لاحظ الألوان في الشريحة 43: مصفوفة الأعداد الصحيحة تستخدم مجموعات الألوان الأربع نفسها التي في تجميع K-means، والأعداد الصحيحة هي ببساطة فهارس K-means مُزاحة للأسفل بمقدار اثنين (الفهرس 3 يصبح 1، والفهرس 0 يصبح -2). التجميع هو نفسه؛ ما تغيّر هو معنى العدد الصحيح. في K-means كان يشير إلى مدخل في جدول؛ هنا هو عدد على خط أعداد مُقاس. هذه فكرة fixed point (الفاصلة الثابتة) من الجزء 01 بصورة معمّمة: القيمة ذات الفاصلة الثابتة هي عدد صحيح مضروب في مقياس من قوى العدد اثنين، والقيمة المكمَّمة خطيًا هي عدد صحيح مُزاح مضروب في مقياس حقيقي اعتباطي.

Why that buys integer arithmeticلماذا يمنحنا ذلك حسابًا بالأعداد الصحيحة

Because the map is affine, a dot product of quantized weights and quantized activations factors cleanly. Every term inside the sum is a product of small integers, so the multiply-accumulate loop runs entirely on integer hardware, and the real-valued scales are applied once per output, not once per weight. This is the scheme Jacob et al. built for integer-arithmetic-only inference on mobile CPUs, and lecture 05-2 derives it in full, including where S and Z come from.

لأن التحويل تآلفي، فإن الضرب النقطي (dot product) بين الأوزان المكمَّمة والتفعيلات المكمَّمة يتحلّل بشكل نظيف. كل حد داخل المجموع هو حاصل ضرب أعداد صحيحة صغيرة، فتعمل حلقة multiply-accumulate بالكامل على عتاد الأعداد الصحيحة، وتُطبَّق المقاييس الحقيقية مرة واحدة لكل خرج، وليس مرة لكل وزن. هذا هو المخطط الذي بناه Jacob et al. للاستدلال بالأعداد الصحيحة فقط على معالجات الهواتف، والمحاضرة 05-2 تشتقّه بالكامل، بما في ذلك من أين تأتي S و Z.

What it costs: a uniform grid fits this matrix worseما كلفته: الشبكة المنتظمة تلائم هذه المصفوفة بشكل أسوأ

K-means places its four values where the weights cluster: -1.00, 0.00, 1.50, 2.00. The linear grid must be evenly spaced: -1.07, 0, 1.07, 2.14. The cluster around 1.5 falls in the gap between 1.07 and 2.14 and rounds down, so 1.53 is stored as 1.07, a Quantization error of 0.46 where K-means made only 0.03.

يضع K-means قيمه الأربع حيث تتجمّع الأوزان: -1.00, 0.00, 1.50, 2.00. أما الشبكة الخطية فيجب أن تكون متساوية التباعد: -1.07, 0, 1.07, 2.14. المجموعة حول 1.5 تقع في الفجوة بين 1.07 و 2.14 وتُقرَّب للأسفل، فتُخزَّن 1.53 على أنها 1.07، أي quantization error (خطأ تكميم) قدره 0.46 حيث لم يتجاوز خطأ K-means القيمة 0.03.

This is the trade the whole quantization field lives on. Learned, non-uniform levels fit the weights better, but they cannot be computed with directly; the Gholami et al. survey notes that non-uniform schemes are typically hard to deploy efficiently on general hardware, which is why uniform quantization is the de facto choice. Uniform levels waste some precision, but in exchange both storage and arithmetic become integer. In practice 8-bit linear quantization has so many levels that the grid is fine enough for most layers; the 2-bit example here exaggerates the error to make the shape of the grid visible.

هذه هي المقايضة التي يقوم عليها مجال التكميم كله. المستويات المتعلَّمة غير المنتظمة تلائم الأوزان أفضل، لكن لا يمكن الحساب بها مباشرة؛ ويذكر مسح Gholami et al. أن المخططات غير المنتظمة يصعب عادةً نشرها بكفاءة على العتاد العام، ولهذا يكون التكميم المنتظم هو الخيار الفعلي السائد. المستويات المنتظمة تهدر بعض الدقة، لكن في المقابل يصبح التخزين والحساب كلاهما بالأعداد الصحيحة. عمليًا، التكميم الخطي بـ 8-bit فيه مستويات كثيرة بما يكفي لتكون الشبكة دقيقة بما يكفي لمعظم الطبقات؛ ومثال 2-bit هنا يضخّم الخطأ ليجعل شكل الشبكة مرئيًا.

The fourth column, Binary and ternary quantization, stays greyed out on the slide. It pushes the integer idea to one bit or three levels and is a later lecture.

العمود الرابع، binary/ternary quantization (التكميم الثنائي والثلاثي)، يبقى رماديًا على الشريحة. إنه يدفع فكرة الأعداد الصحيحة إلى بت واحد أو ثلاثة مستويات، وموضوعه محاضرة لاحقة.

If you went to slide 44 to find the paper behind the 3.2x codebook example or the 35x AlexNet result, you would not find it. The list there starts with a compression survey and Horowitz's energy paper, then runs through Optimal Brain Damage, AMC, network slimming, ThiNet, SparseGPT and other pruning work. Only two entries reach the quantization material, and only indirectly: Song Han's Stanford thesis (entry 5, which contains Deep Compression) and Prof. Han's TinyML course (entry 19, the origin of the slide figures). Slide 45 is a blank closing slide.

لو ذهبت إلى الشريحة 44 لتجد الورقة وراء مثال الـ codebook بنسبة 3.2x أو نتيجة 35x على AlexNet، فلن تجدها. القائمة هناك تبدأ بمسح عن الضغط وورقة Horowitz عن الطاقة، ثم تمر على Optimal Brain Damage و AMC و network slimming و ThiNet و SparseGPT وأعمال تقليم أخرى. مدخلان فقط يصلان إلى مادة التكميم، وبشكل غير مباشر: أطروحة Song Han في Stanford (المدخل 5، الذي يحتوي Deep Compression) ومقرر TinyML للبروفيسور Han (المدخل 19، مصدر أشكال الشرائح). الشريحة 45 شريحة ختامية فارغة.

For revision and for any citation in your own work, use the sources the lecture actually draws on. They are listed below and in the Sources section of this part.

للمراجعة، ولأي استشهاد في عملك الخاص، استخدم المصادر التي تعتمد عليها المحاضرة فعلًا. هي مدرجة أدناه وفي قسم المصادر (Sources) في هذا الجزء.

• Deep Compression is the source for weight sharing, the codebook, centroid fine-tuning and Huffman coding.Deep Compression هي مصدر مشاركة الأوزان (weight sharing)، والـ codebook، والضبط الدقيق للمراكز (centroid fine-tuning)، وترميز Huffman.
• SqueezeNet shows that compression stacks with a small architecture.SqueezeNet تُظهر أن الضغط يتراكم مع معمارية صغيرة.
• Jacob et al. is the source for the linear scheme previewed on slide 43 and developed in lecture 05-2.Jacob et al. هي مصدر المخطط الخطي الذي تقدّم الشريحة 43 لمحة عنه، والذي تطوّره المحاضرة 05-2.