This would be interesting to explore further. Do you have any more thoughts on which specific heuristic might perform better than using gasUsed?
Adding the additional gasUsed values to the BAL isn’t ideal given the additional bandwidth cost and if we can get a better estimate of the run time of each transaction by using the existing information in the BAL that would be ideal. It may not actually be that complex if we are simply looking at numbers of BAL entries for each transaction or similar. Ideally client teams spend some time experimenting with different scheduling approaches and measure the results before deciding.
By the way there is a metric you can use to measure how parallel a set of transaction executions are.
Let T = total run time of all transactions combined (the time it would take for all transactions to execute on a single core)
Let L = run time of the longest running transaction
Let A = actual overall execution time when the transactions are executed on multiple cores (this is basically the makespan as described in this post but measured in execution time rather than gas).
We assume that A is bounded by L and T (L <= A <= T).
Let M = (T - A) / (T - L)
The metric is a value between 0 and 1 which gives an indication of how well a set transactions has been scheduled for execution.
M = 1 indicates the best case parallelization. This occurs when A = L.
M = 0 indicates the worst case parallelization. This occurs when A = T.
When A approaches L (the best case), M approaches 1.
This metric can be used to compare how well various scheduling mechanisms work in practice.
In order to compute the metric for each block an EL would need to first measure the run time of sequential execution while also collecting the run time of the longest transaction and then execute the block a second time to measure the actual run time when executing on multiple cores.
It’s a fairly simple way to compare approaches using empirical data when executing historical blocks.