In: Computer Science
A friend suggests that the prive sieve problem is embarrassingly parallel and can be completed without using locks, because shared variables are only ever written to as booleans (i.e., set from FALSE to TRUE), so race conditions are not a concern as it matters not how many times a number has been crossed out. You agree. Your friend then suggests that, therefore, using 1000 threads to solve this problem will speed up your program 1000-fold. Argue for or against this statement.
Using 1000 threads to solve this problem will speed up your program 1000-fold is not true.The reasons are as follow-
1=We can divide the problem into completely independent parts, where “completely independent” means I don’t have to wait for an answer to one part before going ahead and working on another part. If the answer is “yes” I can keep adding threads until I have as many threads as there are cores. For this kind of problem, 2 threads will be close to twice as fast as 1 thread, and 4 threads will be close to twice as fast as 2 threads. If the answer is “no” then more threads won’t help.
2=A multithreaded program always has more work to do than a single threaded one: in addition to computing the same result, it also has to do some extra work to coordinate multiple threads.A multithreaded program can still finish faster than a sequential one, because some of the work it does can proceed simultaneously.
3=If you program things where the tasks can’t be run in parallel and threads are waiting on each other frequently then the program will be slower. The threads would simply be taking turns using the CPU, and there is a cost of context switching between the threads, so the program would actually be slower.
4=In most threaded programs, all communication between threads is done via global variables. So even if you consider globals to be evil, they are a necessary evil in threads programming.