算法与理论计算机2017arxiv.org
GPU 排序：综述
Sorting with GPUs: A Survey
进阶 · 约 90 分钟读完前置知识：并行计算基础、GPU 架构（CUDA/SIMT）、经典排序算法
导读
这篇综述系统梳理了 GPU 上排序算法的研究现状，回顾了约 50 种不同的 GPU 排序方法。排序是基础性问题，但 GPU 的并行架构与分支密集、需要同步的传统排序算法（如归并排序）存在天然张力，因此该领域有不少专门的设计与优化工作。
HN 关注点：GPU 在通用计算中的潜力与局限，讨论焦点包括 GPU 排序的实际应用场景、硬件可移植性问题以及架构层面的瓶颈。
HN 评论精选
这几条评论里：质疑 1 补充 2 亲历 1
补充GPU 通用计算的最大障碍是硬件可移植性，呼吁跨厂商的抽象层
很高兴看到这个领域的研究。我今年才意识到，对游戏来说 GPU 和显存其实比 CPU 和内存更重要，这大概说明 GPU 在通用计算中被低估了。不过有一个大障碍：可移植性。无论是游戏、神经网络还是挖矿，我总是看到“仅支持 NVIDIA”或“在 AMD 上效果最佳”。如果要在任意应用中使用 GPU，就需要一个支持各种 GPU（包括 Intel 芯片）的硬件抽象库。这样的工作有人在做吗？进展如何？
oelmekki查看英文原文
Cool to see research in that field, I realized this year that for gaming GPU and VRAM were actually more important than CPU and RAM, it probably tells something about underusage of GPU in general computing. There's one big blocker as far as I can tell, though: portability. When it comes to gaming, neural networks, cryptomining, etc, I always see "only nvidia cards supported", or "work best on amd". If we were to use GPU in just any kind of application, we would need to have hardware abstraction library which support any kind of GPU, including intel chips. Is such effort already being worked on, at any stage of completion?
质疑质疑 GPU 排序的实际应用场景，并估计其适用规模门槛
排序是基础问题，所以这很重要，但我一时想不出什么实际问题需要大规模排序操作。有人能举出实际应用吗？我确信它们存在。我猜（假设输入和结果都在 CPU 上）使用 GPU 的盈亏平衡点至少是几 MB、数百万个元素。写这篇论文一定花了很大功夫，这里回顾了大约 50 种方法，很高兴有这样的综述存在。
exDM69查看英文原文
Sorting is a fundamental problem so this is important stuff but I can't right now come up with a practical problem involving large sorting operations. Can anyone come up with a practical application for this? I have no doubt they exist. I would think the breakeven point for using the GPU (assuming inputs and results are on the CPU) is several megabytes of millions or elements at least. Writing this paper must have been a lot of effort. There are something like 50 different methods reviewed here. Good thing that papers like this exist.
亲历亲历分享：GPU.js 虽有 API 局限，仍比 CPU 快约 10 倍
我在 three.js 的 nbody 引力模拟中使用 GPU.js。总体很喜欢，但它有局限：函数只能返回单个浮点数，导致大量冗余计算。比如要得到一个天体的三维加速度向量，我得对每个维度各调用一次函数，每遍都重算所有临时变量，还要再做一遍碰撞检测，最终约是 4n² 而不是 n²。即便如此仍比纯 CPU 实现快约一个数量级。未来计划支持 WebGL 2.0 和 OpenCL，应该会改善灵活性。（附在线演示和 GitHub 链接，可用 ?CPU=true 切换 CPU/GPU 计算，bodyCount 调整天体数量）
gnarbarian查看英文原文
I'm using GPU.js for a nbody gravity simulation in three.js. So far I'm liking GPU.js but it has it's limitations. only being able to return a single float from any function causes a lot of redundancy. For example, in order to get the 3d acceleration vector for one body I have to call the function once for each dimension, recomputing all of the temporary variables each pass. Then I have to make another pass for collision detection so it ends up being about 4n^2 vs just n^2 nonetheless it's still about an order of magnitude faster than the pure CPU implementation I have. In the future they plan to add webGL 2.0 and OpenCL support which should improve the flexibility of the library. http://thedagda.co:9000/?stars=true&bodyCount=1000 you can toggle CPU nbody computation with: ?CPU=true in the url. remove it for GPU computation. you can toggle the number of planets with the bodyCount variable. default is 1000 if you have a beefy computer try bodyCount=4000 gamepad=true works if you have a xbox controller hooked up. on gitHub: https://github.com/ubernaut/spaceSim
补充从架构角度分析：分支密集与同步程序计数器使 GPU 排序天然困难
排序似乎是一个内存受限的问题，而计算上最优的归并排序方案分支密集——这恰恰是 GPU 一直不擅长的两点。此外，CUDA 架构中每个线程块共享同步的程序计数器，对实现最优线程占用率构成了相当大的障碍。
leecarraher查看英文原文
Sorting seems like a memory hard problem where the computationally optimal, merge sort solution, is heavily branched, two things gpus have never been terribly good at. Furthermore, the synchronized program counter per block of threads, presents a considerable road block to getting optimal thread occupancy specifically in the cuda architecture.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2017Hacker News 讨论帖148 分 · 50 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选