网站设计实施方案,如何自己弄一个网站,网站推荐软件,重庆建设摩托车网站利用多核多线程进行程序优化2008 年 11 月 17 日 大家也许还记得 2005 年 3 月 C 大师 Herb Sutter 在 Dr.Dobb’s Journal 上发表了一篇名为《免费的午餐已经结束》的文章。文章指出#xff1a;现在的程序员对效率、伸缩性、吞吐量等一系列性能指标相当忽视#xff0c;很多性… 利用多核多线程进行程序优化 2008 年 11 月 17 日 大家也许还记得 2005 年 3 月 C 大师 Herb Sutter 在 Dr.Dobb’s Journal 上发表了一篇名为《免费的午餐已经结束》的文章。文章指出现在的程序员对效率、伸缩性、吞吐量等一系列性能指标相当忽视很多性能问题都仰仗越来越快的 CPU 来解决。但 CPU 的速度在不久的将来即将偏离摩尔定律的轨迹并达到一定的极限。所以越来越多的应用程序将不得不直面性能问题而解决这些问题的办法就是采用并发编程技术。 样例程序 程序功能求从1一直到 APPLE_MAX_VALUE (100000000) 相加累计的和并赋值给 apple 的 a 和 b 求 orange 数据结构中的 a[i]b[i ] 的和循环 ORANGE_MAX_VALUE (1000000) 次。 说明 由于样例程序是从实际应用中抽象出来的模型所以本文不会进行 test.atest.b test.bsum 、中间变量(查找表)等类似的优化。 以下所有程序片断均为部分代码完整代码请参看本文最下面的附件。 清单 1. 样例程序#define ORANGE_MAX_VALUE 1000000
#define APPLE_MAX_VALUE 100000000
#define MSECOND 1000000struct apple
{unsigned long long a;unsigned long long b;
};struct orange
{int a[ORANGE_MAX_VALUE];int b[ORANGE_MAX_VALUE];};int main (int argc, const char * argv[]) {// insert code here...struct apple test;struct orange test1;for(sum0;sumAPPLE_MAX_VALUE;sum){test.a sum;test.b sum;}sum0;for(index0;indexORANGE_MAX_VALUE;index){sum test1.a[index]test1.b[index];}return 0;
}
回页首K-Best 测量方法 在检测程序运行时间这个复杂问题上将采用 Randal E.Bryant 和 David R. O’Hallaron 提出的 K 次最优测量方法。假设重复的执行一个程序并纪录 K 次最快的时间如果发现测量的误差 ε 很小那么用测量的最快值表示过程的真正执行时间 称这种方法为“ K 次最优K-Best方法”要求设置三个参数 K: 要求在某个接近最快值范围内的测量值数量。 ε 测量值必须多大程度的接近即测量值按照升序标号 V1, V2, V3, … , Vi, … 同时必须满足1 εVi Vk M: 在结束测试之前测量值的最大数量。 按照升序的方式维护一个 K 个最快时间的数组对于每一个新的测量值如果比当前 K 处的值更快则用最新的值替换数组中的元素 K 然后再进行升序排序持续不断的进行该过程并满足误差标准此时就称测量值已经收敛。如果 M 次后不能满足误差标准则称为不能收敛。 在接下来的所有试验中采用 K10ε2%M200 来获取程序运行时间同时也对 K 次最优测量方法进行了改进不是采用最小值来表示程序执行的时间而是采用 K 次测量值的平均值来表示程序的真正运行时间。由于采用的误差 ε 比较大在所有试验程序的时间收集过程中均能收敛但也能说明问题。 为了可移植性采用 gettimeofday() 来获取系统时钟system clock时间可以精确到微秒。回页首测试环境 硬件联想 Dual-core 双核机器主频 2.4G内存 2G 软件Suse Linunx Enterprise 10内核版本linux-2.6.16回页首软件优化的三个层次 医生治病首先要望闻问切然后才确定病因最后再对症下药如果胡乱医治一通不死也残废。说起来大家都懂的道理但在软件优化过程中往往都喜欢犯这样的错误。不分青红皂白一上来这里改改那里改改其结果往往不如人意。 一般将软件优化可分为三个层次系统层面应用层面及微架构层面。首先从宏观进行考虑进行望闻问切即系统层面的优化把所有与程序相关的信息收集上来确定病因。确定病因后开始从微观上进行优化即进行应用层面和微架构方面的优化。 系统层面的优化内存不够CPU 速度过慢系统中进程过多等 应用层面的优化算法优化、并行设计等 微架构层面的优化分支预测、数据结构优化、指令优化等 软件优化可以在应用开发的任一阶段进行当然越早越好这样以后的麻烦就会少很多。 在实际应用程序中采用最多的是应用层面的优化也会采用微架构层面的优化。将某些优化和维护成本进行对比往往选择的都是后者。如分支预测优化和指令优化在大型应用程序中往往采用的比较少因为维护成本过高。 本文将从应用层面和微架构层面对样例程序进行优化。对于应用层面的优化将采用多线程和 CPU 亲和力技术在微架构层面采用 Cache 优化。回页首并行设计 利用并行程序设计模型来设计应用程序就必须把自己的思维从线性模型中拉出来重新审视整个处理流程从头到尾梳理一遍将能够并行执行的部分识别出来。 可以将应用程序看成是众多相互依赖的任务的集合。将应用程序划分成多个独立的任务并确定这些任务之间的相互依赖关系这个过程被称为分解Decomosition。分解问题的方式主要有三种任务分解、数据分解和数据流分解。关于这部分的详细资料请参看参考资料一。 仔细分析样例程序运用任务分解的方法 不难发现计算 apple 的值和计算 orange 的值属于完全不相关的两个操作因此可以并行。 改造后的两线程程序清单 2. 两线程程序void* add(void* x)
{ for(sum0;sumAPPLE_MAX_VALUE;sum){((struct apple *)x)-a sum;((struct apple *)x)-b sum; }return NULL;
}int main (int argc, const char * argv[]) {// insert code here...struct apple test;struct orange test1{{0},{0}};pthread_t ThreadA;pthread_create(ThreadA,NULL,add,test);for(index0;indexORANGE_MAX_VALUE;index){sum test1.a[index]test1.b[index];} pthread_join(ThreadA,NULL);return 0;
}
更甚一步通过数据分解的方法还可以发现计算 apple 的值可以分解为两个线程一个用于计算 apple a 的值另外一个线程用于计算 apple b 的值(说明本方案抽象于实际的应用程序)。但两个线程存在同时访问 apple 的可能性所以需要加锁访问该数据结构。 改造后的三线程程序如下清单 3. 三线程程序struct apple
{unsigned long long a;unsigned long long b;pthread_rwlock_t rwLock;
};void* addx(void* x)
{pthread_rwlock_wrlock(((struct apple *)x)-rwLock);for(sum0;sumAPPLE_MAX_VALUE;sum){((struct apple *)x)-a sum;}pthread_rwlock_unlock(((struct apple *)x)-rwLock);return NULL;
}void* addy(void* y)
{pthread_rwlock_wrlock(((struct apple *)y)-rwLock);for(sum0;sumAPPLE_MAX_VALUE;sum){((struct apple *)y)-b sum;}pthread_rwlock_unlock(((struct apple *)y)-rwLock);return NULL;
}int main (int argc, const char * argv[]) {// insert code here...struct apple test;struct orange test1{{0},{0}};pthread_t ThreadA,ThreadB;pthread_create(ThreadA,NULL,addx,test);pthread_create(ThreadB,NULL,addy,test);for(index0;indexORANGE_MAX_VALUE;index){sumtest1.a[index]test1.b[index];}pthread_join(ThreadA,NULL);pthread_join(ThreadB,NULL);return 0;
}
这样改造后真的能达到我们想要的效果吗通过 K-Best 测量方法其结果让我们大失所望如下图图 1. 单线程与多线程耗时对比图为什么多线程会比单线程更耗时呢其原因就在于线程启停以及线程上下文切换都会引起额外的开销所以消耗的时间比单线程多。 为什么加锁后的三线程比两线程还慢呢其原因也很简单那把读写锁就是罪魁祸首。通过 Thread Viewer 也可以印证刚才的结果实际情况并不是并行执行反而成了串行执行如图2图 2. 通过 Viewer 观察三线程运行情况其中最下面那个线程是主线程一个是 addx 线程另外一个是 addy 线程从图中不难看出其他两个线程为串行执行。 通过数据分解来划分多线程还存在另外一种方式一个线程计算从1到 APPLE_MAX_VALUE/2 的值另外一个线程计算从 APPLE_MAX_VALUE/21 到 APPLE_MAX_VALUE 的值但本文会弃用这种模型有兴趣的读者可以试一试。 在采用多线程方法设计程序时如果产生的额外开销大于线程的工作任务就没有并行的必要。线程并不是越多越好软件线程的数量尽量能与硬件线程的数量相匹配。最好根据实际的需要通过不断的调优来确定线程数量的最佳值。回页首加锁与不加锁 针对加锁的三线程方案由于两个线程访问的是 apple 的不同元素根本没有加锁的必要所以修改 apple 的数据结构删除读写锁代码通过不加锁来提高性能。 测试结果如下图 3. 加锁与不加锁耗时对比图其结果再一次大跌眼镜可能有些人就会越来越糊涂了怎么不加锁的效率反而更低呢将在针对 Cache 的优化一节中细细分析其具体原因。 在实际测试过程中不加锁的三线程方案非常不稳定有时所花费的时间相差4倍多。 要提高并行程序的性能在设计时就需要在较少同步和较多同步之间寻求折中。同步太少会导致错误的结果同步太多又会导致效率过低。尽量使用私有锁降低锁的粒度。无锁设计既有优点也有缺点无锁方案能充分提高效率但使得设计更加复杂维护操作困难不得不借助其他机制来保证程序的正确性。回页首针对 Cache 的优化 在串行程序设计过程中为了节约带宽或者存储空间比较直接的方法就是对数据结构做一些针对性的设计将数据压缩 (pack) 的更紧凑减少数据的移动以此来提高程序的性能。但在多核多线程程序中这种方法往往有时会适得其反。 数据不仅在执行核和存储器之间移动还会在执行核之间传输。根据数据相关性其中有两种读写模式会涉及到数据的移动写后读和写后写 因为这两种模式会引发数据的竞争表面上是并行执行但实际只能串行执行进而影响到性能。 处理器交换的最小单元是 cache 行或称 cache 块。在多核体系中对于不共享 cache 的架构来说两个独立的 cache 在需要读取同一 cache 行时会共享该 cache 行如果在其中一个 cache 中该 cache 行被写入而在另一个 cache 中该 cache 行被读取那么即使读写的地址不相交也需要在这两个 cache 之间移动数据这就被称为 cache 伪共享导致执行核必须在存储总线上来回传递这个 cache 行这种现象被称为“乒乓效应”。 同样地当两个线程写入同一个 cache 的不同部分时也会互相竞争该 cache 行也就是写后写的问题。上文曾提到不加锁的方案反而比加锁的方案更慢就是互相竞争 cache 的原因。 在 X86 机器上某些处理器的一个 cache 行是64字节具体可以参看 Intel 的参考手册。 既然不加锁三线程方案的瓶颈在于 cache那么让 apple 的两个成员 a 和 b 位于不同的 cache 行中效率会有所提高吗 修改后的代码片断如下清单 4. 针对Cache的优化struct apple
{unsigned long long a;char c[128]; /*32,64,128*/unsigned long long b;
};
测量结果如下图所示图 4. 增加 Cache 时间耗时对比图小小的一行代码尽然带来了如此高的收益不难看出我们是用空间来换时间。当然读者也可以采用更简便的方法 __attribute__((__aligned__(L1_CACHE_BYTES))) 来确定 cache 的大小。 如果对加锁三线程方案中的 apple 数据结构也增加一行类似功能的代码效率也是否会提升呢性能不会有所提升其原因是加锁的三线程方案效率低下的原因不是 Cache 失效造成的而是那把锁。 在多核和多线程程序设计过程中要全盘考虑多个线程的访存需求不要单独考虑一个线程的需求。在选择并行任务分解方法时要综合考虑访存带宽和竞争问题将不同处理器和不同线程使用的数据放在不同的 Cache 行中将只读数据和可写数据分离开。回页首CPU 亲和力 CPU 亲和力可分为两大类软亲和力和硬亲和力。 Linux 内核进程调度器天生就具有被称为 CPU 软亲和力affinity 的特性这意味着进程通常不会在处理器之间频繁迁移。这种状态正是我们希望的因为进程迁移的频率小就意味着产生的负载小。但不代表不会进行小范围的迁移。 CPU 硬亲和力是指进程固定在某个处理器上运行而不是在不同的处理器之间进行频繁的迁移。这样不仅改善了程序的性能还提高了程序的可靠性。 从以上不难看出在某种程度上硬亲和力比软亲和力具有一定的优势。但在内核开发者不断的努力下2.6内核软亲和力的缺陷已经比2.4的内核有了很大的改善。 在双核机器上针对两线程的方案如果将计算 apple 的线程绑定到一个 CPU 上将计算 orange 的线程绑定到另外一个 CPU 上效率是否会有所提高呢 程序如下 清单 5. CPU 亲和力struct apple
{unsigned long long a;unsigned long long b;
};struct orange
{int a[ORANGE_MAX_VALUE];int b[ORANGE_MAX_VALUE];
};inline int set_cpu(int i)
{CPU_ZERO(mask);if(2 cpu_nums){CPU_SET(i,mask);if(-1 sched_setaffinity(gettid(),sizeof(mask),mask)){return -1;}}return 0;
}void* add(void* x)
{if(-1 set_cpu(1)){return NULL;} for(sum0;sumAPPLE_MAX_VALUE;sum){((struct apple *)x)-a sum;((struct apple *)x)-b sum;} return NULL;
}int main (int argc, const char * argv[]) {// insert code here...struct apple test;struct orange test1;cpu_nums sysconf(_SC_NPROCESSORS_CONF);if(-1 set_cpu(0)){return -1;} pthread_create(ThreadA,NULL,add,test);for(index0;indexORANGE_MAX_VALUE;index){sumtest1.a[index]test1.b[index];} pthread_join(ThreadA,NULL);return 0;
}
测量结果为图 5. 采用硬亲和力时间对比图(两线程)其测量结果正是我们所希望的但花费的时间还是比单线程的多其原因与上面分析的类似。 进一步分析不难发现样例程序大部分时间都消耗在计算 apple 上如果将计算 a 和 b 的值分布到不同的 CPU 上进行计算同时考虑 Cache 的影响效率是否也会有所提升呢图 6. 采用硬亲和力时间对比图(三线程)从时间上观察设置亲和力的程序所花费的时间略高于采用 Cache 的三线程方案。由于考虑了 Cache 的影响排除了一级缓存造成的瓶颈多出的时间主要消耗在系统调用及内核上可以通过 time 命令来验证 #time ./unlockcachemultiprocessreal 0m0.834s user 0m1.644s sys 0m0.004s
#time ./affinityunlockcacheprocessreal 0m0.875s user 0m1.716s sys 0m0.008s
通过设置 CPU 亲和力来利用多核特性为提高应用程序性能提供了捷径。同时也是一把双刃剑如果忽略负载均衡、数据竞争等因素效率将大打折扣甚至带来事倍功半的结果。 在进行具体的设计过程中需要设计良好的数据结构和算法使其适合于应用的数据移动和处理器的性能特性。回页首总结 根据以上分析及实验对所有改进方案的测试时间做一个综合对比如下图所示图 7. 各方案时间对比图单线程原始程序平均耗时1.049046s最慢的不加锁三线程方案平均耗时2.217413s最快的三线程( Cache 为128)平均耗时0.826674s效率提升约26%。当然还可以进一步优化让效率得到更高的提升。 从上图不难得出结论采用多核多线程并行设计方案能有效提高性能但如果考虑不全面如忽略带宽、数据竞争及数据同步不当等因素效率反而降低程序执行越来越慢。 如果抛开本文开篇时的限制采用上文曾提到的另外一种数据分解模型同时结合硬亲和力对样例程序进行优化测试时间为0.54s效率提升了92%。 软件优化是一个贯穿整个软件开发周期从开始设计到最终完成一直进行的连续过程。在优化前需要找出瓶颈和热点所在。正如最伟大的 C 语言大师 Rob Pike 所说 如果你无法断定程序会在什么地方耗费运行时间瓶颈经常出现在意想不到的地方所以别急于胡乱找个地方改代码除非你已经证实那儿就是瓶颈所在。 将这句话送给所有的优化人员和大家共勉。转载于:https://www.cnblogs.com/mtcnn/archive/2008/11/28/9410146.html
