Leistungsbewertung

Der SEND-Befehl braucht intraplanar die Zeit t_S,intra und interplanar t_S,inter. Die Zeit für die Umwandlung Floating-Point-to-Integer wird mit t_FIC und von Integer-to-Floating-Point mit t_IFC bezeichnet. Die arithmetischen Operationen haben die Ausführungszeiten t_FADD, t_FSUB, t_FMULT, t_FDIV, t_FSQR und t_FEXP. Der LOAD-Befehl hat die Zeit t_LOAD. Jeder Befehl wird in einem Takt abgearbeitet. Deshalb wird jede Operation durch eine abstrakte Zeiteinheit beschrieben, sowohl für Kommunikationsbefehle als auch für arithmetische Operationen. Es gilt t_S,intra = t_S,inter = t_FADD = t_FSUB = t_FMULT = t_FDIV = t_FSQR = t_FEXP = t_FTC = t_ITC = t_LOAD = 1. Die Gesamtrechenzeit von Programm () kann mit t_ges Takten genau angegeben werden.
$$\begin{align*}t_{ges} = & \ 4t_{S,intra} + (2+n)t_{S,inter} + (2+n)t_{FADD} + 3... ...IV} + t_{FSQR} + t_{FEXP} + t_{FTC} + t_{ITC} + t_{LOAD} = \ 22+2n \end{align*}$$

Der parallele Algorithmus ist dann von der Zeitkomplexität T(n) = O(t_ges) = O(n). Die serielle optimale Zeit ist T^*(n) = O(n³), da jeder der n² SPPE auf einer Ebene sequentiell durchlaufen werden muß. Die Anzahl der insgesamt zu bewältigenden Arbeitsschritte des Algorithmus ist von der Größenordunng W(n) = n²*(22+2n) = O(n³). Der parallele Algorithmus ist somit optimal. Daß der Algorithmus auch streng optimal ist liegt daran, daß sich wegen der beschränkten interplanaren Kommunikation kein schnelleres Aufsummieren bewerkstelligen läßt. Erst wenn jeder Prozessor ohne zusätzlichen Zeitaufwand Zugriff auf die Daten aller anderen Prozessoren hätte, könnte man z.B. mit dem Binärbaumparadigma^2.1 die Zeit T(n) für die Summation von O(n) auf $O(\log n)$ senken.