Analytic engine for optimally distributing work between threads for dependency-based scheduling for concurrent online analytics

Patent metadata

Field	Value
Publication number	US-12554533-B2
Application number	US-202217708187-A
Country	US
Kind code	B2
Filing date	Mar 30, 2022
Priority date	Mar 30, 2021
Publication date	Feb 17, 2026
Grant date	Feb 17, 2026

Abstract

A system, method and non-transitory computer-readable storage medium for computing a full dependency graph before obtaining a result of an analytic; and constructing a scheduling graph to optimally distribute work between the available threads, based on the full dependency graph. This may include receiving a request for a result of an algorithm executed on a node; checking, by the processor, the algorithm for a secondary dependency algorithm and executing, by the processor, the algorithm on the node.

First claim

What is claimed is:

1 . A computer-implemented method for an analytics engine comprising:
computing, by a processor, a full dependency graph before obtaining a result of an analytic, the full dependency graph comprising a plurality of nodes and threads, where every node in the full dependency graph is an executable unit and at least some of the plurality of nodes depend on data from another of the plurality of nodes in order to compute a metric at the given node, and each of the threads of the full dependency graph is a separate processing unit the analytics engine iterates over as a graph edge; constructing, by the processor, a scheduling graph from the full dependency graph to optimally distribute work between available threads of the full dependency graph; receiving, by the processor, a request for a result of an algorithm executed on the given node; checking, by the processor, the algorithm for a secondary dependency algorithm; calculating, by the secondary dependency algorithm graph by recursively executing the secondary dependency algorithm on the given node; and parallel scheduling, by the processor, on the secondary dependency algorithm graph to pre-calculate dependency results; caching, by the processor, the pre-calculated dependency results; and executing, by the processor, the algorithm on the given node based on the scheduling graph.

2 . The computer-implemented method of claim 1 , wherein executing the algorithm on the given node comprises:
calculating, by the processor, un-cached dependencies by the algorithm.

3 . A system comprising:
a processor for an analytics engine; and a memory storing instructions that, when executed by the processor, configure the system to: compute, by the processor, a full dependency graph before obtaining a result of an analytic the full dependency graph comprising a plurality of nodes where each node in the full dependency graph is an executable unit and at least some of the plurality of nodes depend on data from another of the plurality of nodes in order to compute a metric at a given node; construct, by the processor, a scheduling graph from the full dependency graph to optimally distribute work between available threads of the full dependency graph, each of the threads of the full dependency graph being a separate processing unit the analytics engine iterates over; receive, by the processor, a request for a result of an algorithm executed on the given node; check, by the processor, the algorithm for secondary dependency algorithm; calculate, by the processor, a secondary dependency algorithm graph by recursively executing the dependency algorithm on the given node; and parallel schedule, by the processor on the secondary dependency algorithm graph to pre-calculate dependency results; cache, by the processor the precalculated dependency results; and execute, by the processor, the algorithm on the given node based on the scheduling graph.

4 . The system of claim 3 , wherein in executing the algorithm on the given node, the system is further configured to:
calculate, by the processor, un-cached dependencies by the algorithm.

5 . A non-transitory computer-readable storage medium, the computer-readable storage medium including instructions that when executed by a computer, cause the computer to:
compute, by a processor of an analytics engine, a full dependency graph before obtaining a result of an analytic, the full dependency graph comprising a plurality of nodes and threads, where each node in the full dependency graph is an executable unit and at least some of the plurality of nodes depend on data from another of the plurality of nodes in order to compute a metric at a given node, and each of the threads of the full dependency graph is a separate processing unit the analytics engine iterates over as a graph edge; and construct, by the processor, a scheduling graph from the full dependency graph to optimally distribute work between available threads of the full dependency graph; receive, by the processor, a request for a result of an algorithm executed on the given node; check, by the processor, the algorithm for a secondary dependency algorithm; calculate, by the processor, a secondary dependency algorithm graph by recursively executing the dependency algorithm on the given node; and parallel schedule, by the processor on the secondary dependency algorithm graph to pre-calculate dependency results; cache, by the processor, the pre-calculated dependency results; and executing, by the processor, the algorithm on the given node based on the scheduling graph.

6 . The non-transitory computer-readable storage medium of claim 5 , wherein the instructions for executing the algorithm on the given node, further cause the computer to:
calculate, by the processor, un-cached dependencies by the algorithm.

Assignees

• Kinaxis Inc

Inventors

• Henshall Dane
• Diener Matt
• Cadieux-Pelletier Philippe
• Stanley Nathaniel
• Macmillan Rob

Classifications

• G06F9/3838

  Dependency mechanisms, e.g. register scoreboarding · CPC title

• G06F9/3885

  using a plurality of independent parallel functional units · CPC title

• G06Q10/0631

  Resource planning, allocation, distributing or scheduling for enterprises or organisations · CPC title

• G06F8/433

  Dependency analysis; Data or control flow analysis · CPC title

• G06F9/5066

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title