Karp–Flatt metric

This article includes a improve this article by introducing more precise citations. (March 2020) (Learn how and when to remove this template message )

The Karp–Flatt metric is a measure of

as an indication of the extent to which a particular computer code is parallelized. It was proposed by Alan H. Karp and Horace P. Flatt in 1990.

Description

Given a parallel computation exhibiting speedup ${\displaystyle \psi }$ on ${\displaystyle p}$ processors, where ${\displaystyle p}$ > 1, the experimentally determined serial fraction ${\displaystyle e}$ is defined to be the Karp–Flatt Metric viz:

${\displaystyle e={\frac {{\frac {1}{\psi }}-{\frac {1}{p}}}{1-{\frac {1}{p}}}}}$

The lower the value of ${\displaystyle e}$, the better the parallelization.

Justification

There are many ways to measure the performance of a

, which can be written as:

${\displaystyle T(p)=T_{s}+{\frac {T_{p}}{p}}}$

Where:

• ${\displaystyle T(p)}$ is the total time taken for code execution in a ${\displaystyle p}$-processor system
• ${\displaystyle T_{s}}$ is the time taken for the serial part of the code to run
• ${\displaystyle T_{p}}$ is the time taken for the parallel part of the code to run in one processor
• ${\displaystyle p}$ is the number of processors

with the result obtained by substituting ${\displaystyle p}$ = 1 viz. ${\displaystyle T(1)=T_{s}+T_{p}}$, if we define the serial fraction ${\displaystyle e}$ = ${\displaystyle {\frac {T_{s}}{T(1)}}}$ then the equation can be rewritten as

${\displaystyle T(p)=T(1)e+{\frac {T(1)(1-e)}{p}}}$

In terms of the speedup ${\displaystyle \psi }$ = ${\displaystyle {\frac {T(1)}{T(p)}}}$ :

${\displaystyle {\frac {1}{\psi }}=e+{\frac {1-e}{p}}}$

Solving for the serial fraction, we get the Karp–Flatt metric as above. Note that this is not a "derivation" from Amdahl's law as the left hand side represents a

rather than a mathematically derived quantity. The treatment above merely shows that the Karp–Flatt metric is consistent with Amdahl's Law.

Use

While the serial fraction e is often mentioned in

into consideration. Using the serial fraction as a metric poses definite advantages over the others, particularly as the number of processors grows.

For a problem of fixed size, the efficiency of a parallel computation typically decreases as the number of processors increases. By using the serial fraction obtained experimentally using the Karp–Flatt metric, we can determine if the efficiency decrease is due to limited opportunities of parallelism or increases in algorithmic or architectural overhead.

References

• Karp, Alan H. & Flatt, Horace P. (1990). "Measuring Parallel Processor Performance". Communications of the ACM. 33 (5): 539–543.
  doi:10.1145/78607.78614
  .
• Quinn, Michael J. (2004). Parallel Programming in C with MPI and OpenMP. Boston: McGraw-Hill.
  ISBN 0-07-058201-7
  .

External links

• Lecture Notes on Karp–Flatt metric - Virginia Tech