Amdahl’s Law

For programs that are not 100% efficient at using multiple cores, or programs that can be divided into serial and parallel parts, Amdahl’s law is used to measure CPU’s efficiency in executing the programs.

If T(p) is the time it takes the CPU to run with p processors and the theoretical speedup is S(p) 
 then,
 S(p) = T(1) / T(p)

T(p) can be derived by getting the sum of the time it takes for serial processing and parallel processing.

Derivation

Serial processing Time. T(n, p) is the observed time it took for a CPU with p processors to execute n number of threads. ß(n, p) is the fraction of the program that must be executed with serial processing Ts(n) is the fraction of T(n, p) that was used for serial processing

Ts(n) = ß(n, 1) * T(n, 1)

Parallel Processing Time Tp(n, p) is the fraction of T(n, p) that was used for parallel processing

Tp(n, p) = ( 1-ß(n, 1) ) * T(n, 1) / p

Here, 1-ß(n, 1) is the fraction of the program that can be parallel processed.
This equation gets the time it would have taken the CPU to run parallel processed threads with serial processing and divides that with the number of processes p.

T(n, p) = Ts(n) + Tp(n, p) = [ ß(n, 1) + ( 1-ß(n, 1) ) / p ] * T(n, 1)

S(n, p) = T(n, 1) / T(n, p) = 1/ [ ß(n, 1) + ( 1-ß(n, 1) ) / p ]

&ref(https://latex.codecogs.com/gif.latex?S%28n%29%3D%5Cfrac%7BT%281%29%7D%7BT%28n%29%7D%3D%5Cfrac%7BT%281%29%7D%7BT%281%29%28B+%5Cfrac%7B1%7D%7Bn%7D%281-B%29%7D)

&ref(https://latex.codecogs.com/gif.latex?S%28n%29%3D%5Cfrac%7B1%7D%7B%281-P%29+%5Cfrac%7BP%7D%7Bn%7D%7D)

When the number of processes increases to infinity, the speedup nears 1 / ß(n, 1)

Gustafson’s Law

Same principle as Amdahl’s Law. Unlike Amdahl’s Law, the Gustafson’s Law normalizes the total time of execution T(p) = 1. Therefore,

Ts(n) + Tp(n, p) = 1 Ts(n) = ß(n, p) Tp(n) = 1- ß(n, p)

S(n, p) = ( Ts(n) + Tp(n, p)*p ) / Ts(n) + Tp(n, p) = p+ ( 1 - p) * Ts(n) = p - (p - 1) * ß(n, p)

Limitations

  • Not every tasks will have the same number of parallelization
    • Some tasks contain different amount of instructions to execute
    • Calculate parallelization efficiency for each task individually
  • Amdahl’s Law focuses on the performance of the CPU
    • It will not accurately calculate the performance if RAM or hardware performance is preventing the program from running faster
  • Majority of software in the market are coded for single core CPU

References

https://arxiv.org/pdf/0809.1177.pdf

https://www.pugetsystems.com/labs/articles/Estimating-CPU-Performance-using-Amdahls-Law-619/


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2018-07-16 (月) 15:03:11 (368d)