## 4 SpMV and Gauss-Seidel on Matrix-DSP
### Multicore Vectorization Algorithm  
Combining the above optimization methods, the final multicore vectorization algorithms can be obtained as shown in Algorithms 3 and 4. Both algorithms compute blocks sequentially (Line 1 in Algorithms 3 and 4), and the first steps are generating the _Local_x_ and transferring it to the the GSM (Lines 2-4 in Algorithms 3 and 4). In the SpMV, each DSP core computes _AM_n_ subblocks in parallel, and double-buffering is performed in the AM loop (Lines 6-17 in Algorithm 3). Then, the _Vector_K_ and _Vector_xi_ are transferred into the AM (Lines 8-9 in Algorithm 3) for vector computation (Lines 10-15 in Algorithm 3). Finally, the computation output of the _Vector_ax_ is returned to the DDR (Line 16 in Algorithm 3). In Gauss-Seidel, all DSP cores are computed in parallel for one color (Lines 5-24 in Algorithm 4). In each AM loop with double buffering, the _Vector_x_, _Vector_K_, _Vector_xi_, _Vector_diag_, and _Vector_F_ are transferred into the AM (Lines 9-13 in Algorithm 4); then, vector iteration is performed (Lines 14-21 in Algorithm 4), and, finally, the updated _Vector_x_ is transferred back to the GSM (Line 22 in Algorithm 4). When all colors have been completed, the _Vector_x_ from the GSM is transferred back to the DDR for updating (Line 25 in Algorithm 4).  
Figure 8: Description of SpMV DMA double buffering. (**a**) denotes the original data transfer computation flow and (**b**) denotes the double-buffer data transfer computation flow.  
Figure 9: Description of Gauss–Seidel DMA double buffering. (**a**) denotes the original data transfer computation flow and (**b**) denotes the double-buffer data transfer computation flow.  
```
1:for\((nb=0;nb<block\_n;nb++)\)do
2:MEM_copy:indexVector_x by Buffer_idx[nb] get Buffer_x[nb]
3:DMA_p2p:transfer Buffer_x[nb] from DDR to GSM
4:DMA_p2p:transfer Vector_x[nb] from DDR to GSM
5:#DSP core parallel:
6:for\((j=0;j<AM\_n;j++)\)do
7:#Double buffering:
8:DMA_p2p:Vector_K from DDR to AM
9:DMA_SG:index Local_x by Local_idx from GSM to AM
10:for\((k=0;k<vec\_n;k++)\)do
11:for\((n=0;n<nnz\_row;n++)\)do
12:#vectorized parallel:
13:\(vec\_ax[k]+=vec\_K[k+vec\_n\cdot n]\cdotvec\_xi[k+vec\_n]\)
14:endfor
15:endfor
16:DMA_p2p:transfer Vector_ax from AM to DDR
17:endfor
18:endfor
```  
**Algorithm 3** Optimized SpMV on Matrix-DSP  
```
1:for\((nb=0;nb<block\_n;nb++)\)do
2:MEM_copy:index Vector_x by Buffer_idx[nb] get Buffer_x[nb]
3:DMA_p2p:transfer Buffer_x[nb] from DDR to GSM
4:DMA_p2p:transfer Vector_x[nb] from DDR to GSM
5:for\((i=0;i<color\_n;i++)\)do
6:#DSP core parallel:
7:for\((j=0;j<AM\_n;j++)\)do
8:#Double buffering:
9:DMA_p2p:transfer Vector_x from GSM to AM
10:DMA_p2p:transfer Vector_K from DDR to AM
11:DMA_SG:index Local_x by Local_idx from GSM to AM
12:DMA_p2p:transfer Vector_diag from DDR to AM
13:DMA_p2p:transfer Vector_F from DDR to AM
14:for\((k=0;k<vec\_n;k++)\)do
15:for\((n=0;n<nnz\_row;n++)\)do
16:#vectorized parallel:
17:\(vec\_ax[k]+=vec\_K[k+vec\_n\cdot n]\cdotvec\_xi[k+vec\_n\cdot n]\)
18:endfor
19:#vectorized parallel:
20:\(vec\_x[k]+=(vec\_F[k]-vec\_ax[k])/vec\_diag[k]\)
21:endfor
22:DMA_p2p:transfer Vector_x from AM to GSM
23:endfor
24:endfor
25:DMA_p2p:transfer Vector_x[nb] from GSM to DDR
26:endfor
```  
**Algorithm 4** Optimized Gauss-Seidel on Matrix-DSP