Page controlled cache directory addressing

• US 4,441,155 A
• Filed: 11/23/1981
• Issued: 04/03/1984
• Est. Priority Date: 11/23/1981
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Martin, Daniel B., Fletcher, Robert P.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Niessen, William G.
• Application Number:
  US06/324,165
• Time in Patent Office: 862 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/3
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing

Abstract

The described embodiment modifies cache addressing in order to decrease the cache miss rate based on a statistical observation that the lowest and highest locations in pages in main storage page frames are usually accessed at a higher frequency than intermediate locations in the pages. Cache class addressing controls are modified to change the distribution of cache contained data more uniformly among the congruence classes in the cache (by comparison with conventional cache class distribution). The cache addressing controls change the congruence class address as a function of the state of a higher-order bit or field in any CPU requested address.

Claims

1. A method of modifying the addressing of a cache directory with a virtual addres requested by a CPU for accessing a page frame in main storage, the virtual address including an external page address field and an internal page address field, the external page address field being used for addressing the page frame in main storage, a page component field at the high-order end of the internal page address field, a congruence class selection field being taken from the virtual address and including the page component field, the modified cache addressing method comprising the steps of:

selecting a group of contiguous bit positions from the requested virtual address including at least the congruence class selection field and a control bit position which is the lowest-order bit position in the external page address field,

inverting the content of a sub-page bit position in the page component field of the congruence class selection field when the control bit position has one state and not changing the content of the sub-page bit position when the control bit position has another state,

addressing the cache direction with a modified congruence class selection field derived by the inverting step being applied to the congruence class selection field obtained by the selecting step,

whereby improved cache utilization can be obtained by the inverting step redistributing the congruence classes in the cache directory.

2. A method as defined in claim 1, the modified cache addressing method having the sub-page bit position located at the second highest-order bit position in the page component field.

3. A method as defined in claims 1 or 2, the modified cache addressing method further comprising:

executing the inverting step in hardware-circuit paths to cache directory addressing circuits with addressing bits provided by the inverting step having a propagation delay to the cache directory not significantly greater than other bits in the modified congruence class selection field,

whereby the cache directory speed of operation is not affected by the cache addressing method.

4. A method as defined in claim 3, the modified cache addressing method further comprising:

finding a propagation delay for each hardware-circuit to the cache directory addressing circuits for each bit position in the modified congruence class selection field obtained by the selecting step to determine the relative propagation times for the respective hardware-circuit paths,

shortening the propagation time of the hardware-circuits for each bit position provided by the inverting step if the finding step finds the propagation delay for the bit position provided by the inverting step to be longer than a path delay for other bit positions in the modified congruence class selection field.

5. A method as defined in claim 2, the modified cache addressing method further comprising:

setting bistable devices to the states of the bit positions in the congruence class selection field,

providing the inverting step on an output side of the bistable devices for generating the modified congruence class selection field.

6. A method as defined in claim 5, the inverting step further comprising:

exclusive-ORing the control bit position and the second highest-order bit position in the congruence class selection field selected by the selecting step to provide the inverting step on an input side of a register that receives the modified congruence class selection field.

7. Means for addressing a cache directory with a virtual address requested by a CPU for accessing a page frame in main storage, the virtual address including an external page address field and an internal page address field, the external page address field being used for addressing the page frame in main storage, a page component field at the high-order end of the internal page address field, a congruence class selection field being taken from the virtual address and including the page component field, cache addressing means for providing a modified congruence class address field comprising:

gate circuits for selecting a group of contiguous bit positions from the requested virtual address including at least the congruence class selection field and a control bit position which is the lowest-order bit position in the external page address field,

inverter means for receiving and inverting a sub-page bit position in the page component field of the congruence class selection field when the control bit position has a one state and not changing the sub-page bit position when the control bit position has a zero state,

means for addressing the cache directory with a modified congruence class address generated by the inverting means modifying the congruence class selection field to provide the modified congruence class address,

whereby improved cache utilization is obtained by accessing the cache directory with modified congruence class addresses.

8. Cache directory addressing means as defined in claim 7, the inverter means receiving and inverting a sub-page bit position which is the second highest-order bit position in the page component field.

9. Cache directory adressing means as defined in claim 8, the inverter further comprising:

an exclusive-OR circuit receiving the control bit position and the second highest-order bit position to generate the second-highest order bit position in the modified congruence class address having other bit positions the same as in the congruence class selection field.