Scalable task scheduling systems and methods for cyclic interdependent tasks using semantic analysis

1. A scalable task scheduling method for cyclic interdependent tasks comprising:

for a software application including a plurality of tasks which are cyclic interdependent tasks, segmenting the plurality of tasks into a task graph with vertices including the plurality of tasks and edges including interdependencies between the plurality of tasks;

processing the task graph into a dependency graph which is a Directed Acyclic Graph (DAG) including

determining one or more islands in the task graph which are disconnected completely from the rest of the task graph,

segmenting each of the one or more islands into Strongly Connected Components (SCCs), and

breaking cycles in each of the SCCs to provide the DAG, wherein the breaking the cycles is based on determining which task in an associated cycle has a highest probability of not requiring to be re-run if that task is run with predicted input; and

causing execution of the plurality of tasks in a parallel manner based on the dependency graph.

2. The scalable task scheduling method of claim 1 , further comprising:

utilizing semantic analysis to predict input and output for the plurality of tasks and utilizing data balls which are predicted outputs as inputs to one or more tasks.

3. The scalable task scheduling method of claim 1 , wherein the segmenting each of the one or more islands into the SCCs utilizes Kosaraju's Algorithm.

4. The scalable task scheduling method of claim 1 , wherein the determining cycles in each of the SCCs utilizes Johnson's Algorithm.

5. The scalable task scheduling method of claim 1 wherein the breaking the cycles to provide the DAG includes breaking as many of the cycles as necessary such that the dependency graph is a finite directed graph with no directed cycles.

6. The scalable task scheduling method of claim 1 , wherein the software application is a network validation application configured to verify optical viability of paths in an optical network.

7. A server comprising:

a plurality of processors; and

memory storing instructions that, when executed, cause the plurality of processors to

for a software application including a plurality of tasks which are cyclic interdependent tasks, segment the plurality of tasks into a task graph with vertices including the plurality of tasks and edges including interdependencies between the plurality of tasks;

process the task graph into a dependency graph which is a Directed Acyclic Graph (DAG), to process the task graph, the processor is configured to

determine one or more islands in the task graph which are disconnected completely from the rest of the task graph,

segment each of the one or more islands into Strongly Connected Components (SCCs), and

break cycles in each of the SCCs to provide the DAG, wherein the cycles are broke based on a determination of which task in an associated cycle has a highest probability of not requiring to be re-run if that task is run with predicted input; and

execute the plurality of tasks in a parallel manner on the plurality of processors based on the dependency graph.

8. The server of claim 7 , wherein the memory storing instructions that, when executed, cause the plurality of processors to

utilize semantic analysis to predict input and output for the plurality of tasks and utilizing data balls which are predicted outputs as inputs to one or more tasks.

9. The server of claim 7 , wherein the segmentation of each of the one or more islands into the SCCs utilizes Kosaraju's Algorithm.

10. The server of claim 7 , wherein the determination of cycles in each of the SCCs utilizes Johnson's Algorithm.

11. The server of claim 7 , wherein the cycles are broken to provide the DAG by breaking as many of the cycles as necessary such that the dependency graph is a finite directed graph with no directed cycles.

12. The server of claim 7 , wherein the software application is a network validation application configured to verify optical viability of paths in an optical network.

13. A non-transitory computer-readable medium comprising instructions that, when executed, cause a plurality of processors to perform the steps of:

for a software application including a plurality of tasks which are cyclic interdependent tasks, segmenting the plurality of tasks into a task graph with vertices including the plurality of tasks and edges including interdependencies between the plurality of tasks;

processing the task graph into a dependency graph which is a Directed Acyclic Graph (DAG) including

determining one or more islands in the task graph which are disconnected completely from the rest of the task graph,

segmenting each of the one or more islands into Strongly Connected Components (SCCs), and

breaking cycles in each of the SCCs to provide the DAG, wherein the breaking the cycles is based on determining which task in an associated cycle has a highest probability of not requiring to be re-run if that task is run with predicted input; and

causing execution of the plurality of tasks in a parallel manner based on the dependency graph.

14. The non-transitory computer-readable medium of claim 13 , wherein the instructions that, when executed, cause a plurality of processors to perform the steps of:

utilizing semantic analysis to predict input and output for the plurality of tasks and utilizing data balls which are predicted outputs as inputs to one or more tasks.

15. The non-transitory computer-readable medium of claim 13 , wherein the processing the task graph comprises:

determining one or more islands in the task graph which are disconnected completely from the rest of the task graph;

segmenting each of the one or more islands into Strongly Connected Components (SCCs);

determining cycles in each of the SCCs; and

breaking the cycles to provide the DAG.