Direkt zum Inhalt

Lexikon der Mathematik: Beschleunigungsfaktor bei Parallelisierung

Meßgröße zur Bestimmung der Effizienz der Parallelisierung eines numerischen Verfahrens.

Gegeben sei ein numerisches Verfahren, bestehend aus n Operationen, das auf einem Parallelrechner mit p Prozessoren und der Taktrate τ implementiert werden soll. Man interessiert sich dann für die Frage, wie hoch die Beschleunigung des Verfahrens durch die Parallelisierung gegenüber einer Implementierung auf einem sequentiellen Rechner ist.

Dies wird gemessen durch den Quotienten der Rechenzeit bei sequentieller und soweit wie möglich parallelisierter Implementierung, den Beschleunigungsfaktor \begin{eqnarray}B(\alpha,p) & = & \displaystyle \frac{n\tau }{(1-\alpha )n\tau +\alpha n\tau /p}\\ & = & \displaystyle \frac{1}{1-\alpha +\alpha /p}.\end{eqnarray}

Hierbei ist a, 0 < α < 1, derjenige Anteil der n Operationen, der sich gleichmäßig auf die vorhandenen p Prozessoren verteilen läßt. Diese Beziehung heißt auch Amdahls Gesetz.

Man erkennt, daß auch für eine sehr große Anzahl von Prozessoren der Beschleunigungsfaktor stets durch \begin{eqnarray}\mathop{\mathrm{lim}}\limits_{p\to \infty }B(\alpha,p)=\frac{1}{1-\alpha }\end{eqnarray}beschränkt ist.

Die mittlere Auslastung des einzelnen Prozessors wird durch die Effizienz \begin{eqnarray}\frac{B(\alpha,p)}{p}=\frac{1}{\alpha +p\cdot (1-\alpha )}\end{eqnarray} gemessen. Sie wird offenbar für wachsende Prozessorenzahl immer kleiner und strebt im Grenzfall p → ∞ gegen Null.

In der Praxis gilt eine Effizienz von 0,5 als gut und Werte von 0,8 bereits als sehr gut.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos