Ideas for more efficient scheduling of very large suites

[cylc]

First, see Issue #107 (more efficient scheduling of large ensembles).

Currently the scheduling algorithm works like this: every task in the suite is represented by its own task proxy. Every time a task proxy changes state (usually after receiving a progress message from the real task) each task proxy communicates its completed outputs to a broker, then each task proxy asks the broker to satisfy its prerequisites - by literal string matching of unsatisfied prerequisites to completed outputs. The broker simply dumps its outputs and starts again each time through the loop. To prevent the task pool from growing indefinitely spent tasks are eliminated from the pool as soon as cylc decides they are not needed to satisfy any other task's prerequisites anymore.

[hjoliver]

1/ is literal string matching (prerequisites <-> outputs) very inefficient? Could replace with numerical hashes. This is probably not important, but I don't know.

2/ make the broker state persistent (from one scheduling loop cycle to the next, and across restarts) and thereby get rid of all "succeeded" task proxies from the pool as soon as they've registered their completed outputs. This will greatly reduce the size of the task pool in large suites that are spread across a number of cycles, and enable us to get rid of the rather complicated spent task clean-up algorithm. To allow users to view and interact with finished tasks we could move them from the main task pool to another pool that does not participate in dependency negotiation.

3/ Inner-loop optimization by use of more efficient Python data structures and techniques. I've already done this once, to great effect, but there may be more to do.

4/ If necessary, re-code any inner-loop bottleneck code in C - apparently Python has an excellent C API, and C is ten times faster than Python.

[matthewrmshin]

I'd imagine that literal string matching would be highly optimised in Python? I cannot remember if Python uses numeric hashes to implement dict and set, but I would imagine it doing so, and probably very highly optimised. Assuming that, it should be quite efficient to implement the persistent broker state as a Python dict or set.

[hjoliver]

5/ now that cylc has a dependency graph specified up front, we could actually take a step back from completely indiscriminate dependency matching (each task looks at the outputs of all other tasks): tasks could just check the outputs of the others that, from the graph, we know they depend on.

[UPDATE] - done by #1688

[hjoliver]

6/ Here's an idea that could make cylc really lean and fast: the bulk of memory use is, I suspect, for storing the complete set of [runtime] configuration data (after inheritance expansion) for every task proxy in the suite. Most of this is, by definition, only needed by the individual tasks at runtime, it has no bearing on the scheduling at all - but it is potentially a lot to hold in memory for the duration of the suite run, and loading the suite definition at start-up may be slow if we have to fully load all task proxies. So, instead of storing [runtime] data in each task proxy, we could defer loading it (and doing the inheritance) until just prior to job submission, for each task. Runtime parsing and inheritance would thus be repeated for every new task instance (or we could do it once and store the result on disk somewhere) but it would happen for individual tasks in the (soon to be) background job submission worker thread, instead of doing it all up front and storing everything. The only data held by each task proxy object would be, roughly speaking, that which is relevant to the scheduling algorithm, namely prerequisites and outputs - very light. This is also relevant to #170.

[UPDATE] this is superseded by #1689

[hjoliver]

I think we can close this Issue as superseded. For the points above:

1. doesn't matter
2. was investigated in Use the run-db to satisfy task prerequisites. #1428, follow-up Follow up on persistent broker state  #1902
3. and 4. - obvious things to do if profiling shows a bottleneck
4. done by Large suites: more efficient dependency matching. #1688
5. superseded by Large suites: light weight task proxies. #1689