Karp -Flatt -Metrik

Das Karp -Flatt -Metrik ist ein Maß von Parallelisierung von Code in Parallelprozessor Systeme. Diese Metrik existiert zusätzlich zu Amdahls Gesetz und Gustafsons Gesetz als Hinweis darauf, inwieweit ein bestimmter Computercode parallelisiert ist. Es wurde 1990 von Alan H. Karp und Horace P. Flatt vorgeschlagen.

Beschreibung

Angesichts einer parallelen Berechnung ausgestellt beschleunigen ${\ displayStyle \ psi}$ an ${\ displayStyle p}$ Prozessoren, wo ${\ displayStyle p}$ > 1 die experimentell bestimmte serielle Fraktion ${\ displayStyle e}$ ist definiert als Karp -Flatt -Metrik, nämlich:

$oder$

Je niedriger der Wert von ${\ displayStyle e}$, desto besser die Parallelisierung.

Rechtfertigung

Es gibt viele Möglichkeiten, die Leistung von a zu messen Parallelalgorithmus auf einem parallelen Prozessor laufen. Die Karp -Flatt -Metrik definiert eine Metrik, die Aspekte der Leistung zeigt, die nicht leicht aus anderen Metriken erkennen können. Eine Art Pseudo- "Derivation" folgt aus Amdahls Gesetz, was geschrieben werden kann wie:

${\ displayStyle t (p) = t_ {s}+{\ frac {t_ {p}} {p}}}$

Wo:

• ${\ displayStyle t (p)}$ ist die Gesamtzeit für die Codeausführung in a ${\ displayStyle p}$-prozessorsystem
• ${\ displayStyle t_ {s}}$ ist die Zeit, die der serielle Teil des Codes ausführen muss
• ${\ displayStyle t_ {p}}$ ist die Zeit, die der parallele Teil des Codes in einem Prozessor ausführen kann
• ${\ displayStyle p}$ ist die Anzahl der Prozessoren

mit dem Ergebnis, das durch Substituieren erzielt wurde ${\ displayStyle p}$ = 1 nämlich. ${\ displayStyle t (1) = t_ {s}+t_ {p}}$, wenn wir die serielle Fraktion definieren ${\ displayStyle e}$ = ${\ displaystyle {\ frac {t_ {s}} {t (1)}}}$ Dann kann die Gleichung als umgeschrieben werden

${\ displayStyle t (p) = t (1) e+{\ frac {t (1) (1-e)} {p}}}$

In Bezug auf die beschleunigen ${\ displayStyle \ psi}$ = ${\ displayStyle {\ frac {t (1)} {t (p)}}}$:

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

Wenn wir für die serielle Fraktion lösen, erhalten wir die KARP -Flatt -Metrik wie oben. Beachten Sie, dass dies keine "Ableitung" aus dem Amdahlschen Gesetz ist, da die linke Seite a metrisch eher als eine mathematisch abgeleitete Menge. Die obige Behandlung zeigt lediglich, dass die Karp -Flatt -Metrik mit dem Amdahlschen Gesetz übereinstimmt.

Verwenden

Während die serielle Fraktion E oft in erwähnt wird Informatik Literatur, es wurde selten als diagnostisches Werkzeug so verwendet beschleunigen und Effizienz sind. Karp und Flatt hofften, dies zu korrigieren, indem sie diese Metrik vorgeschlagen hatten. Diese Metrik befasst sich mit den Unzulänglichkeiten der anderen Gesetze und Größen zur Messung der Parallelisierung des Computercode. Insbesondere das Gesetz der Amdahl berücksichtigt nicht Lastverteilung Probleme, und es dauert auch nicht Überkopf in Betracht. Die Verwendung der seriellen Fraktion als Metrik bietet eindeutige Vorteile gegenüber den anderen, insbesondere wenn die Anzahl der Prozessoren wächst.

Für ein Problem der festen Größe nimmt die Effizienz einer parallele Berechnung typischerweise mit zunehmender Anzahl der Prozessoren ab. Durch die Verwendung der seriellen Fraktion, die experimentell unter Verwendung der Karp -Flatt -Metrik erhalten wurde, können wir feststellen, ob die Effizienzabnahme auf begrenzte Parallelitätsmöglichkeiten oder eine Erhöhung des algorithmischen oder architektonischen Overheads zurückzuführen ist.

Verweise

• Karp, Alan H. & Flatt, Horace P. (1990). "Parallele Prozessorleistung messen". Kommunikation der ACM. 33 (5): 539–543. doi:10.1145/78607.78614.
• Quinn, Michael J. (2004). Parallele Programmierung in C mit MPI und OpenMP. Boston: McGraw-Hill. ISBN 0-07-058201-7.

Externe Links

• Vorlesungen zur Karp -Flatt -Metrik - Virginia Tech