Disons qu'une liste FIFO de workitems c'est intéressant dans le sens ou on peu gérer de la priorité, paramétrer le nombre de workerthreads pour savoir exactement quel nombre donne les meilleurs résultats. Et c'est très maîtrisable au niveau des context switch, en plus ça prône la réutilisation des threads.

Pour info c'est le principe utilisé dans les serveurs d'applications.

Sinon godrik, t'as surement raison ça doit être des threads utilisateurs, quelqu'un m'a confirmé pour les 1mo RAM nécessaires.

En fonction des temps de calcul des elements, il peut etre preferable de distribue la fifo pour eviter les contentions sur la FIFO. Du coup tu n'es plus forcement fifo, amis tu peux arriver a etre suffisament fifo pour que cela ne pose pas de probleme

Une solution s'il s'agit de test d'algo (je n'ai pas lu avec attention tout le thread donc je suis peu être à coté de ce que tu fais) c'est d'utiliser OCaml qui, en bytecode, n'utilise que des thread utilisateur avec très peu de coûts associés à chaques thread (à peu de chose près, rien).

C'est quoi ces différents types de Thread dont vous parlez? Moi j'utilise simplement des classes qui étendent la classe "Thread".

Pour faire mes mutex, je crée un verrou:
private final ReentrantLock lock = new ReentrantLock();

Et j'encadre la section critique avec:
lock.lock(); et lock.unlock();

De toute manière, je suis obligé d'utiliser Java pour ce projet et de créer 1 thread par agent.

Mais je ne sais pas si l'utilisation de thread utilisateur bénéficie réellement des multi core ou multi processeurs.
Je suis mal renseigné à ce sujet.

1. godrik Voir le profil de godrik
2. Posté le 6 juillet 2009 à 21:17:58 Avertir un modérateur
3. En fonction des temps de calcul des elements, il peut etre preferable de distribue la fifo pour eviter les contentions sur la FIFO. Du coup tu n'es plus forcement fifo, amis tu peux arriver a etre suffisament fifo pour que cela ne pose pas de probleme

Mais ce serait le cas seulement si les locks lors de l'accès à la file surpassent le temps d'exécution du workitem, c'est ça que tu veux dire?
A ce que j'en sais, acquérir un lock simple (non réentrant) coûte quelque chose comme 20 nanos.

1. Isukthar Voir le profil de Isukthar
2. Posté le 6 juillet 2009 à 21:46:50 Avertir un modérateur
3. De toute manière, je suis obligé d'utiliser Java pour ce projet et de créer 1 thread par agent.

Mais pourquoi pas un pool de thread avec un file? Tu as ça dans le package "concurrent". Tu crées des workitems contenant le nécessaire de calcul pour déplacer l'agent, et tu les fous dans la file, les threads la consomme automatiquement.

Commencer à créer 1000 threads, c'est insensé sans des machines de brutes faites pour ça.

J'utilise la classe ThreadPoolExecutor, donc c'est sûrement lui qui s'occupe de tout ça. Perso, je ne connais pas trop les mécanismes de la JVM pour ce qui est des threads.

"C'est quoi ces différents types de Thread dont vous parlez? Moi j'utilise simplement des classes qui étendent la classe "Thread"."

Basiquement il y a deux types de threads dans la vie. Ceux qui sont gere par le noyau et ceux qui sont gere par l'utilisateur. Les threads noyaux c'est ceux qui sont cree par des apppels a clone(2) sous linux (ce qui est appelle par fork et pthread_create). Ca cree un nouveau processus dans le systeme d'exploitation qui va etre schedule comme un processus normal (Au niveau du systeme la difference entre un thread et un processus est assez faible). Ce sont ces threads la qui sont mappe par le noyau sur les differents processeurs.

L'autre type de thread est le thread utilisateur. Ici, ce n'est pas le noyau qui fait l'ordonnancement des threads, c'est l'application qui la fait manuellement par exemple a base de setjmp/longjmp.

Le noyau a souvent aussi des threads internes mais qui sont souvent pas tres important pour le developpeurs d'application.

"Mais je ne sais pas si l'utilisation de thread utilisateur bénéficie réellement des multi core ou multi processeurs."

Classiquement les libs de thread utilisateur bien ecrite mappent les thread utilisateur sur des threads noyau pour profiter de tous les CPUs de la machine (ce qui n'est pas forcement une bonne idee en terme de performance).

"Mais ce serait le cas seulement si les locks lors de l'accès à la file surpassent le temps d'exécution du workitem, c'est ça que tu veux dire?
A ce que j'en sais, acquérir un lock simple (non réentrant) coûte quelque chose comme 20 nanos. "

Il y a deux chsoes differentes ici. La premiere chose c'est en effet le surcout de la file en elle meme. Si le temps de traitement d'un objet de la file est comparable au cout du depilage de la file. Tu as perdu. Ca arrive assez souvent dans des cas ou le travail a effectue est coupe en tout petit bout. Ce qui m'a l'air d'etre le cas ici. Quand tu as 15000 threads dans des appli multi agent. Souvent ces des fourmis des choses comme ca, qui font chacun un traitement tres simple. Certainement inferieur a une milliseconde. Et la gestion de la file est eleve dans un cas comme ca.

Le deuxieme surcout vient de la contention sur la fifo en elle meme. La il ya deux effets qui se cumule, si tu as beaucoup de processeur, il devient probable qu'il y en ait deux qui accede la fifo en meme temps. Et donc l'un va devoir attendre. Ce qui souvent implique que l'un des processus va s'endormir pour un tour de scheduler noyau.
L'autre phenomene quand tu augmente le nombre de processeur est que les acces a la memoire deviennent souvent non uniforme (NUMA). Basiquement les barretes de memoires sont affecte a un processeur (ou ensemble de processeur). du coup, si la fifo n'est pas sur ta barrete de ram, les temps d'access deviennent plus eleve avec deux consequence soit une famine pour ce processeur la qui n'arrivent pas a locker la memoire soit un delai important pour les processeur "locaux" qui attendent que le processeur "distant" ai termine ses access a la memoire.
Dans tous les cas ca rallonge considerablement les temps d'access.

Ces effets NUMA arrivent assez rapidement par exemple, si tu as un bi quad coeur, tu as des effets numa qui apparaissent entre les caches des deux chip.

Une solution pour faire ca est d'avoir autant de file de travail que de point de contention memoire, ou meme de processeur. Chaque processeur ne prends des verrou que sur ca file locale et donc il y a moins de contention memoire. Quand la file d'un processeur devient vide, il verrouille la file d'un autre processeur et prends une fraction (typiquement la moitie) du travail.

Quelquechose d'assez interessant la dedans, c'est que tu peux implementer ces mecanismes la sans utiliser de verrou quasiment en utilisant juste des access memoire atomique. Tu peux meme faire des trucs plus fous en faisant un access non protege a la memoire et en verifiant qu'il n'y a pas eu d'acces concurent. Si il n'y a pas eu de probleme, tu es content, si il y a un probleme tu rentres dans un processus de synchronisation standard.

D'après ce que tu m'explique, ça serait des threads utilisateurs dans mon application. Dans ce cas, c'est bien le ThreadPoolExecutor qui gère tout ça?

Dans ma simulation, c'est pas vraiment des fourmis que j'ai puisque ce sont des humains qui doivent se déplacer. Il y a un peu de calcul pour trouver son chemin, échanger des infos, ... Est-ce que même avec des threads utilisateurs, il est utopique de faire tourner 15 000 agents?

"D'après ce que tu m'explique, ça serait des threads utilisateurs dans mon application. Dans ce cas, c'est bien le ThreadPoolExecutor qui gère tout ça? "

Je ne sais pas bien comment marche java, lis la doc de ton API et de ton interpreteur.
Verifie combien il y a de threads de declare au niveau de ton systeme d'exploitation. Si il y en a 15000 c'est cuit, il faut faire autrement.

"Dans ma simulation, c'est pas vraiment des fourmis que j'ai puisque ce sont des humains qui doivent se déplacer. Il y a un peu de calcul pour trouver son chemin, échanger des infos, ... Est-ce que même avec des threads utilisateurs, il est utopique de faire tourner 15 000 agents?"
la question est "quel volume de calcul represente une iteration de 1 humain ?"

Sur une simu de 1000 agents, j'ai une 30aine de thrad créés selon le gestionnaire de tâches de Windows.
Le volume de calcul pour 1 itération d'1 agent est fortement variable. Ca peut aller de "ne rien faire" à "cherche un plus court chemin à travers un (petit) graphe", mais rien de bien lourd en calcul.

1. Isukthar Voir le profil de Isukthar
2. Posté le 6 juillet 2009 à 21:59:42 Avertir un modérateur
3. J'utilise la classe ThreadPoolExecutor,

Quand tu auras tout dit!!!