Read around speculative load

[0002] 1. Field of the Invention

[0003] The present invention relates generally to a method of handling memory reads in a computer system and, more particularly, to a method that indicates to a computer's memory subsystem that a current read request is speculative so that the subsystem can service non-speculative read requests first.

[0004] 2. Description of the Related Art

[0005] With the ever-increasing amount of data being processed by today's computer systems, the efficient use of computer resources is very important. The processing power of computer systems is often increased by adding processors. In today's multi-processor computer systems, memory read requests are typically serviced on a first-come-first-served basis, and a processor that has issued a memory request might be paused by other requests that are ahead of it in the memory subsystem. The memory subsystem can be a bottleneck in processing speed because the memory subsystem's physical devices typically operate more slowly than a computer's processor or because multiple processors are using the same memory subsystem. To address this concern many processors issue read requests before data is actually needed and often even before it is known whether the data will ever be needed. An example of this occurs when a processor approaches a branch. Not knowing which path of a program will be executed, a processor may request the data necessary for both paths so that the program, when it reaches the branch, can continue regardless of the path chosen. This typically helps the performance of a processor in a single processor system, but in a multiple processor system memory bandwidth is limited and these extra requests can hurt the performance of other processors in the system. Being able to cancel unneeded memory cycles in that case would be particularly beneficial.

[0006] Another example of a processor performing operations that are speculative is when a processor, such as the PENTIUM® Pro manufactured by the Intel Corporation of Santa Clara, Calif. utilizes “speculative execution.” Speculative execution is a mechanism in which the processor maintains an “instruction queue,” looks ahead in the instruction queue and performs instructions out of order rather than waiting for unread operands. The results of the out-of-order instructions are stored in an “instruction pool.” Once it is apparent that an instruction is necessary and all previous instructions in the queue have been completed, the results stored in the instruction pool are committed to memory, either registers, RAM, or disk. When an instruction is a branch, the processor typically makes a guess as to the most likely path. If the guess is ultimately wrong, the processor clears the unneeded instructions and results from the instruction pool.

[0007] In the speculative execution environment, a read request may also be marked speculative if it is uncertain whether the value of an operand might change after the instruction is executed but before the result is committed. In that case, the instruction needs to be re-executed with correct data before the result is committed.

[0008] Although current processors typically speculate concerning instructions and data that might be needed, current memory subsystems are designed to service memory requests in a first-come-first-served order.

[0009] In a system implemented according to the invention, a processor initiates memory read transactions on a bus, and when the read is a speculative load, the processor provides information regarding the speculative nature of the transaction. A bus device, such as a memory controller, then receives the transaction and places the request in a queue to be serviced in an order dependent upon the relative speculative nature of the request. Transactions that are “non-speculative” are serviced before transactions that are “speculative.”

[0010] In addition, the bus device, upon receipt of an appropriate signal, cancels a speculative read that is no longer needed or upgrades the priority of a speculative read that has become non-speculative. If data required for a load is not available in a computer's random access memory (RAM) or cache memory, a page fault typically occurs, resulting in a disk read. In the case of a speculative load that is ultimately cancelled, by “putting off” the speculative load, an unnecessary page fault (and the resulting disk read) might be prevented.

[0011] A better understanding of the present invention can be obtained when the following detailed description of the preferred embodiment is considered in conjunction with the following drawings, in which:

[0012] FIG. 1 is a block diagram of a computer system S according to the invention showing peripheral devices and data/address buses;

[0013] FIG. 2 is a portion of FIG. 1 showing the computer system S with multiple processors;

[0014] FIG. 3 is a block diagram of software running on the computer system S illustrating speculative and non-speculative reads; and

[0015] FIG. 4 is a diagram of a memory request queue showing a non-speculative memory request being inserted into a memory request queue ahead of speculative memory requests.

[0016] Turning to FIG. 1, illustrated is a typical computer system S implemented according to the present invention. The computer system S in the illustrated embodiment is a PCI bus based machine, having a peripheral component interconnect (PCI) bus 10. The PCI bus 10 is controlled by PCI controller circuitry located within a memory/accelerated graphics port (AGP)/PCI controller 14. This controller 14 (the “host bridge”) couples the PCI bus 10 to a processor 30, random access memory (RAM) 18 and a disk memory subsystem 20. The processor 30 includes a microprocessor a level two (L2) cache 34.

[0017] The host bridge 14 in the disclosed embodiment is a 440LX Integrated Circuit by Intel Corporation, also known as a PCI AGP Controller (PAC). The processor 30 is preferably a PENTIUM® Pro, manufactured by the Intel Corporation of Santa Clara, Calif. The processor 30 could be replaced with a different processor, other than the PENTIUM® Pro, without detracting from the spirit of the invention.

[0018] The PCI bus 10 couples a variety of devices that generally take advantage of a high-speed data path. This includes a network interface controller (NIC) 42, which preferably supports the ThunderLan™ power management specification by Texas Instruments, and a floppy disk drive 74. The floppy disk drive 74 preferably would be a 3½″ floppy disk. A video display 82, a mouse 70, and a keyboard 68 can also be coupled to the host bridge 14, enabling human interaction with the computer system S.

[0019] Finally, SCSI host adapter 36 is shown connected to the PCI bus 10. Connected to the SCSI host adapter 36 by means of a SCSI bus 50 are two SCSI devices 38 and 40. The SCSI device 38 might be an internal device such as a CD-ROM drive or a tape drive. For the purposes of this example, the SCSI device 40 might be an external disk array.

[0020] The computer system S illustrates only one platform in which the system according to the present invention can be implemented. The disclosed techniques can, without distracting from the spirit of the invention, be implemented in many systems that contains a memory subsystem, regardless of whether the device contains less, additional, or different components than the system in FIG. 1.

[0021] Turning to FIG. 2, illustrated is a portion of the computer system shown in FIG. 1 but which contains multiple processors 29, 30, and 31 with L2 Caches 33, 34, and 35 respectively. The processors 29, 30, and 31 are each connected to their own host buses 101, 102, and 103 respectively, which in turn connect to the PCI bus 10. A random access memory (RAM) 18 serves all of the processors 29, 30, and 31.

[0022] Turning to FIG. 3, illustrated is block diagram of a section of software 300 that runs on the computer system S and is in the processor's 30 instruction queue. A processor 30 may execute an instruction 301 generated by an application 451 (see FIG. 4). If the data necessary to process the instruction 301 is not yet loaded, the processor 30 would typically look ahead for instructions that can be performed immediately or data that may be needed eventually. In this example, an instruction 302 may need data that does not depend upon the result of the processing of the instruction 301. In that case, the processor 30 would issue a non-speculative load, or read, request. Although in this example read requests are serviced from the RAM 18, data necessary to service a read request may be located in the computer system's RAM 18, hard disk memory 20, registers or the L2 cache 34. The disclosed techniques apply wherever data is located in the memory sub-system.

[0023] Also in the processor 30 instruction queue is a branch 303. The processor 30 might request data from memory 20 to service instructions following the branch 303 while (or before) instruction 301 is executing. Upon processing the branch 303 from memory 20, the processor 30 can determine that there are two possible paths the application 451 can follow, a Yes path and a No path. Not knowing whether the application 451 will eventually take the Yes path or the No path, the processor 30 when implementing speculative loads would typically submit a read request for any data needed by both the instruction 304 and the instruction 305 in spite of the uncertainty of whether they will ultimately be processed. In this example, regardless of which path, Yes or No, is taken, an instruction 305 will be executed by the processor 30. In accordance with the present invention, the data for instruction 304 would be requested from memory with a status of speculative.

[0024] The data necessary for instruction 305 would typically be requested from memory with a status of speculative as well. This is because the instruction 305 is one possibility of a branch, and the processor 30 will typically simply label both paths as speculative, even though it turns out that the instruction 305 will always be executed. The processor 30, however, could be intelligent enough to look ahead and see that the instruction 305 will always be executed and that the data required does not depend upon previous, unexecuted instructions. In that case that data can be initially requested with a status of speculative because it is not needed immediately. Later, if the memory subsystem never has the bandwidth to fetch the data, then the request can be upgraded to non-speculative. The point is that the data (the program code for instruction 305) will definitely be needed but giving it too high of a priority can place it in front of items that will be needed sooner.

[0025] In another embodiment, the instruction set of the processor 30 could be such that a compiler could predetermine the speculative or non-speculative native of the transaction 305 and pass that information to the processor 30, such as with a bit encoded in the instruction. Either way, the processor 30 labels some transactions as speculative and some as non-speculative.

[0026] In a further embodiment, an additional status of “needed, but not right now” can be used. The branch prediction logic inside the processor 30 can use this status, for example. The branch prediction logic “knows” the processor 30 is going to loop several more times, but eventually will definitely need the subsequent instruction after the loop. Preferably, the branch prediction logic would wait until the loop was near termination to issue the “needed, but not right now” memory references or requests.

[0027] When the application 451 reaches the branch 303, there are several possibilities. The first possibility is that the memory requests for both instructions 304 and 305 have been completed. In that case, the application 451 can proceed down either the Yes or No path without delay. A second possibility is that only one memory request has been completed. According to the present invention, the memory request for instruction 305 is processed by the memory controller 14 first if it is determined to be a non-speculative memory request because a non-speculative request takes precedence over a speculative request, like the request for instruction 304. If the processor 30 chooses the Yes path, a memory request is sent requesting that the memory controller 14 update the memory request for instruction 304 from speculative to non-speculative. If the processor 30 chooses the No path, the processor 30 can send a memory request requesting that the memory request for instruction 304 be cancelled and the application 451 can then continue execution without delay.

[0028] A third possibility is that the software can reach the branch 303 with neither memory requests for instructions 304 and 305 completed. If the Yes path is chosen, the processor 30 can send a memory request to upgrade the memory request for instruction 304 from speculative to non-speculative. If the No path is chosen, the processor 30 can send a memory request to cancel the memory request for instruction 304. In either of the two cases of the third possibility, the application 451 is suspended while it waits for the completion of the memory requests. However, in a processor 30 without the disclosed techniques, the application 451 would wait for the memory controller 14 to fetch instruction 304 even if the application 451 takes the No path and no longer requires the instruction 304.

[0029] This example is for illustrative purposes only. In an actual computer, both instructions and data are fetched from memory. Instructions would not be fetched from memory one at a time, but would instead be requested in blocks containing multiple instructions, branches, and data. In addition, multiple processes on multiple processors might be running, all requiring the processor 30 to generate memory requests. Thus whole blocks of both instructions and data might be speculative or non-speculative. The principle is the same.

[0030] Turning to FIG. 4, a processor 30 executes a portion of the software 300 of an application 451. The processor 30, while executing the application 451, initiates a memory request 421 on the PCI bus 10 and further assigns, to the memory request 421, a status 422 with the value of non-speculative. Transaction decoder logic 441 is a scheduling logic within the memory controller 14, scheduling the memory request 421 by inserting it into a memory request queue 401. To make room for the memory request 421 in the memory request queue 401, already stored memory requests 417 and 419 and their associated statuses 418 and 420 are rescheduled. An already stored memory request 419 and its associated status 420, with a value of speculative, are moved to memory request queue location 411 and status storage location 412 respectively to create space in the memory request queue 401 at location 409 and in the status storage 402 at location 410. An already stored memory request 417 and its corresponding status 418, with a value of speculative, are moved to locations 409 and 410 respectively to create a space in the queue for the received memory request 421 and its corresponding status 422, with a value of non-speculative. The received memory request 421 and its corresponding status 422 are then inserted into the memory request queue 401 and the status storage 402 at locations 407 and 408 respectively.

[0031] In another embodiment, multiple queues can be used, one for non-speculative requests and one for speculative requests. In both cases, new requests are added onto the end of the appropriate queue. The speculative queue is read only if there are no requests in the non-speculative queue. In this way, the non-speculative queue is emptied before emptying of the speculative queue. This has the added benefit of naturally limiting the number of requests a processor is making. In a single processor system, large numbers of speculative requests are typically acceptable. But in a multiprocessor system, this type of behaviour consumes memory bandwidth that is needed by the other processors for non-speculative work. Having separate queues that are prioritized can allow a graceful transition from a single processor system to a multiprocessor system.

[0032] The memory request queue 401 is now ordered with higher priority memory requests 413 and 415, with their associated statuses 414 and 416 of values non-speculative, first and second in line to be sent to memory request processing logic 442. The processor memory request 421 and its associated status 422 of value non-speculative are next in line to be processed. The memory request 422 is followed by memory request 417 with its corresponding status 418 of value speculative and memory request 419 with its corresponding status 420 of value speculative. Typically, the processor 30 would generate the memory request 421 in an attempt to anticipate the needs of the application 451. Once the application 451 reaches a point in its execution where it needs the memory request 421, the memory request would already be completed and waiting for the application 451 in the processor's L2 cache 34. If the application 451 reaches a point in its execution where it needs the memory request 421 and the memory request 421 has not yet been completed by the memory request processing logic 442, the processor 30 might pause the application 451 and issue another memory request 421 to shorten the delay. If the memory request 421 had originally been assigned a status of speculative, the second memory request 421 would upgrade the previously stored memory request 421 from a status of speculative to non-speculative. If the processor 30 reaches a point in where it realizes that it is not going to need memory request 421, the processor 30 would generate a memory request indicating that the memory request 421 may be cancelled.

[0033] This is a logical description of the memory request insertion process; a system according to the invention could instead prioritize the memory requests in many different ways. For example, it can insert the memory request entry into any available spot in the queue and then resort the entire queue to maintain the relative ordering without changing the spirit of the invention. More preferably, the method of the disclosed technique can use pointers to memory requests and their associated statuses stored in another storage area so that, during a sort, only the pointers are changed and the memory requests and the statuses need not be moved. In addition, another embodiment can have separate queues for the processing of speculative and non-speculative memory requests. The memory controller 14 can process all requests in the non-speculative queue before servicing any requests from the speculative queue. Similarly, separate queues are often provided for code and data—these, too, can have associated speculative/non-speculative status or separate speculative/non-speculative queues. A further embodiment which uses a “needed, but not right now” status can employ a third queue.

[0034] Further, it also is not critical how the status is transmitted in conjunction with the bus transaction. The techniques according to the invention can be implemented in a variety of ways. For example, the embodiment of FIG. 3 illustrates a multiplexing of the priority with the transaction so that they are delivered sequentially over a single bus. In an alternative embodiment, a separate “status bus,” which delivers the status simultaneously with the memory request, can be used. Further, a “change current status” command can instead be transmitted to adjust the status of an already stored memory request. A “delete memory request” command can be transmitted to prevent a memory request that is no longer needed from being processed. Whatever the technique, transmission of a memory request, associated with status information, allows a device, such as the memory controller 14, to more effectively process memory requests. By prioritizing memory requests over a bus based on status information, memory bandwidth can be more effectively utilized.

[0035] In one embodiment, a counter is associated with each request on a queue. Multiple processors can request the same memory cycle, resulting in a queue element with a counter greater than one. If a processor cancels its request, the counter is decremented. As long as the counter is positive, the request is still active for at least one processor and remains in the queue. If the counter becomes zero, the request has been cancelled by all requesting processors, and the queue element can be removed. In this embodiment, requests in a given queue can be prioritized based on the counter value, which indicates how many processors will benefit from the memory cycle when it completes.

[0036] The foregoing disclosure and description of the invention are illustrative and explanatory thereof, and various changes in the size, shape, materials, components, circuit elements, wiring connections and contacts, as well as in the details of the illustrated circuitry and construction and method of operation may be made without departing from the spirit of the invention.