lindsay@gandalf.cs.cmu.edu (Donald Lindsay) (02/20/89)
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 --
aglew@mcdurb.Urbana.Gould.COM (02/20/89)
>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. Well, from the academic side Berkeley's HPSm project _built_ a microprocessor with Tomasulo scheduling, and backup by copying of the register file. The principals have since left Berkeley: Wen-Mei Hwu, my advisor, is at Illinois, and Yale Patt is going somewhere else in the midwest. Myself, I'm flogging a hardware renaming technique that is considerably less expensive than backing up the entire register file. Industrially - who knows? :-) Andy "Krazy" Glew aglew@urbana.mcd.mot.com uunet!uiucdcs!mcdurb!aglew Motorola Microcomputer Division, Champaign-Urbana Design Center 1101 E. University, Urbana, Illinois 61801, USA. My opinions are my own, and are not the opinions of my employer, or any other organisation. I indicate my company only so that the reader may account for any possible bias I may have towards our products.
marc@oahu.cs.ucla.edu (Marc Tremblay) (02/22/89)
In article <28200280@mcdurb> aglew@mcdurb.Urbana.Gould.COM writes: >Well, from the academic side Berkeley's HPSm project _built_ a >microprocessor with Tomasulo scheduling, and backup by copying >of the register file. Did they actually fabricate it? > Myself, I'm flogging a hardware renaming technique that is >considerably less expensive than backing up the entire register >file. We have designed a mechanism that "rolls back" the register file without much area penalty. The register file is not replicated, instead the "writes" into the register file are delayed for a few cycles until there is no more need to retrieve them. The register address of the writes is also stored in the "delayed-write buffer" allowing subsequent "reads" to access the up-to-date value of a register. You can imagine the mechanism as "forwarding" for multiple registers. The delayed-write buffer can be invalidated partially of completely in a single cycle. If more information is needed I can post or e-mail the references. Marc Tremblay marc@CS.UCLA.EDU Computer Science Department, UCLA