Cacheoptimierung für OpenMP



  • Guten Tag,

    ich möchte mein Programm Cacheoptimieren um somit die Geschwindigkeit zu verbessern. Dazu habe ich mir ein paar Gedanken gemacht und möchte fragen ob diese korrekt sind.

    for (int iteration=0; iteration<100; iteration++) {
    	for (int a=0; a<150; a++) {
    		for (int b=0; b<150; b++) {
    			for (int c=0; c<150; c++) {
    				//hier findet die Berechnung mit 20 verschiedenen float-Werten für jedes a,b,c welche in einem Array abgelegt sind statt.
    			}
    		}
    	}
    }
    

    Das Array mit den float-Werten für die Berechnung besitzt also eine Größe von (20x150x150x150x4)Bytes=270MB.

    Außerdem soll die Berechnung parallelisiert werden. Dazu ist wichtig zu wissen, dass bevor ein neuer Iterationsschritt (insgesamt sind es 100) startet, alle 150 a's des akutellen Iterationsschritt fertig berechnet sein müssen, da diese für die nächste Iteration gebraucht werden.

    Deswegen denke ich, ist die beste Stelle für die Parallelisierung bei der a-Schleife, weil dadurch so wenig wie möglich Thread-Neuorganisiation stattfindet, was Zeit spart.

    omp_set_num_threads(10);
    for (int iter=0; iter<100; iter++) {
    	#pragma omp parallel for schedule(guided)
    	for (int a=0; a<150; a++) {
    		for (int b=0; b<150; b++) {
    			for (int c=0; c<150; c++) {
    				//hier findet die Berechnung mit 20 verschiedenen float-Werten für jedes a,b,c welche in einem Array abgelegt sind.
    			}
    		}
    	}
    	#pragma omp barrier
    }
    

    Wenn z.B. ein Intel® Xeon® Processor E5-2680 v2 mit 25MB Cache und 10 Kernen verwendet wird, sollte ich dann auch nur 10 Threads starten, also für jeden Kern einen Thread?

    Da sich alle 10 Kerne die 25MB Cache teilen, darf diese Grenze nicht überschritten werden, damit das Array nicht ständig neu in den Cache geladen werden muss, was Zeit kostet.

    Dazu würde ich das 270 MB Array teilen und zwar so, dass jeder Teil in den Cache passt.
    → 20x13x150x150x4=23,4MB
    → 20x7x150x150x4=12,6MB
    Das ergbit also 11 Teile mit 23,4MB und einen letzten Teil mit 12,6MB.

    omp_set_num_threads(10);
    for (int iter=0; iter<100; iter++) {
    	#pragma omp parallel for schedule(guided)
    	for (int a=0; a<13; a++) {
    		for (int b=0; b<150; b++) {
    			for (int c=0; c<150; c++) {
    				//hier findet die Berechnung mit 20 verschiedenen float-Werten für jedes a,b,c welche in einem Array abgelegt sind.
    			}
    		}
    	}
    	#pragma omp barrier
    	#pragma omp parallel for schedule(guided)
    	for (int a=0; a<13; a++) {
    		for (int b=0; b<150; b++) {
    			for (int c=0; c<150; c++) {
    				//hier findet die Berechnung mit 20 verschiedenen float-Werten für jedes a,b,c welche in einem Array abgelegt sind.
    			}
    		}
    	}
    	#pragma omp barrier
    	#pragma omp parallel for schedule(guided)
    	for (int a=0; a<13; a++) {
    		for (int b=0; b<150; b++) {
    			for (int c=0; c<150; c++) {
    				//hier findet die Berechnung mit 20 verschiedenen float-Werten für jedes a,b,c welche in einem Array abgelegt sind.
    			}
    		}
    	}
    	#pragma omp barrier
    
        //usw...
    
    	#pragma omp parallel for schedule(guided)
    	for (int a=0; a<7; a++) {
    		for (int b=0; b<150; b++) {
    			for (int c=0; c<150; c++) {
    				//hier findet die Berechnung mit 20 verschiedenen float-Werten für jedes a,b,c welche in einem Array abgelegt sind.
    			}
    		}
    	}
    	#pragma omp barrier
    }
    

    Ist diese Vorgehenweise effektiv, oder gibt es da eine bessere Methode. Übersehe ich etwas?
    Wie ist es wenn ich 2 Intel® Xeon® Processor E5-2680 v2 mit 25MB Cache und 10 Kernen verwende, dann habe ich ja 2x25MB und 2x10 Kerne. Kann ich dann irgendwie steuern welche Parallelisierung mit dem dazugehörigen Array in CPU1 stattfindet und eine welche mit dem dazugehörigen Array in CPU2 ? Oder mach ich einfach ein Array mit 50MB und setzte omp_set_num_threads auf 20 und es wird von allein geregelt?



  • Da Du auf einer vierdimensionalen Matrix arbeitest, haengt das schon davon ab, was Du in der inneren Schleife machst.

    //hier findet die Berechnung mit 20 verschiedenen float-Werten für jedes a,b,c welche in einem Array abgelegt sind statt.
    

    Das ist genau der Knackpunkt: Abhaengig davon, wie Du auf die 20 verschiedenen floats zugreifst, wird sich auch die Cache-Hit-Rate veraendern.

    Das ist dann auch noch zu beruecksichtigen, wenn Du das auf mehrere Threads verteilst. Da sollen dann nicht nur die verarbeiteten Daten voneinander unabhaengig sein, sondern sie sollten auch noch in verschiedenen Cachelines liegen.



  • @TE Studierst du zufällig im Master Informatik an der Hochschule Niederrhein ?



  • @blablub12134214 nein 🙂

    Brauche unbedingt Infos wie es ist, wenn ich mehr als einen Prozessor verwende.
    Hat da niemand einen Link?

    Kann ich irgendwie bestimmten, dass er in Cache1 von Prozessor1 ein bestimmtes Array1 läd und dann mit den 10 Kernen von Prozessor1 auch nur die Berechnungen durchführt bei denen das Array1 benötigt wird und in Cache2 von Prozessor2 ein bestimmtes Array2 läd und dann mit den 10 Kernen von Prozessor2 auch nur die Berechnungen durchführt bei denen das Array2 benötigt wird.

    Oder ist es sogar so, dass Cache1 und Cache2 quasi allen 20 Kernen gleich zur verfügung stehen, also es keinen Geschwindigkeitsunterschied macht ob ein Kern von Prozessor1 etwas aus dem Cache1 oder Cache2 holt?



  • Du kannst das AFAIK gar nicht kontrollieren, und nein, es macht schon nen deutlichen Geschwindigkeitsunterschied ob die Daten im eigenen Cache liegen oder in dem einer anderen CPU.

    Hast du die Sachen ausprobiert die ich im anderen Thread geschrieben hatte? Da ist irgendwie nix mehr von dir zurückgekommen wenn ich mich richtig erinnere...


Anmelden zum Antworten