Deadlock avoidance using exponential backoff

Details Deadlock avoidance using exponential backoff Deadlock avoidance using exponential backoff

1999-05-18

2002-07-30

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S151000, C711S152000, C711S163000

Reexamination Certificate

active

06427193

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to the field of processors and, more particularly, to load/store units within processors.
2. Description of the Related Art
Processors are more and more being designed using techniques to increase the number of instructions executed per second. Superscalar techniques involve providing multiple execution units and attempting to execute multiple instructions in parallel. Pipelining, or superpipelining, techniques involve overlapping the execution of different instructions using pipeline stages. Each stage performs a portion of the instruction execution process (involving fetch, decode, execution, and result commit, among others), and passes the instruction on to the next stage. While each instruction still executes in the same amount of time, the overlapping of instruction execution allows for the effective execution rate to be higher. Typical processors employ a combination of these techniques and others to increase the instruction execution rate.
As processors allow larger numbers of instructions to be in-flight within the processors, the number of load and store memory operations which are in-flight increases as well. As used here, an instruction is “in-flight” if the instruction has been fetched into the instruction pipeline (either speculatively or non-speculatively) but has not yet completed execution by committing its results (either to architected registers or memory locations). Additionally, the term “memory operation” is an operation which specifies a transfer of data between a processor and memory (although the transfer may be accomplished in cache). Load memory operations specify a transfer of data from memory to the processor, and store memory operations specify a transfer of data from the processor to memory. Load memory operations may be referred to herein more succinctly as “loads”, and similarly store memory operations may be referred to as “stores”. Memory operations may be implicit within an instruction which directly accesses a memory operand to perform its defined function (e.g. arithmetic, logic, etc.), or may be an explicit instruction which performs the data transfer only, depending upon the instruction set employed by the processor. Generally, memory operations specify the affected memory location via an address generated from one or more operands of the memory operation. This address will be referred to herein in as a “data address” generally, or a load address (when the corresponding memory operation is a load) or a store address (when the corresponding memory operation is a store). On the other hand, addresses which locate the instructions themselves within memory are referred to as “instruction addresses”.
Since memory operations are part of the instruction stream, having more instructions in-flight leads to having more memory operations in-flight. Accordingly, cache misses are encountered more frequently and thus bandwidth on the interfaces between the processors and memory becomes increasingly saturated. A memory operation is a “hit” in a cache if the data accessed by the memory operation is stored in cache at the time of access, and is a “miss” if the data accessed by the memory operation is not stored in cache at the time of access. When a load memory operation misses a data cache, the data is typically loaded into the cache. Store memory operations which miss the data cache may or may not cause the data to be loaded into the cache. Data is stored in caches in units referred to as “cache lines”, which are the minimum number of contiguous bytes to be allocated and deallocated storage within the cache.
Furthermore, computer systems employing multiple processors in a coherent multiprocessor configuration are becoming more common. As these computer systems employ higher performance processors which utilize more bandwidth, deadlock scenarios become increasingly likely. Generally, deadlock scenarios may occur when two or more processors are attempting to concurrently obtain ownership of a cache line. For memory operations to be coherent, certain ownership levels in one processor require a release of ownership by other processors. For example, one processor obtaining exclusive ownership requires than all other processors relinquish ownership. However, if more than one processor is attempting to achieve exclusive ownership, ownership may be transferred from processor to processor prior to any processor being able to complete its operation. While the system coherency scheme may correctly be handing off ownership, no processor is making forward progress by completing the underlying memory operation.
Such deadlock problems may occur with respect to a single cache line, but may be even more pronounced if a memory operation is misaligned in such a way that the memory operation accesses some bytes within one cache line and other bytes within another cache line. If two or more processors concurrently attempt to perform such memory operations to the same cache lines, the processors can easily trade ownership of the cache lines with no processor maintaining exclusive ownership of both cache lines long enough to complete the memory operation. Accordingly, a processor which may be included in a multiprocessing computer system and which aids in resolving such deadlock scenarios is desired.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a processor as described herein. The processor is configured, upon losing sufficient ownership of a cache block to complete a memory operation, to “backoff” for a backoff time interval. During the backoff time interval, the processor does not attempt to reestablish ownership of the cache block. Once the backoff time interval expires, the processor reestablishes ownership of the cache block. If the ownership is lost again before completing the memory operation, the processor is configured to increase the backoff time interval. In one embodiment, the processor is configured to increase the backoff time at an exponential rate. Accordingly, when two or more processors are attempting to obtain ownership of one or more cache blocks to complete a memory operation, the backoff time interval may eventually increase to an interval which allows one of the processors to complete the memory operation. Other ones of the two or more processors may subsequently complete their memory operations. Deadlock may therefore be avoided.
Broadly speaking, a computer system is contemplated comprising a first processor, a second processor, and a memory coupled to the first processor and the second processor. The first processor is configured to access a first memory location. In response to a snoop operation corresponding to the access of the first memory location by the first processor, the second processor is configured to relinquish ownership of the first memory location and to inhibit reestablishing the ownership of the first memory location for a first time interval subsequent to the snoop operation. Additionally, the second processor is configured to increase the first time interval in response to additional repetitions of reestablishing the ownership and relinquishing the ownership while attempting to perform a first memory operation to the first memory location.
A processor is contemplated comprising a bus interface unit and a load/store unit coupled thereto. The bus interface unit is configured to communicate upon a bus to which the processor is couplable. The bus interface unit is configured to receive a snoop operation upon the bus. The load/store unit includes a buffer configured to store a first memory operation. The load/store unit is configured to compare a snoop address corresponding to the snoop operation to a first data address corresponding to the first memory operation to detect a snoop hit. In response to the snoop hit, the load/store unit is configured to: (i) relinquish ownership of a memory location identified by the first data address; and (ii) increase a first time interval from the snoop request during which the processor

Affiliated with

Also associated with

Rating

Deadlock avoidance using exponential backoff does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Deadlock avoidance using exponential backoff, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deadlock avoidance using exponential backoff will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2893274