k-means 算法并行化

截止时间 (Hard Deadline)：2026年7月10日 23:59

提交内容：

  1. 代码源文件 kmeans-parallel.c：注意代码中应有必要的注释
  2. 实验报告 学号.pdf：简要描述实验中遇到的关键问题及解决方案、印象最深的 bugs、性能优化尝试、或者额外实现的功能等即可 (1～2 页)。

提交方式：TBD

k-means 是机器学习中一个非常经典的无监督聚类算法。给定一组数据点和聚类个数 k，该算法会尝试将数据点划分到 k 个 cluster 中，使得同一个 cluster 内的数据点尽可能接近，而不同 cluster 之间尽可能分离。

实现单线程版本的 k-means 算法并不复杂，我们在框架代码中也提供了一份 C 语言的参考实现，但这样一种实现方式在面对数据点维度 (dimension) 和数量 (scale) 剧烈增长时往往难于满足实时性要求。在本实验中，你需要将单线程的 k-means 算法并行化，通过使用锁 (locks)、条件变量 (condition variables) 或信号量 (semaphores) 来实现正确的互斥和同步，从而在多核处理器上获得预期的加速比。

运行如下命令下载本实验的框架代码：

git clone https://git.nju.edu.cn/oslab/kmeans-2026.git
cd kmeans-2026

🗒️ 实验内容

k-means 的输入包括 n 个 d 维数据点，以及希望得到的聚类个数 k。算法首先会随机选择 k 个点作为初始聚类中心 (centroids)，随后不断重复如下两个阶段，直到聚类结果已经收敛、或者达到指定的最大迭代次数：

  1. 分配阶段 (Assignment)：对于每一个数据点，计算它到所有聚类中心的距离 (本实验使用欧式距离)，并将该数据点分配给距离最近的聚类中心；
  2. 更新阶段 (Update)：对于每一个聚类，将所有被分配到该聚类的数据点求平均值，并将其作为新的聚类中心。

上述计算过程是一个非常适合并行化的场景 (embarrassingly parallel)，即可以较为容易地将其分解成多个独立小任务，从而可以在多核系统上提高算法的执行速度。

框架代码和实现需求

本次实验的框架代码中已包含单线程版本的 k-means，你可以在目录下直接运行 make 进行编译，并以如下方式来运行：

./kmeans [input_file] [k] [iterations]            # 调用串行版本
./kmeans [input_file] [k] [iterations] [threads]  # 调用并行版本

其中，input_file 是存储数据点的文件，k 是指定的聚类个数，iterations 是允许的最大迭代轮数，可选参数 threads 指定工作线程个数 (若提供则调用并行版本，否则调用串行版本)。程序运行结束后将在 stdout 打印最终的聚类中心和每个数据点所属的聚类编号，并在 stderr 打印计时信息。

输入文件 input_file 的第一行包含两个整数 n 和 d，分别表示数据点个数和数据维度。在接下来的 n 行中，每行包含 d 个浮点数，表示一个数据点。例如：

6 2
1.0 1.0
1.2 0.8
0.8 1.1
8.0 8.0
8.3 7.7
7.9 8.2

框架代码中存储数据集 Dataset 和聚类状态 State 的结构体如下所示：

typedef struct {
  int n;              // 数据点个数
  int d;              // 数据维度
  double *points;     // 数据点数组 (n * d 个浮点数，按行优先方式存储)
} Dataset;

typedef struct {
  int k;              // 聚类个数
  double *centroids;  // 聚类中心 (k * d 个浮点数，按行优先方式存储) 
  int *labels;        // 每个数据点当前所属的聚类编号
} State;

你可以在 kmeans.h 和 kmeans.c 中找到读取、打印和操作上述结构体的相关函数定义和实现，并在 kmeans-serial.c 中找到串行版本的实现。同时，input 目录下提供了 2 个数据点文件可用于测试。

基于框架代码，你需要考虑如何对 k-means 的迭代过程进行并行化，仔细思考其中可能涉及的互斥和同步需求，并实现 kmeans-parallel.c 文件中的如下函数：

void kmeans_parallel(int threads, const Dataset *data, State *state, int iterations)

该函数的输入参数包括：

  • threads: 代码运行过程中任何时刻能同时存在的线程个数上限 (不包括主线程，即你最多可以使用 threads + 1 个线程来进行计算)；
  • data: 输入数据集，函数执行过程中不应修改其中的数据点；
  • state: 当前的聚类状态，函数执行结束后应包含最终聚类中心和聚类编号；
  • iterations: 允许的最大迭代轮数。

注意本次实验的重点在于并行化 (相比于单线程版本的速度提升)，而不是提升 k-means 的聚类效果 (是否簇内相似度高且簇间相似度低)。对于 k-means 的计算过程，你可以直接复用串行版本中的合适代码片段。当然，你也可以设计不同的实现方式，但需要确保不改变 Dataset 和 State 结构体的定义，并在 kmeans-parallel.c 中包含所有额外定义的数据结构和函数实现。

本次实验中仅允许使用 pthread.h 和 semaphore.h 库中的如下 API (API 手册)：

  • 线程创建和结束：pthread_create()、pthread_exit()、pthread_yield()、pthread_join()
  • 互斥锁 (mutex): 以 pthread_mutex_ 为前缀的 API
  • 自旋锁 (spin): 以 pthread_spin_ 为前缀的 API
  • 条件变量 (cond): 以 pthread_cond_ 为前缀的 API
  • 信号量 (sem): 以 sem_ 为前缀的 API

📊 结果评估

我们会在特定测试环境中编译和运行你提交的 kmeans-parallel.c 文件来评估代码实现的正确性和执行速度：

  1. 正确性：如果并行版本最终能输出和单线程版本一致的聚类中心和聚类编号，则可获得该次测试 40% 的分数。注意在浮点数计算中，不同的计算顺序可能导致最后几位结果存在差异，因此聚类中心将按照误差范围进行比较，聚类编号的比较同样基于最终聚类中心，评测时会以最终 centroids 为参照，将每个数据点重新分配给最近的聚类中心后再进行比较，以避免因浮点数误差导致单线程和多线程版本计算结果的不一致。
  2. 执行速度：在允许最多 N 个线程的情况下，并行版本在具有 N 个物理 CPU Core 的运行环境中应能获得合理和稳定的加速比。如果并行版本能获得预计的加速效果，则可获得该次测试剩余 60% 的分数 (按加速比区间进行计算)。

注意提交的代码在运行过程中不能违反以下规则，否则会直接返回错误信息：

  • 更改了 kmeans-parallel.c 中引用的头文件、或增加了新的头文件；
  • 使用了 pthread.h 和 semaphore.h 库中允许范围之外的 API；
  • 代码运行过程中任意时刻同时存在的工作线程（不含主线程）超过了 threads 指定的上限。

我们测试环境使用的 Makefile 和 main.c 与框架代码中提供的类似。在提交代码之前，建议大家在提交前先自行编写测试代码来进行测试 (包括构造具有各种不同特征的数据文件、不同的输入参数、以及使用不同的物理 CPU Core 个数)。

💭 Tips

并行程序往往会 “看似运行正确，实则包含错误”。为了观察到并行程序的错误行为，往往需要 “精心” 构造合适的测试数据。例如，可以考虑的方向包括：

  • 大规模高维场景：增加 n、d 或 iterations 的值，理想情况下应该体现较高的加速比；
  • 多簇密集场景：增加 k 的值，在处理聚类中心时是否正确和高效；
  • 负载不均衡场景：某些聚类包含很多点、某些很少，此时任务划分是否合理；
  • 重复运行测试：相同输入下重复运行多次，输出是否稳定。

此外，框架代码的 Makefile 中会额外编译两个二进制文件，可用于检测一些错误情况：

  • ./kmeans-tsan：由 ThreadSanitizer 编译，可以帮助你检测及调试竞争条件
  • ./kmeans-asan：由 AddressSanitizer 编译，可以帮助你检测及调试内存错误

关于多线程编程的一些介绍：