dgh@validgh.com (David G. Hough on validgh) (06/18/91)
Dik Winter observes that dynamic rounding modes (that can be varied at run time) don't have to be quite so expensive on pipelined systems if the control modes can be written without emptying the pipeline. If you don't have such a feature then the cost of interval addition is dominated by the cost of emptying the pipe and the cost of the two additions is minor. However several existing instruction set architectures, including SPARC for which I can take some blame, combine too much stuff into the floating-point control/status register, so that it's unrealistic to expect the hardware to keep track of changes to the rounding modes only... so the pipeline will necessarily have to be drained. In addition the SPARC architecture specifies that changes to the floating-point control/status register don't have to take effect for a couple of cycles after the load, with no hardware interlock support, so you have to force some nop dead time before you can initiate a rounded add. Other RISC architectures may be similar. The common CISC architectures have separate control and status registers, and at least the microcoded implementations of floating-point +-*/ are so slow that control register manipulations are of no consequence. This was the environment anticipated when IEEE 754 was being drafted, leading to its expectation (though not a requirement) that rounding modes be implemented dynamically in hardware. So for satisfactory interval arithmetic performance, I've come to the conclusion that one of the following paths must be followed: 1) separate control and status registers and appropriate hardware support 2) additional instructions with static rounding modes built in - +-*/ rounding to +infinity +-*/ rounding to -infinity 3) microprogrammed instructions, perhaps in a coprocessor, to perform interval operations directly -- David Hough dgh@validgh.com uunet!validgh!dgh na.hough@na-net.ornl.gov
dhinds@elaine18.Stanford.EDU (David Hinds) (06/19/91)
In article <399@validgh.com> dgh@validgh.com (David G. Hough on validgh) writes: >Dik Winter observes that dynamic rounding modes (that can be varied >at run time) don't have to be quite so expensive on pipelined systems >if the control modes can be written without emptying the pipeline. > >If you don't have such a feature then the cost of interval addition >is dominated by the cost of emptying the pipe and the cost of the two >additions is minor. > Really, it seems to me that if support for interval arithmetic is built into a compiler, it should be able to optimize away most of the rounding mode changes without too much trouble. This should be trivial for the cases where the mode changes would otherwise do the most damage, such as in tight inner loops with no dependencies, i.e., vector operations. Just split and do two loops, one for the lower and one for the upper vectors. -David Hinds dhinds@cb-iris.stanford.edu
rh@craycos.com (Robert Herndon) (06/19/91)
While I've seen lots of verbage on the pros and cons of interval operations, I've seen NO discussion of its impact on algorithms. The question is then, how does one allow for changes of algorithm flow because of interval arithmetic? I.e., any time a decision is made based on the value of an interval, one sees a dichotomy of possible flow paths. E.g., partial pivoting requires selection of the largest element of a matrix column. If interval arithmetic shows that two elements' intervals overlap, how does one choose? Presumably, one picks the element with the larger potential absolute value, but this may be a bad choice if the element has a large interval, compared with another of similar magnitude but smaller interval. Perhaps the element with the largest ratio of magnitude to interval is chosen, so as to minimize the intervals of the reduced elements? Anyhow, is there a standard strategy for making these kinds of choices? How are error bounds computed in light of these choices? Is it even a factor? Does one simply compute as one computes, and take the final answer as gospel and then tweak the algorithm to reduce the intervals of the results as much as possible? Robert Herndon -- Robert Herndon -- not speaking officially for Cray Computer. Cray Computer Corporation --|-- 719/540-4240 1110 Bayfield Dr. -----o----- rh@craycos.com Colorado Springs, CO 80906 " " Skyhawk N7511T
jbs@WATSON.IBM.COM (06/19/91)
David Hinds said:
Really, it seems to me that if support for interval arithmetic is built
into a compiler, it should be able to optimize away most of the rounding
mode changes without too much trouble. This should be trivial for the
cases where the mode changes would otherwise do the most damage, such as
in tight inner loops with no dependencies, i.e., vector operations. Just
split and do two loops, one for the lower and one for the upper vectors.
I believe if you try to do this with
DO 10 J=1,N
10 X(J)=Y(J)*Z(J)
you will discover things are not so simple.
James B. Shearerjbs@WATSON.IBM.COM (06/19/91)
Robert Herdon asked:
While I've seen lots of verbage on the pros and cons of interval
operations, I've seen NO discussion of its impact on algorithms.
The question is then, how does one allow for changes of algorithm
flow because of interval arithmetic? I.e., any time a decision
is made based on the value of an interval, one sees a dichotomy
of possible flow paths.
If you are using interval arithmetic to figure error bounds for
a non-interval arithmetic calculation then it is necessary to carry along
the non-interval arithmetic values at each stage as well to get the con-
trol flow correct. Using the usual interval representation this will in-
crease the cost considerably. Of course you could represent intervals
as (value, maximum possible absolute error).
James B. Shearerok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (06/19/91)
> If you don't have such a feature then the cost of interval addition > is dominated by the cost of emptying the pipe and the cost of the two > additions is minor. It sounds to me as though there is some scope for compiler research here: if I have something like X = X - Y Z = Z + W then you can halve the number of mode switches in a fairly obvious way. This should pay off spectacularly for vector operations: X(1:N) = X(1:N) - Y(1:N) only needs one mode switch (provided the compiler keeps track of the mode setting at the beginning of each basic block). I think it would be instructive to look at the level 1 BLAS and a few subroutines from LINPACK to see whether a plausible optimisation level applied to Fortran-90 versions could reduce the cost of mode switching. What exactly do the interval arithmetic operations look like when built on top of IEEE 754 primitives? -- Q: What should I know about quicksort? A: That it is *slow*. Q: When should I use it? A: When you have only 256 words of main storage.
rodman@sgi.com (Paul K. Rodman) (06/19/91)
In article <9106190449.AA02871@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes: > Robert Herdon asked: >While I've seen lots of verbage on the pros and cons of interval.. I've heard yapping about interval arithmetic for a decade and have yet to see anyone that actually _used_ it. Has anyone implemented a compiler with set of "interval" data types? Has anyone used interval arithmetic by doing it themselves with macros/functions/subroutines. I'd be interested in seeing more of the uses.... --------- On the conditional assignment topic, since no other ex-Multifloids spoke up yet, I'll just mention that the Trace family had multiple condition codes and could do a "select" operation between two values based on a condition code bit. The new machine we were working on upon our demise.., <sniff>, had both selects and conditional assignments. In a VLIW it isn't very hard to implement this critters. In a typical scoreboarded machine you might not like the select instructions as they are 4-address instructions. In addition, the floating point data path might not have the ability to transport either source field, etc, etc. pkr -- Paul K. Rodman Advanced Systems Division rodman@sgi.com Silicon Graphics, Inc. KA1ZA Mountain View, Ca.
bremner@cs.sfu.ca (David Bremner) (06/20/91)
In article <1991Jun19.165150.2121@shinobu.sgi.com> rodman@sgi.com (Paul K. Rodman) writes: >I've heard yapping about interval arithmetic for a decade and have yet >to see anyone that actually _used_ it. Has anyone implemented a >compiler with set of "interval" data types? Well, it's not FORTRAN, but languages designed for constraint logic programming (CLP) include "real" intervals, both with and without holes in them. I'm not familiar enough with CLP to know what the implementation issues are, but if no one less ignorant than me comes forward, I can ask the local CLPeople . David -- bremner@cs.sfu.ca ubc-cs!fornax!bremner
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (06/20/91)
In article <1991Jun19.165150.2121@shinobu.sgi.com>, rodman@sgi.com (Paul K. Rodman) writes: > I've heard yapping about interval arithmetic for a decade and have yet ^^^^^^^ polite, isn't he? > to see anyone that actually _used_ it. Has anyone implemented a > compiler with set of "interval" data types? Wisconsin. A preprocessor for Fortran provided both interval and triplex. IBM (germany?) Pascal/SC. Quite a few others I can't remember the names of. The hard part is not the compiler, but implementing the primitive operations. -- I agree with Jim Giles about many of the deficiencies of present UNIX.
robison@brazil (Arch D. Robison) (06/26/91)
There have been comments that changing the rounding mode on some machines can be slow. But does it really need to be changed? IEEE arithmetic is symmetric with regard to +/-, and we have the identity: ceiling(x) = -floor(-x) So by flipping signs, we can stay in round-down mode all the way. Better yet, instead of storing an interval as (lower,upper), store it as (lower,-upper) and avoid flipping signs. Then two intervals can be added with a single setting of the rounding mode to ``round-down'' and two addition instructions. Arch D. Robison robison@shell.com Bellaire Research Center (713)-245-7240 Shell Development Company