| Author |
Message |
Guest
|
 Posted:
Sat Sep 10, 2005 12:03 am Post subject:
interrupting for overflow and loop termination |
|
|
Are there any CPU architectures which tie the overflow flag to an
interrupt, so that programs don't have to put a flag test and
conditional branch after each arithmetic operation in order to avoid
modular arithmetic?
And similarly, are there any architectures which tie the output of a
logic function (hardwired or programmable) of the bits of a register or
combination of registers to an interrupt, in order to provide
interrupt-based loop termination and interrupt-based pattern matching? |
|
| Back to top |
|
 |
Jason Lee Eckhardt
Guest
|
| Posted:
Sat Sep 10, 2005 12:03 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
In article <1126290898.835776.58100@f14g2000cwb.googlegroups.com>,
<andrewspencers@yahoo.com> wrote:
| Quote: | Are there any CPU architectures which tie the overflow flag to an
interrupt, so that programs don't have to put a flag test and
conditional branch after each arithmetic operation in order to avoid
modular arithmetic?
|
The Intel i860 went part of the way to that functionality. It
had a "intovr" instruction (interrupt on overflow) which would trap
if EPSR.OF was set. But the programmer still had to insert
this instruction manually. This is somewhat simpler than a
test-and-branch sequence, since it is only one instruction and the
target is implicit. |
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Sat Sep 10, 2005 12:10 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
In article <1126290898.835776.58100@f14g2000cwb.googlegroups.com>,
<andrewspencers@yahoo.com> wrote:
| Quote: | Are there any CPU architectures which tie the overflow flag to an
interrupt, so that programs don't have to put a flag test and
conditional branch after each arithmetic operation in order to avoid
modular arithmetic?
|
Many, even today, after decades of the ghastly approach to eliminating
overflow errors by eliminating overflow detection. But, switch it on,
and you will find an awfully high proportion of compiled code, run-time
systems and libraries fall over horribly.
| Quote: | And similarly, are there any architectures which tie the output of a
logic function (hardwired or programmable) of the bits of a register or
combination of registers to an interrupt, in order to provide
interrupt-based loop termination and interrupt-based pattern matching?
|
Not that I know of. It is an old idea, but I don't know if it was
ever implemented in hardware. God alone knows why not, because it
is an obviously useful facility (e.g. for C assert) and needs next
to no hardware to implement it.
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Sat Sep 10, 2005 12:15 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
andrewspencers@yahoo.com wrote:
| Quote: | Are there any CPU architectures which tie the overflow flag to an
interrupt, so that programs don't have to put a flag test and
conditional branch after each arithmetic operation in order to avoid
modular arithmetic?
|
S/360 and successors have a program mask which activates or deactivates
four program interrupts. Those four are fixed point overflow, decimal
overflow, exponent underflow, and significance. There is no bit for
exponent overflow, that is always enabled. (The interrupt routine
can return without doing anything, though.)
| Quote: | And similarly, are there any architectures which tie the output of a
logic function (hardwired or programmable) of the bits of a register or
combination of registers to an interrupt, in order to provide
interrupt-based loop termination and interrupt-based pattern matching?
|
This reminds me a little of the S/370 PER (program event recording)
facility. You can request an interrupt for a register or set of
registers being modified, storage within a range of addresses being
modified or executed or the target of a branch instruction.
See: http://publibfp.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/dz9zr003/4.5
for the current version of PER.. It is mostly used by debuggers.
-- glen |
|
| Back to top |
|
|
Terje Mathisen
Guest
|
| Posted:
Sat Sep 10, 2005 12:15 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
Jason Lee Eckhardt wrote:
| Quote: | In article <1126290898.835776.58100@f14g2000cwb.googlegroups.com>,
andrewspencers@yahoo.com> wrote:
Are there any CPU architectures which tie the overflow flag to an
interrupt, so that programs don't have to put a flag test and
conditional branch after each arithmetic operation in order to avoid
modular arithmetic?
The Intel i860 went part of the way to that functionality. It
had a "intovr" instruction (interrupt on overflow) which would trap
if EPSR.OF was set. But the programmer still had to insert
this instruction manually. This is somewhat simpler than a
test-and-branch sequence, since it is only one instruction and the
target is implicit.
|
This is exactly analogous to the x86 special one-byte opcode,
INTerrupt_on_Overflow (INTO) which also has to be compiled in, and which
will generate an interrupt, if the Overflow flag was set by the last
arithmetic/logic operation.
Terje
--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching" |
|
| Back to top |
|
|
Guest
|
| Posted:
Sat Sep 10, 2005 12:15 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
Works great on signed arithmetic, blows wind on unsigned arithmetic,
and other useful programming mechanisms.
Do you really want to take an interrupt on a piece of code that looks
like:
int extract( int container, int size, int offset )
{
return (container << (32-offset-size)) >> (32-size);
}
Would you still want to take an interrupt if the function was:
int extract( int container, unsigned size, unsigned offset )
{
return (container << (32-offset-size)) >> (32-size);
}
You can get rid of the overflow problem if:
unsigned extract( unsigned container, unsigned size, unsigned offset )
{
return (container >> offset) & ~(~0 << size);
}
But here, you cannot get a signed field extractded from an unsigned
container without a lot of type-punning. |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Sat Sep 10, 2005 12:15 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
MitchAlsup@aol.com wrote:
| Quote: | Works great on signed arithmetic, blows wind on unsigned arithmetic,
and other useful programming mechanisms.
|
(snip of C code examples)
Note that S/360, a machine that does have such an interrupt
(controllable with a user supplied mask), has both signed
and unsigned add and subtract instructions. AL (add logical)
does not generate a fixed overflow exception.
The main reason for the two instructions is that the
condition codes are different, as needed for unsigned
or multiple precision arithmetic, but also the different
exceptions allowed.
To continue the discussion, if exponent underflow is disabled
the register is set to zero. If enabled, the wrapped exponent
is stored and the interrupt routine can use it.
The significance exception comes from subtracting floating point
numbers when all significant bits are lost. I have never seen it
used, especially as the common way to zero a floating point
register is to subtract it from itself. As to the OP, though,
that is one place where the logical result is used to generate
an interrupt.
-- glen |
|
| Back to top |
|
|
Guest
|
| Posted:
Sat Sep 10, 2005 12:15 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
Nick Maclaren wrote:
| Quote: | Are there any CPU architectures which tie the overflow flag to an
interrupt, so that programs don't have to put a flag test and
conditional branch after each arithmetic operation in order to avoid
modular arithmetic?
Many, even today,
Which ones? |
| Quote: | And similarly, are there any architectures which tie the output of a
logic function (hardwired or programmable) of the bits of a register or
combination of registers to an interrupt, in order to provide
interrupt-based loop termination and interrupt-based pattern matching?
after decades of the ghastly approach to eliminating
overflow errors by eliminating overflow detection. But, switch it on,
and you will find an awfully high proportion of compiled code, run-time
systems and libraries fall over horribly.
I'm a bit confused here; if the overflow flag can be tied to an |
interrupt, and a program isn't explictly written to use that feature,
then turning the feature on and then running the program will cause the
program to fall over horribly if it experiences an overflow,
_regardless_ of whether the program was just ignoring the overflow flag
(which is the wrong thing to do if there's a possibility of overflow)
or actually checking the overflow flag and taking an appropriate course
of action. I'm talking not about using the interrupt-on-overflow
feature as an error checking mechanism, but as an optimization.
The program would have to be written explicitly to use the feature,
i.e. turn the feature on _itself_, and install its own interrupt
handler. The idea is that if the program is expecting to do a whole lot
of overflow-prone operations, e.g. bignum arithmetic
(infinite-precision integer arithmetic), it can install an interrupt
handler to examine the interrupted process and handle overflows, thus
allowing the main program to omit the "test overflow flag - conditional
branch past overflow hander - handle overflow" postscript which is
otherwise necessary after every overflowable operation.
| Quote: | Not that I know of. It is an old idea, but I don't know if it was
ever implemented in hardware. God alone knows why not, because it
is an obviously useful facility (e.g. for C assert) and needs next
to no hardware to implement it.
Well yes C assert would be another use, and array bounds checking. |
But again I'm talking about using the feature as an optimization, not
as an error checking mechanism. E.g. instead of the standard "compare
loop counter register - conditional branch out of loop - increment loop
register - unconditional branch to beginning of loop" postscript at the
end of a loop, a program could instead simply use "increment loop
register - unconditional branch to beginning of loop" after setting an
interrupt to be triggered when the loop counter register reaches some
value, with the interrupt handler used to jump out of the loop.
And for linear searching, instead of the standard "load memory -
compare to test register - conditional branch out of loop - compare
loop counter register - conditional branch out of loop - increment loop
register - unconditional branch to beginning of loop", the program
could set an interrupt to be triggered when either the loop counter
register reaches some value or the test register matches some value,
thus allowing the actual loop to be simply "load memory - increment
loop register - unconditional branch to beginning of loop".
On an architecture with virtual memory, the interrupt handler address
could be vectored through the page tables the same way as normal
process memory, thus allowing processes to install and use their own
private interrupt handlers without interfering with or having to rely
on the operating system.
As it's clear that both Intel and AMD are willing to add useful
hardware features at the request of software developers (witness MMX
and variants, and now Vanderpool and Pacifica) even if those features
require substantial effort to implement, the only explanation for the
lack of interrupt-based overflow, loop termination, and pattern
matching, which would be simple to implement, is that no significant
software developers have requested these features.
Perhaps they've simply not paid any attention to the potential for such
optimization, and are under the delusion that branch prediction and
speculative execution subsume the interrupt-based optimizations? |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Sat Sep 10, 2005 12:15 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
andrewspencers@yahoo.com wrote:
(snip)
| Quote: | Well yes C assert would be another use, and array bounds checking.
But again I'm talking about using the feature as an optimization, not
as an error checking mechanism. E.g. instead of the standard "compare
loop counter register - conditional branch out of loop - increment loop
register - unconditional branch to beginning of loop" postscript at the
end of a loop, a program could instead simply use "increment loop
register - unconditional branch to beginning of loop" after setting an
interrupt to be triggered when the loop counter register reaches some
value, with the interrupt handler used to jump out of the loop.
|
Consider what the advantage would be. Unconditional branch is nice,
but mainly because the processor knows it is unconditional. A predicted
conditional branch should be about as good. The 360/91, a machine
designed before the cache was invented (on the 360/85), had a special
loop mode buffer. A backward branch within some number of doublewords
would enter loop mode where instruction fetch would stop (they were
in the buffer) and the branch was assumed taken (for prefetching).
It seems that in ESA/390 processors BXH is predicted as not taken,
and BXLE is predicted as taken. These instructions are often
used in test at the top and test at the bottom loops, respectively,
though there is no requirement that they be used that way.
It seems, then, with a cache and good branch prediction there
is nothing to be gained by using interrupts to exit the loop.
| Quote: | And for linear searching, instead of the standard "load memory -
compare to test register - conditional branch out of loop - compare
loop counter register - conditional branch out of loop - increment loop
register - unconditional branch to beginning of loop", the program
could set an interrupt to be triggered when either the loop counter
register reaches some value or the test register matches some value,
thus allowing the actual loop to be simply "load memory - increment
loop register - unconditional branch to beginning of loop".
|
Even better, offer special instructions for searching.
It is, then, a microcode loops that should be even better, and
no interrupt is required.
| Quote: | On an architecture with virtual memory, the interrupt handler address
could be vectored through the page tables the same way as normal
process memory, thus allowing processes to install and use their own
private interrupt handlers without interfering with or having to rely
on the operating system.
|
This would require some extra changes to handle interrupts in user
state, but it could make some sense.
(snip)
Consider the IBM mainframe SIE instruction, Start Interpretive
Execution. It is used for virtual machines, somewhat similar to the
virtual86 mode on intel chips. SIE executes instructions as
described in some control block until it needs supervisor help,
such as for a privileged instruction. It then goes to the
instruction following SIE, no interrupt overhead, no context
switch other than that internal to SIE, nothing else.
Instead of interrupt exit for a loop why not an instruction to
enter loop mode specifying where to go when the loop is done,
and then an unconditional loop. A special loop exiting
instruction or condition would then trigger the previously
specified exit. You might even have a way to indicate early
that the loop was about to finish to give the processor time
to start prefetching and decoding outside the loop.
-- glen |
|
| Back to top |
|
|
Guest
|
| Posted:
Sat Sep 10, 2005 7:42 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
glen herrmannsfeldt wrote:
| Quote: | Instead of interrupt exit for a loop why not an instruction to
enter loop mode specifying where to go when the loop is done,
and then an unconditional loop.
Yes; this is for example the instruction sequence "install usermode |
interrupt handler at address y" and "trigger usermode interrupt when
register X is zero" followed by the loop itself. Address y is the
instruction immediately following the loop, and at that address is an
instruction to pop the return address (pushed by the processor when
invoking the interrupt handler) and throw it away, and then the program
continues onward at that point.
| Quote: | A special loop exiting
instruction or condition would then trigger the previously
specified exit.
Well a special condition, yes: for example, when register X is zero. |
But a special instruction inside the loop? That's called "comparison
followed by conditional branch", which is exactly what we're trying to
avoid!
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.
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. |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Sat Sep 10, 2005 8:15 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
andrewspencers@yahoo.com wrote:
| Quote: | glen herrmannsfeldt wrote:
|
(snip)
| Quote: | A special loop exiting
instruction or condition would then trigger the previously
specified exit.
Well a special condition, yes: for example, when register X is zero.
But a special instruction inside the loop? That's called "comparison
followed by conditional branch", which is exactly what we're trying to
avoid!
|
That isn't what I was saying, but it is a fine difference.
The address is specified before the loop, you can call it an
interrupt address or a future branch address.
Inside the loop, does it matter if it is one instruction or two?
If it is a comparison followed by a conditional interrupt as
two instructions? How about a compare and conditional branch
as one instruction? Or a compare and conditional interrupt
as one instruction.
| 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.
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.
|
Branches predicted as not taken that aren't taken have a fairly low
cost already. It might be a relative branch with an 8 bit offset, so
the cost is 8 bits of instruction. It might be that the compare
and relative branch could be in one instruction.
When branch prediction logic works right conditional branches
are pretty cheap. That is why so much work goes into them.
-- glen |
|
| Back to top |
|
|
Anton Ertl
Guest
|
| Posted:
Sat Sep 10, 2005 8:15 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
andrewspencers@yahoo.com writes:
| Quote: | Are there any CPU architectures which tie the overflow flag to an
interrupt, so that programs don't have to put a flag test and
conditional branch after each arithmetic operation in order to avoid
modular arithmetic?
|
MIPS and Alpha
On MIPS, add traps on overflow, addu does modulo arithmetic. A
student of mine once used add by mistake, resulting in a SIGFPE under
Ultrix or Irix.
On Alpha, add does modulo arithmetic, addv traps on overflow.
- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html |
|
| Back to top |
|
|
Guest
|
| Posted:
Sat Sep 10, 2005 8:15 am Post subject:
Re: interrupting for overflow and loop termination |
|
|
glen herrmannsfeldt wrote:
| Quote: | But a special instruction inside the loop? That's called "comparison
followed by conditional branch", which is exactly what we're trying to
avoid!
That isn't what I was saying, but it is a fine difference.
The address is specified before the loop, you can call it an
interrupt address or a future branch address.
Inside the loop, does it matter if it is one instruction or two?
I mean _zero_ test/branch/soft interrupt/etc instructions inside the |
loop.
| Quote: | If it is a comparison followed by a conditional interrupt as
two instructions? How about a compare and conditional branch
as one instruction? Or a compare and conditional interrupt
as one instruction.
No, not a soft interrupt; I'm talking about a hard interrupt, triggered |
by the output of some hardware-implemented logic function of a
register's bits.
Thus, the program sets an interrupt to trigger when the register
reaches some predefined value, and then enters an infinite loop, and
the interrupt will break the infinite loop. |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Sat Sep 10, 2005 2:41 pm Post subject:
Re: interrupting for overflow and loop termination |
|
|
andrewspencers@yahoo.com wrote:
| Quote: | glen herrmannsfeldt wrote:
But a special instruction inside the loop? That's called "comparison
followed by conditional branch", which is exactly what we're trying to
avoid!
That isn't what I was saying, but it is a fine difference.
The address is specified before the loop, you can call it an
interrupt address or a future branch address.
Inside the loop, does it matter if it is one instruction or two?
I mean _zero_ test/branch/soft interrupt/etc instructions inside the
loop.
|
I thought we were discussion comparison or search operations,
in which case it should be doing some comparing in the loop.
(snip)
| Quote: | No, not a soft interrupt; I'm talking about a hard interrupt, triggered
by the output of some hardware-implemented logic function of a
register's bits.
Thus, the program sets an interrupt to trigger when the register
reaches some predefined value, and then enters an infinite loop, and
the interrupt will break the infinite loop.
|
That is fine, though I find the distinction between hard and soft
not so obvious. I was considering doing something inside the loop
which might exit the loop early, such as the completion of
a search operation. In any case, the exit address is stored
somewhere before entering the loop, and the loop is exited at
the appropriate time to that address. Does it matter if the
exit address is in a general register instead of a special location
for interrupts?
Though I am still finding the distinction hard to make.
Say compare to the S/360 BCTR instruction, decrement a
register and branch to the address in another register
if the value isn't zero. Your loop still needs a counter,
and it still needs a branch at the end. How much difference
can there be between a conditional branch based on the
register value and an unconditional branch with an
interrupt based on that register value?
BCTR is 16 bits long, so instruction fetch time isn't
very limiting.
Note that there is a fair amount of overhead needed to perform
a precise interrupt as you will require. With an imprecise
interrupt the processor could execute a few more loop cycles
before the interrupt was actually taken, which isn't good
for searching. The things people used to do to make fast
processors, but don't anymore.
-- glen |
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Sat Sep 10, 2005 2:41 pm Post subject:
Re: interrupting for overflow and loop termination |
|
|
In article <1126308566.021605.110950@z14g2000cwz.googlegroups.com>,
<andrewspencers@yahoo.com> wrote:
| Quote: | Nick Maclaren wrote:
Are there any CPU architectures which tie the overflow flag to an
interrupt, so that programs don't have to put a flag test and
conditional branch after each arithmetic operation in order to avoid
modular arithmetic?
Many, even today,
Which ones?
|
z/OS (System/390). I can't remember which of the RISC ones can still
do it, and would have to read the architectures to remind myself.
I think that x86 can.
| Quote: | And similarly, are there any architectures which tie the output of a
logic function (hardwired or programmable) of the bits of a register or
combination of registers to an interrupt, in order to provide
interrupt-based loop termination and interrupt-based pattern matching?
after decades of the ghastly approach to eliminating
overflow errors by eliminating overflow detection. But, switch it on,
and you will find an awfully high proportion of compiled code, run-time
systems and libraries fall over horribly.
I'm a bit confused here; if the overflow flag can be tied to an
interrupt, and a program isn't explictly written to use that feature,
then turning the feature on and then running the program will cause the
program to fall over horribly if it experiences an overflow,
_regardless_ of whether the program was just ignoring the overflow flag
(which is the wrong thing to do if there's a possibility of overflow)
or actually checking the overflow flag and taking an appropriate course
of action. I'm talking not about using the interrupt-on-overflow
feature as an error checking mechanism, but as an optimization.
|
Nope.
The point is that sloppy programmers often use signed arithmetic
when they should be using unsigned. On a twos complement machine,
ignoring overflow on signed arithmetic is almost equivalent to
using unsigned arithmetic, so they get away with it. Until someone
switches on overflow trapping ....
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in