# Presentation: 544453

## NPB MG routine RESID

-             **do i3=2,n3-1**
**         ****do i2=2,n2-1**
**            ****do i1=1,n1**
**               ****u1(i1) = u(i1,i2-1,i3) + u(i1,i2+1,i3)**
**     ****>                + u(i1,i2,i3-1) + u(i1,i2,i3+1)**
**               ****u2(i1) = u(i1,i2-1,i3-1) + u(i1,i2+1,i3-1)**
**     ****>                + u(i1,i2-1,i3+1) + u(i1,i2+1,i3+1)**
**            ****enddo**
**            ****do i1=2,n1-1**
**               ****r(i1,i2,i3) = v(i1,i2,i3)**
**     ****>                     - a(0) * u(i1,i2,i3)**
**     ****>                     - a(2) * ( u2(i1) + u1(i1-1) + u1(i1+1) )**
**     ****>                     - a(3) * ( u2(i1-1) + u2(i1+1) )**
**            ****enddo**
**         ****enddo**
**      ****enddo**

**========================================================================**
**USER / resid_**
**------------------------------------------------------------------------**
**  ****Time%                                         42.4%**
**  ****Time                                      12.397761**
**  ****Imb.Time                                   0.000370**
**  ****Imb.Time%                                      0.0%**
**  ****Calls                                           340**
**  ****PAPI_L1_DCA             2719.188M/sec   33711498004 ops**
**  ****DC_L2_REFILL_MOESI        79.644M/sec     987402929 ops**
**  ****DC_SYS_REFILL_MOESI        4.059M/sec      50318116 ops**
**  ****BU_L2_REQ_DC             129.172M/sec    1601429574 req**
**  ****User time                 12.398 secs   32233848320 cycles**
**  ****Utilization rate                             100.0%**
**  ****L1 Data cache misses      83.703M/sec    1037721045 misses**
**  ****LD & ST per D1 miss                           32.49 ops/miss**
**  ****D1 cache hit ratio                            96.9%**
**  ****LD & ST per D2 miss                          669.97 ops/miss**
**  ****D2 cache hit ratio                            96.9%**
**  ****L2 cache hit ratio                            95.2%**
**  ****Memory to D1 refill        4.059M/sec      50318116 lines**
**  ****Memory to D1 bandwidth   247.723MB/sec   3220359424 bytes**
**  ****L2 to Dcache bandwidth  4861.112MB/sec  63193787456 bytes**
- ========================================================================

- n1

- n2

- n3

- Chunk Fits in L2 Cache

- i1 +1

- i1 -1

- i2 +1

- i2 - 1

- i3 + 1

- i3 - 1

- Entire Cube does not fit in
- L2 Cache
-   256*256*256*3 arrays
-  = 402 MBytes

- Take data in chunks that
- Fit in L2 Cache
-   256*16*32*3 arrays
-  = 1 MBytes

## Tiling for better Cache utilization

** ****do i3block=2,n3-1,BLOCK3**
**      ****do i2block=2,n2-1,BLOCK2**
**      ****do i3=i3block,min(n3-1,i3block+BLOCK3-1)**
**         ****do i2=i2block,min(n2-1,i2block+BLOCK2-1)**
**            ****do i1=1, n1**
**               ****u1(i1) = u(i1,i2-1,i3) + u(i1,i2+1,i3)**
**     ****>                + u(i1,i2,i3-1) + u(i1,i2,i3+1)**
**               ****u2(i1) = u(i1,i2-1,i3-1) + u(i1,i2+1,i3-1)**
**     ****>                + u(i1,i2-1,i3+1) + u(i1,i2+1,i3+1)**
**            ****enddo**
**            ****do i1=1, n1**
**               ****r(i1,i2,i3) = v(i1,i2,i3)**
**     ****>                     - a(0) * u(i1,i2,i3)**
**     ****>                     - a(2) * ( u2(i1) + u1(i1-1) + u1(i1+1) )**
**     ****>                     - a(3) * ( u2(i1-1) + u2(i1+1) )**
**            ****enddo**
**         ****enddo**
**      ****enddo**
**      ****enddo**
**      ****enddo**

- ========================================================================
**USER / resid_**
**------------------------------------------------------------------------**
**  ****Time%                                         36.3%**
**  ****Time                                       8.753226**
**  ****Imb.Time                                   0.000596**
**  ****Imb.Time%                                      0.0%**
**  ****Calls                                           340**
**  ****PAPI_L1_DCA             3861.533M/sec   33800955933 ops**
**  ****DC_L2_REFILL_MOESI       116.399M/sec    1018867620 ops**
**  ****DC_SYS_REFILL_MOESI        2.755M/sec      24114222 ops**
**  ****BU_L2_REQ_DC             161.490M/sec    1413560527 req**
**  ****User time                  8.753 secs   22758444048 cycles**
**  ****Utilization rate                             100.0%**
**  ****L1 Data cache misses     119.154M/sec    1042981842 misses**
**  ****LD & ST per D1 miss                           32.41 ops/miss**
**  ****D1 cache hit ratio                            96.9%**
**  ****LD & ST per D2 miss                         1401.70 ops/miss**
**  ****D2 cache hit ratio                            98.3%**
**  ****L2 cache hit ratio                            97.7%**
**  ****Memory to D1 refill        2.755M/sec      24114222 lines**
**  ****Memory to D1 bandwidth   168.145MB/sec   1543310208 bytes**
**  ****L2 to Dcache bandwidth  7104.420MB/sec  65207527680 bytes**

-        **do i3block=2,n3-1,BLOCK3**
**      ****do i2block=2,n2-1,BLOCK2**
**      ****do i3=i3block,min(n3-1,i3block+BLOCK3-1)**
**         ****do i2=i2block,min(n2-1,i2block+BLOCK2-1)**
**            ****do i1=1,n1**
**               ****u1(i1) = u(i1,i2-1,i3) + u(i1,i2+1,i3)**
**     ****>                + u(i1,i2,i3-1) + u(i1,i2,i3+1)**
**               ****u2(i1) = u(i1,i2-1,i3-1) + u(i1,i2+1,i3-1)**
**     ****>                + u(i1,i2-1,i3+1) + u(i1,i2+1,i3+1)**
**            ****enddo**
**            ****do i1=2,n1-1**
**               ****r(i1,i2,i3) = v(i1,i2,i3)**
**     ****>                     - a(0) * u(i1,i2,i3)**
**     ****>                     - a(2) * ( u2(i1) + u1(i1-1) + u1(i1+1) )**
**     ****>                     - a(3) * ( u2(i1-1) + u2(i1+1) )**
**            ****enddo**
**         ****enddo**
**      ****enddo**
**      ****enddo**
**      ****enddo**

-       **do i3block=2,n3-1,BLOCK3**
**      ****do i2block=2,n2-1,BLOCK2**
**      ****do i3=i3block,min(n3-1,i3block+BLOCK3-1)**
**         ****do i2=i2block,min(n2-1,i2block+BLOCK2-1)**
**            ****do i1=2,n1-1**
**               ****u21 = u(i1,i2-1,i3-1) + u(i1,i2+1,i3-1)**
**     ****>                + u(i1,i2-1,i3+1) + u(i1,i2+1,i3+1)**
**               ****u21p1 = u(i1+1,i2-1,i3-1) + u(i1+1,i2+1,i3-1)**
**     ****>                + u(i1+1,i2-1,i3+1) + u(i1+1,i2+1,i3+1)**
**               ****u21m1 = u(i1-1,i2-1,i3-1) + u(i1-1,i2+1,i3-1)**
**     ****>                + u(i1-1,i2-1,i3+1) + u(i1-1,i2+1,i3+1)**
**               ****u11p1 = u(i1+1,i2-1,i3) + u(i1+1,i2+1,i3)**
**     ****>                + u(i1+1,i2,i3-1) + u(i1+1,i2,i3+1)**
**               ****u11m1 = u(i1-1,i2-1,i3) + u(i1-1,i2+1,i3)**
**     ****>                + u(i1-1,i2,i3-1) + u(i1-1,i2,i3+1)**
**               ****r(i1,i2,i3) = v(i1,i2,i3)**
**     ****>                     - a(0) * u(i1,i2,i3)**
**     ****>                     - a(2) * ( u21 + u11m1 + u11p1 )**
**     ****>                     - a(3) * ( u21m1 + u21p1 )**
**            ****enddo**
**         ****enddo**
**      ****enddo**
**      ****enddo**
**      ****enddo**

**USER / resid_**
**------------------------------------------------------------------------**
**  ****Time%                                       37.7%**
**  ****Time                                     9.132935**
**  ****Imb.Time                                 0.003440**
**  ****Imb.Time%                                    0.1%**
**  ****Calls                                         340**
**  ****PAPI_TLB_DM               0.139M/sec      1270096 misses**
**  ****PAPI_L1_DCA            3694.219M/sec  33739238309 ops**
**  ****PAPI_FP_OPS            2601.948M/sec  23763548027 ops**
**  ****DC_MISS                 111.833M/sec   1021371774 ops**
**  ****User time                 9.133 secs  23745753175 cycles**
**  ****Utilization rate                           100.0%**
**  ****HW FP Ops / Cycles                           1.00 ops/cycle**
**  ****HW FP Ops / User time  2601.948M/sec  23763548027 ops        25.0%peak**
**  ****HW FP Ops / WCT        2601.948M/sec**
**  ****Computation intensity                        0.70 ops/ref**
**  ****LD & ST per TLB miss                     26564.32 ops/miss**
**  ****LD & ST per D1 miss                         33.03 ops/miss**
**  ****D1 cache hit ratio                          97.0%**
**  ****% TLB misses / cycle                         0.0%**

**USER / resid_**
**------------------------------------------------------------------------**
**  ****Time%                                       39.6%**
**  ****Time                                     9.752716**
**  ****Imb.Time                                 0.002081**
**  ****Imb.Time%                                    0.0%**
**  ****Calls                                         340**
**  ****PAPI_TLB_DM               0.115M/sec      1119418 misses**
**  ****PAPI_L1_DCA            2792.319M/sec  27232706384 ops**
**  ****PAPI_FP_OPS            3488.881M/sec  34026076279 ops**
**  ****DC_MISS                 104.718M/sec   1021283533 ops**
**  ****User time                 9.753 secs  25357072370 cycles**
**  ****Utilization rate                           100.0%**
**  ****HW FP Ops / Cycles                           1.34 ops/cycle**
**  ****HW FP Ops / User time  3488.881M/sec  34026076279 ops     33.5%peak**
**  ****HW FP Ops / WCT        3488.881M/sec**
**  ****Computation intensity                        1.25 ops/ref**
**  ****LD & ST per TLB miss                     24327.56 ops/miss**
**  ****LD & ST per D1 miss                         26.67 ops/miss**
**  ****D1 cache hit ratio                          96.2%**
**  ****% TLB misses / cycle                         0.0%**

**USER / resid_**
**------------------------------------------------------------------------**
**  ****Time%                                         38.3%**
**  ****Time                                       9.162149**
**  ****Imb.Time                                   0.006363**
**  ****Imb.Time%                                      0.1%**
**  ****Calls                                           340**
**  ****PAPI_L1_DCA             3682.405M/sec   33739250204 ops**
**  ****DC_L2_REFILL_MOESI       111.475M/sec    1021369289 ops**
**  ****DC_SYS_REFILL_MOESI        2.964M/sec      27157915 ops**
**  ****BU_L2_REQ_DC             157.164M/sec    1439982850 req**
**  ****User time                  9.162 secs   23821945786 cycles**
**  ****Utilization rate                             100.0%**
**  ****L1 Data cache misses     114.439M/sec    1048527204 misses**
**  ****LD & ST per D1 miss                           32.18 ops/miss**
**  ****D1 cache hit ratio                            96.9%**
**  ****LD & ST per D2 miss                         1242.34 ops/miss**
**  ****D2 cache hit ratio                            98.1%**
**  ****L2 cache hit ratio                            97.4%**
**  ****Memory to D1 refill        2.964M/sec      27157915 lines**
**  ****Memory to D1 bandwidth   180.914MB/sec   1738106560 bytes**
**  ****L2 to Dcache bandwidth  6803.916MB/sec  65367634496 bytes**

**USER / resid_**
**------------------------------------------------------------------------**
**  ****Time%                                         39.4%**
**  ****Time                                       9.699533**
**  ****Imb.Time                                   0.003564**
**  ****Imb.Time%                                      0.1%**
**  ****Calls                                           340**
**  ****PAPI_L1_DCA             2807.643M/sec   27232738768 ops**
**  ****DC_L2_REFILL_MOESI       105.292M/sec    1021281565 ops**
**  ****DC_SYS_REFILL_MOESI        2.366M/sec      22945693 ops**
**  ****BU_L2_REQ_DC             114.970M/sec    1115152062 req**
**  ****User time                  9.700 secs   25218702347 cycles**
**  ****Utilization rate                             100.0%**
**  ****L1 Data cache misses     107.658M/sec    1044227258 misses**
**  ****LD & ST per D1 miss                           26.08 ops/miss**
**  ****D1 cache hit ratio                            96.2%**
**  ****LD & ST per D2 miss                         1186.83 ops/miss**
**  ****D2 cache hit ratio                            97.9%**
**  ****L2 cache hit ratio                            97.8%**
**  ****Memory to D1 refill        2.366M/sec      22945693 lines**
**  ****Memory to D1 bandwidth   144.388MB/sec   1468524352 bytes**
**  ****L2 to Dcache bandwidth  6426.524MB/sec  65362020160 bytes**

## Sparse CSR MV	

- do q = 1, n_rhs
-          next_row_begin = row_start (1)
-          do i = 1, n_rows
-                row_begin      = next_row_begin
-                next_row_begin = row_start (i +1)
-                ip        = 0.0_wp
-                do k = row_begin, next_row_begin - 1
-                     ip   = ip  +  values (k) * x (col_index (k), q)
-                end do
-                y (i, q) = ip
-           end do
-  end do

*Unroll q loop x times*

*Unroll k loop x times*

*Prefetch x cachelines of *
*values and y cachelines of*
* **col_index, z iterations ahead*

*+ 3 choices of compilers*

*+ zero / one based indexing*

*+ implicit unroll options*

*Should Scream on Granite!*

## e.g. prefetch value