Out-of-sequence fetch controls for a data processing system

Claim 2

A processor having data and instruction storage, as defined in Claim 1, the OOS detecting means comprising: means for comparing the IID of a current fetch request with the IID of the oldest unfetched request to determine if the IIDs of the fetch requests are in the sequence of assigned IIDs to indicate the operands are in the conceptual sequence; and means for signalling an OOS condition for either one or both of the compared fetch requests if the comparing means indicates their IIDs are not in the assigned sequence.

Claim 3

A processor having data and instruction storage, as defined in Claim 2, comprising: request holding means having a plurality of fetch request representations for operands in the process of preparing to fetch data from storage, the request holding means holding each fetch request representation for at least until the requested data is obtained; and means for storing information into the fetch request representation for a fetch request, including a storage address for data to be fetched and including any OOS condition signal from the signalling means for the fetch request.

Claim 4

A processor having data and instruction storage, as defined in Claim 3, the processor being one of plural CPUs in a multiprocessor system (MP), each CPU comprising: a private L1 cache having an L1 directory with an entry for each data unit in the L1 cache; means for setting on an OOS field associated with an L1 entry accessed by a fetch request having an OOS condition signal stored in its fetch request representation; 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 CPU; means for testing an OOS condition field associated with an L1 entry accessed for an XI request of another CPU; and means for initiating the executing means to reexecute the program from, or before, an instruction with an operand that set on the OOS condition field tested by the testing means for an XI request.

Claim 5

A processor having data and instruction storage, as defined in Claim 4, the processor being one of plural CPUs in a multiprocessor system (MP), the OOS field associated with each L1 directory entry comprising: an OOS bit set on in response to being accessed by a fetch request having a representation with an OOS condition signal.

Claim 6

A processor having data and instruction storage, as defined in Claim 5, the processor being one of plural CPUs in a multiprocessor system (MP), the CPU comprising: OOS bit turn-on means for setting on the OOS bit associated with all fetches requested while a fetch request has an cache miss with unreturned data.

Claim 7

A processor having data and instruction storage, as defined in Claim 5, the processor being one of plural CPUs in a multiprocessor system (MP), the CPU comprising: OOS bit turn-on means for setting on the OOS bit associated with all fetches requested from the decoding of a serializing type of instruction until the serializing instruction has its execution completed.

Claim 8

A processor having data and instruction storage, as defined in Claim 5, the processor being one of plural CPUs in a multiprocessor system (MP), the CPU comprising: store buffers in an instruction/execution part of the CPU for receiving data from storage fetched for a store operand; and OOS bit turn-on means for setting on the OOS bit associated with an L1 directory entry accessed by a fetch request that accesses data for a store operand in a store buffer.

Claim 9

A processor having data and instruction storage, as defined in Claim 5, the processor being one of plural CPUs in a multiprocessor system (MP), the CPU comprising: OOS bit turn-off means for resetting off all OOS bits associated with an L1 directory while no fetch request is accessing data for a store operand from any store buffer, and no fetch request has a cache miss with unreturned data, and no fetch request is being processed for a fetch operand of a serialization type of instruction, and no fetch request representations in the request holding means has any indication of an OOS condition; and an OOS mode state means set to its OOS mode state in response to an output from the OOS bit turn-off means to enable the setting on of OOS bits associated with the L1 directory entries.

Claim 10

A processor having data and instruction storage, as defined in Claim 9, the processor being one of plural CPUs in a multiprocessor system (MP), the OOS mode state means further comprising: counter means for counting the number of OOS bits that have been turned on; and OOS disabling means being actuated when the counter means reaches a predetermined count to reset off the OOS mode state means set to its OOS mode disabled state.

Claim 11

A processor having data and instruction storage, as defined in Claim 4, the processor being one of plural CPUs in a multiprocessor system (MP), the OOS field associated with each L1 directory entry comprising: an OOS IID (instruction identifier) field associated with each L1 directory entry; and means for setting the OOS IID field to the IID of a fetch request accessing the associated L1 directory entry with an OOS condition signal.

Claim 12

A processor having data and instruction storage, as defined in Claim 11, the processor being one of plural CPUs in a multiprocessor system (MP), the CPU comprising: OOS IID tag storage means for receiving and temporarily storing the IID of each fetch request having an OOS indication in a tag entry at a location corresponding to an L1 directory entry accessed by the fetch request; and means for indicating the validity of each tag entry.

Claim 13

A processor having data and instruction storage, as defined in Claim 12, the processor being one of plural CPUs in a multiprocessor system (MP), the CPU comprising: means for detecting the validity of a tag entry corresponding to an L1 directory entry accessed by the XI means; means for reading the OOS IID in the tag entry if the detecting means indicates the tag entry is valid; and means for reinitiating execution of a current program from, or before, an instruction having the OOS IID read by the reading means.

Claim 14

A processor having data and instruction storage, as defined in Claim 13, the processor being one of plural CPUs in a multiprocessor system (MP), the CPU comprising: means for resetting to an invalid state the tag entry having the OOS IID read by the reading means, comprising: means for providing the IID of each instruction being completed; and means for comparing the OOS IID in the read tag entry with the IID of each completed instruction and setting the tag entry to an invalid state upon an equal comparison.

Claim 15

A processor having data and instruction storage, as defined in Claim 13, the processor being one of plural CPUs in a multiprocessor system (MP), the CPU comprising: OOS IID stack storage means for receiving and temporarily storing the EA (effective address) of each fetch request having an OOS indication in a stack entry at a location corresponding to the received OOS IID; and means for indicating the validity of each stack entry.

Claim 16

A processor having data and instruction storage, as defined in Claim 15, the processor being one of plural CPUs in a multiprocessor system (MP), tag entry invalidating means comprising: means for providing the IID of each instruction being completed in response to the initiating means; means for finding any valid stack entry in the stack storage means having the IID of each completed instruction; means for reading out an EA in any found stack entry; means for locating an OOS IID in a tag entry in the tag storage means with the read out EA; and setting the located tag entry to an invalid state.

Claim 17

A processor having data and instruction storage, as defined in Claim 13, the processor being one of plural CPUs in a multiprocessor system (MP), entry invalidating means comprising: means for invalidating all tag entries.

Claim 18

A processor having data and instruction storage, as defined in Claim 15, the processor being one of plural CPUs in a multiprocessor system (MP), entry invalidating means comprising: means for invalidating all tag entries and all stack entries.

Claim 19

A processor having data and instruction storage, as defined in Claim 2, comprising: means in the processor for setting a serializer field to a serializer state in a fetch operand request representation when decoding a serialization type of instruction; the detecting means detecting for the occurrance of an OOS condition of a fetch operand when the serializer field is set to a serializer state in the fetch operand request representation and providing the IID assigned to the operand; and means for initiating reexecution of a current program including an instruction having an OOS IID provided by the detecting means.

Claim 20

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 each fetch operand specification decoded by the decoding means without regard to the conceptual sequence of the IIDs assigned to the fetch operands; means for accessing data for each 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 out of the assigned sequence; 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 an OOS condition as the occurrence of an XI request from another processor during an OOS window; and means for executing instructions in the processor provided by a program at least from any instruction having a fetch operand with a detected OOS condition if an OOS condition is detected.

Claim 21

A processor having data and instruction storage, as defined in Claim 1, the fetch request representations comprising: a plurality of fetch queue (FQ) entries in a FQ, each FQ entry containing fields for controlling a fetch request, the fields including a fetch request (FR) field set when requested data returns from storage; NIPR means for addressing a current FQ entry having its FR field set off and being the next in sequence FQ entry in the FQ to issue a fetch request to storage; and means for changing the setting of the NIPR means when the currently addressed FQ entry has its FR field set on to change the NIPR setting to address the currently oldest valid FQ entry having its FQ field set off to a non-requested state to control a conceptual sequence of FQ entries addressed by the NIPR means.

Claim 22

A processor having data and instruction storage, as defined in Claim 21, the fetch request representations comprising: a plurality of fetch queue (FQ) entries in a FQ, each FQ entry containing fields for controlling a fetch request, including: an effective address (EA) validly addressing requested data in storage; a fetch request (FR) field set on when data is requested from storage; an OSC indicator set on to indicate when the FQ entry has an operand storage compare condition due to the EA in the FQ entry addressing the same storage location as a store request of an earlier instruction which has not had a store acknowledge signal indicating the store operation has been completed; and NAPR means detecting each FQ entry having a valid address in its EA field and its OSC field indicating no OSC condition exists for the EA and its FR field indicating no request has yet been made for the FQ entry, and the NAPR means operating for each NAPR detected FQ entry by issuing a fetch request to storage for accessing the requested data at the EA in the respective FQ entry, including setting the FR field to indicate a requested state to control the sequence of fetch requests from the FQ to storage which need not be in conceptual sequence.

Claim 23

A processor having data and instruction storage, as defined in Claim 22, the fetch request representations comprising: a plurality of fetch queue (FQ) entries in a FQ, each FQ entry containing fields for controlling a fetch request, including: an effective address (EA) validly addressing requested data in storage; a fetch request (FR) field set on when data is requested from storage; a data return field set on when requested data returns from storage; an OSC indicator set on to indicate when the FQ entry has an operand storage compare condition due to the EA in the FQ entry addressing the same storage location as a store request of an earlier instruction which has not had a store acknowledge signal indicating the store operation has been completed; and DQPR means detecting each FQ entry having its DR field set on indicating requested data has returned from storage for the execution of a respective instruction and resetting the FQ entry to an invalid state.

Claim 24

A processor having data and instruction storage, as defined in Claim 22, the fetch request representations comprising: NUPR means for detecting and addressing each dependent FQ entry (DIDO), the dependent FQ entry being a FQ entry following a NAPR addressed FQ entry (IDFO) and the DIDO having a discontinuity in its IID in relation to the IID sequence of the entries provided to the FQ, the DIDO and the IDFO from which the DIDO determines its discontinuity being a IDFO/DIDO pair.

Claim 25

A processor having data and instruction storage, as defined in Claim 24, NUPR means further comprising: means for setting the NUPR to the pointer contained in the NAPR when the NAPR pointer is different from the NIPR pointer; means for incrementing pointer values in the NUPR in the direction of a pointer value in the NIPR until a fetch queue entry (FQE) is found that represents a fetch operand has not been requested from storage; and and means for writing the pointer value in the NUPR in a dependent field in a table for comparing storage addesses of out-of-sequence fetch requests with addresses of cross-invalidate requests of another processor in an MP.

Claim 26

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.

Claim 27

A particular processor in an MP, as defined in Claim 26, the processor further comprising: means for determining one or more quasi-OOS conditions for a fetch operand that can exist independent of any actual OOS condition for the operand; means for generating an OOST entry for a fetch request having a quasi-OOS condition, the OOST entry for a quasi-OOS operand also receiving an IDFO and an EA for a data unit for the operand; and means for providing a dependency identifier (DIDO) in the OOST entry for the quasi-OOS operand indicating a condition for removal of the quasi-OOS OOST entry from the OOST.

Claim 28

A particular processor in an MP, as defined in Claim 27, the fetch request generating and requesting means further comprising: means for providing the IDFO and EA of each OOS fetch request to the cache for enabling the storage hierarchy to tag the IDFO and EA with the data unit fetched for the request; and data return controls with the cache for sending the IDFO and EA tagged with the fetched data unit to the instruction/execution unit of the processor.

Claim 29

A particular processor in an MP, as defined in Claim 28, the processor further comprising: an associative array containing the OOST for receiving each OOST entry for each OOS fetch request to the cache; and OOST search means for searching in parallel in all valid entries in the associative array for an IDFO identifier equal to a tagged IDFO returned to the instruction/execution unit by the data return controls with the cache for a data unit for a fetch request.

Claim 30

A particular processor in an MP, as defined in Claim 28, the means for providing a dependency identifier (DIDO) for an OOS or quasi-OOS fetch operand further comprising: a fetch operand queue for receiving an entry (FQE) for each fetch specification provided by the decoder means; request selection means (NAPR) for selecting each FQE to next have a fetch request to the cache; conceptual order indicating means (NIPR) for indicating the last fetch request issued in the conceptual order of the fetch requests in the queue; dependency FQE indicating means (NUPR) for indicating the oldest entry in the queue in a condition for making a fetch request to the cache for an operand data unit; and writing an identifier (IDFO) of the operand represented by the FQE indicated by the dependency FQE indicating means (NUPR).

Claim 31

A particular processor in an MP, as defined in Claim 28, the means for providing a dependency identifier (DIDO) for an OOS or quasi-OOS fetch operand further comprising: cache miss signalling means with the cache for signalling to the OOST the IDFO and EA of a fetch request being delayed by a cache miss; means for making an entry in the OOST for the fetch operand of each cache miss signalled by the cache miss signalling means; and means for setting both an IDFO and a DIDO in the OOST entry provided by the making means to the value of the IDFO returned with the cache miss signal, and also setting a cache miss indicator for the OOST entry.

Claim 32

A particular processor in an MP, as defined in Claim 28, the means for providing a dependency identifier (DIDO) for an OOS or quasi-OOS fetch operand further comprising: the fetch operand requesting means indicating when a fetch request is for a store operand; store buffer (SB) means for receiving data units fetched in response to a store operand request; means for generating a fetch request for fetching a data unit from a SB, the SB fetching being a quasi-OOS condition for a fetch request; means for generating an OOST entry for a quasi-OOS fetch request that is to fetch a data unit from a SB; and means for providing a dependency identifier (DIDO) in the OOST entry that identifies the store operand for which the SB fetch is being made, the removal of the OOST entry from the OOST occurring when the storage access for the store operand is complete.

Claim 33

A particular processor in an MP, as defined in Claim 28, the means for providing dependency identifiers (DIDOs) for OOS and quasi-OOS fetch operands further comprising: means for indicating when a fetch operand is for a serialization instruction; means for indicating a quasi-OOS condition for a fetch request for fetching a data unit from the storage hierarchy for each operand in the serialization instruction; means for generating an OOST entry for each quasi-OOS fetch request made for the serialization instruction; means for providing a dependency identifier (DIDO) in each OOST entry made for each quasi-OOS fetch request for the serialization instruction, the dependency identifier identifying the last store operand decoded prior to the serialization instruction, the removal of the OOST entry from the OOST occurring when the storage access for the last store operand is complete; means for signalling when execution of the serialization instruction is complete; means for indicating a quasi-OOS condition for each fetch request provided for any instruction following the serialization instruction before the signalling means signals that the execution is complete for the serialization instruction; means for generating an OOST entry for each quasi-OOS fetch request made following the serialization instruction; and means for providing a dependency identifier (DIDO) in each OOST entry made for each quasi-OOS fetch operand following the serialization instruction, the dependency identifier identifying any store operand in the serialization instruction, the removal of the OOST entry from the OOST occurring when the storage access for the serialization instruction's store operand is complete.

Claim 34

A particular processor in an MP, as defined in Claim 33, the means for providing dependency identifiers (DIDOs) for OOS and quasi-OOS fetch operands further comprising: means for providing first and second indicator fields in any selected entry (FQE) in a fetch queue used for storage fetch requests not currently having returned data, the first indicator field being set to indicate a fetch request for a fetch operand in a serialization instruction, the second indicator field being set to indicate a fetch request for a fetch operand in an instruction following a serialization instruction.

Claim 35

A particular processor in an MP, as defined in Claim 33, processor means for supporting OOS and quasi-OOS fetch operands further comprising: means for comparing the returned IDFO provided by the data return controls with the IDFO in each OOST entry; means for registering the DIDO(i) in any entry OOST(i) found to have an IDFO(i) equal to the returned IDFO and not OOST(i) not having a cache miss, and means for removing any found entry OOST(i) having a cache miss; means for comparing the returned IDFO with the DIDO in each OOST entry to find any OOST(j) having a DIDO(j) equal to the returned IDFO; means for removing any found entry OOST(j) if no OOST(i) is found; and means for setting each DIDO(j) to the registered DIDO(i) if OOST(i) is found.

Claim 36

A particular processor in an MP, as defined in Claim 34, processor means for supporting OOS and quasi-OOS fetch operands further comprising: associative array means containing the OOST for enabling the returned IDFO to be compared in parallel with the IDFOs and the DIDOs in all OOST entries.

Claim 37

A particular processor in an MP, as defined in Claim 35, processor means for supporting OOS and quasi-OOS fetch operands further comprising: means for invalidating any OOST entry having a DIDO that compares equal with any returned identifier for a store operand.

Claim 38

A particular processor in an MP, as defined in Claim 36, processor means for supporting OOS and quasi-OOS fetch operands further comprising: means for providing a cross-invalidate (XI) signal for any other processor requesting to obtain control over a data unit that may be stored in the cache of the particular processor, a storage location EA for the data unit being provided with the XI signal; means for comparing an EA in each entry in the OOST with the EA provided with the XI signal, and means for providing an XI hit signal if any EA in the OOST is found equal to the XI's EA; and means for invalidating all entrties in OOST when any entry has an EA equal to the XI's EA.

Claim 39

A particular processor in an MP, as defined in Claim 37, processor means for supporting OOS and quasi-OOS fetch operands further comprising: means for signalling a retry being actuated by the XI hit signal; and means for initiating a restart of the program at the oldest instruction currently having its execution incomplete in response to an XI hit signal.

Claim 40

A particular processor in an MP, as defined in Claim 37, processor means for supporting OOS and quasi-OOS fetch operands further comprising: means for also invalidating at least a data unit having an EA equal to the XI's EA in the private cache of the particular processor.