本书采用工程理论、工具详解和实际案例分析相结合的方式,全面介绍了英特尔Parallel Studio工具集的使用。全书分三部分:基础部分(第1、2章)介绍了多核架构、并行编程的关键理论,Parallel Studio的特点以及一些简单案例;中级部分(第3~12章)详述了Parallel Studio各个组件的使用,是本书的**;提高部分(第13章)选取了来自英特尔线程挑战赛的4个算例和1个商业软件并行优化案例,提供了从工程实际角度解决并行问题的视角。
本书适合所有对并行开发技术感兴趣的人员,包括具备一定编程经验的程序员、调试人员,计算密集型行业的高性能计算架构师、性能优化分析师,并行开发的研究人员,对英特尔Parallel Studio感兴趣的技术决策者等。此外,本书也可作为高等院校计算机专业并行开发相关课程的培训及社会实践参考 用书。

目 录
第1章 并行开发理论基础
1.1 并行相关概念
1.1.1 并发与并行、并行度
1.1.2 粒度
1.1.3 加速比及其定律
1.1.4 可扩展性与并行效率
1.1.5 负载均衡
1.1.6 吞吐量与延迟
1.1.7 热点与瓶颈
1.2 多核并行
1.2.1 多核软硬件现实
1.2.2 多核架构
1.2.3 多核并行手段
1.2.4 多核并行设计方法
1.2.5 多核多线程系统
1.2.6 多核多线程同步
1.2.7 多核多线程实现的问题
1.3 小结
第2章 英特尔Parallel Studio基础
2.1 英特尔Parallel Studio介绍
2.1.1 英特尔 Parallel Studio背景
2.1.2 英特尔 Parallel Studio的组成
2.1.3 英特尔 Parallel Studio的特色
2.1.4 英特尔 Parallel Studio的使用者
2.2 英特尔Parallel Studio快速上手
2.2.1 英特尔 Parallel Studio的下载安装
2.2.2 选择案例
2.2.3 实践动手**步:采用Parallel Studio运行串行程序
2.2.4 实践动手第二步:选用合适的实现对代码并行化
2.2.5 实践动手第三步:定位错误
2.2.6 实践动手第四步:性能优化
2.3 小结
第3章 英特尔Parallel Composer详解
3.1 Composer概述
3.2 英特尔C/C++编译器
3.2.1 自动并行和OpenMP并行
3.2.2 过程间优化
3.2.3 档案导引优化
3.2.4 编译器向量化
3.3 英特尔并行调试器
3.3.1 英特尔并行调试器概述
3.3.2 线程数据共享侦测
3.3.3 可重入函数调用侦测
3.3.4 SSE寄存器窗口
3.3.5 OpenMP多线程调试
3.3.6 并行区域的串行执行
3.4 英特尔TBB线程构建模块
3.4.1 英特尔TBB概述
3.4.2 功能模块分类与介绍
3.4.3 编译和运行TBB多线程程序
3.5 英特尔IPP性能基元
3.5.1 英特尔IPP概述
3.5.2 主要函数及其功能
3.5.3 编译和运行
3.6 小结
第4章 并行化方法
4.1 基本概念
4.1.1 Amdahl定律
4.1.2 进程与线程
4.2 并行化方法
4.3 并行化设计
4.3.1 任务划分
4.3.2 功能划分
4.3.3 并行化开发中的一些思考
4.4 案例分析:用蒙特卡罗方法计算π值
4.5 小结
第5章 英特尔Parallel Composer案例分析
5.1 案例5-1:Composer的使用——向量化和自动并行化
5.2 案例5-2:并行调试器的使用
5.3 案例5-3:通过TBB进行字符串查找
5.4 案例5-4:IPP压缩和解压缩案例介绍
5.5 小结
第6章 英特尔Parallel Inspector详解
6.1 Inspector概述
6.2 启动Inspectort
6.2.1 工作流程
6.2.2 启动
6.3 配置查找错误的类型和粒度
6.3.1 基于线程的相关错误及粒度
6.3.2 基于内存的相关错误及粒度
6.4 定位和解决发现的错误
6.4.1 检查错误
6.4.2 查看和分析错误
6.5 小结
第7章 软件纠错方法
7.1 基本概念
7.1.1 软件查错或纠错
7.1.2 白盒测试
7.1.3 黑盒测试
7.2 并行软件的纠错
7.3 线程并行的常见错误
7.3.1 线程间死锁
7.3.2 线程间竞争
7.3.3 内存泄露
7.4 小结
第8章 并行软件纠错案例
8.1 案例8-1:线程间相互作用导致的死锁问题
8.2 案例8-2:线程竞争
8.3 案例8-3:内存泄露
8.4 小结
第9章 英特尔Parallel Amplifier详解
9.1 Amplifier概述
9.1.1 如何开始Amplifier
9.1.2 如何使用符号信息
9.1.3 环境和对象
9.2 Amplifier的几个概念
9.3 Amplifier的分析运行
9.3.1 分析运行的几个选项
9.3.2 选择分析模式
9.3.3 如何选择分析模式
9.3.4 如何在命令行下运行分析模式
9.3.5 热点:分析程序哪里耗时
9.3.6 并行度:展现并行程序的另外一个特点
9.3.7 锁和等待:分析程序在哪里等待
9.3.8 选择数据采集的时段
9.4 Amplifier中浏览性能数据结果
9.4.1 总览
9.4.2 在Bottom-up和Top-down中切换
9.4.3 选择和管理栈类型
9.4.4 选择颜色方案
9.4.5 按照不同类型划分组
9.4.6 在命令行模式下查看性能数据
9.5 Amplifier解释性能数据结果
9.5.1 总览
9.5.2 解释热点分析结果
9.5.3 解释并行度分析结果
9.5.4 解释锁和等待分析结果
9.6 Amplifier中的源代码
9.7 Amplifier中对比性能数据结果
9.8 Amplifier中管理结果文件
9.9 小结
第10章 性能优化方法
10.1 性能优化概述
10.1.1 性能和性能优化是计算机领域不变的主题
10.1.2 性能优化的定义
10.2 性能优化通用方法
10.2.1 性能优化的顺序
10.2.2 系统级别的性能优化
10.2.3 应用级别的性能优化
10.2.4 微架构级别的性能优化
10.2.5 性能优化工作循环
10.2.6 性能优化循环的常见问题
10.3 并行应用性能优化方法
10.3.1 概述
10.3.2 减少关键路径上的时间
10.3.3 检查是否选择*优的并行方法
10.3.4 检查是否选择合适的层级开始并行
10.3.5 Amdahl定律的检查:减少串行部分的比例
10.3.6 检查程序的负载均衡问题
10.3.7 检查程序的粒度问题
10.3.8 采用合适的线程库
10.3.9 检查同步性能问题
10.3.10 检查硬件导致的扩展性问题
10.4 小结
第11章 性能优化案例
11.1 IO并行:系统级优化案例
11.2 锁的实现:锁优化案例
11.3 同步与负载均衡:生产消费类型的优化案例
11.4 优化临界区:WinThread循环计算型优化案例
11.5 负载均衡与归约:OpenMP循环计算型优化案例
11.6 线程数,桶数与锁:Hash表与TBB优化案例
11.7 选择合适的层级并行:任务与数据并行优化案例
11.8 避免硬件性能瓶颈:内存与高速缓存优化案例
11.9 算法选择:排序优化与TBB案例
11.10 内存操作TBB优化案例
11.11 小结
第12章 英特尔Parallel Advisor详解
12.1 Advisor基础
12.1.1 Advisor总览
12.1.2 如何开始Advisor
12.2 Advisor工作流程
12.3 Annotations
12.4 Advisor 工具
12.4.1 Survey
12.4.2 Suitability
12.4.3 Correctness
12.5 使用案例
12.5.1 SpMV并行化
12.5.2 DGEMM并行化
12.6 小结
第13章 总体系统化案例
13.1 数独
13.1.1 串行算法
13.1.2 并行优化
13.1.3 小结
13.2 *短路径
13.2.1 串行算法
13.2.2 并行优化
13.2.3 小结
13.3 基数排序
13.3.1 串行算法
13.3.2 并行优化
13.3.3 小结
13.4 骑士巡游
13.4.1 串行算法
13.4.2 并行优化
13.4.3 小结
13.5 商业软件Paraview
13.5.1 问题描述
13.5.2 并行优化
13.5.3 小结
附录A 英文术语表

第1章 并行开发理论基础
为了更好地发挥英特尔Parallel Studio并行开发工具的功能,在介绍这一套件的使用前还需要有一定的理论基础,本章介绍*基本的理论和技术。
1.1 并行相关概念
使用英特尔Parallel Studio的核心是发挥应用的并行性。因此,并行相关概念显得尤为重要。
1.1.1 并发与并行、并行度
并行计算中常见的两个名词:并行与并发。二者有微妙的不同。
并发是指从广义上讲只要同时多任务处理,就是并发;但是并发并不能保证在每一个时刻都有多个任务(线程,进程)同时工作。例如,一个单核处理器平台并且这个平台没有或者没有打开硬件超线程或者多线程功能,在上面运行一个多线程程序,虽然这个程序是并行程序,但是由于处理器资源有限,在任意一个时刻*多只有一个线程是工作的。
并行就不同。并行是指在同一时刻,有多个任务同时运行,才称之为并行。从性能上讲,它体现了并行的计算能力。例如,在一个双核处理器的平台上运行多线程程序,如果并行程序设计得好,在某些时刻,同时运行的线程数应该可以达到二,从而充分利用了处理器多核资源。因此,并行是指无论从微观还是宏观上看,都是多个线程或者进程同时执行,而并发在微观上不是同时执行的,只是把时间分成若干段,使多个进程或线程快速交替地执行。
接下来还有并行度这个概念:在某个时刻同时工作的任务(线程,进程)的数量,称之为并行度。并行度越高,说明同时运行的任务数越多,如果相应的核数合适,可以提高整体的计算能力,充分发挥并行程序的效率。当然有时候也叫并发度,但是基本上都是在微观上表示同时进行的线程/进程的个数。
1.1.2 粒度
粒度是衡量计算与通信大小的度量。具体分为应用的粒度与机器的粒度。一般我们讲的粒度都是针对应用而言。
应用的粒度定义为:应用的计算量与通信量的比。通信量指的是线程之间或者进程之间进行数据共享或者消息传递的开销。
机器的粒度定义为:这个机器的计算能力与通信能力的比。
如果应用是大粒度的,则说明计算量远大于通信量,时间较多地花在计算上,有时也称之为粗粒度。一般而言,任务级并行的粒度大于语句级的并行。例如,OpenMP内层循环语句做并行,是一种小粒度(细粒度)的并行;而任务级别的应用花在同步或者通信上的时间几乎没有,是典型的粗粒度应用。
对于机器而言,如果这个机器是大粒度的,说明它的通信能力与计算能力相比很差,例如采用千兆网络的集群,网络处理能力比处理器的处理能力落后好几个量级。对于细粒度的机器,它的通信能力是相对较强的,例如SMP架构或者NUMA架构的机器,通信能力是内存共享,只与处理器的处理能力相差一到两个量级。
总之,掌握了粒度,对于编写、分析与运行并行程序帮助很大。例如,我们编写的并行代码尽可能采用粗粒度的方法,让计算量远远大于通信量,提高代码的效率;此外,尽量采用合适粒度的架构去运行并行应用。还比如,对于一个细粒度的应用,如果采用粗粒度的机器去运行,效率会很差。因为通信部分本来就是细粒度应用的瓶颈,而粗粒度的机器加剧了这个问题。图1-1提供了一种解决方案,应用与机器的粒度要匹配,超过和不及都不恰当。
1.1.3 加速比及其定律
简单讲,加速比指的是给定的应用,并行程序的并行执行速度相对于串行执行快了多少倍。这个指标始终贯穿于并行化和并行性能的全部,是并行计算的核心。从应用角度出发,不论是开发还是使用,都希望能达到理想的加速比。即随着处理能力的倍数提升,并行应用的执行速度也是相应的倍数提升。
但是在现实世界中,很难有**的加速比。有以下几个定律会与之相关。
Amdal定律:在问题规模一定的前提下,加速比不能随着处理器数目的增加而无限上升,而是受限于串行比例,加速比极限是串行比例的倒数。
Gustafson定律:对于放大问题规模的情况下,加速比几乎与处理器数成比例地线性增长,串行比例不再是加速比的瓶颈。
Amdal定律大家或许接触较多,反映了固定负载的加速公式。
Gustafson定律则反映了对于大型计算可变的负载,如何充分利用处理器性能。也就是说增多处理器必须相应地增大问题规模,
在一般实际应用中,可以考虑加速的经验公式:p/log p ≤S≤ p,这里S为加速比,p为处理器个数。理想情况下是p,但是有时候会出现超线性加速。原因之一是高速缓存。在运行某些大规模问题时,在进程数少的情况下,高速缓存不能放下所有的数据,因此需要和内存打交道,运行时间会变长;在进程数多的情况下,平均每个线程或者进程所分的问题规模会变小,有可能高速缓存可以放下处理的数据,因此运行性能可以大幅提高。当这些高速缓存效应得到的提高大于通信或者同步带来的额外性能损失时,就会造成超线性加速的现象。此外,某些算法也可能导致超线性加速,例如算法随着线程数的增多而朝着性能优化的方向发生变化。
在实际平台上运行并行程序,考虑加速比时还需要考虑系统开销,如线程创建的开销,线程切换的开销,线程销毁的开销;进程通信的开销,进程等待的开销;负载不均衡的开销;等等。随着线程数或者进程数的增多,这部分的比例会随着变大。
1.1.4 可扩展性与并行效率
可扩展性是指并行机或并行算法有效利用多处理器增加的能力的一个度量。随着处理机的增加,如果效率曲线基本保持不变,或略有下降,则认为该算法在所用的并行机上扩展性好;否则,其可扩展性差。影响一个并行算法的扩展性的因素较多,评判的准则也不尽相同。
并行效率是指加速比除以处理器个数,它反映了并行应用的执行效率。
可扩展性是与加速比以及效率紧密相连的。好的扩展性必然是有良好的加速比以及并行效率。
1.1.5 负载均衡
负载均衡在并行计算里指的是将任务分配到并行执行系统中各个计算资源上,使之充分发挥计算能力,没有空闲或等待,也不存在过负载。
好的并行方法可以发挥好的负载均衡效果。负载不均衡就会导致计算效率的下降以及糟糕的扩展性。因此,实现负载均衡是并行计算中的重要方面。特别是��着处理器的增多,负载均衡性很可能随着降低。
负载均衡度用来衡量负载均衡的指标,即各个CPU的平均使用时间/*大CPU使用时间。
在不考虑其他因素时,加速比在负载均衡度为定值时,是线性加速的;如果负载均衡度随着处理器的增多而降低,则加速比无法随着处理器的增加而线性增加。
1.1.6 吞吐量与延迟
吞吐量是指在给定时间里能完成的工作量。延迟是指一个工作量从头到尾做完所用的时间。
吞吐量体现了系统对任务群所能处理的*大值,例如每秒*多能处理的网络报文 数,一个系统的*大带宽数等。延迟体现了单独任务处理的速度,也反映了系统的响应时间,如CPU指令延迟、网络延迟等。
通常对系统的衡量包括吞吐量和延迟。例如,在小于某个延迟下的*大吞吐量就是对系统的一个衡量。
1.1.7 热点与瓶颈
热点是指程序耗时*多的部分。瓶颈是指系统或者程序中*慢的热点部分。
因此,并行化时要看热点,优化时要看瓶颈。
1.2 多核并行
仅仅了解并行概念是不够的,在多核时代,还要了解多核的一些基本概念和架构,以及多核下编程的挑战。
1.2.1 多核软硬件现实
多核成为处理器发展的现实,摩尔定律在多核实现上依旧保持着,也即单位面积上晶体管数量每18个月到24个月翻番。这意味着更多核的集成。从双核到四核到八核甚至到众核。
因此,众所周知,单纯依赖CPU主频的提升而提升软件性能的免费午餐已经结束,需要并行编程利用多核资源。不论是从编程思路还是编程语言,甚至是编程环境,都需要面对新的挑战。很多现有的应用或者没有并行化,或者并行化后在双核上的性能不佳,或者在双核上性能尚可,但是在多核上的加速比越来越差,甚至出现死锁或者饥饿现象。
1.2.2 多核架构
一个物理处理器可以有一系列的资源,包括通用寄存器、控制寄存器、高速缓存、总线、执行单元、分支预测单元等。随着芯片技术的提升,可以在每个CPU封装中实现两套或者多套核心,每个核心有独立的一系列执行资源和微架构的其他资源,也可以共享一些资源,如高速缓存,这种结构就是片上多核处理器。在一台机器上,可以有一个或者多个这样的处理器封装。
以现在流行的英特尔多核架构为例。可分为单路和多路架构,每路有共享缓存以及独立缓存架构;多路架构有SMP架构和NUMA架构。
图1-4就是一个基于前端总线架构的SMP两路服务器(对称多处理器系统)。每个CPU封装有两个独立的高速缓存,每两个计算核心共享一个高速缓存,通过北桥芯片互联,共享内存资源。
再如图1-5是NUMA架构(非一致内存访问)的两路服务器。每个CPU封装中的计算核心采用完全共享高速缓存的方式,并且每个CPU封装把内存控制器放进CPU中,直接和内存相连。CPU之间通过高速协议QPI接口实现高速互联,CPU与外设之间也可以通过QPI高速互联。在多核情况下,可以充分地扩展内存系统带宽,减少内存冲突的开销,提高系统的扩展性和性能。在这种情况下,编程中尽量使用本地内存,避免使用远程内存。
共享高速缓存虽然可以降低内存系统的消息传递,但是多核与单核相比,平均每核占用的缓存容量更少,使得在多核运行下,有时候扩展性“看起来”没那么好。独立高速缓存虽然使得每核占用的缓存数量保持均衡,但是增加了内存总线的冲突,不利于多核的设计和扩展;而且在工作线程不饱满的情况下难以利用全部的缓存。事实上,共享缓存是一个总的趋势。
基本上,在客户端采用单路结构,在服务器端采用多路结构。多路结构可能会引发伪共享的性能问题。
1.2.3 多核并行手段
在一个这样的并行环境中,可以有多种手段实现并行。在单机环境中,可以用多线程方式与多进程方式。在多机分布式环境中,主要是多进程并行方式。本书只涉及单机环境。
多线程方式是内存共享模式的并行编程方式,主要方式有OpenMP的隐式并行、WinThread的显式并行(在Windows环境中)、Pthread显示并行(在Linux环境中)。其他一些上层工具也提供部分并行功能,如TBB、IPP、ACE等。表1-1是主要三种方式的异同比较。
表1-1 多线程并行方法比较
比较类别 TBB WinThread OpenMP
可移植性 ü ü
可扩展性 ü ü ü
初始目的 性能 功能 性能
续表
比较类别 TBB WinThread OpenMP
支持任务并行 ü ü ü
支持数据并行 ü ü ü
渐进式并行化 ü ü
编程层次 高层 底层 高层
串行代码未作修改 ü
调试难度 易 难 易

多进程方式有IPC方式、MPI方式、PVM方式等。主要是通过消息传递实现数据共享。
在单机多核环境下采用多线程手段时,因为内存是共享的,对共享数据的访问不存在访问不了的问题,只存在数据竞争与加锁的问题。而在多进程模式下,每个进程有自己的存储空间,进程之间如果要进行数据共享,必须通过通信来实现数据搬迁。前者影响加速比的因素是数据竞争和同步;后者影响加速比的因素是消息传递的开销。
本书只讨论单机环境下多核的多线程编程。
那么和单核多线程编程相比,有什么不一样呢?单核下的多线程编程更多的是考虑功能,而多核的多线程编程除了考虑功能,更要考虑性能。二者区别如下:
多核下锁竞争导致并行度降低:在单核系统中,如果某个线程获得锁,则这个线程将获得CPU的运行时间,其他线程将被阻塞,得不到CPU的运行时间,因此,在单核系统上,即使使用了锁,影响的也是加锁解锁的时间,CPU自始至终都是处于运行状态,因为只有一个核心。但是在多核系统中,加锁会让其他线程阻塞,从而有可能导致某个CPU核心处于空闲状态,从而并行度降低,甚至串行,影响了性能。
多核下多线程的分解与执行:在单核系统中,多线程的目的通常是创建线程将一些计算放到后台运行,避免阻塞用户界面的操作,看起来用户界面操作和其他计算可以并发进行,提高可操作性。而在多核系统中,多线程的分解与执行,除了提高操作性,更多的是让计算分配到各个计算核心中去执行。
多核下需要考虑负载均衡:在单核系统中,不需要考虑各个CPU的负载均衡问题,即使多线程的各个计算量相差很大,也不会影响程序的计算时间;而在多核系统中,各个线程要把各自的负载分给不同的核心去计算,如果计算量相差很大,则导致一部分计算量小的核心过早计算完而处于空闲状态,也就是导致了饥饿问题。
多核下任务调度策略:在单核系统中,任务调度主要是为了各个任务取得一定的分时效果,或者保证某些任务优先运行,通常由操作系统完成,有时间片轮转、优先级抢占。程序员不需要考虑调度算法,只要安排多线程的优先级即可。但是在多核系统中,多核的调度任务除了满足单核时的那些需求,还要考虑各个任务的耗时问题,需要根据耗时进行合理的安排,均衡地分配到各个核心中。通常操作系统不知道细节,需要程序员设计任务调度策略。
此外,还有伪共享问题,任务优先级抢占问题等。
1.2.4 多核并行设计方法
多核下的并行设计方法主要有数据并行模式、任务并行模式、流水线并行模式、任务调度并行模式、分治模式等。
(1)数据并行模式:是把数据分割成若干相对独立的子数据集,每个线程处理其中一个或者多个子数据集。如果对子数据集的处理时间是相同的,则均匀分割数据就可以了,并且数据子集的数量为CPU的核数的整数倍。如果对单个数据子集的处理时间不相同,就不能采用均匀分割的方式,否则就会负载不均衡。一种解决办法是:分割的数据集数远远大于CPU核数,动态调度从而使得负载均衡。此外,要避免伪共享。
(2)任务并行模式:指的是将一个大任务分解成各自独立的小任务,这些小任务并行执行。对于循环类的任务,通常分解出来的小任务是对等的,容易负载均衡。但是对于天然多任务的大任务而言,各自任务的负载不一定一致,需要考虑负载均衡。尤其是多个不对等的小任务分配给多个CPU核执行时,需要找到*优的分配方案,这就是一个NP难题。
(3)流水线并行模式:一个任务被分解成多个阶段,不同阶段之间的数据有依赖。在并行实现过程中,每个阶段可以多个线程并行工作;对于不同阶段,可以对没有数据相关性的部分实现多线程并行执行。对于数据相关的部分,需要同步地加以保护。
(4)任务调度并行模式:在任务并行中,各个子任务都是彼此独立的;但在实际应用中,任务的执行并非独立的,而是存在执行依赖关系,如何将这些有执行依赖关系的任务集合分给不同CPU核心上去执行是一个调度问题,因此称之为任务调度模式。例如,OpenMP很难将多个任务均匀地分给各个处理器核心,使得各个线程的执行时间大致相同,也不能处理执行有依赖关系的情况。有多种用于任务调度的方案,如WFM、CPM等。主要内容分为两个步骤:先将任务分层,分成n个任务组,然后对每层也就是每个任务组的所有任务进行调度,各个任务组之间串行执行,任务组内部并行执行。此外还可以手工分解任务。
另外,任务在很多情况下不是静态的,而是在运行过程中产生的,那么需要用动态任务调度的模式去设计。例如,服务器每收到客户端的请求都会产生一个任务。这种模式下设计要考虑负载均衡问题。传统的做法有:使用全局共享队列,任务放进队列,处理任务的线程从队列中取任务执行。缺点是要对队列加锁,使得多线程下加速比下降。另外一种方法是工作偷取,方法是每个线程维护自己的队列,当一个线程无法从自己队列获取任务时,选取其他某个线程的队列去读取任务。这样多线程下有多个队列,大多数情况下每个线程只是读取自己队列的任务,不会发生集中式锁竞争现象,相当于使用了分布式锁。
(5)分治模式:是指将一个原问题的求解分解成多个子问题的求解,然后将多个子问题的解通过一定的计算方法合并成原问题的解。例如排序问题,可以将一个大区间的排序分解成若干个小区间的排序问题;求解完毕后用归并的方法合并成大区间的解。子问题求解可能会带来负载不均衡的问题,合并子解时可能引来串行执行的问题。串行比例大的话,会影响加速比。因此,需要采用任务调度方法解决负载均衡问题,需要使用并行合并的方法解决串行问题。
1.2.5 多核多线程系统
设计好的应用,不仅要了解设计方法、结构、多线程的API和编程语言,以及编译器或者运行环境,还要了解运行的平台和系统。
在多核平台上,基本上线程计算模型可以分为三层,从上到下依次是应用级别的线程,内核级别的线程以及硬件线程。因此,一个应用程序的线程会在操作系统级的线程实现,并*终以硬件线程的方式执行。
而在现有流行的操作系统中,系统被分为两个层:应用层和内核层。很多线程库使用的是内核层的线程,如OpenMP、PThread;有些是既支持应用层又支持内核层,例如WinThread。虽然内核层的线程提供更好的性能,但是它们的开销是大于应用层的线程开销的,因此通常采用多种机制**利用,如重用机制、线程池机制。线程的管理工作通常在用户级实现的线程库来支持。这些操作都在用户空间进行,无需内核支持,因此开销比较小。
从应用来看,一个应用可以有一个或者多个进程,每个进程可以有一个或者多个线程,每个线程*终会被操作系统的调度器映射到一个处理器上。这种用户级线程和内核级线程之间的映射机制有很多种,有一对一映射机制,多对一映射机制,以及多对多映射机制。Linux和Windows大多使用一对一映射机制,即每个用户线程映射到一个内核线程,允许进程的多个线程在多处理器上并行运行,当一个线程阻塞时,其他线程仍然可以运行,缺点是创建一个用户线程就要创建一个对应的内核线程,消耗了有限的内核资源,因此系统会限制系统中线程的数目,线程数目过多也会严重影响性能。
从处理器角度看,处理器只知道所有的线程都是来自操作系统的内核级别的线程,虽然这些线程大多是从应用层的线程映射到内核层的。
一个进程可以有多个线程,线程之间相对独立,彼此之间会有一些共享的内存空间和其他一些共享资源,例如文件描述符等。每个线程会有各自私有的栈。如图1-6所示,这些栈通常是由操作系统来管理的,默认有一个栈大小的值,超过了就会有错,特定情况下需要修改这个限制。
一旦一个线程被创建,它总在四个状态的其中一个状态中:准备状态,运行状态,等待状态及结束。关于详细介绍可参考相关的书籍。
1.2.6 多核多线程同步
本书多线程的实现主要是在Windows平台上,因此WinThread和OpenMP是*主要的实现。多线程实现的核心是并行,并行的难点是同步。因为往往会导致程序出错或者效率不高。
那么什么是同步?我们知道多线程的程序设计中需要实现多个线程共享同一段代码,这时,由于线程和线程之间互相竞争CPU资源,会使得线程无序地访问这些共享资源,*终可能导致无法得到正确的结果,这就是竞争。为了保证数据的一致性,避免对共享数据的访问造成数据的不一致性和错误,就需要同步。
同步方法和同步结构有很多,包括但不限于:
• 互斥量;
• 原子操作;
• 临界区;
• 路障;
• 事件;
• 信号量。
互斥是指在同一个时间,同一个地点不能有两件事情同时存在。作为互斥设备,有两个状态:上锁和空闲。同一个时刻只能有一个线程能对互斥量加锁。对于一个已经被加锁的互斥量,另外一个线程试图对它加锁时,该线程会被阻塞,直到该互斥量被释放。在WinThread编程中实现时,主要使用mutex;在OpenMP中,类似的实现如omp_lock_t。
原子操作是指执行指令过程中不可分割的*小单元。比如声明变量的操作、给变量直接赋值的操作,这些都是原子操作,这些操作是**的。在多线程的程序中,一旦将某 个关键代码封装成一个原子操作,那么对它们的操作就不会存在不同步的情况。因此原 子操作或者不执行,或者不分开的执行,这种操作保证了数据的完备性。在WinThread编程中,原子操作有Interlocked函数,例如InterlockedIncrement、InterlockedDeccrement、InterlockedExchange等; 在OpenMP中,类似的实现如#pragma omp atomic。
临界区是一种多线程必须互斥访问的代码段,保证了原子性。一般都是在用户级线程实现的,开销较小。临界区的大小会影响性能,应尽可能分割成小块,提高并行度。在WinThread编程中,用EnterCriticalSection和LeaveCriticalSection实现,在OpenMP中,用#pragma omp critical来实现。
路障是另外一种同步机制。主要用于逻辑计算的控制流操作。通过这种方法,任何线程在一个控���点等待其他所有线程在这个点完成,然后继续下面的处理。这种方法保证了任何一个线程不会在其他线程还没有到达前往下进行。路障的性能因素要考虑,包括线程数的多少和粒度的大小。过细的粒度,或者负载不均衡的多线程,会导致路障有很差的性能。在OpenMP中,路障大部分是隐式实现的,如#pragma omp parallel for在循环结束时会有线程的同步、#pragma omp single、#pragma omp section也类似,还有专门的语句#pragma omp barrier。
有时线程并不是要访问某个受保护的数据或资源,而是需要等待某一事件(event)的发生,这在GUI编程中十分常见。事件主要在WinThread中实现,事件用于一个线程通知另一线程某一事件的发生(发信号表示某一操作已经完成),它是同步对象中形式*简单的一种,而且其同步的机制也是*具有弹性的。事件存在两种状态:激发状态和未激发状态(Signal/True、Unsignal/False)。事件可分为两类,即手动设置与自动恢复;前者需要程序手动设置,如SetEvent以及ResetEvent;后者指一旦事件发生并处理后,自动恢复到没有事件状态。
信号量(Semaphore)也是WinThread的常见同步结构。它也是一个核心对象,拥有计数器,用来管理大量有限的系统资源。当计数器大于零时,信号量为有信号状态;当计数器为零时,信号量处于无信号状态。当线程用信号量对象的句柄作参数来调用等待函数WaitForSingleObject时,系统会检查该信号量所对应的资源数是否大于0(即资源是否可用),若大于0(称为有信号signaled)则减少资源计数并唤醒线程,若等于0(称为无信号nonsignaled)则让线程进入睡眠状态直到(超出指定时间或当指定时间为无限时)占用该资源的其他线程释放资源并增加资源的计数(使信号量大于0,即有信号或有资源可用)为止。通过创建信号量,等待多个对象以及释放信号量方式实现同步。信号量的本质就是PV操作,对应了两个原子操作。典型应用场景是多线程下保护共享资源的使用。例如有n个共享资源,一开始信号量的值是n,当一个线程需要获取一个资源时,就做一个P操作,当资源使用完毕后做一个V操作。
1.2.7 多核多线程实现的问题
首先,多核平台上的多线程编程,面向的是大于等于双核的这类平台。往往出现并行化错误和性能不佳两类问题。
并行化错误包括死锁、活锁、读写脏数据、内存错误等。
性能问题包括CPU饥饿问题、负载均衡问题、加速比扩展性问题。
调试工具除了本书详细介绍的,还有VisualStudio自带的调试工具,以及英特尔的Thread Checker。Thread Checker类似于Parallel Studio中的Inspector。
性能工具除了本书详细介绍的外,还有英特尔Vtune工具、Thread Profiler工具,以及MKL工具。英特尔 Vtune性能分析器可以采集分析并显示上至系统级别,下至源码级别的性能数据,这些数据包括时间数据和微架构数据,以及函数调用关系和用时图。这些性能数据可以帮助查找并消除性能瓶颈,抓到程序热点从而提供并行化思路以及提供微架构中阻碍扩展性的问题。Thread Profiler类似于Parallel Studio中的Amplifier,但是功能更加强大,尤其能提供时间轴展开的各个线程的交互状态图。此外,MKL库是大规模数学核心库,支持多核下多线程的高性能库,和IPP一起提供了强大的性能库支持。
1.3 小结
本章着重介绍了并行开发所需要的基础理论知识。包括并行基本概念、多核硬件架构以及多核编程的并行设计和实现。这些基础知识有助于对后续章节的理解与学习。

第2章 英特尔Parallel Studio基础
本章将通过一个快速上手的案例展示英特尔Parallel Studio的主要功能和使用方法。
2.1 英特尔Parallel Studio介绍
本节只作整体套件的简单介绍,更详细的功能和案例将在后面章节详细展开。
2.1.1 英特尔 Parallel Studio背景
自从多核问世以来,各个硬件厂家逐渐采用多核处理器,多核技术已经成为一种主流。在旧编程模式尚未完全抛弃,新的编程模式还没有定势的情况下,如何能够利用多核的处理能力,是一个挑战性的问题。另一方面,英特尔公司早在单核时代,就开发并购了非常丰富的工具库,这些工具库有些是面向高性能计算的,有些是面向企业级服务器使用的,那么很多工具本身就具有多线程编程或者多进程编程的开发指导功能。随着计算下移,甚至很多笔记本都成为一个小型服务器,使得在这些平台上利用英特尔软件开发工具成为可能。由于英特尔软件开发工具种类繁多,对应的平台也千差万别,面向***的使用阶段也各不一样,掌握这些工具本身就是一件艰难的事情。考虑到Windows平台开发是主流,那么集成这些英特尔工具到具有多核计算能力的Windows开发平台上,就是一件非常有意义的事情。
同时,作为IT的基础厂商,英特尔公司也希望能够通过软件的丰富和性能需求来进一步释放激发这个产业。为此,英特尔公司创新地开发了一套为Windows开发平台Visual Studio定制的Parallel Studio工具集,整合了超过 25 年的并行软件和高性能专门技术,嵌入了从*初开发到*终优化的一系列工具,提供了一系列工具来优化客户端应用,实现了功能的丰富,又相当的易用和简单。
2.1.2 英特尔 Parallel Studio的组成
英特尔Parallel Studio主要包括三个模块:英特尔 Parallel Composer、英特尔 Parallel Inspector以及英特尔 Parallel Amplifier,这三个部分是依次递进开发多线程程序的。此外,还有英特尔 Parallel Advisior,目前单独作为**版本。
英特尔 Parallel Composer主要包含英特尔C/C++编译器、IPP性能库、TBB多线程开发库。编译器中含有OpenMP多线程的支持和自动并行化的支持,IPP库本身具有多线程功能,并且是线程**的,TBB集合了很多多线程算法和数据结构的实现,方便了多线程的开发。英特尔Parallel Debugger Extension可简化并行调试并确保线程的准确性。整个英特尔 Parallel Composer作为英特尔 Parallel Studio的一部分,已经集合到Microsoft Visual C++当中,更加方便Windows平台的开发。
英特尔 Parallel Inspector主要是从英特尔Thread Checker演化而来的,包含多线程正确性的检查和内存正确性的检查。它具有前瞻性,可自动查找潜在的错误。英特尔 Parallel Inspector采用动态技术,不需要特殊的检查工具或者编译器。采用英特尔 Parallel Inspector的好处一目了然,让开发人员从痛苦的多线程调试中解脱出来,让这个工具自动定位和发现错误,提高了开发人员的工作效率。
英特尔Parallel Amplifier主要是从英特尔Thread Profiler演化而来的,是一个性能分析器。能够迅速查找多线程程序在多核/多路下的性能瓶颈,无需了解处理器微架构,无需了解代码的具体算法,省略了大量的推理过程,快速找到问题症结,指明解决问题的方向,告诉使用者软件的扩展性和并行度,从而大大缩减开发人员的开发周期,特别是可以快速提高应用软件本身的性能和效率。
这三个模块是依次使用的,先利用英特尔 Parallel Composer实现*基础的并行化开发工作,然后依赖英特尔Parallel Inspector查找错误并改正,*后再使用英特尔 Parallel Amplifier优化程序,如图2-1所示。
2.1.3 英特尔 Parallel Studio的特色
英特尔 Parallel Studio 为 Microsoft Visual Studio C/C++ 应用程序的开发带来了全面的并行性。英特尔 Parallel Studio 专为软件行业的领先者和***而设计,直接解决他们所关注的问题。这些产品协同工作覆盖整个开发周期,使程序并行性变得****的简单可行。这些工具不仅为刚接触并行化的新手而设计,让他们能够边学边用,同时也能使经验丰富的并行程序员更有效、更自信地工作。英特尔Parallel Studio可与常见的并行编程库和API标准(如英特尔线程构建模块和 OpenMP)实现互操作性,并为实现多核平台的性能优势提供了迅捷的机会。
从当初*开始的测试版本到现在,已经数年有余,英特尔 Parallel Studio的功能和特性也已经完善了,实际上它已经进行了在高端服务器将近30年的开发,并成功下移融入了客户端。
并且,它不仅仅提供了一套工具,在工具背后是方法论,和一整套解决方案:面向多核应用的整体端到端的解决方案,包含了从设计开始,到编码,调试和优化应用,简化开发过程中的所有阶段的实施。
此外,工具集不仅仅面向多核,还为未来的众核开发做准备。
英特尔Parallel Studio工具集既可以让开发人员选择数据并行编程,又可以选择任务级并行编程;既可以在非常底层的代码里并行化,也可以在上层代码区并行化。总之,提供了非常丰富的并行方式。
所有这些,提高了并行开发的工作效率,降低了并行开发的门槛,简化线程并提供减少缺陷和系统性能问题的能力,帮助将性能更好、功能更丰富的产品快速推向市场,加速了软硬件投资的回报。
2.1.4 英特尔 Parallel Studio的使用者
只要是在Windows上编程的开发人员,都适合使用英特尔 Parallel Studio。他们包括(但不局限于)以下几类:多线程编程人员;高性能计算编程人员;性能优化分析师;软件调试工程师;垂直领域科研开发工作者,如数值算法研究,编解码研究;互联网计算密集型应用***;等等。
2.2 英特尔Parallel Studio快速上手
本节只是从简单案例入手,快速介绍Parallel Studio各个模块的大致用法,有些小模块甚至没有用到,目的是展示Parallel Studio的产品的易用性,方便时间有限的读者。如果需要更详细的介绍和案例分析,可详细阅读后面章节。
2.2.1 英特尔 Parallel Studio的下载安装
下载安装英特尔Parallel Studio的步骤如下:
(1)进入英特尔官方软件网站http://software.intel.com/en-us/intel-sdp-home/或者http://software.intel.com/en-us/articles/intel-software-evaluation-center/,单击Intel Parallel Studio,进入注册页面,输入正确的E-mail账号和地区,然后单击download按钮,进入*后的下载页面,单击Intel Parallel Studio(all tools),存到本地。或者使用下载管理器更好。
(2)下载安装包,约几百兆字节。
(3)安装MS Visual Studio 2005。
(4)安装英特尔Parallel Studio,具体组件包括:英特尔Parallel Composer(含英特尔C++ Compiler for 32位和64位,debug扩展以及文档)、英特尔性能基本库IPP(32位和64位),英特尔线程构建模块TBB、英特尔 Parallel Inspector及英特尔 Parallel Amplifier。
2.2.2 选择案例
为了更清楚地介绍各个模块,我们将选择一个范例贯穿整个Parallel Studio的基本使用方法,这里就以N皇后(Queens)问题为例。
NQueen问题是一个很经典的棋盘问题,是数据结构的一个经典算例。在国际象棋棋盘中,放一个皇后,那么在8个方向上就不能再放其他棋子了,但是在别的位置还能放置其他皇后,使她们不会相互攻击。那么在一个大小为N×N的棋盘中,可以放多少个皇后,有多少种方法。
串行算法比较简单,应用试探回溯法,判断行列以及斜线位置是否能放皇后,当可以放置皇后时就继续到下一行,不行的话就返回到下一个要放的位置检查是否能放皇后,如此回溯中前进,如果进行到末尾,就产生一种解决方案。如此反复,直到将所有解解出。
这里棋盘大小size为N,N越大,计算量也越大,放置的方法种类也越多。
2.2.3 实践动手**步:采用Parallel Studio运行串行程序
如何在Windows下实现程序并行化,首先是要能顺利地运行串行程序,并且找到合适的测试案例,在合适的平台上测试出基准性能值,为今后的并行化提供基础参考指标。
此外,要顺利地使用Parallel Studio,了解MS VS和Parallel Studio二者的结合。在运行结果正确之后,还要简要分析串行程序代码的框架,找到合理的热点模块进行分析。因为热点往往是一些函数或者是循环(当然循环里也可以包含函数)。
并行化的原则之一就是二八原则,80%的时间消耗到20%的代码中,当然这只是一个略数。它反映了程序的局部性。在并行化时,就要利用这个特性。我们不必把每句话都并行化,只要能把热点并行化了,就可以达到满意的事半功倍效果,并且,如果对非热点也并行化,可能并行化本身的开销大于并行化这个非热点的收益,从而损失性能,得不偿失。
找到热点仅是**步。并行化往往有负面效果,如多线程下的竞争,因此还需要对共享对象做逐一分析,区分特性,如共享还是私有。
在环境上,这个案例采用的是英特尔酷睿双核CPU L9400,1.86GHz,2GB内存。
(1)打开MS Visual Studio 2005,打开一个project。选择在NQueens-ParallelStudio目录下的NQueens-ParallelStudio.sln。然后单击“确定”按钮,打开开发主界面。
(2)选择使用英特尔编译器,选择solution右击,在图2-2所示的下拉菜单中选择Intel Parallel Composer中的Use Intel C++。当然,如果将来想换回微软的编译器,可以用相同的方式换回。
(3)单击solution浏览器里的step1-Serial-Hotspot,右击,在快捷菜单中选择Set as StartUp Project,如图2-3所示。这时step1-serial-update标为粗黑体,确定当前的操作都在这个子项目中。
(4)运行这个串行程序,选择Debug | Start Without Debugging命令。如果是**次运行,注意output窗口区的信息,是否是英特尔编译器在编译程序,如果不是,说明没有使用英特尔编译器,需要以上的步骤换成英特尔编译器。在运行成功后,显示如图2-4所示。
修改size默认值12,改为15,运行时间很长,344s,查看Windows性能观察器(Performance Monitor)得知,CPU利用率一直保持在50%。为了和今后并行程序的性能做对比,我们修改项目属性,把debug模式改成release模式。*后列出表。
考虑到size为12时,运行时间较少,负载过小也不能反映实际问题,否则就不需要并行化了。而size为15时,运行时间过长,浪费很多等待时间。当size为14时,11s的运行时间较恰当,因此取size为14作为性能基准测试负载,而取size为12作为正确性验证测试。
采用非debug方式运行的原因是:debug模式下的性能非常慢。对于本书而言,性能是我们需要关注的指标。作为一个基准性能指标,我们以非debug模式下的串行程序性能作为基准。
(5)分析这个串行程序。我们发现这个程序有两个函数,solve和它的子函数SetQueen,而SetQueen又是递归调用。我们显示的时间结果其实就是这个程序热点solve的运行时间。仔细看进去,其实就是SetQueen的运行时间。因此,我们下面进行的并行化,就是对这些函数做分析和并行化的。
实践动手**步已经做完。下面可以顺利地使用Parallel Studio完成对串行程序的编译、运行、结果判定、性能记录和代码简单分析了。
2.2.4 实践动手第二步:选用合适的实现对代码并行化
并行化手段只是关注多线程并行化。多线程并行化手段有很多种,对于在MS Visual Studio里,结合Parallel Studio工具,可以使用以下几种方法:OpenMP方法、TBB方法、IPP方法及WinThread方法。研究这个皇后问题,发现比较自然的方式是采用OpenMP或者WinThread方法。这里采用OpenMP方法。
(1)单击solution浏览器里的step2-3-Parallel -Check,在下拉菜单中��中Set as StartUp Project。确定当前工作项目为step2-3-Parallel-Check。
(2)找到nq-parallelstart.cpp,找到solve和SetQueen,根据OpenMP原则,尽可能在*上层实现并行化;因此在solve的SetQueen循环外加入并行制导语句。

void solve() {
// Execute SetQueen loop in parallel
#pragma omp parallel for
for(int i=0; i<size; i++) {
SetQueen(new int[size], 0, i);
}
}

(3)由于英特尔编译器能很好地支持OpenMP的实现,这里转换为使用英特尔编译器。选择solution并右击,在快捷菜单选择Intel Parallel Composer中的Use Intel C++。在Build下拉菜单中选择Configuration Manager,确定这个子项目是debug模式。在子项目的属性(Properties)中,确定C/C++的command Line中有/Qopenmp选项,如果没有,在language选项中的OpenMP Support里加入OpenMp的支持。
(4)执行程序,选择Debug | Start Without Debugging。发现程序运行时间由串行的1266ms缩短为641ms,但是程序提示有错误“incorrect results!”,如图2-5所示。
(5)多次运行这个并行程序,可能不是每次报错。但是只要有一次报错,就存在bug。因此,需要找到并解决掉这个bug。在传统debug方式下,并行程序的debug非常困难,工作效率也非常低。需要对程序的算法有很深的了解。想想这个简单的程序错误可能在 哪里。
在实践动手第二步中,我们选择了合适的并行方式,并且进行了简单的并行化,发现性能提高但是有错误。
2.2.5 实践动手第三步:定位错误
使用Parallel Inspector,可以大大简化debug的工作,提高并行程序开发效率。大部分并行问题都可以使用Parallel Inspector得以发现并解决,包括线程错误和内存错误两大类。
(1)确定当前子项目为step2-3-Parallel-Check,选择Intel Parallel Inspector|Inspect Threading Errors命令,如图2-6所示。
(2)选择命令后弹出新窗口如图2-7所示,有四个选项,不同的选项运行时间不同,*简单的检测“Does my target have deadlocks?”使得程序运行变慢10~40倍;而*复杂的检测“Where are all the threading problems Inspector can find?”使得程序变慢80~320倍。到底选择哪个选项,取决于这个程序负载的运行时间、想要检查错误的详细程度以及你能忍受的时间。因为在这个算例中,size=12运行不到1s,因此可以采用*详细的检查模式。
(3)选择后,单击Run Analysis按钮,程序开始运行,Parallel Inspector实时检查可能的线程错误。打开Windows的性能检测窗口,发现所有CPU都****工作。内存使用也突然加大。那么即使是这么非常小规模的算例,Parallel Inspector为了检查可能的bug,本身也采用了多线程机制,并且消耗大量内存等资源。因此,如果是更大规模的算例,需要Parallel Inspector,*好是在工作站甚至在多路大内存服务器上进行。
(4)当分析结束,程序也结束,Output输出窗口*下行会显示“Threading error analysis: completed”,主窗口也会显示“Analysis completed successfully”,在event log中显示的description一栏中,存在这几个“error:Data race”,这就是我们要找的错误,对应着Source的具体行数:nq-parallelstart.cpp:82。如果我们熟悉并行编程,那么后面的具体分析基本上就不用看,可直接定位问题,修改程序。如果不熟悉,可以单击Interpret Result按钮,分析工具提供了更进一步的说明,如图2-8所示。这里,工具清晰地告诉我们问题所在和原因:读写冲突以及写写冲突,单击X6, X4, X5的+,展开具体说明。所有的问题都是同一行语句“nrOfSolutions++;”,单击Details这个标签,可以发现类似的描述,问题描述是数据竞争的问题。
(5)发现问题,定位问题,找到原因后,解决问题就显得易如反掌。由于nrOfSolutions在*前面声明定义,是一个全局变量,语句nrOfSolutions++是在setqueen函数中,而setqueen在并行区里,因此nrOfSolution被多个线程共享,是一个共享变量,每个线程都会对它又读又写,因此这个语句需要成为临界区(critical section)才能保证数据**。方法有很多种。我们将会在优化部分加以讨论。
(6)用相同的方式进行memory check,这里就不再详述。
综上所述,在实践动手第三步中,使用Parallel Inspector快速地发现了并行程序的问题,提高了并行开发的效率。
2.2.6 实践动手第四步:性能优化
这一步往往是大家所忽略的,当程序并行化后而且结果没有错误,似乎整个开发就结束了,而对性能的好坏没有太在意。在多核时代,为了充分利用CPU资源,提高硬件资源的使用率,需要进一步的优化,提高程序效率。
优化的工具有很多种,在内嵌的Parallel Studio中使用Parallel Amplifier。它能告诉我们程序的并行化效率、并行的扩展性、串行部分的运行时间所占的比例等,以及更详细的信息如哪里的代码段使得程序在等待,哪个部分并行度低等。
(1)确定当前子项目为step4-Parrallel-Tune。由于现在已经完成debug阶段,考虑性能为主,因此一定记住把configuration的debug模式转换成release模式。
(2)注意到并行问题得到解决(这里采用critical方式):

if(row==size-1) {
// Found a solution. nrOfSolutions is a shared/global counter, and should be
// protected in a critical section if setQueen() is run in multiple threads
#pragma omp critical
nrOfSolutions++;
}

(3)进行编译链接,选择Build | Build Step4-Parallel-Tune命令,修改size值为14,以便对照。然后运行程序,Debug | Start Without Debug。时间是6203ms。
(4)由于是双核系统,这个加速比已经非常不错,达到1.83的加速,并行效率是91%。使用Parallel Amplifier观察。首先单击下拉列表框,选择“Concurrency-Where is my concurrency poor?”,如图2-9所示,然后单击左边的Profile按钮,程序开始运行,性能数据开始收集。这个选项的性能数据主要是展示并发度,即程序在多大程度上是并行计算的。工具采用了不同的颜色显示,例如,红色表示利用率低,即运行的线程数少于CPU的核数;绿色表示理想的并行度,即运行的线程数等于CPU的核数;蓝色表示运行的线程数大于CPU的核数。
(5)并行程序并行运行完成后,会在图例上显示并行度的状态,如图2-10所示。
主要时间花在了setQueen里,其中大部分时间是满负荷理想情况工作的,即绿色。只有小部分是红色:即线程数小于核数,这里就是1个线程在工作。如果需要具体的信息,可以右击它,在快捷菜单中选择Show Data as中的Percents and Bar,如图2-11所示。时间就从时间值变为比例。
的确,Poor的值非常小,只有0.692s,Ideal的值为13.665s。图上Idle的意思就是CPU完全空闲状态,Poor表示运行的线程个数少于CPU核数的一半,OK表示使用处理器线程的个数处于处理器核数的51%~85%。Ideal表示使用处理器线程的个数处于处理器核数的86%~115%。Over表示使用处理器线程的个数大于处理器核数的116%。
(6)如图2-13所示是另外一种表现方式。等待时间是0.454s,和Poor的时间类似。这张图还告诉了我们开启的线程数目、核数等。
(7)采用类似的方式,可以在下拉列表中选择Locks and Waits-Where is my program waiting,如图2-14所示,然后单击Profile按钮,等待程序运行和分析结束。用这种方式可以找到Poor的部分是由谁造成的。

图2-13 英特尔Parallel Amplifier并行度总结 图2-14 英特尔 Parallel Amplifier选择运行方式2
(8)结果出来了,如图2-15所示,这是由Critical Section引起的*主要的性能损失,导致单线程模式工作约1s。这里有个问题,为什么和上次采集的值不一样呢?这里是有误差的,因为这种方式需要有更多工具的介入,因而对程序性能影响更大,误差也更大,但大体上是一个量级。
(9)修改critical section,采用更为有效的InterlockedIncrement语句,如下:

//#pragma omp critical
// nrOfSolutions++;
InterlockedIncrement(&nrOfSolutions);

(10)重新编译链接,运行程序,性能对比见表2-2。
表2-2 N皇后固定问题规模运行时间对比
大小(size=n) Release 时间/ms 线程数 方法
14 11 046 1 串行
14 6203 2 Critical Section
14 6125 2 InterlockedIncrement

(11)采用Amplifier采集并行度特性,如图2-16和图2-17所示,性能与Critical Section的实现相比,Poor所占的比例减小,整体时间值从7s降为6s。
在第四步优化中,使用了Parallel Amplifier的各种特性来分析并行程序的并发度,这个应用的实现说明利用工具可以快速地提高并行代码的效率。而且是知其然也知其所以然,对程序整体的扩展性有了量化的了解。
2.3 小结
本章通过一个简单的例子,介绍了Parallel Studio的使用,把一个程序从串行改成并行,在整个应用过程中,在不同阶段采用不同的工具和手段,快速开发,快速定位,快速debug,快速优化,使得开发的效率得到提高,开发出来的程序的性能和效率也得到充分的挖掘和提升。

并行科技 北京并行科技有限公司(以下简称并行科技),是一家专注于高性能计算软件与技术服务的高新技术企业,与英特尔等软硬件厂商有着密切的合作伙伴关系,主要客户包括科研院所、能源、气象、制造、金融、互联网等计算密集型用户。在程序并行化、优化领域,并行科技拥有自主知识产权的Paramon、Paraview专业工具,积累了从搜集应用特征、定位性能瓶颈到分级优化的系统方法,被誉为“性能专家”。同时,并行科技作为英特尔软件代理商,也为用户提供**的英特尔软件技术支持、培训等。 英特尔高性能计算支持团队 英特尔高性能计算支持团队,专注于多核平台和服务器集群的并行应用优化,负责为国内高性能计算和互联网数据**用户,提供应用性能优化、代码并行、应用特征分析、开发工具培训以及并行解决方案建议和评估等工程支持,在石油勘探、制造业、气候气象、生命科学和互联网搜索引擎等大规模并行应用领域积累了丰富的经验。 英特尔软件工具技术顾问团队 英特尔软件工具技术顾问团队,由英特尔各领域专家组成,为所有英特尔软件工具,如C/C++编译器、Fortran编译器、VTune性能分析器、核心数学库、英特尔Parallel Studio等,提供专业的售前、售后服务,并提供相关技术的**培训。