MemTest86 Test Algorithms
MemTest86 uses two algorithms that provide a reasonable approximation of the ideal test strategy above. The first of these strategies is called moving inversions. The moving inversion test works as follows:
- Fill memory with a pattern
-
Starting at the lowest address
- check that the pattern has not changed
- write the patterns complement
- increment the address
- repeat
-
Starting at the highest address
- check that the pattern has not changed
- write the patterns complement
- decrement the address
- repeat
This algorithm is a good approximation of an ideal memory test but there are some limitations. Most high density chips today store data 4 to 16 bits wide. With chips that are more than one bit wide it is impossible to selectively read or write just one bit. This means that we cannot guarantee that all adjacent cells have been tested for interaction. In this case the best we can do is to use some patterns to ensure that all adjacent cells have at least been written with all possible one and zero combinations.
It can also be seen that caching, buffering and out of order execution will interfere with the moving inversions algorithm and make less effective. It is possible to turn off cache but the memory buffering in new high performance chips can not be disabled. To address this limitation a new algorithm I call Modulo-X was created. This algorithm is not affected by cache or buffering. The algorithm works as follows:
-
For starting offsets of 0 - 20 do
- write every 20th location with a pattern
- write all other locations with the patterns complement
- repeat above one or more times
- check every 20th location for the pattern
This algorithm accomplishes nearly the same level of adjacency testing as moving inversions but is not affected by caching or buffering. Since separate write passes (1a, 1b) and the read pass (1c) are done for all of memory we can be assured that all of the buffers and cache have been flushed between passes. The selection of 20 as the stride size was somewhat arbitrary. Larger strides may be more effective but would take longer to execute. The choice of 20 seemed to be a reasonable compromise between speed and thoroughness.
