变态家族

用70年代后期的Multigrid方法解决泊松问题， 一个未知数需要三十个操作， 对于更一般的椭圆方程问题， 一个未知需要一百个左右的操作， 对于一个现在的CPU，一秒钟可以有1Gflop， 如果一切完美， 只考虑CPU频率， 我们可以在一秒钟内解决1000万个未知， 需要O（100）Mbyte的内存。 但是实际上只要多于一万到十万个未知， 你的代码就会崩溃， 需要一个小时左右， 需要不可计数的内存。

问题不在于处理数据， 而在于转移数据。  访问数据有两个指标， 延迟和带宽。 延迟–读写内存的时间太长， CPU内的数据访问需要0.5ns， 而内存需要50ns。 带宽–每秒可以读写的byte数， 对于1GFLOP的CPU需要24Gbyte/秒的带宽。 而现在CPU所拥有的峰值带宽是5Gbyte/s， 而实际应用上远远达不到这个数字。 解决的办法除了可以提高带宽无法提高延迟的Interleaving以外， 就是两方面都可以提高的cache， 通常现在会有两到三层的cache， 但是只有在数据在本地的cache的时候才能用。 载入cache的原则有根据时间的还有根据空间的， 每次载入的是一个cache line， 通常是32-128byte， 现在最长时1kbyte。  这里需要了解的是替换的策略， 关联， cache line的大小， hit ratio和miss ratio的概念。 这是一些现在电脑的cache数据。 Lx指的是x级的cache， 比如说L1就是一级的cache。

• IBM Power 3:
    • L1 = 64 KB, 128-way set associative
     L2 = 4 MB, direct mapped, line size = 128, write back
• Compaq EV6 (Alpha 21264):
    • L1 = 64 KB, 2-way associative, line size= 32
    • L2 = 4 MB (or larger), direct mapped, line size = 64
• HP PA: no L2
    • PA8500, PA8600: L1 = 1.5 MB, PA8700: L1 = 2.25 MB
• AMD Athlon: L1 = 64 KB, L2 = 256 KB
• Intel Pentium 4: L1 = 8 KB, L2 = 256 KB
• Intel Itanium:
    • L1 = 16 KB, 4-way associative
    • L2 = 96 KB
        6-way associative, L3 = off chip, size varies

• 选择最好的算法。这是废话， 不过意思是告诉你， 破算法没有什么优化的价值。要优化就要优化MG这样优秀的算法。 

• 使用效率高的库。

• 使好合适的编译器选项。

• 子程序水平的评估： 编译器在开始和结束的时候插入timing calls， 粗略的评估， 评估的代价高。

• 时钟水平的评估： 定时的执行OS的中断指令， 监视代码的存放位置， 更详细的评估， 代价仍然很高。

• 基于硬件的评估： 最流行的方法。

工具
PCL =Performance Counter Library, 跨平台，在代码内或代码外使用。
PAPI =Peformance API，跨平台， 高级和低级的接口。
DCPI ：基于Alpha的Compaq Tru64 Unix

例子： 代码外
 PCL Hardware performance monitor: hpm
% hpm –-events PCL_CYCLES, PCL_MFLOPS ./mg
hpm: elapsed time: 5.172 s
hpm: counter 0 : 2564941490 PCL_CYCLES
hpm: counter 1 : 19.635955 PCL_MFLOPS

或者是代码内 ……

可见要查看cache的miss ratio， 就必须要用第三种方法了。

• Loop unrolling
• Fused Multiply-Add (FMA) instructions
• Exposing instruction-level parallelism (ILP)
• Software pipelining (again: exploit ILP)
• Aliasing
• Special functions
• Eliminating overheads

Loop unrolling
更少的判断/跳转指令， （loop更大， 代价就越小）
更少的load指令

–让loop更大，比如i：n步进为1的循环，改成i：n步进为4的循环。
–flop-to-load-ration
–重命名， Fortran不允许， c可以。 F更快。c可以使用编译选项 -noalias或c的关键字restrict
–特别的函数，比如除， 开根号， 指数，对数， 三角运算代价更高， 会用掉几个周期。
–避免在最内层的循环使用if， 但是不存在这样的技术。 不要在判断时用到上面说的那些代价高的函数。
–循环的代价：cpu需要释放一定的寄存器， 比如说循环寄存器，地址寄存器来开始循环， 所以短的循环相对代价更高。 如果n>m, 这样的循环
    do i=1，n
    do j=1，m
    就没有下面这个循环有效率
    do i=1，m
    do j=1，n
– call子函数的代价。子函数对程序的良好结构很重要， 但是呼叫的代价很高， 大概是100个cycles。 传递值参数需要复制数据，如果使用不当代价会非常高。 但是使用指针可能会不安全， 可以在使用时用const的声明。 通常， 在很小的循环中， 不应该呼叫子函数。在c中使用incline声明， 使用宏。

for it= 1 to numIter/B do
// Special handling: rows 1, …, 2B-1
// Not shown here …
// Inner part of the 2D grid
for k= 2*B to n- 1 do
for i= k to k- 2*B+1 by ?2 do
for j= 1+(k+1)%2 to n- 1 by 2 do
relax(u(j,i))
relax(u(j,i- 1))
end for
end for
end for
// Special handling: rows n-2B+1, …, n-1
// Not shown here …
end for