Mark D. Hill
Computer Sciences Department
R&D Engineer at VMware
December 2008; updated January 2009
http://www.cs.wisc.edu/~markhill/racey.html
University of Wisconsin-Madison
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:
sig[threadId]
,
mix
values in an integer array
m[...].value
(padded to have one element per cache block),
sig[threadId]
,
#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:
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.