Inventors: Steven C. Woo, Trung A. Diep and Michael T. Ching

Technical Field

[0001] The disclosed embodiments generally relate to the design of memory systems for computers. More specifically, the disclosed embodiments relate to the design of a memory system that provides adaptive time -multiplexing for memory references received from multiple processor cores.

Background

[0002] Recent advances in computing technology have enabled computer system designers to efficiently integrate multiple processor cores into a single chip. At present, dual- core processor systems are commonplace, and quad-core processor systems are going to dominate in the next couple of years. Extrapolating forward several years, the technology roadmap for virtually every processor manufacturer indicates significant growth in the number of processor cores in computer systems. Hence, computer systems are likely to include 64, 128, 256, or even 512 processor cores in the not-too-distant future.

[0003] However, as larger numbers of processor cores attempt to access a computer's memory system, conflicts are likely to arise. More specifically, because processor cores generally run different programs, their memory reference patterns are generally uncorrected. This lack of correlation is not a problem for computer systems that have a small number of processor cores and a large number of memory banks, because the likelihood of two or more processor cores accessing the same memory banks is small on average when the number of banks is much larger than the number of processor cores. Hence, references from a given processor core are unlikely to encounter open pages from another processor core. The rows which are accessed by a given processor core are likely to be already open to service preceding references from the given processor core, which means that memory references are likely to generate page- hits.

[0004] However, as the number of processor cores increases, the number of software threads is likely to increase proportionately, and with more threads comes more interference. The likelihood of a thread interfering with another thread is likely to increase significantly with the number of threads for a given number of banks in the memory system. For example, instead of keeping a page open to service multiple column accesses from the same processor core to take advantage of spatial locality in reference streams, an access from another processor core can disrupt the memory access stream and cause the page to be closed and a new page to be opened. These additional page operations cause additional precharge and activate operations, and can lead to wasted power and lower efficiency for the memory system.

BRIEF DESCRIPTION OF THE FIGURES

[0005] FIG. 1 illustrates an example of how memory references from multiple processor cores are processed in accordance with the disclosed embodiments.

[0006] FIG. 2 illustrates another example of how memory references from multiple processor cores are processed in accordance with the disclosed embodiments.

[0007] FIG. 3 illustrates how processor cores can be coupled into a ring topology in accordance with the disclosed embodiments.

[0008] FIG. 4 presents a flow chart illustrating how memory references are processed in accordance with the disclosed embodiments.

DETAILED DESCRIPTION

Time-Multiplexing

[0009] The disclosed embodiments provide a scalable solution which improves memory system power and performance by increasing the locality in the memory reference stream as seen by the system memory controller. During the course of execution, a program often exhibits varying amounts of spatial and temporal locality. When multiple programs are running in parallel, while each program may exhibit its own spatial and temporal locality, when their respective memory reference streams reach the memory controller, the mixing of the memory reference streams can cause spatial and temporal locality to be severely reduced. Hence, to improve overall memory reference stream locality, the memory controller can time-multiplex access to the memory system between processor cores when the overall memory reference stream exhibits a lack of locality. This time-multiplexing allows the memory controller to issue multiple memory references from one processor core back-to-back, thereby utilizing the processor core's locality to improve overall memory system power consumption and performance. This technique sometimes adds latency to references from different cores, but there is typically less latency for consecutive references from a given processor core.

[0010] For example, FIG. 1 illustrates a system which includes 64 processor cores (coreO, ..., core63) and memory devices that include memory banks. FIG. 1 also illustrates a number of memory references in which each memory reference is associated with a specific originating core, bank, row and column. For example, the memory reference which appears immediately under core 0 is labeled "CoreO, BankO, RowO and Coll". This memory reference also appears in the queue for bank 0 with the abbreviated label "CO, BO, R0, CI," wherein "CO" represents core 0, "BO" represents bank 0, "R0" represents row 0 and "CO" represents column 0.

[0011] In this example, the processor cores (coreO, ..., core63) send their memory references to a memory controller 104. Memory controller 104 receives these references through a processor interface 105 and forwards the memory references to respective queues for the eight memory banks (bankO, ... , bank7) and then to the eight memory banks through a memory interface 107. In one embodiment, the memory controller and processor cores are all

implemented as functional circuit blocks on a single chip or integrated circuit device. The memory devices, for example dynamic random access memory devices, can be single chip devices that include memory cells organized as banks. Alternatively the memory banks can be integrated on a single chip along with the processor cores and the memory controller. In another embodiment, the processor cores, memory controller and memory devices are implemented on separate chips. Separate chip implementations can be housed or packaged in a stacked

configuration, for example by using through silicon vias, and can be encapsulated in a single package housing. Because there are 64 processor cores and eight memory banks, memory references from different processor cores are likely to interfere with each other at the memory banks. The stream of references from coreO accesses bankO and bankl, while the stream of references from core63 accesses bank6 and bank7. However, in this example, because there exist a large number of intervening memory references from other processor cores, each memory access encounters an open page associated with another processor core, which causes a page- miss.

[0012] FIG. 2 illustrates another example in which time-multiplexing has been activated in a system such as the one illustrated in FIG. 1. The system in FIG. 2 also includes 64 processor cores (coreO, ..., core63) and eight memory banks (bankO, ..., bank7). When time-multiplexing is activated, each processor core is able to issue a block of memory references consecutively. These blocks of consecutive memory references typically have some amount of locality, so these accesses tend to generate more page-hits. In particular, the first access to page may generate a page-miss, but subsequent accesses to the same page by the same processor core will generate page-hits. This increased hit rate reduces the number of precharge and activate operations, which saves power and can possibly increase performance.

[0013] To optimize the performance of this technique, it is important to be able to determine when to start and end the time-multiplexing. To accomplish this, the system can augment each memory request sent from a processor core to the memory controller with a hint

(on the order of a couple of additional bits) that indicates whether the transaction would have been a hit, a miss, or an empty-access had the initiating core been the only requestor in the computer system. These hints can be generated by maintaining a storage structure in each processor and/or processor core that tracks the state of the accessed pages as if the processor core were the only processor core in the system. (Note that this structure is different from, and in addition to, a similar structure located in the memory controller.)

[0014] Next, the memory controller compares these hints against the actual transactional results to determine if hits and empty-accesses are being turned into misses because of interference from memory references from other processor cores. If too many hits and empty- accesses at the individual processors/cores/threads are being turned into misses, the memory controller can switch to time-multiplexing. It is important to note that, even though in some situations these hints may adversely affect performance, they do not affect correctness.

[0015] Also, instead of generating the hints at the processor cores, the queues and other circuitry involved in generating the hints can alternatively be incorporated into the memory controller. However, this can lead to a prohibitively large and complex memory controller that does not scale well with the number of processor cores, and which can become a bottleneck to performance. The hints attached to the memory references can also include a suggestion about whether or not to precharge the page after a memory reference completes.

[0016] Processor cores can be notified to switch into time-multiplexing mode via a number of possible communication mechanisms, such as tokens or direct messages from the memory controller. For example, in a token-based system, possession of a token by a processor core indicates that it is the processor core's turn to issue memory references. If the processor core does not have any references to issue, the processor core can pass the token to another processor core. Tokens can be communicated efficiently through a simple processor-core interconnection topology, such as a ring.

[0017] Tokens can also communicate different types of information between the memory controller and the cores. Examples include when to turn multiplexing on and off, when to time- multiplex a subset of banks (and not the entire memory system), and when to enforce time- multiplexing for a subset of cores. Decisions on when to turn on multiplexing, which banks to time multiplex, etc. can be made based on hints such as those described above, or based on additional information, such as the depth of occupancy of the memory bank queues at the memory controller. Note that these tokens provide a framework in which information about the memory controller can be used by the processor cores and vice versa. Conventionally, memory systems have provided only one-way communication from the processor cores to the memory controller, with no communication coming back the other way.

[0018] Tokens and memory references can also be used to communicate priority information. For example specific threads and associated memory references can be identified as being "high-priority" to ensure a high Quality of Service (QoS). For example, high-priority references can be allowed to issue without stalling, and a high-priority thread can be allowed to issue a larger block of consecutive references than a lower-priority thread.

[0019] Moreover, the tokens or messages passed to the processor cores can also include information specifying the number of consecutive references that can be issued by a core. In this way, the number of consecutive memory references that each processor core can issue to the memory controller can be increased or decreased (within user-defined limits) depending upon how well the processed memory references match the hints from the processor cores. When a small number of hits/empty-accesses are being turned into misses, or if average latency is being negatively impacted by time-multiplexing, the degree of time -multiplexing can be reduced (fewer consecutive references per core), or time-multiplexing can be terminated.

Ring Topology

[0020] FIG. 3 illustrates an exemplary ring topology for a multi-core processor system in accordance with the disclosed embodiments. (Note that a ring topology is only one of a number of possible interconnect topologies. In general, other interconnection topologies can also be used.) This ring topology includes a number of processor cores 310-317 which are coupled to a bidirectional ring 304. The system also includes a control processor 318 which is coupled to ring 304, wherein control processor 318 facilitates executing an operating system and various applications and also controls operation of processor cores 310-317. Ring 304 is also coupled to an I/O interface 308 to provide access to I/O devices, such as disk drives. Ring 304 is additionally coupled to a coherent interface 306, which facilitates controlling coherence among caches in the processor cores 310-317, control processor 318 and additional processor cores on a different die (not shown) that are connected through the coherent interface 306. Finally, ring 304 is also coupled to a memory controller 302, which directs memory requests from processor cores 310-317 and control processor 318 to a number of memory banks (not shown).

[0021] During operation of the computer system illustrated in FIG. 3, when the computer system is heavily loaded and memory accesses from different processor cores begin to interfere with each other, memory controller 302 initiates time -multiplexing by passing a token onto ring 304 (label A). This token first flows to processor core 310, which in response to receiving the token issues a block of consecutive memory references to memory controller 302 (label B). After processor core 310 has issued the block of consecutive memory references, it passes the token back onto the ring (label C). Next, the token flows to processor core 311, which also issues a block of consecutive memory references to memory controller 302 (label D). After processor core 311 has issued its block of consecutive memory references, it passes the token back onto the ring (label E) for the next core, and so on. The token continues to circulate around the ring to control the issuing of memory reference until memory controller 302 terminates the time -multiplexing by removing the token from the ring.

Scheduling Decisions Made by Processor Cores

[0022] The processor cores can also make certain scheduling decisions to optimize performance during time-multiplexing. For example, a given processor core can track the last open pages in each bank for its own reference stream. This enables the given processor core to determine which memory references will generate page-hits during time -multiplexing. The processor cores can also maintain their own local queues that store pending references to each memory bank. The processor cores can then search and sort the memory references in these local queues before consolidating a set of memory references to be sent to the memory controller. This additional queue space at the processor cores effectively acts like a per-bank overflow storage area that extends the list of pending references per memory bank beyond what the memory controller can store.

[0023] The preceding examples presume that all storage and scheduling decisions are made by the processor cores and the memory controller. However, a ring bus architecture often includes ring "stops" (places to enter and exit rings, as well as transfer between rings or skip ring stops), and the above-described techniques can be applied to ring stops as well. For example, memory references can be buffered in the ring stops, and tokens can be used to control access restrictions for the ring stops and/or their associated processor cores. Scheduling decisions can also be made by the ring stops in addition to (or instead of) by the cores and/or memory controller.

Latency Sensitive Requests

[0024] The above embodiments, in some aspects, relate to situations in which the memory system is heavily loaded and power consumption and bandwidth are important.

However, there are other embodiments in which the above-described techniques can be applied, for example when the memory system is less loaded and reducing latency is a more important consideration. In this case, memory references can be augmented to include a timestamp specifying when they were generated. If time-multiplexing is enabled and references can't be issued until the processor core gains possession of a token, when a memory reference is finally issued to the memory controller, the associated timestamp is examined to determine how long the reference has been delayed. If the delay is large relative to the time the memory reference spends in the memory bank queues and the memory controller, the time -multiplexing is detrimental to memory latency and it should be turned off for this bank/core. Also, if average latency becomes too high (and queues are not full), the memory controller can issue a second token to effectively cut the wait time in half.

Processing Memory References

[0025] FIG. 4 presents a flow chart illustrating how memory references are processed in accordance with the disclosed embodiments. First, each processor core determines whether memory references from the processor core would have generated a page-hit, an empty-access, or a page-miss if all memory references from the processor core were processed without

interference from other processor cores (step 402). Next, each processor core communicates a hint with each memory reference to the memory controller, wherein the hint indicates whether the memory reference would have generated a page-hit, an empty-access, or a page-miss (step 404).

[0026] Next, the memory controller uses the hints to determine whether memory references from other processor cores are causing memory references from the given processor core, which would have generated page-hits or empty-accesses, to generate page-misses, thereby indicating that memory references from different processor cores are interfering with each other (step 406). If memory references from different processor cores are interfering with each other, the memory controller starts time -multiplexing the processing of memory references between processor cores, so that a block of consecutive memory references from a given processor core is processed by the memory system before memory references from other processor cores are processed (step 408). (Note that it is also possible for the processor cores to initiate the time- multiplexing if some type of feedback mechanism is provided to enable the processor cores to learn whether the references turned out to be hits or misses. The processor cores can then compare this information with the hints they generated for the references.)

[0027] Finally, while time-multiplexing is taking place, if the rate of interference between memory references from different processor cores falls below a threshold, or if latencies for the memory references exceed a threshold and if queues containing pending references for the memory banks are not full, the memory controller can either discontinue the time-multiplexing (step 410), or reduce the degree of time-multiplexing by reducing the number of consecutive memory references a core can issue at one time.

Generalizations and Extensions

[0028] The above-described techniques relate to time-multiplexing, but they can be extended to the more general concept of controlling how and when changes are made to the mechanism by which memory references are passed from processor cores to the memory controller. Moreover, although the above-described techniques are described in the context of a computer system which includes only one memory controller, these techniques can also be applied to computer systems that have multiple memory controllers.

[0029] Also, the storage and scheduling decisions described above in the context of ring bus architectures can be extended to alternative interconnection topologies, such as a mesh or cross-connected configuration.

[0030] The preceding description was presented to enable any person skilled in the art to make and use the disclosed embodiments, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the disclosed embodiments. Thus, the disclosed embodiments are not limited to the embodiments shown, but are to be accorded the widest scope consistent with the principles and features disclosed herein.

[0031] Moreover, the methods and processes described in the detailed description section can be embodied as code and/or data, which can be stored in a computer-readable storage medium as described above. When a computer system reads and executes the code and/or data stored on the computer-readable storage medium, the computer system performs the methods and processes embodied as data structures and code and stored within the computer-readable storage medium. Furthermore, the methods and processes described below can be included in hardware. For example, the hardware can include, but is not limited to, application-specific integrated circuit (ASIC) chips, field-programmable gate arrays (FPGAs), system-on-chip integrated circuits and other programmable-logic devices now known or later developed. When the hardware is activated, the hardware performs the methods and processes included within the hardware modules.

[0032] The foregoing descriptions of embodiments have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the present description to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present description. The scope of the present description is defined by the appended claims.