Chinaunix首页 | 论坛 | 博客
  • 博客访问: 8005667
  • 博文数量: 159
  • 博客积分: 10424
  • 博客等级: 少将
  • 技术积分: 14615
  • 用 户 组: 普通用户
  • 注册时间: 2010-07-14 12:45
个人简介

啦啦啦~~~

文章分类
文章存档

2015年(5)

2014年(1)

2013年(5)

2012年(10)

2011年(116)

2010年(22)

分类: LINUX

2011-12-07 22:44:59

作者:gfree.wind@gmail.com
博客:blog.focus-linux.net   linuxfocus.blog.chinaunix.net
 
 
本文的copyleft归gfree.wind@gmail.com所有,使用GPL发布,可以自由拷贝,转载。但转载请保持文档的完整性,注明原作者及原链接,严禁用于任何商业用途。
======================================================================================================

很早就建立多核、多线程的博文目录,但一直没有写相关文章,后来干脆把这两个目录合为一个,叫做并行编程。

今天就开始第一篇吧,写一点自己关于提高程序并行效率的一点经验。并行编程从多线程编程,多进程编程,直到现在的多核编程。目前多核CPU应用已经越来越广泛了,大部分的电脑都是多核了。所以提高多核下的程序并发性,可以极大的提高程序的效率。

先从最基本的锁说起吧。在多核下,锁的代价比以前更高了,这个稍后会提到。为了提高并发性,最好的追求是无锁。如果锁是无法避免的,那么要让锁的粒度尽量小。
1. 如何做到无锁呢?
1)一般我们可以牺牲空间来换取性能。比如一些统计信息,可以建立per CPU的变量,即每个CPU都有一份统计信息,当计算总的统计信息时,需要加上所有的per CPU的统计信息。
2)可以使用RCU机制——RCU的具体用法,问google去:D。使用RCU机制,可以避免锁的使用;
3)良好的设计。举个简单的例子,读写队列。读线程和写线程分别维护两个指针,来实现队列的入队和出队。
2. 缩小锁的粒度
当锁的粒度越小,竞争发生的概率也就越小,程序的并发性也就越好。举个简单的例子,一个hash表。如果只有一把锁用于保护hash表,那么为了提高并发性,可以为每一个桶slot建立一把锁来取代原来的hash表的全局锁。显然,后者的并发性一定强于前者多倍。
3. 选择恰当的锁
1)如关键代码运行时间很短,可以使用spin lock,来取代mutex或者semphore。原因有二,一个是mutex和semphore为系统调用,这个cost较高,需要用户态和内核态的转换。另外一个原因是当等待锁的时候,该线程会被加入到sleep对列。这两个原因都影响了并发性。当然,如果关键代码的运行时间比较长,就不要使用spin lock,而使用mutex或者semphore。因为spin lock时,等待的线程是一直自旋spin,这白白浪费了CPU的资源。
2)如果锁包含的对象,在被修改的过程中,可以合法访问——即不造成程序crash,那么可以使用seqlock。seqlock对于写者来说,是一个真的锁,即不允许多个写者同时修改对象。但是对于读者来说,根本没有加锁和解锁的过程,读者通过检查锁的seq number,来检查对象的数据是否一致。seqlock对于读取多修改少的情况,非常适用。

关于CPU的cache。对于多核CPU来说,每个CPU都有自己的data cache和code cache。这里指的是L1 cache,我记得L2 cache就是多CPU共享的了。那么当一个变量同时存在于多个CPU cache时,当一个CPU更新这个变量时,它的cache自然会被更新。但是因为多个CPU的存在,那么其它CPU的cache同样也需要更新。一般来说cache更新有两种机制,write-back和write-through。不同的厂商的CPU采取的机制也不同,但是更新cache的代价却是不可避免的。那么我们为了提高效率,就要尽量避免这种cache的更新。如何做呢?就是让变量不要存在于多个CPU的cache中。这个就有各种方法了。像上面提到的per cpu的变量,以及不同CPU使用不同的变量。还有上面提到的锁的问题。当加锁时,会强制CPU更新cache,来保证数据的一致性。
另外,cache除了有cache间的同步问题。还有一些情况,会导致CPU的cache被清除。
1)进程切换,即CPU要运行一个新的task,这时CPU会清空以前的cache;
2)发生中断,处理中断的CPU会清空cache;
应该还有其他的情况,会导致CPU清空自己的cache。但是我一时想不起那么多了,欢迎大家补充。

最后一个关于提高并行效率的方法就是优秀的架构和软件设计。关于这点也是听上去最虚的,没法具体说明,但是它确实最有效的方法。不过这个需要具体问题具体分析。一个简单的原则就是在硬件资源上进行划分,如内存,不同CPU使用不同的内存。对于软件来说,将整个工作,划分为耦合性很低的不同任务,使不同任务可以同时运行。并且可以利用CPU的亲和性,使某个task只在某CPU上运行,减少或禁止进程切换到另外一个CPU上。这样既保证了CPU的cache不会被清空,也使cache的命中率大大提高。

啰啰嗦嗦的说了一大堆,基本上自己刚刚对于并行编程的一点经验总结吧。做了比较长时间的多核编程了,一直没有认真的总结一下经验。现在这么一写,发现还是有不少东西值得再研究一下细节,再拓展一下的。等我以后的总结吧:D
阅读(11368) | 评论(13) | 转发(8) |
给主人留下些什么吧!~~

GFree_Wind2012-05-11 10:21:44

platinaluo: can you paste some sample code segment?.....
OK. I will paste some codes later. Now I am investigating on the computer architecture, and the basic knowledge of network.

platinaluo2012-05-10 23:08:21

can you paste some sample code segment?

GFree_Wind2012-03-28 13:54:03

alexhak2004: 我是先入为主了,因为看到了spin_lock,所以以为就是内核态了。。。
其实,我觉得,其实你提到的最后一点,也就是优秀的架构和软件设计,我认为是最难的。。。很.....
是的。所以一般设计都不会有一个通用的设计,必须要根据应用场景,做调整,也包括你说的如何折中。

alexhak20042012-03-28 13:23:17

我是先入为主了,因为看到了spin_lock,所以以为就是内核态了。。。
其实,我觉得,其实你提到的最后一点,也就是优秀的架构和软件设计,我认为是最难的。。。很多时候,需要做一些折中。比如,视频的编解码就是一例,为了达到程序并行,可能会考虑把一幅图像分为多个slice进行编码,每个slice作为一个线程处理,但是这就使得不同的slice间不能相互参考,从而降低了整体的压缩效率。。。

GFree_Wind2012-03-22 18:36:29

alexhak2004: "semphore为系统调用"这句话好像有点问题哦,内核也可以使用semphore,当然后面说的赞同。.....
呵呵,我说系统调用是基于应用层的并发而说的。对比spinlock,semphore为系统调用。

内核确实也可以使用semphore。你的意见很对,我应该加上上下文环境,说明是应用层的开发。