Efficient sequential consistency via conflict ordering
Changhui Lin
UC Riverside

SC is easy to understand, but hard to do with good performance.

Implementing it: in-window speculation: speculate on load->load
reordering.

Post-retirement speculation: speculate on store->load/store
reordering.

Draw a graph with instructions for nodes, program order for edges, and
an edge from A to B if A and B conflict and A happened before B on
this run.  Then there is an SC violation iff there is a cycle.
Therefore need to run cycle checker when retiring instructions.

Predecessors of instruction -> all operations which appear before it
in global memory order.  Conflict order: allow a2 to complete if there
are no uncompleted predecessors of a1 which conflict with it (a1 ==
immediate program order predecessor of a2, and a1 is itself
incomplete).

New hardware: write-list registers.  <didn't understand his explanation
of what those were for>

Stores have to check for conflict in write-list registers when
committing.

How to determine predecessors?

-- Write miss: get from cache directory <?>

<I don't have any idea what he's talking about>


-----------------------------------