Racey: A Stress Test for Deterministic Execution

Racey: A Stress Test for Deterministic Execution

Computer Sciences Department
University of Wisconsin-Madison

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;
  }

Each thread races with other concurrent threads to:

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 num = sig[threadId];
    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;
    sig[threadId] = 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:

Slightly updated 2009 code (recommended, e.g., compiles under linux)
Original 2002 code

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.