Faktorisierung mit MPI



  • Hi

    Ich habe ein einfaches Programm geschrieben, welches das Message Passing Interface benutzt. Leider erhalte ich immer irgendwelche Debug Assertion.

    #include "mpi.h"
    #include "windows.h"
    #include "assert.h"
    #include <iostream>
    #include <vector>
    #include <cmath>
    
    using namespace std;
    
    typedef unsigned long long ullong;
    
    // Zahl welche es zu faktorisieren gilt
    ullong factnum = 12222222222222; 
    
    // MPI Tags, Faktor gefunden
    const int tagfactfound = 1;
    
    // Auftragverteilung
    const int tagbeginjob = 2;
    
    // Auftrag beendet
    const int tagendjob = 3;
    
    int myid;
    
    // Berechnet die Quadratwurzel eine Variable des Typs unsigned long long
    ullong ulsqrt(ullong num){
    
    	/*__asm {
    		// Double word move (64bit)
    		movq mm1,num 
    		// Konvertiere two double int (64bit) to double pr. float (128bit)
    		cvtpi2pd xmm0,mm1
    		// Quadratwurzel ziehen
    		sqrtsd xmm0,xmm0
    		// Konvertiere double pr. float (128bit) to two double int (64bit)
    		cvtpd2pi eax,xmm0
    	}*/
    
    	return sqrt((long double)num);
    }
    
    // Funktion welche anhand des Sieb des Eratosthenes überprüft ob eine Zahl 
    // Primfaktoren besitzt
    bool isprime(ullong num){
    	assert (num % 2 == 1);
    
    	// Grösster Teiler
    	ullong max = ulsqrt(num);
    
    	// Boolsches Array auf dem Heap allozieren
    	bool * eratos = new bool[max];
    
    	// Primzahlenspeicher
    	ullong * prim = new ullong[max/2];
    	ullong count = 0;
    
    	// Primzahlen besimmten
    	for (ullong i=2; i <= max; ++i){
    
    		// Zahl ist prim
    		if (eratos[i]){
    			prim[i] = i;
    			count++;
    		}
    
    		// Alle Vielfachen als nicht prim markieren
    		ullong j = i*i;
    		while (j <= max){
    			eratos[j] = false;
    			j += j;
    		}
    	}
    
    	// Zahl anhand der vorher berechneten Primzahlen überprüfen
    	for (ullong i=0; i < count; ++i){
    		if(num % prim[i] == 0)return false;
    	}
    
    	return true;
    }
    
    // Diese Funktion überprüft ob die Zahl num eine Primzahl ist, falls nicht
    // liefert sie die nächstmögliche Primzahl
    ullong getnextprime(ullong num){
    	if (num == 0 || num == 1) return 2;
    	// Nächste Primzahl berechnen wenn num nicht prim ist
    	while(!isprime(num)){
    		num += 2;
    	}
    	return num;
    }
    
    int main(int argc, char* argv[]) {
    
    	// Message Passing Interface initalisieren
    	MPI::Init(argc, argv);
    
    	// Anzahl der Nodes ermitteln
    	int numprocs = MPI::COMM_WORLD.Get_size();
    
    	if (numprocs < 2){
    		printf("Need than one process for calculation\n");	
    		return 0;
    	}
    
    	// Welcher Node bin ich?
    	myid = MPI::COMM_WORLD.Get_rank();
    
    	MPI::Status stat;
    
    	ullong jobmax = ulsqrt(factnum);
    	ullong jobsize = ceil((long double)(jobmax)/(long double)(numprocs-1));
    
    	ullong jobcounter = 0;
    
    	std::vector<ullong> fact;
    
    	// Managernode
    	if (myid == 0) {
    		printf("Beginning of job distribution for %d workers with candidate %lld\n",numprocs,factnum);
    
    		// Ausgabe sofort an die Pipe senden
    		fflush(stdout);
    
    		// Jedem Workernode einen Auftrag übergeben
    		for (int i = 1; i < numprocs; ++i){
    			printf("Distribut job (%lld ",jobcounter);
    			jobcounter += jobsize;
    			printf("to %lld) to %d\n",jobcounter,i);
    
    			fflush(stdout);
    
    			// Jeweiligen Auftrag an den jeweiligen Arbeit schicken
    			MPI::COMM_WORLD.Send(&jobcounter, sizeof(ullong), MPI::UNSIGNED_LONG_LONG,i,tagbeginjob);
    		}
    
    		do {
    
    			while (MPI::COMM_WORLD.Iprobe(MPI::ANY_SOURCE,tagendjob,stat))
    			{
    				int b;
    				// Leer Benachrichtung aus dem Speicher entferne
    				MPI::COMM_WORLD.Recv(&b,sizeof(b),MPI::INT,MPI::ANY_SOURCE,tagendjob,stat);
    
    				// Ein Arbeiter wurde fertig
    				--numprocs;
    
    			}
    
    			while (MPI::COMM_WORLD.Iprobe(MPI::ANY_SOURCE,tagfactfound,stat))
    			{
    
    				// Ein Arbeiter hat einen Faktor gefunden
    				ullong lbuf;
    
    				// Faktor aus Nachrichtenspeicher holen
    				MPI::COMM_WORLD.Recv(&lbuf,sizeof(lbuf),MPI::UNSIGNED_LONG_LONG,MPI::ANY_SOURCE,tagfactfound,stat);
    
    				// Zahl minimieren
    				factnum /= lbuf;
    
    				// Dem Faktorenvektor hinzufügen
    				fact.push_back(lbuf);
    
    			}
    
    		} while (numprocs != 1);
    
    		if (factnum != 1) fact.push_back(factnum);
    
    		// Alle Arbeiter haben ihren Auftrag erledigt
    		printf("Factors: ");
    		std::copy(fact.begin(),fact.end(),std::ostream_iterator<ullong>(std::cout," "));
    		printf("\n");
    
    	// Workernodes
    	} else {
    
    		ullong fbuf;
    
    		// Auftrag empfangen
    		MPI::COMM_WORLD.Recv(&fbuf,sizeof(fbuf),MPI::UNSIGNED_LONG_LONG,MPI::ANY_SOURCE,tagbeginjob);
    
    		// Untere Grenze bestimmen;
    		ullong minsize = fbuf-jobsize;
    
    		// Alle ungeraden Zahlen werden überprüft
    		if (minsize % 2 == 0) ++minsize;
    		ullong maxsize = fbuf;
    
    		printf("Worker %d got Job %lld to %lld\n",myid,minsize,fbuf);
    		fflush(stdout);
    
    		ullong i = getnextprime(minsize);
    		ullong g;
    
    		// Auftrag bearbeiten
    		while(i < maxsize){
    
    			// Hat ein andere Arbeiter einen Faktor gefunden?
    			if (MPI::COMM_WORLD.Iprobe(MPI::ANY_SOURCE,tagfactfound,stat)){
    				ullong lbuf;
    				// Faktor auslesen
    				MPI::COMM_WORLD.Recv(&lbuf,sizeof(lbuf),MPI::UNSIGNED_LONG_LONG,MPI::ANY_SOURCE,tagfactfound);
    
    				// Zahl minimieren
    				factnum /= lbuf;
    			}
    			g = 1;
    
    			// Wir haben einen Faktor gefunden
    			if (factnum % i == 0){
    				ullong lbuf = i;
    
    				// Zahl minimieren
    				factnum = factnum / lbuf;
    
    				for (int l = 0; l < MPI::COMM_WORLD.Get_size(); ++l)
    				{
    					if (l != myid){
    
    						// Den anderen Arbeitern und dem Manager mitteilen
    						MPI::COMM_WORLD.Send(&lbuf, sizeof(lbuf),MPI::UNSIGNED_LONG_LONG,l,tagfactfound);
    					}
    				}
    			} else {
    
    				// Nächste Primzahl generieren
    				if (i == 2) i = 3;
    
    				else i = getnextprime(i+2);
    				fflush(stdout);
    			}
    		}
    
    		// Auftrag wurde erledigt
    		int b = 1;
    		MPI::COMM_WORLD.Send(&b,sizeof(b),MPI::INT,0,tagendjob);
    	}
    
    	// Message Passing Interface Umgebung beenden
    	MPI::Finalize();
    	return 0;
    }
    

    Die Fehler passieren immer bei einem Aufruf von Recv. Ich habe schon diverse MPI Dokumente studiert, jedoch nichts gefunden was ich falsch gemacht habe. Das Programm funktionierte mit unsigned long.

    MfG Joe


Log in to reply