coreblocks icon indicating copy to clipboard operation
coreblocks copied to clipboard

Optimize transactron `eager_deterministic_cc_scheduler`

Open xThaid opened this issue 9 months ago • 0 comments

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.

xThaid avatar May 22 '24 12:05 xThaid