Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!uwvax!cottage!lm
From: lm@cottage.WISC.EDU (Larry McVoy)
Newsgroups: comp.arch
Subject: Re: Branch prediction in the 532
Message-ID: <3508@spool.WISC.EDU>
Date: Fri, 1-May-87 12:28:11 EDT
Article-I.D.: spool.3508
Posted: Fri May  1 12:28:11 1987
Date-Received: Sat, 2-May-87 16:33:07 EDT
References: <324@dumbo.UUCP> <165100008@uiucdcsb> <5662@shemp.UCLA.EDU> <269@mtu.UUCP>
Sender: news@spool.WISC.EDU
Reply-To: lm@cottage.WISC.EDU (Larry McVoy)
Organization: U of Wisconsin CS Dept
Lines: 28

In article <269@mtu.UUCP> pop@mtu.UUCP (Dave Poplawski) writes:
>In article <5662@shemp.UCLA.EDU> marc@CS.UCLA.EDU (Marc Tremblay) writes:
>>In article <165100008@uiucdcsb> robison@uiucdcsb.cs.uiuc.edu writes:
>>>
>>>Are there any good papers on branch prediction?  I've seen two schemes:

I don't know whether anyone mentioned this one or not, but a very complete
paper is 

    A Study of Branch Prediction Strategies by J.E. Smith, appeared
    in IEEE ??? in 1981.

7 different strategies, 6 "real", static [i.e., all branches taken], and
dynamic [i.e., cache recently taken branches] are explained, simulated, and
the results compared.  The bottom line from this paper is that just about ANY
branch prediction is a win (lowest is 35 % hit ratio, with average in the
80's) and that some very simple branch predictions are extremely effective.

The one I liked the best is a dynamic one that maintains an extra bit in
the icache that is set iff the cache entry is a branch instruction that was
taken on the last execution.  Quite easy to implement, stingy on chip real
estate, and on the average was right about 90.3% of the time (highest 98.9,
lowest was 76.1).

Mail me if you need more.
Larry McVoy 	        mcvoy@rsch.wisc.edu  or  uwvax!mcvoy

"What a wonderful world it is that has girls in it!"