Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!rutgers!rochester!pt.cs.cmu.edu!gandalf.cs.cmu.edu!lindsay
From: lindsay@gandalf.cs.cmu.edu (Donald Lindsay)
Newsgroups: comp.arch
Subject: Bus History Units
Keywords: bus transactions, execution transactions
Message-ID: <4316@pt.cs.cmu.edu>
Date: 20 Feb 89 04:33:22 GMT
Organization: Carnegie-Mellon University, CS/RI
Lines: 44

There was recently a discussion here about memory operations that may
occur out of order. Some pseudocode for the CDC6600 illustrated this:

>	X7 = X0/X1
>	memloc = X7
>	if(X3 < 0) goto LL
>	...
>LL	memloc = X6
>
>But the timing is such that if X3 < 0, then the "second" store is 
>completed before the "first" store begins.

There are three ways out of this: 
 - compilers (elegant but limited to compile-time knowledge)
 - interlocks that may stall instruction issue (simple conceptual model
	but interlocks unnecessarily often)
 - a bus history unit.

The history unit watches the CPU's data port to memory, and remembers the
activity. By using content-addressable techniques (and issue-order tags),
the unit can detect when the execution has been over-exuberant.

From a distance, the fixup looks pretty easy. If two writes were
reversed, then simply repeat the one that happened first (or prevent the
second one from being clocked out). Then you notice that read-write
reversal implies undoing computations. How to recover the old register
state (etc) ?

Well, someone out there is doing it. They plan to make it all easier by
having "snaphot" register banks that remember the old register states.
Neat stuff.

What's that you say? I/O devices? Multiprocessors? What if some logic out
there in busland has seen the data that you're trying to take back?

Oddly enough, someone (else) is building a history unit BECAUSE of that.
To the best of my knowledge, they don't have out-of-order problems. What
they do have, is a machine that is so big that answers may take a while
to propagate across it. So, they use "optimistic" code, and their history
units provide atomic transactions. If an answer turns out bad, the memory
writes are undone, and the local program counter is forced to the "else"
of the last "start bus transaction".
-- 
Don		D.C.Lindsay 	Carnegie Mellon   Computer Science
--