A question fell on my test of Operating Systems and I was in doubt. During the test I got confused and I marked the alternative D, today I know that she is wrong and has nothing to do. I'm tending more to alternative A, given that the maximum performance was achieved with 8 threads and the machine has 16 processors. Can someone help me? Important: There may be 1, 2, 3 or 4 correct alternatives.
Here's the question:
This graph shows something very important when it comes to parallel algorithms: there is a limit on the performance gain that is obtained with parallel algorithms, that is, the increase in the number of processors used indiscriminately can mean a worsening of (a term used to measure the performance of parallel algorithms, if compared to the best sequential version or with the parallel algorithm itself running on only a processor).
Note that I am not citing the term thread , since parallel algorithms can run in heterogeneous environments, ie on different computers, even at different locations (see grid computing). >
It is clear in this graph that with 8 processors you get the highest speedup . From there, speedup drops as the number of processors increases. This kind of behavior is natural in parallel algorithms.
Note that when a problem is parallelized, there is a need for communication between processes (or at least the central node) to solve the problem. This communication can occur only at the end, to consolidate the result produced by each process or can occur at all times during the computation. So the more processors, the more time it takes to communicate, and that's one of the reasons for speedup to fall with the increase in processors.
Another important reason is granularity. One can divide the problem into many small parts which depending on the problem can make it inefficient. In addition, there may be many pieces of sequential code, and this may also undermine the speedup (Amdahl's Law).
Short analogy
In this sense, an interesting analogy is made when it comes to project management. Doubling the number of people on a project does not mean it will be delivered in half the time. On the contrary, it can mean a delay, since it is necessary to coordinate all these people together for the delivery of the project. Likewise, if there is a person in the project that accumulates many functions, then there will be a delay, even if there are other people to do (analogy of parallel algorithms that have a lot of sequential code).
Getting back to the subject ...
This obviously varies from problem to problem. IO-bound problems (where IO is spent more than IO than CPU) behave in a way. Already CPU-bound problems (where a lot of CPU is used and little IO), behave in another. You must understand your problem to know the limit on the number of processors.
In the question scenario, we have:
A - incorrect. Since the increase in the number of threads represented (from 8, exclusive) a decrease in performance ( speedup ). That is, there were enough threads to solve the problem.
C - I think I'm incorrect, but I'm still analyzing. Initial Argument: The machine was harnessed to its full potential when 16 or more threads were used. Do not confuse with the algorithm properly.
D - incorrect. Obviously using 4 threads you spend less resource (in this case colors ) than 16.
So you get the answer B.
Answer B says that implementations with 4 threads or less had a gain above 90% of the maximum theoretically possible.
I'm understanding gain as efficiency. The efficiency is calculated by the following formula: eficiencia = speedup/p . Where p is the number of processors.
Thus, in the ideal case where (speedup = p), we have an efficiency of 100% (theoretical efficiency).
You can see from the chart that up to 4 threads efficiency was above 90%. Example of the clause for 4 threads: 3,8/4=95% . 3,8 is the speedup, found on the Y axis of the graph. 4 is the number of threads found on the X axis.
Note: 3,8 is an approximation, since the scale of the graph is 1 in 1.
