interrupting for overflow and loop termination
|
From: MitchAlsup on 9 Sep 2005 18:55 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.
From: glen herrmannsfeldt on 9 Sep 2005 19:07 MitchAlsup(a)aol.com wrote: > 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
From: andrewspencers on 9 Sep 2005 19:29 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? >> 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. > 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?
From: glen herrmannsfeldt on 9 Sep 2005 20:14 andrewspencers(a)yahoo.com wrote: (snip) > 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. > 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. > 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
From: andrewspencers on 9 Sep 2005 22:42
glen herrmannsfeldt wrote: > 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. > 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. |