[P0] Unaccounted Routing Delay Causes Extra Stall Before ADD Operation in BICG

[guosran]

Description

There is an II mismatch between the compiler's schedule and the RTL execution in the BiCG kernel. The compiler schedules under the assumption of zero-delay for cross-tile data movement, but the RTL implementation introduces a 1-cycle routing pipeline register delay on mesh links.

When this routing delay falls on a fully scheduled operation slot with no NAH slots to absorb it, it causes data misalignment (one operand arrives late). This results in an unexpected 1-cycle stall right before the operation can execute, directly increasing the overall II.

Log Trace

We can observe this behavior on an add (+) operation at tile 4 (t4), which ends up occupying two cycles instead of one:

  cyc= 280 | t0:a9t29(NAH)        | t1:a9t29(grant_pred)✓ | t2:a0t30(NAH)        | t4:a9t29(+)         ◇ | t5:a8t28(!)         ✓ | t6:a0t30(ret_void)  ◇ | t8:a8t28(*)         ✓ | t9:a8t28(*)         ☒ | t12:a0t10(st)        ◇ | t13:a8t8(NAH)       
  cyc= 281 | t0:a0t30(grant_once')✓ | t1:a9t29(grant_pred)☒ | t2:a1t31(NAH)        | t4:a9t29(+)         ✓ | t5:a9t29(grant_pred)✓ | t6:a0t30(ret_void)  ◇ | t8:a9t29(strdcst)   ◇ | t9:a8t28(*)         ☒ | t12:a0t10(st)        ◇ | t13:a9t9(+)         ✓

As shown in PE (0,1). The `ADD` takes 2 cycles, the first one is actually the stall.

<img width="4201" height="1253" alt="Image" src="https://github.com/user-attachments/assets/fd147019-cb80-433a-9800-6f055eeac061" />

[guosran]

As shown in PE (0,1). The `ADD` takes 2 cycles, the first one is actually the stall.

[tancheng]

When this routing delay falls on a fully scheduled operation slot with no NAH slots to absorb it, it causes data misalignment (one operand arrives late).

Do you mean the operand needs to be written into register cluster first before being consumed by computation? I am not able to see the data dependency so hard to reason about your example.

And do you have some potential solution?

[guosran]

I am debugging the BiCG kernel. The simulated II is 12, which is abnormally larger than the compiled ii which is 10. The reason seems to be the excessive stall introduced before the add operation in tile (0,1). I will provide more detailed information after class :)

…

________________________________ From: Cheng Tan ***@***.***> Sent: Monday, April 13, 2026 1:21:45 AM To: tancheng/VectorCGRA ***@***.***> Cc: GUO Shiran ***@***.***>; Author ***@***.***> Subject: Re: [tancheng/VectorCGRA] [P0] Unaccounted Routing Delay Causes Extra Stall Before ADD Operation in BICG (Issue #283) [https://avatars.githubusercontent.com/u/6756658?s=20&v=4]tancheng left a comment (tancheng/VectorCGRA#283)<#283 (comment)> When this routing delay falls on a fully scheduled operation slot with no NAH slots to absorb it, it causes data misalignment (one operand arrives late). Do you mean the operand needs to be written into register cluster first before being consumed by computation? I am not able to see the data dependency so hard to reason about your example. And do you have some potential solution? — Reply to this email directly, view it on GitHub<#283 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/BHMYV7SQSNQFRJKP56WK4C34VSBPTAVCNFSM6AAAAACXWUDY7WVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHM2DEMZUGI3DGMBVGA>. You are receiving this because you authored the thread.Message ID: ***@***.***>

[guosran]

The operand does not need to be written to a Register Cluster first. It is directly consumed by the computation functional unit. The delay simply comes from a hardware-level 1-cycle pipeline register on the mesh routing links between tiles.

The compiler schedules the instructions assuming 0-cycle latency for cross-tile operand routing. In the actual RTL, the inter-tile link has a pipeline register. The data arrives at the neighboring tile at t+1.

Other kernels also suffer from this RTL routing delay, but their schedules have enough NAHs on their dependency paths to passively absorb the latency without increasing the total II.

So a reasonable solution maight be on the compiler side?

[tancheng]

The compiler schedules the instructions assuming 0-cycle latency for cross-tile operand routing.

Compiler indeed respects 1-cycle latency across neighboring tiles. Tile A produces the data/result and sends into Tile B's inport channel (assuming Tile A -> Tile B), then next cycle Tile B can consume the data from the inport channel's top (channel works as a pipe). In other words, in RTL, data_move/ctrl_move happens in the same cycle as the producer (FU computation).

So what is your data dependency? The Tile A generates data but sends to A's register? This might be a buggy case. Anyways, can you elaborate on the concrete example?

[guosran]

So what is your data dependency? The Tile A generates data but sends to A's register? This might be a buggy case. Anyways, can you elaborate on the concrete example?

Tile A sends the data directly out its mesh routing port, not register.

ASM:

Tile(1,1) At index_per_ii = 8, it executes:

{
  NOT, [$0] -> [WEST, RED], [SOUTH, RED] (t=8, inv_iters=0)
} (idx_per_ii=8)

The output is driven directly to its inter-tile mesh port.

Tile(1,0) At index_per_ii = 9, it has two operations in the same control step:

{
  GRANT_PREDICATE, [$0], [$8] -> [WEST, RED] (t=9, inv_iters=0)
  DATA_MOV, [NORTH, RED] -> [$0] (t=9, inv_iters=0)
} (idx_per_ii=9)

The DATA_MOV attempts to consume the mesh data arriving via [NORTH], while GRANT_PREDICATE consumes local registers.

In Execution:

• At T, both are executing index = 8 instructions. Tile(1,1) evaluates the NOT operation and places the valid result onto the mesh network's pipeline register.
• At the start of Clock Cycle T+1, both tiles advance to index = 9.
  Tile(1,0) attempts to execute both GRANT_PREDICATE and DATA_MOV concurrently:
  GRANT_PREDICATE sees val=1.
  DATA_MOV expects data from the routing crossbar [NORTH].

However, the physical mesh data from Tile(1,1) is sent during Cycle T+1, and arrives at the end of T+1.
So the operands are executed at T+2.

[tancheng]

the physical mesh data from Tile(1,1) is sent during Cycle T+1

You mean NOT is the producer towards Tile(1, 0)'s north, right? which would be consumed by Tile(1, 0)'s DATA_MOV, right? From HW/RTL perspective, the data should be sent during T, and be valid since beginning of T+1 on Tile(1, 0)'s north, instead of T+2.

[guosran]

You mean NOT is the producer towards Tile(1, 0)'s north, right? which would be consumed by Tile(1, 0)'s DATA_MOV, right? From HW/RTL perspective, the data should be sent during T, and be valid since beginning of T+1 on Tile(1, 0)'s north, instead of T+2.

Sorry for the confusion. It seems to be a write-read hazard inside RegisterClusterRTL.

Root Cause

In RegisterClusterRTL.py line 93, which is edited by #282, the recv_data_from_routing_crossbar[i].rdy signal couples register write readiness with the FU read path:

s.recv_data_from_routing_crossbar[i].rdy @= \
    (s.inport_opt.operation == OPT_NAH) | \
    (s.inport_opt.fu_in[i] == 0) | \
    s.send_data_to_fu[i].rdy       # problem: depends on FU read path

The dependency chain is:

recv_data_from_routing_crossbar[i].rdy
  <- send_data_to_fu[i].rdy
    <- element.recv_in[i].rdy
      <- FU accepting input

When a ctrl step requires the same register bank i to be simultaneously:

1. Read by the FU (register -> send_data_to_fu[i] -> FU input)
2. Written by the routing crossbar (neighbor tile -> recv_data_from_routing_crossbar[i] -> register)

the following sequence occurs:

Cycle	What Happens
N	FU executes, asserts element.recv_opt.rdy=1 → element_done latches to 1
N+1	element_done=1 → FU no longer accepts new input → send_data_to_fu[i].rdy drops to 0
N+1	This forces recv_data_from_routing_crossbar[i].rdy=0, blocking the routing crossbar write
N+1	Routing crossbar can't complete all sends → routing_crossbar.recv_opt.rdy=0 → routing_crossbar_done stays 0
N+1	ctrl_mem.send_ctrl.rdy requires (routing_crossbar_done | routing_crossbar.recv_opt.rdy) = 0 → ctrl stalls for 1 extra cycle
N+2	element_done resets to 0, FU re-accepts input, send_data_to_fu.rdy=1 → write completes → ctrl advances

Each such conflict wastes exactly 1 cycle per occurrence.

---

2. Trace Evidence

From the BiCG 4×4 trace (compiled II=10, 10 ctrl steps per iteration):

Per-Tile Steady-State II

Tile	Measured II	Extra Stalls
T(0,0)	12	+2
T(0,1)	12	+2
T(0,2)	12	+2
T(1,0)	12	+2
T(1,1)	12	+2
T(1,2)	12	+2
T(2,0)	12	+2
T(2,1)	12	+2
T(3,0)	10	0
T(3,1)	10	0

T(3,0) and T(3,1) achieve II=10 exactly as compiled — they have no read+write conflicts on the same register bank within the same step.

Per-Tile Register-Write-Blocked Stalls

These are cycles where element_done=1 but routing_crossbar_done=0 (FU finished, but routing crossbar is blocked by register cluster refusing the write):

Tile	Stall at Steps	Stalls per Iteration
T(0,0)	step 3	1
T(0,1)	step 5, step 9	2
T(1,0)	step 1	1
T(1,1)	step 7	1
T(2,0)	step 3	1
T(2,1)	step 6	1
T(0,2)	—	0 (cascading)
T(1,2)	—	0 (cascading)
T(3,0)	—	0
T(3,1)	—	0

The critical-path tile T(0,1) has 2 root-cause stalls per iteration. These stalls cascade through inter-tile backpressure, causing all tiles (except T(3,0)/T(3,1)) to observe II=12.

Concrete Example: T(0,1) at Step 9

Cycle 341: addr=9, element_done=0, routing_xbar_done=0           — normal execution
Cycle 342: addr=9 (STALLED!), element_done=1, fu_xbar_done=1,
           BUT routing_xbar_done=0
           routing_xbar send[4].rdy=0, send[5].rdy=0
           → register cluster refuses routing_crossbar write
             because send_data_to_fu.rdy=0 (FU already consumed input)
Cycle 343: addr=0                                                 — wasted 1 cycle

---

3. Fix Attempted & Deadlock

I attempted a fix by adding | element_done to bypass the blocked write after FU completion:

# In RegisterClusterRTL.py
s.recv_data_from_routing_crossbar[i].rdy @= \
    (s.inport_opt.operation == OPT_NAH) | \
    (s.inport_opt.fu_in[i] == 0) | \
    s.send_data_to_fu[i].rdy | \
    s.inport_element_done            # ← attempted fix

With inport_element_done connected from TileRTL.element_done.

Result: Deadlock. All tiles get stuck at their first ctrl step and never advance. The issue is that element_done feeds back through the val/rdy handshake chain, creating a combinational dependency loop that prevents the tile from ever starting execution.

---

4. The Fundamental Issue

The register cluster assumes a single-ported model where each register bank i is either read OR written in a given step. But the compiler can schedule both a read (fu_in[i] != 0) and a write (routing_xbar_outport → local port i) on the same register bank in the same step. The rdy coupling means the write path is blocked while the FU read path is active, and the write can't complete until the FU stops reading, which only happens when the step advances (next cycle).

[guosran]

The above result is from shiran-fufill-compiled-kernels. The simulation result in deadlock when trying to rebase on zeonica-spmv-validation.

[tancheng]

I think the condition now is updated to:

        s.recv_data_from_routing_crossbar[i].rdy @= ((s.inport_opt.write_reg_from[i] == PORT_ROUTING_CROSSBAR) \
                & (s.inport_opt.operation == OPT_NAH)) | s.send_data_to_fu[i].rdy

And our register allows read/write happen simultaneously.

It is hard to explain by texting. Can we schedule a 30min meeting to talk about this? @guosran @ShangkunLi @yyan7223?

[ShangkunLi]

I think the condition now is updated to:

        s.recv_data_from_routing_crossbar[i].rdy @= ((s.inport_opt.write_reg_from[i] == PORT_ROUTING_CROSSBAR) \
                & (s.inport_opt.operation == OPT_NAH)) | s.send_data_to_fu[i].rdy

And our register allows read/write happen simultaneously.

It is hard to explain by texting. Can we schedule a 30min meeting to talk about this? @guosran @ShangkunLi @yyan7223?

I am available all day today and tomorrow~

[tancheng]

Can you help schedule one? plz check with @yyan7223 and @guosran.

[ShangkunLi]

Can you help schedule one? plz check with @yyan7223 and @guosran.

Sent you the meeting invitation through email~

[guosran]

@yyan7223Hi Yufei, I have pushed the conv test branch zeonica-conv-validation to remote. The vcd file isunder the root: VectorCGRA.cgra.test.CgraRTL_conv4x4_test_from_yaml__test_homogeneous_4x4_conv_combinational_mem_access.vcd. Attached is the time series diagram:

[yyan7223]

Hi @guosran, Can I also have a translated config like #281 (comment) ?

And I don't need to care anything to talk above, right? I remember in the meeting you said it was deprecated.