宠儿

和 CPU 相比,GPU 是一种完全不同的 architecture,没有多级存储器,没有 CPU 那么 IMBA 的超长流水线和分支预测,但是它有更多的计算核心(Tesla 2050 有 448 个硬件核心),而且线程切换以硬件的方式完成,因此可以用成千上万的线程将访存延时隐藏起来(当一个线程等待数据时,其它线程立马抢占硬件资源),也就是说这几百个核可以一直不停地计算,直到得到最终的答案。

如果只用 GPU 做图形渲染,那就浪费它在通用计算和浮点运算方面的“才华”了。人们拿 GPU 干的最多的一件事就是暴力破解,前段时间在 V2EX 闹得沸沸扬扬的“免费送 MBP 事件”其实就是一个文艺青年用 GPU 加彩虹表破解 md5 的故事。后来豆瓣的一个程序员还因为这件事写了一篇《FPU 的逆袭》,还是在说 GPU。

阿克琉斯之踵

虽然 GPU 非常适合用来做数据级并行,但是遇到访存比计算还多的情况还是注定要歇菜。比如图算法的“阿克琉斯之踵”——不规则计算。以 BFS 为例,线程在扩展每个顶点时,都需要对顶点“是否访问过”进行修改,并把顶点加到队列中,这些操作都会对显存进行访问,延时在所难免。一般情况下,GPU 会将对显存多次的访问合并成一次,前提是这些访问是整齐的,而在图算法中访问模式是随机的,因为图中任意两个顶点都有可能相连。

而在 CPU 中,“脚”同样存在,CPU 为了少访存,总是希望数据和代码出现在离它最近的 cache 里,这个“美好的愿望”通常由程序的局部性原理和 CPU 强大的预判能力来保证,但在图算法中顶点的访问不存在固定模式的,因此也就无法预测。

集体智慧

在 BFS 中,所有的“记忆”都是全局的。个体在做选择时,必须依据全局的情况做出判断,而这个参考的过程无论在怎样的 architecture 中都需要非常长的延时。

大雁排成一字南飞,蜜蜂选出蜂后,球场中的人们制造人浪,这一切都不需要事先约定,或者有一个诸如导演之类的角色。记忆分散地保存在个体中,最终却有机地结合在一起,完成一件了不起的事。

一只看不见的手,你也可以叫他集体智慧。

有多少 mutex 值得等待?

BFS 之所以难以并行化,除了前面提到的不规则计算,另一个原因是程序中有大量的锁操作。之所以有如此多的锁,是因为它用了队列。

世界上本没有队列,等在一个地方的人多了就有了队列。

等待的是什么?如果用信号量实现,那么就是等待 waiting list 里第一个阻塞线程唤醒。如果用 Lock-free 实现,那么就是等没有线程访问内存。

当系统中大部分线程 Right There Waiting 的时候,码农们只好用迪克牛仔的歌抒发自己心中的无奈:

有多少爱可以重来?有多少 mutex 值得等待?

轮子

Doug Lea 说 java.util.concurrent 中一个 Non Blocking 的算法的实现(500行)大概需要 1 年的时间。第一次看到这句话我的想法是每天写两行代码的程序员是有多么欢乐。

于是当我发现程序中需要实现一个高效的并发队列时,我想都没想就去找别人已经发明过的轮子了。

半自动步枪

CLRS 在第三版中加入“多线程编程”这一章节倒不是因为作者之一的 Leiserson 自己是开并行公司的,而是多核的时代确实已经来到,只不过人们还没有做好充足的准备,最好的证据就是那些运行在 i5、i7 上的串行程序。

PG 在《野心勃勃到令人恐惧的创业想法》提出了一个有趣的建议:成立一个平台,在用户看来它是一个将串行程序并行化的自动化工具,但内部却是由人工来完成并行化和优化工作,通过建立这样的平台, 越来越多的自动化工具就能被发明出来,因为越来越多的参与者会写机器人来完成并行的工作,最后等所有的并行化都能由机器人来完成,一个绝顶聪明的编译器就完成了,而这项工作绝对不以是一个人或一个公司的力量能够完成的。

以上这些八卦和隐喻本应出现在我的答辩演说中,却因为不够严肃只能静静地躺在这个地方。



Published

27 May 2012

Tags