3 ms·
In some application domains, the program conceptually operates on a big shared data structure. The usual example applications are mesh triangulation and mesh re
by chrisseaton 12y ago
In some application domains, the program conceptually operates on a big shared data structure. The usual example applications are mesh triangulation and mesh refinement [1].
For these kind of algorithms, it is not possible to divide work up into isolated jobs that can be run entirely independently of others, as until we start solving something like a refinement problem, we don't know what parts of the graph we will need.
That rules out OpenCL and CUDA, as they want to take a job and run it to completion without having to worry about what anyone else is doing.
It also makes multi-processes less attractive. If you have isolated processes and just pass messages between them, then you have the same problem. Do you have one process that handles the shared data structure? Well then you've effectively serialised your program. Do you divide up the data structure between processes? I wouldn't know how to do that as operations may span the partitions.
Perhaps you'll use shared memory between the processes? Well then you're effectively writing multi-threaded code and you might as well use threads.
In the end the easiest way to do things that we know of is to use multiple threads, shared memory, synchronisation primitives and optimistic algorithms.
[1] K. Pingali, D. Nguyen, M. Kulkarni, M. Burtscher, M. A. Hassaan, R. Kaleem, T.-H. Lee, A. Lenharth, R. Manevich, M. M. ndez-Lojo, D. Prountzos, and X. Sui, “The Tao of Parallelism in Algorithms,” presented at the Proceedings of the 32nd Conference on Programming Language Design and Implementation (PLDI), 2011.
- aardvark179 12y agoThank you for being a voice of sanity on this Chris. There seems to be a terrible amount of cargo culting around safe concurrent programming and the reinvention of the wheel just because somebody heard the original wheel was bad (c.f. Processes and shared memory vs. threads), and the hope that CSP and similar schemes will act as a magik bullet. In the end you need to think carefully about the design of your program, work out what races might occur, and try encapsulate any shared state mutation in as small an area as possible where it can be sensibly reasoned about. Remember that using concurrent data structures will not automatically make your code safe, put in comments saying why any shortcut you take is safe, and do really thorough code review.