Karp–Flatt metric

The Karp–Flatt metric is a measure of parallelization of code in parallel processor systems. This metric exists in addition to Amdahl's law and Gustafson's law 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 $\psi$ on $p$ processors, where $p$ > 1, the experimentally determined serial fraction $e$ is defined to be the Karp–Flatt Metric viz:

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

The less the value of $e$ the better the parallelization.

Justification

There are many ways to measure the performance of a parallel algorithm running on a parallel processor. The Karp–Flatt metric defines a metric which reveals aspects of the performance that are not easily discerned from other metrics. A pseudo-"derivation" of sorts follows from Amdahl's Law, which can be written as:

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

Where:

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

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

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

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

{\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 metric 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 computer science literature, it was rarely used as a diagnostic tool the way speedup and efficiency are. Karp and Flatt hoped to correct this by proposing this metric. This metric addresses the inadequacies of the other laws and quantities used to measure the parallelization of computer code. In particular, Amdahl's law does not take into account load balancing issues, nor does it take overhead 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". Communication 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

Parallel computing

General	Distributed computing Cloud computing High-performance computing

Levels	Bit Instruction Task Data Memory Loop Pipeline

Multithreading	Temporal Simultaneous Preemptive Cooperative

Theory	PRAM model Analysis of parallel algorithms Amdahl's law Gustafson's law Cost efficiency Karp–Flatt metric Slowdown Speedup

Elements	Process Thread Fiber Instruction window

Coordination	Multiprocessing Memory coherency Cache coherency Cache invalidation Barrier Synchronization Application checkpointing

Programming	Stream Processing Dataflow programming Models Implicit parallelism Explicit parallelism Concurrency Non-blocking algorithm

Hardware	Flynn's taxonomy SISD SIMD MISD MIMD Dataflow architecture Pipelined processor Superscalar processor Vector processor Multiprocessor symmetric asymmetric Memory shared distributed distributed shared UMA NUMA COMA Massively parallel computer Computer cluster Grid computer

APIs	Ateji PX Boost.Thread Charm++ Cilk Coarray Fortran CUDA Dryad C++ AMP Global Arrays MPI OpenMP OpenCL OpenHMPP OpenACC TPL PLINQ PVM POSIX Threads RaftLib UPC TBB

Problems	Embarrassingly parallel Software lockout Scalability Race condition Deadlock Livelock Starvation Deterministic algorithm Parallel slowdown

Category: parallel computing Media related to parallel computing at Wikimedia Commons

This article is issued from Wikipedia - version of the 11/25/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.