World Library  
Flag as Inappropriate
Email this Article

Karp–Flatt metric

Article Id: WHEBN0009453042
Reproduction Date:

Title: Karp–Flatt metric  
Author: World Heritage Encyclopedia
Language: English
Subject: Amdahl's law, Parallel computing, Yield method, Cache invalidation, Parallel slowdown
Collection: Analysis of Parallel Algorithms, Parallel Computing
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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 the 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.

Contents

  • Description 1
  • Justification 2
  • Use 3
  • References 4
  • External links 5

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

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.