hansen@mips.UUCP (Craig Hansen) (04/21/87)
I've been reading two publications from National, one the infamous "Series 32000: NS32532 Competitive Comparison" that lists the eight separate patent applications we've already heard about, the other titled "Series 32000: NS32532 Technical Introduction." The feature that most caught my eye was that of branch prediction, for which I quote from the "Technical Introduction": The selection is based on the branch condition and direction; forward branches are predicted as taken, backward branches as non-taken. Well, I don't see how the branch prediction can depend on the branch condition, since waiting for the condition corresponds to no branch prediction at all. (Certainly novel and non-obvious...) But when I was a young sprout, they always told me that backward branches often represented loops and were most frequently taken. Forward branches often represent conditional expressions, and are more ambivalent. As far as I can see from the description, there is no prediction based on past behaviour from previous invocations of the branch instruction. If the description in National's literature is entirely accurate, the branch prediction scheme used is seriously broken and should predict the wrong answer more often than the right answer. Then again, if National hasn't seen silicon yet, and uses the opportunity to fix it now, I may have just saved them a few tens of thousands of dollars in wafer costs and hundreds in otherwise lost revenue.... -- Craig Hansen Manager, Architecture Development MIPS Computer Systems, Inc. ...decwrl!mips!hansen
amos@instable.UUCP (04/22/87)
Looks like the person who wrote the brochure about the 32532 didn't
look at the spec; anyway it's certain that:
1. The whole point of branch prediction is not waiting for the condition
codes; therefore the prediction cannot, and does not, rely on them.
2. Forward branches are predicted as not taken, backward branches are
predicted as taken, no matter who says otherwise. (We have tried
several methods of state machines, caches, etc. and found out that
this simple-minded method had the best ratio of relative performance
increase vs. cost in chip area and overhead.)
--
Amos Shapir
National Semiconductor (Israel)
6 Maskit st. P.O.B. 3007, Herzlia 46104, Israel Tel. (972)52-522261
amos%nsta@nsc.com {hplabs,pyramid,sun,decwrl} 34.48'E 32.10'Nroger@nsc.nsc.com (Roger Thompson) (04/23/87)
In article <324@dumbo.UUCP>, hansen@mips.UUCP (Craig Hansen) writes: > > The selection is based on the branch condition and > direction; forward branches are predicted as taken, > backward branches as non-taken. > YES the brochure has misplaced a "non" in the above paragraph. Reverse the usage. > Well, I don't see how the branch prediction can depend on the branch > condition, since waiting for the condition corresponds to no branch > prediction at all. (Certainly novel and non-obvious...) The condition factor that is used is that which is specified by the opcode, not the actual result from the operation being tested. The concept is that the predictor has an algorithm that has multiple inputs. Under certain conditions, the predictor determines one answer or the other. The prediction should not be confussed with the result. Our prediction algorithm is accurate to 70 - 80%. > > But when I was a young sprout, they always told me that backward branches > often represented loops and were most frequently taken. Forward branches > often represent conditional expressions, and are more ambivalent. > Agreed.
jfh@killer.UUCP (04/28/87)
In article <324@dumbo.UUCP>, hansen@mips.UUCP (Craig Hansen) writes: [ Stuff ] > > The feature that most caught my eye was that of branch prediction, > for which I quote from the "Technical Introduction": > > The selection is based on the branch condition and > direction; forward branches are predicted as taken, > backward branches as non-taken. > [ Alot more stuff ] I too had wondered about this branch prediction mess, and I agree with this poster about this being the WRONG way to do things. I was prepared to make the argument that trying to find the branch direction would require fetching the offset (assuming relative branches), which would obligate the processor to a possibly unneeded fetch, along with running this offset through some logic (one or two more micro instructions) to figure out the direction, which sounded like a real loser. However, I suspect that someone at AMD would tell me how wonderfully pipelined their machine was and so on ... [ Now for the revised posting ] Craig stated that, like the rest of us, he was raised to believe that backwards branches make nice branches after while loops and such, and forward branches make nice branches before if-thens. Has anyone bothered to think about adding branch instructions that tell the CPU explicitly whether or not they expect to be taken? For example, MBLEQ - most of the time branch less or equal SBLEQ - seldom branch less or equal Compilers would be able to pick the instructions they wanted. (Speaking of patents, if this idea is patentable and has not yet been so, anyone but Nat-Semi can have it ... :-) :-) so long as I get credit ... :-) :-) - John (jfh@killer.UUCP) Disclaimer: No disclaimer. Whatcha gonna do, sue me?
adb@homxa.UUCP (A.BERENBAUM) (05/06/87)
In article <809@killer.UUCP>, jfh@killer.UUCP (John Haugh) writes: > [ Stuff ] > Has anyone bothered to think about adding branch instructions that tell > the CPU explicitly whether or not they expect to be taken? For example, > > MBLEQ - most of the time branch less or equal > SBLEQ - seldom branch less or equal > > Compilers would be able to pick the instructions they wanted. (Speaking of > patents, if this idea is patentable and has not yet been so, anyone but > Nat-Semi can have it ... :-) :-) so long as I get credit ... :-) :-) > > - John (jfh@killer.UUCP) The CRISP Microprocessor has a single flag bit (call it True/False), and four conditional branch instructions: if True jump, predicted taken if True jump, predicted not taken if False jump, predicted taken if False jump, predicted not taken I think this covers what you ask for, but I'm sorry, you don't get credit. There's a paper in the 1987 COMPCON about compiling for CRISP that discusses how a compiler can exploit the prediction bits (it can do quite well -- we get correct prediction of nearly 90% as I recall). Alan Berenbaum, AT&T-something-or-other research!adb
pdg@ihdev.ATT.COM (Joe Isuzu) (05/06/87)
In article <809@killer.UUCP> jfh@killer.UUCP (John Haugh) writes: >Craig stated that, like the rest of us, he was raised to believe that >backwards branches make nice branches after while loops and such, and >forward branches make nice branches before if-thens. Has anyone bothered >to think about adding branch instructions that tell the CPU explicitly >whether or not they expect to be taken? For example, > > MBLEQ - most of the time branch less or equal > SBLEQ - seldom branch less or equal The AT&T CRISP processor does this, with instructions like ifFjmpn, ifFjmpy (if false, expect to jump no or yes) ifTjmpn, ifTjmpy (if true, expect to jump no or yes) These take 0 cycles for a correct prediction, and a max of 3 cycles for an incorrect prediction (-1 cycle per instruction between the compare and the branch). For more info, see any of the CRISP articles from IEEE Compcon '87. -- Paul Guthrie ihnp4!ihdev!pdg This Brain left intentionally blank.