System for independent cache-to-cache transfer

• US 4,503,497 A
• Filed: 05/27/1982
• Issued: 03/05/1985
• Est. Priority Date: 05/27/1982
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Krygowski, Matthew A., Messina, Benedicto U., Silkman, William D.
• Primary Examiner(s): Thomas, James D.
• Assistant Examiner(s): Clark, David L.
• Application Number:
  US06/382,842
• Time in Patent Office: 1,013 Days
• Field of Search: 364/200, 364/900
• US Class Current: 711/124
• CPC Class Codes: G06F 12/0822 Copy directories local copy tags for implementing a bus snooping protocol G06F12/0831

Abstract

The disclosure provides a plurality of embodiments for controlling the bus paths for a line of data from any cache in a multiprocessing system (MP) to any requesting cache or I/O channel processor in the MP. The data transfers can occur in parallel among plural CPU caches, channel processors and main storage (MS) sections using crosspoint switches in a manner which utilizes the high circuit count of LSI modules without substantially utilizing the module I/O pin count to enable MP structures to contain more CPUs than could be contained with conventional bussing.

Claims

1. In a multiprocessor system (MP) having plural central processing units (CPUs), an I/O channel processor, and a shared main storage (MS), each CPU having a cache directory and cache for receiving and casting-out lines of data from and to MS on MS bussing means, any cache in the MP becoming a requesting cache when it does not contain a data line having a data unit requested by the associated CPU which is signalled as a missed request by cache directory controls, the MP comprising:

cross-interrogation (XI) means for receiving each CPU request missed in a requesting cache to search directories for all other caches in the MP for a data line containing the requested data unit, any other cache being found by the XI means to have a data line containing the requested data unit being designated as a XI hit line in a XIH cache,

control communication means associated with the XI means for control signalling to the requesting cache when a XIH line is to be transferred from the XIH cache,

data bussing means separate from the MS bussing means for transferring the XIH line of data from the XIH cache to the requesting cache without passing the data through MS or synchronizing the transfer with the availability of the MS bussing means,

means for starting a data transfer on the data bussing means by first transferring the requested data unit and then transferring the remainder of the data line from the XIH cache to the requesting cache,

whereby the requesting CPU can begin execution with the requested data unit before the cache-to-cache transfer of the data line is completed,

the MS bussing means being available for an MS operation for a different data line during the cache-to-cache transfer of the data line on the data bussing means, whereby the cache-to-cache data transfer is not delayed by MS being busy with other requests.

2. In a MP as defined in claim 1, further comprising:

a plurality of output data buffers (OBBs), one OBB associated with each cache,

means for copying the XIH line from the XIH cache into the associated OBB beginning with the requested data unit,

the data bussing means transferring the XIH line from the OBB to the requesting cache beginning with the requested data unit,

means for the XIH cache to be accessed by the associated CPU for other data lines simultaneously while the XIH line is being transferred from the associated OBB to the requesting cache on the data bussing means.

3. In a MP as defined in claim 1, further comprising:

an instruction element in each CPU in the MP for making requests for data exclusive to an associated cache directory which may miss and generate an exclusive missed request to the XI means,

the XI means finding the XIH line changed in the XIH cache,

the control communication means marking the received line changed and exclusive in the directory for the requesting cache,

the data bussing means transferring the line to the requesting cache, no data transfer from or to MS occurring on the MS bussing means for the exclusive request for the XIH line.

4. In a MP as defined in claim 1, further comprising:

an instruction element in each CPU in the MP for making requests for readonly data to an associated cache directory which may miss and generate a readonly missed request to the XI means,

the XI means detecting the state of a line changed (CH) flag field for a XIH line in the XIH cache,

the data bussing means transferring the XIH line to the requesting cache,

the control communication means marking the received line exclusive in the directory for the receiving cache and setting the CH flag field for the received line to the same state as the CH flag field detected by the XI means for the XIH line when the request is made,

no data transfer from or to MS occurring for the XIH data line which is to be held exclusively in the requesting cache.

5. In a MP as defined in claim 1, further comprising:

an instruction element in each CPU in the MP for making requests for either exclusive (EX) or readonly (RO) data to an associated cache directory,

flag means with each cache directory in the MP for indicating the EX or RO state of each line of data being validly held in each associated cache,

means for generating a MS request for a line fetch in MS of a line of data containing the missed request at the time the XI means receives the missed request,

means for cancelling the MS request in response to the control communication means signalling that a XIH cache is found with an EX flag indicating the XIH line is exclusive,

whereby no data transfer from MS to the requesting cache occurs for the exclusive XIH line of data which is transferred from the XIH cache to the requesting cache, thereby freeing path resources from MS to the requesting cache.

6. In a MP as defined in claim 5, an instruction element causing an EX missed request, further comprising:

means for setting on the EX state in the flag means for the XIH line in the requesting cache directory,

means for invalidating the XIH line in the XIH cache directory,

whereby the transferred line is available exclusively in the requesting cache after the cache-to-cache transfer.

7. In a MP as defined in claim 2, further comprising:

flag means accompanying each entry in each cache directory in the MP for indicating an exclusive (EX) or readonly (RO) state and a changed (CH) or not changed state of each validly held line of data in the associated cache,

an instruction element making a RO request which missed in the associated cache which outputs a RO missed request to the XI means,

the CH flag means for the XIH line in the XIH cache being found by the XIH means to indicate the XIH line is changed and different from a corresponding line in MS with the same MS address,

means for transferring the XIH line on the data bussing means from the associated OBB to the requesting cache without regard to the availability of the MS bussing means,

the MS bussing means, when available, later transferring the XIH line to MS from the associated OBB for a RO request,

means for setting flag means in the requesting cache directory for the XIH line to RO state and not changed state to indicate the received line is now the same as the line in MS with the same address.

8. In a MP as defined in claim 7, further comprising:

XIH means for inhibiting the transferring means when line is flagged in the XIH cache as not changed and therefore is the same as the corresponding line in MS,

whereby the XIH line is transferred to the requesting cache but is not transferred to MS when the XIH line is flagged to be the same as the corresponding line of data in MS, regardless of whether the instruction unit request causes a RO or an EX missed request.

9. In a MP as defined in claim 8, further comprising:

the XI means including a copy directory (CD) for each cache directory in the MP,

flag means with each entry in each cache directory in the MP for indicating an exclusive (EX) or readonly (RO) state and a changed (CH) or not changed state of each line of data being validly held in each associated cache, each CD having a copy of the EX/RO flag means for each entry but not having any copy of any CH flag means,

an instruction element making an exclusive request which missed in the associated cache which outputs a EX missed request to the XI means,

the CH flag means for a XIH line found in the XIH cache directory indicating the XIH line is changed and different from a corresponding line in MS with the same MS address,

means for inhibiting the transferring means when the XIH line has the EX flag means on in the XIH CD to prevent a transfer of the line to MS,

whereby the XIH line is transferred by the data bussing means to the requesting cache but is not transferred to MS regardless of the state of the CH flag for the XIH line in the XIH cache directory when the EX flag is set on for the XIH line in the XIH CD for an EX missed request, and

whereby the XI means determines the action required by the XIH cache directory before the control communication means communicates with the XIH cache or XIH cache directory.

10. In a MP as defined in claim 8, further comprising:

MS cancelling means for cancelling an access request to MS, the MS cancelling means not being actuated by the XI means when the XI means finds an XIH cache directory that indicates the XIH line is not-changed and is in RO state,

the MS bussing means is actuated to fetch the MS requested line from MS to the requesting cache, whereby no cache-to-cache transfer occurs regardless of whether the instruction unit request cause a RO or an EX missed request.

11. In a MP as defined in claim 8, further comprising:

the MS cancelling means not being actuated when the XI means does not find any XIH line in any cache in the MP and has a XI miss,

whereby the MS requested line fetch is transferred from MS to the requesting cache and no cache-to-cache transfer occurs for the XI miss.

12. In a MP system as defined in claim 1, further comprising:

means for connecting I/O channel requests for MS data accesses to the XI means,

the communication control means signalling when a XIH line has been found by the XI means in a cache directory for an I/O channel request, and that the line is being transferred to the requesting channel,

the data bussing means transferring the data from the XIH cache to the requesting channel without passing the data through MS or synchronizing the transfer with the availability of MS.

13. In a MP as defined in claim 12, further comprising:

a plurality of output data buffers (OBBs), one OBB associated with each cache,

means for copying the XIH line from the XIH cache into the associated OBB in response to signalling from the communication control means,

the data bussing means transferring the XIH line from the OBB to the requesting I/O channel in response to a signal that the XIH line is received by the associated OBB,

whereby the XIH cache can be performing access operations independent of the XIH line while the XIH line is being transferred to the requesting channel from the associated OBB.

14. In a MP system as defined in claim 13, further comprising:

means for transferring the XIH line from the associated OBB to MS whenever MS is available after the XIH line or any part of the line is transferred from the associated OBB to the requesting I/O channel,

whereby the I/O channel can later obtain from MS any data in the XIH line not received by the I/O channel during the cache-to-channel transfer, so that the XIH cache is not again disturbed for the same line of data by any other channel request.

15. In a MP as defined in claim 1, in which the XI means further comprises:

a copy directory (CD) corresponding to an associated CPU cache directory associated with each CPU,

cache request command means for responding to a missed request in a CPU cache directory to signal the missed request to the XI means,

command registering means (LFAR) for storing a miss request to the XI means,

whereby the cache having a miss request registered in the command registering means is available for receiving other CPU requests while waiting for the requested line of data.

16. In a MP as defined in claim 15, in which the control communication means further comprises:

XI search address registering means (XISAR) for receiving miss requests from each CPU cache directory, the XI means connecting the XISAR to each CD in the MP for searching each required CD for a miss request being provided by the XISAR, a found line being designated CD(XIH) and its associated CPU cache directory being designated SIC(XIH),

XIH request signalling means for signalling from the CD(XIH) to controls for SIC(XIH) when a XIH line is found in the CD(XIH) that must be castout and/or invalidated, or changed-to-readonly state.

17. In a MP as defined in claim 16, the XI means further comprising:

means for comparing addresses in each signalled CD with an address in XISAR, wherein the finding of an equal address in a CD identifies an XIH entry in a CD(XIH),

means for testing flag fields in the XIH entry in CD(XIH), the flag fields including a valid (V) field and an exclusive/readonly (EX/RO) field,

XIH request bus means being actuated by the comparing means finding an XIH line for requesting the cache controls for SIC(XIH) and the associated cache directory to castout and/or invalidate or change-to-readonly the XIH line in response to the request on the XIH request bus means.

18. In a MP as defined in claim 17, in which the control communication means further comprises:

XIH response control means associated with the controls for each CPU cache directory in the MP for generating XIH response signals for indicating that the cache controls are complying with a XIH request received from the XIH request bus means.

19. In a MP as defined in claim 18, in which the control communication means further comprises:

XIH command response control means for signalling to controls for the requesting cache whether the XIH line is changed in relation to a line in MS at the same address.

20. In a MP as defined in claim 19, in which the MP further comprises:

data switching circuit means for connecting a data path from the XIH cache to the requesting cache in response to the response signals from the XIH response control means for SIC(XIH).

21. In a MP as defined in claim 20, the data path from the XIH cache further comprising:

a data line buffer (OBB) connected to the output of the XIH cache for receiving the XIH line in response to the response signals for SIC(XIH),

the data switching circuit means being connected between the output of the OBB for SIC(XIH) and an input bus to the requesting cache.

22. In a MP as defined in claim 21, in which the MP further comprises:

a system control element (SCE) containing the XI means and CDs for all CPU caches in the MP, the XIH command response control means, the OBBs, and the data switching circuit means,

the cache request command means being connected to SCE cache controls in the MP, and

I/O channel request means being connected to the XI means in the SCE, and

MS being connected to the SCE for providing data for MS requests not satisfied by a data transfer from a cache.

23. In a MP as defined in claim 21, in which the MP further comprises:

a plurality of system control elements (SCEs) containing the XI means, each SCE being directly connected to cache controls (BCEs) for a subset of the CPUs in the MP, to a MS section, to an I/O channel processor, and to each other SCE in the MP,

each SCE including a CD corresponding to a CPU cache directory in each BCE directly connected to the respective SCE, the XI means connecting each CD to a respective cache miss request command bus from each directly connected BCE, each SCE also including XIH request means, XIH command response control means, OBBs for receiving data from the directly connected BCEs, and data switching circuit means.

24. In a MP as defined in claims 21 or 22, the data switching means further comprising:

crosspoint (XP) switching means in each SCE connected to the data outputs of the OBBs, the data input to each directly connected BCE, the input and output of the MS section, at least the input to the I/O channel processor, and inputs and outputs to each other SCE.

25. In a MP as defined in claim 24, the crosspoint switching means in each SCE further comprising:

dedicated bussing means providing parallel connections between inputs and outputs connected to the crosspoint switching means.

26. In a MP as defined in claim 25, the data switching means further comprising:

dedicated busses connected between the cross-point switching means in each SCE and in each other SCE in the MP to provide inter-SCE dedicated bussing.

27. In a MP as defined in claim 24, the data switching means further comprising:

assignable bus connection means in each crosspoint switching means for providing parallel connections between its inputs to outputs,

bus assignment priority means in each SCE for assigning bus connection means in each crosspoint switching means in the SCE, and the priority means receiving availability signals for each of the inputs and outputs connecting to each crosspoint switching means in the SCE.

28. In a MP as defined in claim 27, the crosspoint switching means in each SCE further comprising:

a plurality of crosspoint switches, each crosspoint switch connecting to all of the inputs and outputs of the crosspoint switching means,

each crosspoint switch enabling an independent bus connection in the SCE,

whereby plural crosspoint switches can sustain simultaneous parallel data transfers.

29. In a MP as defined in claim 28, the crosspoint switches further comprising:

LSI circuits internal to LSI modules,

whereby the crosspoint switches require minimal module I/O pin count, providing less than all possible simultaneous path connections in any SCE, to enable an increase in the number of CPUs supportable by each SCE in a MP.

30. In a MP as defined in claim 28, further comprising:

the priority means selecting an available input or output of a crosspoint switch in one SCE from or to another SCE for transferring data between SCEs,

a plurality of data busses connecting between the SCEs.

31. In a MP as defined in claim 30, the data busses connecting between SCEs further comprising:

plural half-duplex bidirectional data busses.

32. In a MP as defined in claim 30, the data busses connecting between SCEs further comprising:

plural full-duplex bidirectional data busses.

33. In a MP as defined in claim 30, the data busses connecting between SCEs further comprising:

each of plural data busses comprised of two unidirectional busses for opposite transmission directions.

34. In a MP as defined in claim 28, further comprising:

OBB outputs connected to the crosspoint switching means for outputting any OBB in consecutive machine cycles to a requesting cache or channel processor, regardless of whether the data in the OBB was received from a sending cache in consecutive machine cycles.

35. In a MP as defined in claim 34, further comprising:

means for simultaneously connecting plural OBBs to separate outputs to enable parallel data transmissions to and/or from the plural OBBs in the MP.