# Presentation: 849130

## Optimization for the Cray XT4TMMPP Supercomputer

**John M. Levesque**
**March, 2007**

## `

**The Cray XT4 System**

## Recipe for a good MPP

- Select Best Microprocessor
- Surround it with a balanced or “bandwidth rich” environment
- “Scale” the System
- Eliminate Operating System Interference (OS Jitter)
- Design in Reliability and Resiliency
- Provide Scaleable System Management
- Provide Scalable I/O
- Provide Scalable Programming and Performance Tools
- System Service Life (provide an upgrade path)

**Notes:**
The Recipe for a good MPP hasn’t changed since the days of the Cray T3D.

The first step is to select the best microprocessor.  Based on a number of criteria, we selected the AMD Opteron processor.

Step 2 is to place this processor in a bandwidth-rich environment.  This means low latency to local and remote memory, good bytes / flop ratios on the local node and between nodes.

Note that Step 1 and 2 can also be largely accomplished on a cluster by selecting the Opteron processor and a high-end cluster interconnect.  Step 3 is the real “special sauce” of an MPP computer.  It can be summed up as simply “absolute attention to scaling detail”.  This requires a complete focus on the mission of scaling computation, something that typically doesn’t come through in a commodity cluster system.

## AMD Opteron:  Why we selected it

**PCI-X****Bridge**

- 6.4 GB/sec

**HT**

**HT**

**Direct attached local memory for leading bandwidth and latency**
**HyperTransport can be directly attached to Cray SeaStar2 interconnect**
**Simple two-chip design saves power and complexity**

- PCI-X Slot

- PCI-X Slot

- PCI-X Slot

**Notes:**
This slide looks at the generic Opteron architecture in detail.

Note that the Northbridge chip is gone, and functionality has been placed on the Opteron Die itself.  In particular, the memory controller for DDR is there.  Note that memory latency is as low as 58 nanoseconds with a DRAM page hit!  This translates into real performance advantages from the integrated memory controller.

Also note that upgraded Opterons may come with faster memory controllers.  That is, you don’t need a new Northbridge to run faster DDR memory components but these can be upgraded with the processor.

The high-speed interface off the chip is not proprietary, but an open standard called HyperTransport.  Intellectual Property is available on the market for this technology.  It would allow, for example, a bridge chip designer to pick up an HT core and quickly make a chip that would talk to Opteron.

In the Cray case, we could get a HT core and talk at high speed to our router chip.

Note that HT uses Low Voltage Differential Signaling, running a small number of lines at high frequency.  This type of signaling technology typically only can be implemented in the traces of a printed circuit board.  Thus, this tight coupling requires a purpose-built motherboard and we see it as a clear separation from cluster technology which relies on commodity mother boards and commodity off-board connections such as PCI-X.

## Recipe for a good MPP

- Select Best Microprocessor
- Surround it with a balanced or “bandwidth rich” environment
- “Scale” the System
- Eliminate Operating System Interference (OS Jitter)
- Design in Reliability and Resiliency
- Provide Scalable System Management
- Provide Scalable I/O
- Provide Scalable Programming and Performance Tools
- System Service Life (provide an upgrade path)

**Notes:**
The Recipe for a good MPP hasn’t changed since the days of the Cray T3D.

The first step is to select the best microprocessor.  Based on a number of criteria, we selected the AMD Opteron processor.

Step 2 is to place this processor in a bandwidth-rich environment.  This means low latency to local and remote memory, good bytes / flop ratios on the local node and between nodes.

Note that Step 1 and 2 can also be largely accomplished on a cluster by selecting the Opteron processor and a high-end cluster interconnect.  Step 3 is the real “special sauce” of an MPP computer.  It can be summed up as simply “absolute attention to scaling detail”.  This requires a complete focus on the mission of scaling computation, something that typically doesn’t come through in a commodity cluster system.

## The Cray XT4 Processing Element:Providing a bandwidth-rich environment

- The Cray XT4 Processing Element:Providing a bandwidth-rich environment

## Recipe for a good MPP

- Select Best Microprocessor
- Surround it with a balanced or “bandwidth rich” environment
- “Scale” the System
- Eliminate Operating System Interference (OS Jitter)
- Design in Reliability and Resiliency
- Provide Scalable System Management
- Provide Scalable I/O
- Provide Scalable Programming and Performance Tools
- System Service Life (provide an upgrade path)

**Notes:**
The Recipe for a good MPP hasn’t changed since the days of the Cray T3D.

The first step is to select the best microprocessor.  Based on a number of criteria, we selected the AMD Opteron processor.

Step 2 is to place this processor in a bandwidth-rich environment.  This means low latency to local and remote memory, good bytes / flop ratios on the local node and between nodes.

Note that Step 1 and 2 can also be largely accomplished on a cluster by selecting the Opteron processor and a high-end cluster interconnect.  Step 3 is the real “special sauce” of an MPP computer.  It can be summed up as simply “absolute attention to scaling detail”.  This requires a complete focus on the mission of scaling computation, something that typically doesn’t come through in a commodity cluster system.

## Scalable Software Architecture:  UNICOS/lc“Primum non nocere”

- Microkernel on Compute PEs, full featured Linux on Service PEs.
- Service PEs specialize by function
- Software Architecture eliminates OS “Jitter”
- Software Architecture enables reproducible run times
- Large machines boot in under 30 minutes, including filesystem

**Service Partition**

***Specialized Linux nodes***

**Compute PE  **
**Login PE  **
**Network PE  **
**System PE  **
**I/O PE  **

**Notes:**
The Cray XT3 software architecture introduces two innovations. 
Specialize nodes dedicate Computer Processing Elements to application processing,  while a series of Service PEs are optimized to handle networking, login, and I/O. An MPP optimized operating system provides Linux environment for system administration and programmability,  while using a light weight kernel on compute nodes for high efficiency.  Both of these innovations contribute to the Cray XT3’s highly scalable operating environment.  

The Cray XT3 operating system UNICOS/lc is designed to run large complex applications and scale efficiently to 30,000 processors. As in previous generation MPP systems from Cray, UNICOS/lc consists of two primary components - a microkernel for compute PEs and a full-featured operating system for the service PEs. This proven microkernel architecture ensures reproducible run-times for MPP jobs, supports fine-granularity processing at scale, and ensures high performance, low latency MPI and SHMEM communication.

Service PEs run a full Linux kernel. Service PEs can be configured to perform as login, I/O, system, or network PEs. 
Login PEs offer the programmer the look and feel of a Linux-based environment with full access to the programming environment and all of the standard Linux utilities, commands, and shells to make program development both easy and portable. Network PEs provide high-speed connectivity with other systems.   I/O PEs provide scalable connectivity to the global, parallel file system. System PEs are used to run global system services such as the system database. System services can be scaled to fit the size of the system or the specific needs of the users.

The I/O subsystem is  based on Lustre and scalable to 100 GB/sec bandwidth.  All files have full visibility and connectivity into the file system over the high speed interconnect. Red Storm, for example, can dump its 10 TB memory to disk in under two minutes.

## This is the real reason the XT4 will scale to a Petaflop

- Download P-SNAP from the web and try it on your system

## Relating Scalability and Cost Effectiveness of Red Storm Architecture

***We believe the Cray XT3 will have the same characteristics; More cost effective than clusters somewhere between 64 and 256 MPI tasks***

*Source: Sandia National Labs*

## Opteron Speeds and Feeds

- Core
- 2.6Ghz clock frequency
- SSE SIMD FPU (2flops/cycle = 5.2GF peak)
- Cache Hierarchy
- L1 Dcache/Icache: 64k/core
- L2 D/I cache: 1M/core
- 12 HW stream prefetch
- SW Prefetch and loads to L1
- Evictions and HW prefetch to L2
- Memory
- Dual Channel DDR2
- 10GB/s peak @ 667MHz
- 8GB/s nominal STREAMs

**TLB**
**Small pages**
**4k pages**
**512 entries**
**covers 2M memory.**
**Large pages:  **
**2MB pages**
**8 entries**
**covers 16MB memory**
**2-pages used by OS (so really only 6 entries covering 12MB)**
**Shared Resources**
**HyperTransport (to Seastar)**
**Memory controller**
**Otherwise, no other shared resources!!!**

## Performance = F( Cache Utilization )

## AMD Opteron Processor

- 36 entry FPU instruction scheduler
- 64-bit/80-bit FP Realized throughput (1 Mul + 1 Add)/cycle: 1.9 FLOPs/cycle
- 32-bit FP Realized throughput (2 Mul + 2 Add)/cycle: 3.4+ FLOPs/cycle

**Notes:**
L2 data and Instruction cache in one??

L1 cache
data and instruction caches are separate
Each are 2-way set associative
Bandwidth is 2 x 64 Bits per clock, i.e. Either 2 loads, 1 load 1 store, or 2 stores

L2 cache
Is an „exclusive“ cache, i.e. serves as a „victim“ cache when L1 cache lines are replaced, and receives a copy on stores

Cache line size is 64 Bytes for both
Is 16-way associative and holds both data and instructions
Bandwidth is 64 Bits per clock

## Simplified memory hierachy on the AMD Opteron

- ......

- registers

- L1 data cache

- L2 cache

- 16 SSE2 128-bit registers
-  16 64 bit registers

- 2 x 8 Bytes per clock, i.e. Either 2 loads, 1 load 1 store, or 2 stores     (38 GB/s on 2.4 Ghz)

- Main memory

-  64 Byte cache line
-  complete data cache lines are loaded from main
-    memory, if not in L2 cache
-  if L1 data cache needs to be refilled, then
-    storing back to L2 cache
-  64 Byte cache line
-  write back cache: data offloaded  from L1 data
-    cache are stored here first
-    until they are flushed out to main memory

- 16 Bytes wide data bus => 6.4 GB/s for DDR400

- 8 Bytes per clock

## Cache Visualization

- Level 1 Cache

- Level 1 Cache
- 	65536 B
- 	1024 Lines
- 	8192 8B Ws
- 	16384 4B Ws
- 	2 way Assoc
- Associativity Class
- 	32768 B
- 	512 Lines
- 	4096 8B Ws
- 	8192 4B Ws

- Width = 32768 Bytes

- MEMORY

- 64*64*8 = 32768 B

## Consider the following example

- Level 1 Cache

- Level 1 Cache
- 	65536 B
- 	1024 Lines
- 	8192 8B Ws
- 	16384 4B Ws
- 	2 way Assoc
- Associativity Class
- 	32768 B
- 	512 Lines
- 	4096 8B Ws
- 	8192 4B Ws

- Width = 32768 Bytes

- MEMORY

- 64*64*8 = 32768 B

- Level 1 Cache

- Level 1 Cache
- 	65536 B
- 	1024 Lines
- 	8192 8B Ws
- 	16384 4B Ws
- 	2 way Assoc
- Associativity Class
- 	32768 B
- 	512 Lines
- 	4096 8B Ws
- 	8192 4B Ws

- Width = 32768 Bytes

- MEMORY

- 64*64*8 = 32768 B

- Level 1 Cache

- Level 1 Cache
- 	65536 B
- 	1024 Lines
- 	8192 8B Ws
- 	16384 4B Ws
- 	2 way Assoc
- Associativity Class
- 	32768 B
- 	512 Lines
- 	4096 8B Ws
- 	8192 4B Ws

- Width = 32768 Bytes

- MEMORY

- 64*64*8 = 32768 B

## Must be a better Way

- Level 1 Cache

- Level 1 Cache
- 	65536 B
- 	1024 Lines
- 	8192 8B Ws
- 	16384 4B Ws
- 	2 way Assoc
- Associativity Class
- 	32768 B
- 	512 Lines
- 	4096 8B Ws
- 	8192 4B Ws

- Width = 32768 Bytes

- MEMORY

- 64*64*8 = 32768 B

## Bad Cache Alignment

-  **Time%                                       0.2%**
**  ****Time                                    0.000003**
**  ****Calls                                          1**
**  ****PAPI_L1_DCA              455.433M/sec       1367 ops**
**  ****DC_L2_REFILL_MOESI        49.641M/sec        149 ops**
**  ****DC_SYS_REFILL_MOESI        0.666M/sec          2 ops**
**  ****BU_L2_REQ_DC              74.628M/sec        224 req**
**  ****User time                  0.000 secs       7804 cycles**
**  ****Utilization rate                           97.9%**
**  ****L1 Data cache misses      50.308M/sec        151 misses**
**  ****LD & ST per D1 miss                         9.05 ops/miss**
**  ****D1 cache hit ratio                         89.0%**
**  ****LD & ST per D2 miss                       683.50 ops/miss**
**  ****D2 cache hit ratio                         99.1%**
**  ****L2 cache hit ratio                         98.7%**
**  ****Memory to D1 refill        0.666M/sec          2 lines**
**  ****Memory to D1 bandwidth    40.669MB/sec       128 bytes**
**  ****L2 to Dcache bandwidth  3029.859MB/sec      9536 bytes**

## Good Cache Alignment

**  ****Time%                                       0.1%**
**  ****Time                                    0.000002**
**  ****Calls                                          1**
**  ****PAPI_L1_DCA              689.986M/sec       1333 ops**
**  ****DC_L2_REFILL_MOESI        33.645M/sec         65 ops**
**  ****DC_SYS_REFILL_MOESI                            0 ops**
**  ****BU_L2_REQ_DC              34.163M/sec         66 req**
**  ****User time                  0.000 secs       5023 cycles**
**  ****Utilization rate                           95.1%**
**  ****L1 Data cache misses      33.645M/sec         65 misses**
**  ****LD & ST per D1 miss                        20.51 ops/miss**
**  ****D1 cache hit ratio                         95.1%**
**  ****LD & ST per D2 miss                      1333.00 ops/miss**
**  ****D2 cache hit ratio                        100.0%**
**  ****L2 cache hit ratio                        100.0%**
**  ****Memory to D1 refill                            0 lines**
**  ****Memory to D1 bandwidth                         0 bytes**
**  ****L2 to Dcache bandwidth  2053.542MB/sec      4160 bytes**

## C     3 OPERATIONS - 5 OPERANDS     RATIO = 3/5            DO 41023 I=1, N       A(I) = B(I) * C(I) + D(I) * E(I)41023 CONTINUE

## C     DIMENSION A(128,N)      DO 41080  I = 1,N       A( 1,I) = C1*A(13,I) + C2* A(12,I) + C3*A(11,I) +     *           C4*A(10,I) + C5* A( 9,I) + C6*A( 8,I) +     *           C7*A( 7,I) + C0*(A( 5,I) + A( 6,I) )  + A( 3,I)41080 CONTINUE

## C     DIMENSION B(13,N)      DO 41081 I = 1,N       B( 1,I) = C1*B(13,I) + C2* B(12,I) + C3*B(11,I) +     *           C4*B(10,I) + C5* B( 9,I) + C6*B( 8,I) +     *           C7*B( 7,I) + C0*(B( 5,I) + B( 6,I) )  + B( 3,I)41081 CONTINUE

## dimension a(1000,1000,4,4),b(1000,1000,4,4)real*8 a,b,c,dclock,dtimb=rand();a=rand()a=0ka = 999ke = 1ja = 1je = 1000dtim = dclock()ia = 1ie = 4      DO 41090 K = KA, KE, -1        DO 41090 J = JA, JE          DO 41090 I = IA, IE            A(K,J,I,3) = A(K,J,I,3) - B(J,K,I,1)*A(K+1,J,I,1)&         - B(J,K,I,2)*A(K+1,J,I,2) - B(J,K,I,3)*A(K+1,J,I,3)&         - B(J,K,I,4)*A(K+1,J,I,4) - B(J,K,I,4)*A(K-1,J,I,4)41090 CONTINUEdtim = dclock()-dtimprint*,'     MFLOP/SEC',999*1000*4*10/dtim/1e6end

## Using small pages

- USER / MAIN_
- ------------------------------------------------------------------------
-   Time%                                    100.0%
-   Time                                   0.679214
-   Calls                                         1
-   PAPI_TLB_DM             24.426M/sec    16590471 misses
-   PAPI_L1_DCA            145.216M/sec    98632806 ops
-   PAPI_FP_OPS             58.930M/sec    40026496 ops
-   DC_MISS                 32.376M/sec    21990324 ops
-   User time                0.679 secs  1765961050 cycles
-   Utilization rate                         100.0%
-   HW FP Ops / Cycles                         0.02 ops/cycle
-   HW FP Ops / User time   58.930M/sec    40026496 ops        1.1%peak
-   HW FP Ops / WCT         58.930M/sec
-   Computation intensity                      0.41 ops/ref
-   LD & ST per TLB miss                       5.95 ops/miss
-   LD & ST per D1 miss                        4.49 ops/miss
-   D1 cache hit ratio                        77.7%
-   % TLB misses / cycle                       0.9%

## First Restructuring 

**dimension a(4,4,1000,1000),b(4,4,1000,1000)**
**real*8 a,b,c,dclock,dtim**
**b=rand();a=rand()**
**a=0**
**ka = 999**
**ke = 1**
**ja = 1**
**je = 1000**
**dtim = dclock()**
**ia = 1**
**ie = 4**
**      ****DO 41090 K = KA, KE, -1**
**        ****DO 41090 J = JA, JE**
**          ****DO 41090 I = IA, IE**
**            ****A(I,3,K,J) = A(I,3,K,J) - B(I,1,J,K)*A(I,1,K+1,J)&**
**         ****- B(I,2,J,K)*A(I,2,K+1,J) - B(I,3,J,K)*A(I,3,K+1,J)&**
**         ****- B(I,4,J,K)*A(I,4,K+1,J) - B(I,4,J,K)*A(I,4,K-1,J)**
**41090 CONTINUE**
**dtim = dclock()-dtim**
**print*,'     MFLOP/SEC',999*1000*4*10/dtim/1e6**
**end**

## Using Small Pages

- USER / MAIN_
- ------------------------------------------------------------------------
-   Time%                                    99.8%
-   Time                                  0.219233
-   Calls                                        1
-   PAPI_TLB_DM              4.587M/sec    1005738 misses
-   PAPI_L1_DCA            426.675M/sec   93541922 ops
-   PAPI_FP_OPS            182.305M/sec   39967607 ops
-   DC_MISS                 45.597M/sec    9996488 ops
-   User time                0.219 secs  570010039 cycles
-   Utilization rate                        100.0%
-   HW FP Ops / Cycles                        0.07 ops/cycle
-   HW FP Ops / User time  182.305M/sec   39967607 ops        3.5%peak
-   HW FP Ops / WCT        182.305M/sec
-   Computation intensity                     0.43 ops/ref
-   LD & ST per TLB miss                     93.01 ops/miss
-   LD & ST per D1 miss                       9.36 ops/miss
-   D1 cache hit ratio                       89.3%
-   % TLB misses / cycle                      0.2%

## Restructuring 2

**dimension a(1000,1000,4,4),b(1000,1000,4,4)**
**real*8 a,b,c,dclock,dtim,scalar,c0,c1,c2,c3,c4,c5,c6**
**b=rand();a=rand()**
**a=0**
**ka = 999**
**ke = 1**
**ja = 1**
**je = 1000**
**l = 8**
**dtim = dclock()**
**ia = 1**
**ie = 4**
**          ****DO 41090 I = IA, IE**
**        ****DO 41090 J = JA, JE**
**      ****DO 41090 K = KA, KE, -1**
**            ****A(K,J,I,3) = A(K,J,I,3) - B(K,J,I,1)*A(K+1,J,I,1)&**
**         ****- B(K,J,I,2)*A(K+1,J,I,2) - B(K,J,I,3)*A(K+1,J,I,3)&**
**         ****- B(K,J,I,4)*A(K+1,J,I,4) - B(K,J,I,4)*A(K-1,J,I,4)**
**41090 CONTINUE**
**dtim = dclock()-dtim**
**print*,'     MFLOP/SEC',999*1000*4*10/dtim/1e6**
**end**

## Small Pages

- USER / MAIN_
- ------------------------------------------------------------------------
-   Time%                                    99.8%
-   Time                                  0.159259
-   Calls                                        1
-   PAPI_TLB_DM              0.785M/sec     125077 misses
-   PAPI_L1_DCA            611.597M/sec   97403340 ops
-   PAPI_FP_OPS            251.382M/sec   40035233 ops
-   DC_MISS                 50.323M/sec    8014507 ops
-   User time                0.159 secs  414077811 cycles
-   Utilization rate                        100.0%
-   HW FP Ops / Cycles                        0.10 ops/cycle
-   HW FP Ops / User time  251.382M/sec   40035233 ops        4.8%peak
-   HW FP Ops / WCT        251.382M/sec
-   Computation intensity                     0.41 ops/ref
-   LD & ST per TLB miss                    778.75 ops/miss
-   LD & ST per D1 miss                      12.15 ops/miss
-   D1 cache hit ratio                       91.8%
-   % TLB misses / cycle                      0.0%
- ========================================================================

## Restructuring 3

**dimension a(1000,1000,4,4),b(1000,1000,4,4)**
**real*8 a,b,c,dclock,dtim**
**b=rand();a=rand()**
**a=0**
**ka = 999**
**ke = 1**
**ja = 1**
**je = 1000**
**dtim = dclock()**
**ia = 1**
**ie = 4**
**          ****DO 41090 I = IA, IE**
**      ****DO 41090 K = KA, KE, -1**
**        ****DO 41090 J = JA, JE**
**            ****A(J,K,I,3) = A(J,K,I,3) - B(J,K,I,1)*A(J,K+1,I,1)&**
**         ****- B(J,K,I,2)*A(J,K+1,I,2) - B(J,K,I,3)*A(J,K+1,I,3)&**
**         ****- B(J,K,I,4)*A(J,K+1,I,4) - B(J,K,I,4)*A(J,K-1,I,4)**
**41090 CONTINUE**
**dtim = dclock()-dtim**
**print*,'     MFLOP/SEC',999*1000*4*10/dtim/1e6**
**end**

## Small Pages

**USER / MAIN_**
**------------------------------------------------------------------------**
**  ****Time%                                    99.8%**
**  ****Time                                  0.154248**
**  ****Calls                                        1**
**  ****PAPI_TLB_DM              0.831M/sec     128183 misses**
**  ****PAPI_L1_DCA            666.774M/sec  102849427 ops**
**  ****PAPI_FP_OPS            259.572M/sec   40038736 ops**
**  ****DC_MISS                 58.415M/sec    9010497 ops**
**  ****User time                0.154 secs  401047898 cycles**
**  ****Utilization rate                        100.0%**
**  ****HW FP Ops / Cycles                        0.10 ops/cycle**
**  ****HW FP Ops / User time  259.572M/sec   40038736 ops        5.0%peak**
**  ****HW FP Ops / WCT        259.572M/sec**
**  ****Computation intensity                     0.39 ops/ref**
**  ****LD & ST per TLB miss                    802.36 ops/miss**
**  ****LD & ST per D1 miss                      11.41 ops/miss**
**  ****D1 cache hit ratio                       91.2%**
**  ****% TLB misses / cycle                      0.0%**
**========================================================================**

##  DO 44050 I = 1, N       DO 44050 J = 1, N        A(I,J) = 0.0        DO 44050 K = 1, N         A(I,J) = A(I,J) + B(I,K) * C(K,J)44050 CONTINUE

##        DO 44051 J = 1, N       DO 44051 I = 1, N        A(I,J) = 0.044051 CONTINUE      DO 44052 K = 1, N       DO 44052 J = 1, N        DO 44052 I = 1, N         A(I,J) = A(I,J) + B(I,K) * C(K,J)44052 CONTINUE

##         DO 44060 I = 1, N       A(I) = 0.0       DO 44060 J = 1, I        A(I) = A(I) + B(I,J) * C(J,I)44060 CONTINUE

##              DO 44061 I = 1, N       A(I) = 0.044061 CONTINUE      DO 44062 J = 1, N       DO 44062 I = J, N        A(I) = A(I) + B(I,J) * C(J,I)44062 CONTINUE

## C      THE ORIGINAL      DO 46011 J = 1, 4       DO 46010 I = 1, N        C(J,I)=0.046010 CONTINUE        DO 46011 K = 1,4        DO 46011 I = 1,N         C(J,I) = C(J,I) + A(J,K) * B(K,I)46011 CONTINUE

## C       THE RESTRUCTURED      DO 46012 I = 1, N       C(1,I) = A(1,1) * B(1,I) + A(1,2) * B(2,I)     *        + A(1,3) * B(3,I) + A(1,4) * B(4,I)       C(2,I) = A(2,1) * B(1,I) + A(2,2) * B(2,I)     *        + A(2,3) * B(3,I) + A(2,4) * B(4,I)       C(3,I) = A(3,1) * B(1,I) + A(3,2) * B(2,I)     *        + A(3,3) * B(3,I) + A(3,4) * B(4,I)       C(4,I) = A(4,1) * B(1,I) + A(4,2) * B(2,I)     *        + A(4,3) * B(3,I) + A(4,4) * B(4,I)46012 CONTINUE

- OPT have non-power of two as first dimension

##        DO 46030 J  = 1, N       DO 46030 I = 1, N        A(I,J) = 0.46030 CONTINUE      DO 46031   K = 1, N       DO 46031  J = 1, N        DO 46031 I = 1, N         A(I,J) = A(I,J) + B(I,K) * C(K,J)46031 CONTINUE

## C       THE RESTRUCTURED      DO 46032  J = 1, N       DO 46032 I = 1, N        A(I,J)=0.46032 CONTINUEC      DO 46033   K = 1, N-5, 6       DO 46033  J = 1, N        DO 46033 I = 1, N         A(I,J) = A(I,J) + B(I,K  ) * C(K  ,J)     *                   + B(I,K+1) * C(K+1,J)     *                   + B(I,K+2) * C(K+2,J)     *                   + B(I,K+3) * C(K+3,J)     *                   + B(I,K+4) * C(K+4,J)     *                   + B(I,K+5) * C(K+5,J)46033 CONTINUEC      DO 46034  KK = K, N       DO 46034  J = 1, N        DO 46034 I = 1, N         A(I,J) = A(I,J) + B(I,KK) * C(KK ,J)46034 CONTINUE

- USER / #1.inner product
- ------------------------------------------------------------------------
-   Time%                                       73.0%
-   Time                                     0.226803
-   Calls                                           1
-   PAPI_TLB_DM                  22 /sec            5 misses
-   PAPI_L1_DCA             947.759M/sec    214953166 ops
-   PAPI_FP_OPS            1495.678M/sec    339222112 ops
-   DC_MISS                 177.035M/sec     40151838 ops
-   User time                 0.227 secs    589683955 cycles
-   Utilization rate                           100.0%
-   HW FP Ops / Cycles                           0.58 ops/cycle
-   HW FP Ops / User time  1495.678M/sec    339222112 ops        28.8%peak
-   HW FP Ops / WCT        1495.671M/sec
-   Computation intensity                        1.58 ops/ref
-   LD & ST per TLB miss                  42990633.20 ops/miss
-   LD & ST per D1 miss                          5.35 ops/miss
-   D1 cache hit ratio                          81.3%
-   % TLB misses / cycle                         0.0%

- USER / #2.unrolled product
- ------------------------------------------------------------------------
-   Time%                                       17.9%
-   Time                                     0.055725
-   Calls                                           1
-   PAPI_TLB_DM                  71 /sec            4 misses
-   PAPI_L1_DCA            1967.956M/sec    109667050 ops
-   PAPI_FP_OPS            3062.605M/sec    170667843 ops
-   DC_MISS                  25.496M/sec      1420773 ops
-   User time                 0.056 secs    144888568 cycles
-   Utilization rate                           100.0%
-   HW FP Ops / Cycles                           1.18 ops/cycle
-   HW FP Ops / User time  3062.605M/sec    170667843 ops        58.9%peak
-   HW FP Ops / WCT        3062.605M/sec
-   Computation intensity                        1.56 ops/ref
-   LD & ST per TLB miss                  27416762.50 ops/miss
-   LD & ST per D1 miss                         77.19 ops/miss
-   D1 cache hit ratio                          98.7%
-   % TLB misses / cycle                         0.0%

## 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