PandA-2024.02
nussinov.c
Go to the documentation of this file.
1 
10 /* nussinov.c: this file is part of PolyBench/C */
11 
12 #include <stdio.h>
13 #include <unistd.h>
14 #include <string.h>
15 #include <math.h>
16 
17 /* Include polybench common header. */
18 #include <polybench.h>
19 
20 /* Include benchmark-specific header. */
21 #include "nussinov.h"
22 
23 /* RNA bases represented as chars, range is [0,3] */
24 typedef char base;
25 
26 #define match(b1, b2) (((b1)+(b2)) == 3 ? 1 : 0)
27 #define max_score(s1, s2) ((s1 >= s2) ? s1 : s2)
28 
29 /* Array initialization. */
30 static
31 void init_array (int n,
34 {
35  int i, j;
36 
37  //base is AGCT/0..3
38  for (i=0; i <n; i++) {
39  seq[i] = (base)((i+1)%4);
40  }
41 
42  for (i=0; i <n; i++)
43  for (j=0; j <n; j++)
44  table[i][j] = 0;
45 }
46 
47 
48 /* DCE code. Must scan the entire live-out data.
49  Can be used also to check the correctness of the output. */
50 static
51 void print_array(int n,
53 
54 {
55  int i, j;
56  int t = 0;
57 
59  POLYBENCH_DUMP_BEGIN("table");
60  for (i = 0; i < n; i++) {
61  for (j = i; j < n; j++) {
62  if (t % 20 == 0) fprintf (POLYBENCH_DUMP_TARGET, "\n");
64  t++;
65  }
66  }
67  POLYBENCH_DUMP_END("table");
69 }
70 
71 
72 /* Main computational kernel. The whole function will be timed,
73  including the call and return. */
74 /*
75  Original version by Dave Wonnacott at Haverford College <davew@cs.haverford.edu>,
76  with help from Allison Lake, Ting Zhou, and Tian Jin,
77  based on algorithm by Nussinov, described in Allison Lake's senior thesis.
78 */
79 __attribute__((noinline))
80 void kernel_nussinov(int n, base POLYBENCH_1D(seq,N,n),
82 {
83  int i, j, k;
84 
85 #pragma scop
86  for (i = _PB_N-1; i >= 0; i--) {
87  for (j=i+1; j<_PB_N; j++) {
88 
89  if (j-1>=0)
90  table[i][j] = max_score(table[i][j], table[i][j-1]);
91  if (i+1<_PB_N)
92  table[i][j] = max_score(table[i][j], table[i+1][j]);
93 
94  if (j-1>=0 && i+1<_PB_N) {
95  /* don't allow adjacent elements to bond */
96  if (i<j-1)
97  table[i][j] = max_score(table[i][j], table[i+1][j-1]+match(seq[i], seq[j]));
98  else
99  table[i][j] = max_score(table[i][j], table[i+1][j-1]);
100  }
101 
102  for (k=i+1; k<j; k++) {
103  table[i][j] = max_score(table[i][j], table[i][k] + table[k+1][j]);
104  }
105  }
106  }
107 #pragma endscop
108 
109 }
110 
111 
112 int main(int argc, char** argv)
113 {
114  /* Retrieve problem size. */
115  int n = N;
116 
117  /* Variable declaration/allocation. */
120 
121  /* Initialize array(s). */
123 
124  /* Start timer. */
126 
127  /* Run kernel. */
128  kernel_nussinov (n, POLYBENCH_ARRAY(seq), POLYBENCH_ARRAY(table));
129 
130  /* Stop and print timer. */
133 
134  /* Prevent dead-code elimination. All live-out data must be printed
135  by the function call in argument. */
137 
138  /* Be clean. */
141 
142  return 0;
143 }
#define POLYBENCH_ARRAY(x)
Definition: polybench.h:84
#define POLYBENCH_DUMP_BEGIN(s)
Definition: polybench.h:167
char base
This version is stamped on May 10, 2016.
Definition: nussinov.c:24
__attribute__((noinline))
Convert the given fixedpt number to a decimal string.
Definition: nussinov.c:79
#define POLYBENCH_FREE_ARRAY(x)
Definition: polybench.h:88
#define POLYBENCH_2D(var, dim1, dim2, ddim1, ddim2)
Definition: polybench.h:98
base seq[MAX_SIZE]
int main(int argc, char **argv)
Definition: nussinov.c:112
static void print_array(int n, DATA_TYPE POLYBENCH_2D(table, N, N, n, n))
Definition: nussinov.c:51
static const uint32_t k[]
Definition: sha-256.c:22
static void init_array(int n, base POLYBENCH_1D(seq, N, n), DATA_TYPE POLYBENCH_2D(table, N, N, n, n))
Definition: nussinov.c:31
#define POLYBENCH_DUMP_START
Definition: polybench.h:165
#define N
Definition: dfdiv.c:60
#define POLYBENCH_2D_ARRAY_DECL(var, type, dim1, dim2, ddim1, ddim2)
Definition: polybench.h:131
#define DATA_PRINTF_MODIFIER
Definition: correlation.h:73
#define polybench_prevent_dce(func)
Definition: polybench.h:170
#define POLYBENCH_DUMP_TARGET
Definition: polybench.h:164
#define POLYBENCH_DUMP_END(s)
Definition: polybench.h:168
#define POLYBENCH_1D(var, dim1, ddim1)
Definition: polybench.h:97
#define max_score(s1, s2)
Definition: nussinov.c:27
#define POLYBENCH_DUMP_FINISH
Definition: polybench.h:166
#define POLYBENCH_1D_ARRAY_DECL(var, type, dim1, ddim1)
Definition: polybench.h:128
#define match(b1, b2)
Definition: nussinov.c:26
#define _PB_N
Definition: correlation.h:49
#define polybench_stop_instruments
Definition: polybench.h:177
#define polybench_print_instruments
Definition: polybench.h:178
#define polybench_start_instruments
Definition: polybench.h:176
#define DATA_TYPE
Definition: correlation.h:72

Generated on Mon Feb 12 2024 13:02:50 for PandA-2024.02 by doxygen 1.8.13