Prioritized conflict handling in a system

A controller has a cache to store data associated with an address that is subject to conflict resolution. A conflict resolution queue stores information relating to plural transactions, and logic reprioritizes the plural transactions in the conflict resolution queue to change a priority of a first type of transaction with respect to a priority of second type of transaction.

BACKGROUND

A multiprocessor system can include multiple processors that can be associated with respective local memories. The multiprocessor system can be arranged as a non-uniform memory access (NUMA) system in which one processor can remotely access the local memory associated with another processor.

DETAILED DESCRIPTION

In a non-uniform memory access (NUMA) multiprocessor system, processors can be interconnected by a system interconnect (including buses or links), or alternatively, processors can be interconnected using a connection infrastructure that includes intermediate controllers as well as a system interconnect. The processors of the multiprocessor system can be associated with respective local memories. Each processor is able to access its local memory. Additionally, a processor can also remotely access the local memory of another processor. A “memory” can refer to a storage device or collection of storage devices, which can include integrated circuit or semiconductor memory device(s) or other types of storage devices.

In a NUMA multiprocessor system, a processor is able to access its local memory with lower latency than access of the local memory by a remote processor. A local processor is able to access the local memory over a relatively high-speed interconnect. A memory transaction issued by the local processor to access data in the local memory is referred to as a local memory transaction. In contrast, a remote memory transaction from a remote processor travels from the remote processor through an intermediate system interconnect (and possibly intermediate controllers) before the remote memory transaction can reach the memory controller of the local memory.

In addition to the increased latency associated with a remote memory transaction (as compared to a local memory transaction) due to the different paths traveled by the remote and local memory transactions, performance of synchronization in a multiprocessor system can also add to latency associated with the remote memory transaction. Synchronization enables concurrent processes or threads to coordinate accesses to a shared resource. Synchronization ensures that multiple requestors (read requestors and/or write requestors) of data at the coherent memory location do not see inconsistent versions of the data.

To access a coherent memory location, a requestor (e.g. a thread or other execution unit that executes on a processor) may acquire a lock associated with the memory location. The lock can be in the form of a semaphore, for example, which is a variable or other information element that controls access by multiple requestors of a common resource (e.g. the coherent memory location in a shared memory device). In other examples, other types of locks can be employed. When a first requestor holds a lock on a particular piece of data (such as data in a coherent memory location), then access to the particular piece of data by another requestor is restricted.

Due to proximity, a thread or other execution unit executing on a local processor may have an advantage in acquiring locks of coherent memory locations in local memory, over threads or other execution units executing on remote processor(s). This advantage in acquiring locks of coherent memory locations can lead to increased lock acquisition latency for remote memory transactions as compared to local memory transactions.

In addition, as part of synchronization, conflict resolution can be performed for multiple memory transactions that seek to access the same memory location (e.g. the memory transactions are directed to the same address associated with the memory location, which results in an address conflict). In some cases, conflict resolution can be performed by serializing the memory transactions, such that ordering and memory consistency can be preserved.

A remote memory transaction may be subjected to conflict resolution at multiple points in the multiprocessor system—for example, the remote memory transaction may be subjected to conflict resolutions in multiple intermediate controllers as well as in a memory controller of a local processor. In contrast, a local memory transaction may be subjected to conflict resolution at one point—the memory controller. If serialization is performed at each of multiple conflict resolution points for the remote memory transaction, then the remote memory transaction may experience higher latency due to conflict resolution as compared to a local memory transaction.

In accordance with some implementations, an intermediate controller (also referred to as an “agent controller” in the ensuing discussion) is configured to reduce the latency of remote memory transactions, while maintaining the ability to properly synchronize multiple transactions that are attempting to access the same address (resulting in an address conflict). The agent controller is able to perform prioritized conflict handling that reduces the imbalance between local and remote memory transactions that are contending for a lock of a local memory location. In some implementations, the prioritized conflict handling can be implemented entirely in hardware. In other implementations, the prioritized conflict handling can be performed by a combination of hardware and machine-readable instructions (which can execute on the hardware).

FIG. 1is a block diagram of an example multiprocessor system that has multiple processors102,104,106, and108. Although four processors are depicted inFIG. 1, note that in other examples, the multiprocessor system can include different numbers of processors. In some examples, the processor102includes multiple processing cores110. Also, the processor102is integrated with a memory controller112that controls access of a local memory114that is connected to the processor102. Each of the other processors104,106, and108similarly includes multiple processing cores and a memory controller. In other examples, instead of having multiple processing cores in a processor, the processor can include just one processing core.

For purposes of discussion, the processor102is considered a local processor, associated with the local memory114. The processors104,106, and108are considered remote processors, in the sense that such remote processors are able to remotely access the local memory114associated with the local processor102.

Although not depicted inFIG. 1, each of the remote processors104,106, and108can also be connected to a respective memory. In a different context, the local processor102can be considered a remote processor that is capable of accessing a local memory of one of the processors104,106, and108.

In implementations according toFIG. 1, each of the processors102,104,106, and108is connected to a respective agent controller116,118,120, and122. The agent controllers116,118,120, and122are interconnected to each other over a system interconnect124(including buses or links). AlthoughFIG. 1shows each processor being connected to a respective agent controller, it is noted that multiple processors can be connected to an agent controller in other examples. Also, in further examples, a processor can also be connected to the system interconnect124without passing through an agent controller.

Although the agent controllers116,118,120, and122are depicted as being separate from their respective processors102,104,106and108, in different examples, an agent controller can be integrated into a respective processor. Thus, an “agent controller” can refer to a controller that is outside of an associated processor, or integrated into the associated processor. In implementations where the agent controller is separate from the respective processor, the agent controller can be implemented as an application-specific integrated circuit (ASIC) device, programmable gate array (PGA), or other type of control chip. An agent controller can perform various defined tasks, including synchronization tasks, data communication tasks, and other tasks.

In the ensuing discussion, the agent controller116is referred to as a “local agent controller,” while the agent controllers118,120, and122are referred to as “remote agent controllers.”

The local processor102is able to issue local memory transactions (read transactions, write transactions, etc.) to the local memory114. Such local memory transactions are issued by threads or other execution units executing on the processing cores110. A local memory transaction from a processing core110is communicated to the memory controller112, which then issues access commands to the local memory114to perform a read or write of the local memory transaction.

A remote processor (104,106, or108) can issue a remote memory transaction to the local memory114. This remote memory transaction is passed through a respective remote agent controller118,120or122, over the system interconnect124, through the local agent controller116, and through the memory controller112of the local processor102to the local memory114. The remote memory transaction can be a read transaction or a write transaction or other type of transaction.

The memory controller112of the local processor102is also able to issue a local snoop transaction. A local snoop transaction can be performed in response to a local memory transaction (issued from a processing core110in the local processor102) if the memory controller112detects that a remote processor may be an owner of the memory location that is the target of the local memory transaction. The memory controller112can track previous remote read transactions to determine remote ownership of memory locations associated with the local memory114. Whenever a local memory transaction attempts to access one of the memory locations that is remotely owned, the memory controller112in the local processor102issues a local snoop transaction to the local agent controller116, which in turn sends the local snoop transaction to the remote processor that owns the accessed memory location. The local snoop transaction sent to the remote processor can cause the remote processor to perform various tasks, including for example: initiating a writeback transaction if the remote processor has modified the data that is the subject of the local snoop transaction, invalidating the data at the remote processor, and so forth. The writeback transaction causes the modified data to be written back to the local memory114to update the corresponding memory location (to ensure that the local memory transaction that caused the local snoop transaction is working with the most up-to-date version of the data).

In examples according toFIG. 1, conflict resolution among memory transactions attempting to access the same memory location (which causes an address conflict) can be performed at various points, including at each of the agent controllers, and at the memory controllers in the various processors. A local memory transaction generated by a processing core110in the local processor102is subjected to possible conflict resolution in the memory controller112. Memory transactions that are directed to the same memory address are placed into a conflict resolution queue130in the memory controller112.

Placing memory transactions in a conflict resolution queue refers to storing information relating to the memory transactions (e.g. information containing the respective commands and any associated data, or information pointing to where the commands and any associated data are stored).

In some examples, conflict resolution at the memory controller112involves serializing the memory transactions such that the memory transactions in the conflict resolution queue130are executed one at a time by the memory controller112.

A remote memory transaction for accessing the local memory114, such as from the remote processor104, is subjected to conflict resolution at three possible points: the remote agent controller118, the local agent controller116, and the memory controller112of the local processor102. The remote agent controller118includes a conflict resolution queue132in which memory transactions associated with an address conflict are placed. Similarly, the local agent controller116includes a conflict resolution queue134into which memory transactions associated with an address conflict are placed. The remote agent controllers120and122similarly include their respective conflict resolution queues136and138.

Note that the conflict resolution queue134in the local agent controller116can store the following memory transactions associated with an address conflict: remote memory transactions directed to a particular address, and local snoop transactions for the particular address.

Although just one conflict resolution queue is depicted in each of the agent controllers116,118,120,122, and in the memory controller112, it is noted that each of the agent controllers and the memory controller can include multiple conflict resolution queues, where each conflict resolution queue is provided for a corresponding address. Thus, where there are multiple conflict resolution queues in a controller (agent controller or memory controller), memory transactions having an address conflict with respect to a first address can be placed in a first conflict resolution queue, memory transactions having an address conflict with respective to a second address can be placed in a second conflict resolution queue, and so forth.

If a remote memory transaction, such as from the remote processor104, is subjected to conflict resolution in each of the three conflict resolution queues132,134, and130, then such remote memory transaction is associated with a larger latency than would be experienced by a local memory transaction, which is subjected to possible conflict resolution at just one point, the conflict resolution queue130of the memory controller112.

In accordance with some implementations, to address the advantage that local memory transactions have over remote memory transactions in the conflict resolution hierarchy, the local agent controller116can implement a prioritized conflict handling mechanism. This prioritized conflict handling mechanism includes conflict resolution logic140and a conflict data cache142, both located in the local agent controller116. Although not shown, the other agent controllers118,120, and122can each also include its respective conflict resolution logic and conflict data cache.

The conflict data cache142is used to store data that is the subject of conflict resolution in the local agent controller116. For example, if the local agent controller116detects multiple memory transactions for the same address of the local memory114, the local agent controller116would store data referred to by the address into an entry (e.g. line) of the conflict data cache142. The conflict data cache142can be relatively small, since conflicts may be relatively rare. In some examples, the conflict data cache142can include as few as eight entries (where each entry can store data corresponding to a specific memory location having a predefined size). In other examples, the conflict data cache142can have different numbers of entries.

Each entry of the conflict data cache142can include the following elements: a data block (which stores the data of the corresponding memory location), a tag (which contains a portion of the address that refers to the corresponding memory location), flag bits (to indicate whether the data in the entry is valid/invalid and dirty/non-dirty), and lock information.

The lock information in an entry of the conflict data cache142allows a remote memory transaction to acquire a lock of the data in the entry of the conflict data cache. This lock can be acquired by setting the lock information in the conflict data cache entry to a predetermined value.

Reference is made toFIGS. 1 and 2in the ensuing discussion.FIG. 2shows the local agent controller116receiving remote read and write transactions (204) from a remote processor (or remote processors), and receiving local snoop transactions (206) from the memory controller112of the local processor102. In response to a remote read or write transaction (204), the local agent controller116passes a corresponding read or write transaction (208) to the memory controller112of the local processor102. Read data (210) retrieved from the local memory114is returned from the memory controller112to the local agent controller116in response to a read transaction (208). The read data (210) can be added to the conflict data cache142.

In response to a remote read transaction received by the local agent controller116, logic202(referred to as “CDC logic”) associated with the conflict data cache142determines if there is a cache hit in the conflict data cache142(in other words, whether the conflict data cache142contains data associated with the memory location referenced by the address of the remote read transaction). A determination of cache hit in the conflict data cache142is accomplished by comparing a portion of an address of the remote read transaction with the tag in the conflict data cache142.

If there is a cache hit, then the data can be retrieved from the conflict data cache142and returned as remote read data (211) to the requesting remote processor in response to the remote read transaction. Satisfying a remote read transaction from the conflict data cache142improves performance of the remote read transaction (by reducing read latency). The reduced latency results because the remote read transaction that can be satisfied from the conflict data cache142does not have to be passed through the local processor102to the local memory114. Moreover, satisfying a remote read transaction from the conflict data cache142eliminates having to perform conflict resolution in the local processor102due to the remote read transaction.

As noted above, a conflict data cache entry can include a dirty bit (part of the flag bits) to indicate whether or not the data in the conflict data cache entry is dirty or non-dirty. Data is dirty if the data in the conflict data cache entry is the most up-to-date version of the data, with copies of the data at the local memory114being out-of-date. For example, a remote write transaction (204) that has a cache hit in the conflict data cache142can cause data in the conflict data cache142to be updated, which would cause the dirty bit to be set to a value indicating that the data in the corresponding conflict data cache entry is dirty (modified).

In addition to the conflict data cache142, the conflict resolution logic140in the local agent controller116is able to further reduce the latency of remote memory transactions by re-prioritizing certain transactions in the conflict resolution queue134. In some implementations, the conflict resolution logic140allows a remote read transaction to bypass a conflicting local snoop transaction in the conflict resolution queue134. Alternatively, a local snoop transaction in the conflict resolution queue134can be deferred when a remote read transaction is present in the conflict resolution queue134, which effectively allows the remote read transaction to have a higher priority. By being able to promote a remote read transaction in the conflict resolution queue134(ahead of a prior conflicting local snoop transaction), the priority of the remote read transaction is increased over the priority of the local snoop transaction.

As noted above, a local snoop transaction is issued by the local processor102in response to a local read transaction. The local read transaction cannot complete until a response is received to the local snoop transaction. By deferring the local snoop transaction in the local agent controller116, the local agent controller116effectively throttles the ability of the local processor102to access a locally-stored lock (for a memory location in the local memory114), to thus improve the ability of the remote read transaction to access the memory location of the local memory114(either from the local memory114or from the conflict data cache142).

In some examples, a local snoop transaction should not be deferred indefinitely, since a timeout (during execution of a thread or execution unit that issued the respective local read transaction) may occur that can result in errors in the system. To prevent starvation of a local snoop transaction, a counter or timer can be employed in the conflict resolution logic140; expiration of the counter or timer causes overriding of the prioritization of remote read transactions over conflicting local snoop transactions (or alternatively, stops the deferment of the local snoop transaction).

FIG. 3is a flow diagram of a process of prioritized conflict handling according to some implementations. The process ofFIG. 3can be performed by the conflict resolution logic140, for example. The process receives (at302) an incoming transaction targeted to an address of the local memory114. The incoming transaction can be a remote read transaction, a remote write transaction, and a local snoop transaction.

The process determines (at304) whether the incoming transaction has an address conflict with another transaction that is in progress or that is in the conflict resolution queue134. If there is no address conflict, then the incoming transaction can be processed (at306). Processing the transaction at306can involve issuing a read to the local memory114, issuing a write to the local memory114, accessing the conflict data cache142, receiving a response from the memory controller112, and/or issuing a response to a requesting remote processor.

If the process determines (at304) that there is an address conflict, the process determines (at308) whether the incoming transaction is a remote write transaction. If so, the remote write transaction is promoted to the head of the line, and is allowed to be processed (at306). In other words, the remote write transaction has priority over a prior remote read transaction or a prior local snoop transaction associated with the same address. Processing the remote write transaction involves issuing the write transaction to the memory controller112of a local processor102.

If the process determines (at308) that the incoming transaction is not a remote write transaction, then the incoming transaction (which can be a remote read transaction or a local snoop transaction) is added (at310) to the conflict resolution queue134.

Tasks312-324ofFIG. 3discussed below are iteratively performed in sequence for each of the transactions in the conflict resolution queue134. If there are n (n>1) transactions in the conflict resolution queue134, then the tasks312-324are iteratively performed n times, one for each transaction in the conflict resolution queue134.

The process determines (at312) if there is an address conflict between a currently considered transaction (in the conflict resolution queue134) with an in-progress transaction. Such address conflict can be removed once the in-progress transaction has completed its operation. If the address conflict with an in-progress transaction is no longer present (following the path from the decision block312), then the currently considered transaction can potentially be removed from the conflict resolution queue134for execution. The process checks (at314) if the currently considered transaction is a local snoop transaction. If not (which can mean that the currently considered transaction is a remote read transaction), then the currently considered transaction is processed (at306).

However, if the currently considered transaction is determined (at314) to be a local snoop transaction, then the process checks (at316) to determine whether the local snoop transaction has been deferred for more than some predefined threshold amount of time. If the local snoop transaction has been deferred for more than the predefined threshold amount of time, then the local snoop transaction is processed (at306). This reduces the likelihood of a time-out event occurring due to excessive delay of the local snoop transaction.

If the local snoop transaction has not been deferred more than the predefined threshold amount of time, then the process next determines (at318) whether there is a remote read transaction in the conflict resolution queue134that conflicts with the local snoop transaction. If so, then the defer time is incremented (at320) and the process returns to task312. However, if there is not a conflicting remote read transaction in the conflict resolution queue134, then the local snoop transaction can be processed (at306).

Tasks318and320act to cause the local snoop transaction to be deferred unless one of two conditions is present: (1) the defer time is greater than the predefined threshold amount of time, or (2) there is no other conflicting remote read transaction in the conflict resolution queue134.

If the currently considered transaction in the conflict resolution queue134is determined (at312) to have an address conflict with an in-progress transaction, then the process determines (at323) whether a deadlock may be possible. A deadlock can occur when there is a circular dependency in which a first transaction depends upon completion of a second transaction, which in turn depends upon completion of the first transaction. Such circular dependency can prevent both the first transaction and the second transaction from completing, which results in deadlock.

Circular dependency can occur in cases where an address conflict for a given address occurs at two or more points in the system. As an example, a remote read transaction is received at the local agent controller116and is provided to the memory controller112of the local processor102. This remote read transaction is labeled “Read2,” and conflicts with an earlier local read transaction (“Read1”) issued by a local processing core110in the local processor102. The local read transaction (Read1) causes the memory controller112to issue a local snoop transaction to the local agent controller116while the local agent controller116is still processing the remote read transaction (Read2). This creates the following circular dependency:

where A→B indicates a dependency of A on B.

To address the foregoing deadlock, the snoop transaction should be allowed to prematurely exit the conflict resolution queue134to break the circular dependency.

As shown inFIG. 3, if the process detects (at323) that a deadlock is possible, then the currently considered memory transaction is allowed to be processed (at306). However, if deadlock is not possible, then the process returns to task312to continue the process ofFIG. 3.

As further shown inFIG. 3, from task306(in which processing of a transaction is performed), the process next determines (at322) whether an address conflict has been detected for the transaction. If so, data associated with the transaction can be inserted (at324) into the conflict data cache142.

FIG. 4illustrates a flow diagram of a process according to further implementations. The process can be performed by logic in the local agent controller116. The process receives (at402) a transaction for data at a particular address. The process determines (at404) whether the received transaction has an address conflict with a second transaction in the local agent controller116. In response to determining the address conflict is present, the process adds (at406) the received transaction to the conflict resolution queue134.

The process can re-prioritize (at408) transactions in the conflict resolution queue134to change a priority of a first type of transaction with respect to a priority of a second type of transaction. For example, a local snoop transaction in the conflict resolution queue134can be deferred to allow a remote read transaction to have greater priority.

In addition, the process stores (at410) data associated with the particular address in the conflict data cache142in response to detecting the address conflict. Such data may have been retrieved from the local memory114in response to a remote read transaction to the particular address.

The logic140and202of the local agent controller116can be implemented as hardware, or implemented as a combination of machine-readable instructions and hardware. In the latter case, the machine-readable instructions can be executed on a processing circuit, which can include a microprocessor, microcontroller, processor module or subsystem, programmable integrated circuit, programmable gate array, or another control or computing device.