CALCULATION METHOD AND APPARATUS FOR EVALUATING RESPONSE TIME OF COMPUTER SYSTEM IN WHICH PLURALITY OF UNITS OF EXECUTION CAN BE RUN ON EACH PROCESSOR CORE

• US 20150169380A1
• Filed: 12/15/2014
• Published: 06/18/2015
• Est. Priority Date: 12/17/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Inoue, Hiroshi
• Granted Patent: US 9,600,290 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

A calculation method for evaluating response time in a computer system in which a plurality of units of execution are run on individual processor cores. The calculation method evaluates response time in a computer system in which a plurality of units of execution are run in parallel on individual processor cores while sharing internal hardware resources. The method includes the steps of: normalizing the utilization state of the computer system with the state of parallelism of the units of execution and evaluating the utilization state; and calculating an expected value of response time in a desired state of parallelism of the units of execution from the normalized utilization state on the basis of queueing theory in which changes in average single-thread performance of the units of execution according to the parallel running state are taken into account.

Claims

1. A computer-implemented calculation method for evaluating a response time in a computer system, wherein a plurality of units of execution are run in parallel on individual processor cores while sharing internal hardware resources, the method comprising:

normalizing the utilization state of the computer system with the state of parallelism of the units of execution and evaluating the utilization state; and

calculating an expected value of response time in a desired state of parallelism of the units of execution from the normalized utilization state on the basis of queueing theory, wherein changes in an average single-thread performance of the units of execution according to the parallel running state are taken into account.

2. The computer-implemented calculation method according to claim 1, wherein accounting for changes in the average single-thread performance refers to calculating a waiting time in a queue by taking changes in the average single-thread performance according to a number of simultaneous operations of units of execution in a processor core at a moment as changes in an average service factor.

3. The computer-implemented calculation method according to claim 1, wherein:

the computer system includes a plurality of processor cores; and

the step of calculating an expected value of response time includes the steps of;

calculating a waiting time in a queue in which the number of units of execution in each processor core is the number of windows;

calculating the migratability probability that at least one processor core capable of accepting a task from another processor core is present in a queue with the number of windows across the plurality of processor cores; and

calculating an expected value of an average response time as the response time from the waiting time and the migratability probability.

4. The computer-implemented calculation method according to claim 3, wherein the step of calculating a waiting time includes the steps of, for two or more degrees of parallelism of units of execution that can be simultaneously operated on a processor core:

giving an initial value of the average single-thread performance of the units of execution;

calculating the distribution of probability of the number of tasks present in each processor core in a queue in which the number of units of execution in each processor core is the number of windows based on the assumption that the average single-thread performance of the units of execution is an average service factor;

updating the average single-thread performance of the units of execution on the basis of the distribution of probability of the number of tasks present in each processor core; and

determining a condition for terminating iteration of the step of calculating the distribution of probability and the updating step.

5. The computer-implemented calculation method according to claim 3, wherein the step of calculating the migratability probability includes the steps of:

calculating the distribution of the probability of the number of tasks present in the plurality of processor cores in a queue in which the total number of units of execution across the plurality of processor cores is the number of windows on the assumption that the average single-thread performance of the units of execution is an average service factor; and

calculating, as the migratability probability, the probability that the number of tasks is equal to or less than a threshold value in at least one of the plurality of processor cores on the basis of the distribution of probability of the number of tasks present in the plurality of processor core.

6. The computer-implemented calculation method according to claim 1, wherein

the step of calculating an expected value of response time is the step of calculating an expected value of response time for the degree of parallelism of a processor core or each of combinations of degrees of parallelism of a plurality of processor cores;

and

the calculation method further comprises;

determining the degree of parallelism or a combination of degrees of parallelism at which the calculated expected value of response time is optimized as the state of parallelism of units of execution used in the utilization state.

7. The computer-implemented calculation method according to claim 1, wherein the evaluation step is the step of calculating normalized CPU utilization of the computer system from the single-thread performance of the units of execution at the individual degrees of parallelism and the utilization of the individual units of execution.

8. The computer-implemented calculation method according to claims 1, wherein

the computer is included in the computer system;

the evaluation step is the step of evaluating the normalized present utilization state on the basis of present CPU utilization information obtained in the computer system; and

the method further comprises;

updating the setting of the state of parallelism of units of execution used on the basis of the calculated result of an expected value of response time in the state of parallelism.

9. The computer-implemented calculation method according to claim 1:

wherein the computer is separated from the computer system to be evaluated; and

wherein the evaluation step is the step of assuming a plurality of utilization states of the computer system; and

the calculation method further comprises;

recording the determined setting of the state of parallelism of units of execution used in association with the assumed individual plurality of utilization states.

10. The computer-implemented calculation method according to claim 1:

wherein the computer system provides a simultaneous multi-threading environment; and

wherein the unit of execution is a hardware thread.

11. A non-transitory computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions which, when implemented, cause a computer device to carry out the steps of the method according to claim 1.

13. The calculation apparatus according to claim 11, wherein

the computer system includes a plurality of processor cores;

and

the response time calculation section includes;

an in-core model calculation portion for calculating a waiting time in a queue, wherein the number of units of execution in each processor core is the number of windows; and

an inter-core model calculation portion for calculating the migratability probability that at least one processor core capable of accepting a task from another processor core is present in a queue with the number of windows across the plurality of processor cores and calculating an expected value of an average response time as the response time from the waiting time and the migratability probability.

16. The calculation apparatus according to one of claims 11, wherein

the calculation apparatus is the computer system;

the utilization-state evaluation section evaluates the normalized present utilization state on the basis of present processing-unit utilization information obtained in the computer system; and

the calculation apparatus further comprises a setting update unit for updating the setting of the state of parallelism of units of execution used on the basis of the calculated result of an expected value of response time in the state of parallelism.

17. The calculation apparatus according to claim 11, wherein:

the calculation apparatus is separated from the computer system to be evaluated;

the utilization-state evaluation section assumes a plurality of utilization states of the computer system; and

the calculation apparatus further comprises a recording unit for recording the determined setting of the state of parallelism of units of execution used in association with the assumed individual plurality of utilization states.

12. A calculation apparatus for evaluating response time in a computer system, wherein in a plurality of units of execution are in parallel on individual processor cores while sharing internal hardware resources, the apparatus comprising:

a utilization-state evaluation section for normalizing the utilization state of the computer system with the state of parallelism of the units of execution and evaluating the utilization state; and

a response time calculation section for calculating an expected value of response time in a desired state of parallelism from the normalized utilization state on the basis of queueing theory, wherein changes in average single-thread performance of the units of execution according to the parallel running state are taken into account.

14. The calculation apparatus according to claim 12, wherein the in-core model calculation portion includes, for two or more degrees of parallelism of units of execution that are simultaneously operated on a processor core:

an initial-value setting portion for giving an initial value of the average single-thread performance of the units of execution;

an in-core-task-distribution calculation portion for calculating the distribution of probability of the number of tasks present in each processor core in a queue in which the number of units of execution in each processor core is the number of windows on the assumption that the average single-thread performance of the units of execution is an average service factor;

a single-thread performance update portion for updating the average single-thread performance of the units of execution on the basis of the distribution of probability of the number of tasks present in each processor core; and

a termination-condition determination portion for determining a condition for terminating iteration of the calculation of the distribution of probability and the update.

15. The calculation apparatus according to claim 12, wherein the inter-core model calculation portion includes:

an in-system-task-distribution calculation portion for calculating the distribution of the probability of the number of tasks present in the plurality of processor cores in a queue in which the total number of units of execution across the plurality of processor cores is the number of windows on the assumption that the average single-thread performance of the units of execution is an average service factor; and

a migratability-probability calculation portion calculating, as the migratability probability, the probability that the number of tasks is equal to or less than a threshold value in at least one of the plurality of processor cores on the basis of the distribution of probability of the number of tasks present in the plurality of processor core.

18. A computer system, wherein a plurality of units of execution are run in parallel on a plurality of individual processor cores while sharing internal hardware resources, the computer system comprising:

a utilization-state evaluation section for normalizing the present utilization state of the computer system with the state of parallelism of the units of execution and evaluates the utilization state; and

a setting update unit for updating the setting of the state of parallelism of units of execution used on the basis of association information associating the state of parallelism of the units of execution used with the utilization state from the normalized present utilization state;

wherein the association information is information that associates the state of parallelism, wherein an expected value of response time is optimized with the individual utilization states, and wherein the expected value being calculated on the basis of queueing theory wherein changes in average single-thread performance of the units of execution according to the parallel running state are taken into account.