Optimierung von Speicherzugriffen

Neben der Vektorisierung ist die Optimierung von Speicherzugriffen eine Möglichkeit, sein Programm merklich zu beschleunigen. Insbesondere sollte man versuchen, Bankkonflikte zu vermeiden. Dazu reicht es oft schon, wenn man die Dimensionen seiner Arrays ungerade wählt, vor allem aber keine Zweierpotenzen benutzt. Folgendes Beispiel zeigt die Auswirkungen:

           PROGRAM BENCH

     C        LOESUNG EINES LINEAREN GLEICHUNGSSYSTEMS: AX=B

           INTEGER   N
           PARAMETER (N=128)

           REAL * 4  A(N,N), B(N)
           INTEGER   IPVT(N)
           REAL * 4  CPUTIME, RAND
           REAL * 4  OP, T1, T2
           INTEGER   I, J, INFO


     C     DEFINITION DER MATRIX A UND DER RECHTEN SEITE B

           DO  I = 1, N
              B(I) = 100.0 * RAND(0)
              DO J = 1, N
                 A(I,J) = 10.0 * RAND(0)
              ENDDO
           ENDDO

     C     LU-ZERLEGUNG DER MATRIX A OHNE KONDITIONSABSCHAETZUNG

           T1 = CPUTIME(0.0)
           CALL SGEFA(A,N,N,IPVT,INFO)

           IF(INFO .EQ. 0) THEN
              CALL SGESL(A,N,N,IPVT,B,0)
              T2 = CPUTIME(T1)
              OP = 0.67*N**3 + 2*N**2
              PRINT*, 'MFLOPS: ', OP/(T2*1.0E+06), ', DIM N: ', N
           ELSE
              PRINT*, 'MATRIX NUMERISCH SINGULAER'
           END IF

           END

Die folgende Tabelle zeigt die MFLOPS-Ergebnisse für verschiedene Arraygrößen (alle Zahlen Mittelwerte über jeweils fünf Läufe):

N	P(N-1)		P(N)		.	P(N+1)		.	PM(N)		.	DP(N)
	[MFLOPS]		[MFLOPS]		.	[MFLOPS]		.	[MFLOPS]		.	[%]
											.
64	69	.	2	31	.	5	65	.	2	67	.	2	53
128	123	.	8	61	.	4	130	.	3	127	.	1	52
256	139	.	5	83	.	2	146	.	3	142	.	9	42
512	154	.	7	112	.	4	159	.	2	157	.	0	28
1024	173	.	0	144	.	7	174	.	5	173	.	8	17

Dabei ist

$$\mbox{PM}(N) = 0.5 * (\mbox{P}(N-1) + \mbox{P}(N+1))$$

und

$$\mbox{DP}(N) = (\mbox{PM}(N) - \mbox{P}(N)) / \mbox{PM}(N) * 100\% \mbox{.}$$

Man sieht deutlich die Auswirkung der Bankkonflikte bei Zweierpotenzen als Array-Dimensionen. Ihr Einfluß nimmt mit steigendem N ab, wie DP(N) zeigt. Dies liegt zum einen daran, daß die Zahl der Speicherzugriffe relativ zur Zahl der arithmetischen Operationen abnimmt. Zum anderen hat man mit wachsender Problemgröße mehr Möglichkeiten, durch Umstellen der Reihenfolge von Operationen die Speicherwartezeit sinnvoll mit etwas anderem als Warten zu verbringen. Bei den hochoptimierten VECLIB-Routinen kann man sicher sein, daß diese Möglichkeiten sehr weitgehend ausgenutzt werden.
Im Abschnitt 4.1 wurde schon darauf hingewiesen, daß Rechnungen mit einfacher statt doppelter Genauigkeit doppelt so schnell sind. Ändert man im Programm BENCH die Arrays auf REAL8 und die VECLIB-Aufrufe in die entsprechenden für doppelte Genauigkeit (DGEFA und DGESL), erhält man z.B. bei N$=$129 einen Wert von 73.1 MFLOPS, also tatsächlich nur wenig mehr als die Hälfte.