# US 9,436,512 B2 · Energy efficient job scheduling in heterogeneous chip multiprocessors based on dynamic program behavior using prim model

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,436,512 B2
- Document ID: US9436512B2
- Status: Granted
- Kind: B2
- Application number: 13/721,264
- Filed: 2012-12-20
- Published: 2013-06-27
- Granted: 2016-09-06
- Earliest claimed: 2011-12-22
- Assignees: Board of Supervisors of Louisana State University and Agricultural and Mechanical College
- Applicants: Board of Supervisors of Louisiana State University and Agricultural and Mechanical College
- Inventors: Lu Peng; Bin Li
- Web page: https://patentgrep.com/patent/US9436512B2

## CPC

- G06F 9/5083: {Techniques for rebalancing the load in a distributed system}
- G06F 9/5094: {where the allocation takes into account power or heat criteria (power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206)}
- G06F 11/3447: {Performance evaluation by modeling}
- G06F 11/3452: {Performance evaluation by statistical analysis}
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

Methods for efficient job scheduling in a heterogeneous chip multiprocessor that include logic comparisons of performance metrics to determine if programs should be moved from an advanced core to a simple core or vice versa.

## Claims

### Claim 1

A method for energy efficient job scheduling in a heterogeneous chip multiprocessor, comprising the steps of:
a) randomly selecting a plurality of program pairs, each pair comprising a first program and a second program;
b) simultaneously executing the first program on an advanced core on the chip multiprocessor and the second program on a simple core on the chip multiprocessor for an interval;
c) comparing at least a first set of performance counters from the first program with at least a second set of performance counters from the second program with at least one rule extracted from a Patient Rule Induction Method (PRIM) model;
d) using a scheduler to move the first program to the simple core and the second program to the advanced core if the at least one rule extracted from the PRIM model determines that such a move would result in a lower energy consumption; and
e) repeating steps b) to d),
wherein the at least one rule extracted from the PRIM model is configured to accept as input the first set of performance counters from the first program and the second set of performance counters from the second program, and wherein the at least one rule is configured to predict if running the first program on the simple core and the second program on the advanced core would yield the lower energy consumption.

### Claim 2 (depends on 1)

The method of claim 1, wherein the advanced core is a superscalar processor configured to support out-of-order execution.

### Claim 3 (depends on 2)

The method of claim 2, wherein the advanced core further includes at least one of more functional units than the simple core, larger L1 and L2 caches than the simple core, and more advanced branch predictors than the simple core, each of which allows the advanced core to consume more power than the simple core.

### Claim 4 (depends on 2)

The method of claim 2, wherein the method includes the following steps:
i) recording the first set of performance counters from the first program having the form of <Xb1, Xb2, Xb3, . . . , Xbm>, wherein the X variables are the performance counters and the superscript identifies the performance counter where m number of performance counters are recorded;
ii) recording the second set of performance counters from the second program having the form of <Xs1, Xs2, Xs3, . . . , Xsn>, wherein the X variables are the performance counters and the superscript identifies the performance counter where n number of performance counters are recorded;
iii) measuring and recording a first energy consumption value over the interval, wherein the first program and the second program were simultaneously run on the advanced core and the simple core, respectively;
iv) measuring and recording a second energy consumption value over the interval wherein the first program and the second program were simultaneously run on the simple core and the advanced core, respectively;
v) defining a Boolean variable flag and setting the flag to TRUE if the second energy consumption value is less than the first energy consumption value;
vi) defining a training sample having the form <Xb1, Xb2, . . . , Xbm, Xs1, Xs2, . . . , Xsn, flag>;
vii) for each of the plurality of program pairs, executing steps i) through vi), thereby defining a plurality of training samples wherein each training sample corresponds to exactly one of the program pairs;
viii) inputting the plurality of training samples into the PRIM model; and
ix) extracting a plurality of rules from the PRIM model.

### Claim 5 (depends on 4)

The method of claim 4, wherein the plurality of rules are configured to accept as the input the first set of performance counters from the first program and the second set of performance counters from the second program, wherein the first program is run on the advanced core and the second program is run on the simple core, and wherein the plurality of rules are further configured to predict if running the first program on the simple core and the second program on the advanced core would yield the lower energy consumption.

### Claim 6 (depends on 5)

The method of claim 5, substituting the following steps after step vii)
x) subdividing the plurality of training samples into subgroups;
xi) inputting each subgroup into the PRIM model;
xii) extracting a plurality of rules from each PRIM model as a different rule set.

### Claim 7 (depends on 6)

The method of claim 6, wherein the plurality of training samples is subdivided with a Classification and Regression Tree (CART) mechanism.

### Claim 8 (depends on 4)

The method of claim 4, wherein the first energy consumption value is the value of the dynamic chip power usage performance counter of the chip multiprocessor at the end of the interval wherein the first program ran on the advanced core and the second program ran on the simple core, and wherein the second energy consumption value is the value of the dynamic chip power usage performance counter of the chip multiprocessor at the end of the interval wherein the second program ran on the advanced core and the first program ran on the simple core.

### Claim 9 (depends on 4)

The method of claim 4, wherein each of the first energy consumption value and the second energy consumption value are calculated by adding, at the close of each respective interval, the power of all components on the chip multiprocessor and the chip idle power.

### Claim 10 (depends on 9)

The method of claim 9, wherein the power of a component on the chip multiprocessor is calculated by the product of the component accessing rate, a scaling factor, and the maximal component power, wherein the component access rate is calculated from at least one chip multiprocessor performance counter, and each of the scaling factor and the maximal component power are calculated via at least one stress benchmark test.

### Claim 11 (depends on 1)

The method of claim 1, wherein the interval is the time until the first and second programs reaches a scheduling point, the scheduling point being the point at which the scheduler compares the at least first set of performance counters from the first program and the at least second set of performance counters from the second program with the at least one rule extracted from the PRIM model, and evaluates whether migrating the first program to the simple core and the second program to the advanced core will result in the lower energy consumption.

### Claim 12

A method for energy efficient job scheduling in a heterogeneous chip multiprocessor, comprising the steps of:
a) simultaneously executing n program pairs, each program pair comprising a first program run on one of m advanced cores and a second program run on one of n simple cores for an interval such that exactly one program is running on each of the m advanced cores and the n simple cores;
b) for each of n iterations, simultaneously comparing at least one performance counter from the first program of each program pair with at least one performance counter from the second program of that program pair with at least one rule extracted from a Patient Rule Induction Method (PRIM) model; and
c) for each of n iterations, using a scheduler to swap the cores of the first program of each program pair with that of the second program of that program pair if the at least one rule extracted from the PRIM model determines that such a move would result in a lower energy consumption,
wherein the PRIM model is configured to predict if executing the first program on the simple core and the second program on the advanced core would result in the lower energy consumption, wherein the power of a component on the chip multiprocessor is calculated by the product of the component accessing rate, a scaling factor, and the maximal component power, wherein the component access rate is calculated from at least one chip multiprocessor performance counter, and each of the scaling factor and the maximal component power are calculated via at least one stress benchmark test.

### Claim 13 (depends on 12)

The method of claim 12, wherein m is equal to n.

### Claim 14 (depends on 12)

The method of claim 12, wherein m is larger than n.

### Claim 15 (depends on 14)

The method of claim 14, further comprising: repeating steps a) to c) ┌m/n┐ rounds.

### Claim 16 (depends on 12)

The method of claim 12, wherein m is less than n.

### Claim 17 (depends on 16)

The method of claim 16, further comprising: repeating steps a) to c) ┌n/m┐ rounds.

### Claim 18

A method for energy efficient job scheduling in a heterogeneous chip multiprocessor, comprising the steps of:
a) randomly selecting a plurality of program pairs, each pair comprising a first program and a second program;
b) simultaneously executing the first program on an advanced core on the chip multiprocessor and the second program on a simple core on the chip multiprocessor for an interval;
c) measuring and recording a first energy consumption value over the interval, wherein the first program and the second program were simultaneously run on the advanced core and the simple core, respectively;
d) measuring and recording a second energy consumption value over the interval wherein the first program and the second program were simultaneously run on the simple core and the advanced core, respectively;
e) comparing at least one performance measurement from the first program with at least one performance measurement from the second program with at least one rule extracted from a Patient Rule Induction Method (PRIM) model;
f) using a scheduler to move the first program to the simple core and the second program to the advanced core if the at least one rule extracted from the PRIM model determines that such a move would result in a lower energy consumption; and
g) repeating steps b) to f),
wherein the PRIM model is configured to predict if executing the first program on the simple core and the second program on the advanced core would result in the lower energy consumption, wherein the power of a component on the chip multiprocessor is calculated by the product of the component accessing rate, a scaling factor, and the maximal component power, wherein the component access rate is calculated from at least one chip multiprocessor performance counter, and each of the scaling factor and the maximal component power are calculated via at least one stress benchmark test.