Sieb des Eratosthenes threaded umsetzen

kellerfe

Einen schönen Samstag, die Damen und Herren!

Zunächst mal die Basics:

Ich habe grundlegende Kenntnisse in Java und C und fortgeschrittene Kenntnisse in ABAP (nicht steinigen bitte). "C von A bis Z" hab ich mir zu Gemüte geführt, ich bin also über die Basics im Bilde.

Da ich nicht total in der ABAP-Welt versauern will, hab ich mir ein kleines Progrämmchen vorgenommen. Es geht, wie der Titel schon sagt, um den Sieb des Eratosthenes, den ich threaded umsetzen will.
Ich hab also in meinem Programm eine Funktion
"int prim_test(int zahl, int index);"
, die die übergebene "zahl" auf prim testet und 1 im Erfolgsfall und 0 sonst zurück gibt. Der "index" gibt an, wie groß die (global definierte) "liste" von bis jetzt gefundenen Primzahlen ist (da wäre es vermutlich klüger gewesen, ein struct zu definieren, dass die "liste" einerseits und die Größe andererseits enthält). Diese Funktion ist also der eigentliche Sieb. Soweit so simpel.
Die Funktion wird in einer while-Schleife aufgerufen. Da jetzt stumpf jede Zahl nacheinander abgeprüft wird, wird nur ein Kern meiner CPU ausgelastet.

Für die Parallelisierung sind mir jetzt zwei Möglichkeiten gekommen:
- In der while-Schleife rufe ich "prim_test()" mehrfach auf;
- In der "prim_test()" prüfe ich die "zahl" durch mehrere Elemente der "liste" gleichzeitig

Ich bin so frei und poste die prim_test, damit man sich ein Bild machen kann:

int prim_test (int zahl, int index)
{
    int i;
    for(i=0;i<index;i++)
        if (sqrt(zahl)>=liste[index])
            if (zahl%liste[i]==0)
                return 0;
        else
            return 1;
    return 1;
}

Es handelt sich also um den "Standard-Sieb".

Ich hab mir jetzt in "C von A bis Z" das Beispiel zu den POSIX-Threads durchgelesen. Die Frage ist jetzt: Wie bekomme ich den Rückgabewert von der "prim_test()"? Die Funktion "pthread_create()" scheint von der übergebenen Funktion als Rückgabewert einen Pointer auf void zu verlangen, oder ist das nur, damit beliebige Pointer zurückgegeben werden können? Oder muss ich da zusätzlich mit "pthread_join()" arbeiten? Und warum will "pthread_join()" für den Rückgabewert ein "void **thread_return", also einen Pointer auf einen Pointer?

Sorry, dass ich da so wenig Ahnung habe, aber vielleicht kann mir ja geholfen werden.

LG Felix

P.S: Auf Wunsch kann ich auch den ganzen Code anhängen, sind nur ca 70 Zeilen. Ich hab allerdings in den FAQ gelesen, dass das nicht erwünschst ist.

EDIT: Da ich grad gelesen hab, das "C von A bis Z" hier verpönt ist, muss ich noch ein paar Dinge hinzufügen.
Ich studiere Informatik, also habe ich die grundlegenden Konzepte nicht nur aus "C von A bis Z".
Ich bin beim Programmieren Pragmatiker, kein Idealist. Das Ziel ist das Ziel, nicht der Weg. Es muss funktionieren, obs dabei 100% korrekt ist, ist mir ehrlich gesagt einerlei.
Und bedenkt folgendes: Programmieren ist wie Fitness. Motivation ist alles.

C++ Forumbot

Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C (C89 und C99) in das Forum Linux/Unix verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Wutz

kellerfe schrieb:

"C von A bis Z" hab ich mir zu Gemüte geführt, ich bin also über die Basics im Bilde.

Prinzipiell eine naive Annahme und prompt in diesem Fall auch schon falsch.

kellerfe schrieb:

Ich bin beim Programmieren Pragmatiker, kein Idealist.

Subjektive Meinung aller, die die 1000fach gemachten Fehler nochmal machen wollen.

kellerfe schrieb:

Das Ziel ist das Ziel, nicht der Weg.

Dann programmiere doch in ABAP.

kellerfe schrieb:

Es muss funktionieren, obs dabei 100% korrekt ist, ist mir ehrlich gesagt einerlei.

Ein nicht 100% korrektes Programm funktioniert nicht.

Für deinen C-Einstieg hast du dir ein diffiziles Thema ausgesucht, und wie du durch das Verschieben vielleicht schon bemerkt hast, sind pthreads kein C-Standard, sondern POSIX.

Prinzipiell arbeiten pthreads mit Funktionen der Form

void* fkt(void*);

Das Argument übergibst du bei pthread_create, den Rückgabewert kannst du dir von pthread_join geben lassen, deswegen void* *.
Auch musst du für die Synchronisation selber sorgen, d.h. deine Daten für jeden Thread extra übergeben oder mit Mutexen voreinander schützen (pthread_mutex_lock/unlock).
Außerdem darfst du keine nichtmultithreadfähigen sonstigen Funktionen aufrufen, z.B. auch keine entsprechenden aus der Standardbibliothek.

Ein absolutes Minimalbeispiel, wobei du die Returnwertauswertung eigentlich gar nicht brauchst, das solltest du alles in dem Datencontainer abhandeln.

#include <stdio.h>
#include <pthread.h>

typedef struct {
  int z;
  int liste[1000]; } Daten;

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void *fkt (void *daten)
{
  Daten *p=daten;
  pthread_mutex_lock (&mutex);
  p->z++;
  pthread_mutex_unlock (&mutex);
  return p->z;
}

int main ()
{
  Daten daten={0};
  pthread_t p1, p2;
  void *v1,*v2;

  pthread_create (&p1, NULL, fkt, &daten);
  pthread_create (&p2, NULL, fkt, &daten);

  pthread_join (p1, &v1);
  pthread_join (p2, &v2);

  printf("%d %d",(int)v1,(int)v2);

  return 0;
}

kellerfe

Danke für die Antwort, das hilft mir auf jeden Fall weiter.

Ein nicht 100% korrektes Programm funktioniert nicht.

Mit korrekt meine ich, dass das Programm am Ende macht, was es machen soll, auch wenn einen der Compiler mit Warnungen bewirft. In dem Kontext sollte Aussage eher heißen, ein nicht 100% fehlerfreies Prgramm funktioniert nicht. Aber letzten Endes ist das auch nur Haarspalterei, ich will keinen Streit.

Für deinen C-Einstieg hast du dir ein diffiziles Thema ausgesucht, und wie du durch das Verschieben vielleicht schon bemerkt hast, sind pthreads kein C-Standard, sondern POSIX.

Hab ich mir schon gedacht, war mir aber nicht sicher. Gäbe es für Threads eine Alternative, die aus dem Standard kommt?

Wutz

kellerfe schrieb:

Mit korrekt meine ich, dass das Programm am Ende macht, was es machen soll, auch wenn einen der Compiler mit Warnungen bewirft.

Der Compiler hat immer recht, ob mit Hinweisen, Warnungen oder Fehlern.
Und ob er aus den in deinem Code gefundenen Inkonformitäten Hinweise/Warnungen/Fehler macht und abbricht oder überhaupt was macht, ist nicht Sache des Standards. Es sind die von absoluten Spezialisten (d.h. Compilerbauern) gutgemeinte Hinweise an dich, die wenn du sie ignorierst, zu fragilem Verhalten deines Programmes führen.
Der Compiler führt eine statische Codeanalyse durch, was besseres kann dir gar nicht passieren, schon vorab, d.h. vor der Laufzeit deines Programmes auf Fehler hingewiesen zu werden.

kellerfe schrieb:

Gäbe es für Threads eine Alternative, die aus dem Standard kommt?

Mit dem neuen ISO C11 Standard gibt es neuerdings auch Threads, allerdings ist derzeit kein Compiler vorhanden, der dies C11-konform umsetzt.
Du könntest dir zu Lernzwecken aber z.B. Rekursion anschauen.

kellerfe

Ah, wieder was gelernt.

Mit Rekursion kenn ich mich ein wenig aus. Es sind mit Rekursion schon rekursive Algorithmen gemeint, oder? Also ein ALgorithmus, der mindestens aus Abbruchbedingung und Selbstaufruf besteht? Spontan fiele mir da der Klassiker der Fakultätberechnung ein:

int ref_fak(int i){
if(i<0)
	return -1;
elseif((i==0)||(i==1))
	return 1;
else
	return i*ref_fak(i-1);
}

Die Frage ist: wie hilft mir das im Kontext der Threaded-Programmierung?

Wutz

Natürlich nicht bei Threads, war als allgemeiner Hinweis zum C-Lernen gedacht und etwas anspruchsvoller als eine Fakultätsberechnung sollte es dann schon sein, z.B. ein rekursiver Passwortknacker, da kannst du dann auch gleich noch C-Strings üben.

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.