Testing Real Page Number Bits in a Cache Directory

• US 20100023697A1
• Filed: 07/25/2008
• Published: 01/28/2010
• Est. Priority Date: 07/25/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zaman, Shiraz M., Kapoor, Shakti
• Granted Patent: US 8,185,694 B2
• Time in Patent Office: Days
• US Class Current: 711/128
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents

Abstract

Testing real page number bits in a cache directory is provided. A specification of a cache to be tested is retrieved in order to test the real page number bits of the cache directory associated with the cache. A range within a real page number address of the cache directory is identified for performing page allocations using the specification of the cache. A random value x is generated that identifies a portion of the real page number bits to be tested. A first random value y is generated that identifies a first congruence class from a set of congruence classes within the portion of the cache to be tested. Responsive to the first congruence class failing to be allocated a predetermined number of times, one page size of memory for the first congruence class is allocated and a first allocation value is incremented by a value of 1.

Claims

1. A method, in a data processing system, for testing real page number bits in a cache directory, the method comprising:

retrieving a specification of a cache to be tested in order to test the real page number bits of the cache directory associated with the cache;

identifying a range within a real page number address of the cache directory for performing page allocations using the specification of the cache;

generating a random value x that identifies a portion of the real page number bits to be tested;

generating a first random value y that identifies a first congruence class from a set of congruence classes within the portion of the cache to be tested;

determining if the first congruence class associated with the first random value y has been allocated a predetermined number of times; and

responsive to the first congruence class associated with the first random value y failing to be allocated the predetermined number of times, allocating one page size of memory for the first congruence class associated with the first random value y; and

incrementing a first allocation value associated with the first congruence class by a value of 1.

2. The method of claim 1, further comprising:

responsive to the first congruence class associated with the first random value y being allocated the predetermined number of times, incrementing a failure counter by a value of 1;

determining if the failure counter is equal to a predetermined value;

responsive to the failure counter failing to equal the predetermined value, generating a second random value y that identifies a second congruence class from the set of congruence classes within the portion of the cache to be tested;

determining if the second congruence class associated with the second random value y has been allocated the predetermined number of times; and

responsive to the second congruence class associated with the second random value y failing to be allocated the predetermined number of times, allocating one page size of memory for the second congruence class associated with the second random value y; and

incrementing a second allocation value associated with the second congruence class by the value of 1.

3. The method of claim 2, further comprising:

responsive to the failure counter equaling the predetermined value, generating a third random value y;

identifying a next congruence class that fails to be allocated the predetermined number of times;

identifying a next value y associated with the next congruence class;

determining if the next congruence class has been allocated the predetermined number of times using the associated next value y; and

responsive to the next congruence class failing to be allocated the predetermined number of times, allocating one page size of memory for the next congruence class associated with the third random value y; and

incrementing a next allocation value associated with the next congruence class by the value of 1.

4. The method of claim 3, wherein identifying the next congruence classes that fails to be allocated the predetermined number of times comprises:

scanning each congruence class in the set of congruence class in order from a third congruence class associated with the third random value y to a maximum congruence set size of the set of congruence classes; and

identifying a congruence class that fails to be allocated the predetermined number of times in order from the third congruence class associated with the third random value y to the maximum congruence set size of the set of congruence classes.

5. The method of claim 4, further comprising:

responsive to a failure to identify the congruence class that fails to be allocated the predetermined number of times in order from the third congruence class associated with the third random value y to the maximum congruence set size of the set of congruence classes, scanning to identify the congruence class that fails to be allocated the predetermined number of times from an initial congruence class in the set of congruence classes up to but not including the third congruence class.

6. The method of claim 1, further comprising:

repeating the generation of a random value of y, the determining, the allocating and the incrementing steps for all congruence classes in the set of congruence classes until all of the congruence classes have been allocated the predetermined number of times.

7. The method of claim 1, wherein identifying the range within the real page number address of the cache directory for performing page allocations comprises:

determining an available memory region within the cache where testing of the memory region along with real page number bits in the cache directory is to be performed.

8. The method of claim 7, wherein determining the available memory region within the cache where testing of memory region along with testing of real page number bits in cache directory is to be performed comprises:

determining one or more variables required to identify a size of the cache in bytes, an associativity of the cache, a size of a page within the cache in bytes, and a size of a cache line in bytes; and

determining a total number of cache lines of the cache associated with the cache directory, a total number of congruence classes in the cache, a number of congruence classes in a page of the cache, and a total number of pages required to test each congruence class once.

9. A computer program product comprising a computer recordable medium having a computer readable program recorded thereon, wherein the computer readable program, when executed on a computing device, causes the computing device to:

retrieve a specification of a cache to be tested in order to test the real page number bits of the cache directory associated with the cache;

identify a range within a real page number address of the cache directory for performing page allocations using the specification of the cache;

generate a random value x that identifies a portion of the real page number bits to be tested;

generate a first random value y that identifies a first congruence class from a set of congruence classes within the portion of the cache to be tested;

determine if the first congruence class associated with the first random value y has been allocated a predetermined number of times; and

responsive to the first congruence class associated with the first random value y failing to be allocated the predetermined number of times, allocate one page size of memory for the first congruence class associated with the first random value y; and

increment a first allocation value associated with the first congruence class by a value of 1.

10. The computer program product of claim 9, wherein the computer readable program further causes the computing device to:

responsive to the first congruence class associated with the first random value y being allocated the predetermined number of times, increment a failure counter by a value of 1;

determine if the failure counter is equal to a predetermined value;

responsive to the failure counter failing to equal the predetermined value, generate a second random value y that identifies a second congruence class from the set of congruence classes within the portion of the cache to be tested;

determine if the second congruence class associated with the second random value y has been allocated the predetermined number of times; and

responsive to the second congruence class associated with the second random value y failing to be allocated the predetermined number of times, allocate one page size of memory for the second congruence class associated with the second random value y; and

increment a second allocation value associated with the second congruence class by the value of 1.

11. The computer program product of claim 10, wherein the computer readable program further causes the computing device to:

responsive to the failure counter equaling the predetermined value, generate a third random value y;

identify a next congruence class that fails to be allocated the predetermined number of times;

identify a next value y associated with the next congruence class;

determine if the next congruence class has been allocated the predetermined number of times using the associated next value y; and

responsive to the next congruence class failing to be allocated the predetermined number of times, allocate one page size of memory for the next congruence class associated with the third random value y; and

increment a next allocation value associated with the next congruence class by the value of 1.

12. The computer program product of claim 11, wherein the computer readable program to identify the next congruence class that fails to be allocated the predetermined number of times further causes the computing device to:

scan each congruence class in the set of congruence classes in order from a third congruence class associated with the third random value y to a maximum congruence set size of the set of congruence classes; and

identify a congruence class that fails to be allocated the predetermined number of times in order from the third congruence class associated with the third random value y to the maximum congruence set size of the set of congruence classes.

13. The computer program product of claim 12, wherein the computer readable program further causes the computing device to:

responsive to a failure to identify the congruence class that fails to be allocated the predetermined number of times in order from the third congruence class associated with the third random value y to the maximum congruence set size of the set of congruence classes, scan to identify the congruence class that fails to be allocated the predetermined number of times from an initial congruence class in the set of congruence classes up to but not including the third congruence class.

14. The computer program product of claim 9, wherein the computer readable program further causes the computing device to:

repeat the computer readable program to generate a random value of y, determine, allocate, and increment for all congruence classes in the set of congruence classes until all of the congruence classes have been allocated the predetermined number of times.

15. An apparatus, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

retrieve a specification of a cache to be tested in order to test the real page number bits of the cache directory associated with the cache;

identify a range within a real page number address of the cache directory for performing page allocations using the specification of the cache;

generate a random value x that identifies a portion of the real page number bits to be tested;

generate a first random value y that identifies a first congruence class from a set of congruence classes within the portion of the cache to be tested;

determine if the first congruence class associated with the first random value y has been allocated a predetermined number of times; and

responsive to the first congruence class associated with the first random value y failing to be allocated the predetermined number of times, allocate one page size of memory for the first congruence class associated with the first random value y; and

increment a first allocation value associated with the first congruence class by a value of 1.

16. The apparatus of claim 15, wherein the instructions further cause the processor to:

responsive to the first congruence class associated with the first random value y being allocated the predetermined number of times, increment a failure counter by a value of 1;

determine if the failure counter is equal to a predetermined value;

responsive to the failure counter failing to equal the predetermined value, generate a second random value y that identifies a second congruence class from the set of congruence classes within the portion of the cache to be tested;

determine if the second congruence class associated with the second random value y has been allocated the predetermined number of times; and

responsive to the second congruence class associated with the second random value y failing to be allocated the predetermined number of times, allocate one page size of memory for the second congruence class associated with the second random value y; and

increment a second allocation value associated with the second congruence class by the value of 1.

17. The apparatus of claim 16, wherein the instructions further cause the processor to:

responsive to the failure counter equaling the predetermined value, generate a third random value y;

identify a next congruence class that fails to be allocated the predetermined number of times;

identify a next value y associated with the next congruence class;

determine if the next congruence class has been allocated the predetermined number of times using the associated next value y; and

responsive to the next congruence class failing to be allocated the predetermined number of times, allocate one page size of memory for the next congruence class associated with the third random value y; and

increment a next allocation value associated with the next congruence class by the value of 1.

18. The apparatus of claim 17, wherein the instructions to identify the next congruence class that fails to be allocated the predetermined number of times further cause the processor to:

scan each congruence class in the set of congruence classes in order from a third congruence class associated with the third random value y to a maximum congruence set size of the set of congruence classes; and

identify a congruence class that fails to be allocated the predetermined number of times in order from the third congruence class associated with the third random value y to the maximum congruence set size of the set of congruence classes.

19. The apparatus of claim 18, wherein the instructions further cause the processor to:

responsive to a failure to identify the congruence class that fails to be allocated the predetermined number of times in order from the third congruence class associated with the third random value y to the maximum congruence set size of the set of congruence classes, scan to identify the congruence class that fails to be allocated the predetermined number of times from an initial congruence class in the set of congruence classes up to but not including the third congruence class.

20. The apparatus of claim 15, wherein the instructions further cause the processor to:

repeat the instructions to generate a random value of y, determine, allocate, and increment for all congruence classes in the set of congruence classes until all of the congruence classes have been allocated the predetermined number of times.