nonbinary.computer
OR-1 dataflow CPU sketch
1"""
2Tests for network topology, routing, and backpressure.
3
4Verifies:
5- or1-emu.AC4.1: PE-to-PE routing — token with dest PE_id N arrives at PE N's input store
6- or1-emu.AC4.2: SM routing — token routes to correct SM by SM_id
7- or1-emu.AC4.3: Backpressure blocking — PE blocks on put() when destination store at capacity
8- or1-emu.AC4.4: Backpressure release — backpressure releases when consumer drains store
9"""
10
11import simpy
12
13from cm_inst import ALUInst, Addr, ArithOp, MemOp, Port, RoutingOp, SMInst
14from emu import build_topology, PEConfig, SMConfig
15from emu.pe import ProcessingElement
16from sm_mod import Presence
17from tokens import CMToken, DyadToken, MonadToken, SMToken
18
19
20class TestAC41PEtoPERouting:
21 """Test AC4.1: PE-to-PE routing"""
22
23 def test_monad_token_routes_to_target_pe(self):
24 """PE0 with PASS instruction outputs token routing to PE1's input_store."""
25 env = simpy.Environment()
26
27 # PE0 has PASS instruction at offset 0, routing to PE1
28 # Note: We use an output_store to collect results without involving PE1's process
29 pe0_iram = {
30 0: ALUInst(
31 op=RoutingOp.PASS,
32 dest_l=Addr(a=0, port=Port.L, pe=1),
33 dest_r=None,
34 const=None,
35 )
36 }
37
38 pe0 = ProcessingElement(env, 0, pe0_iram)
39
40 # Set up output store to collect results (no matching/processing)
41 output_store = simpy.Store(env, capacity=10)
42 pe0.route_table[1] = output_store
43
44 # Inject a MonadToken to PE0
45 def inject():
46 seed_token = MonadToken(
47 target=0,
48 offset=0,
49 ctx=0,
50 data=42,
51 inline=False,
52 )
53 yield pe0.input_store.put(seed_token)
54
55 env.process(inject())
56 env.run(until=100)
57
58 # Verify output_store received a token
59 assert len(output_store.items) > 0
60 result_token = output_store.items[0]
61 # PASS returns left operand (data=42)
62 assert result_token.data == 42
63 assert isinstance(result_token, DyadToken)
64
65 def test_dual_mode_routes_to_both_pes(self):
66 """Dual-mode instruction routes to both dest_l and dest_r PEs."""
67 env = simpy.Environment()
68
69 # PE0 with CONST instruction (dual mode), routes to PE1 and PE2
70 pe0_iram = {
71 0: ALUInst(
72 op=RoutingOp.CONST,
73 dest_l=Addr(a=1, port=Port.L, pe=1),
74 dest_r=Addr(a=2, port=Port.R, pe=2),
75 const=99,
76 )
77 }
78
79 pe0 = ProcessingElement(env, 0, pe0_iram)
80
81 # Set up output stores for each destination
82 output_store_1 = simpy.Store(env, capacity=10)
83 output_store_2 = simpy.Store(env, capacity=10)
84 pe0.route_table[1] = output_store_1
85 pe0.route_table[2] = output_store_2
86
87 # Inject token
88 def inject():
89 seed_token = MonadToken(
90 target=0,
91 offset=0,
92 ctx=0,
93 data=0,
94 inline=False,
95 )
96 yield pe0.input_store.put(seed_token)
97
98 env.process(inject())
99 env.run(until=100)
100
101 # Both stores should have received tokens
102 assert len(output_store_1.items) > 0
103 assert len(output_store_2.items) > 0
104
105 # Both should have CONST value (99)
106 assert output_store_1.items[0].data == 99
107 assert output_store_2.items[0].data == 99
108
109
110class TestAC42SMRouting:
111 """Test AC4.2: SM routing"""
112
113 def test_direct_sm_injection(self):
114 """Direct injection into SM via inject_sm() works correctly."""
115 env = simpy.Environment()
116
117 # Initialize SM0 with a FULL cell at address 5
118 sm_config = SMConfig(
119 sm_id=0,
120 cell_count=512,
121 initial_cells={5: (Presence.FULL, 42)},
122 )
123
124 sys = build_topology(
125 env,
126 [PEConfig(0, {})],
127 [sm_config],
128 )
129
130 # Set up output store for SM results
131 output_store = simpy.Store(env, capacity=10)
132 sys.sms[0].route_table[0] = output_store
133
134 # Create a READ token for cell 5, returning to PE0
135 return_route = CMToken(target=0, offset=10, ctx=0, data=0)
136 sm_token = SMToken(
137 target=0,
138 addr=5,
139 op=MemOp.READ,
140 flags=None,
141 data=None,
142 ret=return_route,
143 )
144
145 sys.inject(sm_token)
146
147 env.run()
148
149 # Verify result arrived in output_store
150 assert len(output_store.items) > 0
151 result = output_store.items[0]
152 assert result.data == 42 # Cell data was read
153 assert result.target == 0
154 assert result.offset == 10
155
156 def test_pe_emits_sm_write(self):
157 """PE emits SMInst that writes to SM."""
158 env = simpy.Environment()
159
160 # PE0 with SMInst(WRITE) at offset 0
161 pe0_iram = {
162 0: SMInst(
163 op=MemOp.WRITE,
164 sm_id=0,
165 const=5, # cell address
166 ret=None,
167 )
168 }
169
170 sys = build_topology(
171 env,
172 [PEConfig(0, pe0_iram)],
173 [SMConfig(0, cell_count=512)],
174 )
175
176 # Inject MonadToken with data=42 to PE0
177 seed_token = MonadToken(
178 target=0,
179 offset=0,
180 ctx=0,
181 data=42,
182 inline=False,
183 )
184 sys.inject(seed_token)
185
186 env.run()
187
188 # Verify SM0's cell 5 is now FULL with data 42
189 cell = sys.sms[0].cells[5]
190 assert cell.pres == Presence.FULL
191 assert cell.data_l == 42
192
193 def test_pe_emits_sm_read_returns_to_pe(self):
194 """PE emits SMInst(READ) which returns result to PE."""
195 env = simpy.Environment()
196
197 # Initialize SM0 with FULL cell at address 3
198 sm_config = SMConfig(
199 sm_id=0,
200 cell_count=512,
201 initial_cells={3: (Presence.FULL, 77)},
202 )
203
204 # PE0 with SMInst(READ) at offset 0
205 pe0_iram = {
206 0: SMInst(
207 op=MemOp.READ,
208 sm_id=0,
209 const=3, # cell address
210 ret=Addr(a=20, port=Port.L, pe=1), # return to PE1
211 )
212 }
213
214 sys = build_topology(
215 env,
216 [PEConfig(0, pe0_iram), PEConfig(1, {})],
217 [sm_config],
218 )
219
220 # Set up output store for PE1 results
221 output_store = simpy.Store(env, capacity=10)
222 sys.sms[0].route_table[1] = output_store
223
224 # Inject MonadToken to PE0
225 def inject():
226 seed_token = MonadToken(
227 target=0,
228 offset=0,
229 ctx=0,
230 data=0,
231 inline=False,
232 )
233 yield sys.pes[0].input_store.put(seed_token)
234
235 env.process(inject())
236 env.run()
237
238 # Verify result arrived in output_store
239 assert len(output_store.items) > 0
240 result = output_store.items[0]
241 assert result.data == 77 # Read cell data
242 assert result.target == 1
243 assert result.offset == 20
244
245
246class TestAC43Backpressure:
247 """Test AC4.3: Backpressure blocking"""
248
249 def test_backpressure_blocks_on_full_store(self):
250 """Delivery process blocks when destination store is full.
251
252 With process-per-token architecture, the PE spawns async delivery processes.
253 The PE itself doesn't block on delivery (pipelined), but the delivery process
254 blocks when destination store is full. With sufficient time, eventual delivery
255 will complete and populate destination store up to capacity.
256 """
257 env = simpy.Environment()
258
259 # PE0 with CONST instruction (emits to destination store)
260 pe0_iram = {
261 0: ALUInst(
262 op=RoutingOp.CONST,
263 dest_l=Addr(a=0, port=Port.L, pe=1),
264 dest_r=None,
265 const=10,
266 )
267 }
268
269 pe0 = ProcessingElement(env, 0, pe0_iram, fifo_capacity=8)
270
271 # Set up a small destination store to trigger backpressure in delivery
272 dest_store = simpy.Store(env, capacity=2)
273 pe0.route_table[1] = dest_store
274
275 # Inject 4 tokens to PE0
276 def inject_tokens():
277 for i in range(4):
278 token = MonadToken(
279 target=0,
280 offset=0,
281 ctx=0,
282 data=i,
283 inline=False,
284 )
285 yield pe0.input_store.put(token)
286
287 env.process(inject_tokens())
288
289 # Run simulation with sufficient time for delivery processes
290 env.run(until=100)
291
292 # All 4 tokens should be processed and delivered (with delivery async)
293 # Destination store should accumulate tokens up to its capacity (2)
294 assert len(dest_store.items) == 2
295
296 # PE input_store should be empty (all tokens dequeued and processed)
297 assert len(pe0.input_store.items) == 0
298
299 # PE should have emitted all 4 tokens (logged in output_log)
300 # delivery may be blocked on store capacity, but all tokens were processed
301 assert len(pe0.output_log) == 4
302
303 def test_pe_unblocks_with_some_tokens(self):
304 """After partial time, some tokens reach destination and store fills."""
305 env = simpy.Environment()
306
307 pe0_iram = {
308 0: ALUInst(
309 op=RoutingOp.CONST,
310 dest_l=Addr(a=0, port=Port.L, pe=1),
311 dest_r=None,
312 const=100,
313 )
314 }
315
316 pe0 = ProcessingElement(env, 0, pe0_iram, fifo_capacity=8)
317
318 # Small destination store
319 dest_store = simpy.Store(env, capacity=2)
320 pe0.route_table[1] = dest_store
321
322 # Inject 6 tokens
323 def inject_tokens():
324 for i in range(6):
325 token = MonadToken(
326 target=0,
327 offset=0,
328 ctx=0,
329 data=i,
330 inline=False,
331 )
332 yield pe0.input_store.put(token)
333
334 env.process(inject_tokens())
335 env.run(until=50)
336
337 # Destination store should be at capacity
338 assert len(dest_store.items) == 2 # fifo_capacity
339
340
341class TestAC44BackpressureRelease:
342 """Test AC4.4: Backpressure release when consumer drains store"""
343
344 def test_backpressure_releases_with_consumer(self):
345 """When consumer drains destination store, producer unblocks and continues."""
346 env = simpy.Environment()
347
348 pe0_iram = {
349 0: ALUInst(
350 op=RoutingOp.CONST,
351 dest_l=Addr(a=0, port=Port.L, pe=1),
352 dest_r=None,
353 const=42,
354 )
355 }
356
357 pe0 = ProcessingElement(env, 0, pe0_iram, fifo_capacity=8)
358
359 # Small destination store
360 dest_store = simpy.Store(env, capacity=2)
361 pe0.route_table[1] = dest_store
362
363 # Track consumed tokens
364 consumed = []
365
366 # Inject 4 tokens to PE0
367 def inject_tokens():
368 for i in range(4):
369 token = MonadToken(
370 target=0,
371 offset=0,
372 ctx=0,
373 data=i,
374 inline=False,
375 )
376 yield pe0.input_store.put(token)
377
378 # Consumer process that drains the destination store
379 def consumer():
380 while True:
381 token = yield dest_store.get()
382 consumed.append(token)
383
384 env.process(inject_tokens())
385 env.process(consumer())
386
387 env.run()
388
389 # All 4 injected tokens should have been consumed by the consumer
390 assert len(consumed) == 4
391 # PE0's input store should be fully drained after all tokens processed
392 assert len(pe0.input_store.items) == 0
393
394 def test_multiple_producers_with_consumer(self):
395 """Multiple producers routing to shared destination, consumer drains."""
396 env = simpy.Environment()
397
398 # PE0 and PE2 both emit to shared destination
399 pe0_iram = {
400 0: ALUInst(
401 op=RoutingOp.CONST,
402 dest_l=Addr(a=0, port=Port.L, pe=1),
403 dest_r=None,
404 const=10,
405 )
406 }
407
408 pe2_iram = {
409 0: ALUInst(
410 op=RoutingOp.CONST,
411 dest_l=Addr(a=1, port=Port.L, pe=1),
412 dest_r=None,
413 const=20,
414 )
415 }
416
417 pe0 = ProcessingElement(env, 0, pe0_iram, fifo_capacity=8)
418 pe2 = ProcessingElement(env, 2, pe2_iram, fifo_capacity=8)
419
420 # Shared destination store
421 dest_store = simpy.Store(env, capacity=2)
422 pe0.route_table[1] = dest_store
423 pe2.route_table[1] = dest_store
424
425 # Inject seeds to both PEs
426 def inject_pe0():
427 token = MonadToken(target=0, offset=0, ctx=0, data=0, inline=False)
428 yield pe0.input_store.put(token)
429
430 def inject_pe2():
431 token = MonadToken(target=2, offset=0, ctx=0, data=2, inline=False)
432 yield pe2.input_store.put(token)
433
434 # Consumer that drains destination
435 consumed = []
436
437 def consumer():
438 while True:
439 token = yield dest_store.get()
440 consumed.append(token)
441
442 env.process(inject_pe0())
443 env.process(inject_pe2())
444 env.process(consumer())
445
446 env.run()
447
448 assert len(consumed) == 2
449 assert len(pe0.input_store.items) == 0
450 assert len(pe2.input_store.items) == 0
451
452
453class TestNetworkIntegration:
454 """Integration tests for complete network scenarios."""
455
456 def test_chain_routing_pe0_to_output(self):
457 """Tokens flow from PE0 through routing."""
458 env = simpy.Environment()
459
460 # PE0: PASS to output
461 pe0_iram = {
462 0: ALUInst(
463 op=RoutingOp.PASS,
464 dest_l=Addr(a=0, port=Port.L, pe=1),
465 dest_r=None,
466 const=None,
467 )
468 }
469
470 pe0 = ProcessingElement(env, 0, pe0_iram)
471
472 # Set up output store
473 output_store = simpy.Store(env, capacity=10)
474 pe0.route_table[1] = output_store
475
476 # Inject seed
477 def inject():
478 seed = MonadToken(target=0, offset=0, ctx=0, data=123, inline=False)
479 yield pe0.input_store.put(seed)
480
481 env.process(inject())
482 env.run()
483
484 # Token should arrive at output
485 assert len(output_store.items) > 0
486 result = output_store.items[0]
487 assert result.data == 123
488
489 def test_sm_write_then_read_via_pe(self):
490 """PE writes to SM, then reads back via another operation."""
491 env = simpy.Environment()
492
493 # Initialize SM0 with empty cells
494 sm_config = SMConfig(sm_id=0, cell_count=512)
495
496 # PE0: First write value 88 to cell 10, then read it back
497 # We'll use two separate simulations or a more complex IRAM
498 # For simplicity, do just the write in this test
499 pe0_iram = {
500 0: SMInst(
501 op=MemOp.WRITE,
502 sm_id=0,
503 const=10,
504 ret=None,
505 )
506 }
507
508 sys = build_topology(
509 env,
510 [PEConfig(0, pe0_iram)],
511 [sm_config],
512 )
513
514 seed = MonadToken(target=0, offset=0, ctx=0, data=88, inline=False)
515 sys.inject(seed)
516
517 env.run()
518
519 # Verify cell 10 is FULL with value 88
520 cell = sys.sms[0].cells[10]
521 assert cell.pres == Presence.FULL
522 assert cell.data_l == 88
523
524
525class TestRestrictedTopology:
526 """Test restricted topology via PEConfig allowed routes (AC7.6–AC7.7).
527
528 Verifies:
529 - AC7.6: build_topology applies route restrictions from PEConfig
530 - AC7.7: PEConfig with None routes preserves full-mesh (backward compatibility)
531 """
532
533 def test_ac76_restricted_topology_pe_routes(self):
534 """AC7.6: build_topology restricts PE routes based on allowed_pe_routes."""
535 env = simpy.Environment()
536
537 # Create 3 PEs but restrict PE 0 to only route to PE 1
538 pe0_config = PEConfig(pe_id=0, iram={}, allowed_pe_routes={1})
539 pe1_config = PEConfig(pe_id=1, iram={})
540 pe2_config = PEConfig(pe_id=2, iram={})
541
542 sys = build_topology(env, [pe0_config, pe1_config, pe2_config], [])
543
544 # PE 0 should only have PE 1 in its route_table
545 pe0 = sys.pes[0]
546 assert set(pe0.route_table.keys()) == {1}
547
548 def test_ac76_restricted_topology_sm_routes(self):
549 """AC7.6: build_topology restricts SM routes based on allowed_sm_routes."""
550 env = simpy.Environment()
551
552 # Create PE 0 restricted to SM 0 only (not SM 1)
553 pe0_config = PEConfig(pe_id=0, iram={}, allowed_sm_routes={0})
554 sm0_config = SMConfig(sm_id=0)
555 sm1_config = SMConfig(sm_id=1)
556
557 sys = build_topology(env, [pe0_config], [sm0_config, sm1_config])
558
559 # PE 0 should only have SM 0 in its sm_routes
560 pe0 = sys.pes[0]
561 assert set(pe0.sm_routes.keys()) == {0}
562
563 def test_ac76_restricted_topology_both_pe_and_sm(self):
564 """AC7.6: build_topology applies both PE and SM route restrictions."""
565 env = simpy.Environment()
566
567 # Create PE 0 restricted to PE 1 and SM 0 only
568 pe0_config = PEConfig(
569 pe_id=0,
570 iram={},
571 allowed_pe_routes={1},
572 allowed_sm_routes={0}
573 )
574 pe1_config = PEConfig(pe_id=1, iram={})
575 pe2_config = PEConfig(pe_id=2, iram={})
576 sm0_config = SMConfig(sm_id=0)
577 sm1_config = SMConfig(sm_id=1)
578
579 sys = build_topology(
580 env,
581 [pe0_config, pe1_config, pe2_config],
582 [sm0_config, sm1_config]
583 )
584
585 # PE 0 should be restricted in both dimensions
586 pe0 = sys.pes[0]
587 assert set(pe0.route_table.keys()) == {1}
588 assert set(pe0.sm_routes.keys()) == {0}
589
590 # PE 1 and PE 2 should have full-mesh (no restrictions)
591 pe1 = sys.pes[1]
592 assert set(pe1.route_table.keys()) == {0, 1, 2}
593 assert set(pe1.sm_routes.keys()) == {0, 1}
594
595 pe2 = sys.pes[2]
596 assert set(pe2.route_table.keys()) == {0, 1, 2}
597 assert set(pe2.sm_routes.keys()) == {0, 1}
598
599 def test_ac77_none_routes_preserves_full_mesh(self):
600 """AC7.7: PEConfig with None routes preserves full-mesh topology (backward compat)."""
601 env = simpy.Environment()
602
603 # Create 3 PEs with no route restrictions (None)
604 pe0_config = PEConfig(pe_id=0, iram={}) # allowed_pe_routes=None, allowed_sm_routes=None
605 pe1_config = PEConfig(pe_id=1, iram={})
606 pe2_config = PEConfig(pe_id=2, iram={})
607 sm0_config = SMConfig(sm_id=0)
608 sm1_config = SMConfig(sm_id=1)
609
610 sys = build_topology(
611 env,
612 [pe0_config, pe1_config, pe2_config],
613 [sm0_config, sm1_config]
614 )
615
616 # All PEs should have full-mesh routes
617 for pe_id in [0, 1, 2]:
618 pe = sys.pes[pe_id]
619 assert set(pe.route_table.keys()) == {0, 1, 2}
620 assert set(pe.sm_routes.keys()) == {0, 1}
621
622 def test_ac77_existing_tests_still_pass(self):
623 """AC7.7: Existing test scenarios still work with full-mesh (regression test)."""
624 env = simpy.Environment()
625
626 # This is the basic test from test_integration.py: CONST feeds ADD
627 pe0_iram = {
628 0: ALUInst(
629 op=RoutingOp.CONST,
630 dest_l=Addr(a=0, port=Port.L, pe=1),
631 dest_r=None,
632 const=7,
633 ),
634 1: ALUInst(
635 op=RoutingOp.CONST,
636 dest_l=Addr(a=0, port=Port.R, pe=1),
637 dest_r=None,
638 const=3,
639 ),
640 }
641
642 pe1_iram = {
643 0: ALUInst(
644 op=ArithOp.ADD,
645 dest_l=Addr(a=0, port=Port.L, pe=2),
646 dest_r=None,
647 const=None,
648 ),
649 }
650
651 sys = build_topology(
652 env,
653 [
654 PEConfig(pe_id=0, iram=pe0_iram),
655 PEConfig(pe_id=1, iram=pe1_iram),
656 PEConfig(pe_id=2, iram={}),
657 ],
658 [],
659 )
660
661 # All PEs should have full-mesh routes
662 for pe_id in [0, 1, 2]:
663 pe = sys.pes[pe_id]
664 assert set(pe.route_table.keys()) == {0, 1, 2}
665
666 # Collector to verify routing works
667 collector_store = simpy.Store(env, capacity=100)
668 sys.pes[1].route_table[2] = collector_store
669
670 # Inject tokens
671 def injector():
672 yield sys.pes[0].input_store.put(MonadToken(target=0, offset=0, ctx=0, data=0, inline=False))
673 yield sys.pes[0].input_store.put(MonadToken(target=0, offset=1, ctx=0, data=0, inline=False))
674
675 env.process(injector())
676 env.run()
677
678 # Verify result: 7 + 3 = 10 routed to collector
679 assert len(collector_store.items) > 0
680 result = collector_store.items[0]
681 assert result.data == 10
682
683
684class TestSystemInjectTokenAPI:
685 """Test System.inject() unified API."""
686
687 def test_inject_token_monad(self):
688 """System.inject() can inject MonadToken and PE executes it."""
689 env = simpy.Environment()
690
691 # PE0 with PASS instruction routing to PE1
692 pe0_iram = {
693 0: ALUInst(
694 op=RoutingOp.PASS,
695 dest_l=Addr(a=0, port=Port.L, pe=1),
696 dest_r=None,
697 const=None,
698 )
699 }
700
701 sys = build_topology(env, [PEConfig(0, pe0_iram), PEConfig(1, {})], [])
702
703 # Inject MonadToken via unified API
704 token = MonadToken(target=0, offset=0, ctx=0, data=0xABCD, inline=False)
705 sys.inject(token)
706
707 env.run()
708
709 # PE0 should have executed PASS and emitted the token
710 assert len(sys.pes[0].output_log) >= 1
711 emitted = [t for t in sys.pes[0].output_log if hasattr(t, 'data') and t.data == 0xABCD]
712 assert len(emitted) == 1
713
714 def test_inject_token_dyad(self):
715 """System.inject() can inject DyadToken."""
716 env = simpy.Environment()
717
718 # PE0 with ADD instruction
719 pe0_iram = {
720 0: ALUInst(
721 op=ArithOp.ADD,
722 dest_l=Addr(a=0, port=Port.L, pe=1),
723 dest_r=None,
724 const=None,
725 )
726 }
727
728 sys = build_topology(env, [PEConfig(0, pe0_iram), PEConfig(1, {})], [])
729
730 # Set up output stores
731 output_store = simpy.Store(env, capacity=10)
732 sys.pes[0].route_table[1] = output_store
733
734 # Create and inject first DyadToken
735 token1 = DyadToken(target=0, offset=0, ctx=0, data=10, port=Port.L, gen=0, wide=False)
736 sys.inject(token1)
737
738 # Create and inject second DyadToken to fire the instruction
739 token2 = DyadToken(target=0, offset=0, ctx=0, data=20, port=Port.R, gen=0, wide=False)
740 sys.inject(token2)
741
742 env.run()
743
744 # Verify ADD result (10 + 20 = 30)
745 assert len(output_store.items) == 1
746 assert output_store.items[0].data == 30