Unit (regression) testing scientific algorithms given floating point behavior

Question

I have been working on a project and running into a very difficult problem. The problem can be stated simply as how to unit-test numerical algorithms. However if you just took this simple statement you would get the standard set of answer isolation of input, random processes, mocking, tolerancing, etc.
The answer (if there is one) does not reside with these.

Also, as a note, I am not concerned with testing the correctness of the algorithm. That is done with very different methods and it is assumed that the algorithm is correct. What I am using unit-testing for is to make sure that changes in other parts of the system/support algorithms do not change the output of the algorithm under test.

So, for a description of the problem: We have an algorithm which takes Gigabits of data, processing it, and generates an image with a corresponding map of which pixels are good and which ones are not. It is this map which I need to verify does not change and pixels which are not valid are not to be used in any way other than the fact that they invalid.

If this was all that was given I would have many possible solutions and in fact the method have been using for years is to look at the number of valid pixels, the average, standard deviation, peak and valley of the image. This has proven very sensitive detector for changes.

But, this year has added complications which is causing issues with this approach.

• The number of threads being used has increased causing changes in the floating point behavior. In the past the smaller number of thread was accounted for in the tolerances used.
• We have been using floating point (as compared to double) to increase throughput. This has caused the rounding behavior to change even more and combined with the number of threads makes it worse. This has also been made worse as we move to using SIMD processing like GPU and/or AVX instructions sets.
• We have been enhancing the algorithms used to recover more of the pixels which would have been marked as invalid in the past are not valid. This combined with 1 and 2 above is resulting in some pixels being included on some machine and not on others. Since these are on the edge of useability these difference are handled by the algorithms with use this image and are not of concern for the system as a whole, but are causing problems with unit testing the algorithms.
• We have also recently ran into the problem that two numbers (internal to the calculation) are the same and because of the rounding behavior one or the other is picked resulting in different outputs. . Again this is not a problem of the system as a whole, only with unit testing to flag for differences.
• As a minor side example, we also have other non-linear algorithms with due to rounding behavior can give different outputs. Since these algorithms are self correcting the final solution is good, but has a higher variability than easily accounted for unless the tolerances are opened larger than desired.

So, my questions is how to account for these issue in unit testing.
I strongly need unit testing because we have a team of programmers working on the system and we need the ability to detect when someone makes a change which unknowingly impacts other algorithms. Yes this has happened in the past and the method being used at the time caught the change before it reached the final product. As the primary algorithm developer I can use your help. I have had many ideas, but they don’t work for all cases and it’s not clear when to use one of the different methods.

Edit: I now that this is frequently called regression testing but I also know that many time it is also generically called unit testing by many people, even if it's not completely correct.

I am not necessarily looking for a magic bullet (that would be nice) but I do need a way of handling these issues in a way which can be handled by others in the group which may not be as knowledgeable on the details. If that is a “pick” one of these methods that is fine if it the rule are clear. We do adjust the parameters when we change the algorithms, but once it is fixed the floating point behavior is still causing differences. When we see differences we always investigate why and in general we try to adjust the algorithm to reduce the difference, but there are times where these is not possible because of the additional computation time. If we stayed away from the limits this would not be an issue (as in the past) but to advance the technology we need to push the limits giving rise to the issues described.

You can see this in a simple example. Calculating an average of many numbers. If you stay with number which are close to each other, there are simple methods to make sure the results are accurate. Now when you allow for numbers which have large (orders of mag) difference, with threading, float compared to double, etc you can get very different results. Yes I know there are algorithms which can be used to fix these issue but they can be very computation expensive. While averaging is not my problem you could imagine that the difference don’t impact downstream processing but you still want to write a test to monitor the calculation.

Answer 1

First of all, it is not very clear if you compare floating point numbers with exact values in your unit tests. If you do so, this is wrong and you should rely on approximate comparison of floating point numbers [1].

That being said, if your computations are sensitive to factors such as the number of threads involved, the precision of numbers used and the other things you describe, then you should question the stability of your numerical procedures. If you are lucky, you can rewrite some calculations to improve the stability without significantly change the number of operations required. But it might also happen, that writing better procedures involves more calculations, so that you will have to find an acceptable trade-off between time and precision.

[1] For instance, you can start here: http://www.gnu.org/software/gsl/manual/html_node/Approximate-Comparison-of-Floating-Point-Numbers.html

Answer 2

How do you eat an elephant? One bite at a time. It sounds you are looking for a "magic bullet" to solve all of your problems at once, and that's IMHO part of the problem. There is not magic bullet, this is hard work, and you can only solve it step-by-step.

For example, you told us that you have already some fuzzy or statistical methods in place to compare the result of your tests to an expected result. I guess these fuzzy methods have some threshold parameters when to accept a result and when not. Whenever you change the behaviour of your algorithms, you will have to adept these parameters - do this for one change after another, run the tests again, make sure the new results are in the accepted range. In fact, you have to fine-tune this parameters, since it may be not ad-hoc clear which results are correct, which are incorrect and if there is a "grey area" between right and wrong.

If that does not work, you may have to look for a modification of the "fuzzy comparison" itself - each time you come across a new kind of change. Unfortunately I cannot tell you how these comparison have to look like, since one must have in-depth know-how about your problem domain to make a right decision.

EDIT: maybe image matching techniques will help in your case, see this SO post for some ideas.

And if this does not work either, this may also be a sign that your modification of the algorithm introduced too many unwanted side effects, so maybe you don't have to change the test, but the way you modify the algorithm implementation.

I have had many ideas, but they don’t work for all cases

Then don't look for a solution which works for "all cases". Use different solutions for different test cases.

Answer 3

You shouldn’t expect bit-for-bit identical results. Even ab + cd is allowed by C, C++ and others to yield at least two different results.

You use different methods in different cases. For example, if you use floats instead of double, have a unit test that compares both methods and checks whether results are acceptable.

Answer 4

There is a contradiction in your question. First you are saying:

What I am using unit-testing for is to make sure that changes in other parts of the system/support algorithms do not change the output of the algorithm under test.

But then you list several ways the output has changed that were not the changes you wanted to catch. So "change of the output" isn't your ultimate deciding criterion, but you are using it in your unit test. Why?

You need to define which changes are meaningful to you (as the "any change" metric clearly doesn't work) and use that in your unit tests.

On the other hand, maybe you'd like to be notified for any change, but need a quicker method to approve the new results than editing source code?