paralléliser un traitement

Version imprimable

30/10/2009, 11h34
siempre

paralléliser un traitement
Bonjour,
J'ai une demande et j'ai besoin de vos aides. En réalité, J'ai fichier XML "input.xml" de taille volumineux. Pour lire ce fichier, j'ai utilisé la fonction 'lire_fichier(nom de fichier)'.
Dans mon cas, je dois décomposer ce fichier xml en plusieurs fichiers XML selon des critères bien définis.
Supposons que N est le nombre de ces fichiers décomposés.

Je vais faire le même traitement X pour chacun de ces N fichiers

Voici une partie de code:
Code:

1 2 3 4 5 6 7 8 9 10 for(i=1;i <= N;i++) { sprintf(tmp,"input%d",i); lire_fichier(tmp); //le même traitement X .......... ............ }
J'ai testé ce code sur ma machine alors ceci prendre beaucoup de temps.

Mon but est d'avoir le temps d'exécution le moins possible.

Est ce que c'est possible d'avoir un temps plus longue si on a travaille sur les N fichiers au lieu de travailler sur un seul fichier ou bien ceci dépend d'autres facteurs?

Dans mon cas, est ce que le mécanisme de parallélisme est possible ? c'est à dire on exécute chaque traitement sur une machine portant un fichier et donc on va utiliser N machines ?
C'est à dire on lance le traitement en même temps. Mais, ceci garantie que on va obtenir le résultat en un temps le moins possible ?

Que proposez vous ?

Merci.
30/10/2009, 13h04
Mac LAK

Citation:

Envoyé par siempre

J'ai testé ce code sur ma machine alors ceci prendre beaucoup de temps.

Mon but est d'avoir le temps d'exécution le moins possible.

Au cas où : pense quand même à vérifier que des outils XML adaptés (XSL, librairies-parser, génération de code, etc.) ne te simplifieraient pas la vie, dans le cas où tu n'aurais que l'obligation de résultat et non pas l'obligation de moyens.

Citation:

Envoyé par siempre

Est ce que c'est possible d'avoir un temps plus longue si on a travaille sur les N fichiers au lieu de travailler sur un seul fichier ou bien ceci dépend d'autres facteurs?

Cela dépend d'autres facteurs : typiquement, le disque dur est une ressource critique (=accessible par un seul élément à la fois), donc avoir 10 threads qui tapent dedans allègrement est plus pénalisant qu'autre chose en général : tu perds beaucoup de temps via le temps d'accès du disque...
Dans ton cas, il faudrait un thread lisant les fichiers, mis en cache en mémoire, et distribuant ensuite le boulot à des threads qui n'auraient alors plus besoin d'accéder au disque dur. Ils pourraient alors bénéficier correctement des cœurs multiples disponibles.

Citation:

Envoyé par siempre

Dans mon cas, est ce que le mécanisme de parallélisme est possible ? c'est à dire on exécute chaque traitement sur une machine portant un fichier et donc on va utiliser N machines ?

Tu peux découper ça avec un traitement par cœur de CPU, même. Le transfert sur une machine distante (clustering) ne peut être une solution intéressante QUE si l'on vérifie auparavant que le temps de transfert par le réseau n'est pas pénalisant par rapport au temps de traitement de chaque fichier. Plus ton fichier est petit et plus le traitement est long, et plus le clustering devient intéressant.

Citation:

Envoyé par siempre

C'est à dire on lance le traitement en même temps. Mais, ceci garantie que on va obtenir le résultat en un temps le moins possible ?

Tout dépend de ce que tu mesures : le temps réel physique (on commence le boulot à 13h00 et on le finit à 13h10, donc 10 minutes) ou le temps CPU consommé (si tu parallélises sur 20 unités d'exécution, tes 10 minutes "réelles" deviennent 10 x 20 = 200 minutes...).

Paralléliser coûte en général plus cher en temps CPU qu'un traitement parallèle, mais permet de gagner du temps "réel". Tout dépend ensuite de ce qui est le plus coûteux pour toi...
30/10/2009, 14h26
siempre

Ce qui est important pour moi est le temps CPU.
30/10/2009, 16h17
Mac LAK

Heu... As-tu bien compris ce qu'était le temps CPU, et ne confonds-tu pas avec le temps physique "réel" ?

Si oui, tu cherches à le maximiser (= saturer la machine), ou à le réduire ?
30/10/2009, 22h26
siempre

Citation:

As-tu bien compris ce qu'était le temps CPU, et ne confonds-tu pas avec le temps physique "réel" ?

non.

Citation:

tu cherches à le maximiser (= saturer la machine), ou à le réduire ?

à le réduire.
31/10/2009, 10h50
Mac LAK

Alors aucun intérêt à paralléliser, vu que ça va augmenter le temps CPU utilisé.

Si tu veux réduire le temps CPU (= la charge de la machine), on passe par des processus peu prioritaires et des traitements les moins lourds/intrusifs possibles : cela veut dire virer l'affichage, virer les tests "inutiles", présupposer la bonne forme des entrées et bosser en laissant du temps aux autres processus (ex : des "sleeps" placés judicieusement, passer toutes les I/O en asynchrone, etc.).

C'est pour ça que je te demandais si tu ne confondais pas les deux... Réduire le temps CPU utilisé n'a en général de sens que sur une machine intensivement partagée sur laquelle le temps CPU est "cher" (serveur d'applications par exemple), et n'a que rarement de sens / but sur des machines "personnelles".
31/10/2009, 17h54
siempre
Bonjour,

J'ai un fichier bien défini X et N fichiers Y de même format.
A chaque fois je compare le fichier X avec un de N fichiers. Donc j'ai N comparaisons.

le but de comparaison est chercher les lignes qui existent dans X et qui n'existent pas dans Y

Le principe de comparaison entre les deux fichiers X et Y:
on lit ligne par ligne de fichier X et on parcoure tout le fichier Y s'il n'existe pas cette ligne dans Y alors on affiche cette ligne etc ...

Voici un pseudo code :
Code:

1 2 3 4 5 for(i=1;i<=N;i++) while(fgets(s,100,X)) while(fgets(s,100,Y[i])) //chercher les lignes qui existent dans X et qui n'existent pas dans Y
On a ici le même traitement :
chercher les lignes qui existent dans X et qui n'existent pas dans Y

Que proposez vous ?

C'est quoi le multi-threading (n threads) et comment adapter ceci à mon cas?

Moi je mesure le temps d'exécution de comparaison entre deux fichiers.
Code:

1 2 3 4 5 6 debut = clock(); //comparaison entre deux fichiers fin = clock(); printf(stderr, "temps : %f\n", (double)(fin-debut) / (double) CLOCKS_PER_SEC);
lorsque je lance une comparaison entre deux fichiers alors on a un temps t très longue par exemples t = milliers des secondes ou bien la machine se plante.
par exemple X et Y contiennent des centaines des lignes.

Merci.
31/10/2009, 18h53
Mac LAK

Citation:

Envoyé par siempre

Moi je mesure le temps d'exécution de comparaison entre deux fichiers.

Ce que tu mesures, c'est le temps physique réel... Le temps que tu vois TOI, et non pas le temps machine (qui peut se résumer en "nombre total de cycles CPU utilisés sur toutes les unités d'exécution possibles").
Je savais bien que tu confondais... ;)

Citation:

Envoyé par siempre

lorsque je lance une comparaison entre deux fichiers alors on a un temps t très longue par exemples t = milliers des secondes ou bien la machine se plante.
par exemple X et Y contiennent des centaines des lignes.

Si elle se plante, t'as une erreur dans tes algos, tout simplement.
Sinon, effectivement, la parallélisation est une bonne option, il faut commencer par mettre en mémoire (= en cache) le fichier d'origine X, et lancer un thread par coeur sur la comparaison avec les autres fichiers (un thread se chargeant de la répartition). Les données du fichier X doivent bien sûr être considérées comme étant en lecture seule.

Ensuite, chaque thread de travail va lire le fichier qu'il doit comparer, effectuer ladite comparaison, puis retourner un résultat.
Le thread de répartition, lui, peut être le thread principal. Il va faire la liste des fichiers à comparer pour commencer, charger le fichier de référence X, puis créer (et alimenter !) les threads de calcul tout en récupérant / concaténant les résultats.
31/10/2009, 19h25
siempre

Citation:

et non pas le temps machine (qui peut se résumer en "nombre total de cycles CPU utilisés sur toutes les unités d'exécution possibles").

Donc, comment on mesure le temps CPU ? il y a des fonctions prédéfinis en C permettant de mesurer ce temps ?

Citation:

Si elle se plante, t'as une erreur dans tes algos, tout simplement.

Je voulais dire que le résultat apparait sur écran après un certain temps.

Citation:

Sinon, effectivement, la parallélisation est une bonne option, il faut commencer par mettre en mémoire (= en cache) le fichier d'origine X, et lancer un thread par coeur sur la comparaison avec les autres fichiers (un thread se chargeant de la répartition). Les données du fichier X doivent bien sûr être considérées comme étant en lecture seule.

Ensuite, chaque thread de travail va lire le fichier qu'il doit comparer, effectuer ladite comparaison, puis retourner un résultat.
Le thread de répartition, lui, peut être le thread principal. Il va faire la liste des fichiers à comparer pour commencer, charger le fichier de référence X, puis créer (et alimenter !) les threads de calcul tout en récupérant / concaténant les résultats.

Je vous demande c'est possible de m'expliquer encore votre idée et c'est possible un pseudo code ou code de votre solution ?

Merci.

Citation:

Envoyé par siempre

Bonjour,

J'ai un fichier bien défini X et N fichiers Y de même format.
A chaque fois je compare le fichier X avec un de N fichiers. Donc j'ai N comparaisons.

le but de comparaison est chercher les lignes qui existent dans X et qui n'existent pas dans Y

Le principe de comparaison entre les deux fichiers X et Y:
on lit ligne par ligne de fichier X et on parcoure tout le fichier Y s'il n'existe pas cette ligne dans Y alors on affiche cette ligne etc ...

Ca c'est l'algo du débutant ou de celui qui n'a rien d'autre.

En revanche, si tes 2 fichiers sont triés tous deux sur le même critère, alors tu peux réduire tes temps de recherche de façon exponentielle en utilisant l'appareillage.
Le principe est de lire alternativement l'un ou l'autre des deux fichiers en se basant sur leur tri. Si l'info du fichier 1 est plus petite que l'info du fichier 2, alors on continue à lire le fichier 1. Si l'info devient tout d'un coup plus grande, alors on sait que l'info du fichier 2 n'est pas dans le fichier 1 sinon on aurait eu une égalité. Et on se met alors à lire le fichier 2 jusqu'à ce qu'on dépasse l'info du fichier 1. On rebascule alors sur le fichier 1 et ainsi de suite

Algo:
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 ouvrir fichier 1 ouvrir fichier 2 flag1=vrai flag2=vrai tant que not eof fichier 1 ou not eof fichier 2 faire si flag1 alors lire fichier 1 flag1=faux fin si si flag2 alors lire fichier 2 flag2=faux fin si si info fichier1 = info fichier2 alors info commune fin si si info fichier1 <= info fichier2 alors flag1=vrai fin si si info fichier2 <= info fichier1 alors flag2=vrai fin si fin faire fermer fichiers
Faut affiner un peu le truc (ne pas lire un fichier dont l'eof aura été atteint) mais l'idée est là. Et cet algo peut très bien être étendu sur 3, 4, 50 fichiers lus en parallèles. Normalement il est enseigné dans les débuts des études d'informatique...