From rf11@rncmm2.urz.tu-dresden.de Sat Jun 23 11:58:26 2001
Return-Path: <rf11@rncmm2.urz.tu-dresden.de>
Delivered-To: leitner-fefe-web@fefe.de
Received: (qmail 18980 invoked from network); 23 Jun 2001 09:58:26 -0000
Received: from rncmm2.urz.tu-dresden.de (141.30.67.222)
  by fefe.de with SMTP; 23 Jun 2001 09:58:26 -0000
Received: (from rf11@localhost)
	by rncmm2.urz.tu-dresden.de (8.10.2+Sun/8.10.2) id f5N9w8g00870
	for web@fefe.de; Sat, 23 Jun 2001 11:58:08 +0200 (MET DST)
Date: Sat, 23 Jun 2001 11:58:08 +0200
From: Reinhard Foerster <rf11@inf.tu-dresden.de>
To: web@fefe.de
Subject: zu deinem Cache Beispiel
Message-ID: <20010623115808.A795@rncmm2.urz.tu-dresden.de>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Status: RO
X-Status: A
Content-Length: 4581

Hallo Felix,

ich habe in den letzten Tagen ziemlich viel von www.fefe.de genossen und
dabei einige nette Sachen hinsichtlich Optimierung aufgeschnappt. Kompliment 
und Dank erstmal dafür

Bei http://www.fefe.de/devel/cacheassoc.txt hat mich zielich gewundert, daß 
es mit den größeren Arrays "nur" 30% schneller wird. Also habe ich mal ein 
bisschen rumprobiert:

  Athlon Thunderbird 900 Mhz (ich glaube den nimmst du auch, auf einer 
    anderen Seite stand IMO was von Athlon 900)
  1st lvl dcache 64k 2-way associative
  2nd lvl d+icache 265k 16-way associative
  alle Meßwerte sind über 10 Versuche gemittelt

Erstmal fällt auf, daß die Meßwerte mit deinem Programm recht stark 
schwanken. Das dürfte daran liegen, daß es pro Lauf viele - aber 
recht unterschiedlich viele - misses im lvl 2 cache gibt. Diese kommen 
aber kaum daher, das sich in der inner loop die Abschnitte der 3 Arrays 
gegenseitig aus dem 2nd lvl Cache werfen weil sie die "gleiche Adresse" für 
die cache line haben. Ein 16-wege assoz. Cache hat mit lediglich 3 cache 
lines mit "gleicher Adresse" absolut kein Problem. Das working set mit den 
3 arrays a 128k ist insgesamt ein bisschen gross für die Caches (insgesamt 
maximal 320k dache) und so muß recht oft auf den Hauptspeicher gewartet 
werden.

Hier nochmal dein Test. Das Programm ist minimal verändert (mehr Runden, 2 
neuen defines) COMP soll für COMPuted size stehen - naja.

#define SIZE   16400
#define COMP   16384
#define ROUNDS 3000

double a[SIZE], b[SIZE], c[SIZE];

void mpy(double *a,double *b,double *c,int n) {
    int i;                                     
    for (i=0; i<n; ++i)
      c[i]=a[i]*b[i];
}
 
int main() {
  double d=0,e=0;
  int i;
  for (i=0; i<COMP; ++i) {
    a[i]=(d+=1.23);       
    b[i]=(e+=2.34);
  }
  for (i=0; i<ROUNDS; ++i)
    mpy(a,b,c,COMP);      
}

Meßwerte:
  SIZE=16384  COMP=16384  ROUNDS=3000   2.596s
  SIZE=16400    "           "           1.834s (-29%)

Gut, die 30% sind also bestätigt.
Jetz mache ich mal die Arrays etwas kleiner. Damit bleibt fast alles 
wenigstens im lvl 2 cache und man kann gezielt den lvl 1 cache ärgern.

  SIZE=8192  COMP=8192    ROUNDS=10000  1.140s
  SIZE=8208    "            "           0.680s (-40%)

Die innere Schleife läuft jetzt in kürzerer Zeit viel öfter (vorher 
16k*3000, jetzt 8k*10000) weil wir kaum noch etwas mit dem Hauptspeicher 
zu tun haben. Der lvl 1 cache ist mit dieser Methode viel einfacher in die 
Knie zu zwingen, da er nur 2-wege assoziativ ist. In der inner loop 
streiten sich also 3 Kandidaten um 2 für die jeweilige Adresse zur Verfügung 
stehenden 2 cache lines. 3 auf 2 ist eigentlich noch ziemlich nett von 
uns: 
"Innen" passiert folgendes: a lesen, b lesen, c schreiben. Ziemlich 
wahrscheinlich landen a und b in den beiden verschiedenen cache lines für 
die Adresse und c überschreibt dann lediglich eine der beiden. Somit ist 
bei der nächsten iteration über i entweder a oder b noch im cache. 
(falls b noch im cache ist kann es jetzt eventuell auch beim Lesen von a
überschrieben werden, womit 2 misses auftreten. Ich nehme aber mal an,
das die Lesezugriffe von der CPU irgendwie schlau sortiert werden -
zumindest jeweils 2, damit das nicht passiert. Mein Bsp. weiter unten 
scheint diese Vermutung zu bestätigen)

Weil wir ja wieder mal gemein sind, nehmen wir nun 4 arrays:

#define SIZE   8208
#define COMP   8192
#define ROUNDS 10000

double a[SIZE], b[SIZE], c[SIZE], x[SIZE];

void mpy(double *a,double *b,double *c,double *x,int n) {
    int i;                                               
    for (i=0; i<n; ++i)
      x[i]=a[i]*b[i]*c[i];
}
 
int main() {
  double d=0,e=0,f=0;
  int i;
  for (i=0; i<COMP; ++i) {
    a[i]=(d+=1.23);       
    b[i]=(e+=2.34);
    c[i]=(f+=3.45);
  }
  for (i=0; i<ROUNDS; ++i)
    mpy(a,b,c,x,COMP);    
}

Die Meßwerte:

  SIZE=8192  COMP=8192    ROUNDS=10000  2.378
  SIZE=8208    "            "           0.972 (-59%)

Statt 3 streiten sich nun 4 cache lines um die beiden Einträge für diese 
Adresse im Cache. Die Wahrscheinlichkeit, daß a, b oder c jetzt noch aus dem 
1st lvl cache kommen, sollte gegen 0 gehen und das wollten wir ja  ;-) 
Die Performance geht dementsprechend drastisch in den Keller und die 
Vergrößerung der Arrays bringt noch mehr Gewinn als vorher.

Solche "Fehler" findet man in eigener Software sowieso nicht per Hand. Den 
neueren intel-CPUs kann man irgendwie die cache hit rates entlocken. Wie das 
genau geht weiß ich aber nicht. Damit könnte man dann ähnlich wie mit dem 
rdtscl()-makro ab und an mal testen.

  Schönes WE noch, Reinhard