Critical Path Detection in Job
AssigneeMicrosoft Technology Licensing, LLC
InventorsYifung Lin, Omid Afnan, Dian Zhang
Life of this patent
Estimating the term…
Abstract
Identifying a path for a distributed job. A method includes dynamically collecting timing and relationship information for vertices in stages of a running job. The method further includes identifying a particular vertex. The method further includes iteratively identifying a single path parent-child sequence path for the identified vertex. The method further includes displaying a Gantt chart showing the identified path, wherein the Gantt chart shows timing relationships and execution progress information.
Claims21
A system comprising:
- one or more processors;
- and
- one or more computer-readable media having stored thereon executable instructions which, when executed by the one or more processors, cause the system to perform a computer-implemented method of improving performance of a distributed computational job by using dynamically collected timing and relationship information for vertices contained in various stages of the running job to identify a critical path for the running job, wherein the critical path is then used to resolve bottlenecks or other problems which improve the performance of the distributed computational job, and wherein the computer-implemented method comprises:
- executing a distributed computational job comprised of a plurality of stages each comprising a set of computations applied to a given data element, wherein the stages are coupled to each other by various parent-child relationships and wherein each stage includes one or more vertices, each vertex comprising a set of related computations together with a particular instance of input data to be acted on;
- as the computational job runs, dynamically collecting a job profile and storing the job profile in a database, where the job profile is a file that can be streamed and comprises timing information and relationship information for the vertices in the plurality of stages of the running computational job, and wherein the timing information comprises each vertex's creation time, queued time, executing time and completed time, each said time being stored when a particular vertex changes state, and wherein the relationship information comprises each vertex's parent vertex;
- based on the job profile, identifying a critical path of the computational job, the critical path representing the longest running single path of any parent-child vertex sequence of the computational job, and wherein the critical path is identified by beginning at the last completed vertex, identifying a parent vertex of the last completed vertex, then identifying a parent vertex of the parent vertex of the last completed vertex, and so on, until a vertex at the start of the computational job is reached;
- presenting the identified critical path in a timeline view showing all vertices along the critical path;
- and
- selecting one or more of the vertices in the timeline view so as to cause a statistics window to appear presenting statistics for the one or more selected vertices on the critical path, and using the presented statistics to improve performance of the computational job by resolving bottlenecks or other problems for at least some of the vertices on the critical path.
The system of claim 0, wherein the computer-implemented method further comprises based on user input selecting one of the operations in the selected vertex, and as a result displaying code for the selected operation.
A computer-implemented method of improving performance of a distributed computational job by using dynamically collected timing and relationship information for vertices contained in various stages of the running job to identify a critical path for the running job, wherein the critical path is then used to resolve bottlenecks or other problems which improve the performance of the distributed computational job, and wherein the computer-implemented method comprises:
- executing a distributed computational job comprised of a plurality of stages each comprising a set of computations applied to a given data element, wherein the stages are coupled to each other by various parent-child relationships and wherein each stage includes one or more vertices, each vertex comprising a set of related computations together with a particular instance of input data to be acted on;
- as the computational job runs, dynamically collecting a job profile and storing the job profile in a database, where the job profile is a file that can be streamed and comprises timing information and relationship information for the vertices in the plurality of stages of the running computational job, and wherein the timing information comprises each vertex's creation time, queued time, executing time and completed time, each said time being stored when a particular vertex changes state, and wherein the relationship information comprises each vertex's parent vertex;
- based on the job profile, identifying a critical path of the computational job, the critical path representing the longest running single path of any parent-child vertex sequence of the computational job, and wherein the critical path is identified by beginning at the last completed vertex, identifying a parent vertex of the last completed vertex, then identifying a parent vertex of the parent vertex of the last completed vertex, and so on, until a vertex at the start of the computational job is reached;
- presenting the identified critical path in a timeline view showing all vertices along the critical path;
- and
- selecting one or more of the vertices in the timeline view so as to cause a statistics window to appear presenting statistics for the one or more selected vertices on the critical path, and using the presented statistics to improve performance of the computational job by resolving bottlenecks or other problems for at least some of the vertices on the critical path.
The computer-implemented method of claim 0, wherein dynamically collecting timing and relationship information of each vertex contained the job profile comprises scheduling vertices based on compiled algebra, and wherein the compiled algebra is represented by a job graph displayed on an interface screen.
The computer-implemented method of claim 0, wherein when beginning at the last completed vertex identifying a parent vertex of the last completed vertex, then identifying a parent vertex of the parent vertex of the last completed vertex, and so on, until a vertex at the start of the computational job is reached, if a parent vertex is unable to be identified due to failure because of an error or due to the parent vertex running too long, starting another vertex with the same code as the failed parent vertex.
-20. (canceled)
A computer-program product comprising one or more hardware storage devices having stored thereon executable instructions which, when executed by one or more processors, cause the system to perform a computer-implemented method of improving performance of a distributed computational job by using dynamically collected timing and relationship information for vertices contained in various stages of the running job to identify a critical path for the running job, wherein the critical path is then used to resolve bottlenecks or other problems which improve the performance of the distributed computational job, and wherein the computer-implemented method comprises:
- executing a distributed computational job comprised of a plurality of stages each comprising a set of computations applied to a given data element, wherein the stages are coupled to each other by various parent-child relationships and wherein each stage includes one or more vertices, each vertex comprising a set of related computations together with a particular instance of input data to be acted on;
- as the computational job runs, dynamically collecting a job profile and storing the job profile in a database, where the job profile is a file that can be streamed and comprises timing information and relationship information for the vertices in the plurality of stages of the running computational job, and wherein the timing information comprises each vertex's creation time, queued time, executing time and completed time, each said time being stored when a particular vertex changes state, and wherein the relationship information comprises each vertex's parent vertex;
- based on the job profile, identifying a critical path of the computational job, the critical path representing the longest running single path of any parent-child vertex sequence of the computational job, and wherein the critical path is identified by beginning at the last completed vertex, identifying a parent vertex of the last completed vertex, then identifying a parent vertex of the parent vertex of the last completed vertex, and so on, until a vertex at the start of the computational job is reached;
- presenting the identified critical path in a timeline view showing all vertices along the critical path;
- and
- selecting one or more of the vertices in the timeline view so as to cause a statistics window to appear presenting statistics for the one or more selected vertices on the critical path, and using the presented statistics to improve performance of the computational job by resolving bottlenecks or other problems for at least some of the vertices on the critical path.
Dependencies are inferred from the claim text.