Linear Quantized Matrix Multiplicationضرب المصفوفات المكمّم خطيًا

Start with something tiny: one weight and one input. Say the real weight is w = 0.5 and the real input is x = 1.5, so the real output is y = 0.75. In a quantized network none of these floats exist on the chip. What exists is three integer codes and, written next to each tensor, a scale and a zero point. The question is: given the codes q_w and q_x, which integer q_y should the chip write out, so that S_y(q_y - Z_y) is as close as possible to 0.75?

ابدأ بشيء صغير جداً: وزن واحد ومدخل واحد. لنقل إن الوزن الحقيقي w = 0.5 والمدخل الحقيقي x = 1.5، فيكون المخرج الحقيقي y = 0.75. في الشبكة المكمّمة لا يوجد أي من هذه الأعداد العشرية على الشريحة. الموجود هو ثلاثة رموز صحيحة (integer codes)، ومع كل مصفوفة scale وzero point مكتوبان بجانبها. والسؤال: بمعرفة الرمزين q_w وq_x، ما العدد الصحيح q_y الذي يجب أن تكتبه الشريحة كي تكون S_y(q_y - Z_y) أقرب ما يمكن إلى 0.75؟

The trick is to stop thinking about the codes and think about what they mean. Under Linear quantization, every tensor obeys the same Affine mapping: the real value equals its Scale (S) times the code minus its Zero point (Z). So wherever the real equation has a real number, you may substitute S(q - Z). The layer is Y = WX, and it is the source of the whole derivation.

الحيلة أن تتوقف عن التفكير في الرموز وتفكر في معناها. في Linear quantization تخضع كل مصفوفة للتحويل نفسه، Affine mapping: القيمة الحقيقية تساوي scale مضروباً في الرمز بعد طرح zero point منه. لذلك أينما ظهر عدد حقيقي في المعادلة الحقيقية يمكنك أن تعوّض مكانه S(q - Z). الطبقة هي Y = WX، وهي منطلق الاشتقاق كله.

Three lines of algebraثلاثة أسطر من الجبر

Substitute the affine map for all three tensors. The left side is the output, the right side the product of the two inputs:

عوّض التحويل affine للمصفوفات الثلاث. الطرف الأيسر هو المخرج، والطرف الأيمن حاصل ضرب المدخلين:

The scales are scalars, so they slide out of the product. Divide both sides by S_Y and move Z_Y to the right. This is the form to remember; it says the output code is a rescaled product of zero-shifted input codes, shifted by the output's zero point:

معاملات scale أعداد مفردة (scalars)، لذا تخرج من حاصل الضرب. اقسم الطرفين على S_Y وانقل Z_Y إلى الطرف الأيمن. هذه هي الصيغة التي يجب أن تحفظها؛ فهي تقول إن رمز المخرج هو حاصل ضرب رموز المدخلات بعد طرح نقاط الصفر منها، مُعاداً قياسه، ثم مُزاحاً بنقطة الصفر الخاصة بالمخرج:

Finally, multiply out the brackets. Nothing new happens mathematically, but this expanded form is the one that exposes the cost of each piece, which is what slides 12 to 14 are about:

أخيراً، افتح الأقواس. لا يحدث شيء جديد رياضياً، لكن هذه الصيغة المفكوكة هي التي تكشف تكلفة كل جزء، وهذا موضوع الشرائح 12 إلى 14:

That is the Quantized matrix multiplication. Notice what it buys. Every quantity inside the big bracket is an integer: codes and zero points. The only non-integer in the whole equation is the single factor S_W S_X / S_Y, a constant for the layer that you know before inference begins. So the expensive part, the inner products with millions of multiply-accumulates, can run on integer hardware, and the float only shows up once per output element at the very end. The construction comes from Jacob et al. (CVPR 2018), which is the source cited on every slide in this part.

هذا هو Quantized matrix multiplication. لاحظ ما يمنحك إياه. كل كمية داخل القوس الكبير عدد صحيح: رموز ونقاط صفر. والعدد غير الصحيح الوحيد في المعادلة كلها هو المعامل المفرد S_W S_X / S_Y، وهو ثابت للطبقة تعرفه قبل أن يبدأ الاستدلال. لذلك يمكن تنفيذ الجزء المكلف، أي الضرب الداخلي بملايين عمليات الضرب والجمع التراكمي (multiply-accumulate)، على عتاد الأعداد الصحيحة، ولا يظهر العدد العشري إلا مرة واحدة لكل عنصر من المخرج في النهاية تماماً. هذا البناء مأخوذ من Jacob et al. (CVPR 2018)، وهو المصدر المذكور في كل شريحة من هذا الجزء.

Look at the four terms inside the bracket and ask one question of each: does it change when the input image changes? q_W q_X obviously does: it is the matrix product itself. Z_W q_X does too, because it contains q_X. But Z_X q_W involves only the weights and the input zero point, both frozen after calibration, and Z_W Z_X is two constants. Those last two are the same for every image the model will ever see, so there is no reason to compute them more than once.

انظر إلى الحدود الأربعة داخل القوس واسأل كل حد سؤالاً واحداً: هل يتغير عندما تتغير صورة المدخل؟ q_W q_X يتغير بالطبع، فهو ضرب المصفوفات نفسه. وZ_W q_X يتغير أيضاً لأنه يحتوي على q_X. لكن Z_X q_W يتضمن الأوزان ونقطة الصفر للمدخل فقط، وكلاهما مُثبَّت بعد المعايرة، وZ_W Z_X عبارة عن ثابتين. هذان الحدان الأخيران متطابقان لكل صورة سيراها النموذج، لذلك لا داعي لحسابهما أكثر من مرة.

That is the logic of slide 12. The amber box marks -Z_X q_W + Z_W Z_X as precomputed: it is evaluated offline, when the model is converted, and stored as a constant per output. The big red box marks the whole bracket as N-bit integer multiplications with 32-bit integer additions and subtractions. The blue box on the left is the rescale, and the small box on the right is +Z_Y, an integer addition. Slide 14 adds the last label: the rescale converts back to an N-bit integer.

هذا منطق الشريحة 12. الصندوق الكهرماني (amber) يحدد -Z_X q_W + Z_W Z_X على أنه precomputed (محسوب مسبقاً): يُقيَّم offline عند تحويل النموذج، ويُخزَّن ثابتاً لكل مخرج. والصندوق الأحمر الكبير يحدد القوس كله على أنه عمليات ضرب صحيحة بـ N بت مع عمليات جمع وطرح صحيحة بـ 32 بت. الصندوق الأزرق على اليسار هو إعادة القياس، والصندوق الصغير على اليمين هو +Z_Y، وهو جمع صحيح. وتضيف الشريحة 14 التسمية الأخيرة: إعادة القياس تُرجع القيمة إلى عدد صحيح بـ N بت.

What the scalar notation hidesما تخفيه الكتابة بالأعداد المفردة

The slides write the terms as if q_W and q_X were single numbers. In a real layer they are matrices, and each output entry is a sum over the inner dimension K:

تكتب الشرائح الحدود كأن q_W وq_X عددان مفردان. في الطبقة الحقيقية هما مصفوفتان، وكل عنصر في المخرج مجموع على البعد الداخلي K:

Read it term by term. Z_W q_X is really Z_W times the column sum of q_X (one number per output column). Z_X q_W is really Z_X times the row sum of q_W (one number per output row). And Z_W Z_X is added once per k, so it appears multiplied by K. This is exactly how production kernels such as gemmlowp organize the computation: they compute the row and column sums during packing and add them as a correction afterwards.

اقرأها حداً حداً. Z_W q_X هو في الحقيقة Z_W مضروباً في مجموع عمود q_X (عدد واحد لكل عمود في المخرج). وZ_X q_W هو في الحقيقة Z_X مضروباً في مجموع صف q_W (عدد واحد لكل صف في المخرج). أما Z_W Z_X فيُضاف مرة لكل k، لذلك يظهر مضروباً في K. وهذا بالضبط ما تفعله النوى (kernels) المستخدمة في الإنتاج مثل gemmlowp: تحسب مجاميع الصفوف والأعمدة أثناء التعبئة (packing) ثم تضيفها تصحيحاً بعد ذلك.

Why the accumulator is 32 bitsلماذا المراكم 32 بت

The red box's label pairs N-bit multiplies with 32-bit additions, and the reason is a bit count. Two INT8 codes multiply to at most (-128) x (-128) = 16,384, which needs 16 signed bits. A dot product adds K of these, and each doubling of K can add one more bit, so the sum needs about 16 + log2(K) bits. That is why products go into an 32-bit accumulator: the width has room for the worst case of more than a hundred thousand terms, far more than any real layer has.

تسمية الصندوق الأحمر تقرن عمليات ضرب بـ N بت مع عمليات جمع بـ 32 بت، والسبب عدٌّ للبتات. حاصل ضرب رمزين من نوع INT8 لا يتجاوز (-128) x (-128) = 16,384، ويحتاج 16 بت بإشارة. الضرب النقطي (dot product) يجمع K من هذه النواتج، وكل مضاعفة لـ K قد تضيف بتاً واحداً، لذلك يحتاج المجموع نحو 16 + log2(K) بت. ولهذا تذهب النواتج إلى 32-bit accumulator: فعرضه يتسع لأسوأ حالة تزيد على مئة ألف حد، وهذا أكثر بكثير مما تملكه أي طبقة حقيقية.

Suppose the accumulator for one output holds 5,000 and the layer's rescale factor is M = S_W S_X / S_Y = 0.0072. The output code before adding Z_Y is 5,000 x 0.0072 = 36. Easy on a laptop. On a microcontroller with no floating-point unit, that multiply by 0.0072 is the one operation left in the equation that is not an integer operation. If it stays a float multiply, the promise of Integer-only inference breaks at the last step.

افترض أن المراكم لمخرج واحد يحمل 5,000 وأن معامل إعادة القياس للطبقة هو M = S_W S_X / S_Y = 0.0072. رمز المخرج قبل إضافة Z_Y هو 5,000 x 0.0072 = 36. أمر سهل على حاسوب محمول. لكن على متحكم دقيق بلا وحدة فاصلة عائمة (floating-point unit)، يكون الضرب في 0.0072 هو العملية الوحيدة المتبقية في المعادلة التي ليست عملية أعداد صحيحة. وإذا بقي ضرباً عشرياً، ينكسر وعد Integer-only inference في الخطوة الأخيرة.

The fix is to rewrite M so that it uses only things integer hardware does cheaply. Keep doubling 0.0072 until it lands in [0.5, 1): 0.0144, 0.0288, 0.0576, 0.1152, 0.2304, 0.4608, 0.9216. Seven doublings. So 0.0072 = 2^(-7) x 0.9216. Multiplying by 0.9216 is a Fixed-point multiplication, and multiplying by 2^(-7) is a right shift by seven bits. That is the M0 and bit shift decomposition of slide 13:

الحل أن نعيد كتابة M بحيث لا تستخدم إلا ما ينفذه عتاد الأعداد الصحيحة بتكلفة رخيصة. استمر في مضاعفة 0.0072 حتى تقع في [0.5, 1): 0.0144، 0.0288، 0.0576، 0.1152، 0.2304، 0.4608، 0.9216. سبع مضاعفات. إذن 0.0072 = 2^(-7) x 0.9216. الضرب في 0.9216 هو Fixed-point multiplication (ضرب بفاصلة ثابتة)، والضرب في 2^(-7) هو إزاحة يمينية بسبع بتات. هذا هو تفكيك M0 and bit shift في الشريحة 13:

How M0 becomes an integerكيف يصبح M0 عدداً صحيحاً

M0 is still a real number, so it is stored as a fixed-point integer. With a 32-bit word, Jacob et al. store the int32 nearest to 2^31 M0, which is the Q31 format: the integer represents the fraction value / 2^31. For M0 = 0.9216 that integer is 1,979,120,930. The chip multiplies the accumulator by this integer into a 64-bit product and keeps the top bits (a right shift by 31 with rounding), then shifts right by n with rounding. Because M0 >= 0.5, the stored integer is at least 2^30, so it always uses about 30 significant bits. That is the point of normalizing: a tiny M stored directly in Q31 would waste most of its bits on leading zeros.

M0 ما زال عدداً حقيقياً، لذلك يُخزَّن عدداً صحيحاً بفاصلة ثابتة. مع كلمة من 32 بت، يخزّن Jacob et al. أقرب عدد int32 إلى 2^31 M0، وهذه صيغة Q31: العدد الصحيح يمثل الكسر value / 2^31. بالنسبة لـ M0 = 0.9216 يكون هذا العدد 1,979,120,930. تضرب الشريحة المراكم في هذا العدد لتحصل على حاصل ضرب من 64 بت وتحتفظ بالبتات العليا (إزاحة يمينية بمقدار 31 مع تقريب)، ثم تزيح يميناً بمقدار n مع تقريب. ولأن M0 >= 0.5، يكون العدد المخزّن 2^30 على الأقل، فيستخدم دائماً نحو 30 بتاً ذات دلالة. هذا هو الهدف من التطبيع (normalizing): لو خُزّن M صغير مباشرة بصيغة Q31 لأهدر معظم بتاته على أصفار بادئة.

Try M = 0.3 in the calculator: one doubling gives 0.6, so n = 1 and M0 = 0.6. Try M = 0.5: it is already in range, so n = 0 and M0 = 0.5. The rule is mechanical: n is the number of doublings needed to reach 0.5, and M0 = M x 2^n.

جرّب M = 0.3 في الحاسبة: مضاعفة واحدة تعطي 0.6، إذن n = 1 وM0 = 0.6. جرّب M = 0.5: هي أصلاً داخل المدى، إذن n = 0 وM0 = 0.5. القاعدة آلية: n هو عدد المضاعفات اللازمة للوصول إلى 0.5، وM0 = M x 2^n.

Why M is below 1, and why that is only an observationلماذا M أقل من 1، ولماذا هذه مجرد ملاحظة

S_W S_X is the value of one unit in the accumulator, and the accumulator sums many products, so it spans a far wider range than one output code. S_Y must cover that whole output range in only 2^N levels, so it is usually much larger than S_W S_X, which makes M small. Jacob et al. report that they empirically find it to always be in (0, 1). That is a finding about trained networks, not a theorem: nothing in the algebra forbids S_Y < S_W S_X. The gemmlowp documentation is more careful and says the multiplier is typically less than one.

S_W S_X هو قيمة الوحدة الواحدة في المراكم، والمراكم يجمع نواتج كثيرة، لذلك يمتد على مدى أوسع بكثير من رمز مخرج واحد. يجب أن يغطي S_Y مدى المخرج كله في 2^N مستوى فقط، لذلك يكون عادة أكبر بكثير من S_W S_X، وهذا يجعل M صغيراً. ويذكر Jacob et al. أنهم وجدوه تجريبياً دائماً في (0, 1). هذه نتيجة عن الشبكات المدرّبة، لا نظرية رياضية: لا شيء في الجبر يمنع S_Y < S_W S_X. ووثائق gemmlowp أكثر حذراً، إذ تقول إن المضاعِف يكون عادةً أقل من واحد.

Go back to the cost map and look at the one term that is neither the core product nor precomputable: Z_W q_X. Slide 14 shades it light blue for that reason. Every inference, before or alongside the main multiply, the kernel has to sum each column of the input codes, multiply by Z_W and subtract. That is an extra pass over X, every inference, for every layer. The extra work is smaller than the matrix product itself (Jacob et al. count it as order N^2 additions against 2N^3 for the product), but it costs memory traffic, kernel complexity and energy, and on a tiny device none of that is free.

عد إلى خريطة التكلفة وانظر إلى الحد الوحيد الذي ليس هو حاصل الضرب الأساسي ولا يمكن حسابه مسبقاً: Z_W q_X. لهذا السبب تظلله الشريحة 14 باللون الأزرق الفاتح. في كل استدلال، قبل الضرب الرئيسي أو بالتوازي معه، يجب على النواة (kernel) أن تجمع كل عمود من رموز المدخل، وتضربه في Z_W، ثم تطرحه. هذا مرور إضافي على X، في كل استدلال، ولكل طبقة. العمل الإضافي أصغر من ضرب المصفوفات نفسه (يحسبه Jacob et al. بعدد عمليات جمع من رتبة N^2 مقابل 2N^3 لحاصل الضرب)، لكنه يكلّف حركة ذاكرة وتعقيداً في النواة وطاقة، وعلى جهاز صغير لا شيء من ذلك مجاني.

The slide's question, Z_W = 0?, is the obvious way out. If the weight zero point is zero, the term Z_W q_X vanishes, and so does Z_W Z_X. What remains is

سؤال الشريحة، Z_W = 0?، هو المخرج الواضح. إذا كانت نقطة الصفر للأوزان صفراً، يختفي الحد Z_W q_X، ويختفي معه Z_W Z_X. والمتبقي هو

Now the only runtime work inside the bracket is the integer matrix product, and the only correction is precomputed. This choice is Z_W = 0, and in practice it means quantizing weights with Symmetric quantization, the topic of the next part.

الآن العمل الوحيد وقت التشغيل داخل القوس هو ضرب المصفوفات الصحيح، والتصحيح الوحيد محسوب مسبقاً. هذا الاختيار هو Z_W = 0، ويعني عملياً تكميم الأوزان بـ Symmetric quantization (التكميم المتماثل)، وهو موضوع الجزء التالي.

Why weights can afford itلماذا تستطيع الأوزان تحمّل ذلك

Forcing Z = 0 means real 0 sits in the middle of the integer range, so the scheme is only efficient when the data is spread roughly evenly on both sides of zero. The histogram on slide 14 shows that weights are: the Weight distribution of a trained layer is a narrow bell, peaked at 0, falling off almost symmetrically by about -0.05 and +0.05. Centering the grid at zero wastes almost no levels. Activations after a ReLU are the opposite case, all non-negative, so a symmetric grid would waste half its codes on values that never occur. That is why activations keep a free zero point and weights do not.

فرض Z = 0 يعني أن الصفر الحقيقي 0 يقع في منتصف مدى الأعداد الصحيحة، لذلك لا يكون هذا الأسلوب فعالاً إلا عندما تنتشر البيانات بشكل متوازن تقريباً على جانبي الصفر. ويُظهر المدرج التكراري (histogram) في الشريحة 14 أن الأوزان كذلك: Weight distribution لطبقة مدرّبة جرس ضيق قمته عند 0، ويتلاشى بشكل شبه متماثل عند نحو -0.05 و+0.05. توسيط الشبكة عند الصفر لا يكاد يهدر أي مستوى. أما التنشيطات (activations) بعد ReLU فهي الحالة المعاكسة، كلها غير سالبة، فالشبكة المتماثلة ستهدر نصف رموزها على قيم لا تظهر أبداً. لهذا تحتفظ التنشيطات بنقطة صفر حرة ولا تحتفظ الأوزان بها.