13 ms·
I basically failed the numerical analysis part of my CS degree forty years ago so forgive me if I misunderstand. The abstract implies by holding and calculating
by ggm 6y ago
I basically failed the numerical analysis part of my CS degree forty years ago so forgive me if I misunderstand. The abstract implies by holding and calculating a shadow higher precision version of the fp value the nsan logic can detect faults in code.
The specific faults we were taught about back then, would seem to be accumulated, loop embedded rounding error. Is there some other calls of merit it can handle? I took (40 years ago) a message that precision and repetition went hand in hand in this problem. I could see that eg incorrect precision handling across function call boundaries could promote ints to speciously accurate floats maybe, but that's a trivially detected type problem surely?
Not saying this isn't good work. Seeking clue about its scale and applicability.
- kevingadd 6y agoOne real-world example: All the textbook algorithms for triangulation by ear-clipping (i.e. turning a convex shape into a bunch of triangles) are broken if executed using IEEE floats, some formulations of them are worse than others. Typically they loop forever. If you take an implementation that appears to work on x86 and compile it for powerpc, it might break. In general you can be taking textbook accurate math based on rock solid proofs and then when you turn it into code it's busted, so nsan seems like it could be really valuable for flushing out some of those problems.
- ggm 6y agoI honestly thought the numerical algorithm group NAG library had fixed this three decades ago. I'm not being sarcastic, I thought the numerical analysis libraries tested the living bejesus out of their code. I guess a lot more intensive FP code exists now, outside of highly tested library code, or calls made from the calls, or whatever.
- yablak 6y agoYou'd be surprised how many of the old, painstakingly tested fp algorithms, have been reimplemented in DL frameworks. I ported many algorithms from cephes to Eigen for use in TensorFlow. Some I was able to make simd. Then the XLA folks reimplemented some in HLO using other approximations that are easier to parallelize. Then consider that some linear algebra and simple functions like softmax and softplus have to be implemented for fast execution in float16 and bfloat16 supporting hardware. You can iterate over the entire fp16 space quite quickly but the initial version isn't usually so thoroughly tested.. performance is king anyway in NNs. Then a couple months later someone ports an old model to V100 and it turns out your softplus underflows. Guess how many weeks it takes to figure out why your model quality went to s**?
- ggm 6y agoI sat next to the NAG maintenance crew at lunch sometimes, back in the 80s in Leeds university who held a contract (I think it moved around, possibly by design). They were fierce, collectivist correctness freaks. Outside code was reviewed mercilessly. Nothing anyone said about their experiences coding mattered as much as what they did to that library. If they stuffed it up, bridges fell down during construction or rockets blew up, and they knew it. I remain in awe. All those jokes about real programmers are wrong. Real programmers take great care.
- kevingadd 6y agoI'm sure those libraries are good, you just tend not to encounter stuff like that in programs written casually or by people who think performance really matters. Most people doing triangulation by ear clipping are trying to rasterize shapes. In the past, cairo (the 2d graphics library) had a bug that would cause crashes/hangs in Firefox because a VPN driver was changing the floating point state on random threads... which would cause one of those geometric algorithms to break.
- gpderetta 6y agoThat must have been extremely painful to debug. Let me guess, on Windows it was resetting the x87 fpu precision from 64 bits to 80?
- hansvm 6y agoAs one example, FP is prone to a huge loss of precision from subtraction. Let X be huge and E be tiny, then (X+E)-X could be nowhere near E. Linear algebra routines usually have a severe trade-off between speed and accounting for those sorts of errors (such accounting is usually implemented as some kind of search for the best order to do a set of operations), when they can even be handled. If your inputs are nice enough (which is often the case) then it could very well be that none of the above matters and you can go full speed ahead with the fastest and most error prone solutions, but feasibly I could see something like this allowing you to detect early on which snippets might need extra attention due to the nature of typical inputs in those locations.
- deleted 6y ago[deleted]
- sn41 6y agoAs pointed out by others, subtraction is very sensitive. The following are also important examples. 1. The problem of small denominators. This is analogous to the subtraction issue, but it was observed and well-studied in the 19th century itself, in the context of celestial mechanics. It is fundamentally difficult to implement these numerically [1]. 2. Whenever there are algorithms which depend on a "discontinuous" choice of a pivot in order to proceed, numerical instability may follow. This is why Gaussian elimination and Gram-Schmidt orthonormalization are numerically unstable, and other algorithms like Householder transformation are preferred instead [2]. A very detailed reference on stability issues is the book by Higham [3]. Some of these are floating point issues. [1] http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=6441&option_lang=eng http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm... [2] https://en.wikipedia.org/wiki/Householder_transformation https://en.wikipedia.org/wiki/Householder_transformation [3] https://epubs.siam.org/doi/book/10.1137/1.9780898718027?mobileUi=0& https://epubs.siam.org/doi/book/10.1137/1.9780898718027?mobi...
- nestorD 6y agoI am not familiar with NSan but other shadow value implementations will keep a higher precision copy of the numbers and follow them in the computation. They detect local errors but also take propagation (amplification and dampening of error) into account to evaluate the numerical accuracy of the final result.