华科七边形 2021 秋季招新

要完成本题，我们希望你拥有一台4核（不含超线程）及以上的设备。

DDL: 2021/11/02 23:59

算法介绍

K-means 是一种直观的聚类算法。在本题中，我们会在考虑二维的 K-Means 算法。程序会以坐标的形式输入$N$个点，K-Means将这些点聚成$K$个点集。

K-means 算法的流程描述如下：

1. 随机生成$k$个点，每一个点$c_i$代表一个点集的中心；

2. 对于每一个点$p$和每一个中心点$c_i$，计算$p$和$c_i$之间的距离$d(p, c_i)$；

3. 将每一个点$p$分配到距离最小的点集中；

4. 计算每一个点集的坐标的平均数，作为每一个点集的新的中心点，

5. 回到第2步，直到收敛或达到设定的最大迭代次数；

然而这些都不重要(吗?)，因为已经有人帮你写好了代码。但是非常遗憾的是，这个人写的代码性能非常差。

文件解释

在 kmeans 文件夹中，我们为你提供了六个文件：

    kmeans
    ├── CMakeLists.txt
    ├── generate.py
    ├── kmeans.cpp
    ├── kmeans.hpp
    ├── main.cpp
    └── visualize.py

其中，kmeans.cpp/.hpp 是 K-means 算法的实现，在本题中，你只能通过修改这两个文件来实现你的优化。 generate.py用于生成数据，visualize.py 用于可视化计算的结果。

为了编译该项目，你需要安装 cmake, make, gcc. 在 kmeans 目录下，执行

cmake -B build
cd build
make -j

即可完成构建。你可以在 build 文件夹下找到编译得到的可执行文件 kmeans.

接下来，你可以使用 generate.py 来生成输入数据。

python3 generate.py

该脚本会在当前目录下生成一个 data.in 文件。生成数据后，你可以运行之前的二进制，并获得输出文件和运行时间：

$ ./kmeans data.out <../data.in 
Running kmeans with num points = 1000000, num centers = 15, max iterations = 1000...
Finished in 166 iterations.
Time cost: 4.15847s
Writing output files...

使用 visualize.py 可以对结果进行可视化。具体使用方法请自行探索。

优化方法

在本题中，你需要通过以下手段来对代码进行优化，从而提高代码的性能：

串行优化

• 消除多余的计算，合并多余的循环¹

• 消除多余的内存分配和内存拷贝²

• 优化内存布局，增强代码的空间局部性³

• 使用SIMD指令⁴

并行优化

• 使用多线程并行化算法，发挥多核CPU的性能⁵

你需要使用至少一种串行优化方法和至少一种并行优化方法。

程序输出的运行时间不包括 IO 时间，因此你不用担心 IO 相关的优化。

性能剖析

代码这么长，我应该优化哪一部分呢？不知道你会不会有这样的疑问。一种简单的思路是，集中精力优化代码中时间占比最大的部分，显然这样会获得更大的收益。

那么究竟哪一部分时间占比最大呢？你可以通过在原始代码中插入计时代码来衡量各个部分的运行时间和优化效果。你也可以通过使用perf, gprof等性能分析器来分析程序的性能情况，也可以尝试火焰图（flamegraph）等工具。

提示

一些对你有用的网站和搜索关键词：

• https://www.brendangregg.com/perf.html

• https://www.brendangregg.com/flamegraphs.html

• https://software.intel.com/sites/landingpage/IntrinsicsGuide/

• https://bisqwit.iki.fi/story/howto/openmp/

• 《CS:APP》第五章：优化程序性能，第六章：存储器层次结构

评分

你需要对你的代码进行测试，保证你的代码可以输出正确的结果。你需要保证代码在优化前后输出的结果文件完全一致。如果代码输出的结果是错误的⁶，你将直接获得零分。

你需要提交代码和文档，文档中应该包含

1. 你的设备的信息，如 CPU 型号和核数，内存容量和频率等等。
2. 你的优化方法，测试结果和优化效果（举例：使用了xxx优化，相对于原代码，速度提升了15.6倍）
3. 你在解题过程中所参考的资料
4. 在解题过程中，遇到的有意思的事情，或者是让你印象深刻的bug

我们会根据你的代码的加速比来进行评分。如果你让代码加速了4倍及以上，请将你的代码上传到 GitHub 上，并在本仓库开一个 issue，附上你的仓库的链接。

挑战

1. 将你的代码搬迁到 GPU 上，使用 CUDA 编程。
2. 将你的代码拓展到多台机器上，使用 MPI 进行通信。

Footnotes

1. 最简单的优化方法, 就是让你的代码少干一些活 ↩

2. 你或许使用过C++中的引用 ↩

3. 如果你还没看过《CS:APP》的话，可以参考书上的对应章节 ↩

4. SIMD指令可以一次处理多个数据，极大地提高了数据的吞吐量。在编写代码时，可以参考Intel® Intrinsics Guide。在使用指令前，请提前确定你的设备是否支持你所使用的指令集。一般来说，现在的 Intel 设备都支持 AVX512，AMD 设备都支持 AVX2，你也可以执行 lscpu 命令，来检测你的设备是否支持这些指令集 ↩

5. 推荐使用 OpenMP。如果你还不知道什么是OpenMP, 可以尝试搜索该关键词。也可以使用std::thread或pthread在并行化代码的同时，也要注意代码的正确性，避免出现数据竞争等并发错误 ↩

6. 注意，一些隐秘的并发bug可能并不是每次都会被触发，我们建议你运行10次代码，检查10次的结果是否都是正确的 ↩