Majid Al-RaimiBinary weights and activations: XNOR and popcountالأوزان والتنشيطات الثنائية: XNOR وpopcount

COE 592Lecture 5.3المحاضرة 5.3Part 07الجزء 07

Binary weights and activations: XNOR and popcountالأوزان والتنشيطات الثنائية: XNOR وpopcount

When activations are binarized too, each multiply of +1/-1 values becomes an XNOR on bits, and the sum becomes a popcount. The identity y = -n + 2 * popcount(W xnor x) turns a dot product into two cheap bit operations, giving about 32x less memory and about 58x less computation.عندما تُثنَّث التنشيطات أيضًا، يصبح كل ضرب لقيم +1/-1 عملية XNOR على البتات، ويصبح المجموع popcount. المتطابقة y = -n + 2 * popcount(W xnor x) تحوّل الضرب النقطي إلى عمليتي بت رخيصتين، مما يعطي ذاكرة أقل بنحو 32x وحسابًا أقل بنحو 58x.

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

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

Part 6 binarized the weights and kept the activations real, which turned every multiply into an add or a subtract. This part goes all the way: weights and activations are both +1 or -1. Then a dot product stops being arithmetic at all. It becomes two bit operations on packed words, XNOR and popcount, plus one shift and one add.

The whole part runs on one example from the slides: W = [1, -1, 1, -1] and x = [1, 1, -1, 1], with n = 4 and true answer -2. You will watch a naive bit trick get the wrong answer (1), repair it with a one-line derivation, and then price the result in memory and compute. For the midterm, expect to derive the formula, evaluate it on given vectors, justify the XNOR truth table, and quote the cost numbers with their caveats. For embedded work, this is the reason a binarized network can run on a microcontroller with no floating-point unit.

في الجزء 6 حوّلنا الأوزان إلى قيم ثنائية (binarized) وأبقينا الـ activations حقيقية، فتحوّل كل ضرب إلى عملية جمع أو طرح. هذا الجزء يذهب إلى النهاية: الأوزان والـ activations كلاهما إما +1 أو -1. عندها يتوقف الـ dot product عن كونه عملية حسابية أصلًا، ويصبح عمليتين على البتات فوق كلمات مضغوطة (packed words)، هما XNOR وpopcount، إضافة إلى إزاحة (shift) واحدة وعملية جمع واحدة.

الجزء كله يدور حول مثال واحد من الشرائح: W = [1, -1, 1, -1] وx = [1, 1, -1, 1]، مع n = 4 والإجابة الصحيحة -2. ستشاهد حيلة بتات ساذجة تعطي إجابة خاطئة (1)، ثم تصلحها باشتقاق من سطر واحد، ثم تقدّر تكلفة النتيجة من حيث الذاكرة والحساب. في الاختبار النصفي توقّع أن يُطلب منك اشتقاق الصيغة، وحسابها على متجهات معطاة، وتبرير جدول حقيقة XNOR، وذكر أرقام التكلفة مع شروطها. وفي العمل على الأنظمة المدمجة (embedded)، هذا هو السبب الذي يجعل شبكة ثنائية تعمل على microcontroller لا يحتوي على وحدة فاصلة عائمة (floating-point unit).

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

  1. Compute a dot product between two ±1 vectors by hand, and say why it needs no multiplier.تحسب يدويًا الـ dot product بين متجهين قيمهما ±1، وتشرح لماذا لا يحتاج إلى أي multiplier.
  2. Explain, with the two truth tables, why XNOR on the bit encoding reproduces the product of signs.تشرح باستخدام جدولَي الحقيقة لماذا تعيد عملية XNOR على الترميز الثنائي (bits) إنتاج حاصل ضرب الإشارات.
  3. Derive y = -n + 2 · popcount(W xnor x) from first principles, and explain why summing XNOR bits alone is wrong.تشتق y = -n + 2 · popcount(W xnor x) من المبادئ الأساسية، وتشرح لماذا يكون جمع بتات XNOR وحدها خاطئًا.
  4. Evaluate the hardware form -n + (popcount << 1) on packed bit words, with the shift applied to the popcount only.تحسب الصيغة العتادية -n + (popcount << 1) على كلمات بتات مضغوطة (packed words)، مع تطبيق الإزاحة (shift) على الـ popcount وحده.
  5. Quote and qualify the cost table: about 32x less memory, about 2x less compute for binary weights, about 58x for binary weights and inputs.تذكر جدول التكلفة مع شروطه: ذاكرة أقل بنحو 32x، وحساب أقل بنحو 2x للأوزان الثنائية، ونحو 58x للأوزان والمدخلات الثنائية معًا.

When weights and activations are both ±1عندما تكون الأوزان والـ activations كلاهما ±1

Take one row of a weight matrix, [8, -3, 5, -1], and an input column, [5, 2, 0, 1]. In full precision the output is 8·5 - 3·2 + 5·0 - 1·1 = 33: four multiplies and three adds on 32-bit floats. Now apply Binarization to both sides. The weight row becomes [1, -1, 1, -1] and the slide turns the input into [1, 1, -1, 1].

خذ صفًا واحدًا من مصفوفة أوزان، [8, -3, 5, -1]، وعمود مدخلات، [5, 2, 0, 1]. بالدقة الكاملة يكون الناتج 8·5 - 3·2 + 5·0 - 1·1 = 33: أربع عمليات ضرب وثلاث عمليات جمع على أعداد عائمة بطول 32-bit. الآن طبّق الـ Binarization على الطرفين. يصبح صف الأوزان [1, -1, 1, -1]، وتحوّل الشريحة المدخلات إلى [1, 1, -1, 1].

yi=∑jWij xj=1⋅1+(−1)⋅1+1⋅(−1)+(−1)⋅1=1−1−1−1=−2y_i = \sum_j W_{ij}\,x_j = 1\cdot1 + (-1)\cdot1 + 1\cdot(-1) + (-1)\cdot1 = 1 - 1 - 1 - 1 = -2
The running example, computed the ordinary wayالمثال المستمر، محسوبًا بالطريقة العادية

Look at what each product can be. Two signs multiplied give a sign: +1 when they agree and -1 when they differ. No product is ever 0, 2 or 0.7. So the result is fully determined by one number: how many positions agree. That observation is the whole part. Everything after it is a way of counting agreements cheaply.

انظر إلى القيم الممكنة لكل حاصل ضرب. ضرب إشارتين يعطي إشارة: +1 عندما تتفقان و-1 عندما تختلفان. لا يكون أي حاصل ضرب 0 أو 2 أو 0.7 أبدًا. لذلك تتحدد النتيجة بالكامل برقم واحد: عدد المواضع التي تتفق فيها الإشارتان. هذه الملاحظة هي الجزء كله، وكل ما يأتي بعدها مجرد طريقة رخيصة لعدّ التطابقات.

This is the setting of XNOR-Net (Rastegari et al., ECCV 2016) and of the Binarized Neural Network (BNN) of Courbariaux, Hubara and colleagues, which appeared the same year. Compared with the Binary Weight Network (BWN) of part 6, the difference is the input side: the activations are binarized too, usually with the same Deterministic binarization, so both operands of every multiply-accumulate are one bit.

هذا هو إطار XNOR-Net (Rastegari et al., ECCV 2016) وإطار الـ Binarized Neural Network (BNN) لـ Courbariaux وHubara وزملائهما، التي ظهرت في السنة نفسها. مقارنةً بالـ Binary Weight Network (BWN) في الجزء 6، الفرق في جانب المدخلات: الـ activations تصبح ثنائية أيضًا، عادةً بنفس الـ Deterministic binarization، فيكون كلا معاملَي كل عملية multiply-accumulate بتًا واحدًا.

Recall

Why does a dot product of two ±1 vectors depend only on how many positions agree?لماذا يعتمد الـ dot product لمتجهين قيمهما ±1 فقط على عدد المواضع التي تتفق فيها الإشارتان؟

Each product is +1 if the two signs agree and -1 if they differ, so the sum is (agreements) minus (disagreements). With n fixed, the number of agreements alone determines it.

كل حاصل ضرب يساوي +1 إذا اتفقت الإشارتان و-1 إذا اختلفتا، لذلك يكون المجموع (عدد الاتفاقات) ناقص (عدد الاختلافات). ومع ثبات n، يحدده عدد الاتفاقات وحده.

Encoding signs as bits: XNOR is the product, but the sum is offترميز الإشارات كبتات: XNOR هي حاصل الضرب، لكن المجموع خاطئ

A processor does not store -1 in one bit. It stores 0 or 1. So pick an encoding: +1 becomes bit 1 and -1 becomes bit 0. The weight row [1, -1, 1, -1] packs into 1010 and the input [1, 1, -1, 1] into 1101. The question is which logic gate, applied to the bits, behaves like multiplication applied to the signs.

المعالج لا يخزّن -1 في بت واحد، بل يخزّن 0 أو 1. لذلك نختار ترميزًا: +1 يصبح البت 1، و-1 يصبح البت 0. يُضغط صف الأوزان [1, -1, 1, -1] إلى 1010، والمدخلات [1, 1, -1, 1] إلى 1101. والسؤال: أي بوابة منطقية (logic gate)، إذا طُبّقت على البتات، تتصرف مثل الضرب المطبّق على الإشارات؟

Line the two truth tables upضع جدولَي الحقيقة جنبًا إلى جنب

WWxxW × xW × xb_wb_wb_xb_xXNOR(b_w, b_x)XNOR(b_w, b_x)
+1+1+1+1+1+1111111
+1+1-1-1-1-1110000
-1-1-1-1+1+1000011
-1-1+1+1-1-1001100
Products of signs (left three columns) against XNOR of their bit encodings (right three columns)حواصل ضرب الإشارات (الأعمدة الثلاثة اليسرى) مقابل XNOR لترميزها الثنائي (الأعمدة الثلاثة اليمنى)

Read across each row. The product is +1 in rows one and three, where the signs agree. XNOR, the negation of exclusive OR, outputs 1 exactly when its two inputs are equal, which is again rows one and three. So under this encoding the product column and the XNOR column are the same column, with -1 written as 0. That is the precise sense in which XNOR replaces multiplication: it is an equality test, and the product of two signs is also an equality test.

اقرأ كل صف أفقيًا. حاصل الضرب يساوي +1 في الصفين الأول والثالث، حيث تتفق الإشارتان. والـ XNOR، وهي نفي الـ exclusive OR، تُخرج 1 بالضبط عندما يتساوى مدخلاها، أي في الصفين الأول والثالث مرة أخرى. إذن تحت هذا الترميز يكون عمود حاصل الضرب وعمود الـ XNOR العمود نفسه، مع كتابة -1 على شكل 0. هذا هو المعنى الدقيق لقولنا إن XNOR تحل محل الضرب: إنها اختبار تساوٍ، وحاصل ضرب إشارتين هو أيضًا اختبار تساوٍ.

The two truth tables row for row: wherever the product is +1, XNOR is 1جدولا الحقيقة صفًا بصف: حيثما كان حاصل الضرب +1 تكون XNOR مساوية 1

The tempting shortcut that failsالاختصار المغري الذي يفشل

If XNOR is the product, surely the dot product is just the sum of the XNOR bits. Try it on the running example, pairing 1010 with 1101 position by position.

إذا كانت XNOR هي حاصل الضرب، فلا بد أن الـ dot product هو مجرد مجموع بتات الـ XNOR. جرّب ذلك على المثال الجاري، بمقابلة 1010 مع 1101 موضعًا بموضع.

(1 xnor 1)+(0 xnor 1)+(1 xnor 0)+(0 xnor 1)=1+0+0+0=1≠−2(1\ \text{xnor}\ 1) + (0\ \text{xnor}\ 1) + (1\ \text{xnor}\ 0) + (0\ \text{xnor}\ 1) = 1 + 0 + 0 + 0 = 1 \neq -2
Summing the XNOR bits gives 1, not the true -2 (the question mark on slide 57)جمع بتات XNOR يعطي 1، لا القيمة الصحيحة -2 (علامة الاستفهام في الشريحة 57)

The mapping is right element by element but wrong in aggregate, because the encoding is not a linear map that preserves sums. A disagreement should contribute -1, but its bit contributes 0. The sum of XNOR bits therefore counts the agreements and silently drops every disagreement. Here there is one agreement and three disagreements, so the true answer is 1 - 3 = -2 while the bit sum reports only the 1.

التحويل صحيح عنصرًا بعنصر لكنه خاطئ في المجموع، لأن الترميز ليس تحويلًا خطيًا يحافظ على المجاميع. عدم التطابق يجب أن يساهم بـ -1، لكن البت الخاص به يساهم بـ 0. لذلك فمجموع بتات الـ XNOR يعدّ التطابقات ويُسقط بصمت كل عدم تطابق. هنا يوجد تطابق واحد وثلاثة عدم تطابقات، فالإجابة الصحيحة 1 - 3 = -2، بينما مجموع البتات لا يُظهر إلا الـ 1.

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

Under the encoding +1 → 1 and -1 → 0, which gate reproduces the product of two signs?تحت الترميز ‎+1 → 1 و‎-1 → 0، أي بوابة تعيد إنتاج حاصل ضرب إشارتين؟

Recall

Sum the XNOR bits for W bits 1010 and x bits 1101. Why is the result not the dot product?اجمع بتات XNOR لبتات W وهي 1010 وبتات x وهي 1101. لماذا لا تكون النتيجة هي الـ dot product؟

1010 xnor 1101 = 1000, which sums to 1. It counts only the agreements; each of the three disagreements should subtract 1 but contributes 0, so the true value is 1 - 3 = -2.

1010 xnor 1101 = 1000، ومجموعها 1. هذا يعدّ التطابقات فقط؛ فكل واحد من عدم التطابقات الثلاثة يجب أن يطرح 1 لكنه يساهم بـ 0، لذلك القيمة الصحيحة 1 - 3 = -2.

Recovering the dot product: y = -n + 2 · popcountاستعادة الـ dot product: y = -n + 2 · popcount

Start from the worst case. Suppose every one of the n = 4 products were -1. The sum would be -4, which is -n. Now each position where the XNOR is 1 is a position whose product is really +1, not -1. Changing one term from -1 to +1 raises the sum by 2. The example has one such position, so the answer is -4 + 2 = -2. That is the blue line on slide 58.

ابدأ من أسوأ حالة. افترض أن كل واحد من حواصل الضرب الـ n = 4 يساوي -1. سيكون المجموع -4، أي -n. الآن، كل موضع تكون فيه الـ XNOR مساوية 1 هو موضع حاصل ضربه في الحقيقة +1 وليس -1. وتغيير حد واحد من -1 إلى +1 يرفع المجموع بمقدار 2. في المثال يوجد موضع واحد من هذا النوع، فتكون الإجابة -4 + 2 = -2. هذا هو الخط الأزرق في الشريحة 58.

Start at -n = -4 with every product assumed -1; each XNOR 1 flips one product to +1 and lifts y by 2ابدأ من -n = -4 بافتراض أن كل حاصل ضرب يساوي -1؛ وكل 1 في XNOR يقلب حاصل ضرب واحدًا إلى +1 ويرفع y بمقدار 2

The general ruleالقاعدة العامة

Write m for the number of matches, the positions where the signs agree. The other n - m positions are mismatches. Matches contribute +1 each and mismatches -1 each, so y = m - (n - m) = 2m - n. And m is exactly the number of 1 bits in the XNOR of the two packed words, which is what Popcount returns.

ليكن m عدد التطابقات، أي المواضع التي تتفق فيها الإشارتان. المواضع الأخرى وعددها n - m هي عدم تطابقات. كل تطابق يساهم بـ +1 وكل عدم تطابق بـ -1، لذلك y = m - (n - m) = 2m - n. وm هو بالضبط عدد البتات التي تساوي 1 في ناتج XNOR للكلمتين المضغوطتين، وهو ما تُرجعه عملية الـ Popcount.

yi=−n+2∑j(bWij xnor bxj)=−n+2⋅popcount⁡ ⁣(Wi xnor x)y_i = -n + 2\sum_{j} \left(b_{W_{ij}}\ \text{xnor}\ b_{x_j}\right) = -n + 2\cdot\operatorname{popcount}\!\left(W_i\ \text{xnor}\ x\right)
The XNOR and popcount form of a binary dot productصيغة XNOR وpopcount للضرب النقطي الثنائي

The same identity drops out of the encoding algebraically. With s = 2b - 1 for each sign and bit, the product of two signs is 2 · XNOR(b_w, b_x) - 1 (check it: 2·1 - 1 = +1, 2·0 - 1 = -1). Summing over n positions gives 2 · Σ XNOR - n, the formula above. Either route is acceptable in an exam; the counting route is quicker to write and easier to defend.

المتطابقة نفسها تخرج جبريًا من الترميز. مع s = 2b - 1 لكل إشارة وبتها، يكون حاصل ضرب إشارتين 2 · XNOR(b_w, b_x) - 1 (تحقّق: 2·1 - 1 = +1، و2·0 - 1 = -1). والجمع على n موضعًا يعطي 2 · Σ XNOR - n، وهي الصيغة أعلاه. الطريقتان مقبولتان في الاختبار؛ وطريقة العدّ أسرع كتابةً وأسهل في الدفاع عنها.

Worked exampleمثال محلول

The slide example, n = 4مثال الشرائح، n = 4

  1. Encodeالترميز

    W = [1, -1, 1, -1] → 1010 and x = [1, 1, -1, 1] → 1101.

    W = [1, -1, 1, -1] → 1010 وx = [1, 1, -1, 1] → 1101.

  2. XNORالـ XNOR

    Position by position: 1,1 → 1, 0,1 → 0, 1,0 → 0, 0,1 → 0, so 1010 xnor 1101 = 1000.

    موضعًا بموضع: 1,1 → 1، 0,1 → 0، 1,0 → 0، 0,1 → 0، إذن 1010 xnor 1101 = 1000.

  3. Popcountالـ Popcount

    popcount(1000) = 1: one match.

    popcount(1000) = 1: تطابق واحد.

  4. Correct for the mismatchesالتصحيح لعدم التطابقات

    y = -4 + 2 × 1 = -2.

    y = -4 + 2 × 1 = -2.

  5. Resultالنتيجة

    -2, identical to 1 - 1 - 1 - 1 computed with real multiplies.
    -2، وهي مطابقة لـ 1 - 1 - 1 - 1 المحسوبة بعمليات ضرب حقيقية.

Worked exampleمثال محلول

Your turn first, then check: n = 8حاول بنفسك أولًا ثم تحقّق: n = 8

  1. The vectorsالمتجهات

    W = [1, 1, -1, 1, -1, -1, 1, 1] and x = [-1, 1, -1, 1, 1, -1, -1, 1].

    W = [1, 1, -1, 1, -1, -1, 1, 1] وx = [-1, 1, -1, 1, 1, -1, -1, 1].

  2. Encodeالترميز

    W → 11010011 and x → 01011001.

    W → 11010011 وx → 01011001.

  3. XNORالـ XNOR

    Matches at positions 2, 3, 4, 6, 8, so 11010011 xnor 01011001 = 01110101.

    التطابقات في المواضع 2, 3, 4, 6, 8، إذن 11010011 xnor 01011001 = 01110101.

  4. Popcount and correctالـ Popcount ثم التصحيح

    popcount = 5, so y = -8 + 2 × 5 = 2.

    popcount = 5، إذن y = -8 + 2 × 5 = 2.

  5. Resultالنتيجة

    Check with signs: products -1, 1, 1, 1, -1, 1, -1, 1 sum to 5 - 3 = 2.
    تحقّق بالإشارات: حواصل الضرب -1, 1, 1, 1, -1, 1, -1, 1 مجموعها 5 - 3 = 2.

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

With W = [-1, 1, 1, -1], x = [1, 1, -1, -1] and n = 4, what does -n + 2 · popcount(W xnor x) give?مع W = [-1, 1, 1, -1] و x = [1, 1, -1, -1] و n = 4، ماذا يعطي ‎-n + 2 · popcount(W xnor x)؟

Recall

Derive y = -n + 2 · popcount(W xnor x) without looking.اشتق y = -n + 2 · popcount(W xnor x) دون النظر.

Let m be the number of positions where the signs agree. Those products are +1, the other n - m are -1, so y = m - (n - m) = 2m - n. Under +1 → 1, -1 → 0, XNOR is 1 exactly where the signs agree, so m = popcount(W xnor x).

ليكن m عدد المواضع التي تتفق فيها الإشارتان. حواصل الضرب هناك تساوي +1، والـ n - m الباقية تساوي -1، إذن y = m - (n - m) = 2m - n. وتحت الترميز +1 → 1, -1 → 0، تكون الـ XNOR مساوية 1 بالضبط حيث تتفق الإشارتان، إذن m = popcount(W xnor x).

The hardware form and what it saves: shift, popcount, 32x and 58xالصيغة العتادية وما توفّره: shift وpopcount و32x و58x

On real hardware the bits of W_i and x sit packed in machine words, 32 or 64 to a register. One XNOR instruction compares all of them at once, one popcount instruction counts the matches, and multiplying by 2 is a left shift by one bit. The slide writes the result as follows.

في العتاد الحقيقي تكون بتات W_i وx مضغوطة في كلمات الآلة (machine words)، 32 أو 64 بتًا في كل register. تعليمة XNOR واحدة تقارن جميعها دفعة واحدة، وتعليمة popcount واحدة تعدّ التطابقات، والضرب في 2 هو إزاحة لليسار (left shift) ببت واحد. وتكتب الشريحة النتيجة كما يلي.

yi=−n+(popcount⁡ ⁣(Wi xnor x)≪1)y_i = -n + \left(\operatorname{popcount}\!\left(W_i\ \text{xnor}\ x\right) \ll 1\right)
The hardware form, with the brackets that make the intended grouping explicitالصيغة العتادية، مع الأقواس التي توضح التجميع المقصود

On the slide example: popcount(1010 xnor 1101) = popcount(1000) = 1, then 1 << 1 = 2, then -4 + 2 = -2. In C, up to 64 elements take a handful of integer instructions: ~(w ^ x) for the XNOR (an XOR and a NOT on most CPUs), __builtin_popcountll for the count, a shift and an add. The BNN paper describes the GPU version as 32 connections evaluated with three instructions (accumulate, popcount, XNOR) taking about 6 clock cycles, a theoretical speedup of 32/6 ≈ 5.3 on that GPU.

على مثال الشرائح: popcount(1010 xnor 1101) = popcount(1000) = 1، ثم 1 << 1 = 2، ثم -4 + 2 = -2. في لغة C، ما يصل إلى 64 عنصرًا يحتاج بضع تعليمات صحيحة فقط: ~(w ^ x) للـ XNOR (أي XOR ثم NOT في معظم المعالجات)، و__builtin_popcountll للعدّ، ثم إزاحة وجمع. وتصف ورقة الـ BNN نسخة الـ GPU بأنها تقيّم 32 اتصالًا بثلاث تعليمات (accumulate وpopcount وXNOR) تستغرق نحو 6 دورات ساعة، أي تسريع نظري قدره 32/6 ≈ 5.3 على ذلك الـ GPU.

What it savesما الذي توفّره

InputالمدخلاتWeightالأوزانOperationsالعملياتMemoryالذاكرةComputationالحسابWhere the number comes fromمصدر الرقم
RealحقيقيةRealحقيقيةmultiply and addضرب وجمع1x1x1x1xFull-precision baselineخط الأساس بالدقة الكاملة
RealحقيقيةBinaryثنائيةadd and subtractجمع وطرح≈32x less≈32x أقل≈2x less≈2x أقلBinary Weight Network: each weight only picks the sign of an inputالـ Binary Weight Network: كل وزن يختار فقط إشارة أحد المدخلات
BinaryثنائيةBinaryثنائيةXNOR and popcountXNOR وpopcount≈32x less≈32x أقل≈58x less≈58x أقلXNOR-Net: 64 bit operations per CPU clock, one convolution measuredالـ XNOR-Net: 64 عملية بت لكل دورة ساعة في الـ CPU، مقيسة على convolution واحدة
Slide 60's cost table, with the source of each number (XNOR-Net, Rastegari et al. 2016)جدول التكلفة في الشريحة 60، مع مصدر كل رقم (XNOR-Net، Rastegari وزملاؤه 2016)
Memory and computation relative to full precision: weights shrink 32x in both binary rows, compute only collapses when both operands are bitsالذاكرة والحساب نسبةً إلى الدقة الكاملة: الأوزان تصغر 32x في كلا الصفين الثنائيين، والحساب لا ينهار إلا عندما يكون المعاملان كلاهما بتات

The memory column is simple arithmetic: a 32-bit float weight becomes one bit, so weight storage shrinks 32x (ignoring the small per-filter scale factors). The computation column needs more care. For binary weights with real inputs, the paper says convolutions need only addition and subtraction, giving about a 2x speedup, and adds that on CPUs which fuse multiply and add into one cycle, binary weights alone give no speedup at all.

عمود الذاكرة حساب بسيط: الوزن العائم بطول 32-bit يصبح بتًا واحدًا، فيصغر تخزين الأوزان 32x (مع تجاهل معاملات المقياس الصغيرة لكل filter). أما عمود الحساب فيحتاج عناية أكبر. للأوزان الثنائية مع مدخلات حقيقية، تقول الورقة إن الـ convolutions لا تحتاج إلا الجمع والطرح، ما يعطي تسريعًا بنحو 2x، وتضيف أنه على المعالجات التي تدمج الضرب والجمع في دورة واحدة لا تعطي الأوزان الثنائية وحدها أي تسريع على الإطلاق.

The 58x comes from a specific count. A standard convolution needs c · N_W · N_I operations (channels, filter size, input size). The binary version needs the same number of binary operations, done 64 per clock, plus N_I non-binary ones for scaling.

الـ 58x تأتي من عدّ محدد. الـ convolution العادية تحتاج c · N_W · N_I عملية (عدد القنوات، وحجم الـ filter، وحجم المدخلات). والنسخة الثنائية تحتاج العدد نفسه من العمليات الثنائية، تُنفَّذ 64 منها في كل دورة ساعة، إضافة إلى N_I عملية غير ثنائية للتحجيم (scaling).

S=c NW NI164 c NW NI+NI=64 c NWc NW+64S = \frac{c\,N_W\,N_I}{\tfrac{1}{64}\,c\,N_W\,N_I + N_I} = \frac{64\,c\,N_W}{c\,N_W + 64}
XNOR-Net speedup in high-precision operations; it depends on channels and filter size, not on input sizeتسريع XNOR-Net في العمليات عالية الدقة؛ يعتمد على عدد القنوات وحجم المرشح، لا على حجم المدخل

Worked exampleمثال محلول

Where 62.27x and 58x come fromمن أين تأتي 62.27x و58x

  1. Plug in the paper's typical layerعوّض بالطبقة النموذجية في الورقة

    c = 256 channels, a 3 × 3 filter so N_W = 9, and c · N_W = 2304.

    c = 256 قناة، وfilter بحجم 3 × 3 أي N_W = 9، وc · N_W = 2304.

  2. Theoretical speedupالتسريع النظري

    S = 64 × 2304 / (2304 + 64) = 147456 / 2368 ≈ 62.27.

    S = 64 × 2304 / (2304 + 64) = 147456 / 2368 ≈ 62.27.

  3. Resultالنتيجة

    The authors measured 58x for one convolution in their CPU implementation, excluding memory allocation and memory access. With c = 3 and a 1 × 1 filter the formula gives only about 2.9x, which is why the first and last layers are usually kept in full precision.
    قاس المؤلفون 58x لـ convolution واحدة في تطبيقهم على الـ CPU، باستثناء حجز الذاكرة والوصول إليها. ومع c = 3 وfilter بحجم 1 × 1 تعطي الصيغة نحو 2.9x فقط، ولهذا تُترك الطبقتان الأولى والأخيرة عادةً بالدقة الكاملة.
SimulatorمحاكيXNOR and popcount, one bit at a timeXNOR وpopcount، بتًا بعد بت

Click any weight or input to flip its sign. Every row below updates at once.انقر على أي وزن أو مُدخل لعكس إشارته. تتحدث كل الصفوف أدناه في الوقت نفسه.

WxW × x+1-1-1-1bits W1010bits x1101xnor1000

Start from the all-mismatch total -n and add the shifted count.ابدأ من المجموع -n الذي يقابل عدم التطابق في كل المواضع، ثم أضف العدد بعد الإزاحة.

Float dot product-2sum of W × xمجموع W × x
Popcount1onespopcount(1000)
Shifted21 << 1
Binary y-2-4 + 2
Match. -4 + 2 × 1 = -2, against a float dot product of -2. Adding the raw XNOR bits alone would have given 1.تطابق. -4 + 2 × 1 = -2، مقابل ضرب نقطي عائم قيمته -2. ولو جمعنا بتات XNOR الخام وحدها لحصلنا على 1.

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

Why do binary weights with real inputs save only about 2x compute, not 58x?لماذا توفّر الأوزان الثنائية مع مدخلات حقيقية نحو 2x فقط من الحساب، لا 58x؟

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

How do C and C++ group the expression -n + p << 1?كيف تجمّع لغتا C و C++ التعبير ‎-n + p << 1؟

Recall

Give the three numbers of the cost table and one condition attached to each.اذكر أرقام جدول التكلفة الثلاثة وشرطًا واحدًا مرتبطًا بكل منها.

Memory about 32x less in both binary rows: 1 bit per weight instead of 32. About 2x less computation for binary weights: only additions and subtractions, and no gain on CPUs with fused multiply-add. About 58x for binary weights and inputs: measured on one convolution with c = 256 and 3 × 3 filters, 62.27x in theory.

الذاكرة أقل بنحو 32x في كلا الصفين الثنائيين: بت 1 لكل وزن بدل 32. الحساب أقل بنحو 2x للأوزان الثنائية: جمع وطرح فقط، ولا مكسب على المعالجات التي فيها fused multiply-add. ونحو 58x للأوزان والمدخلات الثنائية: مقيسة على convolution واحدة مع c = 256 وfilters بحجم 3 × 3، و62.27x نظريًا.

Recapالخلاصة

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

  • With both operands in {-1, +1}, every product is ±1: +1 when the signs agree, -1 when they differ.عندما يكون المعاملان كلاهما في {-1, +1} يكون كل حاصل ضرب ±1: يكون +1 عندما تتفق الإشارتان، و-1 عندما تختلفان.
  • Encode +1 as bit 1 and -1 as bit 0. Then XNOR(b_w, b_x) is 1 exactly where W × x = +1, so XNOR is the product in disguise.رمّز +1 بالبت 1 و-1 بالبت 0. عندها تكون XNOR(b_w, b_x) مساوية 1 بالضبط حيث W × x = +1، أي أن XNOR هي حاصل الضرب متنكرًا.
  • Summing XNOR bits counts matches only. It ignores that each mismatch contributes -1, so it gives 1 instead of -2 on the slide example.جمع بتات XNOR يعدّ التطابقات فقط، ويتجاهل أن كل عدم تطابق يساهم بـ -1، لذلك يعطي 1 بدل -2 في مثال الشرائح.
  • Matches m and mismatches n - m give y = m - (n - m) = 2m - n. With m = popcount(W xnor x): y = -n + 2 · popcount.التطابقات m وعدم التطابقات n - m تعطي y = m - (n - m) = 2m - n. ومع m = popcount(W xnor x) نحصل على y = -n + 2 · popcount.
  • Hardware form: y = -n + (popcount(W xnor x) << 1). The shift binds to the popcount; written without brackets in C it would apply to the whole sum.الصيغة العتادية: y = -n + (popcount(W xnor x) << 1). الإزاحة (shift) ترتبط بالـ popcount وحده؛ ولو كُتبت بلا أقواس في لغة C لطُبّقت على المجموع كله.
  • Slide example: 1010 xnor 1101 = 1000, popcount 1, shifted 2, y = -4 + 2 = -2. Exercise with n = 8: popcount 5, y = -8 + 10 = 2.مثال الشرائح: 1010 xnor 1101 = 1000، والـ popcount يساوي 1، وبعد الإزاحة يصبح 2، فيكون y = -4 + 2 = -2. وفي التمرين مع n = 8: الـ popcount يساوي 5، و y = -8 + 10 = 2.
  • XNOR-Net reports about 32x memory saving and about 58x faster convolutions (62.27x theoretical, c = 256, 3 × 3 filters, 64 bit operations per clock). Binary weights alone give about 2x.تذكر ورقة XNOR-Net توفيرًا في الذاكرة بنحو 32x وتسريعًا للـ convolutions بنحو 58x (و62.27x نظريًا، مع c = 256 ومرشحات 3 × 3 و64 عملية بت لكل دورة ساعة). أما الأوزان الثنائية وحدها فتعطي نحو 2x.

Sourcesالمصادر