# 3D Tiled Code Generation for [PERSON]'s Algorithm
## 4 Related Work  
There are many parallel implementations of [PERSON]'s RNA folding to be run on CPUs, GPUs, co-processors, and FPGA platforms [2; 3; 10; 11; 12; 13; 14; 15]. However, increasing the performance of code implementing [PERSON]'s algorithm is still a challenging task, most of all for optimizing compilers, which automatically generate target parallel code. Code implementing [PERSON]'s folding exposes non-uniform data dependence, which is more difficult for optimization [3]. In this article, we focus mainly on related works that automatically parallelize the [PERSON] code and which can be adapted to similar codes such as [PERSON]'s RNA folding [16] or [PERSON]'s [17] sequence alignment algorithms without manual corrections. [PERSON] and et al. [18] introduced a manual implementation of [PERSON]'s algorithm. They suggested using the lower and unused part of [PERSON]'s matrix and changing the column reading to the more cache efficient row one. In the target code, scanning diagonal elements is possible in parallel--see Listing 5. ```
1#pragmaompparallelfor(i=0;i<=N-1;i++)
3S[i][i] = 0;
4
5#pragmaompparallelfor(i=0;i<=N-2;i++)
7S[i][i+1] = 0;
8
9 for(diag=1;diag<=N-1;diag++){
10#pragmaompparallelforprivate(row,col,_max,t,k) shared(diag,RNA)
11 for(row=0;row<=N-diag-1;row++){
12 col=diag+row;
13_max=S[row+1][col-1]+bond(RNA,row,col);
14 for(k=row;k<=col-1;k++){
15t=S[row][k]+S[col][k+1];
16_max=max(_max,t);
17}
18S[row][col]=S[col][row]=_max;
19}
20}
```  
[PERSON] et al. [19] revised the _transpose_ method discussed above, derived the energy-efficient code, and carried out experiments with that code demonstrating higher performance in comparison with that based on [PERSON]'s transpose. Their code requires about half as much memory as does [PERSON]'s transpose. However, the authors do not present any parallel code. We observed that the ByRow strategy can be multi-threaded. The innermost loop does not carry any dependence, hence it can be parallelized, see Listing 6. Pluto [8] is one of most popular state-of-the-art source-to-source optimizing compilers. It converts serial C programs to parallel code. Unfortunately, Pluto is not able to tile the innermost loop of the code implementing [PERSON]'s algorithm. This loop is crucial for improving code locality [1; 2]. As a result, Pluto fails to produce 3D tiles that make the target tiles unbounded along axis \(k\). This does not allow us to reach maximal code locality and performance. The PPCG optimizing compiler generates code for GPUs; it applies [PERSON]'s and [PERSON]'s time partition schedules [20]. [PERSON] and Boungduhla introduces dynamic tiling for [PERSON]'s optimal prediction for the RNA secondary structure [1]. Theirimplementation is based on 3D iterative dynamic tiling technique, which eliminates cycles in the inter-tile dependence graph. ```
1#pragmaompparallelfor
2 for(i=0;i<=N-2;i++){
3S[i][i] = 0;
4S[i][i+1] = 0;
5}
6S[N-1][N-1] = 0;
7
8 for(i=N-3;i>=0;i--){
9 for(j=i+2;j<=N-1;j++)
10S[i][j] = S[i+1][j-1] + bond(RNA, i, j);
11 for(k=i;k <=N-2;k++)
12#pragmaompparallelforprivate(j)
13 for(j=k+1;j <=N-1;j++)
14S[i][j] = max(S[i][j],S[i][k] + S[k+1][j]);
15}
```  
[PERSON] et al. proposed 3D tiling of \"mostly-tileable\" code for RNA secondary-structure prediction [2]. Their technique forms non-problematic statement instances in source code. Such instances can be directly tiled. The reminding statement instances are not tiled and should be run serially. Their serial execution honors all the dependences that present in the source code. However, the authors do not propose any parallel code to implement their technique. In the past, we developed two techniques able to automatically tile all Nussinov loop nests based on the polyhedral model. Those techniques are implemented in the TRACO compiler. The first technique is discussed in the article [3]. It forms original rectangular tiles and then if original tiles are not valid (there exist cycles in the inter-tile dependence graph), corrects them into valid target ones.