多核多线程期末考试复习完美总结

1、微处理器发展史 1945年，世界上第一台全自动电子数字计算机ENIAC。 处理器发展 第一代（19711973）：4 位或 8 位微处理器。代表：8008 第二代（19741977）：集成度提高1-4倍，运算速度提高10-15倍。代表：Z80，8080 第三代（19781984）：16位。代表：8086 第四代(19851992）：32 位微处理器，代表80386 第五代微处理器(19931995 年)，64位数据总线，32位地址总线，CPU内部采用超标量流水线设计，代表： 奔腾，K5，powerpc 第六代（19932002)：350nm以下工艺微处理器，平行并发计算而设计(EPIC)架构，

2、代表：安腾 多核时代（2002今）：从2002年超线程技术开始的多核时代，代表：酷睿2北京科技大学天津学院-信息工程系2 2多核概念 单芯片多处理器（Chip Multiprocessors，简称CMP），CMP是由美国斯坦福大学提出的，其将大规模并行处理器中的SMP（对称多处理器）集成到同一芯片内，各个处理器并行执行不同的进程。 CMP vs SMT 同时多线程（Simultaneous Multithreading，简称SMT），是在单物理核上增加部分硬件资源，映射单物理核为多个物理核的技术。最早在P4处理器中出现，命名为超线程（Hyper Threading）。 由于CMP结构已经被划分

3、成多个处理器核来设计，每个核都比较简单，有利于优化设计，因此更有发展前途。并行计算的弗林分类 Flynn根据指令流和数据流的不同组织方式，把计算机系统的结构分为以下四类： 单指令流单数据流（Single Instruction stream Single Data stream, SISD） 单指令流多数据流（Single Instruction stream Multiple Data stream, SIMD） 多指令流单数据流（Multiple Instruction stream Single Data stream, MISD） 多指令流多数据流（Multiple Instructi

4、on stream Multiple Data stream, MIMD）北京科技大学天津学院-信息工程系多线程技术 进程与线程 程序是指令的有序集合，是一个静态的概念。 进程是正在被执行的程序，是系统进行资源分配和调度的一个独立单位，是一个动态的概念。 线程是程序的有序控制流，是被执行的指令序列。 线程属于进程，线程运行在进程空间内。 每个进程至少包含一个主线程，负责对进程进行初始化并开始执行初始指令，创建其他子线程。北京科技大学天津学院-信息工程系数据段数据段代码段代码段堆栈堆栈主线程主线程堆栈堆栈线程线程1堆栈堆栈线程线程Ncilk_spawn and cilk_sync cilk_sp

5、awncilk_spawn (or _Cilk_spawn_Cilk_spawn) gives the runtime permission to run a child function asynchronously. No 2nd thread is created or required! If there are no available workers, then the child will execute as a serial function call. The scheduler may steal the parent and run it in parallel wit

6、h the child function. The parent is not guaranteed to run in parallel with the child. cilk_synccilk_sync (or _Cilk_sync_Cilk_sync) waits for all children to complete.Anatomy of a spawnvoid f()void f() cilk_spawn g(); cilk_spawn g(); work work work work work work cilk_sync; cilk_sync; work work void

7、g()void g() work work work work work work spawning function (parent)continuationspawned function (child)spawnsyncWork Stealingwhen another worker is availablevoid f()void f() cilk_spawn g(); cilk_spawn g(); work work work work work work cilk_sync; cilk_sync; work work void g()void g() work work work

8、 work work work Worker AWorker BWorker ?steal!Intel Parallel AdvisorOffers guidance through the methodology. Annotation Wizard assists with the creation and insertion of Advisor annotations.Intel Parallel Studio 20119 Family of Parallel Programming Models Intel Parallel Advisor parallelism design in

9、novation General Enhancements Supports Visual Studio 2010多线程技术 进程与线程的主要区别在于： 进程拥有独立的地址空间，而线程和其他线程共享进程的地址空间。 进程之间的通信可以使用操作系统原语或通过共享存储空间来实现，而线程使用当前程序设计语言的原语或者通过进程共享空间来实现通信。 进程上下文的切换是重量级的，进程所有状态都要保存。而线程之间的切换是轻量级的，只需要保存当前寄存器的状态。北京科技大学天津学院-信息工程系多线程技术 线程的状态及其转换北京科技大学天津学院-信息工程系新建新建就绪就绪终止终止执行执行阻塞阻塞进入进入调度调度超

10、时超时结束结束事件发生事件发生等待事件等待事件普通普通用户用户软件设计师软件设计师操作系统操作系统设计师设计师计算机硬件计算机硬件操作系统操作系统实用程序实用程序应用程序应用程序用户与操作系统的关系用户与操作系统的关系多核程序开发流程开始开始1.问题描述问题描述3.确定分解模确定分解模式式2.是否具有并行性是否具有并行性和并行价值和并行价值4.设计并行算设计并行算法法5.选取一种编程模型进行实现选取一种编程模型进行实现6.性能调优性能调优结束结束是是否否第二部分第二部分编程模型与实现编程模型与实现第一部分第一部分多核程序设计多核程序设计第三部分第三部分性能调优性能调优多核程序设计 3.分解模式

11、 任务分解 数据分解 数据流分解北京科技大学天津学院-信息工程系任务分解美化美化筑墙筑墙屋顶屋顶叠瓦叠瓦安装电气安装电气石膏板石膏板外部墙修饰外部墙修饰 示例：建造房屋 许多问题可被理解为在一个核心数据结构上的一系列操作。许多问题可被理解为在一个核心数据结构上的一系列操作。 结构中的所有元素在计算中被更新或被使用结构中的所有元素在计算中被更新或被使用 数据结构被分为连续的子结构或子区域。数据结构被分为连续的子结构或子区域。 Arrays: divide along one or more dimensions Lists: define sublists of discrete element

12、s Graphs: construct subgraphs数据分解数据分解任务分解vs数据分解 示例：园丁工作包括翻地和除草。 任务分解：两个园丁分别完成各自功能，但在工作中也需要项目协调，两个园丁不能对同一个地方又翻地又除草。 数据分解：将草坪划分成两半，各自完成一半草坪的翻地和除草工作。 在计算领域，采用哪种分解形式更高效取决于问题本身的限制。如果需要修剪草坪的地块非常小以至于没必要用两个人修剪，修剪草坪最好只被分配给一个园丁做，任务分解是最好的选择。数据分解或许适用于其他的任务序列，例如当修剪草坪完成后，两个园丁并行地铲除杂草。北京科技大学天津学院-信息工程系数据流分解 将一个复杂的过程

13、划分成多个任务，这些任务按照某种顺序执行，这种分解方式成为数据流分解。例如一个任务需要另一个任务的输出结果，只有产生输出结果的任务执行完毕，这个任务才能继续执行。 示例：一个园丁承担准备工具任务，他要完成为割草机加油，清扫剪刀等工作。直到这些准备工作就绪后，其他工作才能开始。著名例子是生产者消费者问题。北京科技大学天津学院-信息工程系多核程序设计 4.相关性分析 解决数据依赖关系可能更复杂 最简单的例子是没有依赖 处理任务之间的数据依赖关系的战略： 变量本地化 改造变量 规约 明确的同步机制北京科技大学天津学院-信息工程系多核程序设计 5.数据竞争 明显表征是内存冲突，多个线程同时访问同一内存

14、空间，且至少有一个线程对该内存进行更新操作。 “抢椅子”游戏 读写冲突、写写冲突 当多个线程访问同一资源时，需要以某种顺序来确保该资源某一时刻只能被一个线程使用，这种对线程的执行顺序进行强制性限制的机制称为同步。北京科技大学天津学院-信息工程系常用的同步机制常用的同步机制 临界区（临界区（critical section） 信号量（信号量（semaphore） 互斥量（互斥量（mutex） 栅障（栅障（barrier） 锁的粒度锁的粒度 死锁死锁线程同步线程同步目录 基本线程技术 Thread类 同步互斥访问 新特性 concurrent工具包基本线程技术创建线程 使用java.lang.Th

15、read类或者java.lang.Runnable接口编写代码来定义、实例化和启动新线程 继承Thread类，重写run( )方法，然后通过start()方法去启动线程 实现Runnable接口，重写run( )方法，然后将其交由Thread去执行基本线程技术Thread类 Thread类实现了Runnable接口 关键属性 private char name; /线程名字 private int priority; /线程的优先级 private boolean daemon = false;/是否是守护线程 setDeamon(true) private Runnable target;

16、/What will be run public final static int MIN_PRIORITY = 1; public final static int NORM_PRIORITY = 5;/The default priority that is assigned to a thread. public final static int MAX_PRIORITY = 10;Thread类 常用方法 start方法/启动一个线程当调用start方法后，系统才会开启一个新的线程来执行用户定义的子任务，在这个过程中，会为相应的线程分配需要的资源 run方法不需要用户来调用的，通过st

17、art方法启动一个线程之后，当线程获得了CPU执行时间，便进入run方法体去执行具体的任务。 sleep方法/让线程睡眠一个时间段，让CPU去执行其他的任务 yield方法/交出CPU权限它跟sleep方法类似，但是调用yield方法并不会让线程进入阻塞状态，而是让线程回到可运行状态，以允许具有相同优先级的其他线程获得运行机会，这一点是和sleep方法不一样的Thread类 join方法/合并线程A线程中调用B.join(t)，则A线程会等B线程执行t时间后执行，若调用无参join方法，则等待B线程执行完后A线程继续执行，A、B线程合并。 interrupt方法/中断线程中断处于阻塞状态的线程

18、。 stop方法 destroy方法 currentThread静态方法用来获取当前线程eg. System.out.println(Thread.currentThread().getName(); System.out.println(Thread.currentThread().getID();线程状态转换同步互斥访问问题引出OUTPUT : Thread-0窗口出售一张，剩余票数: 2Thread-1窗口出售一张，剩余票数: 2Thread-2窗口出售一张，剩余票数: 1Thread-3窗口出售一张，剩余票数: 0Thread-1窗口出售一张，剩余票数: -2Thread-0窗口出售一

19、张，剩余票数: -2 定义：多个进程均需要访问的变量称为定义：多个进程均需要访问的变量称为公共变量公共变量( (shared variable) shared variable) ； 定义：访问共享变量的程序段称作定义：访问共享变量的程序段称作临界区临界区域域( (critical region),critical region),也称为临界段也称为临界段( (critical critical section)section)。 临界区临界区 线程互斥是线程之间所发生的一种间接性相互作用线程互斥是线程之间所发生的一种间接性相互作用, ,这种相互作用是进程本身不希望的这种相互作用是进程本身不希

20、望的, ,也是运行线程感也是运行线程感觉不到的。线程互斥可能发生在相关线程之间觉不到的。线程互斥可能发生在相关线程之间, ,也可也可能发生在不相关进程之间。能发生在不相关进程之间。 互斥量（互斥量（MutexMutex）作为一种互斥设备，有两个状态，作为一种互斥设备，有两个状态，上锁和空闲。同一时刻只能有一个线程能够对互斥上锁和空闲。同一时刻只能有一个线程能够对互斥量加锁。对于一个已经被加锁的互斥量，当另外一量加锁。对于一个已经被加锁的互斥量，当另外一个线程试图对它加锁时，该线程会被阻塞，直到该个线程试图对它加锁时，该线程会被阻塞，直到该互斥量被释放。互斥量被释放。 互斥量是一种锁，线程对共享

21、资源进行访问之前必互斥量是一种锁，线程对共享资源进行访问之前必须先获得锁，否则，线程保持等待状态，直到锁可须先获得锁，否则，线程保持等待状态，直到锁可用，只有其他线程都不占有它时，一个线程才可以用，只有其他线程都不占有它时，一个线程才可以占有它。占有锁的过程叫做锁定或者获得互斥量。占有它。占有锁的过程叫做锁定或者获得互斥量。线程互斥线程互斥 信号量与信号量与PV操作：包括一种称作信号灯类型的变量以及对操作：包括一种称作信号灯类型的变量以及对于此种变量所能进行的两个操作：即于此种变量所能进行的两个操作：即P(wait,减量操作减量操作)操作操作和和V（signal,增量操作）操作。增量操作）操作

22、。wait(s) signal(s) s-; s+; if(s 0) if(s = 0) add to S.L; remove from S.L; block(); wakeup(); 信号量使用基本要求信号量使用基本要求: 必需置一次且只能置一次初值必需置一次且只能置一次初值, 而且初值必需为非负整数而且初值必需为非负整数; 只能执行只能执行P操作和操作和V操作操作, 所有其它操作均是非法的。所有其它操作均是非法的。信号量信号量 线程互斥是线程之间所发生的一种间接性相互作用线程互斥是线程之间所发生的一种间接性相互作用, ,这种相互作用是进程本身不希望的这种相互作用是进程本身不希望的, ,也是

23、运行线程感也是运行线程感觉不到的。线程互斥可能发生在相关线程之间觉不到的。线程互斥可能发生在相关线程之间, ,也可也可能发生在不相关进程之间。能发生在不相关进程之间。 互斥量（互斥量（MutexMutex）作为一种互斥设备，有两个状态，作为一种互斥设备，有两个状态，上锁和空闲。同一时刻只能有一个线程能够对互斥上锁和空闲。同一时刻只能有一个线程能够对互斥量加锁。对于一个已经被加锁的互斥量，当另外一量加锁。对于一个已经被加锁的互斥量，当另外一个线程试图对它加锁时，该线程会被阻塞，直到该个线程试图对它加锁时，该线程会被阻塞，直到该互斥量被释放。互斥量被释放。 互斥量是一种锁，线程对共享资源进行访问之

24、前必互斥量是一种锁，线程对共享资源进行访问之前必须先获得锁，否则，线程保持等待状态，直到锁可须先获得锁，否则，线程保持等待状态，直到锁可用，只有其他线程都不占有它时，一个线程才可以用，只有其他线程都不占有它时，一个线程才可以占有它。占有锁的过程叫做锁定或者获得互斥量。占有它。占有锁的过程叫做锁定或者获得互斥量。线程互斥线程互斥3333多核概念 单芯片多处理器（Chip Multiprocessors，简称CMP），CMP是由美国斯坦福大学提出的，其将大规模并行处理器中的SMP（对称多处理器）集成到同一芯片内，各个处理器并行执行不同的进程。 CMP vs SMT 同时多线程（Simultaneo

25、us Multithreading，简称SMT），是在单物理核上增加部分硬件资源，映射单物理核为多个物理核的技术。最早在P4处理器中出现，命名为超线程（Hyper Threading）。 由于CMP结构已经被划分成多个处理器核来设计，每个核都比较简单，有利于优化设计，因此更有发展前途。两个处理器 vs. 双核双核 两个核在一个芯片内直接连接 多线程和多进程自动并行处理 热量消耗增加的很少 封装成本降低两个处理器两个处理器 两个分开的芯片通过外在系两个分开的芯片通过外在系统总线连接统总线连接 需要外在软件支持需要外在软件支持 更多的热量消耗更多的热量消耗超线程技术与多核体系结构的区别两个线程在支

26、持超线程技术的处理器上执行两个线程在双核处理器上并行执行两个线程在双核处理器上并行执行创建线程的创建线程的APIHANDLE CreateThread( LPSECURITY_ATTRIBUTES ThreadAttributes, DWORD StackSize, LPTHREAD_START_ROUTINE StartAddress, LPVOID Parameter, DWORD CreationFlags, LPDWORD ThreadId ); 参数参数1：指向：指向SECURITY_ATTRIBUTES结构的指针。该线程内核对象的默认安全结构的指针。该线程内核对象的默认安全属性，设

27、置为属性，设置为NULL。 参数参数2：设定线程可以将多少地址空间用于它自己的：设定线程可以将多少地址空间用于它自己的堆栈，堆栈，0为默认值。为默认值。 参数参数3：指明要线程执行的线程：指明要线程执行的线程执行函数执行函数地址。地址。多核程序设计 5.数据竞争 明显表征是内存冲突，多个线程同时访问同一内存空间，且至少有一个线程对该内存进行更新操作。 “抢椅子”游戏 读写冲突、写写冲突 当多个线程访问同一资源时，需要以某种顺序来确保该资源某一时刻只能被一个线程使用，这种对线程的执行顺序进行强制性限制的机制称为同步。北京科技大学天津学院-信息工程系 例：例：如果一个进程有一个共享变量如果一个进程

28、有一个共享变量counter，两个两个线程线程producer和和consumer，线程线程producer执行执行counter+，线程线程consumer执行执行counter-，这两个这两个操作都需要多个机器指令来完成，操作都需要多个机器指令来完成，Counter=5counter+ counter-register1=counter register2=counterregister1=register1+1 register2=register2-1counter=register1 counter= register2可能的序列：可能的序列：Producer: register1=

29、counter (register1=5)Producer: register1=register1+1 (register1=6)Consumer: register2=counter (register2=5)Consumer: register2= register2-1 (register2=4)Producer: counter= register1 (counter=6)Consumer: counter= register2 (counter=4)数据竞争数据竞争 例：一个图书馆管理系统例：一个图书馆管理系统, , 连有两个终端连有两个终端, , 用户可通过终端借用户可通过终端借

30、书书. . 为简化问题为简化问题, , 假设所有用户借阅的图书是相同的假设所有用户借阅的图书是相同的. . 设设x x代代表图书的剩余数量表图书的剩余数量, , 为两个终端用户服务的程序为两个终端用户服务的程序 线程同步线程同步常用的同步机制常用的同步机制 临界区（临界区（critical section） 信号量（信号量（semaphore） 互斥量（互斥量（mutex） 栅障（栅障（barrier） 锁的粒度锁的粒度 死锁死锁线程同步线程同步同步例子：同步例子：要求要求: (1): (1)关车门后方能启动车辆关车门后方能启动车辆; ; (2) (2)到站停车后方能开车门到站停车后方能开车门

31、. . 线程同步线程同步 定义：多个进程均需要访问的变量称为定义：多个进程均需要访问的变量称为公共变量公共变量( (shared variable) shared variable) ； 定义：访问共享变量的程序段称作定义：访问共享变量的程序段称作临界区临界区域域( (critical region),critical region),也称为临界段也称为临界段( (critical critical section)section)。 临界区临界区 所有所有n n个进程竞争使用一些共享的数据。个进程竞争使用一些共享的数据。 每个进程有一个代码段每个进程有一个代码段, ,称为临界区称为临界区,

32、,在那儿共享在那儿共享数据被访问。数据被访问。 问题问题: :保证当一个进程正在临界区执行时，没有另保证当一个进程正在临界区执行时，没有另外的进程进入临界区执行。外的进程进入临界区执行。 解决临界区问题需满足解决临界区问题需满足 互斥：假定进程互斥：假定进程PiPi在其临界区内执行，其他任何线程将被排在其临界区内执行，其他任何线程将被排斥在自己的临界区之外斥在自己的临界区之外. . 有空让进：临界区没有线程执行，有些线程需要进入临界区，有空让进：临界区没有线程执行，有些线程需要进入临界区，不能无限期地延长下一个要进入临界区进程的等待时间不能无限期地延长下一个要进入临界区进程的等待时间. . 有

33、限等待：在一个线程提出进入临界区的请求和该请求得到有限等待：在一个线程提出进入临界区的请求和该请求得到答复的时间内，其他线程进入临界区前的等待时间必须是有答复的时间内，其他线程进入临界区前的等待时间必须是有限的。限的。临界区临界区临界区const int n = /* number of threads */;void P(int i)while(true)entercritical(i); 进入区进入区/* critical sectioin */临界区临界区exitcritical(i); 退出区退出区/* remainder */ 剩留区剩留区 线程互斥是线程之间所发生的一种间接性相互作

34、用线程互斥是线程之间所发生的一种间接性相互作用, ,这种相互作用是进程本身不希望的这种相互作用是进程本身不希望的, ,也是运行线程感也是运行线程感觉不到的。线程互斥可能发生在相关线程之间觉不到的。线程互斥可能发生在相关线程之间, ,也可也可能发生在不相关进程之间。能发生在不相关进程之间。 互斥量（互斥量（MutexMutex）作为一种互斥设备，有两个状态，作为一种互斥设备，有两个状态，上锁和空闲。同一时刻只能有一个线程能够对互斥上锁和空闲。同一时刻只能有一个线程能够对互斥量加锁。对于一个已经被加锁的互斥量，当另外一量加锁。对于一个已经被加锁的互斥量，当另外一个线程试图对它加锁时，该线程会被阻塞

35、，直到该个线程试图对它加锁时，该线程会被阻塞，直到该互斥量被释放。互斥量被释放。 互斥量是一种锁，线程对共享资源进行访问之前必互斥量是一种锁，线程对共享资源进行访问之前必须先获得锁，否则，线程保持等待状态，直到锁可须先获得锁，否则，线程保持等待状态，直到锁可用，只有其他线程都不占有它时，一个线程才可以用，只有其他线程都不占有它时，一个线程才可以占有它。占有锁的过程叫做锁定或者获得互斥量。占有它。占有锁的过程叫做锁定或者获得互斥量。线程互斥线程互斥无互斥量 可能的输出：A Hello oneB Hello oneB Hello twoA Hello two创建线程的创建线程的APIHANDLE

36、CreateThread( LPSECURITY_ATTRIBUTES ThreadAttributes, DWORD StackSize, LPTHREAD_START_ROUTINE StartAddress, LPVOID Parameter, DWORD CreationFlags, LPDWORD ThreadId ); 参数参数4：传递给创建线程的：传递给创建线程的参数参数。 参数参数5：如果值为：如果值为0，线程创建后可以立即执行。，线程创建后可以立即执行。 参数参数6：存放新线程的：存放新线程的ID，对线程，对线程ID不感兴趣可设置不感兴趣可设置NULL。线程执行函数线程执行函

37、数MyThreadStart(LPVOID p)即为线程执行函数，函数名自拟。即为线程执行函数，函数名自拟。l释放操作系统资源释放操作系统资源在程序结束前要清除线程及其所占资源在程序结束前要清除线程及其所占资源l线程退出调用函数：线程退出调用函数：BOOL CloseHandle(HANDLE hObject);线程退出线程退出l等待函数：等待函数： DWORD WaitForSingleObject( HANDLE hHandle, DWORD dwMilliseconds );参数参数1：hHandle表示一个能够支持已通知表示一个能够支持已通知/未通知状态的内未通知状态的内核对象；核对象

38、；参数参数2：dwMilliseconds指为了等待该对象变为已通知状指为了等待该对象变为已通知状态，将等待多长时间。态，将等待多长时间。l等待终止条件：等待终止条件：过了预定时间过了预定时间dwMilliseconds使用使用INFINITE参数，表示线程永远等下去，直到该进程中参数，表示线程永远等下去，直到该进程中止。止。Waiting for a Threadl等待函数：等待函数： DWORD WaitForMultipleObjects(DWORD dwCount, CONST HANDLE *lpHandles, BOOL fWaitAll, DWORD dwMilliseconds

39、);参数参数1：dwCount指要让函数查看的内核对象数量；指要让函数查看的内核对象数量；参数参数2：phObjects是指向内核对象句柄的数组的指针；是指向内核对象句柄的数组的指针；参数参数3：fWaitAll为为TRUE时，该函数只有当指定的所有内时，该函数只有当指定的所有内核对象都变为已通知状态才返回；为核对象都变为已通知状态才返回；为FALSE时，该函数只时，该函数只要指定的内核对象中有一个变为已通知状态即返回；要指定的内核对象中有一个变为已通知状态即返回；参数参数4：dwMilliseconds作用同作用同WaitForSingleObject。Waiting for Many Th

40、read 全局变量全局变量 进程中的所有线程均可以访问所有的全局变量，因而全局进程中的所有线程均可以访问所有的全局变量，因而全局变量成为变量成为Win32多线程通信的最简单方式。多线程通信的最简单方式。 事件事件 事件事件(Event)是是WIN32提供的最灵活的线程间同步方式。提供的最灵活的线程间同步方式。 事件存在两种状态：事件存在两种状态： 激发状态激发状态(signaled or true) 未激发状态未激发状态(unsignal or false) 事件可分为两类：事件可分为两类： 手动设置：这种对象只能用程序来手动设置，在需要该事件或者事手动设置：这种对象只能用程序来手动设置，在需

41、要该事件或者事件发生时，采用件发生时，采用SetEvent及及ResetEvent来进行设置。来进行设置。 自动恢复：一旦事件发生并被处理后，自动恢复到没有事件状态，自动恢复：一旦事件发生并被处理后，自动恢复到没有事件状态，不需要再次设置。不需要再次设置。Win32线程同步的实现线程同步的实现l事件对象也属于内核对象，包含一个使用计数，一个事件对象也属于内核对象，包含一个使用计数，一个用于指明该事件是一个自动重置的事件还是一个人工用于指明该事件是一个自动重置的事件还是一个人工重置的事件的布尔值，另一个用于指明该事件处于已重置的事件的布尔值，另一个用于指明该事件处于已通知状态还是未通知状态的布尔

42、值。通知状态还是未通知状态的布尔值。l有两种不同类型的事件对象。一种是人工重置的事件，有两种不同类型的事件对象。一种是人工重置的事件，另一种是自动重置的事件。当人工重置的事件得到通另一种是自动重置的事件。当人工重置的事件得到通知时，等待该事件的所有线程均变为可调度线程。当知时，等待该事件的所有线程均变为可调度线程。当一个自动重置的事件得到通知时，等待该事件的线程一个自动重置的事件得到通知时，等待该事件的线程中只有一个线程变为可调度线程。中只有一个线程变为可调度线程。事件事件事件事件HANDLE CreateEvent ( LPSECURITY_ATTRIBUTES lpEventAttribu

43、tes, BOOL bManualReset, BOOL bInitialState, LPCSTR lpName); lbManualReset能够告诉系统是创建一个人工重置能够告诉系统是创建一个人工重置的事件的事件 （TRUE），还是创建一个自动重置的事件），还是创建一个自动重置的事件（ FALSE ）。）。lbInitialState 指明该事件是要初始化为已通知状态指明该事件是要初始化为已通知状态（TRUE），还是未通知状态（），还是未通知状态（FALSE）。）。l调用调用SetEvent时，可以将事件改为已通知状态：时，可以将事件改为已通知状态：BOOL SetEvent( HAND

44、LE event );l调用调用ResetEvent时，可以将该事件改为未通知状态：时，可以将该事件改为未通知状态：BOOL ResetEvent( HANDLE event );l人工重置事件是指通过人工重置事件是指通过SetEvent和和ResetEvent来设置来设置事件的通知状态，而自动重置事件的含义是：当事件事件的通知状态，而自动重置事件的含义是：当事件被被SetEvent函数设置为已通知状态时，在等待事件的函数设置为已通知状态时，在等待事件的线程中，只有一个线程被恢复，之后系统自动将事件线程中，只有一个线程被恢复，之后系统自动将事件置为未通知状态。置为未通知状态。事件事件Examp

45、le: EventsDWORD WINAPI threadFunc(LPVOID arg) BOOL bFound = bigFind() ; if (bFound) SetEvent(hObj0); / signal data was found bigFound() ; moreBigStuff() ; return 0;HANDLE hObj2; / 0 is event, 1 is threadExample: Main function. . . hObj0 = CreateEvent(NULL, FALSE, FALSE, NULL); hObj1 = CreateThread(N

46、ULL,0,threadFunc,NULL,0,NULL); DWORD waitRet = WaitForMultipleObjects(2, hObj, FALSE, INFINITE); switch(waitRet) case WAIT_OBJECT_0: / event signaled printf(found it!n); WaitForSingleObject(hObj1, INFINITE) ; case WAIT_OBJECT_0+1:/ thread signaled printf(thread donen); break ; default: printf(wait e

47、rror: ret %un, waitRet); break ; OpenMP编程技术循环并行化 循环并行化编译指导语句的格式#pragma omp parallel for clauseclausefor（index=first;test_expression; increment_expr）body of the loop; parallel关键字将紧跟的程序块扩展为若干完全等同的并行区域，每个线程拥有完全相同的并行区域； 关键字for则将循环中的工作分配到线程组中，线程组中的每一个线程完成循环中的一部分内容。 OpenMP编程技术循环并行化北京科技大学天津学院-信息工程系#pragma

48、omp parallel#pragma omp for for (i=0; iN; i+)Do_Work(i);#pragma omp parallel#pragma omp forImplicit barrieri = 0i = 1i = 2i = 3i = 4i = 5i = 6i = 7i = 8i = 9i = 10i = 11#pragma omp parallel#pragma omp for for(i = 0; i 12; i+) ci = ai + bi;OpenMP编程技术循环并行化 这两种方式是等价的：北京科技大学天津学院-信息工程系#pragma omp paralle

49、l #pragma omp for for (i=0; i MAX; i+) resi = huge(); #pragma omp parallel for for (i=0; i MAX; i+) resi = huge(); 循环并行化语句的限制 循环并行化语句必须是for循环语句并具有规范的格式: for （index = start ; index end ; increment_expr） 能够推测出循环的次数，有以下约束 ： 循环语句中的循环变量必须是有符号整型； 循环语句中的比较操作必须是这样的形式：loop_variable , 或= loop_invariant_intege

50、r； 循环语句中的第三个表达式（for循环的循环步长）必须是整数加或整数减，加减的数值必须是一个循环不变量（loop invariant value）； 如果比较操作是或或=，那么循环变量的值在每次迭代时都必须减少； 循环必须是单入口、单出口的，循环内部不允许有能够到达循环之外的跳转语句。 简单循环的并行化 两个向量相加，并将计算的结果保存到第三个向量中，向量的维数为n。向量相加即向量的各个分量分别相加。 for（int i=0; in; i+） zi = xi + yi; 使用循环并行化编译指导语句直接对循环进行并行化 ：#pragma omp parallel forfor（int i=0

51、; in; i+） zi = xi + yi; 但如存在循环依赖性，则不能直接并行化，实例：for（int i=0; in; i+） zi = zi-1 + xi + yiOpenMP多线程编程基础多线程编程基础 OpenMP的编程模型以线程为基础，通过的编程模型以线程为基础，通过编译指导编译指导语句语句来显示地指导并行化，为编程人员提供了对并来显示地指导并行化，为编程人员提供了对并行化的完整的控制。行化的完整的控制。 OpenMP 的执行模型采用的执行模型采用 Fork-Join 的形式的形式 Fork：创建新线程或唤醒已有线程：创建新线程或唤醒已有线程 Join：多线程的汇合：多线程的汇合

52、 OpenMP版本的版本的“Hello World”#include “omp.h”int main（）（） printf（“Hello from serial.n”）; /串行执行串行执行 printf（“Thread number = %dn”,omp_get_thread_num（）（）; omp_set_num_threads(4); #pragma omp parallel /开始并行执行开始并行执行 printf（“Hello from parallel. Thread number=%dn”,omp_get_thread_num（）（）; printf（“Hello from s

53、erial again.n”）; return 0;OpenMP编程技术循环并行化 循环并行化编译指导语句的格式#pragma omp parallel for clauseclausefor（index=first;test_expression; increment_expr）body of the loop; parallel关键字将紧跟的程序块扩展为若干完全等同的并行区域，每个线程拥有完全相同的并行区域； 关键字for则将循环中的工作分配到线程组中，线程组中的每一个线程完成循环中的一部分内容。 数据相关的概念 如果语句S2与语句S1存在数据相关，那么必然存在以下两种情况之一： S1在循

54、环的一次迭代中访问存储单元L，而S2在随后的一次迭代中访问同一存储单元，即：循环迭代相关 ; S1和S2在同一循环迭代中访问同一存储单元L，但S1的执行在S2之前，即：非循环迭代相关 。 实例： x0 = 0; y0 = 1; #pragma omp parallel for private(k) for (k = 1; k 100; k+) xk = yk-1 + 1; /S1 yk = xk-1 + 2; /S2 循环嵌套 循环并行化编译制导语句可以加在任意一个循环之前，则对应的最近的循环语句被并行化，其它部分保持不变。 实际上并行化是作用于嵌套循环中的某一个循环，其它部分由执行到的线程负

55、责执行。 int i; int j;#pragma omp parallel for private(j)for(i=0;i1;i+)for(j=6;j10;j+)printf(i=%d j=%dn,i,j);int i; int j;for(i=0;i2;i+)#pragma omp parallel forfor(j=6;j10;j+)printf(i=%d j=%dn,i,j);规约操作的并行化 常见的规约操作数组求和 # pragma omp parallel for private(arx,ary,n) reduction(+:a,b) for（i=0;in;i+） a=a+arxi

56、; b=b+aryi; 运算符运算符数据类型数据类型默认初始值默认初始值+整数，浮点整数，浮点0*整数，浮点整数，浮点1-整数，浮点整数，浮点0&整数整数所有位都开启，所有位都开启，0|整数整数0整数整数0&整数整数1|整数整数0循环嵌套 循环并行化编译制导语句可以加在任意一个循环之前，则对应的最近的循环语句被并行化，其它部分保持不变。 实际上并行化是作用于嵌套循环中的某一个循环，其它部分由执行到的线程负责执行。 int i; int j;#pragma omp parallel for private(j)for(i=0;i1;i+)for(j=6;j10;j+)printf

57、(i=%d j=%dn,i,j);int i; int j;for(i=0;i2;i+)#pragma omp parallel forfor(j=6;j10;j+)printf(i=%d j=%dn,i,j);控制数据的共享属性 OpenMP 程序在同一个共享内存空间上执行，线程通信容易，一个线程写入一个变量，另一个线程可以读取这个变量来完成线程间的通信。 控制数据的共享属性 全局变量以及程序代码都是全局共享的；而动态分配的堆空间也是共享的。 通过threadprivate来明确指出的某一个数据结构属于线程范围的全局变量。 OpenMP 允许线程保留自己的私有变量不能让其它线程访问到。每一个

58、线程会建立变量的私有拷贝，虽然变量名是相同的，实际上在共享内存空间内部的位置是不同的。 控制数据的共享属性 数据作用域子句用来确定数据的共享属性，有下面以下几个子句 ： shared用来指示一个变量的作用域是共享的； private用来指示一个变量作用域是私有的； firstprivate 和 lastprivate 分别对私有的变量进行初始化的操作和最后终结的操作， firstprivate 将串行的变量值拷贝到同名的私有变量中，在每一个线程开始执行的时候初始化一次。 lastprivate将并行执行中的最后一次循环的私有变量值拷贝到同名的串行变量中； default语句用来改变变量的默认私

59、有属性。 在使用作用域子句的时候要遵循如下的一些规则 ： 作用域子句作用的变量是已经申明的有名变量； 作用域子句在作用到类或者结构的时候，必须作用到类或者结构的整体，而不能只作用于类或者结构的一个部分； 一个编译指导语句能够包含多个数据作用域子句，但变量只能出现在一个作用域子句中，即变量不能既是共享的，又是私有的； 在语法结构上，作用域子句只能作用在出现在编译指导语句起作用的语句变量部分。另外，可以将作用域子句作用在类的静态变量上。控制数据的共享属性 OpenMP 对默认情况下，并行区中所有的变量都是共享的，但有三种例外情况： 在parallel for循环中，循环索引变量是私有的； 并行区中

60、的局部变量是私有的； 所有在private，firstprivate，lastprivate或reduction子句中列出的变量都是私有的。私有化是通过为每个线程创建各个变量的独立副本来完成的。控制数据的共享属性 reduction声明可以看作： 保证了对sum的原则操作 多个线程的执行结果通过reduction中声明的操作符进行计算，以加法操作符为例： 假设sum的初始值为10，reduction（+: sum）声明的并行区域中每个线程的sum初始值为0（规定），并行处理结束之后，会将sum的初始化值10以及每个线程所计算的sum值相加。 规约操作的并行化3.1 体系结构无关的性能调优方法 独立于体系结构性能优化方法主要有：独