Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!pyramid!prls!mips!hansen
From: hansen@mips.COM (Craig Hansen)
Newsgroups: comp.arch
Subject: Re: The advantages of FREQUENCY
Message-ID: <1484@mips.mips.COM>
Date: 4 Feb 88 01:43:57 GMT
References: <8801142212.AA04401@decwrl.dec.com> <3783@hall.cray.com>
Lines: 54

In article <3783@hall.cray.com>, dtj@hall.cray.com (Dean Johnson) writes:
> The performance benefits of FREQUENCY in large scale architectures would
> likely be very slight. In more complex architectures with significant
> instruction buffers (such as supercomputers), jumps are very expensive
> and, unless you moved the less frequent block totally out of the flow of
> the program, you would be jumping around one of the blocks either way.
> 
> If you moved the less frequent case out of the flow of the program, you
> would incur 2 jumps (to and from the block) to get back into the flow of
> the program, thus (atleast) doubling the cost of the less frequent case.

However, even though it "doubles" the cost of less frequent case, if
that case is sufficiently infrequent, it's a win. Take the following
oversimplified model:

assume the time for non-taken branch = 1 cycle
           time for taken branch = n cycles

for an if-then-else clause that executes the "then" clause w/
frequency f: [we assume for an in-line if-then-else, that if the
"then" clause is executed, you have one non-taken branch and one taken
branch; if the "else" clause is executed, you have one taken branch,
which falls through. For the out-of-line case, the "then" clause has
two taken branches, and the "else" clause has one non-taken branch.]

	in-line cost = f*(1+n) + (1-f)*n = f+n
	out-of-line cost = f*2*n + (1-f)*1 = f*(2*n-1) + 1

	out-of-line is better if:
		f*(2*n-1) + 1 < f + n
	==>	f*(2*n-2) < n - 1
	==>	f < (n-1)/(2*n-2)   [if n > 1]
	==>	f < 1/2             [if n > 1]

So out of line execution of the "then" clause is better if:

	n < 1: f > .5
	n = 1: same for any f
	n > 1: f < .5

For n > 1, the benefit is:

	f + n - f*(2*n-1) - 1 = f*(2-2*n) + n - 1
			      = 2*f*(1-n) - (1-n)
			      = (1-n) * (2*f - 1)
			      = (n-1) * (1 - 2*f)

E.g.: f = .25, n = 4, in-line cost = 4.25, out-of-line cost
is .25*7 + 1 = 2.75, average benefit is 1.5 cycles.

-- 
Craig Hansen
Manager, Architecture Development
MIPS Computer Systems, Inc.
...{ames,decwrl,prls}!mips!hansen or hansen@mips.com   408-991-0234