Dev - C++ - Analisis¿Que bucle es paralelizable?

   
Vista:

Analisis¿Que bucle es paralelizable?

Publicado por daniel dacachi@hotmail.es (5 intervenciones) el 24/10/2015 00:31:47
Buenas a todos. Soy bastante novato en c++, y una de las preguntas del siguiente codigo, es que cual de ellos es paralelizable.

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
float pp1 ()
{
	int  i;
	z=0.0;
	for (i=0;i<N_ITER;i++)
	{
		z+=a[i]/4;
 
		//z =  (z+a[i])*a[i]  ; // a longer dependence
		//try this one if simple z+=a[i]/4;   gives cycles/iteration very near from simple loop
	}
	return z;
}
float pp2 ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		a[i]=3/b[i];
	}
	return a[N_ITER-1 ];
}
float pp3 ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		a[i]=b[i]+c[i]+d[i]+e[i]+f[i]+g[i]+h[i]/4;
	}
	return a[N_ITER-1 ];
}
float pp4 ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		a[i]=b[i]+8;
	}
	return a[N_ITER-1 ];
}
 
float pp5a ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		if (cond1[i]!=0)
			a[i]=b[i]+8;
	}
	return a[N_ITER-1 ];
}
float pp5b ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		if (cond2[i]!=0)
			a[i]=b[i]+8;
	}
	return a[N_ITER-1 ];
}
 
float pp5c ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		if (cond3[i]!=0)
			a[i]=b[i]/8;
	}
	return a[N_ITER-1 ];
}
 
float pp5d ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		int cond_true = (cond3[i]); // condition can be 1 or 0
		float result_true = b[i]/8;
		int *p_int =  (int *)(&result_true );
		int mask = (cond_true -1); // the mask can be 0 or 0xFFFFFFFF , that is ,
		// a mask to perform AND operations 
 
		float result_false = -b[i] ;
		int *p_int_false = (int *)(&result_false);
		int temp = (*p_int  & (~mask)) | (*p_int_false & mask);
//		int temp = (*p_int  & (~mask)) | (*p_int & mask);
 
		float *p_float = (float *) & temp;
		a[i] = * p_float ;
	}
 
	/* 
	// The above code is tricky due to the float/integer mixture.
	// If vectors were integer , the integer version would be more understandable:
	for (i=0;i<N_ITER;i++)
		{
		int cond_true = (cond3[i]);   // condition can be 1 or 0
		int  result_true = a_int[i]/8;
		int mask = (cond_true -1);  // the mask can be 0 or 0xFFFFFFFF , that is , a mask to perform AND operations 
		a_int[i] =  ( result_true & (~mask) ) | ( result_true & mask ) ;
		}
		*/
 
	return a[N_ITER-1 ];
}
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

Analisis¿Que bucle es paralelizable?

Publicado por aguml (308 intervenciones) el 24/10/2015 10:09:52
¿Que es "paralelizable"?
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Analisis¿Que bucle es paralelizable?

Publicado por daniel (5 intervenciones) el 24/10/2015 10:31:36
tengo que descubrir que bucle no tienen saltos condicionales ni instrucciones que bloqueen la CPU
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Analisis¿Que bucle es paralelizable?

Publicado por daniel (5 intervenciones) el 24/10/2015 10:38:25
El objetivo de todo este codigo es descubrir cual de los bucles "pp" es el que hace lo mismo que un codigo en ensamblador que tengo.
El codigo ensamblador lo que hace basicamente es: tengo un array de 25 elementos, empieza en -1,2,-3.... y acaba en -25. Los numeros impares son negativos y los pares positivos. El ensamblador compara que si el elemento a analizar es positivo, lo almacena en el array.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Analisis¿Que bucle es paralelizable?

Publicado por Requeteprogramador (8 intervenciones) el 24/10/2015 11:19:02
Paralelizar un código que se ejecuta en un hilo es hacer que se ejecute en más de uno. Así que es paralizable cualquier código que se ejecute en un sólo hilo.

La única instrucción que bloquea una cpu es hlt. Eso para el reloj hasta que le llegue una interrupción externa. Otras cosas, como bucles infinitos, bloquean un hilo o un sistema operativo como mucho.

Yo no veo ningún bucle que haga eso que dices Sería alguno que hiciese algo como if (cond1[i]<0) a[j]=cond1[i];
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Analisis¿Que bucle es paralelizable?

Publicado por daniel (5 intervenciones) el 24/10/2015 12:30:48
Voy a subir el codigo completo , a ver si se aclara un poco.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Analisis¿Que bucle es paralelizable?

Publicado por daniel (5 intervenciones) el 24/10/2015 11:26:16
Voy a subir el codigo completo, a ver si aclara un poco. Una de las cosas que tengo que hacer es medir los tiempos y los ciclos por iteracion y compararlos con los ciclos medidos en un simulador aparte. Pero lo que no entiendo es otra pregunta que me hacen, que es descubrir cuál delas funciones "pp ()" es totalmente paralelizable y no tiene saltos condicionales dentro del bucle ni instrucciones que puedan bloquear la CPU.

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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
 
#include <iostream>
 
using namespace std;
//------------------------------------------------------------------
// project def and includes
 
// this test uses a new version of QueryPerformanceTiming , to measure CPU cycles more precisely using rdtsc asm instr.
#include "QueryPerformanceTiming_rdtsc.h"
 
 
#define  N_REPETIC 150
// repeat several times each test to extract the minimum time
// and to have the caches filled
 
#define  N_ITER (8)
//big number to have a mean time (but not vey big to avoid cache misses) 
 
int a_int[N_ITER ], b_int[N_ITER ];
 
float a[N_ITER ], b[N_ITER ];
float c[N_ITER ], d[N_ITER ];
float e[N_ITER ], f[N_ITER ];
float g[N_ITER ], h[N_ITER ];
float z;
 
int cond1[N_ITER ], cond2[N_ITER ], cond3[N_ITER ];
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
// vectors  init
void vectors_init ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		// a[i] must have little values to avoid overflow in pp1()
		a[i]=(float)rand()/(float)RAND_MAX;
		b[i]=(float)i/5;
		c[i]=(float)i/6;
		d[i]=(float)i/7;
		e[i]=(float)i/8;
		f[i]=(float)i/9;
		g[i]=(float)i/10;
		h[i]=(float)i/11;
 
		a_int[i]=i;
 
		cond1[i]=1;
		cond3[i]=rand()%2;
	}
 
	for (i=0;i<N_ITER;i+=8)
	{
		// put here the pattern behaviour  you want; BTB is very clever !!
		cond2[i+0]=1;
		cond2[i+1]=0;
		cond2[i+2]=1;
		cond2[i+3]=1;
		cond2[i+4]=0;
		cond2[i+5]=1;
		cond2[i+6]=1;
		cond2[i+7]=1;
	}
}
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
/// tests
float pp1 ()
{
	int  i;
	z=0.0;
	for (i=0;i<N_ITER;i++)
	{
		z+=a[i]/4;
 
		//z =  (z+a[i])*a[i]  ; // a longer dependence
		//try this one if simple z+=a[i]/4;   gives cycles/iteration very near from simple loop
	}
	return z;
}
float pp2 ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		a[i]=3/b[i];
	}
	return a[N_ITER-1 ];
}
float pp3 ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		a[i]=b[i]+c[i]+d[i]+e[i]+f[i]+g[i]+h[i]/4;
	}
	return a[N_ITER-1 ];
}
float pp4 ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		a[i]=b[i]+8;
	}
	return a[N_ITER-1 ];
}
 
float pp5a ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		if (cond1[i]!=0)
			a[i]=b[i]+8;
	}
	return a[N_ITER-1 ];
}
float pp5b ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		if (cond2[i]!=0)
			a[i]=b[i]+8;
	}
	return a[N_ITER-1 ];
}
 
float pp5c ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		if (cond3[i]!=0)
			a[i]=b[i]/8;
	}
	return a[N_ITER-1 ];
}
 
float pp5d ()
{
	int i;
	for (i=0;i<N_ITER;i++)
	{
		int cond_true = (cond3[i]); // condition can be 1 or 0
		float result_true = b[i]/8;
		int *p_int =  (int *)(&result_true );
		int mask = (cond_true -1); // the mask can be 0 or 0xFFFFFFFF , that is ,
		// a mask to perform AND operations 
 
		float result_false = -b[i] ;
		int *p_int_false = (int *)(&result_false);
		int temp = (*p_int  & (~mask)) | (*p_int_false & mask);
//		int temp = (*p_int  & (~mask)) | (*p_int & mask);
 
		float *p_float = (float *) & temp;
		a[i] = * p_float ;
	}
 
	/* 
	// The above code is tricky due to the float/integer mixture.
	// If vectors were integer , the integer version would be more understandable:
	for (i=0;i<N_ITER;i++)
		{
		int cond_true = (cond3[i]);   // condition can be 1 or 0
		int  result_true = a_int[i]/8;
		int mask = (cond_true -1);  // the mask can be 0 or 0xFFFFFFFF , that is , a mask to perform AND operations 
		a_int[i] =  ( result_true & (~mask) ) | ( result_true & mask ) ;
		}
		*/
 
	return a[N_ITER-1 ];
}
 
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main( int argc, char** argv ) {
 
	float var1,var2,var3,var4,var5a,var5b,var5c,var5d;
	int i;
 
	QPTimer c1,c2,c3,c4,c5a,c5b,c5c,c5d;
	c1.Calibrate(); //calibrates timer overhead and set cronometer to zero	
	c2.Calibrate(); //calibrates timer overhead and set cronometer to zero	
	c3.Calibrate(); //calibrates timer overhead and set cronometer to zero	
	c4.Calibrate(); //calibrates timer overhead and set cronometer to zero	
	c5a.Calibrate(); //calibrates timer overhead and set cronometer to zero	
	c5b.Calibrate(); //calibrates timer overhead and set cronometer to zero	
	c5c.Calibrate(); //calibrates timer overhead and set cronometer to zero	
	c5d.Calibrate(); //calibrates timer overhead and set cronometer to zero	
 
	vectors_init ();
	// measuring tests
	for (i=0;i<N_REPETIC;i++)
	{
		c1.Start();  // start timer
		var1=pp1(); // Do the test
		c1.Stop();  // stop timer
		c1.Reset();
	}
	vectors_init ();
	for (i=0;i<N_REPETIC;i++)
	{
		c2.Start();  // start timer
		var2=pp2(); // Do the test
		c2.Stop();  // stop timer
		c2.Reset();
	}
	vectors_init ();
	for (i=0;i<N_REPETIC;i++)
	{
		c3.Start();  // start timer
		var3=pp3(); // Do the test
		c3.Stop();  // stop timer
		c3.Reset();
	}
	vectors_init ();
	for (i=0;i<N_REPETIC;i++)
	{
		c4.Start();  // start timer
		var4=pp4(); // Do the test
		c4.Stop();  // stop timer
		c4.Reset();
	}
	vectors_init ();
	for (i=0;i<N_REPETIC;i++)
	{
		c5a.Start();  // start timer
		var5a=pp5a(); // Do the test
		c5a.Stop();  // stop timer
		c5a.Reset();
	}
	vectors_init ();
	for (i=0;i<N_REPETIC;i++)
	{
		c5b.Start();  // start timer
		var5b=pp5b(); // Do the test
		c5b.Stop();  // stop timer
		c5b.Reset();
	}
	vectors_init ();
	for (i=0;i<N_REPETIC;i++)
	{
		c5c.Start();  // start timer
		var5c=pp5c(); // Do the test
		c5c.Stop();  // stop timer
		c5c.Reset();
	}
	vectors_init ();
	for (i=0;i<N_REPETIC;i++)
	{
		c5d.Start();  // start timer
		var5d=pp5d(); // Do the test
		c5d.Stop();  // stop timer
		c5d.Reset();
	}
	// end of    testing
 
	cout << endl << "ONLY PRINTING OUTPUT VARIABLE TO PREVENT THAT THE COMPILER ELIMINATES FUNCTION CALLS: "
		<< var1 << ", "<< var2<< ", "<< var3 << ", "<< var4 << ", "<<var5a << ", "<< var5b << ", "<< var5c << ", "<< var5d << endl;
 
	cout << endl << "-Number of iterations N_ITER: " << N_ITER << endl;
	cout << endl << "-Number of measures: " << c1.NumberOfMeasures() << endl;
 
 
	// uncomment this if more timing results were needed:
	c1.PrintMinimumTime   (" Minimum time in seconds for pp1() is:   ");
	c1.PrintMeanTime      (" Mean time in seconds    for pp1() is:   ");
 
	c1.PrintMinimumCycles (" Minimum time in cycles for pp1()  is:   ");
	c1.PrintMeanCycles    (" Mean time in cycles for pp1() is    :   ");
 
 
	c1.PrintMinimumCyclesByIteration  (" Minimum time in cycles for an iteration of pp1()   is:   ", N_ITER);
	c2.PrintMinimumCyclesByIteration  (" Minimum time in cycles for an iteration of pp2()   is:   ", N_ITER);
	c3.PrintMinimumCyclesByIteration  (" Minimum time in cycles for an iteration of pp3()   is:   ", N_ITER);
	c4.PrintMinimumCyclesByIteration  (" Minimum time in cycles for an iteration of pp4()   is:   ", N_ITER);
	c5a.PrintMinimumCyclesByIteration (" Minimum time in cycles for an iteration of pp5a()  is:   ", N_ITER);
	c5b.PrintMinimumCyclesByIteration (" Minimum time in cycles for an iteration of pp5b()  is:   ", N_ITER);
	c5c.PrintMinimumCyclesByIteration (" Minimum time in cycles for an iteration of pp5c()  is:   ", N_ITER);
	c5d.PrintMinimumCyclesByIteration (" Minimum time in cycles for an iteration of pp5d()  is:   ", N_ITER);
 
	cout << endl  ;
	getchar();
}
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar