0votos

Carrera de "¡Baja la escalera!" en C

por josejuan usando OpenMP hace 5 años

Para 40.000 filas, el esfuerzo de gestionar 8 hilos no compensa.

Una variante que convierte al popular juguete en una carrera de la que debes calcular las mejores rutas de los corredores.

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
/* 
 * Representaremos el árbol como un array 1D 
 *         3,0, 
 *        2,7,0, 
 *       4,5,8,9 
 * Entonces, el índice (en base 0) del primer 
 * número de la fila `r` (en base 0) si el 
 * árbol tiene `w` corredores será 
 *      n w + n (n - 1) / 2 
 */ 
#include <stdio.h>  
#include <stdlib.h>  
#include <omp.h> 
 
#include <windows.h> 
#pragma comment(lib, "kernel32.lib") 
 
typedef LARGE_INTEGER timerStruct; 
 
void GetHighResolutionTime(timerStruct *t) { 
    QueryPerformanceCounter(t); 
 
float ConvertTimeDifferenceToSec(timerStruct *end, timerStruct *begin) { 
    timerStruct freq; QueryPerformanceFrequency(&freq);  return (end->QuadPart - begin->QuadPart) / (float) freq.QuadPart; 
 
#define byte unsigned char  
 
// `w` anchura, `r` índice en base 0 de la fila de la que devolver el índice del primer coste 
int IWR(int w, int r) { 
    return r * w + (r * (r - 1)) / 2; 
 
int * computeCosts(byte *pcosts, int w, int R) { 
    int *tcosts = (int *) malloc(sizeof(int) * IWR(w, R - w + 1)); 
    int i = IWR(w, R - w), iw = R, j, ii; 
 
#pragma omp parallel for default(none) shared(tcosts, pcosts, i, iw) private(j) 
    for (j = 0; j < iw; j++) 
        tcosts[i + j] = pcosts[i + j]; 
 
    while (--iw >= w) { 
        ii = i; 
        i -= iw; 
#pragma omp parallel for default(none) shared(tcosts, pcosts, i, ii, iw) private(j) 
        for (j = 0; j < iw; j++) { 
            int a = tcosts[ii + j]; 
            int b = tcosts[ii + j + 1]; 
            tcosts[i + j] = pcosts[i + j] + (a ^ ((b ^ a) & -(b < a))); 
 
    return tcosts; 
 
byte * randomTree(int w, int R) { 
    int i, maxr = IWR(w, R - w + 1); 
    byte *pcosts = (byte *) malloc(sizeof(byte) * maxr); 
    for (i = 0; i < maxr; i++) 
        pcosts[i] = rand() % 10; 
    return pcosts; 
 
void printTree(byte *pcosts, int w, int R) { 
    int iw; 
    for (iw = w; iw <= R; iw++) { 
        int j, i = IWR(w, iw - w); 
        for (j = iw; j < R; j++) 
            printf(" "); 
        for (j = 0; j < iw; j++) 
            printf("%i,", pcosts[i + j]); 
        printf("\n"); 
 
void printCostsTree(int *tcosts, int w, int R) { 
    int iw; 
    for (iw = w; iw <= R; iw++) { 
        int j, i = IWR(w, iw - w); 
        for (j = iw; j < R; j++) 
            printf("  "); 
        for (j = 0; j < iw; j++) 
            printf("% 4i,", tcosts[i + j]); 
        printf("\n"); 
 
void printCostsRunners(int *tcosts, int w) { 
    int i; 
    for (i = 0; i < w; i++) printf("%i, ", tcosts[i]); 
 
int main(int argc, char **argv) { 
    srand(1); 
    int w = atoi(argv[1]), r = atoi(argv[2]), p = atoi(argv[3]); 
    omp_set_num_threads(p); 
    byte *tree = randomTree(w, r); 
    if (r < 10) { 
        printTree(tree, w, r); 
        printf("\n\n"); 
    timerStruct ti, tf; 
    GetHighResolutionTime(&ti); 
    int *costs = computeCosts(tree, w, r); 
    GetHighResolutionTime(&tf); 
    printCostsRunners(costs, w); 
    printf("\n\n"); 
    if (r < 10) { 
        printCostsTree(costs, w, r); 
        printf("\n\n"); 
    printf("%f seg\n", ConvertTimeDifferenceToSec(&tf, &ti)); 
    printf("\n\n"); 
    return 0; 
/* 
 
testing>downStairsMP.exe 2 40000 8 
81080, 81086, 
 
3.193328 seg 
 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.