interrupting for overflow and loop termination

CASTalk.com
Discussion of DSP, FPGA, storage and embedded system.

FAQ

Memberlist

Profile

interrupting for overflow and loop termination Goto page Previous 1, 2, 3, 4, 5, 6, 7 Next

CASTalk.com Forum Index -> Computer Architecture

Author

Message

Terje Mathisen
Guest

Posted: Sat Sep 10, 2005 3:22 pm Post subject: Re: interrupting for overflow and loop termination

andrewspencers@yahoo.com wrote:

Quote:

My argument is essentially this:
Interrupt-triggered events are better than polling-triggered events,
assuming that the cost of setting up the interrupt is less than the
total cost of all the polling repetitions.

The cost of setting up _and_ the cost of actually taking it!

Quote:

Compare-and-branch inside a loop is a poll of the loop-exiting
condition.
Thus for a high-repetition loop, an interrupt-triggered exit is better
than a compare-and-branch exit.

It is _not_ better:

a) If the loop count is high, the loop branch will always be correctly
predicted, except for the loop exit, right?

b) If the loop count is stored in a fixed register, like ECX for an x86
LOOP instruction, or otherwise designated, then the number of branch
misses should be zero instead of one.

c) The loop count register is often used inside the loop anyway, so you
must use alu resources to update it.

d) How do you propose to generate loops unless you have some kind of (in
your case unconditional) branch at the bottom?

e) Modern cpus are very seldom integer alu resource constrained, so even
when you have no other need for the loop count register, the actual
update is effectively free.

OTOH, ints _can_ be a win in other situations, specifically when they
are used to guard against/handle really exceptional situations, where
the extra overhead of a taken interrupts can be amortized over many runs
when nothing happens.

Noting my argument (e), the overhead of inserting INTO opcodes at
relevant sites in the code can be close to zero, since the cpu can treat
it like a "strongly predicted to fall through" branch, i.e. it doesn't
even need to take up any branch predictor buffer space.

Terje

--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"

Guest

Posted: Sun Sep 11, 2005 7:10 am Post subject: Re: interrupting for overflow and loop termination

Terje Mathisen wrote:

Quote:

a) If the loop count is high, the loop branch will always be correctly
predicted, except for the loop exit, right?
Right.

Quote:

c) The loop count register is often used inside the loop anyway, so you
must use alu resources to update it.
Yes, but I wasn't arguing against using a loop count register or

against updating it inside the loop; I was arguing against including
instructions inside the loop which conditionally branch based on the
value in the register. I wanted the processor to watch the register and
trigger an interrupt when it reached some target value, the same way
that the processor watches e.g. the program counter and triggers an
interrupt when it matches the value in a breakpoint register, with zero
impact on program execution speed until the interrupt is triggered.

Quote:

d) How do you propose to generate loops unless you have some kind of (in
your case unconditional) branch at the bottom?
Yes, I proposed using an unconditional branch at the bottom.

Quote:

OTOH, ints _can_ be a win in other situations, specifically when they
are used to guard against/handle really exceptional situations, where
the extra overhead of a taken interrupts can be amortized over many runs
when nothing happens.
For example, the really exceptional situation of exiting a

high-repetition loop, where the extra overhead of the interrupt can be
amortized over the many repetitions when the interrupt isn't triggered?
I.e. isn't what you wrote here actually an argument in favor of my
proposal?
But actually now I agree that your argument is correct that my proposal
is useless for normal loops, but can be useful for other situations.
But I think you mischaracterized those other situations; ints aren't
useful just because they're handling really exceptional situations, but
because they're handling _a large amount_ of exceptional situations
inside the loop. Specifically, exiting a high-repeition loop is an
exceptional situation, but the cache, branch prediction, and
speculative execution features combine to make a single test-branch (or
possibly even several of them) inside the loop effectively free, so my
interrupt proposal wouldn't gain anything. But if there are enough
test-branches inside the loop (especially if there are a bunch of inner
loops inside the loop), then the speculative execution circuitry and
possibly even the cache can get overloaded, such that test-branch
instructions are no longer free. In _this_ case, my interrupt proposal
would be useful.
And one such case is a loop (possibly a big loop with a lot of inner
loops) with a large number of integer operations each of which must
test for and handle overflows, which is generally the case with bignum
(infinite precision integer) arithmetic, which is the particular case
which prompted me to start this thread in the first place.
Another case would be a linear search for which the target string is
generally very long and there are a lot of partial matches within the
search space.
Another case, I think (but I'm too tired right now to think clearly
enough to be sure), would be a relational join algorithm.

Is my analysis accurate?

Quote:

Noting my argument (e), the overhead of inserting INTO opcodes at
relevant sites in the code can be close to zero, since the cpu can treat
it like a "strongly predicted to fall through" branch, i.e. it doesn't
even need to take up any branch predictor buffer space.
But I'm not proposing using INTO (a soft interrupt); I'm proposing

using a hard interrupt, which works the same way that breakpointing
works.

David Hopwood
Guest

Posted: Sun Sep 11, 2005 9:39 pm Post subject: Re: interrupting for overflow and loop termination

andrewspencers@yahoo.com wrote:

Quote:

But actually now I agree that your argument is correct that my proposal
is useless for normal loops, but can be useful for other situations.
But I think you mischaracterized those other situations; ints aren't
useful just because they're handling really exceptional situations, but
because they're handling _a large amount_ of exceptional situations
inside the loop. Specifically, exiting a high-repetition loop is an
exceptional situation, but the cache, branch prediction, and
speculative execution features combine to make a single test-branch (or
possibly even several of them) inside the loop effectively free, so my
interrupt proposal wouldn't gain anything. But if there are enough
test-branches inside the loop (especially if there are a bunch of inner
loops inside the loop), then the speculative execution circuitry and
possibly even the cache can get overloaded, such that test-branch
instructions are no longer free. In _this_ case, my interrupt proposal
would be useful.

If the speculative execution circuitry is "overloaded", then the same is
likely to be true of the interrupt checking under the same circumstances.
Checking for interrupts (which then need to be delivered precisely) is
not free; in terms of complexity it is similar to speculative execution.
That is, you strongly speculate that the interrupt is not taken on each
instruction, and have to recover if it is. The difference is that you need
dedicated hardware resources to check the interrupt conditions on *every*
instruction, rather than using shared resources to do it only when the
condition is relevant.

(Also, although this would be a fairly minor issue: interrupts used for
this purpose add to the state that has to be saved and restored on context
switches.)

--
David Hopwood <david.nospam.hopwood@blueyonder.co.uk>

Guest

Posted: Mon Sep 12, 2005 12:15 am Post subject: Re: interrupting for overflow and loop termination

David Hopwood wrote:

Quote:

If the speculative execution circuitry is "overloaded", then the same is
likely to be true of the interrupt checking under the same circumstances.
Checking for interrupts (which then need to be delivered precisely) is
not free; in terms of complexity it is similar to speculative execution.
That is, you strongly speculate that the interrupt is not taken on each
instruction, and have to recover if it is. The difference is that you need
dedicated hardware resources to check the interrupt conditions on *every*
instruction, rather than using shared resources to do it only when the
condition is relevant.
Yes, that makes sense. But then in that case, when you wrote in your

prior message:

Quote:

David Hopwood
Guest

Posted: Mon Sep 12, 2005 12:15 am Post subject: Re: interrupting for overflow and loop termination

andrewspencers@yahoo.com wrote:

Quote:

David Hopwood wrote:

If the speculative execution circuitry is "overloaded", then the same is
likely to be true of the interrupt checking under the same circumstances.
Checking for interrupts (which then need to be delivered precisely) is
not free; in terms of complexity it is similar to speculative execution.
That is, you strongly speculate that the interrupt is not taken on each
instruction, and have to recover if it is. The difference is that you need
dedicated hardware resources to check the interrupt conditions on *every*
instruction, rather than using shared resources to do it only when the
condition is relevant.

Yes, that makes sense. But then in that case, when you wrote in your
prior message:

OTOH, ints _can_ be a win in other situations, specifically when they
are used to guard against/handle really exceptional situations, where
the extra overhead of a taken interrupts can be amortized over many runs
when nothing happens.

Which such situations did you have in mind?

I didn't write that; Terje Mathisen did.

--
David Hopwood <david.nospam.hopwood@blueyonder.co.uk>

David Hopwood
Guest

Posted: Mon Sep 12, 2005 12:15 am Post subject: Re: interrupting for overflow and loop termination

David Hopwood wrote:

Quote:

andrewspencers@yahoo.com wrote:

[...] when you wrote in your prior message:

OTOH, ints _can_ be a win in other situations, specifically when they
are used to guard against/handle really exceptional situations, where
the extra overhead of a taken interrupts can be amortized over many runs
when nothing happens.

Which such situations did you have in mind?

I didn't write that; Terje Mathisen did.

But to answer the question, some examples of where this approach can be
effective are using unmapped guard pages to detect stack overflows, exhaustion
of an allocation space, or null pointer accesses in languages that require
null pointer checks.

Note that these are cases in which the relevant operation (allocating a stack
frame or object, indirecting through a pointer) is extremely common, and the
interrupt-based optimization is in "infrastructure" code so that a single
implementation can apply to many programs. Even then it may not pay off: hacks
like this should be reevaluated every so often to see whether they are really
giving a performance improvement that justifies their complexity.

--
David Hopwood <david.nospam.hopwood@blueyonder.co.uk>

glen herrmannsfeldt
Guest