Sieb des Eratosthenes threaded umsetzen

kellerfe

Jetzt versteh ich. Wir haben mal im Rahmen einer Übung ein Prgramm geschrieben, dass einen Text "knackt", der mit einer polyalphabetischen Verschlüsselung verschlüsselt war. Wenn ich mich recht entsinne, war das mit einem Wörterbuch welches die häufigsten Wörter enthielt. Ist aber schon her, deshalb ist das mit den Strings üben keine dumme Idee.

Ich hab noch eine Frage zu dem "Minimalbeispiel":
Was hat es mit dem
pthread_mutex_lock (&mutex);
und dem
pthread_mutex_unlock (&mutex);
auf sich?
Dass da etwas gesperrt wird, ergibt sich ja, aber was?

kellerfe

Unabhängig von der vorherigen Frage, die mich natürlich immer noch interessiert:
Ich habs hinbekommen. Ich bin noch am schauen, ob man noch optimieren/verbessern kann, aber falls jemand den Code will, einfach fragen, ich leite gern weiter.

vario-500

es gab auch mal im c++ unterforum so eine frage danach und soweit ich weiß gab es da auch sehr gute lösungen, also einfach mal die forensuche bemühen

Ich hätte da jetzt eher in Richtung OpenMP gedacht. So oder so habe ich aber meine Zweifel daran, wie viel das wirklich bringt - die äußere Schleife kann man nicht parallelisieren, weil man die bisher berechneten Primzahlen braucht, und bei der inneren Schleife dürfte das Aufsetzen eines Threads ab einem gewissen Zeitpunkt mehr kosten als der Schleifendurchlauf. Dazu kommt, dass man atomischen Zugriff auf das Sieb braucht, was auch dann Performance kosten kann, wenn sich nicht mehrere Threads in die Haare kriegen.

Meine eben kurz hingekladdete OMP-Version (Code unten) läuft denn mit OpenMP auch langsamer als ohne Parallelisierung. Womöglich könnte man etwas rausholen, indem man nur für kleine i parallelisiert, aber das will dann gemessen werden, und die Messergebnisse wären höchst unportabel.

#include <stdio.h>

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(*(arr)))
char sieve[100000000] = { 1, 1, 0 };

int main(void) {
  unsigned long long i;

  for(i = 2; i * i < ARRAY_SIZE(sieve); ++i) {
    unsigned long long j;

    if(!sieve[i]) {
#pragma omp parallel for
      for(j = i * i; j < ARRAY_SIZE(sieve); j += i) {
        if(!sieve[j]) {
#pragma omp atomic
          ++sieve[j];
        }
      }
    }
  }

  for(i = 0; i < ARRAY_SIZE(sieve); ++i) {
    if(!sieve[i]) {
      printf("%d\n", i);
    }
  }

  return 0;
}

$ gcc-4.7 -O3 sieve.c
$ time ./a.out | wc -l
5761455

real    0m2.699s
user    0m2.668s
sys     0m0.148s
$ gcc-4.7 -O3 -fopenmp sieve.c
$ time ./a.out | wc -l
5761455

real    0m3.332s
user    0m8.045s <-- Das hier ist schlecht.
sys     0m0.300s

Gemessen mit gcc 4.7.0 auf Linux/x86-64, Quad-Core-CPU.

kellerfe

Ich hab mich auch mal an OpenMP gewagt und bin genau auf diesen Engpass gestoßen. Die wesentliche Verbesserung der seriellen Laufzeit rührt halt genau aus diesem parallelen Engpass. Mit der Parallelisierung der For-Schleife ist scheinbar nicht viel zu holen.

Ich meld mich nochmal, wenn mir nochwas einfällt, da muss ja was gehn, mich ha n bissl der Ehrgeiz grad^^.

knivil

char sieve[100000000]

beisst sich mit

"liste" von bis jetzt gefundenen Primzahlen

So wie beschrieben ist das Problem trivial parallelisierbar (entspricht aber nicht dem Sieb). In eine Array stehen moegliche Teiler der Zahl, die getestet werden sollen. Thread 1 sollte das erste Viertel pruefen, Thread 2 das zweite Viertel, ... wenn man beispielsweise 4 Threads verwenden moechte.

kellerfe

Ich glaube, ich beschreibe kurz, wie ich mir die serielle Implementierung des Siebes vorstelle und dann werfe ich ein paar Ideen in den Raum, wie man das m.M.n. parallelisieren könnte. (Die Implementierung wird von der am Anfang genannten Implementierung abweichen).

void sieb_seriell_opt(int *liste,int max){
    int j,i,prim,max_i;
    liste=malloc(sizeof(int));
    liste[0]=2;
    max_i=1;
    for(j=3;j<max;j+=2){
        prim=1;
        for(i=0;(sqrt(j)>=liste[i])&prim&(max_i>i);i++){
            if(!(j%liste[i])){
                prim=0;
            }
        }
        if(prim){
            max_i++;
            liste=(int *)realloc(liste,(max_i)*sizeof(int));
            if (liste == NULL)
            {
                printf("Kein virtueller RAM mehr vorhanden ... !");
                return;
            }
            liste[max_i-1]=j;
        }
    }
}

Vorteil dieser Lösung ist, dass die Liste genau so lang wird, wie unbedingt nötig. Nachteil ist, dass immer wieder Speicher allokiert wird, was es insgesamt etwas bremst.

(Mir ist klar, dass der Code alles andere als sauber ist, was die Parameterübergabe usw angeht. Ich bitte dies zu entschuldigen.)

Wenn man diese Lösung nun parallelisieren wollte, ergeben sich nach meinen Erkenntnissen folgende Ansätze:
-Man parallelisiert die äußere for-Schleife (man testet mehrere Zahlen gleichzeitig)
-Man parallelisiert die innere for-Schleife (man testet eine Zahl auf mehrere Teiler gleichzeitig)

Problem im ersten Fall: Die Liste wird vogelwild erweitert und vermutlich sind die Primzahlen danach nicht mehr der Größe nach gespeichert. Darüber hinaus geht das Speichermanagement vermutlich hops, weil die aktuelle Größe der Liste nicht jedem Thread bekannt ist

Problem im Zweiten Fall: die Variable prim gilt für alle Threads, wird also parallel bearbeitet und führt im Zweifel zu falschen Ergebnissen.

Lösung im ersten Fall: Jeder Thread legt eine weitere, eigene Liste an, die die von diesem Thread gefundenen Primzahlen enthält. Die "Testliste" ist bei allen Threads gleich. Nach Beendigung aller Threads werden die gefundenen Primzahlen der Testliste hinzugefügt und geordnet und das Spiel geht von neuem Los.
Nachteil: Es muss sortiert werden, man benötigt weitere Listen=>Speicherplatz

Lösung im zweiten Fall: Jeder Thread erhält eine eigene Variable prim und nach Beendigung aller Threads werden diese ausgewertet (simples &).
Nachteil: Weitere Variable (ist aber m.M.n. vernachlässigbar).

Ich gebe zu, das sind nur Ideen, die mir so durch den Kopf gehen. Darüber hinaus bin ich in C wirklich blutiger Anfänger, aber die Performance von C ist, vorsichtig gesagt, eine Wucht, deshalb reizt mich das extrem.

Was haltet Ihr davon?

SeppJ

Eine (oder meinetwegen auch die) übliche Parallelisierung des Siebes wäre, die Liste auf die Prozesse/Threads aufzuteilen. Der Steuerprozess/Thread schickt dann an die beteiligten Prozesse/Threads die größte derzeit bekannte Primzahl (also 2 und aufwärts). Die Prozesse markieren dann in ihrem Bereich alle Vielfachen dieser Zahl und schicken anschließend die kleinste nicht markierte Zahl an den Steuerprozess. Die kleinste Zahl die dem Steuerthread zugeschickt wurde ist die neueste größte bekannte Primzahl und wird wieder an alle Prozesse gesendet.

Diese Methode hat keinerlei Gefahr konkurrierender Zugriffe und sehr wenig Synchronisierungsaufwand. Meine gemischte Verwendung der Wörter Thread und Prozess im obigen Abschnitt ist bewusst gemacht, um hervorzuheben, dass dies sowohl Thread- als auch Prozessparallel implementiert werden kann.

Jetzt noch ein Schuss in's Blaue: Offensichtlich muss jeder Prozess einen ziemlich dicken Batzen an Zahlen haben, damit sich selbst dieser geringe Synchronisierungsaufwand lohnt. Auf heutigen Heimrechnern kann ein einzelner Prozessor den gesamten RAM in der Größenordnung von Sekunden komplett durchgehen. Beim Sieb des Erastothenes ist er dabei von der RAM-Geschwindigkeit her gebremst, nicht von seiner eigenen Rechenleistung, denn die Rechnungen sind trivial. Damit Parallelisierung auch nur irgendetwas bringt, sollte sie wohl mit mehreren Rechnern die mit einer flotten Schnittstelle verbunden sind erfolgen.

Außerdem muss man sich noch Gedanken über die Aufteilung machen, ich könnte mir gut vorstellen, dass es günstiger sein könnte, das vordere Segment größer zu wählen, da es schneller ausdünnt. Andererseits müsste man dann wieder länger auf die ersten Ergebnisse warten, bevor das Ausdünnen Effekt zeigt.

Soweit mein Senf dazu, vielleicht habe ich heute Abend mal Lust, das am konkreten Beispiel zu demonstrieren. Da ich aber nicht den Rechnercluster damit belasten werde, muss das parallele Programm mit meinem Einzelprozessorprogramm konkurrieren. Mal sehen, ob meine Vermutung oben stimmt oder nicht.

edit: Wilde Optimierungsidee: Jeder Prozess berechnet nochmal unabhängig die Primzahlen bis sqrt(N). Dann entfällt die Kommunikation zwischendurch vollständig, man hat nur die Anfangsaufteilung und die Zusammenführung der Ergebnisse. Bringt nur etwas bei Prozessparallelisierung, bei Threads hat man ja sowieso alles beisammen.

knivil

@kellerfe: Dein Ansatz ist kacke, weil du viel synchronisieren musst. Und das ist nicht das Primzahlsieb des Eratosthenes. Und mal was zum Thema: http://code.google.com/p/primesieve/

kellerfe

@knivil: Im zweiten Fall wäre der Syncaufwand nicht so gewaltig, es muss ja lediglich die prim-Variable der Schleife mit den prim-Variablen der einzelnen Threads abgeglichen werden.

Aber das das nicht mehr der klassische Sieb ist, ist wahr.

EDIT: Cooler Link btw. Werd ich aber nicht kopieren, abschreiben kann jeder ;-).

nachtfeuer

Man könnte die Aufgabe eigentlich ganz gut parallelisieren, erstmal alle geraden rausstreichen (Bytetest) dann alle 3er raus und alle 5er, dass müsste relativ schnell gehen, jeder zweite 5er sowieso schon draußen(bei 3ern und 5ern kann man in hex die Quersumme der Zahl berechnen, aber mal gucken, was schneller geht, und ausserdem müsste man zum Verleich auch mal ein typisches Atkin-Sieb ( http://de.wikipedia.org/wiki/Sieb_von_Atkin )ablaufen lassen.

Dann, was noch in der Liste steht vervielfachen und davon alles raus (geht unabhängig) und dann eben was immer noch steht miteinander ausmultiplizieren.

Zusammenstreichen und die Daten gewissermaßen defragmentieren, können auch nochmal andere Threads erledigen.

...ach ja, und das hier ist ja irgendwie auch eine nette Grafik
http://logic.pdmi.ras.ru/~yumat/personaljournal/sieve/sieve.gif

kellerfe

Das Problem mit dem "Rausstreichen" ist eventuell, dass bei sehr großem oberen Limit die Liste, aus der herausgestrichen wird, riesig wird.
Wenn man als Datentyp nicht int, sondern long long nimmt, braucht eine Liste bis 10^9 also 10^9*8Byte etwa 7,45 Gigabyte, oder hab ich da nen Denkfehler drin?

SeppJ

kellerfe schrieb:

hab ich da nen Denkfehler drin?

Ja. Du musst die Zahlen nicht abspeichern. Du kannst so viele Zahlen testen, wie du Bits (nicht Bytes!) im Computer hast.

Vielleicht erst einmal normal implementieren, dann über Parallelisierung nachdenken.

kellerfe

Seriell hätte ichs einfach so umgesetzt:

#include <stdio.h>
#include <stdlib.h>

int main(){
    int i,j,max=100000000,*liste;

    liste=(int*)calloc(max,sizeof(int));
    if(liste!=NULL){
        max++;
        liste=(int*)realloc(liste,max*sizeof(int));
    }
    while(liste==NULL){
        max--;
        liste=(int*)realloc(liste,max*sizeof(int));
        if (max<0){
             printf("Maximum negativ, beende Programm.\n");
             return -1;
        }
    }

    for (i=0;i<max;i++)
        liste[i]=i+1;

    printf("Primzahlen bis %d werden berechnet...\n",max);
    liste[0]=0;
    for(j=0;((liste[j]*liste[j])<max);j++){
        if(liste[j]){
            for(i=j+liste[j];i<max;i+=liste[j]){
                liste[i]=0;
            }
        }
    }

//    printf("Liste der Primzahlen bis: %d\n",max);
//    for (i=0;i<max;i++)
//        if(liste[i])
//            printf("%d\t", liste[i]);

    free(liste);
    return 0;
}

knivil

Also deine realloc-Sauerei finde ich nicht wirklich gut und fuehert zu memory leaks falls realloc fehlschlaegt.

kellerfe

Sauerei triffts gut, da haste recht. Beim Ausführen merkt mans spätestens, dass man das besser machen sollte.

EDIT: Wie kann man die Speicherallokation anders/besser machen? Ich bin wie gesagt Anfänger, also bin ich um jede Art von Hilfe dankbar.