Zrównoleglenie, przykład minimalny

Mam rekurencyjnego producenta - funkcja rt(),
któremu czasem coś wyjdzie i chciałby dodać to do wyników (wynik[], ile)
ale mam też 4 rdzenie i nawet 8 wątków(?) i chciałbym to wykorzystać.
Windows 7/ Code::Blocks/ MinGW/ GCC

Prosty, przykładowy programik wykonujący się w czasie 0.00 sekundy
ale mający chyba wszystko co bym chciał.
Prosiłbym o zmodyfikowanie w wersji jedno proceso/kompute-rowej
(kiedyś zapytam o wersję wielo...)

#include <cstdio>

int isp(int n){// naiwne testowanie "pierwszości"
	if( n<2 ) return 0;
	if( n%2==0 ) return n==2; if( n%3==0 ) return n==3;
	for(int d=5; d*d<=n; d+=6 )
		if( (n%d==0) || (n%(d+2)==0) )
			return 0;
	return 1;}

int wynik[83]; int ile=0; // tu zbieram wyniki

void dodaj(int n){ // tu może być krytycznie
	//printf("%3d %9d\n", ile+1, n);
	if( n>0 )
		wynik[ile++] = n;}

void rt(int n){ // rekurencyjny producent
	dodaj(n);
	n *= 10;
	for(int i=1; i<10; i++ )
		if( isp( n + i ) ) 
			rt( n + i ); }
int main(){
	rt(0);
	printf("\n%d", ile);
	return 0;}

postawię piwo, czy dwa.

Grot czy VIP?

W OpenMP raczej wygląda na banalne do zrównoleglenia. Coś tak skrobne po pracy.

Jeżeli dysponujesz kompilatorem z obsługą OpenMP 3.0 (może być MinGW)

 
#include <cstdio>
#include <omp.h>

int isp(int n){// naiwne testowanie "pierwszosci"
    //for(volatile int i = 0; i < 0xFFFFFF; ++i);
    if( n<2 ) return 0;
	if( n%2==0 ) return n==2; if( n%3==0 ) return n==3;
	for(int d=5; d*d<=n; d+=6 )
		if( (n%d==0) || (n%(d+2)==0) )
			return 0;
	return 1;
}

int wynik[83]; int ile=0; // tu zbieram wyniki

void dodaj(int n){ // tu moze byc krytycznie
	//printf("%3d %9d\n", ile+1, n);

	if( n>0 ) {
	    int idx = __sync_fetch_and_add(&ile, 1);
		wynik[idx] = n;
	}
}

void rt(int n){ // rekurencyjny producent
	dodaj(n);
	n *= 10;

	for(int i=1; i<10; i++ ) {
        #pragma omp task untied firstprivate(i, n)
        {
            //printf("Num [%d] Thread [%d]\n", n+i, omp_get_thread_num());
            if( isp( n + i ) )
                rt( n + i );
        }
	}
}
int main(){
    #pragma omp parallel num_threads(8)
    {
        #pragma omp single
        rt(0);
        #pragma omp taskwait
    }

    for(int i = 0; i < ile; ++i)
    {
        printf("%d\n", wynik[i]);
    }


	return 0;
}

Jeżeli dysponujesz kompilatorem z obsługą OpenMP3.1 to możesz dodatkowo wywalić __sync_fetch_and_add i przerobić na #pragma omp atomic capture.

dziękuję, dziś się zanietrzeźwię, jutro będę zajęty, a na weekend mam chyba zabawę. Pozdrawiam, Xitami.
prosto to wygląda, ale zawsze miłe złego początki.