logicaffeine_compile/codegen_dram/dataflow.rs
1//! DRAM dataflow composition — the spatial-dataflow layer of the compute-in-memory target.
2//!
3//! The DRAM plane's hardware basis is `{Copy, And, Or}` (unmodified ComputeDRAM: RowClone + the
4//! sense-amp majority) plus `Not` (the Ambit tier: dual-contact cells). `{AND, OR, NOT}` is
5//! FUNCTIONALLY COMPLETE, so every boolean function — XOR, NAND, NOR, XNOR, set difference, … — is
6//! realized by CHAINING those primitives through intermediate rows. That chaining IS a spatial
7//! dataflow graph: edges are DRAM rows, nodes are in-DRAM primitives, and the memory computes the
8//! whole graph in place. Composed bit-serially over bitplanes, the same basis yields integer
9//! ARITHMETIC (ripple-carry ADD from XOR+MAJ) — the SIMDRAM construction (Hajinazar et al., ASPLOS
10//! 2021). Every composed op is proven ≡ its reference by executing the emitted prim sequence on the
11//! Ambit-tier DRAM executor ([`exec_dram_ambit`]).
12
13use crate::codegen_sva::unified_placement::{exec_dram_ambit, Prim, Row};
14
15/// A straight-line in-DRAM dataflow graph: a growable row heap (operands then scratch) and the prim
16/// sequence computed over it. `not`/`and`/`or`/`copy` append a node writing a FRESH scratch row and
17/// return its index; higher-level gates compose those. This is the compiler-side spatial graph the
18/// DRAM plane executes.
19#[derive(Clone, Debug, Default)]
20pub struct DramDataflow {
21 next: usize,
22 prog: Vec<Prim>,
23}
24
25impl DramDataflow {
26 /// A dataflow over `inputs` operand rows (indices `0..inputs`); scratch rows are appended above.
27 pub fn new(inputs: usize) -> Self {
28 DramDataflow {
29 next: inputs,
30 prog: Vec::new(),
31 }
32 }
33
34 fn fresh(&mut self) -> usize {
35 let r = self.next;
36 self.next += 1;
37 r
38 }
39
40 /// Total rows (operands + scratch) the graph touches.
41 pub fn rows(&self) -> usize {
42 self.next
43 }
44
45 /// The number of in-DRAM primitive steps (dataflow nodes) — the cost of the kernel.
46 pub fn node_count(&self) -> usize {
47 self.prog.len()
48 }
49
50 /// The emitted prim sequence (the spatial dataflow, in execution order).
51 pub fn program(&self) -> &[Prim] {
52 &self.prog
53 }
54
55 // ── The hardware basis: {Copy, And, Or} (ComputeDRAM) + Not (Ambit). ──
56 pub fn copy(&mut self, a: usize) -> usize {
57 let d = self.fresh();
58 self.prog.push(Prim::Copy { dst: d, src: a });
59 d
60 }
61 pub fn not(&mut self, a: usize) -> usize {
62 let d = self.fresh();
63 self.prog.push(Prim::Not { dst: d, src: a });
64 d
65 }
66 pub fn and(&mut self, a: usize, b: usize) -> usize {
67 let d = self.fresh();
68 self.prog.push(Prim::And { dst: d, a, b });
69 d
70 }
71 pub fn or(&mut self, a: usize, b: usize) -> usize {
72 let d = self.fresh();
73 self.prog.push(Prim::Or { dst: d, a, b });
74 d
75 }
76
77 // ── Composed gates (functional completeness from {AND, OR, NOT}). ──
78 /// XOR = (a OR b) AND NOT(a AND b).
79 pub fn xor(&mut self, a: usize, b: usize) -> usize {
80 let or = self.or(a, b);
81 let and = self.and(a, b);
82 let nand = self.not(and);
83 self.and(or, nand)
84 }
85 pub fn nand(&mut self, a: usize, b: usize) -> usize {
86 let t = self.and(a, b);
87 self.not(t)
88 }
89 pub fn nor(&mut self, a: usize, b: usize) -> usize {
90 let t = self.or(a, b);
91 self.not(t)
92 }
93 pub fn xnor(&mut self, a: usize, b: usize) -> usize {
94 let x = self.xor(a, b);
95 self.not(x)
96 }
97 /// Set difference a \ b = a AND NOT b.
98 pub fn difference(&mut self, a: usize, b: usize) -> usize {
99 let nb = self.not(b);
100 self.and(a, nb)
101 }
102 /// Bitwise majority MAJ(a,b,c) = (a AND b) OR (a AND c) OR (b AND c) — the full-adder carry.
103 pub fn majority(&mut self, a: usize, b: usize, c: usize) -> usize {
104 let ab = self.and(a, b);
105 let ac = self.and(a, c);
106 let bc = self.and(b, c);
107 let t = self.or(ab, ac);
108 self.or(t, bc)
109 }
110
111 /// Realize an ARBITRARY 2-input boolean function from its 4-bit truth table (bit `2·a+b` =
112 /// f(a,b)) as an OR of minterms over `{AND, OR, NOT}` — a constructive functional-completeness
113 /// witness. An empty table yields constant 0 (a AND NOT a).
114 pub fn boolean_fn(&mut self, a: usize, b: usize, truth: u8) -> usize {
115 let mut acc: Option<usize> = None;
116 for k in 0..4u8 {
117 if (truth >> k) & 1 == 1 {
118 let av = (k >> 1) & 1;
119 let bv = k & 1;
120 let ta = if av == 1 { a } else { self.not(a) };
121 let tb = if bv == 1 { b } else { self.not(b) };
122 let m = self.and(ta, tb);
123 acc = Some(match acc {
124 None => m,
125 Some(p) => self.or(p, m),
126 });
127 }
128 }
129 match acc {
130 Some(r) => r,
131 None => {
132 let na = self.not(a);
133 self.and(a, na)
134 }
135 }
136 }
137
138 /// Execute the dataflow in-DRAM (Ambit tier): `inputs` fill rows `0..inputs.len()`, scratch rows
139 /// are zero-initialized, and each node runs through [`exec_dram_ambit`]. Returns the final heap.
140 pub fn run(&self, inputs: &[Row], width: usize) -> Vec<Row> {
141 let mut heap: Vec<Row> = inputs.to_vec();
142 heap.resize(self.next, vec![0u64; width]);
143 for p in &self.prog {
144 exec_dram_ambit(&mut heap, p)
145 .expect("dataflow node must be a DRAM-realizable primitive");
146 }
147 heap
148 }
149}
150
151/// Bit-serial ripple-carry ADD over `B` bitplanes (SIMD across the lanes packed in each row):
152/// for each bit i, `sum_i = a_i XOR b_i XOR carry`, `carry = MAJ(a_i, b_i, carry)`. `a`/`b` are the
153/// operand-plane row indices (LSB first); `carry0` is a zero row. Returns the `B` sum-plane rows.
154/// Composed entirely from the `{AND, OR, NOT}` basis — arithmetic emerging from boolean dataflow.
155pub fn bit_serial_add(
156 df: &mut DramDataflow,
157 a: &[usize],
158 b: &[usize],
159 carry0: usize,
160) -> Vec<usize> {
161 assert_eq!(a.len(), b.len(), "operands must have equal bit width");
162 let mut carry = carry0;
163 let mut sum = Vec::with_capacity(a.len());
164 for i in 0..a.len() {
165 let axb = df.xor(a[i], b[i]);
166 sum.push(df.xor(axb, carry));
167 if i + 1 < a.len() {
168 carry = df.majority(a[i], b[i], carry);
169 }
170 }
171 sum
172}
173
174/// Bit-serial two's-complement SUBTRACT: `a - b = a + NOT(b) + 1` (mod 2^B). Negates each `b` plane
175/// and ripple-adds with carry-in 1 (`ones_carry` = a row with every lane's bit set). Returns the `B`
176/// difference-plane rows. Arithmetic subtraction, still composed from the boolean basis in-DRAM.
177pub fn bit_serial_sub(
178 df: &mut DramDataflow,
179 a: &[usize],
180 b: &[usize],
181 ones_carry: usize,
182) -> Vec<usize> {
183 let nb: Vec<usize> = b.iter().map(|&bi| df.not(bi)).collect();
184 bit_serial_add(df, a, &nb, ones_carry)
185}
186
187/// Bit-serial unsigned MULTIPLY (shift-add): for each bit i of `b`, add `a` (masked by plane `b[i]`)
188/// shifted up by i into an `out_width`-plane accumulator. Composed from AND + [`bit_serial_add`] —
189/// integer multiply from the boolean basis. Result is `a·b` mod 2^out_width per lane; `zero` is a
190/// zero row (accumulator seed + carry-in + high-plane filler).
191pub fn bit_serial_mul(
192 df: &mut DramDataflow,
193 a: &[usize],
194 b: &[usize],
195 out_width: usize,
196 zero: usize,
197) -> Vec<usize> {
198 let mut acc: Vec<usize> = vec![zero; out_width];
199 for i in 0..b.len() {
200 // partial = (a masked by b[i]) placed at bit offset i.
201 let masked: Vec<usize> = a.iter().map(|&aj| df.and(aj, b[i])).collect();
202 let addend: Vec<usize> = (0..out_width)
203 .map(|p| {
204 if p >= i && p - i < a.len() {
205 masked[p - i]
206 } else {
207 zero
208 }
209 })
210 .collect();
211 acc = bit_serial_add(df, &acc, &addend, zero);
212 }
213 acc
214}
215
216#[cfg(test)]
217#[path = "../../../logicaffeine_tests/unit/logicaffeine_compile/codegen_dram/dataflow/tests.rs"]
218mod tests;