logicaffeine_compile/codegen_sva/
unified_placement.rs

1//! unified_placement — Phase 5: ONE LOGOS program placed across THREE execution planes that all run
2//! LOGOS (host-CPU tiers, the reconfigurable fabric-CPU, and the DRAM-compute plane), under a single
3//! shared primitive descriptor, certified ≡ the VM.
4//!
5//! The bet of the whole campaign, made mechanical: a bulk-bitwise/copy LOGOS op can run *inside the
6//! memory* (ComputeDRAM), a spatial op on the fabric, and everything else on the host CPU — and the
7//! compiler places each op where it wins, with the shared DRAM heap as the common data plane and no
8//! marshalling between planes. Because every plane's per-op semantics are individually ≡VM (host is
9//! the reference; the DRAM path is `super::dram::word_majority` — AND=MAJ(a,b,0), OR=MAJ(a,b,1),
10//! proven in Phase 0; the fabric computes the same bitwise result), the placed whole program is ≡VM.
11//!
12//! `PRIMS` is the SINGLE SOURCE OF TRUTH: both the placement pass and the per-plane executors read it,
13//! and a drift lock proves the DRAM executor supports exactly the ops the descriptor advertises.
14
15use super::dram::word_majority;
16
17/// The execution planes, all of which run LOGOS.
18#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
19pub enum Plane {
20    /// The i9 running the interpreter / VM / JIT / AOT / WASM tiers — universal (runs every op).
21    HostCpu,
22    /// The reconfigurable spatial fabric.
23    Fabric,
24    /// Compute-in-memory: bulk bitwise / copy inside the DDR2 (ComputeDRAM).
25    Dram,
26}
27
28/// The op kinds in the shared primitive vocabulary.
29#[derive(Clone, Copy, PartialEq, Eq, Debug)]
30pub enum PrimKind {
31    Copy,
32    And,
33    Or,
34    Not,
35    Xor,
36    Popcount,
37}
38
39/// A bulk primitive over whole bit-vector rows in the shared data plane (row indices into the heap).
40#[derive(Clone, Copy, PartialEq, Eq, Debug)]
41pub enum Prim {
42    Copy {
43        dst: usize,
44        src: usize,
45    },
46    And {
47        dst: usize,
48        a: usize,
49        b: usize,
50    },
51    Or {
52        dst: usize,
53        a: usize,
54        b: usize,
55    },
56    Not {
57        dst: usize,
58        src: usize,
59    },
60    Xor {
61        dst: usize,
62        a: usize,
63        b: usize,
64    },
65    /// Count the set bits of `src` into word 0 of `dst` (a reduction — host-CPU only).
66    Popcount {
67        dst: usize,
68        src: usize,
69    },
70}
71
72impl Prim {
73    pub fn kind(&self) -> PrimKind {
74        match self {
75            Prim::Copy { .. } => PrimKind::Copy,
76            Prim::And { .. } => PrimKind::And,
77            Prim::Or { .. } => PrimKind::Or,
78            Prim::Not { .. } => PrimKind::Not,
79            Prim::Xor { .. } => PrimKind::Xor,
80            Prim::Popcount { .. } => PrimKind::Popcount,
81        }
82    }
83}
84
85/// One entry of the shared primitive descriptor: which planes can realize this op. The DRAM plane has
86/// TWO tiers: `dram` = unmodified ComputeDRAM (Gao et al., MICRO 2019 — RowClone + MAJ-based AND/OR);
87/// `dram_ambit` = the Ambit tier (Seshadri et al., MICRO 2017), which adds bulk NOT (dual-contact
88/// cells) and thereby XOR, at the cost of MINOR DRAM modifications. `dram_ambit` is a superset of
89/// `dram`.
90#[derive(Clone, Copy, Debug)]
91pub struct PrimDesc {
92    pub kind: PrimKind,
93    pub host_cpu: bool,
94    pub fabric: bool,
95    pub dram: bool,
96    pub dram_ambit: bool,
97}
98
99/// THE SINGLE SOURCE OF TRUTH. host_cpu is always true (the host runs everything — the universal
100/// fallback). `dram` is true only for the ops UNMODIFIED ComputeDRAM realizes: RowClone (copy) + bulk
101/// bitwise AND/OR (the sense-amp majority) — the conservative tier the placement pass routes to.
102/// `dram_ambit` additionally covers NOT + XOR (the Ambit boolean basis) on minor-modification DRAM;
103/// the codegen_dram target uses this tier. Reductions (Popcount) are control-shaped → host only, on
104/// neither tier.
105pub const PRIMS: &[PrimDesc] = &[
106    PrimDesc {
107        kind: PrimKind::Copy,
108        host_cpu: true,
109        fabric: true,
110        dram: true,
111        dram_ambit: true,
112    },
113    PrimDesc {
114        kind: PrimKind::And,
115        host_cpu: true,
116        fabric: true,
117        dram: true,
118        dram_ambit: true,
119    },
120    PrimDesc {
121        kind: PrimKind::Or,
122        host_cpu: true,
123        fabric: true,
124        dram: true,
125        dram_ambit: true,
126    },
127    PrimDesc {
128        kind: PrimKind::Not,
129        host_cpu: true,
130        fabric: true,
131        dram: false,
132        dram_ambit: true,
133    },
134    PrimDesc {
135        kind: PrimKind::Xor,
136        host_cpu: true,
137        fabric: true,
138        dram: false,
139        dram_ambit: true,
140    },
141    PrimDesc {
142        kind: PrimKind::Popcount,
143        host_cpu: true,
144        fabric: false,
145        dram: false,
146        dram_ambit: false,
147    },
148];
149
150pub fn desc(kind: PrimKind) -> &'static PrimDesc {
151    PRIMS
152        .iter()
153        .find(|d| d.kind == kind)
154        .expect("every PrimKind has a descriptor")
155}
156
157/// Operands at least this many u64 words wide favor in-DRAM execution (the bytes-not-moved win).
158pub const WIDE_WORDS: usize = 8;
159
160/// The placement pass: choose the plane for `prim` given its operand width, from the shared descriptor.
161/// Bulk/wide bitwise + copy → DRAM (compute-in-memory); otherwise the fabric; else the host CPU (which
162/// runs everything). Never fails — the host is the universal fallback.
163pub fn place(prim: &Prim, operand_words: usize) -> Plane {
164    let d = desc(prim.kind());
165    if d.dram && operand_words >= WIDE_WORDS {
166        Plane::Dram // bulk/wide bitwise or copy: compute in place, move no bytes across the bus
167    } else if d.fabric {
168        Plane::Fabric // spatial/parallel bitwise the DRAM can't do (or too narrow to win in-memory)
169    } else {
170        debug_assert!(d.host_cpu, "every op is at least host-CPU realizable");
171        Plane::HostCpu // reductions / control — the universal fallback
172    }
173}
174
175/// A row of the shared data plane: a bit vector packed into u64 words.
176pub type Row = Vec<u64>;
177
178/// The reference (VM) semantics of a primitive over the heap — the oracle every plane is proven against.
179pub fn exec_reference(heap: &mut [Row], prim: &Prim) {
180    match *prim {
181        Prim::Copy { dst, src } => heap[dst] = heap[src].clone(),
182        Prim::And { dst, a, b } => {
183            heap[dst] = heap[a].iter().zip(&heap[b]).map(|(x, y)| x & y).collect()
184        }
185        Prim::Or { dst, a, b } => {
186            heap[dst] = heap[a].iter().zip(&heap[b]).map(|(x, y)| x | y).collect()
187        }
188        Prim::Not { dst, src } => heap[dst] = heap[src].iter().map(|x| !x).collect(),
189        Prim::Xor { dst, a, b } => {
190            heap[dst] = heap[a].iter().zip(&heap[b]).map(|(x, y)| x ^ y).collect()
191        }
192        Prim::Popcount { dst, src } => {
193            let n: u64 = heap[src].iter().map(|w| w.count_ones() as u64).sum();
194            let width = heap[dst].len();
195            heap[dst] = std::iter::once(n)
196                .chain(std::iter::repeat(0))
197                .take(width)
198                .collect();
199        }
200    }
201}
202
203/// Execute `prim` on the DRAM-compute plane (ComputeDRAM semantics): RowClone for copy, the sense-amp
204/// majority reduction for AND (MAJ(a,b,0)) and OR (MAJ(a,b,1)). Returns `None` for ops with no plain-
205/// ComputeDRAM realization (the descriptor's `dram: false` ops). MUST agree op-for-op with [`exec_reference`].
206pub fn exec_dram(heap: &mut [Row], prim: &Prim) -> Option<()> {
207    match *prim {
208        Prim::Copy { dst, src } => heap[dst] = heap[src].clone(), // RowClone
209        Prim::And { dst, a, b } => {
210            heap[dst] = heap[a]
211                .iter()
212                .zip(&heap[b])
213                .map(|(x, y)| word_majority(*x, *y, 0))
214                .collect()
215        }
216        Prim::Or { dst, a, b } => {
217            heap[dst] = heap[a]
218                .iter()
219                .zip(&heap[b])
220                .map(|(x, y)| word_majority(*x, *y, u64::MAX))
221                .collect()
222        }
223        // No plain-ComputeDRAM realization (matches the descriptor's dram: false): NOT needs
224        // Ambit-style dual-contact cells; XOR is multi-step; Popcount is a reduction → fabric/host.
225        Prim::Not { .. } | Prim::Xor { .. } | Prim::Popcount { .. } => return None,
226    }
227    Some(())
228}
229
230/// Execute `prim` on the DRAM plane at the AMBIT tier (Seshadri et al., MICRO 2017): the unmodified
231/// ComputeDRAM ops ([`exec_dram`]) PLUS bulk NOT (dual-contact cells) and XOR (NOT + triple-row MAJ,
232/// a multi-row in-DRAM sequence — the RESULT is exactly `a ^ b`, the ≡VM contract; the sequencing is
233/// the in-DRAM implementation detail). Ambit needs MINOR DRAM modifications, distinct from the
234/// unmodified [`exec_dram`]. Returns `None` only for the reduction (Popcount is control-shaped →
235/// host). Realizes EXACTLY the descriptor's `dram_ambit` ops, and agrees op-for-op with
236/// [`exec_reference`].
237pub fn exec_dram_ambit(heap: &mut [Row], prim: &Prim) -> Option<()> {
238    match *prim {
239        Prim::Copy { .. } | Prim::And { .. } | Prim::Or { .. } => return exec_dram(heap, prim),
240        Prim::Not { dst, src } => heap[dst] = heap[src].iter().map(|x| !x).collect(),
241        Prim::Xor { dst, a, b } => {
242            heap[dst] = heap[a].iter().zip(&heap[b]).map(|(x, y)| x ^ y).collect()
243        }
244        Prim::Popcount { .. } => return None,
245    }
246    Some(())
247}
248
249/// Execute `prim` on the fabric plane. The fabric computes the same bitwise result as the VM (its
250/// tile ALUs are proven ≡VM elsewhere); returns `false` for ops with no fabric realization.
251pub fn exec_fabric(heap: &mut [Row], prim: &Prim) -> bool {
252    if !desc(prim.kind()).fabric {
253        return false;
254    }
255    exec_reference(heap, prim);
256    true
257}
258
259/// Dispatch `prim` to `plane`, asserting the plane can realize it (placement must never assign an op to
260/// a plane that cannot run it). Each plane's result equals the VM reference (proven by the locks).
261pub fn exec_on(plane: Plane, heap: &mut [Row], prim: &Prim) {
262    match plane {
263        Plane::HostCpu => exec_reference(heap, prim),
264        Plane::Fabric => assert!(
265            exec_fabric(heap, prim),
266            "fabric cannot run {:?}",
267            prim.kind()
268        ),
269        Plane::Dram => {
270            exec_dram(heap, prim).unwrap_or_else(|| panic!("DRAM cannot run {:?}", prim.kind()))
271        }
272    }
273}
274
275/// Run a program with placement: each op executes on the plane the cost model assigns it. `operand_words`
276/// is the row width (the placement's size input). Returns the final heap.
277pub fn run_placed(heap0: &[Row], program: &[Prim], operand_words: usize) -> Vec<Row> {
278    let mut heap = heap0.to_vec();
279    for prim in program {
280        exec_on(place(prim, operand_words), &mut heap, prim);
281    }
282    heap
283}
284
285/// Run a program entirely on the host CPU — the VM reference.
286pub fn run_reference(heap0: &[Row], program: &[Prim]) -> Vec<Row> {
287    let mut heap = heap0.to_vec();
288    for prim in program {
289        exec_reference(&mut heap, prim);
290    }
291    heap
292}
293
294#[cfg(test)]
295#[path = "../../../logicaffeine_tests/unit/logicaffeine_compile/codegen_sva/unified_placement/tests.rs"]
296mod tests;
logicaffeine_compile/codegen_sva/unified_placement.rs

logicaffeine_compile/codegen_sva/
unified_placement.rs
