在并行计算或数据并行编程中，数据划分是将大量数据分配给多个计算单元（如 GPU 线程或 CPU 核心）进行并行处理的重要技术。块划分（Block Partitioning）和周期划分（Cyclic Partitioning）是两种常见的划分方式，它们的区别主要体现在 数据分配的模式 上。
1. 块划分（Block Partitioning）
基本概念
- 块划分是一种 连续分配 的方法，将数据划分成若干个连续的大块（Block），然后将每个块分配给不同的计算单元（线程、进程或核心）。
- 每个计算单元连续地处理一部分数据。
示例
假设有 16 个数据元素，分配给 4 个线程，则每个线程需要处理的数据量为 ( \text{数据总量} / \text{线程数} = 16 / 4 = 4 )。
块划分分配示意：
线程 0：数据[0, 1, 2, 3]
线程 1：数据[4, 5, 6, 7]
线程 2：数据[8, 9, 10, 11]
线程 3：数据[12, 13, 14, 15]
特点
- 优点：
- 数据连续性好，易于在共享内存或缓存中处理。
- 开销较小，因为数据分配是连续的。
- 缺点：
- 如果任务量不均匀（负载不均衡），可能导致某些线程执行完毕而其他线程仍然在工作。
适用场景
- 数据分布均匀，计算负载均衡。
- 大规模线性数据处理，例如数组遍历、向量加法、矩阵分块等。
2. 周期划分（Cyclic Partitioning）
基本概念
- 周期划分（也称为 轮转划分）将数据按照一定的周期进行分配，即将数据 交替分配 给不同的计算单元。
- 数据的索引按照固定的步长分配给不同线程（例如步长为线程总数）。
示例
假设仍然有 16 个数据元素，分配给 4 个线程，每个线程交替处理数据。
周期划分分配示意：
线程 0：数据[0, 4, 8, 12]
线程 1：数据[1, 5, 9, 13]
线程 2：数据[2, 6, 10, 14]
线程 3：数据[3, 7, 11, 15]
特点
- 优点：
- 适合负载不均匀的任务，能够更好地实现负载均衡。
- 如果数据量较小且任务执行时间不一致，可以减少部分线程的空闲时间。
- 缺点：
- 数据不连续，可能导致内存访问不友好，降低缓存命中率，影响性能。
- 线程之间数据访问分散，可能增加内存访问开销。
适用场景
- 数据量较大但计算负载不均匀，例如某些元素的计算复杂度不同。
- 需要避免线程间负载不均的问题，例如稀疏矩阵计算。
3. 对比总结
| 特性 | 块划分（Block） | 周期划分（Cyclic） |
|---|---|---|
| 数据分配 | 数据连续分配成块 | 数据交替分配，步长为线程数 |
| 内存访问 | 连续访问，缓存友好 | 不连续访问，可能影响缓存性能 |
| 负载均衡 | 适用于负载均匀的任务 | 适用于负载不均匀的任务 |
| 实现复杂度 | 较简单 | 较复杂 |
| 场景 | 大规模均匀数据处理 | 计算负载不均衡的任务 |
4. 应用实例
块划分实例：矩阵向量乘法
将一个矩阵按行划分，每个线程负责处理连续的几行数据，适合矩阵向量乘法：
__global__ void matVecMul(float *matrix, float *vector, float *result, int rows, int cols) {
int row = blockIdx.x * blockDim.x + threadIdx.x;
if (row < rows) {
float sum = 0;
for (int i = 0; i < cols; i++) {
sum += matrix[row * cols + i] * vector[i];
}
result[row] = sum;
}
}
周期划分实例：稀疏矩阵乘法
由于稀疏矩阵中非零元素分布不均匀，可以使用周期划分来均匀分配计算任务，避免负载不均。
__global__ void sparseMatVecMul(float *values, int *indices, float *vector, float *result, int nnz) {
int idx = threadIdx.x + blockIdx.x * blockDim.x;
for (int i = idx; i < nnz; i += gridDim.x * blockDim.x) {
atomicAdd(&result[indices[i]], values[i] * vector[indices[i]]);
}
}
总结
- 块划分：数据连续分配，适合负载均衡的场景，内存访问效率高。
- 周期划分：数据交替分配，适合负载不均衡的任务，保证计算单元的工作均衡，但内存访问效率可能较低。
