Multiprocessor stalled store detection

Details Multiprocessor stalled store detection Multiprocessor stalled store detection

1998-02-19

2001-01-23

An, Meng-Ai T. (Department: 2783)

Electrical computers and digital processing systems: processing

Processing architecture

Distributed processing system

C712S029000, C712S204000

Reexamination Certificate

active

06178493

ABSTRACT:

TECHNICAL FIELD
The present invention relates in general to data processing systems, and in particular, to store and load operations within a multiprocessor system.
BACKGROUND INFORMATION
In multiprocessor systems, situations arise in which the instruction stream executing on one or more processors depends on the successful completion of a memory store operation issued by another processor. Under some circumstances, the store is unable to successfully place its data into memory because the operations initiated by other system participants totally consume the available interconnection bandwidth or have the equivalent effect of blocking the store due to side effects of hazard detection hardware. This store “starvation” may result in a failure to make forward progress in the program which ultimately causes the program to fail. An example of this can be seen in the following pseudo-code:
P1:
P2:
loop:
load word
Rx, A
store word Rz, A
load word
Ry, B
compare word immediate
A, value
branch if not equal
loop
Two processors P
1
, P
2
are involved in a spin loop in which one is waiting for a specific value to be stored by the other processor. Rx, Ry, and Rz refer to processor registers, and A and B are memory addresses. The “compare word immediate” uses a literal value, but comparison to any other source (such as the contents of another register) could also be used.
The store word to A executing in processor P
2
updates a location with a value which is required by the code executing on processor P
1
to make forward process. The loop continues until the expected value is obtained. The second load word instruction (from location B) executing in processor P
1
is not strictly needed to create the starvation scenario if location A is not placed into processor P
1
's cache memory. It is shown in this example to describe a more common situation where locations A and B are cacheable. If processor P
1
's cache is direct mapped and the addresses of locations A and B cause them to occupy the same slot in that cache, the instruction loading word A and the instruction loading word B would always miss, therefore creating repetitive reads from memory external to the processor. If one assumes a more associative cache in processor P
1
, more load word instructions requiring the same slot can be added to the code sequence. The resulting read traffic can have the potential effect of blocking the completion of processor P
2
's store word to A. The likelihood of this blockage increases in a system with a large number of processors if many of the processors are waiting for the value, each executing the sequence shown for processor P
1
.
As a result, there is a need in the art for a solution that permits a stalled store operation to progress.
SUMMARY OF THE INVENTION
The present invention addresses the foregoing problem by providing hardware and a state machine that monitors store requests within each processor in a multiprocessing system and then asserts a store stalled signal in response to a defined threshold being met. This threshold may be the counting of failed store transactions within any one processor, failed arbitrations associated with a stall store operation, or even clock cycles. The store stalled signal is transmitted to all of the processors within the system. In response, read (load) requests pending within those processors are postponed until the stalled store request is allowed to complete. The store stalled signal is then de-asserted and the other processors then continue with their read requests.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention.


REFERENCES:
patent: 4591975 (1986-05-01), Wade et al.
patent: 5710912 (1998-01-01), Schlansker et al.
patent: 5848276 (1998-12-01), King et al.
patent: 5909561 (1999-06-01), Arimilli et al.

Affiliated with

Also associated with

Rating

Multiprocessor stalled store detection does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multiprocessor stalled store detection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiprocessor stalled store detection will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2504555