Optimize transactron eager_deterministic_cc_scheduler

[xThaid]

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.

[tilk]

The maximal clique problem is NP-complete, and so the algorithms for listing them - like the most frequently cited Bron-Kerbosch algorithm - are worst-case exponential. Some algorithms have better bounds for real-life graphs, like (hopefully) the conflict graphs in Transactron. For example:

• Vertex-ordering Bron-Kerbosch has bound $O(dn3^{d/3})$ where $d$ is graph degeneracy and $n$ the number of vertices.
• Algorithm of Chiba and Nishizeki has bound $O(ma)$ per clique, where $m$ is the number of edges and $a$ is graph arboricity.

The python library NetworkX has an implementation of some variant of Bron-Kerbosch. Maybe it can be used to perform some experiments.

Side note: using clique info it's probably possible to implement some sort of fairness in transaction scheduling. I'm not sure how useful this would be in practice.

[tilk]

I have run the maximal clique algorithm on current Coreblocks in the full configuration. It found 10 cliques of size 2, 3 cliques of size 4, 1 clique of size 6 and 3 cliques of size 7. Some of the cliques are not disjoint. In particular, amongst the largest 3 cliques of size 7, one pair is disjoint, one pair has a common vertex, and another pair has two common vertices; so they are almost disjoint.