# Algorithmic Design of an FPGA-Based Calculator for Fast Evaluation of Tsunami Wave Danger
## 2 Materials and Methods
### HLS-Based Algorithm Porting
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Implementation**} & \multirow{2}{*}{**Lines of Code**} & **Maximum Frequency** & **Number of LUTs** & **Number of Flip-Flops** & **Number of BRAMs (36 K)** & **Number of DSP Blocks** \\ \hline Naïve HLS & \(\sim\)40 & 308 MHz & 7364 & 7467 & 198 & 48 \\ HLS (148.5 MHz) & \(\sim\)60 & 308 MHz & 4575 & 5100 & 15 & 39 \\ HLS (400 MHz) & \(\sim\)60 & 637 MHz & 6145 & 9717 & 16 & 30 \\ HLS half (400 MHz) & \(\sim\)60 & 514 MHz & 2875 & 4261 & 8 & 30 \\ MFiz) & \(\sim\)280 & 374 MHz & 4302 & 6709 & 15 & 34 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of FPGA-based implementations by resource utilization. \[\frac{\widetilde{H_{ij}^{n+1}}-H_{ij}^{n}}{\tau}+\frac{H_{ij}^{n}u_{ij}^{n}-H_{i-1 j}^{n}u_{i-1j}^{n}}{\Delta x}+\frac{H_{ij}^{n}v_{ij}^{n}-H_{ij-1}^{n}v_{ij-1}^{n}}{ \Delta y}=0\]

\[\frac{\widetilde{u}_{ij}^{n+1}-u_{ij}^{n}}{\tau}+u_{ij}^{n}\frac{u_{ij}^{n}-u_{ i-1j}^{n}}{\Delta x}+v_{ij}^{n}\frac{u_{ij}^{n}-u_{ij-1}^{n}}{\Delta y}+g\frac{ \eta_{ij}^{n}-\eta_{i-1j}^{n}}{\Delta x}=0\]

\[\frac{\widetilde{v}_{ij}^{n+1}-v_{ij}^{n}}{\tau}+u_{ij}^{n}\frac{v_{ij}^{n}-v _{i-1j}^{n}}{\Delta x}+v_{ij}^{n}\frac{v_{ij}^{n}-v_{i-1}^{n}}{\Delta y}+g \frac{\eta_{ij}^{n}-\eta_{i-1}^{n}}{\Delta y}=0\]

\[\frac{H_{ij}^{n+1}-\left(\widetilde{H_{ij}}^{n+1}+H_{ij}^{n}\right)/2}{\tau/2 }+\frac{\widetilde{H_{i+1j}^{n+1}}\widetilde{u_{i+1j}^{n+1}}-\widetilde{H_{ij }^{n+1}}-\widetilde{u_{ij}^{n+1}}}{\Delta x}+\frac{\widetilde{H_{ij+1}^{n+1}} \widetilde{v_{i+1}^{n+1}}-\widetilde{H_{ij}^{n+1}}\widetilde{v_{ij}^{n+1}}}{ \Delta y}=0\]

\[\frac{u_{ij}^{n+1}-\left(\widetilde{u}_{ij}^{n+1}+u_{ij}^{n}\right)/2}{\tau/2 }+\frac{\widetilde{u_{i+1j}^{n+1}}\widetilde{u_{i+1j}^{n+1}}-\widetilde{u_{ij }^{n+1}}}{\Delta x}+v_{ij}^{n}\frac{\widetilde{u_{i+1}^{n+1}}-\widetilde{v_{ij }^{n+1}}}{\Delta y}+g\frac{\widetilde{\eta_{i+1j}^{n+1}}-\widetilde{\eta_{ij }^{n+1}}}{\Delta x}=0\]

\[\frac{v_{ij}^{n+1}-\left(\widetilde{v}_{ij}^{n+1}+v_{ij}^{n}\right)/2}{\tau/2 }+\frac{u_{ij}^{n}\frac{\widetilde{v_{i+1j}^{n+1}}-\widetilde{v_{ij}^{n+1}}} {\Delta x}}+v_{ij}^{n}\frac{\widetilde{v_{i+1}^{n+1}}-\widetilde{v_{ij}^{n+1}} }{\Delta y}+g\frac{\widetilde{\eta_{i+1}^{n+1}}-\widetilde{\eta_{ij}^{n+1}}}{ \Delta y}=0\]

where \(H^{n}{}_{ij}\), \(u^{n}{}_{ij}\), and \(v^{n}{}_{ij}\) are the gridded variables that correspond to the \(H\), \(u\), and \(v\) functions, respectively, in Differential System (1). The parameters \(\tau\), \(\Delta x\), and \(\Delta y\) are the time step and spatial steps of the computational grid. In order to account for the spherical shape of the Earth, we used a decreasing grid step with respect to longitude for larger values of latitude. The notation \(F_{ij}^{n}\) represents variables at time layer \(n\), \(\widetilde{F_{ij}^{n+1}}\) represents intermediate values, and \(F_{ij}^{n+1}\) corresponds to the variables at time layer \(n+1\). In order to calculate wave parameters \(H_{ij}\), \(u_{ij}\) and \(v_{ij}\) for the time step \(n+1\) along the line \(j=2\) of the gridded arrays, we need the data from the time step \(n\) along the lines \(j=1,2,3\). Wave parameters along the line \(j=1\) are obtained using the boundary conditions. When the wave parameters for the time step \(n+1\) are already calculated for at least 3 neighboring lines \(j=2,3,4\), the calculator #3 can start working to obtain the wave parameters for the time step \(n+2\) along the line \(j=3\), and so on (Figure 1). All 8 calculators work simultaneously on wave parameters for 8 time layers. The inner memory of each calculator keeps all data (wave parameters and bathymetry) for one time layer. Figure 1: The scheme of computing the conveyer (pipeline) using 3+ calculators. In fact, this scheme is similar in structure to the convolutional algorithm described above. Thus, the proposed approach was applied to the MacCormack scheme. As the result, a special processor element (PE) was designed to implement one step of the algorithm (see [1]).