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 """PE blocks when destination store reaches capacity."""
251 env = simpy.Environment()
252
253 # PE0 with CONST instruction (emits to destination store)
254 pe0_iram = {
255 0: ALUInst(
256 op=RoutingOp.CONST,
257 dest_l=Addr(a=0, port=Port.L, pe=1),
258 dest_r=None,
259 const=10,
260 )
261 }
262
263 pe0 = ProcessingElement(env, 0, pe0_iram, fifo_capacity=8)
264
265 # Set up a small destination store to trigger backpressure
266 dest_store = simpy.Store(env, capacity=2)
267 pe0.route_table[1] = dest_store
268
269 # Inject 4 tokens to PE0
270 def inject_tokens():
271 for i in range(4):
272 token = MonadToken(
273 target=0,
274 offset=0,
275 ctx=0,
276 data=i,
277 inline=False,
278 )
279 yield pe0.input_store.put(token)
280
281 env.process(inject_tokens())
282
283 # Run simulation until backpressure takes effect
284 env.run(until=100)
285
286 # Destination store should have exactly 2 items (at capacity)
287 assert len(dest_store.items) == 2
288
289 # PE0 should have processed the first 2 tokens successfully
290 # and blocked on the 3rd
291 assert len(pe0.input_store.items) > 0
292
293 def test_pe_unblocks_with_some_tokens(self):
294 """After partial time, some tokens reach destination and store fills."""
295 env = simpy.Environment()
296
297 pe0_iram = {
298 0: ALUInst(
299 op=RoutingOp.CONST,
300 dest_l=Addr(a=0, port=Port.L, pe=1),
301 dest_r=None,
302 const=100,
303 )
304 }
305
306 pe0 = ProcessingElement(env, 0, pe0_iram, fifo_capacity=8)
307
308 # Small destination store
309 dest_store = simpy.Store(env, capacity=2)
310 pe0.route_table[1] = dest_store
311
312 # Inject 6 tokens
313 def inject_tokens():
314 for i in range(6):
315 token = MonadToken(
316 target=0,
317 offset=0,
318 ctx=0,
319 data=i,
320 inline=False,
321 )
322 yield pe0.input_store.put(token)
323
324 env.process(inject_tokens())
325 env.run(until=50)
326
327 # Destination store should be at capacity
328 assert len(dest_store.items) == 2 # fifo_capacity
329
330
331class TestAC44BackpressureRelease:
332 """Test AC4.4: Backpressure release when consumer drains store"""
333
334 def test_backpressure_releases_with_consumer(self):
335 """When consumer drains destination store, producer unblocks and continues."""
336 env = simpy.Environment()
337
338 pe0_iram = {
339 0: ALUInst(
340 op=RoutingOp.CONST,
341 dest_l=Addr(a=0, port=Port.L, pe=1),
342 dest_r=None,
343 const=42,
344 )
345 }
346
347 pe0 = ProcessingElement(env, 0, pe0_iram, fifo_capacity=8)
348
349 # Small destination store
350 dest_store = simpy.Store(env, capacity=2)
351 pe0.route_table[1] = dest_store
352
353 # Track consumed tokens
354 consumed = []
355
356 # Inject 4 tokens to PE0
357 def inject_tokens():
358 for i in range(4):
359 token = MonadToken(
360 target=0,
361 offset=0,
362 ctx=0,
363 data=i,
364 inline=False,
365 )
366 yield pe0.input_store.put(token)
367
368 # Consumer process that drains the destination store
369 def consumer():
370 while True:
371 token = yield dest_store.get()
372 consumed.append(token)
373
374 env.process(inject_tokens())
375 env.process(consumer())
376
377 env.run()
378
379 # All 4 injected tokens should have been consumed by the consumer
380 assert len(consumed) == 4
381 # PE0's input store should be fully drained after all tokens processed
382 assert len(pe0.input_store.items) == 0
383
384 def test_multiple_producers_with_consumer(self):
385 """Multiple producers routing to shared destination, consumer drains."""
386 env = simpy.Environment()
387
388 # PE0 and PE2 both emit to shared destination
389 pe0_iram = {
390 0: ALUInst(
391 op=RoutingOp.CONST,
392 dest_l=Addr(a=0, port=Port.L, pe=1),
393 dest_r=None,
394 const=10,
395 )
396 }
397
398 pe2_iram = {
399 0: ALUInst(
400 op=RoutingOp.CONST,
401 dest_l=Addr(a=1, port=Port.L, pe=1),
402 dest_r=None,
403 const=20,
404 )
405 }
406
407 pe0 = ProcessingElement(env, 0, pe0_iram, fifo_capacity=8)
408 pe2 = ProcessingElement(env, 2, pe2_iram, fifo_capacity=8)
409
410 # Shared destination store
411 dest_store = simpy.Store(env, capacity=2)
412 pe0.route_table[1] = dest_store
413 pe2.route_table[1] = dest_store
414
415 # Inject seeds to both PEs
416 def inject_pe0():
417 token = MonadToken(target=0, offset=0, ctx=0, data=0, inline=False)
418 yield pe0.input_store.put(token)
419
420 def inject_pe2():
421 token = MonadToken(target=2, offset=0, ctx=0, data=2, inline=False)
422 yield pe2.input_store.put(token)
423
424 # Consumer that drains destination
425 consumed = []
426
427 def consumer():
428 while True:
429 token = yield dest_store.get()
430 consumed.append(token)
431
432 env.process(inject_pe0())
433 env.process(inject_pe2())
434 env.process(consumer())
435
436 env.run()
437
438 assert len(consumed) == 2
439 assert len(pe0.input_store.items) == 0
440 assert len(pe2.input_store.items) == 0
441
442
443class TestNetworkIntegration:
444 """Integration tests for complete network scenarios."""
445
446 def test_chain_routing_pe0_to_output(self):
447 """Tokens flow from PE0 through routing."""
448 env = simpy.Environment()
449
450 # PE0: PASS to output
451 pe0_iram = {
452 0: ALUInst(
453 op=RoutingOp.PASS,
454 dest_l=Addr(a=0, port=Port.L, pe=1),
455 dest_r=None,
456 const=None,
457 )
458 }
459
460 pe0 = ProcessingElement(env, 0, pe0_iram)
461
462 # Set up output store
463 output_store = simpy.Store(env, capacity=10)
464 pe0.route_table[1] = output_store
465
466 # Inject seed
467 def inject():
468 seed = MonadToken(target=0, offset=0, ctx=0, data=123, inline=False)
469 yield pe0.input_store.put(seed)
470
471 env.process(inject())
472 env.run()
473
474 # Token should arrive at output
475 assert len(output_store.items) > 0
476 result = output_store.items[0]
477 assert result.data == 123
478
479 def test_sm_write_then_read_via_pe(self):
480 """PE writes to SM, then reads back via another operation."""
481 env = simpy.Environment()
482
483 # Initialize SM0 with empty cells
484 sm_config = SMConfig(sm_id=0, cell_count=512)
485
486 # PE0: First write value 88 to cell 10, then read it back
487 # We'll use two separate simulations or a more complex IRAM
488 # For simplicity, do just the write in this test
489 pe0_iram = {
490 0: SMInst(
491 op=MemOp.WRITE,
492 sm_id=0,
493 const=10,
494 ret=None,
495 )
496 }
497
498 sys = build_topology(
499 env,
500 [PEConfig(0, pe0_iram)],
501 [sm_config],
502 )
503
504 seed = MonadToken(target=0, offset=0, ctx=0, data=88, inline=False)
505 sys.inject(seed)
506
507 env.run()
508
509 # Verify cell 10 is FULL with value 88
510 cell = sys.sms[0].cells[10]
511 assert cell.pres == Presence.FULL
512 assert cell.data_l == 88
513
514
515class TestRestrictedTopology:
516 """Test restricted topology via PEConfig allowed routes (AC7.6–AC7.7).
517
518 Verifies:
519 - AC7.6: build_topology applies route restrictions from PEConfig
520 - AC7.7: PEConfig with None routes preserves full-mesh (backward compatibility)
521 """
522
523 def test_ac76_restricted_topology_pe_routes(self):
524 """AC7.6: build_topology restricts PE routes based on allowed_pe_routes."""
525 env = simpy.Environment()
526
527 # Create 3 PEs but restrict PE 0 to only route to PE 1
528 pe0_config = PEConfig(pe_id=0, iram={}, allowed_pe_routes={1})
529 pe1_config = PEConfig(pe_id=1, iram={})
530 pe2_config = PEConfig(pe_id=2, iram={})
531
532 sys = build_topology(env, [pe0_config, pe1_config, pe2_config], [])
533
534 # PE 0 should only have PE 1 in its route_table
535 pe0 = sys.pes[0]
536 assert set(pe0.route_table.keys()) == {1}
537
538 def test_ac76_restricted_topology_sm_routes(self):
539 """AC7.6: build_topology restricts SM routes based on allowed_sm_routes."""
540 env = simpy.Environment()
541
542 # Create PE 0 restricted to SM 0 only (not SM 1)
543 pe0_config = PEConfig(pe_id=0, iram={}, allowed_sm_routes={0})
544 sm0_config = SMConfig(sm_id=0)
545 sm1_config = SMConfig(sm_id=1)
546
547 sys = build_topology(env, [pe0_config], [sm0_config, sm1_config])
548
549 # PE 0 should only have SM 0 in its sm_routes
550 pe0 = sys.pes[0]
551 assert set(pe0.sm_routes.keys()) == {0}
552
553 def test_ac76_restricted_topology_both_pe_and_sm(self):
554 """AC7.6: build_topology applies both PE and SM route restrictions."""
555 env = simpy.Environment()
556
557 # Create PE 0 restricted to PE 1 and SM 0 only
558 pe0_config = PEConfig(
559 pe_id=0,
560 iram={},
561 allowed_pe_routes={1},
562 allowed_sm_routes={0}
563 )
564 pe1_config = PEConfig(pe_id=1, iram={})
565 pe2_config = PEConfig(pe_id=2, iram={})
566 sm0_config = SMConfig(sm_id=0)
567 sm1_config = SMConfig(sm_id=1)
568
569 sys = build_topology(
570 env,
571 [pe0_config, pe1_config, pe2_config],
572 [sm0_config, sm1_config]
573 )
574
575 # PE 0 should be restricted in both dimensions
576 pe0 = sys.pes[0]
577 assert set(pe0.route_table.keys()) == {1}
578 assert set(pe0.sm_routes.keys()) == {0}
579
580 # PE 1 and PE 2 should have full-mesh (no restrictions)
581 pe1 = sys.pes[1]
582 assert set(pe1.route_table.keys()) == {0, 1, 2}
583 assert set(pe1.sm_routes.keys()) == {0, 1}
584
585 pe2 = sys.pes[2]
586 assert set(pe2.route_table.keys()) == {0, 1, 2}
587 assert set(pe2.sm_routes.keys()) == {0, 1}
588
589 def test_ac77_none_routes_preserves_full_mesh(self):
590 """AC7.7: PEConfig with None routes preserves full-mesh topology (backward compat)."""
591 env = simpy.Environment()
592
593 # Create 3 PEs with no route restrictions (None)
594 pe0_config = PEConfig(pe_id=0, iram={}) # allowed_pe_routes=None, allowed_sm_routes=None
595 pe1_config = PEConfig(pe_id=1, iram={})
596 pe2_config = PEConfig(pe_id=2, iram={})
597 sm0_config = SMConfig(sm_id=0)
598 sm1_config = SMConfig(sm_id=1)
599
600 sys = build_topology(
601 env,
602 [pe0_config, pe1_config, pe2_config],
603 [sm0_config, sm1_config]
604 )
605
606 # All PEs should have full-mesh routes
607 for pe_id in [0, 1, 2]:
608 pe = sys.pes[pe_id]
609 assert set(pe.route_table.keys()) == {0, 1, 2}
610 assert set(pe.sm_routes.keys()) == {0, 1}
611
612 def test_ac77_existing_tests_still_pass(self):
613 """AC7.7: Existing test scenarios still work with full-mesh (regression test)."""
614 env = simpy.Environment()
615
616 # This is the basic test from test_integration.py: CONST feeds ADD
617 pe0_iram = {
618 0: ALUInst(
619 op=RoutingOp.CONST,
620 dest_l=Addr(a=0, port=Port.L, pe=1),
621 dest_r=None,
622 const=7,
623 ),
624 1: ALUInst(
625 op=RoutingOp.CONST,
626 dest_l=Addr(a=0, port=Port.R, pe=1),
627 dest_r=None,
628 const=3,
629 ),
630 }
631
632 pe1_iram = {
633 0: ALUInst(
634 op=ArithOp.ADD,
635 dest_l=Addr(a=0, port=Port.L, pe=2),
636 dest_r=None,
637 const=None,
638 ),
639 }
640
641 sys = build_topology(
642 env,
643 [
644 PEConfig(pe_id=0, iram=pe0_iram),
645 PEConfig(pe_id=1, iram=pe1_iram),
646 PEConfig(pe_id=2, iram={}),
647 ],
648 [],
649 )
650
651 # All PEs should have full-mesh routes
652 for pe_id in [0, 1, 2]:
653 pe = sys.pes[pe_id]
654 assert set(pe.route_table.keys()) == {0, 1, 2}
655
656 # Collector to verify routing works
657 collector_store = simpy.Store(env, capacity=100)
658 sys.pes[1].route_table[2] = collector_store
659
660 # Inject tokens
661 def injector():
662 yield sys.pes[0].input_store.put(MonadToken(target=0, offset=0, ctx=0, data=0, inline=False))
663 yield sys.pes[0].input_store.put(MonadToken(target=0, offset=1, ctx=0, data=0, inline=False))
664
665 env.process(injector())
666 env.run()
667
668 # Verify result: 7 + 3 = 10 routed to collector
669 assert len(collector_store.items) > 0
670 result = collector_store.items[0]
671 assert result.data == 10
672
673
674class TestSystemInjectTokenAPI:
675 """Test System.inject() unified API."""
676
677 def test_inject_token_monad(self):
678 """System.inject() can inject MonadToken and PE executes it."""
679 env = simpy.Environment()
680
681 # PE0 with PASS instruction routing to PE1
682 pe0_iram = {
683 0: ALUInst(
684 op=RoutingOp.PASS,
685 dest_l=Addr(a=0, port=Port.L, pe=1),
686 dest_r=None,
687 const=None,
688 )
689 }
690
691 sys = build_topology(env, [PEConfig(0, pe0_iram), PEConfig(1, {})], [])
692
693 # Inject MonadToken via unified API
694 token = MonadToken(target=0, offset=0, ctx=0, data=0xABCD, inline=False)
695 sys.inject(token)
696
697 env.run()
698
699 # PE0 should have executed PASS and emitted the token
700 assert len(sys.pes[0].output_log) >= 1
701 emitted = [t for t in sys.pes[0].output_log if hasattr(t, 'data') and t.data == 0xABCD]
702 assert len(emitted) == 1
703
704 def test_inject_token_dyad(self):
705 """System.inject() can inject DyadToken."""
706 env = simpy.Environment()
707
708 # PE0 with ADD instruction
709 pe0_iram = {
710 0: ALUInst(
711 op=ArithOp.ADD,
712 dest_l=Addr(a=0, port=Port.L, pe=1),
713 dest_r=None,
714 const=None,
715 )
716 }
717
718 sys = build_topology(env, [PEConfig(0, pe0_iram), PEConfig(1, {})], [])
719
720 # Set up output stores
721 output_store = simpy.Store(env, capacity=10)
722 sys.pes[0].route_table[1] = output_store
723
724 # Create and inject first DyadToken
725 token1 = DyadToken(target=0, offset=0, ctx=0, data=10, port=Port.L, gen=0, wide=False)
726 sys.inject(token1)
727
728 # Create and inject second DyadToken to fire the instruction
729 token2 = DyadToken(target=0, offset=0, ctx=0, data=20, port=Port.R, gen=0, wide=False)
730 sys.inject(token2)
731
732 env.run()
733
734 # Verify ADD result (10 + 20 = 30)
735 assert len(output_store.items) == 1
736 assert output_store.items[0].data == 30