```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 ``` ```#include #include #include #include #include #include #include #include int A[4096]; int B[13][4096]; int prefix[13][4096]; void omp_function(int m) { int h; for (h = 1; (1 << h) <= m; h++) #pragma omp parallel for for (int j = 0; j < m >> h; j++) B[h][j] = std::min(B[h-1][2*j], B[h - 1][2*j + 1]); //h = log(m) / log(2) - 1; for (h = h - 1; h >= 0; h--) { int end = (m >> h) - 1; prefix[h][0] = B[h][0]; #pragma omp parallel for for (int j = 1; j <= end; j++) { if (j % 2 == 1) { prefix[h][j] = prefix[h+1][(j-1)/2]; } else { prefix[h][j] = std::min(prefix[h+1][j/2 - 1], B[h][j]); } } } } void ser_function(int m) { int h; for (h = 1; (1 << h) <= m; h++) for (int j = 0; j < m >> h; j++) B[h][j] = std::min(B[h-1][2*j], B[h - 1][2*j + 1]); //h = log(m) / log(2) - 1; for (h = h - 1; h >= 0; h--) { int end = (m >> h) - 1; prefix[h][0] = B[h][0]; for (int j = 1; j <= end; j++) { if (j % 2 == 1) { prefix[h][j] = prefix[h+1][(j-1)/2]; } else { prefix[h][j] = std::min(prefix[h+1][j/2 - 1], B[h][j]); } } } } int main(int argc, char * argv[]) { srand(time(NULL)); for (int i = 0; i < 4096; i++) { A[i] = rand(); } struct timeval startt, endt, result; int max = INT_MIN; int min = INT_MAX; int rnd; gettimeofday(&startt, NULL); for (int i = 0; i < 10000; i++) { memcpy(B, A, sizeof(int) * 4096); ser_function(4096); } gettimeofday (&endt, NULL); result.tv_usec = (endt.tv_sec * 1000000 + endt.tv_usec) - (startt.tv_sec * 1000000 + startt.tv_usec); std::cout << " " << result.tv_usec / 1000000 << "." << std::setfill('0') << std::setw(6) << result.tv_usec % 1000000 << std::endl; gettimeofday(&startt, NULL); //#pragma omp parallel for for (int i = 0; i < 10000; i++) { memcpy(B, A, sizeof(int) * 4096); omp_function(4096); } gettimeofday (&endt, NULL); result.tv_usec = (endt.tv_sec * 1000000 + endt.tv_usec) - (startt.tv_sec * 1000000 + startt.tv_usec); std::cout << " " << result.tv_usec / 1000000 << "." << std::setfill('0') << std::setw(6) << result.tv_usec % 1000000 << std::endl; return 0; } ```