Racey: A Stress Test for Deterministic Execution

Computer Sciences Department

Min Xu

R&D Engineer at VMware

December 2008; updated January 2009

http://www.cs.wisc.edu/~markhill/racey.html

This page links to a C program called `RACEY`. `RACEY` is useful for testing methods for deterministic execution or record/reply. `RACEY` computes a signature whose value is exceedingly sensitive to the order of unsynchronized data races. On a non-deterministic system, each of tens of thousands of `RACEY` runs produces a unique signature value.

To test an allegedly deterministic system, run `RACEY` so that the instructions of multiple threads run concurrently. Repeat many times and, if possible, intentionally perturb execution timing. If `RACEY` ever produces different signature values, then the system is non-deterministic. If `RACEY` repeatedly produces the same signature value, your system may be deterministic.

The kernel of `RACEY` uses a multiplicative congruential pseudo-random number generator [Knu] named `mix()`:

```
#define   PRIME1   103072243
#define   PRIME2   103995407
unsigned mix(unsigned i, unsigned j) {
return (i + j * PRIME2) % PRIME1;
}
```
• take its component of a signature `sig[threadId]`,
• `mix` values in an integer array `m[...].value` (padded to have one element per cache block),
• obtain a new `sig[threadId]`,
• and repeat many times.
```
#define   MAX_LOOP 1000
#define   MAX_ELEM 64
for(i = 0 ; i < MAX_LOOP; i++) {
unsigned index1 = num%MAX_ELEM;
unsigned index2;
num = mix(num, m[index1].value);
index2 = num%MAX_ELEM;
num = mix(num, m[index2].value);
m[index2].value = num;
}
```

Since `mix()` is exceedingly NON-associative, any reordering of conflicting accesses (reads/writes or writes/writes) will change the final signature value with high probability.

`RACEY` was developed in 2002 to test the Flight Data Recorder [FDR]. It was written by Min Xu, then a Ph.D. student at Wisconsin. It is based on ideas of Prof. Mark D. Hill with number theory advice from Prof. Eric Bach, both at Wisconsin.

We hereby offer `RACEY` as public domain software. To download `racey.c`, click:

If you use it and find it valuable, please cite us with something like: We tested with RACEY [FDR, HX].

References

[FDR] Min Xu, Rastislav Bodik and Mark D. Hill, A "Flight Data Recorder" for Enabling Full-system Multiprocessor Deterministic Replay, International Symposium on Computer Architecture (ISCA), June 2003.

[HX] Mark D. Hill and Min Xu, Racey: A Stress Test for Deterministic Execution, web page: http://www.cs.wisc.edu/~markhill/racey.html.

[Knu] Donald E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, third edition, 1997.