Systematic tests

• MP: Message passing
• SB: Store buffer forwarding (sometimes called Dekker’s example)
• LB: Load buffering
• IRIW: Independent Reads of Independent Writes
• WRC: Write to Read Causality
• RWC: Read to Write Causality
• ISA2: Second example from POWER documentation
• R
• S
• 2+2W
• WWC
• WRW+2W
• WRW+WR
• WRR+2W
• PPO

These tests are generated using the diycross tool, a variant of diy. They are systematic variations of a number of families, inserting different choices of barriers or dependencies. The families themselves are also systematic, as follows.

Consider tests built from a cycle of edges of the following four kinds: program order (po) (perhaps with barriers or dependencies); reads-from (rf) edges, from a write to a read that reads from it; from-reads (fr) edges, from a read to coherence-successors of the write it reads from; and coherence (co) edges, from a write to a coherence-later write to the same address. In the diagrams below reads from the initial state are shown as rf edges from a red dot; the fr edges are not shown explicitly but go from such reads to the write that is to the same address.

There are six two-thread cycles with four edges, as in the left-hand column of the table below: test families MP, SB, LB, R, S, and 2+2W. MP and SB are the classic ‘message-passing’ and ‘store-buffering’ tests.

For all those test families except LB and R, there is an obvious three-thread analogue in which the initial write is replaced by a read from a write pulled out to another thread, as in the middle column below. The analogues of MP and SB are the classic WRC and RWC tests (as in Boehm and Adve, PLDI 2008). For R there are two three-thread analogues, pulling back the writes of the two threads: WRW+WR and WRR+2W.

MP: rf,fr	WRC: rf,rf,fr
SB: fr,fr	RWC: rf,fr,fr
LB: rf,rf
R: co,fr	WRW+WR: rf,co,fr	WRR+2W: rf,fr,co
S: rf,co	WWC: rf,rf,co
2+2W: co,co	WRW+2W: rf,co,co

The ISA2 family (based on the second example in the Power 2.06 ISA, illustrating B-cumulativity) is a three-thread six-edge test, which one could think of as MP with the first write pulled back along a barrier;rf path, or as WRC with the first write pulled back along a barrier edge:

ISA2: rf,rf,fr

There are many other three-thread six-edge tests, some of which we have explored but do not give here.

The IRIW family is a four-thread six-edge test:

IRIW: rf,fr,rf,fr

All the tests above have at most one edge on each thread. The PPO family (tests of preserved program order) are variations of MP with a barrier on the writing thread and various combinations of edges on the reading thread.

MP: Message passing

SB: Store buffer forwarding (sometimes called Dekker’s example)

LB: Load buffering

IRIW: Independent Reads of Independent Writes

WRC: Write to Read Causality

RWC: Read to Write Causality

ISA2: Second example from POWER documentation

R

S

2+2W

WWC

WRW+2W

WRW+WR

WRR+2W

PPO