Analysis of parallel processing systems

• US 10,055,460 B2
• Filed: 09/03/2014
• Issued: 08/21/2018
• Est. Priority Date: 09/04/2013
• Status: Active Grant

• Current Assignee: Arm Limited (SoftBank Group Corp.)
• Original Assignee: Arm Limited (SoftBank Group Corp.)
• Inventors: O'Connor, Mark
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US14/916,648
• Publication Number:
  US 20160203188A1
• Time in Patent Office: 1,448 Days
• Field of Search: 707756
• CPC Class Codes: G06F 11/3003 Monitoring arrangements specially adapted to the computing system or computing system component being monitored
• CPC Class Codes: G06F 11/3062 where the monitored property is the power consumption power management in a computing system G06F1/3203
• CPC Class Codes: G06F 11/3075 the data filtering being achieved in order to maintain consistency among the monitored data, e.g. ensuring that the monitored data belong to the same timeframe, to the same system or component
• CPC Class Codes: G06F 11/323 Visualisation of programs or trace data
• CPC Class Codes: G06F 11/3404 for parallel or distributed programming
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 11/3476 Data logging G06F11/14, G06F11/2205 take precedence
• CPC Class Codes: G06F 11/3495 for systems
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 2201/835 Timestamp
• CPC Class Codes: G06Q 10/00 Administration; Management

Abstract

A method of analysing streams of metric data from a plurality of data processing sources (2) in a parallel processing system (1), using a computer (6). Each stream includes time stamped data associated with the respective data processing source in respect of a given metric which is sampled at intervals. For each stream of data, a start time and an end time are identified. A normalized start time and a normalized end time are determined across all streams. Sampling points are specified between the normalized start time and the normalized end time. For each stream of data, the data is re-sampled at the specified sampling points. For each sampling point, the re-sampled data across all the streams of data is processed to determine a statistical derivative of the data. A report is displayed which represents the values of the statistical derivative as a function of time. The process may be applied to various different metrics, and the results displayed at the same time, on a common time axis.

Claims

1. A method for generating a report output in respect of a given metric, the method comprising using a data processing system to carry out the following steps for the given metric:

receiving a plurality of streams of data from a plurality of data processing sources of a parallel processing system, each stream including time-stamped data, associated with a respective data processing source of the plurality of data processing sources, in respect of the given metric which is sampled at intervals;

for each stream of data, identifying a respective start time and a respective end time;

determining a normalized start time and a normalized end time;

specifying normalized sampling points between the normalized start time and the normalized end time;

for each stream of data, re-sampling the data at the specified normalized sampling points between the normalized start time and the normalized end time, thereby producing normalized sampled data;

for each normalized sampling point, using a statistical-analysis tree structure to analyze the normalized sampled data across all the streams of data to determine one or more statistical derivatives of the normalized sampled data, the statistical-analysis tree structure having nodes, wherein, for each node in the statistical-analysis tree structure that has one or more immediately-preceding nodes, values for the one or more immediately-preceding nodes are used to determine a value for said node; and

providing a report output which represents values of the one or more statistical derivatives as a function of time.

2. The method of claim 1, wherein the statistical-analysis tree structure is a binary tree structure.

3. The method of claim 1, wherein when there is no data at a specified normalized sampling point for a particular stream of data, an interpolated value is calculated from the stream of data.

4. The method of claim 1, wherein the one or more statistical derivatives comprise two or more derivatives selected from minimum, maximum, mean, variance and skew.

5. The method of claim 4, comprising calculating the two or more statistical derivatives in parallel and merging the statistical derivatives using the statistical-analysis tree structure.

6. The method of claim 4, wherein the statistical derivatives include maximum and minimum, the method further comprising displaying a presentation of the report output of the statistical derivatives as a function of time along a time axis, wherein for each point on the time axis, there is a respective first point representing a maximum value for the metric and a respective second point representing a minimum value for the metric.

7. The method of claim 6, wherein, for each point on the time axis, there is a respective third point representing a mean value for the metric.

8. The method of claim 7, wherein, for each point on the time axis, a region between the first and second points is provided with variable shading, determined in accordance with distance from the mean value of values in this region.

9. The method of claim 8, wherein points in the region between the first and second points that are closer to the mean value are shaded more darkly than points that are farther from the mean value.

10. The method of claim 9, wherein the degree of shading is calculated using a probability function for a given distribution.

11. The method of claim 7, wherein the respective first points for each point on the time axis are joined by a first line, representing a plot of the maximum values;

the respective second points for each point on the time axis are joined by a second line, representing a plot of the minimum values; and

the respective third points for each point on the time axis are joined by a third line, representing a plot of the mean values.

12. The method of claim 1, wherein, for each normalized sampling point, a statistically-valid distribution is generated for a root node of the respective statistical-analysis tree structure.

13. The method of claim 12, wherein each said statistically-valid distribution is characterized by a respective mean value, a respective variance value, a respective minimum value and a respective maximum value.

14. The method of claim 1, wherein each stream of data from the plurality of streams of data is associated with a respective label, and wherein the one or more statistical derivatives includes minimum or maximum, the method further comprising, for each normalized sampling point, using the statistical-analysis tree structure to merge the labels of the plurality of streams of data to determine the label of a stream of data from the plurality of streams of data that has a minimum value across the streams of data, at the normalized sampling point, or to determine the label of a stream of data from the plurality of streams of data that has a maximum value across the streams of data, at the normalized sampling point.

15. The method of claim 1, comprising carrying out the step of determining the normalized start time and the normalized end time using a time-merging tree structure having nodes, in which, for each node in the time-merging tree structure that has one or more immediately-preceding nodes, a start time and an end time are determined for the node by merging start and end times for the one or more immediately preceding nodes.

16. The method of claim 15, wherein the statistical-analysis tree structure and the time-merging tree structure are the same tree structure.

17. The method of claim 1, wherein there are a plurality of streams of data, each including time-stamped data in respect of a plurality of different metrics, associated with each respective data processing source, and the method is repeated for each different metric.

18. The method of claim 17, wherein for each metric there is produced a report output which represents values of a plurality of statistical derivatives as a function of time.

19. The method of claim 18, comprising displaying the report outputs for the different metrics on a common time line.

20. The method of claim 1, comprising logging or displaying the report output.

21. A non-transitory computer-readable medium containing instructions for configuring a data-processing system to generate a report output in respect of a given metric by carrying out the following steps for the given metric:

receiving a plurality of streams of data from a plurality of data processing sources of a parallel processing system, each stream including time-stamped data, associated with a respective data processing source of the plurality of data processing sources, in respect of the given metric which is sampled at intervals;

for each stream of data, identifying a respective start time and a respective end time;

determining a normalized start time and a normalized end time;

specifying normalized sampling points between the normalized start time and the normalized end time;

for each stream of data, re-sampling the data at the specified normalized sampling points between the normalized start time and the normalized end time, thereby producing normalized sampled data;

for each normalized sampling point, using a statistical-analysis tree structure to analyze the normalized sampled data across all the streams of data to determine one or more statistical derivatives of the normalized sampled data, the statistical-analysis tree structure having nodes, wherein, for each node in the statistical-analysis tree structure that has one or more immediately-preceding nodes, values for the one or more immediately-preceding nodes are used to determine a value for said node; and

providing a report output which represents values of the one or more statistical derivatives as a function of time.