Schedulers with load-store queue awareness

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.

BACKGROUND

Various embodiments of this disclosure relate to compile-time schedulers and, more particularly, to compile-time schedulers with load-store queue awareness.

In executing a program, a processor core may need to perform an ordered sequence of arithmetic instructions and memory access instructions. Generally, performing a memory access instruction can take two or more orders of magnitude more time than an arithmetic operation. The specific order of this sequence may be determined by a compiler that converted the program into code executable by the processor.

A load-store queue (LSQ) is a shared queue used by one or more processor cores of a computer processor, where each core inserts memory access instructions into the LSQ during execution of a program. Generally, the LSQ is a first-in-first-out (FIFO) queue, such that memory access instructions are handled in the order they are received at the LSQ. When a memory access instruction is handled, the desired memory addresses are accessed and the retrieved data is returned to the requesting processor core.

The LSQ has a finite capacity and thus has the potential to become full. When the LSQ is full, subsequent memory access instructions from a processor core are forced to stall. In the case of an in-order core, even arithmetic operations that are memory-independent and otherwise ready to execute will stall if they are scheduled for execution after the memory access instruction causing the stall.

SUMMARY

In one embodiment of this disclosure, 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.

In another embodiment, a system includes a memory having computer readable instructions and one or more processors for executing the computer readable instructions. The computer readable instructions include 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 computer readable instructions further include scheduling a plurality of memory access instructions of the program based on the size of the LSQ.

In yet another embodiment, a computer program product for scheduling instructions includes a computer readable storage medium having program instructions embodied therewith. The program instructions are executable by a processor to cause the processor to perform a method. The 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 a plurality of memory access instructions of the program based on the size of the LSQ.

DETAILED DESCRIPTION

Various embodiments of this disclosure are compile-time schedulers with load-store queue (LSQ) awareness. According to some embodiments, a scheduling system, being LSQ-aware, may improve program performance by explicitly tracking the running size of an LSQ and ordering program instructions to postpone memory access requests to minimize or reduce processor stalls.

FIG. 1is a block diagram of a scheduling system100, according to some embodiments of this disclosure. In some embodiments, the scheduling system100may be integrated into a compiler110, and may be used to schedule instructions of a program while the source code of that program is being compiled by the compiler110. The result of the compilation may be an executable file with scheduled instructions. The scheduling system100may be LSQ-aware, and as shown, the scheduling system100may include an LSQ tracker120and an LSQ updater130. In general, the LSQ tracker120may track the status of the LSQ to determine whether the LSQ will become overused if instructions are added at various times; and the LSQ updater130may update the time-varying status of the LSQ130based on instructions having been newly scheduled. These aspects of the scheduling system100will be described in more detail later in this disclosure.

FIG. 2is another block diagram of the scheduling system100, according to some embodiments of this disclosure. As shown inFIG. 2, in contrast toFIG. 1, the scheduling system100need not be integrated into the compiler. While the scheduling system100may run at compile time, it may be sufficient to have the scheduling system100merely in communication with the compiler100, rather than integrated into the compiler100.

FIG. 3is a block diagram of a processor310configured to execute a program scheduled by the scheduling system100, according to some embodiments of this disclosure. As shown, the processor310may have one or more processor cores320and an LSQ330. The processor cores320may be in communication with the LSQ330, such that memory access instructions from the processor cores320may be processed through the LSQ330. The processor310may handle a memory access instruction on the LSQ130by retrieving data in a memory340and returning that retrieved data to the processor core320that issued the instruction. In some embodiments, the LSQ may be a first-in-first-out (FIFO) queue, such that memory access instructions are addressed in the order they are received at the LSQ330. In general, the scheduling system100may schedule instructions by tracking the time-varying status of the LSQ130during compile time, such that processor stalls are reduced are minimized.

Throughout this disclosure, QC represents the LSQ capacity, which is the maximum number of memory access instructions that can be maintained in the LSQ330at a time. Through tracking of the LSQ330, the scheduling system100may ensure that no more than QC memory access instructions are outstanding at any given time. Further, ISU represents an array of the time-varying size, or status, of the LSQ330, which is the quantity of memory access instructions on the queue at a given time. More specifically, each item in the array ISU[t] represents the quantity of memory access instructions in the LSQ330at time t. The size of LSQ330is generally limited by the capacity of the LSQ330, such that any memory access instruction that would increase the LSQ size to exceed the LSQ capacity may cause a processor stall.

To minimize the cost of tracking the LSQ330, the program's execution may be divided into time windows, which may have a fixed size, such that each time window covers the same amount of time. In some embodiments, a time window may be defined based on cycles, such as processor cycles. For example, and not by way of limitation, each time window may cover a thousand cycles. Using time windows, the scheduling system100may avoid tracking the size of the LSQ330(i.e., the number of outstanding memory access instructions) at every single cycle, and may instead ensure that no more than QC memory access instructions are pending within each time window. As a result, the computational cost of the scheduling system100may be reduced dramatically, at the price of decreased fidelity, as compared to an embodiment that checks the current LSQ size at every cycle. As the time window decreases to as few as a single cycle in the extreme case, the fidelity increases along with the computational cost. Analogously, as the time window increases, the fidelity decreases along with the computational cost. Thus, the scheduling system100may select a time window size that provides a reasonable amount of fidelity for reasonable computational cost.

If the scheduling system100detects an overuse of the LSQ330(i.e., the number of memory access instructions issued and not completed exceeds the capacity QC of the LSQ330), memory access instructions that would otherwise have been added to the LSQ330may be scheduled to a time window when space in the LSQ330is available. Scheduling a memory access request may include postponing it to a later time window than the time window currently being examined, or advancing it to a previous time window. Because the schedule of memory access instructions is determined by the scheduling system100at compile-time, it may be possible to not just postpone an instruction, but also to move it to an earlier point. During time windows when the LSQ330is full, the scheduling system100may schedule arithmetic instructions, which do not require use of the LSQ330. In this manner, the processor310may perform useful work, which may avoid stalls, increase processor utilization, and improve overall program performance.

Suppose each instruction I has a length SI, where the length of an instruction is the number of iterations or dynamic instances of the instruction that will be issued for execution. When an instruction begins issuing, all its iterations are issued consecutively. While the length SIof a memory access instruction might be 1, the length will typically be larger than 1 on a single instruction multiple data (SIMD) or vector architecture. Further, suppose a memory access instruction I has an estimated latency of LIcycles. Thus, if the instruction I is scheduled at time T, it may be estimated that the instruction will remain on the LSQ330from time T until time T+SI−1+LI−1.

The latency of memory access instructions may be variable. However, the scheduling system100may estimate the latency of the instruction I, and may use this estimated latency as the value of LI. Various existing techniques may be used to estimate latency. These techniques may include, for example, one or more of: allowing a user to specify access latency of a memory data structure; estimating based on instruction type (e.g., update form instructions are more predictable than gather instructions); estimating based on access mechanism (e.g., sequential or random); estimating based on the memory address being accessed (e.g., instructions that access the local memory return faster than those that access remote memories); and estimating based on historical program execution traces.

To test the appropriateness of issuing an instruction I at a time T, the scheduling system100may determine whether the instruction I will cause an overuse of the LSQ330at any time window in the above time span of T through T+SI−1+LI−1. Example pseudocode representing this test of appropriateness, IsLSQFull( ), follows below, where a return value of True indicates that the LSQ330is too full to handle addition of the instruction I at time T.

As shown in the pseudocode, the scheduling system100may determine whether, at any given time in the time span of T through T+SI−1+LI−1, the outstanding memory access instructions would exceed the capacity QC of the LSQ330if one additional instruction (i.e., the instruction I) were added to the LSQ330. If adding this additional instruction would cause the number of outstanding memory access instructions (i.e., the LSQ size) to exceed the capacity of the LSQ330, then the scheduling system100may determine that the LSQ330is too full to accept the instruction I at time T. Otherwise, the scheduling system100may determine that it would be appropriate to issue the instruction I at time T without overusing the LSQ330.

When the scheduling system100identifies a suitable time T for issuing the instruction I, the scheduling system100may update the array ISU to indicate that an additional memory access request is included for the time span T through T+SI−1+LI−1. Example pseudocode for this updating is as follows:

When scheduling a particular instruction, the scheduling system100may consider only legal time windows for that instruction. Some instructions may depend on others having already been executed, and thus, an instruction may be legally scheduled only after its dependencies have been satisfied.

Determining which time windows are legal may be performed in various ways. For example, and not by way of limitation, for each time window T, the scheduling system100may have a work list of schedulable instructions from which it can choose a limited number to schedule at that time window, depending on the status of the LSQ330. If there are no instructions in the work list or if the LSQ330is full at the time window, the scheduling system100may schedule no instructions at that time. As discussed above, the scheduling system may estimate that a memory access instruction added to the LSQ330at time T will leave the LSQ330at time TE=T+SI−1+LI−1. Thus, at the time window following TE, the scheduling system100may add to the work list instructions that depend on the completed instruction.

In some embodiments, to ensure the legality of instruction scheduling, the scheduling system100may track a time-varying set of schedulable instructions as well as the time-varying status of the LSQ330. In some embodiments, this may be achieved by maintaining a schedulable array SB as well as the status array ISU. It will be understood, however, that other mechanisms for tracking schedulable instructions and the LSQ status may be used. In some embodiments, the schedulable array may store, for each time window T, a list of instructions that can be scheduled as early as that time window. As instructions are scheduled, both these arrays SB and ISU may be updated accordingly. The status array ISU may be updated to indicate, at each given time window, the current size of the LSQ330. The schedulable array SB may be updated to include, in the first time window after the termination time of an instruction that was just scheduled, the instructions dependent on the instruction that was just scheduled.

In this example, for the sake of simplicity, the scheduling system100may step through the work list and attempt to schedule instructions in chronological order. However, it will be understood that the scheduling system100need not attempt to schedule instructions in chronological order. When the scheduling system100begins scheduling instructions in chronological order, it may do so by handling the instructions that are schedulable at the zeroth time window. At this time window, the scheduling system100may schedule any instructions currently in the schedulable list SB[0], which may be initialized to include only instructions that have no dependencies. The scheduling system100may select an instruction from this work list, identify an appropriate time window for the instruction, and schedule the instruction at that time window.

To identify an appropriate time window for an instruction, the scheduling system100may examine some or all time windows at which the instruction may be legally scheduled. From these time windows, the scheduling system100may determine one or more appropriate time windows for which, if the instruction were scheduled at that time window, the LSQ330would not be overused. In some embodiments, the scheduling system100may select the first time window identified as appropriate for each instruction, but it will be understood that other mechanisms may be used to determine which appropriate time window to select if more than one appropriate time window is identified. Example pseudocode for selecting a time window at which to schedule an instruction I follows below.

If no time window T is deemed appropriate for adding a certain instruction in the work list to the LSQ330, then the scheduling system100may schedule the instruction in any legal time window, for example, the time window with the lowest count of outstanding memory access instructions on the LSQ330. It will be understood, however, that in this case, it is likely that instruction I will result in a processor stall.

After the termination time TE=T+SI−1+LI−1 of the newly scheduled instruction I, all instructions dependent on the scheduled instruction I (and not dependent on any instructions that have not yet terminated by time TE) may be added to the schedulable array at the first time window after TE. Thus, when the program time is broken into time windows of length w, these dependent instructions may be added to the schedulable array at SB[ceiling((TE+1)/w)]. In other words, these dependent instructions may become schedulable after the estimated completion of the newly scheduled instruction I.

The scheduling system100may schedule the remainder of the instructions in the zeroth time window's work list. It will be understood that, although a set of instructions are in the work list at the zeroth time window, not all of such instructions need be scheduled for issuance at the zeroth time window. Rather, some or all of these instructions may be scheduled for issuance at later time windows.

After scheduling the instructions in the zeroth time window's work list, the scheduling system100may move forward to address the work list of the first time window, which follows the zeroth time window. At the first time window, instructions in the schedulable list SB[1] may be added to the work list, because the dependencies of these instructions have been met. Once again, the scheduling system100may schedule the instructions in the work list, and may then advance to the work list of the next time window. It will be understood that the scheduling system100may continue stepping through the time windows until all memory access and arithmetic instructions are scheduled. Further, as needed, the scheduling system100may backtrack and modify the time window assignments of instructions in an attempt to optimize the resulting schedule.

The scheduling system100may schedule arithmetic instructions based on the fact that each processor core is capable of doing some work during each cycle. According to this disclosure, arithmetic instructions are instructions that do not require a memory access. For example, the data needed for an arithmetic instruction may already be in the applicable processor core's registers. In contrast to memory access instructions, the latency of arithmetic instruction is fixed. Based on the scheduling discussed above, it may be determined which processor cycles are used for performing memory access instructions. Simultaneously with scheduling memory access instructions, the scheduling system100may schedule arithmetic instructions as needed to cover each processor core's remaining processor cycles. Specifically, for example, arithmetic instructions may be scheduled to use processor cycles during time windows for which the LSQ330would become overused if a memory access instruction were to be scheduled.

After every instruction of a program's code has been scheduled, a compiler using the scheduling system100may generate code according to the resulting schedule. In some embodiments, this code may avoid or reduce processor stalls as compared to conventional schedulers.

FIG. 4is a flow diagram of a method400of scheduling instructions of a program, according to some embodiments of this disclosure. As shown, at block410, an instruction may be selected from a work list. At block420, the scheduling system100may identify a time window at which the selected memory access instruction may be legally scheduled. At decision block430, if the instruction is a memory access instruction, the scheduling system100may determine whether scheduling the memory access instruction at that identified time window would lead to overuse of the LSQ330. If overuse would occur, that time window may be deemed inappropriate for scheduling that instruction, and at block420, the scheduling system100may choose another legal time window to evaluate for appropriateness. Instead, an arithmetic instruction, if available, may be scheduled at the time window that would have an overuse of the LSQ330. If overuse would not occur, then at block440, the scheduling system100may schedule the instruction at the chosen time window. At block450, other instructions whose dependencies will be met by execution of the instruction may be added to the work list for scheduling in a time window after completed execution of the instruction. At decision block460, the scheduling system100may determine whether all instructions have been scheduled. If not, another instruction may be selected from the work list at block410. If all instructions have been scheduled, the scheduling system100may end the scheduling method400at block470. It will be understood that many variations of this method400may be used, according to various embodiments of this disclosure.

FIG. 5illustrates a block diagram of a computer system500for use in implementing a scheduling system or method according to some embodiments. The scheduling systems and methods described herein may be implemented in hardware, software (e.g., firmware), or a combination thereof. In an exemplary embodiment, the methods described may be implemented, at least in part, in hardware and may be part of the microprocessor of a special or general-purpose computer system500, such as a personal computer, workstation, minicomputer, or mainframe computer.

In an exemplary embodiment, as shown inFIG. 5, the computer system500includes a processor505, memory510coupled to a memory controller515, and one or more input devices545and/or output devices540, such as peripherals, that are communicatively coupled via a local I/O controller535. These devices540and545may include, for example, a printer, a scanner, a microphone, and the like. A conventional keyboard550and mouse555may be coupled to the I/O controller535. The I/O controller535may be, for example, one or more buses or other wired or wireless connections, as are known in the art. The I/O controller535may have additional elements, which are omitted for simplicity, such as controllers, buffers (caches), drivers, repeaters, and receivers, to enable communications.

The processor505is a hardware device for executing hardware instructions or software, particularly those stored in memory510. The processor505may be a custom made or commercially available processor, a central processing unit (CPU), an auxiliary processor among several processors associated with the computer system500, a semiconductor based microprocessor (in the form of a microchip or chip set), a macroprocessor, or other device for executing instructions. The processor505includes a cache570, which may include, but is not limited to, an instruction cache to speed up executable instruction fetch, a data cache to speed up data fetch and store, and a translation lookaside buffer (TLB) used to speed up virtual-to-physical address translation for both executable instructions and data. The cache570may be organized as a hierarchy of more cache levels (L1, L2, etc.).

The memory510may include one or combinations of volatile memory elements (e.g., random access memory, RAM, such as DRAM, SRAM, SDRAM, etc.) and nonvolatile memory elements (e.g., ROM, erasable programmable read only memory (EPROM), electronically erasable programmable read only memory (EEPROM), programmable read only memory (PROM), tape, compact disc read only memory (CD-ROM), disk, diskette, cartridge, cassette or the like, etc.). Moreover, the memory510may incorporate electronic, magnetic, optical, or other types of storage media. Note that the memory510may have a distributed architecture, where various components are situated remote from one another but may be accessed by the processor505.

The instructions in memory510may include one or more separate programs, each of which comprises an ordered listing of executable instructions for implementing logical functions. In the example ofFIG. 5, the instructions in the memory510include a suitable operating system (OS)511. The operating system511essentially may control the execution of other computer programs and provides scheduling, input-output control, file and data management, memory management, and communication control and related services.

Additional data, including, for example, instructions for the processor505or other retrievable information, may be stored in storage520, which may be a storage device such as a hard disk drive or solid state drive. The stored instructions in memory510or in storage520may include those enabling the processor to execute one or more aspects of the scheduling systems and methods of this disclosure.

The computer system500may further include a display controller525coupled to a display530. In an exemplary embodiment, the computer system500may further include a network interface560for coupling to a network565. The network565may be an IP-based network for communication between the computer system500and an external server, client and the like via a broadband connection. The network565transmits and receives data between the computer system500and external systems. In an exemplary embodiment, the network565may be a managed IP network administered by a service provider. The network565may be implemented in a wireless fashion, e.g., using wireless protocols and technologies, such as WiFi, WiMax, etc. The network565may also be a packet-switched network such as a local area network, wide area network, metropolitan area network, the Internet, or other similar type of network environment. The network565may be a fixed wireless network, a wireless local area network (LAN), a wireless wide area network (WAN) a personal area network (PAN), a virtual private network (VPN), intranet or other suitable network system and may include equipment for receiving and transmitting signals.

Scheduling systems and methods according to this disclosure may be embodied, in whole or in part, in computer program products or in computer systems500, such as that illustrated inFIG. 5.

Technical effects and benefits of some embodiments include the ability to schedule instructions based on tracking the size of the LSQ130, thereby reducing the number of stalls resulting from the LSQ130becoming full. Using conventional schedulers, compilers attempt to issue memory access instructions as soon as dependencies for those instructions are resolved, to enable covering as much of the memory latency as possible. However, there are processor microarchitectures in which this aggressive issue of memory access instructions can lead to performance degradation and processor stalls. Some embodiments of this disclosure can avoid such processor stalls.