最近假期在家，抽空又过了一遍 cs267 ， 虽然高性能计算相关知识平时工作项目中经常用到， 但在实践基础上重新学一下理论，有助于知识体系结构的系统化和条理化，感觉还是很有收获。

课程地址 https://sites.google.com/lbl.gov/cs267-spr2021

记录了 lecture 核心要点作为此 post，后续陆续更新。

update:

• 20210901～0902: Lec16~26
• 20210830: Lec9~15
• 20210829: Lec7~8
• 20210823: Lec4~6
• 20210819: Lec1~3

Lec1～3 基础知识

Lec1

Overiew

Lec2

• 寄存器简介，cache-hit and cache-miss
• 不同级别的cache速度差异
• SMP/DMP/SIMD 简介（貌似也是贯穿整个课程的）
• FMA 介绍（一次乘法+一次加法）为什么要单独提出这个概念？？answer

Example: gemm/gemv

• 提出概念 计算次数 and 访问内存次数
• 重点关系 matrix storage
• blocking or tiling for resgister 矩阵分片，用以降低读取数据的消耗

Example: conv

• 卷积核读到临时变量中，避免preload消耗. 如下，使用临时变量会更快。

res += filter[0] * signal[0] // using filter value at slow memory

float f0 = filter[0]
res += f0 * signal[0] // using temp value at fast memory(register)

Lec3

• recurrent multiply method
• strassen method 矩阵乘法算法层面的优化 O(n^3) -> O(n^2.8)

roofline model介绍:

• 计算效果既和算力大小有关，也和访存带宽有关。
• 神经网络模型推理速度，既和参数量大小有关，也和flops有关。两者共同决定了瓶颈。

Lec4～6 OpenMp

Lec4

• pthread 及各种锁，mutex的用法。知乎上一个讲的不错的文章，可以用来作补充材料。https://zhuanlan.zhihu.com/p/112297714
• OpenMp 简介 and usage
• SMP-share memory program 的实现
• False Sharing 介绍和解决办法

False Sharing 是很多情况下并行不起作用的根源:

L1 cache line 有大小（64bytes）。在同一个cache line的不同变量不是独立的，系统对整个cacheline有标签。 所以必行计算时，如果不同的变量位于同一个 cache line内，会发生数据竞争。 帮助理解的文章：https://zhuanlan.zhihu.com/p/85984250

这章结合数值积分的例子，包括了大量 OpenMp 的例子。需要在实践中多练习， 才能逐渐掌握里面的各种 trick

Lec5

一些并行计算的例子例子简介

Lec6

结合 n-body 问题和 PDE 问题具体介绍。

感觉上，Jim Demmel 好像更偏传统工程学一些，他的课程部分里没有讲和神经网络相关的部分。

Lec7～Lec8 GPU and cuda

Cpu和gpu架构上的区别 gpu的基本简介

Lec7

Cpu和gpu架构上的区别 gpu的基本简介

Lec8

“scans” method and two example:

• Data parallize radius sort
• List Ranking with Pointer Doubling

application of SIMD

why simd so hast?

Lec9~Lec10 MPI

Lec9 and 10

• 数据分布体系（没有看懂）
• MPI 的基本使用方法

difference from openMP and MPI

• OpenMP: 线程级（并行粒度），共享存储，隐式（数据分配方式），可扩展性差
• MPI：进程级，分布式存储，显式，可扩展性好。

OpenMP采用共享存储，意味着它只适应于SMP, DSM机器，不适合于集群。

MPI虽适合于各种机器，但它的编程模型复杂：

• 需要分析及划分应用程序问题，并将问题映射到分布式进程集合
• 需要解决通信延迟大和负载不平衡两个主要问题
• 调试MPI程序麻烦
• MPI程序可靠性差，一个进程出问题，整个程序将错误；

（好像平时用 openMP 的时候占大多数）

Lec11～Lec12 other-library such as UPC++

lec11

UPC++

• An Asynchronous RMA/RPC Library for Distributed C++ Applications

lec12

some other library of parallel computing

提了一下稀疏矩阵乘法，没太展开。

Lec13～Lec15 Gemm

lec13

• gemm

lec14

• some other function such as gussian elimination and LU
• also related about gpu

lec15

• structure grids (Possion equation)

回去一看，果然讲课者是 Jim Demmel ， 和之前学 lec3～4 的感觉如出一辙。

Lec16~Lec17

机器学习中的并行计算：更多是关于机器学习中常用方法的介绍，有深度的内容不多

Lec18 稀疏矩阵与并行处理

• 稀疏矩阵的存储方式
• 注意稀疏矩阵的某些特点，例如稀疏矩阵可以分成一些子块之类（Register blocking）
• reordering is important，某些graph，可以对应不同的稀疏矩阵形式。

Lec19～25 application

• Lec19 parallel fft
• Lec20 图算法
• Lec21 云计算
  • map-reduce的基本思想，对分发任务的校验
• Lec22 work-treal
• Lec23 nbody问题
• Lec24 并行排序（值得多看一下？）
• Lec25 Cosmology
• Lec26 Biology

后面几章更多都是介绍性内容，浅尝辄止科普为主。

总结：hpc 感觉更多是一门 “经验科学”，真正很硬核的理论有但不多，更多的是一些实际处理问题的方法、思路和技巧。

与此同时，hpc 和体系结构和编译原理联系比较紧密。对这些知识的掌握有助于写出更快更好的程序来。