Buffer allocation for split data messages

A technique to store a plurality of addresses and data to address and data buffers, respectively, in an ordered manner. More particularly, one embodiment of the invention stores a plurality of addresses to a plurality of address buffer entries and a plurality of data to a plurality of data buffer entries according to a true least-recently-used (LRU) allocation algorithm.

FIELD OF INVENTION

Generally, embodiments of the invention relate to integrated electronics and integrated electronics systems. More specifically, one embodiment of the invention relates to a technique to match a message's address and data portions sent separately across an interconnect.

BACKGROUND

In a microprocessor or other electronics device within a computer system, various logic circuits, such as processing cores, may request data from other logic circuits within or outside of the microprocessor or computer system, which may be stored, at least temporarily, within the requesting logic circuit's cache memory for the logic circuit to use. Accordingly, requesting logic circuits and other electronic devices may be referred to as “cache agents”.

Cache agents may communicate with other cache agents or semiconductor devices within a computer system by transmitting messages across an interconnect, such as a point-to-point (P2P) network. Messages may include a data portion and an address portion, which identifies a target recipient of the data portion. Furthermore, the data portion and address portion of the messages may be sent by cache agents along different communication paths, or “channels”. For example, within a multi-core processor (a processor having more than one logic to process instructions), cache agents may transmit data and corresponding address information within the multi-core processor along separate communication paths before the address and data combine into a single message to be transmitted to a target recipient located inside or outside of the multi-core processor.

Because data and addresses transmitted by a cache agent may traverse communication paths of different lengths and delay characteristics, there may be no guarantee that the proper address will be transmitted within a single message with the proper data to which the address corresponds. Furthermore, the problem is exacerbated as more cache agents transmit data and address information along the same two communication paths before being combined and transmitted to a target recipient.

FIG. 1, for example, illustrates an arrangement of cache agents in which the data transmitted by each cache agent traverses a data network communication path and in which the addresses transmitted by each cache agent traverse an address network communication path before being combined into a single message to be transmitted to a target recipient. The cache agents ofFIG. 1may be within a multi-core processor, for example, and the merge block may be an interface to a network of devices within a computer system interconnected by a shared bus or point-to-point interconnect.

If the proper data and corresponding addresses are not properly combined when transmitted in a message to a target recipient, the wrong target recipient may receive the data, which can result in system errors.

DETAILED DESCRIPTION

Embodiments of the invention disclosed herein describe an address and data matching technique that may be used in an electronic device, such as a single core or multiple core microprocessor, or an electronics system, such a shared bus computer system or a point-to-point (P2P) bus computer system. More particularly, one embodiment of the invention describes an architecture, in which data and address transmitted by a cache agent are properly combined into a message before being delivered to a target recipient indicated by the address.

In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the claimed subject matter. However, it will be understood by those skilled in the art that the claimed subject matter may be practiced without these specific details. In other instances, well-known methods, procedures, components and circuits have not been described in detail so as not to obscure the claimed subject matter.

In at least one embodiment of the invention, address and data information transmitted by a cache agent or cache agents along different communication paths before being combined into a message to be delivered to a target recipient device are properly paired within the message by storing the address and data within an address and data buffer, respectively, whose entries are allocated according to a true least-recently used (LRU) resource allocation technique, wherein, in at least one embodiment, address and data buffer resources may be allocated based, at least in part, upon entry resources that have been least-recently deallocated. In one embodiment, in particular, one of three entries of an address and data buffer group corresponding to a particular cache agent is to store newly received address and data information, respectively, according to a true LRU resource allocation algorithm, wherein, in at least one embodiment, a least-recently de-allocated one of the three address and data buffer group entries is allocated to the newly received address or data information, respectively. In one embodiment, each of the three entries are contained within separate buffer circuits, whereas in other embodiments, each of the three entries are contained within the same buffer circuit that has been partitioned (logically or physically) according to the number of cache agents.

Embodiments of the invention may be implemented in a variety of electronic devices and logic circuits. Furthermore, devices or circuits that include embodiments of the invention may be included within a variety of computer systems, including a point-to-point (p2p) computer system and shared bus computer systems. Embodiments of the invention may also be included in other computer system topologies and architectures.

FIG. 2, for example, illustrates a front-side-bus (FSB) computer system in which one embodiment of the invention may be used. A processor205accesses data from a level one (L1) cache memory210and main memory215. In other embodiments of the invention, the cache memory may be a level two (L2) cache or other memory within a computer system memory hierarchy. Furthermore, in some embodiments, the computer system ofFIG. 2may contain both a L1 cache and an L2 cache.

Illustrated within the processor ofFIG. 2is one embodiment of the invention206. The processor may have any number of processing cores. Other embodiments of the invention, however, may be implemented within other devices within the system, such as a separate bus agent, or distributed throughout the system in hardware, software, or some combination thereof.

The main memory may be implemented in various memory sources, such as dynamic random-access memory (DRAM), a hard disk drive (HDD)220, or a memory source located remotely from the computer system via network interface230containing various storage devices and technologies. The cache memory may be located either within the processor or in close proximity to the processor, such as on the processor's local bus207.

Furthermore, the cache memory may contain relatively fast memory cells, such as a six-transistor (6T) cell, or other memory cell of approximately equal or faster access speed. The computer system ofFIG. 2may be a point-to-point (PtP) network of bus agents, such as microprocessors, that communicate via bus signals dedicated to each agent on the PtP network. Within, or at least associated with, each bus agent may be at least one embodiment of invention206, Alternatively, an embodiment of the invention may be located or associated with only one of the bus agents ofFIG. 2, or in fewer than all of the bus agents ofFIG. 2.

Similarly, at least one embodiment may be implemented within a point-to-point computer system.FIG. 3, for example, illustrates a computer system that is arranged in a point-to-point (PtP) configuration. In particular,FIG. 3shows a system where processors, memory, and input/output devices are interconnected by a number of point-to-point interfaces.

The system ofFIG. 3may also include several processors, of which only two, processors370,380are shown for clarity. Processors370,380may each include a local memory controller hub (MCH)372,382to connect with memory32,34. Processors370,380may exchange data via a point-to-point (PtP) interface350using PtP interface circuits378,388. Processors370,380may each exchange data with a chipset390via individual PtP interfaces352,354using point to point interface circuits376,394,386,398. Chipset390may also exchange data with a high-performance graphics circuit338via a high-performance graphics interface339. Embodiments of the invention may be located within any processor having any number of processing cores, or within each of the PtP bus agents ofFIG. 3.

Other embodiments of the invention, however, may exist in other circuits, logic units, or devices within the system ofFIG. 3. Furthermore, in other embodiments of the invention may be distributed throughout several circuits, logic units, or devices illustrated inFIG. 3.

FIG. 4illustrates an architecture, in which at least one cache agent transmits data and address information along separate networks, and in which the data and address information are then properly combined into a message to be delivered to a target recipient device, according to one embodiment of the invention.FIG. 4contains one or more cache agents401connected together via a data network405and an address network407, across which each cache agent may transmit data and address information, respectively.

Address and data may traverse different paths inFIG. 4before being combined by merge logic410and subsequently transmitted in a message to a recipient or recipients indicated by the address portion of the message. For example, address information inFIG. 4may enter a coherence ordered first-in-first-out (FIFO) buffer412from which the address information may be transmitted to dependence resolution logic414before being stored in address buffer416. In other embodiments, the address information may pass through other circuits (more or fewer than inFIG. 4) before being stored in the address buffer. Data, on the other hand, may be transmitted along the data network directly to the data buffer418. In other embodiments, the data may pass through other circuits (more or fewer than those inFIG. 4), before being stored in the data buffer. Furthermore, each cache agent may transmit address and data along the address and data networks in such a manner that multiple addresses may be in route to the address buffer concurrently and multiple data may be in route to the data buffer concurrently.

In one embodiment, the address information may be transmitted to the dependence resolution logic, which may change the order of addresses received from the address network in order to satisfy ordering dependency requirements imposed by a coherence protocol on different types of messages sharing the address network, for example. In one embodiment, the dependence resolution logic includes buffers, in which reordered addresses may be stored until a coherence protocol allows the address information to be forwarded to the address buffer. In one embodiment, address entry allocation logic420may allocate an address buffer entry prior to the address being forwarded to the address buffer or, in some embodiments, prior to the address being reordered within a buffer by the dependence resolution logic.

In some embodiments, the coherence ordered FIFO buffer may store other addresses than those to be merged with a corresponding data element. Furthermore, in some embodiments, addresses that may not be merged with a corresponding data element may be transmitted within the address network along with addresses that are to be merged with a corresponding data element through the coherence ordered FIFO and coherence resolution logic to a target destination without being allocated or stored within the address buffer.

In one embodiment, address and data are stored in entries of the address and data buffers, respectively, that have been allocated by address and data entry allocation logic420422. In other embodiments, the address and data entry allocation logic may be included within the address and data buffer circuits, respectively. In one embodiment, the address and data buffers are partitioned (logically or physically) into groups of entries, each group corresponding to a different cache agent. For example, in one embodiment, each group of entries contains three entries to be allocated to address and data coming from one of the cache agents, whereas in other embodiments, each group of entries may contain more or fewer entries than three for each cache agent.

Arbiter logic425may detect when address and corresponding data, which are to be combined into a message, are present within the address and data buffers, respectively, and subsequently enable the data and address to be passed to the merge logic (thereby deallocating the corresponding buffer entries), where the address and data may be combined into a message. In various embodiment, the arbiter logic may be implemented in software, hardware, or some combination thereof.

Entries within the address and data buffers may be allocated, in one embodiment of the invention, according to an algorithm, such as a least-recently-used (LRU) allocation technique, such that addresses stored in the address buffer will correspond to the proper data stored in the data buffer. For example, in one embodiment of the invention, the address allocation logic includes logic to implement a true LRU algorithm that will allocate an address received by a cache agent to the least recently deallocated entry of the entries to which the cache agent corresponds. Similarly, the data allocation logic, in one embodiment, includes logic to implement a true LRU algorithm that will allocate data received by a cache agent to the least recently deallocated entry of the entries to which the cache agent corresponds. In one embodiment, after a cache agent has been allocated three address and buffer entries, the cache agent may be prevented from sending further addresses or data to the address and data buffers by a credit-based buffer flow control mechanism, for example, until other address and data buffer entries have been deallocated and, therefore, available to store more address and data. In at least one embodiment, the LRU algorithm may be performed for each address and data buffer entry allocation by one or more logic circuits, whereas in other embodiments, the same logic may be used to perform an LRU algorithm for allocating entries in both the address and data buffers.

By allocating the least recently deallocated entries within the address and data entry groups to which a cache agent corresponds independently in each data and address buffer, one embodiment of the invention ensures the correct matching of data and addresses to be combined into a message by the merge logic and delivered to a target recipient specified by the address. In the embodiment illustrated inFIG. 4, a true LRU algorithm is used to allocate address and data buffer entries to the appropriate address and data, respectively. The particular true LRU algorithm used, may be chosen from various known LRU algorithms, including look-up tables, mathematical and/or logical formulas, truth tables, queues, etc. Furthermore, the LRU algorithms may be implemented using hardware logic, software, or some combination thereof. Although the data buffer and address buffer ofFIG. 4are implemented in different logic blocks, they may be combined in some embodiments within the same circuit.

In one embodiment, the architecture depicted inFIG. 4is included within a multi-core processor. However, embodiments of the invention are not so limited in their application. Indeed, embodiments of the invention may be used in single-core processors or among and/or outside of other devices within a computer system.

In one embodiment, the architecture depicted inFIG. 4may merge two messages containing information, such as an address and data to be stored in a location designated by the address, which may be transmitted from a cache agent along one or more neworks, such as an address and data network. However, in other embodiments of the invention, two or more messages containing various types of information, in addition to or instead of address and data information, may be transmitted from a cache agent or agents along any number of networks and combined into a single or otherwise fewer number of messages. For example, in one embodiment of the invention three or more messages may be matched and merged into one message by using a corresponding number of additional buffers and entry allocation logic. Furthermore, in one embodiment, the arbiter logic capabilities may be extended to detect messages being stored or otherwise allocated into any number of buffers, whose contents are to be combined into a single message or messages.