5 ms·

I use deterministic results as my #1 debugging tool. I do this by building queue-based concurrent systems with a resulting nondeterministic order of execution

by varelse 13y ago

I use deterministic results as my #1 debugging tool. I do this by building queue-based concurrent systems with a resulting nondeterministic order of execution but I then insure that the results themselves are deterministic. Consider it to be a single queue with multiple vending machines to process requests. No one knows which vending machine will dispense their soda, but they will always get the soda they desire. No need for special tools there. The overhead of insuring a deterministic result I'd estimate is <2% (the use of 32-bit float to 64-bit int type conversions (fixed point) and 64-bit versus 32-bit atomic operations on GPUs for accumulation). The biggest problems I run into are end users who'd happily trade that predictable output for that <2% perf gain and competitors who are happy to oblige them. And the problem there is that I don't know how you diagnose race conditions or the quality of the underlying algorithm without a deterministic output from a deterministic input. Recently, someone told me they address this problem by running single-threaded to check for race conditions. Sigh... But I guess that lets them evaluate the model.

_yosefk 13y ago
Well, I wouldn't call that "concurrency" just because there's a queue in it - I'd call it "parallel but not concurrent"; or we can call it differently - I really don't claim to use the terms in "the right way" - but that's what I was referring to as "parallel, not concurrent", anyway. "Insure that the results are deterministic" - how? Race detectors deterministically insure that results are deterministic :) which I always found nice... "No special tools" - you mean you just run the thing several times and check the results don't change, or "just" write the code correctly? How do you know it's yielding deterministic results except that it's supposed to do so by design without any tools?
- varelse 13y ago
  I run the code multiple times on different GPUs of the same generation (not necessarily the same model) in different physical machines and get the same bit-accurate output. You're right, technically, there could be a race condition somewhere somehow that just doesn't fire very often. It isn't proven to be free of race conditions, but in practice I suspect it is so (right up until it isn't, a situation often detected by end users using a code path in a unique way, at which point it's a bug, and I fix it). But in practice, since it works like gangbusters to find broken GPUs if one checks for that deterministic output on known working examples, even finding broken GPUs that otherwise pass existing memory tests, I'm reasonably sure it works.
  - _yosefk 13y ago
    I see; deterministic by design then. I guess I'd trust myself without much tooling as well; my background is a hundred of developers hacking on a million of lines of code, hence my love for automated debugging tools.
    - varelse 13y ago
      Heh, this is one of the main arguments I make in support of deterministic results - hundreds of developers are nearly guaranteed to introduce race conditions - and if your output isn't deterministic, how else can you detect them? I don't even trust myself to not introduce them hence the harping on determinism. It mostly falls on deaf ears though. I would love an automated tool that genuinely found these for me. I would immediately incorporate it into my QA tests.
      - _yosefk 13y ago
        Seriously? I mean, it can't be that hard; if the GPU code is written in OpenCL then it could be cross-compiled to the CPU instead of the GPU and then the checkedthreads checker or the Cilk checker or some such would be almost applicable to the problem, perhaps with minor tweaks. We can discuss it here or you can drop me a line at Yossi.Kreinin@gmail.com - it sounds like an interesting thing to hack on, and not incredibly difficult, though I may be missing something and I'm curious to find out what.
  - varelse 13y ago
    PS in my experience, the existing automated GPU tools for finding race conditions Heisenberg the process sufficiently that the race conditions stop occurring. So in practice, I end up running the code as usual, but writing all the intermediate data to a buffer, dumping that to a file with a key for ordering it, sorting it, and then diffing an enormous text file to find out what's inconsistent between two runs.
    - _yosefk 13y ago
      If race detectors so behave, then they aren't very good race detectors - most aren't good, in fact, because they can't be very good, because they support concurrency (that's why Helgrind misses bugs and Cilkscreen doesn't), which was a part of my point. It's a pity if GPUs, which are really a platform for computation acceleration and not for concurrent event handling, lack deterministic race detectors; a good detector not only wouldn't mask a bug that was occurring, but it would detect a bug which perhaps you never observed until running the tool.

by varelse 13y ago

_yosefk 13y ago

Well, I wouldn't call that "concurrency" just because there's a queue in it - I'd call it "parallel but not concurrent"; or we can call it differently - I really don't claim to use the terms in "the right way" - but that's what I was referring to as "parallel, not concurrent", anyway. "Insure that the results are deterministic" - how? Race detectors deterministically insure that results are deterministic :) which I always found nice... "No special tools" - you mean you just run the thing several times and check the results don't change, or "just" write the code correctly? How do you know it's yielding deterministic results except that it's supposed to do so by design without any tools?

varelse 13y ago
I run the code multiple times on different GPUs of the same generation (not necessarily the same model) in different physical machines and get the same bit-accurate output. You're right, technically, there could be a race condition somewhere somehow that just doesn't fire very often. It isn't proven to be free of race conditions, but in practice I suspect it is so (right up until it isn't, a situation often detected by end users using a code path in a unique way, at which point it's a bug, and I fix it). But in practice, since it works like gangbusters to find broken GPUs if one checks for that deterministic output on known working examples, even finding broken GPUs that otherwise pass existing memory tests, I'm reasonably sure it works.
- _yosefk 13y ago
  I see; deterministic by design then. I guess I'd trust myself without much tooling as well; my background is a hundred of developers hacking on a million of lines of code, hence my love for automated debugging tools.
  - varelse 13y ago
    Heh, this is one of the main arguments I make in support of deterministic results - hundreds of developers are nearly guaranteed to introduce race conditions - and if your output isn't deterministic, how else can you detect them? I don't even trust myself to not introduce them hence the harping on determinism. It mostly falls on deaf ears though. I would love an automated tool that genuinely found these for me. I would immediately incorporate it into my QA tests.
    - _yosefk 13y ago
      Seriously? I mean, it can't be that hard; if the GPU code is written in OpenCL then it could be cross-compiled to the CPU instead of the GPU and then the checkedthreads checker or the Cilk checker or some such would be almost applicable to the problem, perhaps with minor tweaks. We can discuss it here or you can drop me a line at Yossi.Kreinin@gmail.com - it sounds like an interesting thing to hack on, and not incredibly difficult, though I may be missing something and I'm curious to find out what.
- varelse 13y ago
  PS in my experience, the existing automated GPU tools for finding race conditions Heisenberg the process sufficiently that the race conditions stop occurring. So in practice, I end up running the code as usual, but writing all the intermediate data to a buffer, dumping that to a file with a key for ordering it, sorting it, and then diffing an enormous text file to find out what's inconsistent between two runs.
  - _yosefk 13y ago
    If race detectors so behave, then they aren't very good race detectors - most aren't good, in fact, because they can't be very good, because they support concurrency (that's why Helgrind misses bugs and Cilkscreen doesn't), which was a part of my point. It's a pity if GPUs, which are really a platform for computation acceleration and not for concurrent event handling, lack deterministic race detectors; a good detector not only wouldn't mask a bug that was occurring, but it would detect a bug which perhaps you never observed until running the tool.