HPCGame 1st 记录

第一次参加HPCGame，一共14道题，比较滑水，抽时间做了8道题，拿了个三等奖，记录一下。

F. 高性能数据校验

考察SHA512算法的优化。由于SHA512的每一块的计算都依赖上一块的结果，所以可以并行的部分其实不多，只能并行当前部分的计算和下一部分的读入。

代码细节：

• 使用mmap按需读入数据，与上一个块的计算并行。
• 使用MPI模型传递计算完的数据。

H. 矩阵乘法

这道题没拿满，只拿了78/100。我主要参考了Optimizing-DGEMM-on-Intel-CPUs-with-AVX512F里的实现。

里面和标答差不多，有诸多的buff可以叠：

• Blocking: 将矩阵分块，利用空间局部性。具体而言，首先可以将任务分为若干个子任务，即求C矩阵的块。其次，对于每个子任务，又可以将A和B矩阵分块相乘。
• AVX512: 使用AVX512指令集，可以同时计算8个double类型的数据。
• Loop Unrolling: 循环展开，有利于指令级并行。（这个很重要，展开后提升很多）
• Packing: 在分块的时候，不同行之间的数据是不连续的，可以将其打包成连续的数据，有利于空间局部性。

我差的那几分似乎是忘记把c矩阵进行打包了。

I. Logistic方程

比较基础的一道题，avx512 + 循环展开就可以拿满。

L. 洪水猛兽

本题的背景是计算机图形学的流体仿真中的粒子-网格混合方法。

我的做法是：每个线程分配一个局部的weight和velocity，然后最后再合并。不过注意，这道题需要调整num_threads才能拿满，即在合并的复杂度和计算的复杂度之间做trade-off。

    std::vector<std::vector<double>> global_local_velocityu(num_threads);
    std::vector<std::vector<double>> global_local_velocityv(num_threads);
    std::vector<std::vector<double>> global_local_weightu(num_threads);
    std::vector<std::vector<double>> global_local_weightv(num_threads);

    auto t1 = omp_get_wtime();
    printf("Init Time: %f s \n", t1 - t0);

    #pragma omp parallel num_threads(num_threads)
    {
        int thread_id = omp_get_thread_num();
        
        // 初始化线程局部存储
        global_local_velocityu[thread_id].resize(resolution * resolution, 0);
        global_local_velocityv[thread_id].resize((resolution + 1) * (resolution + 1), 0);
        global_local_weightu[thread_id].resize(resolution * resolution, 0);
        global_local_weightv[thread_id].resize((resolution + 1) * (resolution + 1), 0);

        auto& local_velocityu = global_local_velocityu[thread_id];
        auto& local_velocityv = global_local_velocityv[thread_id];
        auto& local_weightu = global_local_weightu[thread_id];
        auto& local_weightv = global_local_weightv[thread_id];
        // ...
    }

标答的做法是使用了#pragma omp atomic保证velocity和weight写入的原子性。由于冲突的概率很小，所以这个方法也能拿满，且比较简单。

参考： hpcgame 1st solution