1 Programming with Shared Memory 共享存储器程序设计 Part 2.

Slides:



Advertisements
Similar presentations
C++语言程序设计教程 第5章 构造数据类型 第6章 C++程序的结构.
Advertisements

Course 1 演算法: 效率、分析與量級 Algorithms: Efficiency, Analysis, and Order
程序设计基础 贺辉 图书馆三楼办公室(进馆左侧上楼)
Memory Pool ACM Yanqing Peng.
第一章 C语言概述 计算机公共教学部.
编译原理上机实习
程設一.
周纯葆 中国科学院计算机网络信息中心 超级计算中心
新世代計算機概論 第14章 程式語言.
并行算法实践 上篇 并行程序设计导论.
华南理工大学 陈虎 博士 OpenMP并行程序设计简介 华南理工大学 陈虎 博士
机群应用开发 并行编程原理及 程序设计 Parallel Programming: Fundamentals and Implementation 马少杰 曙光信息产业有限公司
多核结构与程序设计 杨全胜 东南大学成贤学院计算机系.
課程名稱:程式設計 授課老師:________
函數 授課:ANT 日期:2009/3/24.
多核结构与程序设计复习 2012年 杨全胜 东南大学成贤学院计算机系.
并行计算实验上机 国家高性能计算中心(合肥).
OpenMP简介和开发教程 广州创龙电子科技有限公司
并行算法实践.
核探测与核电子学国家重点实验室 报告人:董磊 指导老师:宋克柱
第五讲 数据的分组、合并与转换.
EBNF 请用扩展的 BNF 描述 C语言里语句的结构; 请用扩展的 BNF 描述 C++语言里类声明的结构;
C 程式設計— 語言簡介 台大資訊工程學系 資訊系統訓練班.
C 程式設計— 控制敘述 台大資訊工程學系 資訊系統訓練班.
C 程式設計— 指標 台大資訊工程學系 資訊系統訓練班.
C++ 程式設計— 語言簡介 台大資訊工程學系 資訊系統訓練班.
授课老师:龚涛 信息科学与技术学院 2018年3月 教材: 《Visual C++程序员成长攻略》 《C++ Builder程序员成长攻略》
Function.
2 C++ 的基本語法和使用環境 親自撰寫和執行程式是學好程式語言的不二法門。本章藉由兩個簡單的程式,介紹C++ 程式的基本結構和開發環境,讓初學者能逐漸建立使用C++ 的信心。
实践演练 广州创龙电子科技有限公司 01 广州创龙电子科技有限公司
临界区软件互斥软件实现算法.
线程(Thread).
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
重點 資料結構之選定會影響演算法 選擇對的資料結構讓您上天堂 程式.
2019/1/17 Java语言程序设计-程序流程 教师:段鹏飞.
临界区软件互斥软件实现算法 主讲教师:夏莹杰
計數式重複敘述 for 迴圈 P
十二、并行程序设计基础.
Introduction to lisp lisp.
第1章 概述 本章要点: C语言程序结构和特点 C语言程序的基本符号与关键字 C语言程序的编辑及运行 学习方法建议:
C++ 程式設計 基礎篇 張啟中 Chang Chi-Chung.
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
1.3 C语言的语句和关键字 一、C语言的语句 与其它高级语言一样,C语言也是利用函数体中的可执行 语句,向计算机系统发出操作命令。按照语句功能或构成的不 同,可将C语言的语句分为五类。 goto, return.
易成 Institute of High Energy Physics
C语言概述 第一章.
Chapter 2 & Chapter 3.
C语言环境配置.
OpenMP程序设计 2019/4/25.
Oop8 function函式.
信号量(Semaphore).
第4章 Excel电子表格制作软件 4.4 函数(一).
本节内容 类成员的访问控制 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第九节 赋值运算符和赋值表达式.
第二章 类型、对象、运算符和表达式.
第二章 基本数据类型 ——数据的表示.
授课老师:龚涛 信息科学与技术学院 2016年3月 教材:《Visual C++程序员成长攻略》 《C++ Builder程序员成长攻略》
挑戰C++程式語言 ──第9章 函數.
#include <iostream.h>
临界区问题的硬件指令解决方案 (Synchronization Hardware)
第一讲 面向对象方法学与信息系统建模.
第1章程序设计和C语言.
MultiThread Introduction
并行计算实验上机 国家高性能计算中心(合肥).
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
C++语言程序设计 C++语言程序设计 第九章 类的特殊成员 第十一组 C++语言程序设计.
Race Conditions and Semaphore
C/C++基礎程式設計班 C語言入門、變數、基本處理與輸入輸出 講師:林業峻 CSIE, NTU 3/7, 2015.
第三章 流程控制 程序的运行流程 选择结构语句 循环结构语句 主讲:李祥 时间:2015年10月.
Introduction to the C Programming Language
C++语言程序设计 C++语言程序设计 第二章 基本数据类型与表达式 第十一组 C++语言程序设计.
Presentation transcript:

1 Programming with Shared Memory 共享存储器程序设计 Part 2

2 OpenMP OpenMP 是 1990s 后期由一群工业界的专家所开发的一个已被 接受的标准。 由一个小型的编译器制导指令集 compiler directives, 一个扩 展的小型库例程 library routines, 和使用 Fortran and C/C++ 基 本语言的环境变量 environment variables 组成. 现在有很多 OpenMP 编译器可用 (GNU gcc, IBM linux, Oracle, HP 等等)

3 扩展 并行控制结构 工作共享 同步构造 数据环境

4 OpenMP 不是建立在分布式存储系统上的OpenMP 应用编程接口 API 是在共享存储体系结构上基于线 程的一个编程模型(不是建立在分布式存储系统上的 ) OpenMP programs 可创建多个线程 所有的线程都能访问 global memory 数据可以所有的线程共享,也可以一个线程私有 存在同步结构但不清晰 标准性简洁实用使用方便可移植性

5 OpenMP 使用 “fork-join” 模型,且基于线程的. 开始,一个主线程 master thread. parallel directive 创建一组用特定代码区块供一组线程并行计 算的线程. Other directives used within a parallel construct to specify parallel for loops and different blocks of code for threads.

6 parallel region Multiple threads parallel region Master thread Fork/join model Synchronization

7 对于 C/C++, OpenMP 命令 含在 #pragma 语句中 形式如下 : #pragma omp directive_name [clauses...] 其中 omp 是 OpenMP 的一个关键字. 在制导指令名 directive_name 后可以附加参数 parameters ( 子句 clauses) 等 选项. #pragma ompdirective-name[clause,...]newline 制导指令前缀。对 所有的 OpenMP 语 句都需要这样的前 缀。 OpenMP 制导指 令。在制导指令前 缀和子句之间必须 有一个正确的 OpenMP 制导指 令。 子句。在没有其它 约束条件下,子句 可以无序,也可以 任意的选择。 这一 部分也可以没有。 换行符。表明这条 制导语句的终止。

8 Parallel Directive 并行域结构 #pragma omp parallel structured_block // 语句形成的结构块,对每个线程执行结构块 它将创建多线程,每个线程执行特定的 structured_block, structured_block 可以是一条语句也可以是用 {...} 创建的复合语句, 但必须只有一个入口,一个出口。 在该结构结束处隐含一个 barrier. 该 parallel 命令就相当于以前提到的 forall 构造.

9 if (scalar_expression)if (scalar_expression) private (list)private (list) shared (list)shared (list) default (shared | none)default (shared | none) firstprivate (list)firstprivate (list) reduction (operator: list)reduction (operator: list) copyin (list)copyin (list) #pragma omp parallel [clause[[,]clause]…]newline clause=

10 #include #include int main() { #pragma omp parallel//OpenMP 指令开始一段 parallel {// 大括号必须新起一行 printf(“Hello, world! This is thread %d of %d\n", omp_get_thread_num(), omp_get_num_threads()); } } Hello World ! gcc -fopenmp -o helloworld_omp helloworld_omp.c

11 gcc -fopenmp -o helloworld_omp helloworld_omp.c icc -openmp -o helloworld_omp helloworld_omp.c Intel 编译器 GNU gcc 编译器

12 #include #include #include int main(int argc, char* argv[]) { int nthreads,tid; // fork a team of thread #pragma omp parallel private(nthreads,tid)// 说明线程的私有变量 { //obtian and print thread id tid=omp_get_thread_num(); printf("Hello Word from OMP thread %d\n",tid); // only master thread does this; if(tid==0) { nthreads = omp_get_num_threads(); printf("Number of thread: %d\n",nthreads); } } return 0; }

13 Private and shared variables 私有和共享变量 变量可以在每个 parallel 区声明,但 OpenMP 提供子句 private clause. int tid; … #pragma omp parallel private(tid) { tid = omp_get_thread_num(); printf("Hello World from thread = %d\n", tid); } 每个进程都 有个局部变 量 tid Also a shared clause available.

14 #include main () { int var1, var2, var3; Serial code … //Beginning of parallel section. Fork a team of threads. //Specify variable scoping #pragma omp parallel private(var1, var2) shared(var3) { Parallel section executed by all threads... All threads join master thread and disband } Resume serial code... } 常见的代码结构 #pragma omp parallel default(shared) private(var1, var2)

15

16 线程组中的线程数目 下面的任一方法均可设定 : 1. parallel 命令后的 num_threads 子句 #pragma omp parallel num_threads(8) 2. omp_set_num_threads() 库例程 3. 环境变量 OMP_NUM_THREADS 如果不使用上述方法,可线程可取决于系统。 动态调整: omp_set_num_dynamic(int num_threads)

17 Work-Sharing 共享任务结构 共享任务结构将它所包含的代码划分给线程组的各成员来执行 1. 并行 for 循环 2. 并行 sections 3.single 串行执行 在结构语句结束处有一个隐含的路障,使用了 nowait 子句除外 In all cases, there is an implicit barrier at end of construct unless a nowait clause included, which overrides the barrier. 在结构语句结束处有一个隐含的路障,使用了 nowait 子句除外 Note: These constructs do not start a new team of threads. That done by an enclosing parallel construct.

18

19 Sections 编译制导语句 sections 编译制导语句指定内部的代码被划分给线程组中的各 线程 The construct #pragma omp sections { #pragma omp section structured_block. #pragma omp section structured_block } cause structured blocks to be shared among threads in team. The first section directive optional. 不同的 section 由不 同的线程执 行

20 Example #pragma omp parallel shared(a,b,c,d,nthreads) private(i,tid) { tid = omp_get_thread_num(); #pragma omp sections nowait { #pragma omp section { printf("Thread %d doing section 1\n",tid); for (i=0; i<N; i++) { c[i] = a[i] + b[i]; printf("Thread %d: c[%d]= %f\n",tid,i,c[i]); } #pragma omp section { printf("Thread %d doing section 2\n",tid); for (i=0; i<N; i++) { d[i] = a[i] * b[i]; printf("Thread %d: d[%d]= %f\n",tid,i,d[i]); } } /* end of sections */ } /* end of parallel section */ 一个线程做这段 另一个线程做这段

21 #include #define N 1000 int main(){ int I, tid; float a[N], b[N], c[N],d[N]; /* vectors initializations */ for (i=0; i < N; i++) a[i] = b[i] = i * 1.0; 嵌入上页那段代码; } 你可以尝试一下编译此代码

22 For Loop 编译制导语句  for 语句指定紧随它的循环语句必须由线程组并行执行; #pragma omp for for ( i = 0; …. ) 分割 for 循环的方法可由一个附加的调度 “schedule” 语句. Example schedule (static, chunk_size) 将 for 循环按 chunk_size 所指明的大小进行分割,且以轮转的方 式分给线程 ( 静态 ). For 循环必须是 简单规范的形式

23 schedule 子句描述如何将循环的迭代划分给线程组中 的线程 1.schedule (static, chunk_size), 循环被静态划分为 大小为 chunk 的块,以轮转的方式分给线程,如果 没有指定 chunk 大小,迭代会尽可能的平均分配给 每个线程 2.schedule (dynamic, chunk_size), 循环被动态划分 为大小为 chunk 的块,动态分配给线程 ( 当有进程 空闲就分配一块 ) ,如果没有指定 chunk 大小就默 认为 1 3. schedule (guided,chunk_size) 4. schedule (runtime)

24 Example #pragma omp parallel shared(a,b,c,nthreads,chunk) private(i,tid) { tid = omp_get_thread_num(); if (tid == 0) { nthreads = omp_get_num_threads(); printf("Number of threads = %d\n", nthreads); } printf("Thread %d starting...\n",tid); #pragma omp for schedule(dynamic,chunk) for (i=0; i<N; i++) { c[i] = a[i] + b[i]; printf("Thread %d: c[%d]= %f\n",tid,i,c[i]); } } /* end of parallel section */ For loop Executed by one thread

25 Single 编译制导语句 single 编译制导语句指定内部代码只有线程组中的一个线程执 行。线程组中没有执行 single 语句的线程会一直等待代码块的 结束,使用 nowait 子句除外 #pragma omp single structured block

26 Combined Parallel Work-sharing Constructs 组合的并行共享任务结构 If a parallel directive is followed by a single for directive, it can be combined with similar effects. Parallel for 编译制导语句表明一个并行域包含一个独立的 for 语 句 #pragma omp parallel for

27 #include #define N 1000 #define CHUNKSIZE 100 int main () { int i, chunk; float a[N], b[N], c[N]; /* Some initializations */ for (i=0; i < N; i++) a[i] = b[i] = i * 1.0; chunk = CHUNKSIZE; #pragma omp parallel for shared(a,b,c,chunk) private(i) schedule(static,chunk) for (i=0; i < n; i++) c[i] = a[i] + b[i]; } Parallel for 举例

28 parallel sections 编译制导语句 parallel sections 编译制导语句表明一个并行域包含单独的一个 sections 语句 #pragma omp parallel sections { #pragma omp section structured_block #pragma omp section structured_block. } 注: parallel for 和 parallel sections 都不允许使用 nowait 语句

29 Master Directive The master directive: 新起一行 #pragma omp master 新起一行 structured_block master 制导语句指定代码段只有主线程执 行语句格式 master 制导语句指定代码段 structured_block 只有主线程执 行语句格式  不同于共享任务结构,在它的结构末尾处没有隐含的 barrier( 开始也没有);其他线程遇到该制导指令和其结 构块时不予理会,继续向前执行。

30 Reduction 子句  使用指定的操作对其列表中出现的变量进行归约 将迭代的结果组合成一个值返回, 很像 MPI 的 MPI _Reduce(). 该子句可用在 parallel, for, 和 sections 制导指令中 例如 sum = 0 #pragma omp parallel for reduction(+:sum) for (k = 0; k < 100; k++ ) { sum = sum + funct(k); }初始时,每个线程都保留一份私有拷贝 在结构尾部根据指定的操作对线程中的相应变量进行归约,并 更新改变量的全局值 Operation Variable

31 #include int main () { int i, n, chunk; float a[100], b[100], result; /* Some initializations */ n = 100; chunk = 10; result = 0.0; for (i=0; i < n; i++) { a[i] = i * 1.0; b[i] = i * 2.0; } #pragma omp parallel for default(shared) private(i) schedule(static,chunk) reduction(+:result) for (i=0; i < n; i++) result = result + (a[i] * b[i]); printf("Final result= %f\n",result); } Reduction 举例 : 向量点乘

32 Private variables 私有变量 表示它列出的变量对于每个 线程是局部的 Private(variable_list) clause – 表示它列出的变量对于每个 线程是局部的 creates private copies of variables for each thread firstprivate clause - as private clause but initializes each copy to the values given immediately prior to parallel construct. lastprivate clause – as private but “the value of each lastprivate variable from the sequentially last iteration of the associated loop, or the lexically last section directive, is assigned to the variable’s original object.”

33 Synchronization Constructs Critical 邻接制导语句 critical 制导语句表明域中的代码一次只能执行一个线程 其他线程被阻塞在临界区 #pragma omp critical name structured_block name is optional.

34 #include main() { int x; x = 0; #pragma omp parallel shared(x) { #pragma omp critical x = x + 1; } /* end of parallel section */ }

35 Barrier barrier 制导语句用来同步一个线程组中所有的线程barrier 制导语句用来同步一个线程组中所有的线程 先到达的线程在此阻塞,等待其他线程 先到达的线程在此阻塞,等待其他线程 barrier 语句最小代码必须是一个结构化的块barrier 语句最小代码必须是一个结构化的块语句格式 #pragma omp barrier newline #pragma omp barrier newline 错误正确 if (x == 0) #pragma omp barrier if (x == 0) { #pragma omp barrier }

36 制导语句 Atomic 制导语句该制导语句指定特定的存储单元将被原子更新 The atomic directive #pragma omp atomic expression_statement 可以高效地实现一个临界区,如果临界区只是简单地更新一 个变量 (expression_statement :加 1 ,减 1 ,及其他简单算术 操作 ).

37 Flush 刷新制导语句 flush 制导语句用以标识一个同步点,用以确保 所有的线程看到一致的存储器视图 语句格式 #pragma omp flush (list) newline flush 将在下面几种情形下隐含运行, nowait 子 句除外 barrier critical: 进入与退出部分 ordered: 进入与退出部分 parallel: 退出部分 for: 退出部分 sections: 退出部分 single: 退出部分

38 Ordered 子句 Used in conjunction with for and parallel for directives to cause an iteration to be executed in the order that it would have occurred if written as a sequential loop.Ordered制导语句指出其所包含循环的执行 任何时候只能有一个线程执行被 ordered 所限定部分 只能出现在 for 或者 parallel for 语句的动态范围中 语句格式: #pragma omp ordered newline

39 More information Full information on OpenMP at

40 OpenMP 计算实例:计算 pi

41 C 语言写的串行程序 /* Seriel Code */ static long num_steps = ; double step; void main () { int i; double x, pi, sum = 0.0; step = 1.0/(double) num_steps; for (i=1;i<= num_steps; i++){ x = (i-0.5)*step; sum = sum + 4.0/(1.0+x*x); } pi = step * sum; }

42 使用并行域并行化的程序 #include static long num_steps = ; double step; #define NUM_THREADS 2 void main () { int i; double x, pi, sum[NUM_THREADS]; step = 1.0/(double) num_steps; omp_set_num_threads(NUM_THREADS) #pragma omp parallel { double x; int id; id = omp_get_thraead_num(); for (i=id, sum[id]=0.0;i< num_steps; i=i+NUM_THREADS){ x = (i+0.5)*step; sum[id] += 4.0/(1.0+x*x); } for(i=0, pi=0.0;i<NUM_THREADS;i++) pi += sum[i] * step; }

43 使用共享任务结构并行化的程序 #include static long num_steps = ; double step; #define NUM_THREADS 2 void main () { int i; double x, pi, sum[NUM_THREADS]; step = 1.0/(double) num_steps; omp_set_num_threads(NUM_THREADS) #pragma omp parallel { double x; int id; id = omp_get_thraead_num(); sum[id] = 0; #pragma omp for for (i=id;i< num_steps; i++){ x = (i+0.5)*step; sum[id] += 4.0/(1.0+x*x); } for(i=0, pi=0.0;i<NUM_THREADS;i++) pi += sum[i] * step; }

44 使用 private 子句和 critical 部分并行化的程序 #include static long num_steps = ; double step; #define NUM_THREADS 2 void main () { int i; double x, sum, pi=0.0; step = 1.0/(double) num_steps; omp_set_num_threads(NUM_THREADS) #pragma omp parallel private (x, sum) { id = omp_get_thread_num(); for (i=id,sum=0.0;i< num_steps;i=i+NUM_THREADS){ x = (i+0.5)*step; sum += 4.0/(1.0+x*x); } #pragma omp critical pi += sum }

45 使用并行归约得出的并行程序 #include static long num_steps = ; double step; #define NUM_THREADS 2 void main () { int i; double x, pi, sum = 0.0; step = 1.0/(double) num_steps; omp_set_num_threads(NUM_THREADS) #pragma omp parallel for reduction(+:sum) private(x) for (i=1;i<= num_steps; i++){ x = (i-0.5)*step; sum = sum + 4.0/(1.0+x*x); } pi = step * sum; }