Schedulers with load-store queue awareness

Patent metadata

Field	Value
Publication number	US-9563428-B2
Application number	US-201514669472-A
Country	US
Kind code	B2
Filing date	Mar 26, 2015
Priority date	Mar 26, 2015
Publication date	Feb 7, 2017
Grant date	Feb 7, 2017

Abstract

In one embodiment, a computer-implemented method includes tracking a size of a load-store queue (LSQ) during compile time of a program. The size of the LSQ is time-varying and indicates how many memory access instructions of the program are on the LSQ. The method further includes scheduling, by a computer processor, a plurality of memory access instructions of the program based on the size of the LSQ.

First claim

What is claimed is:

1. A system comprising:
a memory having computer readable instructions; and
one or more processors for executing the computer readable instructions, the computer readable instructions comprising:
tracking a size of a load-store queue (LSQ) during compile time of a program, the size of the LSQ being time-varying and indicating how many memory access instructions of the program are on the LSQ; and
scheduling, into a plurality of time windows, a plurality of memory access instructions of the program, wherein the scheduling into each time window of the plurality of time windows is based on how many memory access instructions of the program are on the LSQ at the time window, and wherein the scheduling comprises:
determining that the LSQ has reached a maximum number of memory access instructions at a first time window of the plurality of time windows;
estimating a length for which a memory access instruction of the plurality of memory accesses will be on the LSQ;
selecting a time at which to schedule the memory access instruction such that the size of the LSQ does not exceed the maximum number of memory access instructions throughout the length of the memory access instruction;
wherein the selecting comprises identifying a different time than the first time window at which to schedule the memory access instruction, responsive to the LSQ having reached the maximum number of memory access instructions at the first time window, wherein the identifying comprises scheduling the memory access instruction at an earlier time than the first time window; and
scheduling an arithmetic instruction at the first time window in addition to the maximum number of memory access instructions, responsive to determining that the LSQ has reached the maximum number of memory access instructions at the first time window.

2. The system of claim 1 , wherein the estimating the length for which the memory access instruction of the plurality of memory accesses will be on the LSQ comprises estimating a latency of the memory access instruction.

3. The system of claim 1 , wherein the estimating the length for which the memory access instruction of the plurality of memory accesses will be on the LSQ comprises determining how many iterations of the memory access instruction will be issued.

4. The system of claim 1 , the computer readable instructions further comprising:
dividing a running time of the program into a plurality of time windows, wherein each time window comprises two or more processor cycles;
wherein the scheduling the plurality of memory access instructions of the program comprises ensuring the size of the LSQ does not exceed the maximum number of memory access instructions in each time window of the plurality of time windows.

5. A computer program product for scheduling instructions, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:
tracking a size of a load-store queue (LSQ) during compile time of a program, the size of the LSQ being time-varying and indicating how many memory access instructions of the program are on the LSQ; and
scheduling, into a plurality of time windows, a plurality of memory access instructions of the program, wherein the scheduling into each time window of the plurality of time windows is based on how many memory access instructions of the program are on the LSQ at the time window, and wherein the scheduling comprises:
determining that the LSQ has reached a maximum number of memory access instructions at a first time window of the plurality of time windows;
estimating a length for which a memory access instruction of the plurality of memory accesses will be on the LSQ;
selecting a time at which to schedule the memory access instruction such that the size of the LSQ does not exceed the maximum number of memory access instructions throughout the length of the memory access instruction;
wherein the selecting comprises identifying a different time than the first time window at which to schedule the memory access instruction, responsive to the LSQ having reached the maximum number of memory access instructions at the first time window, wherein the identifying comprises scheduling the memory access instruction at an earlier time than the first time window; and
scheduling an arithmetic instruction at the first time window in addition to the maximum number of memory access instructions, responsive to determining that the LSQ has reached the maximum number of memory access instructions at the first time window.

6. The computer program product of claim 5 , wherein the estimating the length for which the memory access instruction of the plurality of memory accesses will be on the LSQ comprises estimating a latency of the memory access instruction.

7. The computer program product of claim 5 , further comprising:
dividing a running time of the program into a plurality of time windows, wherein each time window comprises two or more processor cycles;
wherein the scheduling the plurality of memory access instructions of the program comprises ensuring the size of the LSQ does not exceed the maximum number of memory access instructions in each time window of the plurality of time windows.

Assignees

• IBM

Inventors

• Chen Tong
• Eichenberger Alexandre E
• Jacob Arpith C
• Sura Zehra N

Classifications

• G06F8/4434

  Reducing the memory space required by the program code · CPC title

• G06F9/3842 Primary

  Speculative instruction execution · CPC title

• G06F9/30043

  LOAD or STORE instructions; Clear instruction · CPC title

• G06F8/4451 Primary

  Avoiding pipeline stalls · CPC title

• G06F9/3854

  Instruction completion, e.g. retiring, committing or graduating · CPC title