Question: Can someone relate the notion of an inherently sequential part of the program, to the idea of span that you learned about in 15-210?
pht
The idea of span in 15-210 relates to the longest chain of dependencies in a function. Inherently sequential parts of a program are prevented from parallel execution due to dependencies, and all the inherently sequential parts of a program would contribute to the calculation of the program's span.
pajamajama
To add on to what @pht said: another way of looking at span (as described in 210) is the time an algorithm would take to do some computation if there was an infinite number of processors to use on a machine. The parts of a program that can be executed in parallel can take advantage of the unlimited processors; however, the work for the inherently sequential parts can't be split up over many processors (since those parts contain dependencies) and therefore the total time the algo takes would mainly be due to how long the sequential parts are taking.
Here, S is the fraction of stuff that has to be done sequentially and so (1-S) is the fraction of stuff that can be parallelized. If we're doing the work on a machine with n processors, then the time it takes to do the parallel part is (1-S)/n. As n goes towards infinity (i.e. as we use more processors), (1-S)/n becomes infinitely small (~0). The total time it takes to run the program with n processors = (amt of time to execute sequential stuff) + (amt of time to execute parallel stuff), so the maximum speedup due to parallel execution is 1/(S + (1-S)/n) <= 1/S.
Limitation of Amdahl's law when the fraction of sequential code is extremely small or when the total amount of parallel work is extremely greater than sequential work then Amdahl's law doesn't hold good.
Question: Can someone relate the notion of an inherently sequential part of the program, to the idea of span that you learned about in 15-210?
The idea of span in 15-210 relates to the longest chain of dependencies in a function. Inherently sequential parts of a program are prevented from parallel execution due to dependencies, and all the inherently sequential parts of a program would contribute to the calculation of the program's span.
To add on to what @pht said: another way of looking at span (as described in 210) is the time an algorithm would take to do some computation if there was an infinite number of processors to use on a machine. The parts of a program that can be executed in parallel can take advantage of the unlimited processors; however, the work for the inherently sequential parts can't be split up over many processors (since those parts contain dependencies) and therefore the total time the algo takes would mainly be due to how long the sequential parts are taking.
Here, S is the fraction of stuff that has to be done sequentially and so (1-S) is the fraction of stuff that can be parallelized. If we're doing the work on a machine with n processors, then the time it takes to do the parallel part is (1-S)/n. As n goes towards infinity (i.e. as we use more processors), (1-S)/n becomes infinitely small (~0). The total time it takes to run the program with n processors = (amt of time to execute sequential stuff) + (amt of time to execute parallel stuff), so the maximum speedup due to parallel execution is 1/(S + (1-S)/n) <= 1/S.
For anyone trying to review, here are 15-210's notes about Parallelism (Section 1.2) and Work and Span (Section 1.3). https://drive.google.com/file/d/0B4z2gzEmkDDCRkFLMm8wZGhZaFE/view
Limitation of Amdahl's law
when the fraction of sequential code is extremely small or when the total amount of parallel work is extremely greater than sequential work then Amdahl's law doesn't hold good.