-
Notifications
You must be signed in to change notification settings - Fork 0
/
asm_cpu_omp.c
100 lines (80 loc) · 2.59 KB
/
asm_cpu_omp.c
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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
# define DEBUG 0
// ASM algorithm DP
const int POSSIBLE_NUM = 26;
char * POSSIBLE_CHAR = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int** D_matrix, **X_matrix;
int* T, *P;
int m, n;
int min(int a, int b) {
if (a < b) return a;
else return b;
}
void asm_parallel() {
# pragma omp parallel for
for (int i = 0; i < POSSIBLE_NUM; i++) {
for (int j = 0; j <= n; j++) {
if (j == 0) X_matrix[i][j] = 0;
else if(T[j-1] == (int)POSSIBLE_CHAR[i]) X_matrix[i][j] = j;
else X_matrix[i][j] = X_matrix[i][j-1];
}
}
for (int i = 0; i <= m; i++){
# pragma omp parallel for
for (int j = 0; j <= n; j++){
int l = P[i-1] - (int)'A'; // need check
int tmp = min(D_matrix[i-1][j-1], D_matrix[i-1][j]);
if (i == 0) D_matrix[i][j] = 0;
else if (j == 0) D_matrix[i][j] = i;
else if (T[j-1] == P[i-1]) D_matrix[i][j] = D_matrix[i-1][j-1];
else if (X_matrix[l][j] == 0) D_matrix[i][j] = 1 + min(tmp, i+j-1);
else D_matrix[i][j] = 1 + min(tmp, D_matrix[i-1][X_matrix[l][j]-1] + j - 1 - X_matrix[l][j]);
}
}
}
int main (int argc, char *argv[]) {
char *in_T = argv[1], *in_P = argv[2], *out = argv[3];
FILE *input_T, *input_P, *output;
input_T = fopen(in_T, "rb");
input_P = fopen(in_P, "rb");
fread(&n, 1, sizeof(int), input_T);
fread(&m, 1, sizeof(int), input_P);
T = (int*)malloc(sizeof(int)*n);
P = (int*)malloc(sizeof(int)*m);
fread(T, n, sizeof(int), input_T);
fread(P, m, sizeof(int), input_P);
fclose(input_T);
fclose(input_P);
D_matrix = (int**)malloc(sizeof(int*)*(m+1));
for (int i = 0; i <= m; i++){
D_matrix[i] = (int*)malloc(sizeof(int)*(n+1));
memset(D_matrix[i], 0, sizeof(int)*(n+1));
}
X_matrix = (int**)malloc(sizeof(int*)*(POSSIBLE_NUM));
for (int i = 0; i < POSSIBLE_NUM; i++){
X_matrix[i] = (int*)malloc(sizeof(int)*(n+1));
memset(X_matrix[i], 0, sizeof(int)*(n+1));
}
asm_parallel();
output = fopen(out, "wb");
for (int i = 0; i <= m; i++)
fwrite(D_matrix[i], n+1, sizeof(int), output);
# if DEBUG
for (int i = 0; i < POSSIBLE_NUM; i++){
for (int j = 0; j <= n; j++){
printf("%d ", X_matrix[i][j]);
}
printf("\n");
}
for (int i = 0; i <= m; i++){
for (int j = 0; j <= n; j++){
printf("%d ", D_matrix[i][j]);
}
printf("\n");
}
# endif
fclose(output);
return 0;
}