The circuit generated by eager_deterministic_cc_scheduler can be improved a bit. Consider a set of transactions in which every transaction conflicts with every other. This in fact can happen quite often - when all transactions call the same method (ManyToOneConnectTrans). The scheduler would create for each transaction:
conflicts = [ccl[j].grant for j in range(k) if ccl[j] in gr[transaction]]
noconflict = ~Cat(conflicts).any()
m.d.comb += transaction.grant.eq(transaction.request & transaction.runnable & noconflict)
Thus, grant signal of the last transaction would form a critical path of the linear size.
In the case of a clique of conflicts, we could simply choose the first bit set (a la a priority encoder) - logarithmic length of the critical path.
In general, for any given graph of conflicts, we could find a clique cover and then for every clique make a priority encoder.
Having said that, I am not sure (and I don't have data) if this is worth doing at all.
The circuit generated by
eager_deterministic_cc_schedulercan be improved a bit. Consider a set of transactions in which every transaction conflicts with every other. This in fact can happen quite often - when all transactions call the same method (ManyToOneConnectTrans). The scheduler would create for each transaction:Thus,
grantsignal of the last transaction would form a critical path of the linear size.In the case of a clique of conflicts, we could simply choose the first bit set (a la a priority encoder) - logarithmic length of the critical path.
In general, for any given graph of conflicts, we could find a clique cover and then for every clique make a priority encoder.
Having said that, I am not sure (and I don't have data) if this is worth doing at all.