Crible d'Ératosthène en utilisant le parallélisme

Version imprimable

03/12/2019, 20h58
Invité

Crible d'Ératosthène en utilisant le parallélisme

Bonsoir,

Je suis actuellement en train d'essayer d'écrire un programme Java permettant de calculer la somme de tous les nombres premiers inférieurs à un N donné en utilisant le crible d'Ératosthène. Je dois impérativement utiliser le parallélisme et donc les threads pour résoudre ce problème. Plus concrètement, je dispose d'un tableau de booléens de taille N (chaque indice représente un nombre jusque N) et je dois "marquer" tous les multiples d'un nombre premier (en commençant donc par 2) afin d'éliminer tous les nombres qui ne sont pas premiers et me retrouver au final avec un tableau dans lequel il ne me reste que les nombres premiers.

Le problème est donc le suivant : je dois scinder ce tableau en sous-tableaux et faire en sorte qu'un sous-tableau = un thread (le nombre total de threads est une constante de compilation). Je dois donc affecter le marquage de chaque sous-tableau à un thread différent. Cela permet de pouvoir marquer tous les multiples d'un nombre donné en parallèle dans tous les sous-tableau pour accélérer le traitement global. Le problème est que je ne vois pas du tout comment m'y prendre pour résoudre ce problème. Je sais qu'il faut commencer par diviser le tableau en fonction du nombre de threads voulu (par exemple si le nombre de threads vaut 5 et que mon N est égal à 50, je vais certainement devoir diviser le tableau en 5 sous-tableaux de taille 10). Hormis cela, je ne vois pas comment continuer...

Une âme charitable pourrait-elle me guider vers un début de solution ?

Un grand merci par avance,
Bien à vous

Salut,

Tout d'abord au sujet du tableau de booléens, c'est un choix personnel ou c'est imposé par l'énoncé de l'exercice. Parce que tu peux directement faire un tableau qui contient que les n premiers nombre premiers (ou plusieurs tableaux de nombres premiers, que tu assembles ensuite en un seul.

Ensuite, pour ta problématique de diviser un tableau en tableaux, pour les affecter chacun à un thread, il suffit de faire simplement quelque chose comme ça (dans cet exemple, on affiche simplement les différents sous-tableau, et quelques infos) :

Code:

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
public static void main(String[] args) {
 
		int total = 43; // nombre d'éléments dans le tableau de dépar
		int nb = 5; // nombre d'éléments max dans chaque sous tableau
 
		// création d'un tableau de int aléatoire
		int[] array = IntStream.generate(ThreadLocalRandom.current()::nextInt).limit(total).toArray();
 
		// division en sous tableaux
		int count = total/nb+(total%nb==0?0:1);
 
		System.out.printf("Division du tableau de %d élément%s en %d sous-tableau%s de %d élément%s max%n", total, total<=1?"":"s", count, count<=1?"":"x", nb, nb<=1?"":"s");
		System.out.printf("Soit %d thread%s.%n", count, count<=1?"":"s");
		for(int i=0; i<count; i++) {
 
			int offset = i*nb;
			int length = Math.min(nb, array.length-offset);
 
			int[] tab = new int[length]; 
			System.arraycopy(array, offset, tab, 0, length);
 
			int index = i+1; 
			new Thread(()-> {
				System.out.printf("tableau/thread %d: offset=%d length=%d%n: %s%n", index, offset, length, Arrays.toString(tab));
			}).start();
 
		}
 
 
	}

Si tu dois limiter le nombre de threads, tu peux utiliser un FixedSizeThreadPool :

Code:

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
public static void main(String[] args) {
 
		int total = 43; // nombre d'éléments dans le tableau de dépar
		int nb = 5; // nombre d'éléments max dans chaque sous tableau
 
		int nbthreads = 5; // nombre de threads
 
		// création d'un tableau de int aléatoire
		int[] array = IntStream.generate(ThreadLocalRandom.current()::nextInt).limit(total).toArray();
 
		// division en sous tableaux
		int count = total/nb+(total%nb==0?0:1);
 
		System.out.printf("Division du tableau de %d élément%s en %d sous-tableau%s de %d élément%s max%n", total, total<=1?"":"s", count, count<=1?"":"x", nb, nb<=1?"":"s");
		ThreadFactory threadFactory = new ThreadFactory() {
 
			AtomicInteger id = new AtomicInteger();
			@Override
			public Thread newThread(Runnable r) {
				Thread thread = new Thread(r);
				thread.setName("Thread "+id.incrementAndGet());
				return thread;
			}
		};
		ExecutorService executor = Executors.newFixedThreadPool(nbthreads, threadFactory);
		for(int i=0; i<count; i++) {
 
			int offset = i*nb;
			int length = Math.min(nb, array.length-offset);
 
			int[] tab = new int[length]; 
			System.arraycopy(array, offset, tab, 0, length);
 
			int index = i+1; 
			executor.execute(()-> {
				System.out.printf("tableau %d thread %s: offset=%d length=%d%n: %s%n", index, Thread.currentThread().getName(), offset, length, Arrays.toString(tab));
			});
 
		}
 
		try {
			executor.awaitTermination(10, TimeUnit.MINUTES);
		} catch (InterruptedException e) { 
			e.printStackTrace();
		}
		executor.shutdown();
 
}

Si tu ne peux utiliser un ExecutorService (contrainte de l'exercice), tu peux utiliser une double boucle par exemple et utiliser la méthode join() de Thread pour attendre qu'un thread soit terminé. A chaque sous boucle tu lances n threads, stockés dans un tableau et tu attends que les n soit terminés pour faire l'itération suivante de la boucle principal. Ou utiliser CountDawnLatch. Ou simuler un pool avec un tableau.

Regarde aussi éventuellement du côté des "parallelStream".

04/12/2019, 11h30
Invité

Salut,

Merci beaucoup pour ta réponse. C'est super sympa de prendre le temps de m'aider. En fait, je pense que je me suis mal exprimé. Mon problème n'est pas tellement un problème de langage mais plutôt un problème d'algorithmique. Je sais écrire l'algorithme du crible d’Ératosthène en version séquentielle mais je ne parviens pas à le traduire en version parallèle pour tirer profit des threads dans le processus de marquage des multiples dans les sous-tableaux. Cela fait plusieurs jours que je me renseigne et que je réfléchis mais je bloque toujours... Je sais que je vais devoir utiliser les notions de wait(), join() etc pour bien gérer les threads entre eux mais je ne vois pas plus pour le moment.

Par ailleurs, j'ai passé ma soirée hier (4 heures au total) à essayer de trouver des explications sur un éventuel algorithme parallèle pour ce crible d’Ératosthène mais je n'ai rien trouvé. J'ai trouvé une solution permettant d'affecter un thread au marquage des multiples d'un nombre premier (un thread = marquage des multiples d'un seul premier dans le tableau) mais je ne trouve pas de moyen de faire en sorte qu'un thread s'occupe de marquer les multiples d'un premier uniquement dans son sous-tableau (donc un thread par sous-tableau).

Concernant le tableau de booléen, c'est effectivement imposé par l'énoncé mais c'est également logique car il sera indicé de 0 à N et c'est cet indice qui correspond au nombre en question, donc ça permet de stocker uniquement un booléen indiquant s'il est premier ou non au lieu de stocker l'entier lui-même (ce qui allégera l'utilisation de la mémoire de manière non négligeable pour des N très grands du type 1 000 000).

Merci à toi
04/12/2019, 11h49
joel.drigo
Citation:

Envoyé par Sachifus

Merci beaucoup pour ta réponse. C'est super sympa de prendre le temps de m'aider. En fait, je pense que je me suis mal exprimé. Mon problème n'est pas tellement un problème de langage mais plutôt un problème d'algorithmique. Je sais écrire l'algorithme du crible d’Ératosthène en version séquentielle mais je ne parviens pas à le traduire en version parallèle pour tirer profit des threads dans le processus de marquage des multiples dans les sous-tableaux. Cela fait plusieurs jours que je me renseigne et que je réfléchis mais je bloque toujours... Je sais que je vais devoir utiliser les notions de wait(), join() etc pour bien gérer les threads entre eux mais je ne vois pas plus pour le moment.

Par ailleurs, j'ai passé ma soirée hier (4 heures au total) à essayer de trouver des explications sur un éventuel algorithme parallèle pour ce crible d’Ératosthène mais je n'ai rien trouvé.

Oui désolé je n'avais pas fait attention que tu cherchais à limiter le nombre de threads. J'ai compléter ma réponse depuis. A noter que je ma réponse ne concerne pas le crible d’Ératosthène mais juste comment répartir un tableau en n tableaux traités chacun par un thread (parmi x threads, x égal n ou pas).

Citation:

Envoyé par Sachifus

J'ai trouvé une solution permettant d'affecter un thread au marquage des multiples d'un nombre premier (un thread = marquage des multiples d'un seul premier dans le tableau) mais je ne trouve pas de moyen de faire en sorte qu'un thread s'occupe de marquer les multiples d'un premier uniquement dans son sous-tableau (donc un thread par sous-tableau).

Si tu es capable d'écrire un algorithme qui traite ton problème sur un tableau de n éléments quelconques, tu sais le faire dans un thread. Le problème c'est juste de savoir comment reconstituer un résultat unique qui rassemble le résultat de chaque thread et ça, c'est juste de la "concaténation". Donc de la création et de la copie de tableau (à défaut de passer par une ArrayList qui fait ça justement), et de la synchronisation de processus parallèle. Pour faire ça proprement, je ferais personnellement un buffer de type producteur/consomateur (ça fait un thread de plus pour consommer le contenu du buffer, mais ce thread peut être le thread principal).

Oui désolé je n'avais pas fait attention que tu cherchais à limiter le nombre de threads. J'ai compléter ma réponse depuis.

Citation:

Envoyé par Sachifus

c'est effectivement imposé par l'énoncé mais c'est également logique car il sera indicé de 0 à N et c'est cet indice qui correspond au nombre en question, donc ça permet de stocker uniquement un booléen indiquant s'il est premier ou non au lieu de stocker l'entier lui-même (ce qui allégera l'utilisation de la mémoire de manière non négligeable pour des N très grands du type 1 000 000).

Mmm, sans faire les calculs et une démonstration, je dirais intuitivement que ça doit être vrai pour les premiers nombres premiers, mais que ça devient de moins en moins vrai... supposons qu'on soit en train d'évaluer 2 entiers N et M tels que M-N = 10⁶. Il te faut au moins un tableau de 10⁶+1 booléens (de taille donc (10⁶)* 1 +12 octets pour les stocker (avec 2 valeurs à true et le reste à false) ou un tableau de 2 int, soit un taille de 4*2 + 12 octets. Me semble quand même que le tableau de int est plus petit que le tableau de booléen.
Avec une solution parallélisée, on a deux cas :
1. créer un nouveau tableau à chaque fois qu'on parcourt un interval de int pour déterminer lesquels sont premiers. Avec des tableaux de booléens on va en créer beaucoup plus que de tableaux de int. Donc une charge beaucoup plus importante pour le GC.
2. réutiliser les mêmes tableaux. dans le cas de booléen, on va produire beaucoup plus de tableaux à parcourir qui ne contiendront que des false, alors qu'avec des tableaux de int, tout parcours sera utile (parce qu'on aura que des nombres premiers dans le tableau). Si la charge en mémoire est moindre, elle se déplace simplement vers le cpu. Au lieu de consommer beaucoup d'espace pour des trucs inutiles, on va juste passer beaucoup de temps à faire des choses inutiles.
Reste à détermine à partir de quel N il est plus intéressant d'utiliser des int[] que des boolean[]...
06/12/2019, 15h03
Invité
Salut,

Merci beaucoup pour ton aide. Je voulais faire en sorte de pouvoir simplement passer les bornes inférieures et supérieures de la partie du tableau à traiter dans le constructeur de chacun des threads. Par ailleurs, je me dit qu'il ne devrait pas y avoir de problème d'accès concurrentiel aux données du tableau car les threads travailleront à priori toujours sur des zones distinctes de ce dernier. Je pense que ça enlève déjà de la difficulté. Malgré tout, j'en étais resté à cette conclusion sans réussir à aller plus loin dans l'implémentation.

Je ne sais pas s'il est indispensable d'utiliser un système de producteur / consommateur ou s'il est possible de s'en affranchir...

Bien à toi
Citation:
Envoyé par joel.drigo

Oui désolé je n'avais pas fait attention que tu cherchais à limiter le nombre de threads. J'ai compléter ma réponse depuis. A noter que je ma réponse ne concerne pas le crible d’Ératosthène mais juste comment répartir un tableau en n tableaux traités chacun par un thread (parmi x threads, x égal n ou pas).

Si tu es capable d'écrire un algorithme qui traite ton problème sur un tableau de n éléments quelconques, tu sais le faire dans un thread. Le problème c'est juste de savoir comment reconstituer un résultat unique qui rassemble le résultat de chaque thread et ça, c'est juste de la "concaténation". Donc de la création et de la copie de tableau (à défaut de passer par une ArrayList qui fait ça justement), et de la synchronisation de processus parallèle. Pour faire ça proprement, je ferais personnellement un buffer de type producteur/consomateur (ça fait un thread de plus pour consommer le contenu du buffer, mais ce thread peut être le thread principal).

Oui désolé je n'avais pas fait attention que tu cherchais à limiter le nombre de threads. J'ai compléter ma réponse depuis.

Mmm, sans faire les calculs et une démonstration, je dirais intuitivement que ça doit être vrai pour les premiers nombres premiers, mais que ça devient de moins en moins vrai... supposons qu'on soit en train d'évaluer 2 entiers N et M tels que M-N = 10⁶. Il te faut au moins un tableau de 10⁶+1 booléens (de taille donc (10⁶)* 1 +12 octets pour les stocker (avec 2 valeurs à true et le reste à false) ou un tableau de 2 int, soit un taille de 4*2 + 12 octets. Me semble quand même que le tableau de int est plus petit que le tableau de booléen.
Avec une solution parallélisée, on a deux cas :

créer un nouveau tableau à chaque fois qu'on parcourt un interval de int pour déterminer lesquels sont premiers. Avec des tableaux de booléens on va en créer beaucoup plus que de tableaux de int. Donc une charge beaucoup plus importante pour le GC.
réutiliser les mêmes tableaux. dans le cas de booléen, on va produire beaucoup plus de tableaux à parcourir qui ne contiendront que des false, alors qu'avec des tableaux de int, tout parcours sera utile (parce qu'on aura que des nombres premiers dans le tableau). Si la charge en mémoire est moindre, elle se déplace simplement vers le cpu. Au lieu de consommer beaucoup d'espace pour des trucs inutiles, on va juste passer beaucoup de temps à faire des choses inutiles.

Reste à détermine à partir de quel N il est plus intéressant d'utiliser des int[] que des boolean[]...