US 5,185,871 AGranted

Coordination of out-of-sequence fetching between multiple processors using re-execution of instructions

AssigneeInternational Business Machines Corporation

InventorsBradly G. Frey, Raymond J. Pedersen

Life of this patent

Estimating the term…

Loading patent…

Abstract

The disclosure describes means for allowing the sequencing of operand fetches to deviate from the conceptual sequence specified in the program. Allowing fetch sequencing deviations may improve system performance, while not causing any deviation in program execution results. Out-of-sequence (OOS) fetching may be caused by issuing each fetch without regard to the following conditions: 1. a delay in issuance to storage (such as a delay in generating the address for a fetch request); 2. a speed up in operand data return (such as due to fetching the operand data from a store buffer in the execution unit without going to storage for the data); 3. a delay in the return of operand data (such as when a fetch request has a cache miss and its data must be obtained from the storage hierarchy); or 4. an overlap in the return of fetch data for a serializer instruction with execution of instructions preceding the serializer or data and instruction fetching for instructions following the serializer before its completion. Each fetch operand of a serializer is handled as OOS even when it is not OOS in order to eliminate serialized fetching. Operand store compare (OSC) controls are provided to control an OOS fetch dependent on a conceptually prior store operand. If an OOS condition is detected that possibly may have caused wrong data, an execution retry occurs beginning with the currently incomplete instruction stream, and the retry may include OOS fetching. The integrity of data is maintained when an OOS fetch operand is exposed to a cross-invalidation (XI) hit by the storage request of another CPU in a multiprocessor (MP) system.

Claims38

Dependent claims

A processor having data and instruction storage, the processor being one of a plurality of processors in a multiprocessor system (MP), the processor comprising:

instruction decoding means, having instruction buffers for storing fetched instructions assigning instructions indentifier (IID) in sequence at least to each decoded stored instruction in the order that instructions are provided by a program executing on the processor, a conceptual sequence for the instructions in each of said plurality of processors being indicated by the sequence of the assigned IIDs in the processor, and the operand of the instruction being assigned the IID of the instruction;
storage means for storing data units most recently used by the processor, said storage means including a private (L1) cache having an L1 directory with an entry for each data unit in the L1 cache;
cross-invalidate (XI) means for invalidating an L1 entry with a storage address equal to a storage address provided with an XI request from another processor;
means for testing for an out-of-sequence (OOS) indication in an OOS condition field associated with an L1 entry accessed for an XI request of another processor;
means for requesting a fetch of data from the storage means for a fetch operand specification of an instruction being decoded by the decoding means without regard to the conceptual sequence of the IIDs assigned to the fetch operands;
means for storing data for storing a store operand specification decoded by the decoding means with regard to the conceptual sequence of the IIDs assigned to the store operands;
means for detecting an out-of-sequence (OOS) condition for a fetch operand of any instruction decoded or completed having an assigned IID of an instruction in violation of the conceptual sequence of the assigned IIDs;
instruction execution means receiving all fetch operands and store operands and completing the execution of each instruction in conceptual sequence without regard for the sequence of fetches returned from said storage means as long as no OOS condition is detected by the OOS detecting means;
and
means for initiating the executing means to reexecute the program in the sequence of the program from, or before, any instruction having a fetch operand for which the detecting means detected an OOS condition.

7 more elements

A multiprocessor system (MP) with a plurality of processors, and MP storage used in common by the processors for the storage of data and instruction, each processor comprising:

cache means for storing data units most recently used by the processor;
instruction decoding means for assigning an instruction identifier (IID) in sequence at least to each decoded storage instruction in the order that instructions are provided by a program executing on the processor, a conceptual sequence for the instructions in the executing program in each processor being indicated by the sequence of the assigned IIDs in the processor, the operands of an instruction being assigned the IID of the instruction;
means for requesting the cache means for a return of fetch data for a fetch operand specification of an instruction being decoded by the decoding means without regard to the conceptual sequence of the IIDs assigned to the fetch operands;
means for accessing data for a store operand specification decoded by the decoding means with regard to the conceptual sequence of the IIDs assigned to the store operands;
means for detecting an out-of-sequence (OOS) condition for a fetch operand having an assigned IID of an instruction out of the conceptual sequence of the IIDs;
means for determining an OOS window as the period of time that the fetch operand is detected as OOS by the detecting means;
means for storing the OOS indications for fetch operands associatively with affected entries in the processor's cache at least during the OOS window in a location accessible for all processors in the MP;
means for generating a cross-invalidation (XI) request sent to each other processor in the MP when the processor requests to store in its cache in order to invalidate from the cache in each other processor any copy of the data unit to be stored into;
means for detecting a problem OOS condition as the occurrence of an XI request from another processor during an OOS window;
and
means for re-executing instructions in the processor provided by a program at least from any instruction having a fetch operand with a detected OOS condition if a problem OOS condition is detected.

8 more elements

A particular processor having data and instruction storage, the processor being one of plural CPUs in a multiprocessor system (MP), the processor containing an instruction/execution unit including decoding means for decoding instructions in conceptual sequence including detecting fetch operand specifications and store operand specifications in the respective instructions of a program being executed by the processor, and a storage hierarchy containing a cache exclusively used by the processor for accessing operand data from storage as required by instructions of the program, the cache receiving cross-invalidate (XI) requests of other processors in the MP for releasing control of data units to an XI requesting other processor in the MP, the particular processor further comprising:

means for generating and requesting a fetch operand as soon as a fetch request to the cache is generated from the fetch operand specification in an instruction currently decoded by the decoding means in the processor;
means for determining if the fetch request is in the conceptual sequence of decoded operand specifications from the decoding means;
out-of-sequence (OOS) table means having an OOS table (OOST) entry generated therein for each fetch request determined by the determining means to be out of the conceptual sequence of operands;
each OOST entry receiving an identifier (IDFO) of the OOS fetch operand and a storage location (EA) for a data unit for the operand;
and
means for providing a dependency identifier (DIDO) in the OOST entry for determining a condition for removal of the OOST entry from the OOST.

3 more elements

Dependencies are inferred from the claim text.