Deterministic test program generation for evaluating cache coherency
A cache coherency test process is provided which includes deterministically generating a test program to test cache coherency in a computing environment including at least one processing unit. The deterministically generating includes producing cache state test sequences using graph traversal, where the cache state test sequences include closed paths of cache-affecting operations, and where using graph traversal includes traversing one or more state graphs with nodes representing cache states and edges representing operations producing respective cache state transitions in the at least one processing unit. Further, the deterministically generating includes pruning the cache state test sequences, using closed-path graph analysis, to generate the test program, where the test program has a selected cache coherence test coverage using chosen cache state test sequences obtained from pruning the cache state test sequences. Further, the process includes initiating executing of the test program in the computing environment to test the cache coherency.
1 . A computer-implemented method of facilitating processing within a computing environment, the computer-implemented method comprising:
deterministically generating a test program to test cache coherency in the computing environment, the computing environment including multiple processing units, and the deterministically generating including:
generating a weighted multigraph to facilitate producing cache state test sequences, wherein the weighted multigraph comprises nodes representing cache states and connecting edges representing operations producing respective cache state transitions for the multiple processing units, and generating the weighted multigraph includes assigning weight priorities to cache state transitions based on whether the cache state transitions can be reached via interaction between processing units of the multiple processing units;
producing the cache state test sequences using graph traversal of the weighted multigraph, wherein the cache state test sequences comprise closed paths of cache-affecting operations; and
pruning the cache state test sequences, using closed-path graph analysis and the weight priorities, to generate the test program, wherein the test program has a selected cache coherence test coverage using chosen cache state test sequences obtained from pruning the cache state test sequences; and
initiating executing of the test program in the computing environment to test the cache coherency.
2 . The computer-implemented method of claim 1 , wherein the assigning includes assigning higher weight priority to cache state transitions which can be reached via interaction between processing units of the multiple processing units in order to process those cache state transitions before other cache state transitions of the weighted multigraph in obtaining the chosen cache state test sequences for the test program.
3 . The computer-implemented method of claim 2 , wherein generating the weighted multigraph further comprises generating one or more forest of dependency graphs for use in the assigning of the weight priorities to the connecting edges of the weighted multigraph, where each node of the one or more forest of dependency graphs represents a cache state transition, and a connecting edge from one node to another node indicates that the cache state transition in one processing unit of the multiple processing units causes a cache state transition in another processing unit of the multiple processing units.
4 . The computer-implemented method of claim 3 , further comprising:
identifying the closed paths of cache-affecting operations from the weighted multigraph; and
wherein the pruning of the cache state test sequences further comprises:
determining a total weight of each closed path of cache-affecting operations of the cache state test sequences; and
processing the identified closed paths in descending order of the determined total weights in generating the test program.
5 . The computer-implemented method of claim 4 , wherein processing the identified closed paths comprises, for a selected closed path of the identified closed paths, identifying any secondary transitions of the selected closed path in the other processing unit, and using graph coloring processing to facilitate reprioritizing a processing order of the identified closed paths, the graph coloring processing producing a graph with nodes representing closed paths and connecting edges representing secondary paths generated as a result of processing the closed paths.
6 . The computer-implemented method of claim 1 , wherein the selected cache coherence test coverage ensures that executing the test program generates all desired cache state transitions in the computing environment for testing the cache coherency.
7 . The computer-implemented method of claim 1 , further comprising:
identifying, based on executing the test program in the computing environment, a cache coherency issue within the computing environment; and
initiating a cache coherency-related production change to the computing environment to generate a modified computing environment with a cache-related modification to address the identified cache coherency issue.
8 . The computer-implemented method of claim 7 , further comprising:
initiating executing of another test program in the modified computing environment to test cache coherency of the modified computing environment.
9 . A computer system for facilitating processing within a computing environment, the computer system comprising:
a memory; and
at least one processor in communication with the memory, wherein the computer system is configured to perform a method, the method comprising:
deterministically generating a test program to test cache coherency in the computing environment, the computing environment including multiple processing units, and the deterministically generating including:
generating a weighted multigraph to facilitate producing cache state test sequences, wherein the weighted multigraph comprises nodes representing cache states and connecting edges representing operations producing respective cache state transitions for the multiple processing units, and generating the weighted multigraph includes assigning weight priorities to cache state transitions based on whether the cache state transitions can be reached via interaction between processing units of the multiple processing units;
producing the cache state test sequences using graph traversal of the weighted multigraph, wherein the cache state test sequences comprise closed paths of cache-affecting operations; and
pruning the cache state test sequences, using closed-path graph analysis and the weight priorities, to generate the test program, wherein the test program has a selected cache coherence test coverage using chosen cache state test sequences obtained from pruning the cache state test sequences; and
initiating executing of the test program in the computing environment to test the cache coherency.
10 . The computer system of claim 9 , wherein the assigning includes assigning higher weight priority to cache state transitions which can be reached via interaction between processing units of the multiple processing units in order to process those cache state transitions before other cache state transitions of the weighted multigraph in obtaining the chosen cache state test sequences of the test program.
11 . The computer system of claim 10 , wherein generating the weighted multigraph further comprises generating one or more forest of dependency graphs for use in the assigning of the weight priorities to the connecting edges of the weighted multigraph, where each node of the one or more forest of dependency graphs represents a cache state transition, and a connecting edge from one node to another node indicates that the cache state transition in one processing unit of the multiple processing units causes a cache state transition in another processing unit of the multiple processing units.
12 . The computer system of claim 11 , further comprising:
identifying the closed paths of cache-affecting operations from the weighted multigraph; and
wherein the pruning of the cache state test sequences further comprises:
determining a total weight of each closed path of cache-affecting operations of the cache state test sequences; and
processing the identified closed paths in descending order of the determined total weights in generating the test program.
13 . The computer system of claim 12 , wherein processing the identified closed paths comprises, for a selected closed path of the identified closed paths, identifying any secondary transitions of the selected closed path in the other processing unit, and using graph coloring processing to facilitate reprioritizing a processing order of the identified closed paths, the graph coloring processing producing a graph with nodes representing closed paths and connecting edges representing secondary paths generated as a result of processing the closed paths.
14 . The computer system of claim 9 , wherein the selected cache coherence test coverage ensures that executing the test program generates all desired cache state transitions in the computing environment for testing the cache coherency.
15 . A computer program product for facilitating processing within a computing environment, the computer program product comprising:
one or more computer readable storage media and program instructions collectively stored on the one or more computer readable storage media readable by at least one processer to:
deterministically generate a test program to test cache coherency in the computing environment, where the computing environment includes multiple processing units, and the deterministically generating includes:
generating a weighted multigraph to facilitate producing cache state test sequences, wherein the weighted multigraph comprises nodes representing cache states and connecting edges representing operations producing respective cache state transitions for the multiple processing units, and generating the weighted multigraph includes assigning weight priorities to cache state transitions based on whether the cache state transitions can be reached via interaction between processing units of the multiple processing units;
producing the cache state test sequences using graph traversal of the weighted multigraph, wherein the cache state test sequences comprise closed paths of cache-affecting operations; and
pruning the cache state test sequences, using closed-path graph analysis and the weight priorities, to generate the test program, wherein the test program has a selected cache coherence test coverage using chosen cache state test sequences obtained from pruning the cache state test sequences; and
initiate executing of the test program in the computing environment to test the cache coherency.
16 . The computer program product of claim 15 , wherein the assigning includes assigning higher weight priority to cache state transitions which can be reached via interaction between processing units of the multiple processing units in order to process those cache state transitions before other cache state transitions of the weighted multigraph in obtaining the chosen cache state test sequences of the test program.
17 . The computer program product of claim 16 , further comprising:
identifying the closed paths of cache-affecting operations from the weighted multigraph; and
wherein the pruning of the cache state test sequences further comprises:
determining a total weight of each closed path of cache-affecting operations of the cache state test sequences; and
processing the identified closed paths in descending order of the determined total weights in generating the test program.