Lecture 05-3 · Quantization III

المحاضرة 05-3 · التكميم الثالث

XNOR-Net: binary activations and popcount

XNOR-Net: التفعيلات الثنائية وpopcount

Slides 55–61الشرائح 55–61 P1 MUSTP1 ضروري

Binarize the activations too, and a dot product of ±1 vectors becomes one XNOR and one popcount on packed bits. The only catch is the arithmetic: counting matches is not the same as summing products, so the result needs a −n + 2x correction.

إذا حوّلنا التفعيلات (activations) أيضاً إلى ثنائية، يصبح الضرب النقطي لمتجهات ±1 عملية XNOR واحدة وعملية popcount واحدة على بتات مضغوطة. المشكلة الوحيدة حسابية: عدّ التطابقات ليس هو مجموع حواصل الضرب، لذلك تحتاج النتيجة إلى تصحيح −n + 2x.

Both sides binary: the ±1 dot product

الطرفان ثنائيان: الضرب النقطي لمتجهات ±1

Slide 55 keeps the weight row binary, W = [1, −1, 1, −1], and now binarizes the input as well, x = [1, 1, −1, 1]. Every product is ±1:

تبقي الشريحة 55 صف الأوزان ثنائياً W = [1, −1, 1, −1]، وتحوّل المدخل أيضاً إلى ثنائي x = [1, 1, −1, 1]. كل حاصل ضرب يساوي ±1:

y = 1×1 + (−1)×1 + 1×(−1) + (−1)×1 = 1 − 1 − 1 − 1 = −2

النتيجة y = −2: حاصل ضرب واحد فقط يساوي +1 (حيث تتطابق الإشارتان) والثلاثة الباقية −1.

Encode −1 as bit 0: multiplication becomes XNOR

رمّز −1 كبت 0: يصبح الضرب XNOR

Store +1 as bit 1 and −1 as bit 0. The product of two ±1 values is +1 exactly when the signs agree, and XNOR outputs 1 exactly when the bits agree. So the multiplication table and the XNOR truth table are the same table (slide 56).

خزّن +1 كبت 1 و−1 كبت 0. حاصل ضرب قيمتين ±1 يساوي +1 بالضبط عندما تتفق الإشارتان، وXNOR يُخرج 1 بالضبط عندما يتفق البتان. إذن جدول الضرب وجدول صواب XNOR هما الجدول نفسه (الشريحة 56).

WxW·xbWbxXNOR(bW, bx)
111111
1−1−1100
−1−11001
−11−1010

في كل سطر: حيث يكون الضرب 1 يكون XNOR مساوياً 1، وحيث يكون الضرب −1 يكون XNOR مساوياً 0. الفرق الوحيد أن القيمة −1 صارت 0.

Why summing the XNOR bits is wrong, and the fix

لماذا يكون جمع بتات XNOR خاطئاً، وكيف نصلحه

Slide 57 shows the problem. With the bits bW = 1010 and bx = 1101, the XNORs are 1, 0, 0, 0, which sum to 1, not −2. A 0 bit stands for −1, but adding it contributes 0. Each mismatch is under-counted by 1, and each match is still counted as 1.

تعرض الشريحة 57 المشكلة. مع البتات b_W = 1010 وb_x = 1101 تكون نواتج XNOR هي 1, 0, 0, 0 ومجموعها 1 وليس −2. البت 0 يمثل −1، لكن جمعه يضيف 0. فكل عدم تطابق يُحسب أقل بمقدار 1، وكل تطابق يُحسب 1.

Fix it with counting. Let n be the vector length and m the number of matching positions (the XNOR popcount). Matches contribute +1 each and the n − m mismatches contribute −1 each:

نصلح ذلك بالعدّ. ليكن n طول المتجه وm عدد المواضع المتطابقة (أي popcount لناتج XNOR). كل تطابق يضيف +1 وكل واحد من حالات عدم التطابق n − m يضيف −1:

y = m − (n − m) = −n + 2m = −n + 2 · Σj (Wij xnor xj)

إذن y = m − (n − m) = −n + 2m. طريقة الشريحة 58: افترض أن كل الحدود −1 فتبدأ من −n، ثم كل تطابق يرفع الحد من −1 إلى +1، أي يضيف +2.

On hardware, multiplying by 2 is a left shift by one bit, so the whole row is one XNOR, one popcount, one shift and one subtract (slide 60):

في العتاد، الضرب في 2 هو إزاحة يسار ببت واحد، فيصبح الصف كله XNOR واحدة وpopcount واحدة وإزاحة واحدة وطرح واحد (الشريحة 60):

yi = −n + popcount(Wi xnor x) << 1

bW bx XNOR 1010 1101 1000 +1 · +1−1 · +1+1 · −1−1 · +1 matchmissmissmiss n = 4 popcount(1000) = 1 1 << 1 = 2 y = −4 + 2 = −2 naive sum of XNOR bits = 1 (wrong)
Slides 57 to 60. One match and three misses: −4 + 2 × 1 = −2, the same answer as the ±1 arithmetic.الشرائح من 57 إلى 60. تطابق واحد وثلاث حالات عدم تطابق: −4 + 2 × 1 = −2، وهو الجواب نفسه الذي يعطيه حساب ±1.
Worked exampleمثال محلول

An 8-element row: W = [1, −1, −1, 1, 1, 1, −1, 1], x = [1, 1, −1, −1, 1, −1, −1, 1]. Compute y both ways.

صف من 8 عناصر: W = [1, −1, −1, 1, 1, 1, −1, 1] وx = [1, 1, −1, −1, 1, −1, −1, 1]. احسب y بالطريقتين.

±1 arithmetic
  products: 1, −1, 1, −1, 1, −1, 1, 1
  y = 1 − 1 + 1 − 1 + 1 − 1 + 1 + 1 = 2

Bit encoding (+1 → 1, −1 → 0)
  b_W = 1 0 0 1 1 1 0 1
  b_x = 1 1 0 0 1 0 0 1
  XNOR= 1 0 1 0 1 0 1 1      (1 where bits agree)
  popcount = 5,  n = 8

  y = −n + popcount << 1 = −8 + (5 << 1) = −8 + 10 = 2   ✓

Check: 5 matches × (+1) + 3 misses × (−1) = 5 − 3 = 2

Sanity bounds: y ranges from −n (all mismatch, popcount 0) to +n (all match, popcount n), and y always has the same parity as n.

حدود للتحقق: y يتراوح من −n (كلها غير متطابقة، popcount = 0) إلى +n (كلها متطابقة، popcount = n)، وy دائماً له نفس زوجية n.

Cost: memory and compute for each pairing

التكلفة: الذاكرة والحساب لكل تركيبة

inputالمدخلweightالوزنoperationsالعملياتmemoryالذاكرةcomputationالحساب
RR+ ×1x1x
RB+ −~32x lessأقل بنحو 32x~2x lessأقل بنحو 2x
BBxnor, popcount~32x lessأقل بنحو 32x~58x lessأقل بنحو 58x

جدول الشريحة 60: عندما يكون المدخل والوزن ثنائيين (B × B) تبقى الذاكرة أقل بحوالي 32x لكن الحساب يصبح أقل بحوالي 58x، لأن كلمة واحدة من 64 بت تنفذ 64 عملية ضرب بعملية XNOR واحدة ثم popcount.

The ~58x comes from bit-level parallelism: one 64-bit XNOR plus one popcount instruction replaces 64 multiply-accumulates. Memory stays at ~32x because the weights were already 1 bit in the R × B row.

مصدر ~58x هو التوازي على مستوى البت: تعليمة XNOR واحدة على 64 بت مع تعليمة popcount واحدة تحل محل 64 عملية multiply-accumulate. والذاكرة تبقى عند ~32x لأن الأوزان كانت أصلاً 1 بت في سطر R × B.

Accuracy: scale factors decide it

الدقة: معاملات المقياس هي الحاسمة

AlexNet methodطريقة AlexNetW bitsبتات WA bitsبتات AImageNet top-1 deltaتغيّر دقة top-1 على ImageNet
BWN (scale for weights)BWN (مقياس للأوزان)1320.2%
BNN (no scale factors)BNN (بدون معاملات مقياس)11−28.7%
XNOR-Net (scales for weights and activations)XNOR-Net (مقاييس للأوزان والتفعيلات)11−12.4%

جدول الشريحة 61: BWN يحوّل الأوزان فقط فيخسر تقريباً لا شيء (0.2%). BNN يحوّل الأوزان والتفعيلات بدون أي مقياس فيخسر −28.7%. وXNOR-Net يحوّل الاثنين لكن مع معاملات مقياس للأوزان والتفعيلات فيخسر −12.4% فقط.

Read the table in two steps. Going from BWN to BNN binarizes the activations and costs about 29 points. Going from BNN to XNOR-Net keeps 1-bit activations but adds scale factors, which wins back about 16 points (−28.7 to −12.4).

اقرأ الجدول على خطوتين. الانتقال من BWN إلى BNN يحوّل التفعيلات إلى ثنائية ويكلّف حوالي 29 نقطة. والانتقال من BNN إلى XNOR-Net يبقي التفعيلات 1 بت لكن يضيف معاملات المقياس، فيستعيد حوالي 16 نقطة (من −28.7 إلى −12.4).

Memory trickحيلة للتذكر

"Start at −n, every match pays +2". Assume every term is −1, then each matching bit lifts one term from −1 to +1.

"ابدأ من −n، وكل تطابق يدفع +2". افترض أن كل حد −1، ثم كل بت متطابق يرفع حداً من −1 إلى +1.

Exam trapفخ في الاختبار

The raw XNOR sum is not the answer. popcount(1000) = 1, but y = −2. Forgetting −n + 2x is the most common mistake; always finish with −n + 2 × popcount.

مجموع XNOR الخام ليس هو الجواب. popcount(1000) = 1 لكن y = −2. نسيان −n + 2x هو الخطأ الأشيع، فأنهِ دائماً بـ −n + 2 × popcount.

−1 is stored as 0, not as a two's complement −1. The encoding is one bit per value: 1 means +1 and 0 means −1. Writing W = [1, −1, 1, −1] as 1010 is correct; 1 0 1 0 does not mean "1, 0, 1, 0" in value.

القيمة −1 تُخزَّن كـ 0 وليس كـ −1 بتمثيل two's complement. الترميز بت واحد لكل قيمة: 1 يعني +1 و0 يعني −1. كتابة W = [1, −1, 1, −1] كـ 1010 صحيحة، و1010 لا تعني القيم "1, 0, 1, 0".

XNOR, not XOR. XOR is 1 on a mismatch, so it counts the −1 products. If a question uses XOR, the formula becomes y = n − 2 × popcount(W xor x).

XNOR وليس XOR. XOR يعطي 1 عند عدم التطابق، فهو يعدّ حواصل الضرب −1. إذا استخدم السؤال XOR تصبح الصيغة y = n − 2 × popcount(W xor x).

Check yourself

اختبر نفسك

bW = 1010 and bx = 1101 (1 means +1, 0 means −1). What is y = W · x?

b_W = 1010 وb_x = 1101 (1 يعني +1 و0 يعني −1). ما قيمة y = W · x؟

B. XNOR = 1000, popcount = 1, y = −4 + 2 × 1 = −2. A is the raw popcount without correction. C drops the sign of −n + 2. D is −n + popcount, forgetting the shift.

B. XNOR = 1000، وpopcount = 1، وy = −4 + 2 × 1 = −2. الخيار A هو popcount الخام بدون تصحيح. والخيار C يُسقط إشارة −n + 2. والخيار D هو −n + popcount، أي أنه ينسى الإزاحة.

For n = 8 binary elements, popcount(W xnor x) = 6. What is y?

لـ n = 8 عناصر ثنائية، popcount(W xnor x) = 6. ما قيمة y؟

D. −8 + 2 × 6 = 4 (6 matches minus 2 misses). A is the uncorrected count. B is −8 + 6. C is 2 × 6 without subtracting n.

D. −8 + 2 × 6 = 4 (6 تطابقات ناقص حالتي عدم تطابق). الخيار A هو العدّ بدون تصحيح. والخيار B هو −8 + 6. والخيار C هو 2 × 6 بدون طرح n.

On AlexNet, which method binarizes both weights and activations and still uses scale factors?

على AlexNet، أي طريقة تحوّل الأوزان والتفعيلات إلى ثنائية وتستخدم معاملات مقياس؟

A. XNOR-Net is (1, 1) bits with scales for both. B is (1, 1) with no scales. C keeps 32-bit activations. D binarizes only weights and has no scale.

A. XNOR-Net بتاته (1, 1) مع مقاييس للاثنين. والخيار B هو (1, 1) بدون مقاييس. والخيار C يُبقي التفعيلات بـ 32 بت. والخيار D يحوّل الأوزان فقط إلى ثنائية وليس فيه مقياس.

Compared with real × real, a binary × binary layer gives about:

مقارنة بـ real × real، تعطي طبقة binary × binary تقريباً:

C. Memory is set by 32 bits → 1 bit, and XNOR plus popcount gives ~58x on compute. A is the R × B row. B swaps the numbers. D is not on the slide.

C. الذاكرة يحددها الانتقال من 32 بت إلى 1 بت، وXNOR مع popcount يعطيان نحو 58x في الحساب. الخيار A هو سطر R × B. والخيار B يبدّل الرقمين. والخيار D غير موجود في الشريحة.

Why is the XNOR truth table a valid replacement for ±1 multiplication?

لماذا يصلح جدول صواب XNOR بديلاً لضرب ±1؟

B. With +1 → 1 and −1 → 0, "same sign" equals "same bit". A is wrong since the encoding is not two's complement. C is false (0 xnor 0 = 1, 0 and 0 = 0). D is backwards: popcount counts matches, and −n + 2x restores the negatives.

B. مع +1 → 1 و−1 → 0 تصبح "الإشارة نفسها" مساوية لـ "البت نفسه". الخيار A خاطئ لأن الترميز ليس two's complement. والخيار C غير صحيح (0 xnor 0 = 1 بينما 0 and 0 = 0). والخيار D معكوس: popcount يعدّ التطابقات، و−n + 2x هو ما يعيد الحدود السالبة.