Closed jlgreathouse closed 9 years ago
I've been working on code for this for the last few days, and it's almost done. I started the Issue partially as a centralized point of discussion for the eventual changes.
With respect to the first recommendation (computing more accurately on the CPU), I've made some simple changes to calculate the comparison point for single precision SpM-DV using double precision on the CPU. Since I do my development on Linux, I'm linking in libquadmath to use 128-bit precision intermediate numbers when computing the comparison point for double precision SpM-DV.
This works for me, but I'm guessing that libquadmath is not the right way to go about doing 128-bit FP in Windows.
Recommendations?
As for the second set of questions, I'll start by saying that I've been adding in support for compensated summation into both csrmv_general and csrmv_adaptive. In particular, the algorithm presented in this paper from Yamanaka, Ogita, Rump, and Oishi.
When combined with the above method of making the CPU computations more accurate, we get answers that are within 0.001% in single precision, and 1e-10% in double precision (there are still rounding errors due to multiplication, etc. so we still shouldn't expect bitwise-exact answers).
However, performing compensated summations is more computationally intensive than a simple summation. On my test platform (with a FirePro W9100), this increased accuracy causes roughly 10% slowdown (on average). This is the reason for all of my questions related to how we should present this more accurate method to users. In addition, I believe it will make our double precision results noticeably slower on GPUs with worse DPFP performance, as it makes the kernels much more computation heavy.
In my opinion, this method of more precise calculation should be an option -- I think a lot of our users will want the ability to get tighter error bounds. However, because of the performance loss, I'm building this to be a kernel-compile-time option (e.g. -DEXTENDED_PRECISION).
Should this mode be the default, meaning users would need to request a fast-calculation mode if they're OK with more naive summation techniques?
There are also some ways to get middle-of-the-road results -- more accurate than naive while only ~3% performance loss. Should that be another separate mode, or should we just have two?
I understand floating point accuracy issues, did we compare CPU implementations against GPU implementation for integer data type?
No, we do not. The test application as written only tests floats and doubles. We'll need to make some (minor) modifications to csrmv_adaptive to handle integer and long data types if this is a goal.
I'm nearly finished adding compensated summation into both csrmv_general and csrmv_adaptive. With this mechanism in place, the double precision output in ./test-blas2 is bit-for-bit identical to a CPU calculation performed in quad precision and cast down to double (0 ULPs).
There is one wrinkle that I would like to bring up, however. The current AMD OpenCL implementation does not support single precision denormals on current AMD GPUs. Instead, it rounds to zero for denorms.
As such, the error rate for single precision numbers SpMV calculations can't be eliminated, as the compensated summation methods presented in the literature assume no underflow. Dropping denorms to zero causes a not-insignificant amount of new underflow in some of the test matrices. These matrices, then, will vary from what is calculated on the CPU. This is not because the algorithm on the CPU is wrong, per se, but because the CPU and the GPU are using different floating point rules.
Thoughts on how to best handle this? I'm tempted to say that test-blas2 should use rough error bounds for single precision (the answers are usually still close) while using much stricter bounds on double precision.
Another, perhaps hackier, possibility is to set Beta (the -b command line parameter) very high (10000?) -- this often prevents denormalized results on the matrices I'm testing, resulting in accurate results.
Hi Joe~ Thank you so much for creating this discussion and writing your thoughts down; I appreciate that. You have a lot of information and brainstorming written above, and I'm coming to the conversation a bit late. Let me add a few of my thoughts on your comments:
One extra wet idea to throw against the wall:
Hi Kent,
Thanks for the feedback. I'll try to push out my changes tomorrow in order to get some more specific comments.
I agree that libquadmath is not the correct solution in general (it helped during development, though). As such, I tried using compensated summation method linked above on the CPU as well. This allows us to calculate the double precision SpMV baseline as if it were calculated in quad precision and then cast to double. I've verified that the answers are bitwise identical between using this method and using libquadmath. This doesn't hurt performance too much and removes any extra library dependencies.
As for precision/speed and which should be the default, we should probably have a face-to-face discussion once you're back. Some of the folks I've talked to indicated they might like accuracy first and foremost, and only when doing something akin to -ffast-math should we return answers with higher error bounds. However, it might behoove us to instead put our best performance face forward, as per your recommendation.
Along the lines of your final idea: maybe we could just force all data being loaded from .mtx files (for test-blas2, not for anything else) to be a positive number. I don't think any values being read from .mtx files will come in as denorms, so this would prevent us from running into denorm verification problems for single precision.
I have a working version of my changes pushed into my fork in ad7144c, 774d357, 3ad5527, and 7670486.
I don't think this mechanism is completely integrated (for instance, I hard code the fact that we're using extended precision). In addition, it currently causes between 10-15% slowdown. As such, I haven't issued a pull request. However, this may work for the tests you want to run, @kvaragan.
For a while now, we've been mulling over how to validate results in test-blas2. Ideally, we would be able to compare the results of a GPU-based SpM-DV calculation against a known-good CPU implementation. However, we're using floating point and comparing floating point values is hard.
This comes from two problems (which are related):
The first problem means that we cannot directly compare (bit-for-bit) the output of a CPU-based SpM-DV and a GPU-based SpM-DV. The inability to directly compare the two floating point numbers is somewhat common knowledge, and we currently compare against a range of values.
Originally, we hard-coded this to say e.g. "if in single precision, the values must be within 1e-5 of each other". I recently changed this to instead say that "in single, the values must be within 0.1% of one another". We shouldn't be comparing against a static value (because a gigantic number, e.g. 1.0e126, cannot have another number that is within 1e-5 to it in single precision -- thus we're just doing a direct comparison that is doomed to fail). However, even the (extremely loose) error bounds I've included fail for many of the matrices we're operating on.
That is due to the second issue: floating point summation has linearly-increasing error bounds and suffers from catastrophic cancellation effects that can cause large values (which are eventually subtracted out) to destroy values that, in the end, are significant. This is true even in our CPU-based algorithm. This means that our CPU and GPU results may be different and they may both be wrong.
For example, the matrix dc2 from the UFL sparse matrix collection has a couple of extremely long rows (e.g. row 91, which has 47,193 non-zero values). A simple CPU-based SpMV algorithm (where the input vector entirely contains 1s) that is calculated in single precision says that the output for row 91 is roughly -1.921. csrmv_general calculates the answer as roughly -1.857, a noticeable percentage off. csrmv_adaptive returns roughly -1.013. Much worse!
However, if you perform this calculation in higher (double, quad) precision, the answer is roughly -1.005. Both the single-precision CPU and GPU results are wrong -- and the GPU-based results are closer to the correct answer. The different calculation orders between these algorithms have all resulted in different errors -- and it's not always the case that the GPU algorithms are closer.
This leads to the problems and questions I want to raise.
I believe this issue is larger than just the test case. It's also a question about how accurate our SpM-DV should be.