内存优化

从内存结构的角度来优化我们的程序。

Vector temporaries

REAL V(1024,3), S(1024), U(3)

DO I=1,1024
    S(I) = U(1)*V(I,1)
END DO

DO I=1,1024
    S(I) = S(I) + U(2)*V(I,2)
END DO

DO I=1,1024
    S(I) = S(I) + U(3)*V(I,3)
END DO

DO J=1,3
    DO I=1,1024
        V(I,J) = S(I) * U(J)
    END DO
END DO
---------------------------------------->
REAL V(1024,3), S, U(3)
    DO I=1,1024
        S = U(1)*V(I,1) + U(2)*V(I,2) + U(3)*V(I,3)
        DO J=1,3
            V(I,J) = S * U(J)
        END DO
END DO

将运算组织成近似向量的形式，编译器就很容易借助这种优势来将代码优化为向量的运算。

Hybrid

REAL V(1024,3), S(8), U(3)
DO K=1,1024,8
    DO I=0,7
        S(I) = U(1)*V(I+K,1) + U(2)*V(I+K,2) + U(3)*V(I+K,3)
        DO J=1,3
            V(I+K,J) = S(I) * U(J)
        END DO
    END DO
END DO

这种版本的代码可以increase locality

Subroutine merging

两个过程（可以是循环）有相似的迭代空间并且数据array只用来在他们之间传输数据，也就是他们之间这个array上没有其他操作。那就可以合并，合并的好处是很多的。

If two routines have the same iteration space and an data array only exists to pass data between them then consider merging

reduce cache miss

conflict code:

REAL A(1024), B(1024), C(1024), X
COMMON /DAT/ A,B,C ! Contiguous
    DO I=1,1024
        A(I) = B(I) + X*C(I)
    END DO

每一个循环里A,B,C的I位置都映射到一个set里（当然是在直接映射cache下，如果multi-way那就好很多），每次都发生三次conflict

Cache padding

REAL A(1024),B(1024),C(1024),T(8),T2(8),X
COMMON /DAT/ A,T,B,T2,C
    DO I=1,1024
        A(I) = B(I) + X*C(I)
    END DO

Padding 是常用技巧，不说了

Array extension

REAL A(1032,4), B(1024)
DO I=1,1024
    DO J=1,4
        B(I) = B(I) + A(I,J)
    END DO
END DO

这个也可以叫做padding，是A自己的不同维度的vector发生coflict，把A自己padding一下就行了

Loop re-ordering

REAL A(1024,4),T(8), B(1024)

DO J=1,4
    DO I=1,1024
        B(I) = B(I) + A(I,J)
    END DO
END DO

直接按列访问就没有A上的冲突了，B与A的冲突就依赖于T（8）的引入来消除。

Index re-ordering


REAL A(4,1024), B(1024)
DO I=1,1024
    DO J=1,4
        B(I) = B(I) + A(J,I)
    END DO
END DO

这样一来A和B的冲突也没了，但这种改变影响的是所有用到A的地方，一般需要在全局来修改，用脚本来改。

Introduce temporaries

REAL A(1024,4), B(1024),T1,T2,…
DO I=1,1024,8
    DO J=1,4
        T1 = A(I,J)
        T2 = A(I+1,J)
        …
        B(I) = B(I) + T1 +T2 …
    END DO
END DO

留一下，这里的优化感觉很有限，这句也没理解：

Only works if unroll is multiple of block size

关于写操作的优化

cache

先说一下cache：

写回，写穿透

还有：

write allocate ：写区域不在cache，就把它搞到cache里写

No write allocate：写区域不在cache，就直接修改cache以下的内存层级

Write stalls

CPU在寄存器里的值被拷贝回去之后才能继续进行操作，这就引入了stall。

引入write buffer：这是硬件的解决方案，写操作时直接写入write buffer，一般大小和一级缓存差不多，且如果比多个字长的话就可以合并这个write到一个单独的block write里去。

Array initialization

初始化array的开销会比较大，尤其在array的size比较大的时候更明显。

使用特殊硬件配合编译器指令来做初始化
将初始化操作和第一次使用的loop放到一起（很明显这会导致一些错误，因为你无法保证第一次是什么时候）

Writes and vectorisation

SIMD/Vector store operations usually work best when writing well-aligned contiguous blocks of data

这和write buffer的使用很类似，所以只需要遵循向量化的数据访存就能顺带做到适应write buffer的优化。

prefetch

预取数据到cache中

很多处理器都有这个支持，编译器也可以做一些工作

最好的情况是有一些指令可以给程序员自己使用

Write-allocate caches可能有一些清零cache line的指令

void __builtin_prefetch (const void *addr, int rw, int locality)

https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

Streams

一般预取到cache里能优化的都是连续序列的cache miss。

处理器还有一些stream buffer：

每一个都保存有active stream的地址
这个地址会随着data的load移动，指向未load的data
由一系列的连续地址的cache miss构建

如果一个loop需要比硬件支持的多的stream，那么就没有cache预取发生因为硬件流引擎将会不断地被重置到新的流上。

这个还得回来研究一下，其实没太理解它到底是啥。

Non-temporal operations

直接操作内存，忽视cache

#pragma vector nontemporal
void __builtin_nontemporal_store(T value, T *addr);
T __builtin_nontemporal_load(T *addr);

alignment

load/store指令的大小是不一样的，对齐做好的话可以一次load就取出整数个元素。

Compilers 做了什么？

内置类型和局部变量的对齐是编译器的强项。
参数指针和结构体变量编译器一般就无能为力了

如果编译器没办法确定对齐策略：

不用对齐的指令（带来低效率）
通过一些动态测试，测出程序的对齐大小

优化：

编译器提供对齐相关的指令
需要确保内存数据有一个良好的排列
malloc：只有最大的内置类型可以保证良好的对齐。64bit
有的话就不用malloc，换成其他提供的带对齐的内存分配api

Pointer aliasing

考虑一下，编译器需要：

当通过指针写，重新加载所有指针指向的值
当通过指针读，需要确保这个操作前的操作都可见。
如果有类似c++的unique指针就比较好

C语言里指针是unrestricted的，所以严重影响了性能。

防止指针重叠，可以采用类似引用计数的方法（Explicit use of local scalar temporaries）

分配在堆上的内存，一般都是比较随机的，除非一次分配很多一样的元素。 cache miss会少一些，但是因为缺少了局部性，TLB的miss会增多（缺页）。

一些动态类型比如双向链表，它里面指针占的内存也很多，存在浪费。且会带来更多的cache miss。