Lecture 04-2 · Pruning and Sparsity IIالمحاضرة 04-2 · التقليم والتناثر II

EIE dataflow, PE pipeline and relative-index CSC

تدفق البيانات في EIE، وخط معالجة PE، وCSC بالفهرس النسبي

Slides 61–70الشرائح 61–70 P2 SHOULD

Follow one nonzero activation from the central controller into a processing element: it is queued, two pointers bound its column, 8-bit entries are fetched, decoded and multiplied, and the result lands in a register. Know the stages in order and the storage format bit by bit.

تتبّع activation واحداً غير صفري من وحدة التحكم المركزية إلى داخل processing element: يدخل الطابور، ثم يحدد مؤشران حدود عموده، ثم تُجلب مُدخلات من 8-bit وتُفك وتُضرب، ثم تُكتب النتيجة في سجل. احفظ المراحل بالترتيب وصيغة التخزين بتاً بتاً.

What gets askedما الذي يُسأل عنه

Name the PE stages in order, explain the relative index and why a padding zero is needed, derive a pointer array, and quote the key numbers: 4-bit code plus 4-bit index, 16-entry codebook, 16-bit fixed point, FIFO depth 8, 64 PEs, 162 KB SRAM per PE.

سمِّ مراحل PE بالترتيب، واشرح relative index ولماذا نحتاج padding zero، واستخرج مصفوفة المؤشرات، واذكر الأرقام الأساسية: 4-bit code زائد 4-bit index، وcodebook من 16 قيمة، و16-bit fixed point، وFIFO depth 8، و64 PEs، و162 KB SRAM لكل PE.

The dataflow, slides 61 to 63

تدفق البيانات، الشرائح 61 إلى 63

The central control unit (CCU) scans the input vector a for its next nonzero aj and broadcasts the pair (value, index) = (aj, j) to every PE. Each PE looks up its own nonzeros in column j, multiplies each by aj, and accumulates into the output rows it owns. No partial sums are ever exchanged between PEs; the only communication is the broadcast.

وحدة التحكم المركزية (CCU) تمسح متجه الدخل a بحثاً عن القيمة غير الصفرية التالية aj وتبثّ الزوج (value, index) = (aj, j) إلى كل PE. كل PE يبحث عن قيمه غير الصفرية في العمود j، ويضرب كلاً منها في aj، ويجمع في صفوف الخرج التي يملكها. لا تُتبادل أي partial sums بين PEs؛ الاتصال الوحيد هو البث.

In the 8 x 4 example from the previous page, a = (0, a1, 0, a3): the broadcast of a1 gives PE0, PE2 and PE3 one multiply each; the broadcast of a3 gives PE0 and PE2 two each. Total 7 multiplies against 32 dense.

في مثال 8 x 4 من الصفحة السابقة، a = (0, a1, 0, a3): بثّ a1 يعطي PE0 وPE2 وPE3 عملية ضرب واحدة لكل منها؛ وبثّ a3 يعطي PE0 وPE2 عمليتين لكل منهما. المجموع 7 عمليات ضرب مقابل 32 في الحالة الكثيفة.

Inside one PE, slides 64 to 70

داخل PE واحد، الشرائح 64 إلى 70

1. Act Queue FIFO depth 8 2. Pointer Read even / odd banks 3. Sparse Matrix Access, 128 KB 4. Arithmetic decode, x, + 5. Act R/W src / dest regs 6. ReLU + LNZD next nonzero ONE PE, LEFT TO RIGHT in: (a_j, j) from CCU j p_j, p_j+1 code4 | gap4 b_x += v·a_j dest regs nonzero outputs become the next layer's broadcast (via the CCU and H-tree) SRAM registers combinational
The five stages of slide 70 plus the ReLU and leading nonzero detection tail. Blue labels between boxes are what crosses each boundary.المراحل الخمس في الشريحة 70 ومعها الذيل المكوّن من ReLU وleading nonzero detection. التسميات الزرقاء بين الصناديق هي ما يعبر كل حد بين مرحلتين.
  1. Act Queue. A FIFO of broadcast (aj, j) pairs, depth 8. It lets a PE with little work in one column run ahead while a busy PE catches up. This is the load-balance fix; the broadcast stalls only when some PE's queue is full.

    Act Queue. طابور FIFO لأزواج (aj, j) المبثوثة، بعمق 8. يسمح لـ PE قليل العمل في عمود ما بالتقدم بينما يلحق PE المشغول. هذا هو حل load balance؛ ويتوقف البث فقط عندما يمتلئ طابور أحد PEs.

  2. Pointer Read. The index j reads pj and pj+1, the start and end of column j. They are adjacent addresses, so they sit in different banks (even and odd), and both are read in one cycle from single-ported SRAM.

    Pointer Read. الـ index j يقرأ pj وpj+1، أي بداية العمود j ونهايته. هما عنوانان متجاوران، فيقعان في بنكين مختلفين (even وodd)، ويُقرآن معاً في دورة واحدة من SRAM أحادية المنفذ.

  3. Sparse Matrix Access. Fetches the 8-bit entries of column j from the sparse matrix SRAM: each is a 4-bit weight code plus a 4-bit relative index.

    Sparse Matrix Access. يجلب مُدخلات العمود j ذات 8-bit من sparse matrix SRAM: كل منها 4-bit weight code زائد 4-bit relative index.

  4. Arithmetic Unit. The weight decoder turns the code into a 16-bit fixed-point weight via the 16-entry codebook; the address accumulator turns relative indices into an absolute row x; then bx = bx + v · aj. A bypass path forwards the adder output when two consecutive entries hit the same accumulator.

    Arithmetic Unit. يحوّل weight decoder الـ code إلى وزن 16-bit fixed point عبر codebook من 16 قيمة؛ ويحوّل address accumulator الـ relative indices إلى صف مطلق x؛ ثم bx = bx + v · aj. ومسار bypass يمرر خرج الجامع مباشرة عندما تصيب مُدخلتان متتاليتان نفس السجل.

  5. Act R/W. Two register files, source and destination. The destination collects this layer's outputs while the source feeds its inputs; at the next layer they swap roles, so nothing is copied.

    Act R/W. ملفّا سجلات، source وdestination. الوجهة تجمع مخرجات هذه الطبقة بينما المصدر يغذي مدخلاتها؛ وفي الطبقة التالية يتبادلان الأدوار، فلا يُنسخ شيء.

  6. ReLU and Leading Nonzero Detection (LNZD). ReLU clamps negatives to zero; LNZD finds the next nonzero to broadcast. It is hierarchical: each group of 4 PEs feeds a detector node, and the root sits in the CCU.

    ReLU وLeading Nonzero Detection (LNZD). ReLU يحوّل القيم السالبة إلى صفر؛ وLNZD يجد القيمة غير الصفرية التالية للبث. وهو هرمي: كل مجموعة من 4 PEs تغذي عقدة كشف، والجذر في CCU.

Storage: relative-index CSC

التخزين: CSC بالفهرس النسبي

Standard compressed sparse column (CSC) stores three arrays: the nonzero values, the absolute row index of each, and a column pointer array p so that column j occupies entries pj to pj+1 − 1. EIE keeps values and pointers but replaces the absolute row with a relative index z: the number of zeros since the previous nonzero in that PE's slice of the column.

Compressed sparse column (CSC) القياسي يخزّن ثلاث مصفوفات: القيم غير الصفرية، ورقم الصف المطلق لكل منها، ومصفوفة مؤشرات أعمدة p بحيث يشغل العمود j المُدخلات من pj إلى pj+1 − 1. يحتفظ EIE بالقيم والمؤشرات لكنه يستبدل رقم الصف المطلق بـ relative index z: عدد الأصفار منذ آخر قيمة غير صفرية في شريحة ذلك PE من العمود.

FieldالحقلWidthالعرضMeaningالمعنى
v (weight code)v (رمز الوزن)4 bit4 bitindex into the layer's 16-entry codebookفهرس داخل codebook الطبقة ذي 16 مُدخلة
z (relative index)z (الفهرس النسبي)4 bit4 bitzeros since the previous nonzero, max 15عدد الأصفار منذ القيمة غير الصفرية السابقة، بحد أقصى 15
one entryمُدخلة واحدة8 bit8 bitv and z packed togetherv وz محزومان معاً
column pointer pمؤشر العمود p16 bit16 bitpj+1 − pj = entries in column jpj+1 − pj = عدد المُدخلات في العمود j
decoded weightالوزن بعد فك الترميز16 bit16 bitfixed point, what the multiplier seesفاصلة ثابتة (fixed point)، وهو ما يراه المضاعِف

A 4-bit z can count at most 15 zeros. When a gap is longer, the encoder inserts a padding zero: an entry with v = 0 and z = 15. It is stored, read, decoded to 0, multiplied and accumulated like any real entry, so it wastes one cycle and 8 bits, but it keeps the format fixed-width. More PEs mean shorter slices per column and fewer long gaps, so fewer padding zeros.

z ذو 4-bit يعدّ 15 صفراً على الأكثر. إذا كانت الفجوة أطول، يُدخل المُرمِّز padding zero: مُدخلة فيها v = 0 وz = 15. تُخزَّن وتُقرأ وتُفك إلى 0 وتُضرب وتُجمع مثل أي مُدخلة حقيقية، فتهدر دورة واحدة و8 bits، لكنها تبقي الصيغة ثابتة العرض. وكلما زاد عدد PEs قصرت شريحة العمود لكل منها وقلّت الفجوات الطويلة، فيقل عدد padding zeros.

· 0 · 1 1 2 2 3 · 4 · 5 · 6 · 7 · 8 · 9 · 10 · 11 · 12 · 13 · 14 · 15 · 16 · 17 · 18 0 19 · 20 · 21 3 22 row index in this PE's slice of the column gap 2 15 zeros gap 2 v=1 z=2 v=2 z=0 v=0 z=15 v=3 z=2 stored 8-bit entries 4-bit code | 4-bit gap; the orange entry is the padding zero
The paper's example: nonzeros 1, 2, 3 at rows 2, 3 and 22. The gap from row 3 to row 22 is 18 zeros, more than 15, so a padding entry (0, 15) occupies row 19 and the 3 follows with z = 2.مثال البحث: القيم غير الصفرية 1 و2 و3 في الصفوف 2 و3 و22. الفجوة من الصف 3 إلى الصف 22 هي 18 صفراً، أي أكثر من 15، لذلك تشغل مُدخلة حشو (0, 15) الصف 19، ثم تأتي القيمة 3 مع z = 2.
Worked: encode, then decodeمثال محلول: الترميز ثم فك الترميز

Column (one PE's slice): value 1 at row 2, value 2 at row 3, value 3 at row 22, zeros elsewhere.

العمود (شريحة PE واحد): القيمة 1 في الصف 2، والقيمة 2 في الصف 3، والقيمة 3 في الصف 22، وأصفار في البقية.

encode
row 2 : zeros before = 2                      -> (v=1, z=2)
row 3 : zeros since row 2 = 0                 -> (v=2, z=0)
row 22: zeros since row 3 = 18 > 15
        pad after 15 zeros, lands on row 19   -> (v=0, z=15)
        zeros since row 19 = 2 (rows 20, 21)  -> (v=3, z=2)
v = [1, 2, 0, 3]   z = [2, 0, 15, 2]           4 entries x 8 bit = 32 bits

decode (address accumulator: row = prev + z + 1, prev starts at -1)
-1 + 2 + 1  = 2     2 + 0 + 1 = 3     3 + 15 + 1 = 19 (pad)     19 + 2 + 1 = 22

Pointers for PE0 of the 8 x 4 example (rows 0 and 4; column entry counts 1, 1, 1, 2): p = [0, 1, 2, 3, 5]. Column 3 is entries p3 = 3 to p4 − 1 = 4, two entries, which is p4 − p3 = 2.

مؤشرات PE0 في مثال 8 x 4 (الصفان 0 و4؛ عدد المُدخلات في الأعمدة 1, 1, 1, 2): p = [0, 1, 2, 3, 5]. العمود 3 هو المُدخلات من p3 = 3 إلى p4 − 1 = 4، أي مُدخلتان، وهذا هو p4 − p3 = 2.

Weight sharing: 4 bits stored, 16 bits computed

مشاركة الأوزان: 4 bits تُخزَّن و16 bits تُحسب

The stored code is not a weight. It indexes a per-layer table of 16 shared weights from k-means (Deep Compression), and the decoder expands it to 16-bit fixed point right before the multiplier. 16-bit fixed point costs about 0.5 point of AlexNet accuracy against 32-bit float (79.8% vs 80.3%), while 8-bit fixed point collapses to 53.0%.

الـ code المخزّن ليس وزناً. إنه يشير إلى جدول لكل طبقة من 16 وزناً مشتركاً ناتج عن k-means (Deep Compression)، والـ decoder يوسّعه إلى 16-bit fixed point قبل المضاعف مباشرة. يكلف 16-bit fixed point نحو 0.5 نقطة من دقة AlexNet مقارنةً بـ 32-bit float (79.8% مقابل 80.3%)، بينما ينهار 8-bit fixed point إلى 53.0%.

Key numbers

أرقام أساسية

64 PEs at 800 MHz. FIFO depth 8 (depth 1 leaves about half of all cycles idle). 162 KB SRAM per PE, of which 128 KB is sparse matrix SRAM. SRAM is 93% of PE area.

64 PEs بتردد 800 MHz. FIFO depth 8 (العمق 1 يترك نحو نصف الدورات خاملة). 162 KB SRAM لكل PE، منها 128 KB لـ sparse matrix SRAM. وتشكل SRAM نسبة 93% من مساحة PE.

Why relative, not absolute

لماذا نسبي وليس مطلقاً

A 4096-row layer needs 12 bits for an absolute row (6 bits even PE-local over 64 PEs). A 4-bit gap matches the 4-bit code, so one 8-bit entry holds both. The price is the occasional padding zero.

طبقة من 4096 صفاً تحتاج 12 bits لرقم صف مطلق (و6 bits حتى محلياً مع 64 PEs). الفجوة ذات 4-bit تطابق الـ code ذا 4-bit، فتحمل مُدخلة واحدة من 8-bit الاثنين معاً. والثمن هو padding zero أحياناً.

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

z is a gap, not a row number. Rows 2, 3 encode as z = 2, 0, not 2, 3. To recover the row, add z + 1 to the previous row. The padding zero exists because z has only 4 bits: a gap of 18 cannot be written, so (0, 15) is inserted and counts as a position itself, leaving z = 2, not 3. It is computed like a real weight (wasted work), not skipped. Also: the codebook decodes to 16-bit fixed point, not 32-bit float, and pointers are 16 bits, not 4.

z فجوة، وليس رقم صف. الصفان 2, 3 يُرمَّزان كـ z = 2, 0 لا 2, 3. لاستعادة الصف أضف z + 1 إلى الصف السابق. padding zero موجود لأن z له 4 bits فقط: فجوة 18 لا يمكن كتابتها، فتُدخل (0, 15) وتُحسب هي نفسها موقعاً، فيبقى z = 2 لا 3. وهو يُحسب كوزن حقيقي (عمل مهدور) ولا يُتخطى. كذلك: codebook يُفك إلى 16-bit fixed point لا 32-bit float، والمؤشرات 16 bits لا 4.

Memory trickحيلة للحفظ

The stage order reads as a sentence: "Queue, Point, Access, Compute, Write, then ReLU finds the next." And the entry is "four and four make eight": 4-bit code, 4-bit gap, 8-bit entry, 15 is the longest gap.

ترتيب المراحل يُقرأ كجملة: "اصطف، أشِر، اجلب، احسب، اكتب، ثم يجد ReLU التالي." والمُدخلة "أربعة وأربعة تساوي ثمانية": 4-bit code و4-bit gap و8-bit entry، و15 هي أطول فجوة.

Check yourself

اختبر نفسك

A PE's slice of a column has nonzeros 5 at row 2 and 7 at row 7. What is the relative-index encoding?

شريحة PE من عمود فيها القيمة 5 في الصف 2 والقيمة 7 في الصف 7. ما ترميز relative index؟

B. Two zeros precede row 2; rows 3, 4, 5, 6 are four zeros between the two values. A uses absolute rows; C uses the row difference 7 − 2 = 5 instead of the zero count; D inserts a padding zero that is only needed for gaps above 15.

الجواب B. يسبق الصف 2 صفران؛ والصفوف 3, 4, 5, 6 أربعة أصفار بين القيمتين. والخيار A يستخدم أرقام الصفوف المطلقة؛ وC يستخدم الفرق 7 − 2 = 5 بدلاً من عدد الأصفار؛ وD يُدخل padding zero لا يلزم إلا لفجوات أكبر من 15.

Why does EIE need a padding zero?

لماذا يحتاج EIE إلى padding zero؟

C. A gap of 16 or more zeros does not fit in 4 bits, so an entry (0, 15) is inserted and counting restarts after it. B is the pointer array's job (pj+1 marks the end); D is the activation queue's job.

الجواب C. فجوة من 16 صفراً أو أكثر لا تتسع في 4 bits، فتُدخل مُدخلة (0, 15) ويُستأنف العد بعدها. والخيار B هو وظيفة مصفوفة المؤشرات (pj+1 يحدد النهاية)؛ وD وظيفة activation queue.

A PE's pointer array is p = [0, 3, 3, 7]. How many stored entries does column 1 have?

مصفوفة المؤشرات في PE هي p = [0, 3, 3, 7]. كم مُدخلة مخزّنة في العمود 1؟

A. Entries in column j are pj+1 − pj; for j = 1 that is 3 − 3 = 0, so this PE has no work when a1 is broadcast. B is p1 itself (column 0's count), C is column 2's count, D is the total.

الجواب A. عدد مُدخلات العمود j هو pj+1 − pj؛ وعند j = 1 يساوي 3 − 3 = 0، فلا عمل لهذا PE عند بث a1. والخيار B هو p1 نفسه (عدد العمود 0)، وC عدد العمود 2، وD المجموع.

What do the even and odd pointer SRAM banks buy?

ماذا يوفّر تقسيم pointer SRAM إلى بنكين even وodd؟

D. Adjacent addresses differ in their least significant bit, so the two bounds always sit in different banks. Pointers stay 16 bits (A), skipping zero activations is LNZD's job (B), and the decoder handles one weight per cycle (C).

الجواب D. العنوانان المتجاوران يختلفان في البت الأقل أهمية، فيقع الحدّان دائماً في بنكين مختلفين. المؤشرات تبقى 16 bits (A)، وتخطي activations الصفرية وظيفة LNZD (B)، والـ decoder يعالج وزناً واحداً في كل دورة (C).

Which stage order matches the EIE PE?

أي ترتيب للمراحل يطابق PE في EIE؟

B. The broadcast pair is queued, its index reads the column bounds, the bounds fetch the entries, the entries are decoded and multiplied, and the result is written. You cannot fetch entries (C) before knowing where the column starts.

الجواب B. يدخل الزوج المبثوث الطابور، ثم يقرأ الـ index حدود العمود، ثم تجلب الحدود المُدخلات، ثم تُفك المُدخلات وتُضرب، ثم تُكتب النتيجة. ولا يمكن جلب المُدخلات (C) قبل معرفة أين يبدأ العمود.