3 ms·
_yosefk, I'm trying to digest your argument and I'm wondering if I have this correct: 1. Concurrency is a property of any problem that involves resource conten
by kibwen 14y ago
_yosefk, I'm trying to digest your argument and I'm wondering if I have this correct:
1. Concurrency is a property of any problem that involves resource contention.
2. Parallelism is merely a performance optimization for certain classes of problems.
3. Tools that address the concurrency problem are capable of performing the parallelism optimization by recasting a problem as a resource-contention problem.
4. However, casting a problem as a resource-contention problem introduces necessary nondeterminism and likely race conditions, as these are inherent properties of the problem domain for which these tools were designed.
5. Instead, use a tool that is explicitly designed to address parallelism in a deterministic, race-free manner.
Is this the essence of your essay? Personally, I'd love to see an example of a small real-world problem solved in e.g. Erlang vs. the same solution in checkedthreads.
- jamii 14y ago> Personally, I'd love to see an example of a small real-world problem solved in e.g. Erlang vs. the same solution in checkedthreads. Wide Finder 2 would be a good demo for checkedthreads, although it does involve some amount of concurrency in io. http://www.tbray.org/ongoing/When/200x/2008/05/01/Wide-Finder-2 http://www.tbray.org/ongoing/When/200x/2008/05/01/Wide-Finde...
- _yosefk 14y agoIt's like you said, roughly, though it's certainly possible to use a system designed for concurrency without introducing non-determinism - by not letting the queues provided by the system (message queues, STM, locks, thread-safe data structures - whatever type of queue) affect semantics. As in, you could easily implement a nice load balancer in Go for computational code and you could implement a checker to make sure the code is deterministic, perhaps based on their race detector. I'm only saying that it should be done, not that it can't be done... Erlang vs checkedthreads (or Cilk or anything C-based), computing an image convolution kernel or handling some other computational problem? I could, though I think such a showdown with Erlang predictably ripped to shreds would be trolling, and I really like Erlang - I don't necessarily like Armstrong's marketing where he says Erlang makes more sense than C for parallelizing computations (seriously - you gonna send the image sub-regions via message queues byte by byte?), but I like Erlang, and it'd be a pity if anyone looked at such a silly showdown and conclude that Erlang was inferior - it's not, it's just for different things entirely.
- varelse 14y agoI 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 14y agoWell, 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 14y agoI 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.