Schedulers with load-store queue awareness

Patent metadata

Field	Value
Publication number	US-2016283248-A1
Application number	US-201514669472-A
Country	US
Kind code	A1
Filing date	Mar 26, 2015
Priority date	Mar 26, 2015
Publication date	Sep 29, 2016
Grant date	—

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

1 - 7 . (canceled)

8 . 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 a plurality of memory access instructions of the program based on the size of the LSQ.

9 . The system of claim 8 , wherein the scheduling comprises:
estimating a length for which a memory access instruction of the plurality of memory accesses will be on the LSQ; and selecting a time at which to schedule the memory access instruction such that the size of the LSQ remains within a capacity of the LSQ throughout the length of the memory access instruction.

10 . The system of claim 9 , wherein the selecting comprises:
determining that scheduling the memory access instruction at a given time would cause the size of the LSQ to exceed the capacity of the LSQ; and identifying a different time than the given time at which to schedule the memory access instruction, wherein the identifying comprises at least one of postponing the instruction and scheduling the instruction at an earlier time.

11 . The system of claim 9 , 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.

12 . The system of claim 9 , 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.

13 . The system of claim 8 , the computer readable instructions further comprising:
dividing a running time of the program into a plurality of time windows, wherein each time window comprises one or more processor cycles; wherein the scheduling the plurality of memory access instructions of the program based on the size of the LSQ comprises ensuring the size of the LSQ does not exceed a capacity of the LSQ in a first time window of the plurality of time windows.

14 . The system of claim 13 , the computer readable instructions further comprising scheduling an arithmetic instruction of the program in a time window during which the size of the LSQ would exceed the capacity of the LSQ if a memory access instruction were scheduled.

15 . 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 a plurality of memory access instructions of the program based on the size of the LSQ.

16 . The computer program product of claim 15 , wherein the scheduling comprises:
estimating a length for which a memory access instruction of the plurality of memory accesses will be on the LSQ; and selecting a time at which to schedule the memory access instruction such that the size of the LSQ remains within a capacity of the LSQ throughout the length of the memory access instruction.

17 . The computer program product of claim 16 , wherein the selecting comprises:
determining that scheduling the memory access instruction at a given time would cause the size of the LSQ to exceed the capacity of the LSQ; and identifying a different time than the given time at which to schedule the memory access instruction, wherein the identifying comprises at least one of postponing the instruction and scheduling the instruction at an earlier time.

18 . The computer program product of claim 16 , 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.

19 . The computer program product of claim 15 , further comprising:
dividing a running time of the program into a plurality of time windows, wherein each time window comprises one or more processor cycles; wherein the scheduling the plurality of memory access instructions of the program based on the size of the LSQ comprises ensuring the size of the LSQ does not exceed a capacity of the LSQ in a first time window of the plurality of time windows.

20 . The computer program product of claim 19 , further comprising scheduling an arithmetic instruction of the program in a time window during which the size of the LSQ would exceed the capacity of the LSQ if a memory access instruction were scheduled.

Assignees

• IBM

Inventors

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

Classifications

• G06F9/3842 Primary

  Speculative instruction execution · CPC title

• G06F9/30043

  LOAD or STORE instructions; Clear instruction · CPC title

• G06F8/4434

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

• G06F8/4451 Primary

  Avoiding pipeline stalls · CPC title

• G06F9/3854

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