HPC Game Writeup
flag
mode_edit

感觉七天时间还是太长了，好累

2.B 乘一乘

用 omp 并行矩阵乘法。模仿 cutlass 的写法，对 C 矩阵进行切分，每个线程算一块。

2.C 解方程

这个“五点格式求解 Poisson 方程”感觉比较神秘，大概看了下，是在求解线性方程组。后来搜索到了 https://zhuanlan.zhihu.com/p/130808947 。发现原来是直接对着式子算就行了。

2.D 道生一

主要在优化排序部分。首先对原数组进行切分，对每部分分别使用 vqsort, 然后用手写的 merge 进行合并。

这里的并行 merge 有一些 trick. 可以用两个线程，一个线程正向 merge, 另一个反向 merge, 最终在中间相遇，可以提高并行度。此外，还有 merge path 等并行度更高的方法，由于懒，所以没写。。最后是 160⁄200 左右。

另外似乎还可以用 radix sort 之类的东西，这个确实没有研究过。

2.E 卷积

手写一下 AVX512。由于卷积核比较大，且 n = channel = 1. 因此实际上是在算 stencil。写法大概是把整个卷积核都放进 mm512 里面去。然后在图像上纵向滑动。每移动一行，就在向量寄存器中替换一行。这样做对 cache 和访存比较友好

不过最后发现，好像 IO 的时间比计算卷积的时间多得多…

template <int m, int n>
void simd_version(Mat &input, KernelMat<m, n> &kernel, Mat &res) {
  constexpr int vec_width = 512 / 8 / sizeof(float);
  __m512 kernel_vec[m][n / vec_width];
#pragma unroll(2)
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n / vec_width; ++j) {
      kernel_vec[i][j] = _mm512_load_ps(&kernel.get(i, j * vec_width));
    }
  }
  for (int qi = 0; qi < res.n; ++qi) {
    __m512 input_vec[m][n / vec_width];
#pragma unroll(2)
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n / vec_width; ++j) {
        input_vec[i][j] = _mm512_loadu_ps(&input.get(i, qi + j * vec_width));
      }
    }
    for (int pi = 0; pi < res.m; ++pi) {
      __m512 res_vec = {0};
      int offset = pi % m;
#pragma unroll(2)
      for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n / vec_width; ++j) {
          res_vec = _mm512_fmadd_ps(kernel_vec[i][j],
                                    input_vec[(i + offset) % m][j], res_vec);
        }
      }
      res.get(pi, qi) = _mm512_reduce_add_ps(res_vec);
      if (pi + 1 < res.m) {
        for (int j = 0; j < n / vec_width; ++j) {
          input_vec[offset][j] =
              _mm512_loadu_ps(&input.get(pi + m, qi + j * vec_width));
        }
      }
    }
  }
}

3.A 造 AI

这个 cifar10 是真的难搞。从网上抄了一个 resnet18, 然后开始嗯炼。发现想搞到 90+ 以上还是很困难。于是搞了一大堆 trick：

  • 数据增强：把图片随机裁切，缩放
  • 学习率调整：用了个神秘的 scheduler
  • 梯度 clip：这个不知道是干啥的…

中间还遇到了一些乌龙…比如训练集上 normalize 了，而测试集没有，于是正确率越来越低。反倒是 section2 简单了很多，随便就到 90+了。

3.B 焦散

感觉这个有意思。题意大概是，在 z=0 平面上的单位正方形上，向上投射出很多垂直与平面的光线。光线依次通过若干个和单位正方形一样大的玻璃板。每个玻璃板上有若干透镜，试求每一条光线最终打到的位置的坐标。

原始的代码逻辑是：对于每一个采样点（也就是每一条光线），遍历每一块玻璃板，遍历所有透镜，看看有没有相交的。如果存在相交，那么据此计算该透镜对光线偏折方向的贡献。将一块玻璃板所对应的贡献累加起来，就能求出光线经过玻璃板后的传播方向。

原始代码可以很轻松地改写成 GPU 代码：有几个采样点就开几个线程就可以了。但是这还可以进一步优化。通过注释部分代码。可以发现遍历所有透镜并挨个求交，是最热的部分。考虑到覆盖到一个点的透镜数量其实应该不多，因此大部分计算都浪费掉了。

我本来写了个 bvh，来试图加速这一部分，没想到开销有点大，变成了负优化。后来改成了网格预处理的方式。把玻璃板切分成网格，提前预处理每一个透镜都和哪些格子相交了，之后就可以根据点在网格中的位置，只遍历对应网格的透镜，从而减少求交的计算量。例如，如果切成了 3*3 的网格，最理想的情况下，就只需要 1⁄9 的计算量。

除此之外，还需要注意 block 的划分和任务的分配，应该让同一个 warp 的线程所处理的采样点，在空间上比较接近。我这里好像写的比较垃圾。。于是得了 180⁄200 分。

4.A 扫雷

大概是模拟了我本人玩扫雷的策略。

  • 随机点开一片区域
  • 对于边界上的点，挨个双击一下，看看有没有发现
  • 如果边界上的点用完了，就随机再开一片区域

该策略在小地图上可以拿到 90% 的分数。对于更大的地图，可以切分为多个区域，分别由不同线程处理即可。

4.B AI 算子优化

说实话这题没整明白，暴力交上去得了 80.调换了一下 gemm 的 mnk 顺序，于是变成了 101⁄150 分。101 分还卷什么，我直接开躺。

总结

我个人觉得比较有意思的是焦散这个题，确实比较大脑升级。另外没想到排序的科技居然这么多..真的是出乎意料。剩下的 fft 和 rdma 两个题确实是知识盲区..真不会

HPC C++
navigate_before navigate_next