# Algorithmic Design of an FPGA-Based Calculator for Fast Evaluation of Tsunami Wave Danger
## 2 Materials and Methods
### HLS-Based Algorithm Porting  
Porting an existing algorithm from C/C++ in the Vivado/Vitis HLS environment consists of creating directives to the synthesizer indicating how one or another language construct should be implemented. If one starts the synthesis of the original streaming algorithm, the synthesizer will generate an ALU with multiplication and addition operations, as well as a state machine that will read data from the input interfaces and load them into the ALU in the desired order. This approach uses only two operational blocks, but requires several clock cycles to compute one pixel. In real tasks, it is necessary to use pipelining in order to be able to process one pixel per cycle; for this, the following PIPELINE directive given in Listing 4 is used. **Listing 4. ** Vitis HLS pipelining. ```
for(inti=0;i<width*(height+KERNELSIZE/2)+KERNELSIZE/2;i++){ #pragmaHLSPIPELINE... }
```  
This tells the synthesizer that this loop should be implemented as a pipeline; each iteration should start as soon as possible (interval, II)--ideally, every clock cycle. Not every loop can be perfectly pipelined; however, in our case, the synthesizer successfully pipelined the loop at intervals of 1 (every clock cycle). However, the resulting processor uses 9 times more memory for _stencil_ than needed. The source of this problem is suboptimal access to the _stencil_ variable. The fact is that the memory inside the FPGA has only two access ports; by default, HLS generates only one and, accordingly, the processor can access only one value from the _stencil_ at once, and convolution of each pixel requires access to 9 (KERNELSIZE * KERNELSIZE) values at the same time. The synthesizer bypasses this limitation by creating 9 copies of the _stencil_ buffer. However, if one looks closer at the algorithm, it become apparent that, for each iteration, one needs only to access one value from the previous lines, and the values of the previous pixels can be saved between iterations. Moreover, the very first line in the buffer can be immediately replaced with the current one. Then, only _KERNELSIZE-1_ samples from the stencil are required. Moreover, it should be noted that for each line of the buffer, only one pixel is selected at a time, so the buffer can be split line by line between memory blocks, providing the required number of ports. Thus, Listing 5 of the algorithm is as follows:```
... Pixelstencil[KERNELSIZE-1][MAXWIDTH]; #pragmaHLSARRAYARTITIONdim=1 type=completevariable=stencil Pixelpixels[KERNELSIZE][KERNELSIZE][E][KERNELSIZE]; #pragmaHLSARRAYARTITIONdim=1 type=completevariable=pixels #pragmaHLSARRAYARTITIONdim=2 type=completevariable=pixels for(inti=0;i<width*(height+KERNELSIZE/2)+KERNELSIZE/2;i++){ #pragmaHLSPIPELINE Pixelcur=0.0f; if(iy<height) cur=input.read(); for(intky=0;ky<KERNESIZE;ky++){ #pragmaHLSUNROLL for(intltx=0;kx<KERNESIZE-1;kx++){ #pragmaHLSUNROLL pixels[ky][kx]=pixels[ky][kx+1]; } if(ky!=KERNELSIZE-1) pixels[ky][KERNELSIZE-1]=  stencil[(iy+ky)%(KERNESIZE-1)][ix]; else pixels[ky][KERNELSIZE-1]=cur; } stencil[iy%(KERNELSIZE-1)][ix]=cur; if((ox\geq 0)&&(oy\geq 0)){  Pixelresult=0.0; for(intlxy=0;ky<KERNESIZE;ky++){ #pragmaHLSUNROLL for(intltx=0;kx<KERNESIZE;kx++){ #pragmaHLSUNROLL intss=ox+kx-KERNESIZE/2; intss=oy+ky-KERNELESIZE/2; sx=(ss<0)? (KERNESIZE/2-ox):((ssx>width-1+KERNELSIZE/2-ox):kx); (width-1+KERNELSIZE/2-oy):((sy>height)? (height-1+KERNELSIZE/2-oy):ky); result+=pixels[sy][ssx]*kernel[ky][kx]; } } output. write (result); }...
```

**Listing 5**. Convolutional filter with array partitioning. Here, the _pixels_ array is used to store the current pixels participating in the convolution. _HLSARRAYARTITION_ specifies how the array is decomposed across FPGA memory blocks. _HLS UNROLL_ unrolls a loop into linear code at the compilation stage. ### Comparison to Verolog Realization

Using a similar approach, the filtering algorithm was implemented in the Verilog language.