#pragma omp for

[sonyxp]

Έχω φτιάξει ένα πρόγραμμα που βρίσκει όλους τους πρώτους αριθμούς μέχρι όσο δώσω

 

Όπως αντιλαμβάνεστε, η διαδικασία αυτή αργεί...

 

Ένας τρόπος είναι να σπάσουμε τον αριθμό σε μικρότερα κομμάτια ώστε να τρέξουμε παράλληλα Threads για να επιταχύνουμε την δουλειά μας.

        #pragma omp parallel num_threads(10)
	{
		#pragma omp for
		for(unsigned int i=0; i < MAX_NUM; i++)
                {
	            if (isPrime(i))
                    {
                         Write(i);
                    
                         if ((clock() - temp) >= tempDelay)
                         {
                            system("cls");
                            printf("[%d%%] %d / %d till now has elapsed (%d) seconds\n", i*100 / MAX_NUM, i, MAX_NUM, abs(clock()/1000));
                            temp += tempDelay;
                         }
                    }
                }//for
	 }

Δεν βλέπω καμιά διαφορά στον χρόνο όμως!

[imitheos]

Έχεις ενεργοποιημένα τα warnings του compiler σου ? Αν όχι, κάνε το. Επίσης διάβασες αν ο compiler σου υποστηρίζει OpenMP και τι χρειάζεται για να ενεργοποιηθεί ?

 

Για παράδειγμα σε gcc έχουμε.

 

% cc -Wall -std=c99 -o tmp tmp.c  
tmp.c: In function ‘main’:
tmp.c:10:0: προειδοποίηση: ignoring #pragma omp parallel [-Wunknown-pragmas]
 #pragma omp parallel num_threads(3)
 ^
tmp.c:12:0: προειδοποίηση: ignoring #pragma omp for [-Wunknown-pragmas]
   #pragma omp for
 ^
% ldd tmp 
   linux-vdso.so.1
   libc.so.6
   /lib64/ld-linux-x86-64.so.2
% cc -Wall -std=c99 -fopenmp -o tmp tmp.c 
% ldd tmp                               
   linux-vdso.so.1
   libgomp.so.1
   libpthread.so.0
   libc.so.6
   /lib64/ld-linux-x86-64.so.2

Όταν βάζουμε την fopenmp δεν παίρνουμε κανένα μήνυμα λάθους και το εκτελέσιμο γίνεται link με την gomp και την pthread ώστε να υποστηρίζει νήματα. Χωρίς την fopenmp ο gcc αγνοεί τα pragma και δεν κάνει τίποτα.

 

Οι χρόνοι εκτέλεσης του κώδικά σου για να βρει πρώτους από 0 μέχρι 900000 είναι 55 δευτερόλεπτα χωρίς νήματα και 37 δευτερόλεπτα με 3 νήματα.

 

Έχε υπόψην ότι μπορεί να έχεις προβλήματα με την printf και system. Ο κώδικας της isPrime ποιος είναι ? Μήπως να βελτιστοποιήσεις εκείνον πρώτα πριν πας σε νήματα ?

[sonyxp]

με visual studio δουλεύω, θα το ψάξω το θέμα με τα warnings...

 

Κάτι που παρατήρησα και δεν μου άρεσε είναι η τεράστια διαφορά χρόνου όταν το τρέχω σε Debug και σε Release

 

σε Debug από 0...10κκ κάνει 120~ sec σε μένα (laptop 2 cores cpu)

όταν το κάνω Release και το τρέξω κάνει ~10 sec

 

πολύ κουφό έτσι? έχω χαλαστεί άσχημα γιατί αν κάποιος θέλει να ασχοληθεί με στατιστικά και χρόνους, τότε θα πάρει εντελώς λάθος αποτελέσματα (έλεος!)

 

Κώδικας

http://pastebin.com/JEEu6b2G

 

ΥΓ: ξέρω ότι αυτό το κομμάτι καθυστερεί τον κώδικα...

				if ((clock() - temp) >= tempDelay)
				{
					system("cls");
					printf("[%d%%] %d / %d till now has elapsed (%d) seconds\n", i*100 / MAX_NUM, i, MAX_NUM, abs(clock()/1000));
					temp += tempDelay;
				}

όπως και η εγγραφή σε αρχείο

 

Θα μου πεις, γιατί τα βγάζεις σε αρχείο, που θα σου χρειαστούν; ... έλα μου ντε!

[imitheos]

με visual studio δουλεύω, θα το ψάξω το θέμα με τα warnings...

 

Κάτι που παρατήρησα και δεν μου άρεσε είναι η τεράστια διαφορά χρόνου όταν το τρέχω σε Debug και σε Release

 

σε Debug από 0...10κκ κάνει 120~ sec σε μένα (laptop 2 cores cpu)

όταν το κάνω Release και το τρέξω κάνει ~10 sec

Ο optimizer μπορεί να αλλάξει εντελώς τον κώδικα ή να αφαιρέσει κώδικα που δεν χρειάζεται οπότε δεν μπορείς να κάνεις debug γραμμή-γραμμή. Για αυτό το λόγο επιλέγεται συνήθως να μην γίνεται optimization σε debug builds. Σε release μπαίνει το optimization το οποίο κάνει τον κώδικας πολύ πιο γρήγορο. Αυτό γίνεται σε όλους τους κώδικες. Με linux + gcc το πρόγραμμά σου θέλει 33s με -Ο0, 9s -O2 και βαράει segmentation fault με O3

 

 

ΥΓ: ξέρω ότι αυτό το κομμάτι καθυστερεί τον κώδικα...

				if ((clock() - temp) >= tempDelay)
				{
					system("cls");
					printf("[%d%%] %d / %d till now has elapsed (%d) seconds\n", i*100 / MAX_NUM, i, MAX_NUM, abs(clock()/1000));
					temp += tempDelay;
				}

όπως και η εγγραφή σε αρχείο

 

Θα μου πεις, γιατί τα βγάζεις σε αρχείο, που θα σου χρειαστούν; ... έλα μου ντε!

 

Το I/O είναι πάντα η πιο αργή διαδικασία και οι συναρτήσεις χρόνου είναι σχετικά αργές. Εν προκειμένω δεν κάνουν μεγάλη διαφορά (αφαιρώντας τα printf και το αρχείο κέρδισα μόλις 1s και στα δύο builds) αλλά όσο μπορείς να τα περιορίσεις καλό είναι. Μια και χρησιμοποίησα linux, ο κώδικας που έτρεξα δεν είχε τα system(cls) οπότε δεν ξέρω τι αντίκτυπο έχουν. Δοκίμασε χωρίς τα system(cls) και δες αν κερδίζεις σημαντικά σε χρόνο.

 

Πολλές φορές σε κώδικα βλέπουμε "system(pause)" και λέμε να μπει getchar(). Ένας σημαντικός λόγος είναι ότι η getchar είναι πρότυπη βιβλιοθήκη και παίζει παντού σε αντίθεση με μόνο σε windows.

 

Υπάρχει όμως και ένας άλλος λόγος που αντενδείκνυται η χρήση της system. Όταν τρέξεις την system θα σταματήσει προσωρινά το πρόγραμμά σου και θα φορτωθεί στη μνήμη και θα τρέξει ένα κέλυφος (ό,τι τρέχουν τα windows εν πάση περιπτώσει) το οποίο θα ψάξει στο path να βρει την εντολή που ζητήθηκε, θα φορτωθεί στη μνήμη, θα τρέξει η εντολή και μετά θα συνεχίσει το πρόγραμμα (ίσως να γίνει και ελευθέρωση της μνήμης). Σύγκρινε όλο αυτό σε σχέση με μια απλή εκτέλεση της getchar (ή με μια printf που ουσιαστικά είναι η cls).

 

Αυτό το λόγο δεν τον αναφέρουμε γιατί όταν ένας κώδικας τρέχει μια φορά στο τέλος του system(pause) δεν έγινε και τίποτα αλλά στη δική σου περίπτωση που καλείται τόσο συχνά ίσως να έχει σημαντική διαφορά (ίσως και όχι).

 

Αν δεις ότι υπάρχει σημαντική διαφορά χωρίς τα cls μπορείς να χρησιμοποιήσεις κάποιο άλλο τρόπο για να καθαρίσεις την οθόνη. Το αρχαίο conio.h είχε την clrscr αλλά εφόσον εισάγεις το windows.h σίγουρα το winapi θα δίνει κάποια συνάρτηση για αυτή τη δουλειά (ή μπορείς να κάνεις το μπακάλικο printf("\n\n\nκτλ"))

[albNik]

Πάντως ο Ερατοσθένης (χωρις threads) παράγει όλους τους πρώτους μεχρι 100.000.000 σε 3 sec στο pc μου.

        const int P=100000000;
	int primes[P]; 
	primes[0]=primes[1]=0;
	for(int i=2;i<P;i++)
	   primes[i]=1;

	for(int i=2; i*i<=P; i++)
          if(primes[i]) 
	     for(int j=i*i; j<P; j+=i) 
		primes[j] = 0;

[imitheos]

Ναι εννοείται. Για αυτό του είπα να κοιτάξει πρώτα τον αλγόριθμό του.

 

Στο project euler έχει κάμποσα προβλήματα με πρώτους αριθμούς. Στο πρόβλημα 10 ζητάει το άθροισμα όλων των πρώτων αριθμών μέχρι 2,000,000. Αρχικά το είχα κάνει με το κλασικό "ψάχνε αν διαιρείται με κάποοιον αριθμό" περίπου σαν αυτόν που έκανε ο OP και μου είχε πάρει 3 λεπτά και 28 δευτερόλεπτα για να τους βρει. Με το κόσκινο πήρε 0.2 δευτερόλεπτα δηλαδή 1000 φορές κάτω :)

[sonyxp]

εξαρτάται από πολλά τώρα αυτό...

 

τι να κάνω με έναν Intel P6100 2.1GHz  - 2Cores...

 

tested on i5, it took about 7(6900ms) seconds from 13-14 (Intel p6100)

 

**** Μέχρι το 10kk αυτή τη φορά

ΥΓ: το openmp ήταν off, το ενεργοποίησα αλλά τώρα έχω θέματα στον κώδικα, δεν το δέχεται έτσι (δεν περνάει καν απο compile)