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 等并行度更高的方法,由于懒,所以没写。。最后是 160200 左右。

另外似乎还可以用 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 的网格,最理想的情况下,就只需要 19 的计算量。

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

4.A 扫雷

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

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

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

4.B AI 算子优化

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

总结

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

navigate_next