Inquiry into Bluespec Scheduler Granularity Capabilities: Rule vs. Case-Arm Level

#850

I’ve been digging into the scheduling behavior of my TagEngine implementation and could use some insight from the community on how Bluespec resolves conflicts between methods and rules, particularly with respect to granularity.

In my TagEngine (FIFO-based tag management), I have:

?

?* A requestTag method that issues tags, initially from a countdown (initialTagDistributor) and later from a tagFIFO:

?

```
requestTag :: ActionValue UIntLog2N(numTags)
requestTag =
? ? do
? ? ? ? case initialTagDistributor of
? ? ? ? ? ? Just 0 -> do
? ? ? ? ? ? ? ? initialTagDistributor := Nothing
? ? ? ? ? ? ? ? (select tagUsageTracker 0) := True
? ? ? ? ? ? ? ? return 0
? ? ? ? ? ? Just tag -> do
? ? ? ? ? ? ? ? initialTagDistributor := Just |> tag - 1
? ? ? ? ? ? ? ? (select tagUsageTracker tag) := True
? ? ? ? ? ? ? ? return tag
? ? ? ? ? ? Nothing -> do
? ? ? ? ? ? ? ? let tag = tagFIFO.first
? ? ? ? ? ? ? ? tagFIFO.deq
? ? ? ? ? ? ? ? return tag
```

?

?* A retire_tags rule that recycles tags into the tagFIFO:

?

```
"retire_tags": when True ==>
? ? do
? ? ? ? $display "firing retire_tags" (fshow retireTag)
? ? ? ? tagFIFO.enq retireTag
? ? ? ? (select tagUsageTracker retireTag) := False
```

Triggered via a `retireTag` method writing to a wire (`retireTag :: Wire UIntLog2N(numTags)`).

?

My question is about scheduler granularity:

In the `Nothing` case of `requestTag`, there’s no write to `tagUsageTracker`, unlike the `Just` cases. `retire_tags`, however, always writes to `tagUsageTracker`. I expected the scheduler to conservatively block `requestTag` and `retire_tags` from firing in the same cycle due to the potential conflict on `tagUsageTracker`, even when `initialTagDistributor` is `Nothing`.

?

However, my Bluesim output suggests they do fire together:

?

```
count : 7
retiring tag : 4?
got tag : 2
firing retire_tags4
count : 8
retiring tag : 4?
got tag : 4
```

?

This comes from a tester using an ActionSeq:

?

```
|> do?
? ? retireTagAction 4
? ? requestTagAction
```

?

where `retireTagAction` calls `retireTag 4` and `requestTagAction` calls `requestTag`.

The dumped schedule for retire_tags shows:

?

```
Rule: tagEngine_retire_tags
Predicate: tagEngine_retireTag.whas && tagEngine_tagFIFO.i_notFull
Blocking rules: (none)
```

but doesn’t mention `requestTag` (a method, not a rule). My understanding was that the scheduler operates at the rule/method level, not case-arm level, so it wouldn’t distinguish the Nothing case’s lack of tagUsageTracker writes. Yet, the simulation suggests otherwise.

?

Here are my final questions:

?* At what granularity does the scheduler resolve conflicts? Does it consider runtime paths (e.g., Nothing vs. Just) or just the union of all possible resource accesses?
?* Why can requestTag (in Nothing) and retire_tags fire in the same cycle here? Is it because they’re sequenced within one ActionSeq rule, and tagFIFO (a FIFOF) allows enq/deq together?

#851

And here is the link to the relevant code:

#852

I might have an idea about how the compiler does this... Under the hood, can Bluespec rewrite rules into multiple rules? That is, can a rule be split into two rules for the purpose of reasoning about scheduling?

#853

If you give the -show-rule-rel flags, or query the schedule information from within the BDW GUI or using Blutecl commands, the tools can show you what method calls contribute to the inferred rule relationship.? For example:

Scheduling info for rules "RL_r1" and "RL_r2":
predicates are not disjoint
? ? <> conflict: calls to rg.write vs. rg.write
? ? no < conflict
? ? no resource conflict
? ? no cycle conflict
? ? no attribute conflict

Scheduling info for rules "RL_r2" and "RL_r1":
predicates are not disjoint
? ? <> conflict: calls to rg.write vs. rg.write
? ? no < conflict
? ? no resource conflict
? ? no cycle conflict
? ? no attribute conflict

This also shows that there are a couple kinds of conflict.? One kind is that two rules just can't execute in the same clock cycle.? But register writes are not all-out conflicts like that.? If you have one rule that writes True to a register and another that writes False, BSC can make logic that implements the firing of both rules, one after another, by only writing the final value into the register (say, False).? I believe that's what's happening in your code.? This treatment of registers can be unexpected, and I know that some people prefer to use their own register definitions that force writes to conflict.

In the above schedule info, that I generated for a small example, BSC is reporting that the rules do touch common state, and therefore their execution order will be visible, but that there's nothing to prevent them from executing in sequence in the same clock cycle.? The "<" conflict would mean that one rule has to execute before the other -- for example, if one rule was also reading the value, that would have to come first.? If both directions have an ordering conflict ("<"), then there's an all-out conflict, because the rules can't be executed in either order.

To answer your scheduling questions: ?BSC will not generate conditional conflicts.? However, BSC will take the conditions of the actions into account.? So if one rule calls a method when "x > 10" and the other rule calls when "x < 10", BSC will notice that the methods are never called at the same time and will exempt them from consideration.? But if one rule calls when "x > 10" and one rule always calls, BSC won't generate a dynamic scheduler that allows the rules to both fire when "x <= 10", it will just make them conflict.? There is the "-aggressive-conditions" flag (which we should make on by default), which lifts method conditions to the rule's condition, but that's only about a rule's own firing condition, and not about scheduling between rules.

There are some features for splitting rules, if you want.? I don't tend to use it, but I could image there could be situations.? In BSV, you can put an attribute like "split" on an if-statement or a case-statement or possibly a rule or method or module.? That directs BSC to split a rule in half for every conditional inside it.? For BH, I don't think the parser accepts a pragma, but there's a function "splitIf" that can be used in place of an if-expression.? BSC also supports a global "-split-if" flag, although that would be an extremely large hammer, so it's probably not useful.? But if you did go that route, there are "nosplit" attributes and "noSplitIf" functions that can be used in the code, to disable splitting in specific locations.

Anyway, the benefit of splitting is that the two rules can be placed at different points in the schedule.? For example, if rule A conflicts with rule B because it can't execute before or after, rule splitting might allow A-True to schedule before and A-False to schedule after.? If that's the case, you can always just write the two rules explicitly, instead of using a split-if.? But the option's there.

J

#854

But register writes are not all-out conflicts like that.? If you have one rule that writes True to a register and another that writes False, BSC can make logic that implements the firing of both rules, one after another, by only writing the final value into the register (say, False).? I believe that's what's happening in your code.

?

Ok... This is quite fascinating and makes sense... I suppose if we evaluate a model action by action, two actions that write to the same resource one after the other can be reduced to the last write that occurred. Given the current code, the retire_tag rule and teh request_tag method will never have write conflicts in practice... But suppose for a moment they did, how does the bluespec compiler decide which one gets the final write?

#858

There may be other state that the rules are using, which enforce an order.? But if the rules can equally execute in either order, then BSC will arbitrarily pick an order, and will report a warning about that choice:

Warning: "Test2.bsv", line 2, column 8: (G0036)
? Rule "r1" will appear to fire before "r2" when both fire in the same clock
? cycle, affecting:
? ? calls to rg.write vs. rg.write

You can enforce a particular order by specifying an "execution_order" attribute.? Alternatively, you can instantiate 'mkCReg' instead of 'mkReg', and assign one rule port 0 and the other rule port 1, and enforce an order that way.

If you have a rule whose writes are shadowed by other rules, BSC will also warn about that:

Warning: "Test2.bsv", line 2, column 8: (G0117)
? Rule `r2' shadows the effects of `r1' when they execute in the same clock
? cycle. Affected method calls:
? ? rg.write

J

On Sat, Apr 5, 2025 at 3:18?AM Yehowshua Immanuel via <programmed4jesus=[email protected]> wrote:

But register writes are not all-out conflicts like that.? If you have one rule that writes True to a register and another that writes False, BSC can make logic that implements the firing of both rules, one after another, by only writing the final value into the register (say, False).? I believe that's what's happening in your code.

?

Ok... This is quite fascinating and makes sense... I suppose if we evaluate a model action by action, two actions that write to the same resource one after the other can be reduced to the last write that occurred. Given the current code, the retire_tag rule and teh request_tag method will never have write conflicts in practice... But suppose for a moment they did, how does the bluespec compiler decide which one gets the final write?

开云体育

Inquiry into Bluespec Scheduler Granularity Capabilities: Rule vs. Case-Arm Level