spawn on demand / event driven graph

[oliver-sanders]

Replace the iterative task pool with an event-driven graph solution.

Just realised that despite all the discussion we don't actually have an issue open for this
(let me know if I've simply missed it).

For a longer (and much more rambling) read see https://github.com/cylc/cylc-flow/wiki/Possible-Cylc-Futures#event-driven-scheduler.

Quick overview

• Translate an iterative problem into a lookup problem.
  • O(N) => O(1)
  • Messages come into the system,
  • a lookup associates them with nodes in the graph,
  • these events propagate through the graph,
  • so there is no need to loop over the task pool to determine consequences.
• Implement cycling "drivers" to provide a simple abstract interface for things a graph could cycle over.

Benefits

• Better scaling to number of:
  • active tasks (close Large suites: light weight task proxies. #1689);
  • recurrences (close Suites a large number of cycles in can have high cpu usage #1751);
  • prerequisites (close Use shared dependency objects. #1894).
• Improved responsiveness (from one task succeeding to the next submitting should be fast).
• Removes the need to keep around inactive TaskProxy objects (closes limit task pool size #987, Large suites: light weight task proxies. #1689).
• Understands graph structure so can make informed decisions when it changes (closes reload, restart - initial and final cycle point changes #773, reload and restart - smart insertion of new tasks #774)
• Obsoletes/removes suicide triggering with branched workflows (closes graph: optional branching #3226)
• Clean up the TaskProxy/TaskState/Prerequisite/Depdency/Output interaction (closes Improve interaction between task state, output and prerequisite #2329)

Further desired benefits

• Supports subgraphs (closes graph: optional branching #3226, Cycling - run every [date-time] *starting from* some offset of the ICP #2668).
• Supports cycling within subgraphs (closes Sub-cycling? #2241).
• Abstracts cycling "drivers" allowing the following to be used as cycling "drivers":
  • Suite parameters.
  • External events (closes Add a cron-like real time scheduling mode? #3188).
  • RRULE datetime recurrences (closes Advanced Cycling #2398, cycling: last day of the month - 31T00 #2382).
  • Dynamic collections (e.g. a suite parameter which can be changed whilst the suite is running e.g. via broadcast).
  • (Would need to close Relative Inter Cycle Dependencies #2452 on route)

[hjoliver]

Another benefit:

• should be much easier for users to understand (currently the task pool model has to be understood to explain some aspects of workflow evolution and response to commands).

[matthewrmshin]

(Should we mark some of the issues mentioned above as superseded and close them down?)

[matthewrmshin]

(Can probably supersede #2329 as well.)

[oliver-sanders]

(Should we mark some of the issues mentioned above as superseded and close them down?)

I guess, maybe some of the ones in the first section?

(Can probably supersede #2329 as well.)

Good point, added.

[matthewrmshin]

#993 was the original version of this issue!

[hjoliver]

update post merge of task-proxy based spawn on demand

With merge of #3515 Cylc now has "spawn on demand" but by a different method than suggested here, which required less extensive refactoring: task proxies simply record (during graph parsing) who depends on their outputs, and spawn them as outputs are completed. So there is still no explicit use of the graph at run time.

We should probably close this issue and replace it with several others:

• consider converting to the method suggest here on the Cylc 9 timescale?
• other enhancements suggested here - e.g. see "further desired benefits" above.