Histogramming

原始题目：LeetGPU - Histogramming

题目描述

编写一个 GPU 程序，计算 32 位整数数组的直方图。直方图应统计 $[0, num\_bins)$ 范围内每个整数值的出现次数。给定长度为 $N$ 的输入数组 input 和桶数量 num_bins，结果为一个长度为 num_bins 的整数数组，每个元素表示输入数组中对应下标值的出现计数。

实现要求

• 不允许使用外部库。
• solve 函数签名必须保持不变。
• 最终结果必须存储在 histogram 数组中。

示例

示例 1

Input:  input = [0, 1, 2, 1, 0], N = 5, num_bins = 3
Output: [2, 2, 1]

示例 2

Input:  input = [3, 3, 3, 3], N = 4, num_bins = 5
Output: [0, 0, 0, 4, 0]

约束条件

• $1 \le N \le 100{,}000{,}000$。
• $0 \le input[i] < num\_bins$。
• $1 \le num\_bins \le 1{,}024$。
• 性能测试在 $N = 50{,}000{,}000,\ num\_bins = 256$ 的规模下进行。

解题思路

直方图是经典的以输入为中心（Input-centric / Scatter）操作：每个线程处理一个输入元素，竞争写入对应的 bin。核心挑战在于并行写入冲突——多个线程可能同时更新同一个 bin，需要使用 atomicAdd 来保证正确性。但原子操作是串行化的，当数据分布极度不均匀时（如所有值落入少数 bin），性能会严重下降。缓解策略包括：使用共享内存中的本地直方图减少全局原子操作、每个线程块维护私有直方图最后归并。欢迎在 GitHub Discussions 分享你的解法。