Aiur

zellux 的博客

PPoPP 08 - FastForward

FastForward for Efficient Pipeline Parallelism http://systems.cs.colorado.edu/~moseleyt/publications/giacomoni-2008-ppopp-ff.pdf 这篇paper介绍了一种针对多核访问优化的队列, 主要的特点: 1. Lock-free 2. Single-producer/single-consumer 3. Cache-optimized 经典的Lamport的lock-free的队列实现可以用下面的伪代码来表述(同样只适用于单一生产者/单一消费者的情形): enqueue_nonblock(data) { if (NEXT(head) == tail) { return EWOULDBLOCK; } buffer[head] = data; head = NEXT(head); return 0; } dequeue_nonblock(data) { (head == tail) { return EWOULDBLOCK; } data = buffer[tail]; tail = NEXT(tail); return 0; } 这种实现尽管做到了lock-free,但是存在几个问题,首先是它只适用于sequential consistency内存模型,在relaxed consistency的内存模型里可能会出现类似于Double-Checked Lock(http://techblog.zellux.czm.cn/?p=30)的问题,当然这个问题可以通过插fence指令来解决;第二个问题是这篇paper着重解决的,就是enqueue和dequeue这两个操作都用到了tail和head这两个全局变量,导致多核在读取/修改这两个变量时的为了保证cache coherency会频繁的进行cache的更新,从而导致cache line threading,降低了效率。 接下来看FastForward的实现: enqueue_nonblock(data) { if (NULL != buffer[head]) { return EWOULDBLOCK; } buffer[head] = data; head = NEXT(head); return 0; } dequeue_nonblock(data) { data = buffer[tail]; if (NULL == data) { return EWOULDBLOCK; } buffer[tail] = NULL; tail = NEXT(tail); return 0; } 这个版本的队列实现粗看和Lamport的那个区别很小,而实际上这里解决了一个重要的问题:解除了head和tail的共享问题。dequeue操作只需要关心tail,enqueue操作只关心head,这样两个变量就变成CPU本地的资源了,不需要做任何同步。当然这个实现同样局限于sequential consistency,不过加fence保证顺序的overhead不大。最后测试中这个版本的单次操作比Lamport的快3. 阅读全文 →

CGO 09 一篇关于 DCL 检测的论文

Double-Checked Lock是一个常见的由于程序员把内存模型默认为sequential momery consistency导致的问题,具体见我去年写的一篇博文http://techblog.iamzellux.com/2008/07/singleton-pattern-and-double-checked-lock/ 虽然Java 5解决了这个问题,但是C++等语言中这个问题依然存在,依然有很多因为程序员假设sequential consistency而编译器做了错误的指令调度后导致的bug,见http://www.newsmth.net/bbscon.php?bid=335&id=250203 CGO 09的这篇paper Detecting and Eliminating Potential Violations of Sequential Consistency for Concurrent C/C++ Programs针对这个问题进行了深入研究,通过加fence指令的方法解决了因编译器的指令调度造成的违背程序员原义的问题,可以在http://ppi.fudan.edu.cn/yuelu_duan下载到。没有认真读过,俺在这里就不误人子弟了 O.O 阅读全文 →

OSDI 08 - CHESS

Finding and Reproducing Heisenbugs in Concurrent Programs OSDI ‘08上微软研究院发的paper,针对并发编程中难以发现的bug问题。 paper的内容主要分两大块。 一是如何在发现bug的时候记录下线程的运行先后(thread interleaving),途径是在线程API和用户程序多写一层wrapper functions,这里还有一些其他的问题,比如只记录下了thread interleaving的话出现data race怎么解决等。 另外一块内容是如何遍历出给定程序运行后所能产生的结果的集合,加入这个能实现的话那就能把所有隐藏的bug都找出来了。但是这个搜索空间很大,是指数级的,的一个结论就是:给定一个程序有n个的线程,所有线程共完成k条指令,那么c次占先调度后线程的排列情况数的复杂度是$$k^{c}$$的,所以在实现遍历代码的时候必须有效的降低k和c的值。 阅读全文 →