Optimisation de code

**mrjay42** · 19/10/2012, 13h14

Bonjour à tous,

Le problème
Je viens de reprendre mes études, et j'ai un prof' très "sympa" en "Optimisation de code".
Nous n'avons fait que des cours "généraux" et il vient de nous balancer comme ça, sans prévenir un code en langage C à "paralléliser" en utilisant openMP.

Je ne cherche pas vraiment une solution "clé en main", mais simplement des pistes sur lesquelles je pourrais travailler pour améliorer ce code...Néanmoins si vous pouvez illustrer vos réponses avec des petits exemples précis, je suis quand même preneur .

A quoi sert ce code ?
Il effectue un "crible d'Eratosthène" (ou "Sieve of Eratosthene" en anglais

)
En gros, c'est un programme qui cherche et compte les nombres premiers entre 2 et N (N étant le nombre entier que l'on veut

)

Le code à paralléliser
Ci-dessous vous trouverez le code donné par le prof...que j'ai à peine modifier afin d'y intégrer une mesure du temps (basé sur time.h), j'ai aussi ajouté l'include "omp.h".

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdlib.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <omp.h>
 
int main(int argc, char **argv)
{
	int top_value = 99999999;
	int count     = 0;
	int *array    = calloc( top_value + 1, sizeof(int));
	int i, prime, multiple;
 
	printf("******************\n");
	printf("Program as started \n");
	printf("******************\n");
	time_t start = clock();  /* Start measuring time */
 
 
	/* mark each int as potentially prime                                    */
	for (i=2; i <= top_value; ++i)
	{
		array[i] = 1;
	}
 
 
	/* for each starting prime, mark its every multiple as non-prime         */
	//#pragma omp parallel for
	//#pragma omp parallel for num_threads(4) ordered
	//#pragma omp parallel for
 
	for (prime = 2; prime <= top_value; ++prime)
	{
		if (array[prime])
		{	
 
 
			//#pragma omp parallel for num_threads(24)
			//#pragma omp parallel for schedule(static, 2)
			//#pragma omp parallel for num_threads(2) schedule(dynamic, top_value/24)
			for (multiple = 2*prime; multiple <= top_value; multiple += prime)
			{
				if (array[multiple])
				{
					array[multiple] = 0;
					//--count;
				}
			}
		}
	}
 
 
 
	time_t stop = clock();    /* Stop timer */
 
	double total_time = (double)(stop-start)/ CLOCKS_PER_SEC;
	printf("\nClock time for Sieve operation %6.3f s total\n", total_time);	
 
	/* Now that we have marked all multiples of primes as non-prime, print   */
	/* the remaining numbers that fell through the sieve, and are thus prime */
	for (i=2; i <= top_value; ++i)
	{
		if (array[i])
		{
			//printf("%d ", i);
			count++;
		}
	}
 
	printf("\n\n %d primes up to %d found.\n", count, top_value);
	total_time = (double)(stop-start)/ CLOCKS_PER_SEC;
	printf("\nClock time for Sieve operation %6.3f s total\n", total_time);
 
	exit(0);
}

Compilation
Voici la ligne de commande que j'utilise pour compiler ce petit programme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

gcc -o sieve -O3 -Wall -fopenmp sieve.c -lm -ffast-math

Ce que j'ai fait jusqu'à présent
J'ai essayé d'ajouter des directives openMP dans le programme...notamment un petit "#pragma omp parallel for" mais ça n'améliore pas trop les perf et surtout les résultats sont totalement faussés

Ça doit être lié aux variables partagées/privées...enfin je pense...

Ma question
Si vous voyez comment utiliser correctement openMP dans ce programme je suis preneur
Notamment comment bien géré les variables partagées/privées !

Je vous remercie par avance pour votre aide