Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!lll-lcc!well!msudoc!mtu!pop
From: pop@mtu.UUCP
Newsgroups: comp.arch
Subject: Re: Branch prediction in the 532
Message-ID: <269@mtu.UUCP>
Date: Thu, 30-Apr-87 20:29:57 EDT
Article-I.D.: mtu.269
Posted: Thu Apr 30 20:29:57 1987
Date-Received: Sat, 2-May-87 14:04:37 EDT
References: <324@dumbo.UUCP> <165100008@uiucdcsb> <5662@shemp.UCLA.EDU>
Reply-To: pop@mtu.UUCP (Dave Poplawski)
Organization: Michigan Technological University, Houghton, MI
Lines: 40

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:
>>
>>	1) Put an extra bit in the instruction indicating which way the branch
>>	   will probably go.  This is a compile-time prediction.
>>
>>	2) Keep a record of past branches, i.e. run-time prediction.   
>>
>>Though I've heard of examples of machines with each scheme, I've never
>>seen any studies of their efficiency.
>>
>>Arch D. Robison
>>University of Illinois at Urbana-Champaign
>>	

You might also check out my article about branch prediction which combines
the two:

%A D. A. Poplawski
%T Low cost branch prediction
%J Proceedings of the Twenty-Third Allerton Conference on Communication,
   Control and Computing
%P 979-983
%D October, 1985

Basically the idea is to monitor the execution of a program for a (very) few
data sets, recording the number of times each unique branch instruction
either branched and didn't branch, then predict all future executions of the
same branch instruction according to the dominate outcome.  It turns out that
while there are always a few branch instructions which are unpredictable (i.e,
branch half the time and don't branch half the time), the VAST majority are
very predictible, and from my observations of programs like the C compiler,
which you probably wouldn't think has very predictable branching behavior,
the prediction accuracy is very high, even when just one sample of the
execution is made and then used on other VERY different data sets.
Basically the prediction accuracies are comparable with dynamic (i.e.,
expensive) schemes while the implementation cost is comparable with static
(i.e., cheap) schemes.