Brute force : OpenMP Thread

Invité · 25/04/2011, 09h50

Bonjour,

J'avais produit il y a quelque temps un code pour réaliser toutes les combinaisons d'une chaîne (brute force donc). Même si en soit ce code ne sert à rien en lisant des articles sur les trheads et sur le calcul parallèle, j'ai voulu tester cela sur mon code.

Voici les trois codes ("normal" ; pthread ; openmp) :

Normal

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <float.h>
#include <pthread.h>
 
int brute_force(char *charset, int nbChar);
void usage(char *nom_soft);
 
int brute_force(char *charset, int nbChar)
{
 
    int lenAlph = strlen(charset);
 
    int position[nbChar];
    int i,z;
    for (i = 0; i <  nbChar; i++)
        position[i] = 0;
    double nbPass;
    if (nbChar >= 3)
        nbPass = pow((double)lenAlph,(double)nbChar)-1;
    else
        nbPass = pow((double)lenAlph,(double)nbChar);
 
 
 
    double tailleKo, tailleMo, tailleGo;
    tailleKo = ((double)nbPass*((double)nbChar+2))/1024;
    tailleMo = tailleKo /1024;
    tailleGo = tailleMo /1024;
    fprintf(stderr, "Pour %.0f mots\nVous devez disposer d'environ : %.2f Ko soit %.2f Mo soit %.2f Go\n", nbPass, tailleKo, tailleMo, tailleGo);
    for(i=0; i < nbPass; i++)
    {
        for(z=0; z < nbChar; z++)
        {
            printf("%c", charset[position[z]]);
            position[z] += 1;
 
            int j = z;
            while(j >= 0)
            {
                if (position[j] == lenAlph)
                {
                    position[j] = 0;
                    position[j-1] +=1;
                }
                j--;
            }
 
 
        }
        puts("");
    }
 
    return nbPass;
}
 
void usage(char *nom_soft)
{
    fprintf(stderr, "Usage : %s <min> <max> (-c Charset) (-m|-u output)\n", nom_soft);
    fprintf(stderr, "min : Minimum length of words\n");
    fprintf(stderr, "max : Maximum length of words\n");
    fprintf(stderr, "Alphabet : caracters of the charset. Default is \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"\n");
    fprintf(stderr, "Output : -m : one file for each length\n");
    fprintf(stderr, "         -u : a single file\n");
    fprintf(stderr, "         default output is screen\n");
}
 
int main (int argc, char *argv[])
{
    int min, max;
    if ((argc <3) || (argc >7))
    {
        usage(argv[0]);
        exit(EXIT_FAILURE);
    }
 
    min = (int)strtol(argv[1], NULL,10);
    max = (int)strtol(argv[2],NULL,10);
 
    int i;
    if(max < min)
    {
        int tmp = min;
        min = max;
        max = tmp;
    }
 
 
 
 
    clock_t start, end;
    double elapsed;
 
    start = clock();                                  /* Lancement de la mesure */
    int nbPass = 0;
 
    for(i=min; i<=max; i++)
    {
        if ((argc == 5) && (strncmp(argv[3],"-c",(size_t)2)==0))
        {
            nbPass += brute_force(argv[4], i);
        }
        else if ((argc == 7) && (strncmp(argv[5],"-c",(size_t)2)==0))
        {
            nbPass += brute_force(argv[6], i);
        }
        else
        {
            nbPass += brute_force((char*)"ABCDEFGHIJKLMNOPQRSTUVWXYZ", i);
        }
    }
 
 
    fprintf(stderr, "FINISH\n");
    end = clock();                                    /* Arret de la mesure     */
 
    elapsed = ((double)end - start) / CLOCKS_PER_SEC; /* Conversion en seconde  */
 
    fprintf(stderr, "%d mots générés en %.2f secondes.\n", nbPass, elapsed);
 
    return EXIT_SUCCESS;
}

Pthread

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <float.h>
#include <pthread.h>
 
 
struct data
{
    int nbChar;
    char *charset;
};
 
void *brute_force(void *p_data);
void usage(char *nom_soft);
 
void *brute_force(void *p_data)
{
    if(p_data != NULL)
    {
 
 
        struct data *p = p_data;
        int lenAlph = strlen(p->charset);
 
        int position[p->nbChar];
        int i,z;
        for (i = 0; i <  p->nbChar; i++)
            position[i] = 0;
        double nbPass;
        if (p->nbChar >= 3)
            nbPass = pow((double)lenAlph,(double)p->nbChar)-1;
        else
            nbPass = pow((double)lenAlph,(double)p->nbChar);
 
 
 
        double tailleKo, tailleMo, tailleGo;
        tailleKo = ((double)nbPass*((double)p->nbChar+2))/1024;
        tailleMo = tailleKo /1024;
        tailleGo = tailleMo /1024;
        fprintf(stderr, "Pour %.0f mots\nVous devez disposer d'environ : %.2f Ko soit %.2f Mo soit %.2f Go\n", nbPass, tailleKo, tailleMo, tailleGo);
 
        for(i=0; i < nbPass; i++)
        {
            for(z=0; z < p->nbChar; z++)
            {
                printf("%c", p->charset[position[z]]);
                position[z] += 1;
 
                int j = z;
                while(j >= 0)
                {
                    if (position[j] == lenAlph)
                    {
                        position[j] = 0;
                        position[j-1] +=1;
                    }
                    j--;
                }
 
 
            }
            puts("");
        }
 
        return (void*)NULL/*nbPass*/;
 
    }
    return (void*)NULL;
}
 
void usage(char *nom_soft)
{
    fprintf(stderr, "Usage : %s <min> <max> (-c Charset) (-m|-u output)\n", nom_soft);
    fprintf(stderr, "min : Minimum length of words\n");
    fprintf(stderr, "max : Maximum length of words\n");
    fprintf(stderr, "Alphabet : caracters of the charset. Default is \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"\n");
    fprintf(stderr, "Output : -m : one file for each length\n");
    fprintf(stderr, "         -u : a single file\n");
    fprintf(stderr, "         default output is screen\n");
}
 
int main (int argc, char *argv[])
{
    int min, max;
    if ((argc <3) || (argc >7))
    {
        usage(argv[0]);
        exit(EXIT_FAILURE);
    }
 
    min = (int)strtol(argv[1], NULL,10);
    max = (int)strtol(argv[2],NULL,10);
 
    int i;
    if(max < min)
    {
        int tmp = min;
        min = max;
        max = tmp;
    }
 
 
 
 
    clock_t start, end;
    double elapsed;
 
    start = clock();                                  /* Lancement de la mesure */
    int nbPass = 0;
 
    pthread_t threads[max-min+1];
    struct data data_threads[max-min+1];
 
 
 
 
    int rc;
 
    for(i=min; i<=max; i++)
    {
 
        if ((argc == 5) && (strncmp(argv[3],"-c",(size_t)2)==0))
        {
            data_threads[i].nbChar = i;
 
            data_threads[i].charset = malloc(strlen(argv[4])*sizeof(char));
            if(data_threads[i].charset==NULL)
            {
                printf("erreur d'allocation mémoire\n");
                exit(EXIT_FAILURE);
            }
            strncpy(data_threads[i].charset,argv[4],strlen(argv[4]));
        }
        else if ((argc == 7) && (strncmp(argv[5],"-c",(size_t)2)==0))
        {
            data_threads[i].nbChar = i;
            data_threads[i].charset = malloc(strlen(argv[6])*sizeof(char));
            if(data_threads[i].charset==NULL)
            {
                printf("erreur d'allocation mémoire\n");
                exit(EXIT_FAILURE);
            }
            strncpy(data_threads[i].charset,argv[6],strlen(argv[6]));
        }
        else
        {
            data_threads[i].nbChar = i;
            data_threads[i].charset = malloc(strlen("ABCDEFGHIJKLMNOPQRSTUVWXYZ")*sizeof(char));
            if(data_threads[i].charset==NULL)
            {
                printf("erreur d'allocation mémoire\n");
                exit(EXIT_FAILURE);
            }
            strncpy(data_threads[i].charset,"ABCDEFGHIJKLMNOPQRSTUVWXYZ",strlen("ABCDEFGHIJKLMNOPQRSTUVWXYZ"));
        }
 
        rc = pthread_create(&threads[i], NULL, brute_force, &data_threads[i]);
        pthread_join (threads[i], NULL);
        if (rc)
        {
            printf("ERROR; return code from pthread_create() is %d\n", rc);
            exit(-1);
        }
    }
 
    fprintf(stderr, "FINISH\n");
    end = clock();                                    /* Arret de la mesure     */
 
    elapsed = ((double)end - start) / CLOCKS_PER_SEC; /* Conversion en seconde  */
 
    fprintf(stderr, "%d mots générés en %.2f secondes.\n", nbPass, elapsed);
 
    return EXIT_SUCCESS;
}

Openmp

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <float.h>
#include <omp.h>
 
int brute_force(char *charset, int nbChar);
void usage(char *nom_soft);
 
int brute_force(char *charset, int nbChar)
{
 
    int lenAlph = strlen(charset);
 
    int position[nbChar];
    int i,z;
    for (i = 0; i <  nbChar; i++)
        position[i] = 0;
    double nbPass;
    if (nbChar >= 3)
        nbPass = pow((double)lenAlph,(double)nbChar)-1;
    else
        nbPass = pow((double)lenAlph,(double)nbChar);
 
 
 
    double tailleKo, tailleMo, tailleGo;
    tailleKo = ((double)nbPass*((double)nbChar+2))/1024;
    tailleMo = tailleKo /1024;
    tailleGo = tailleMo /1024;
    fprintf(stderr, "Pour %.0f mots\nVous devez disposer d'environ : %.2f Ko soit %.2f Mo soit %.2f Go\n", nbPass, tailleKo, tailleMo, tailleGo);
    for(i=0; i < nbPass; i++)
    {
        for(z=0; z < nbChar; z++)
        {
            printf("%c", charset[position[z]]);
            position[z] += 1;
 
            int j = z;
            while(j >= 0)
            {
                if (position[j] == lenAlph)
                {
                    position[j] = 0;
                    position[j-1] +=1;
                }
                j--;
            }
 
 
        }
        puts("");
    }
 
    return nbPass;
}
 
void usage(char *nom_soft)
{
    fprintf(stderr, "Usage : %s <min> <max> (-c Charset) (-m|-u output)\n", nom_soft);
    fprintf(stderr, "min : Minimum length of words\n");
    fprintf(stderr, "max : Maximum length of words\n");
    fprintf(stderr, "Alphabet : caracters of the charset. Default is \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\"\n");
    fprintf(stderr, "Output : -m : one file for each length\n");
    fprintf(stderr, "         -u : a single file\n");
    fprintf(stderr, "         default output is screen\n");
}
 
int main (int argc, char *argv[])
{
    int min, max;
    if ((argc <3) || (argc >7))
    {
        usage(argv[0]);
        exit(EXIT_FAILURE);
    }
 
    min = (int)strtol(argv[1], NULL,10);
    max = (int)strtol(argv[2],NULL,10);
 
    int i;
    if(max < min)
    {
        int tmp = min;
        min = max;
        max = tmp;
    }
 
 
 
 
    clock_t start, end;
    double elapsed;
 
    start = clock();                                  /* Lancement de la mesure */
    int nbPass = 0;
#pragma omp parallel for private(i)
    for(i=min; i<=max; i++)
    {
        if ((argc == 5) && (strncmp(argv[3],"-c",(size_t)2)==0))
        {
            nbPass += brute_force(argv[4], i);
        }
        else if ((argc == 7) && (strncmp(argv[5],"-c",(size_t)2)==0))
        {
            nbPass += brute_force(argv[6], i);
        }
        else
        {
            nbPass += brute_force((char*)"ABCDEFGHIJKLMNOPQRSTUVWXYZ", i);
        }
    }
 
 
    fprintf(stderr, "FINISH\n");
    end = clock();                                    /* Arret de la mesure     */
 
    elapsed = ((double)end - start) / CLOCKS_PER_SEC; /* Conversion en seconde  */
 
    fprintf(stderr, "%d mots générés en %.2f secondes.\n", nbPass, elapsed);
 
    return EXIT_SUCCESS;
}

Je pense que je fait une erreur sur les codes threads et parallèle car voici le résultat de mes tests pour le charset par défaut avec mini 2 et max 5 :

thread : 29.17 s
openmp : 29.12 s
normal : 22 s

Quelles sont mes erreurs ? Comment puis-je améliorer ce résultat ?

**D[r]eadLock** · 27/04/2011, 23h06

Quelques remarques:

dans le code multi-thread, tu attends, la fin de chaque thread, dans ta boucle, donc en gros tu lance un thread, et l'attends ! Tu devrais faire deux boucles: une pour lancer les threads, et une pour les attendre.
si tu n'as qu'un seul core, tu ne devrais pas avoir de gain
tu devrais gérer indépendamment le parsing de la ligne de commande et le 'process' en lui-même.
je ne sais pas ce que tu as comme machine, mais je n'ai pas une machine récente, et avec 2 et 5 ça prends 4 secondes (normal et multi-threadé)

Brute force : OpenMP Thread

C

Discussions similaires

Partager

Partager