Saturday, February 9, 2008

Karp-Flatt metricKarp-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.

Justification
While the Karp-Flatt metric is mentioned frequently 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.

No comments: