3 ms·
I don't program in Go, so I can't speak to that. The fork-join model generally starts off with one-thread, often called "The Single" or "The Master". Its where
by dragontamer 6y ago
I don't program in Go, so I can't speak to that.
The fork-join model generally starts off with one-thread, often called "The Single" or "The Master". Its where main() begins.
But somewhere along the line, you discover a portion of code that needs to be multithreaded. So you fork into many threads: maybe dozens of threads, or thousands in the case of SIMD or GPUs. This multithreaded portion is then "joined", that is, the "master" thread refuses to continue until all children are done executing.
Lets say there's a raytracer you are writing.
main() {
// In the "Single" thread
Foo();
Bar();
fork(doRayCastingInParallel(), 5-million); // Spawns 5,000,000-threads, one for each ray
// Implicitly wait for all 5-million threads to finish
doSomethingElse();
}
Now, raycasting has a bunch of things to do, but you can break it up into the same steps for all 5-million threads.
doRayCastingInParallel(int myIdx){
doTrigonometry(ray[myIdx]);
findCollision(ray[myIdx]);
outputColor[myIdx] = calculateColors(ray[myIdx]);
}
So from both the "single" thread, as well as your "child" thread, it feels like you're writing single-threaded code. But in actuality, your "child" thread is a 5-million spawned copy, executing in gross parallelism.
The "Fork-Join" model assigns a different "myIdx" number to each thread. So Ray#500 knows to do things differently than Ray#68121.
But otherwise, they run through the same code.
---------------
The important bit here is how general this mindset is. Its commonly used for GPU-programming (CPU issues a GPU command to spawn millions of threads often one-per-pixel, or even thousands per pixel). Then the CPU waits for the GPU threads to finish, and then just carries on.
But ISPC proved that you can use this fork-join model on SIMD units like AVX512 or SSE. Julia and Python are showing off how you can use it in higher level languages. Etc. etc.
OpenMP further proves that fork-join works on normal CPU threads. Maybe there's some other CPU-threading languages (but OpenMP is the one I'm personally familiar with).
- pkulak 6y agoIsn't that how nearly all multi-threaded code is written? Wouldn't the only other option be fire-and-forget? I've been writing code like this is nearly every language I've ever used for decades. Are you talking about the actual fork() function, instead of, say, spawning inside a loop explicitly?
- dragontamer 6y ago> Isn't that how nearly all multi-threaded code is written Producer-consumer queues say otherwise. As does Async. There's also message-passing. There's also thread-pools. Task-based programming doesn't wait for the tasks to finish. So without the "join", you don't have an easy synchronization point to rely upon, and have to use explicit locks for synchronization. ------ Producer - consumer can't work with fork/join, because there's no "join" at all! The producer keeps producing, and the consumers just keep consuming. Async is... a tangled mess. I'm pretty sure its just the modern "unstructured goto" style of spaghetti that has been rediscovered. Yeah, its super-efficient, but no, its not really easy to program. Task-based parallelism is probably my next favorite style. Fork-join is super easy, but the join causes a significant waiting period and underutilization of the processor. Task-based provides more flexibility (at the cost of a little bit more complexity). ------ There's a ton of other models of parallelism. But fork-join seems to be the methodology that more and more work is being focused on.
- leephillips 6y agoAs I mention in the article, Julia has task-based parellelism now, with a @spawn macro.
- dragontamer 6y agoThat's wonderful to hear! I'm looking into it: and it looks like "Stupid Fibonacci" proves that its working in Julia (https://julialang.org/blog/2019/07/multithreading/ https://julialang.org/blog/2019/07/multithreading/). Task-based parallelism is fraught with more overhead than other patterns. But it really is a powerful construct: converting recursive ideas into multithreaded concepts rather easily.
- nbadg 6y ago> Async is... a tangled mess. I'm pretty sure its just the modern "unstructured goto" style of spaghetti that has been rediscovered. Yeah, its super-efficient, but no, its not really easy to program. That's not inherent to async though, just a property of the implementations that have seen widespread adoption. There's nothing stopping async from implementing the same process tree semantics; in fact, there's at least one high-level async library that does exactly that (python-trio, https://trio.readthedocs.io/en/stable/ https://trio.readthedocs.io/en/stable/)
- peheje 6y ago"thousands in the case of SIMD or GPUs" What does 'Single Instruction Multiple Data' have to do with threads? Also fork join sounds just like normal threads to me in the way you are describing it. Sorry what an I missing?
- dragontamer 6y agoFork join by and large doesn't use mutexes. If you need to synchronize, wait for the next fork/join cycle instead of doing explicit mutexes. The "join" provides your synchronization point. If you have a complicated set of highly-synchronous calculations, then you don't fork at all. You simply use the "Single Thread" to perform all those calculations (and therefore negate the need of cross-thread synchronization). Fork-join has low-utilization, but its very easy to program. In some cases, fork-join remains efficient (ex: spawn a thread per pixel on the screen), because all pixels do NOT need to synchronize with each other (or call mutexes). ----- If a sync point within the children are needed, you usually make due with a barrier instead of a mutex. > What does 'Single Instruction Multiple Data' have to do with threads? SIMD processors, such as GPUs, emulate a thread in their SIMD units. Its called a "CUDA Thread". Its not a true thread in the sense of CPU-threads, but the performance by-and-large scales as if it were real threads. (With exception of the "thread-divergence problem") Ultimately, the fork-join model translates trivially to SIMD. Any practitioner of CUDA, OpenCL, ROCm, or ISPC can prove that to you easily.
- jschwartzi 6y agoYeah in this model you wouldn't need a mutex because each "thread" is independent and operates either on independent data or uses constant-but-shared data. As soon as the result of one thread depends on the result of another thread you have to have some mechanism for synchronization. I mean it's not really any different from writing a C/C++ program that avoids use of mutexes by having each thread operate on separate parts of the process address space. I'm still intrigued but it's not mind-blowing to me to fork a bunch of threads and join them when the function execution completes.
- 6y ago