OpenMP学习笔记:编程

2014-04-10 • 技术文章

并行域的管理

OpenMP编程首先要产生多个线程来并发地执行任务。在OpenMP的相邻的fork和join操作之间我们称之为一个并行域,并行域可以嵌套。parallel制导指令就是用来创建并行域的,可以和for、sections等配合成为符合指令。

在C/C++中,parallel的使用方法如下:

1
2
3
4
#pragma omp parallel [for | sections] [子句[子句]„]
{
	//code
}

容易看到,code部分的内容(如简单的打印语句)被执行了数次,说明总共创建了相应数量的线程来执行code部分的代码。我们可以通过设置环境变量OMP_NUM_THREADS或者调用omp_set_num_theads()函数或者使用num_threads子句,以使用num_threads为例,如下所示,执行结果是被执行了8次。出于兼容考虑,我个人觉得这种方法更好。

1
2
3
4
#pragma omp parallel num_threads(8)
{
	printf("ThreadId=%d\n", omp_get_thread_num());
}

parallel的并行域内部代码中,若再出现parallel制导指令则出现并行嵌套问题,如果设置了OMP_NESTED环境变量,那么在条件许可时内部并行域也会由多个线程执行,反之没有设置相应变量,那么内部并行域的代码将只由一个线程来执行。还有 一个环境变量OMP_DYNAMIC也影响并行域的行为,如果没有设置该环境变量将不允许动态调整并行域内的线程数目,omp_set_dynamic()也是用于同样的目的。

任务分担

显然,我们使用多线程并不是为了徒增重复的计算量,而是为了加快计算,所以对计算任务要进行分担而不是像上面那样来用。在OpenMP中for和sections是任务分担指令,single是协助任务分担的指令。

for要和parallel配合使用才行,如下两个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// e.g.1
#pragma omp parallel for
for (j=0; j<4; ++j) {
	printf("j=%d, Threadid=%d\n", j, omp_get_thread_num());
}
 
// e.g.2
#pragma omp parallel
{
	#pragma omp for
	for (j=0; j<4; ++j){
		printf("j=%d, Threadid=%d\n", j, omp_get_thread_num());
	}
}
 
/*
	可能一种打印结果:
	j=0, Threadid=0
	j=1, Threadid=1
	j=3, Threadid=3
	j=2, Threadid=2
*/

假如在一个parallel并行域中有多个for制导指令,在该并行域内的多个线程首先完成第一个for语句的任务分担,然后在此进行一次同步(for制导指令本身隐含有结束处的路障同步),然后再进行第二个for语句的任务分担,直到退出并行域并只剩下一个主线程为止。

对于for循环的并行计算,如果仅仅像上面这种方式进行任务分配,假如循环变量不同时计算量不同,那么这样的分配是不合理的。对于这种情况,我们可以使用schedule子句来解决。

schedule子句的格式是schedule(type [,size])。type的类型有static、dynamic、guided三种调度方式,此外还可以是runtime,但runtime是根据环境变量OMP_SCHEDULED来选择前三种中的某种类型,相应的内部控制变量ICV是run-sched-var。size是可选的,默认为平均分配。size参数必须是整数,表示以循环迭代次数计算的划分单位,每个线程所承担的计算任务对应于0个或若干个size次循环。需要注意的是,当type参数类型为runtime时,size参数是非法的。

首先来看static类型。当for或者parallel for编译制导指令没有带schedule子句时,大部分系统中默认采用size为1的static调度方式。假设有n次循环迭代,t个线程,那么给每个线程静态分配大约n/t次迭代计算,当然不要钻什么除不尽这样的牛角尖,线程分配到的迭代次数相差一次就行了。如果指定了size,则可能相差更大。对两个线程,以schedule(static)为例,以for循环10次为例,它们将分别得到5次;再以schedule(static,2)为例,0、1次迭代分配给0号线程,2、3次迭代分配给1号线程,4、5次迭代分配给0号线程,6、7次迭代分配给1号线程,…

再来讨论dynamic类型。schedule(dynamic)是按情况每size次迭代进行分配,各线程动态地申请任务,因此较快的线程可能申请更多次数,而较慢的线程申请任务次数可能较少,因此动态调度可以在一定程度上避免前面提到的按循环次数划分引起的负载不平衡问题。默认size为1,类似于static的情况,容易想到size被指定后的情形,就不再赘述。

再讨论guided类型,这是一种采用指导性的启发式自调度方法。开始时每个线程会分配到较大的迭代块,之后分配到的迭代块会逐渐递减。迭代块的大小会按指数级下降到指定的size大小,如果没有指定size参数,那么迭代块大小最小会降到1。听上去有点晕,下面举个例子。其中第0、1、2、3、4次迭代被分配给线程0,第5、6、7次迭代被分配给线程1,第8、9次迭代被分配给线程0,分配的迭代次数呈递减趋势,最后一次递减到2次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#pragma omp parallel for schedule(guided,2)
for (j=0; j<10; ++j) {
	printf("j=%d, Threadid=%d\n", j, omp_get_thread_num());
}
/* 可能的打印结果:
i=0, thread_id=0
i=1, thread_id=0
i=2, thread_id=0
i=3, thread_id=0
i=4, thread_id=0 
i=8, thread_id=0
i=9, thread_id=0
i=5, thread_id=1
i=6, thread_id=1
i=7, thread_id=1 */

最后看runtime调度,它是在运行时根据环境变量OMP_SCHEDULE来确定调度类型。

1
2
setenv OMP_SCHEDULE "dynamic, 2"  # UNIX
set OMP_SCHEDULE="dynamic, 2"  # Windows

下面看sections,它用于非迭代计算的任务分担。它将sections语句里的代码用section制导指令划分成几个不同的段(可以是一条语句,也可以是用{}括起来的结构块),不同的section段由不同的线程并行执行。

1
2
3
4
5
6
7
#pragma omp parallel sections 
{
	#pragma omp section
	printf("section 1 thread = %d\n", omp_get_thread_num());
	#pragma omp section
	printf("section 2 thread = %d\n", omp_get_thread_num());
}

如果在parallel下有多个sections,每个sections内又有多个section。那么与for制导指令一样,在sections的结束处有一个隐含的路障同步。这也就说明每个section执行的时间要差不多,否则将出现部分先执行完的线程空闲等待的情况。for的任务分担由系统自动化分,但sections则由程序员手工指定,这是一点重要的区别。

再来看single制导指令。单线程执行single制导指令指定所包含的代码只由一个线程执行,别的线程跳过这段代码。如果没有nowait从句,所有线程在single制导指令结束处隐式同步点同步。如果single制导指令有nowait从句,则别的线程直接向下执行,不在隐式同步点等待;single制导指令用在一段只被单个线程执行的代码段之前,表示后面的代码段将被单线程执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#pragma omp parallel
{
	#pragma omp single
	printf("Beginning work1.\n");
 
	printf("work on 1 parallelly.%d\n", omp_get_thread_num());
 
	#pragma omp single
	printf("Finishing work1.\n"); // 决定了全部线程执行完1,再去管2
 
	#pragma omp single nowait
	printf("Beginning work2.\n");
 
	printf("work on 2 parallelly.%d\n", omp_get_thread_num());
}
/* 可能的一种打印结果:
Beginning work1.
work on 1 parallelly.2
work on 1 parallelly.1
Finishing work1.
work on 1 parallelly.0
work on 1 parallelly.3
Beginning work2.
work on 2 parallelly.1
work on 2 parallelly.0
work on 2 parallelly.2
work on 2 parallelly.3 */

同步

OpenMP支持两种不同类型的线程同步机制,一种是互斥锁的机制,可以用来保护一块共享的存储空间,使任何时候访问这块共享内存空间的线程最多只有一个,从而保证了数据的完整性;另外一种同步机制是事件同步机制,这种机制保证了多个线程之间的执行顺序。互斥的操作针对需要保护的数据而言,在产生了数据竞争的内存区域加入互斥,可以使用包括critical、atomic等制导指令以及API中的互斥函数。而事件机制则控制线程执行顺序,包括barrier同步路障、ordered定序区段、master主线程执行等。

对于可能产生内存数据访问竞争的地方要插入相应的临界区制导指令critical,critical语句不允许互相嵌套。以下面的代码为例,在一个并行域内的for任务分担域中,各个线程逐个进入到critical保护的区域内,比较当前元素和最大值的关系并可能进行最大值的更替,从而避免了数据竞争的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int i;
int max_num_x=max_num_y=-1;
#pragma omp parallel for
for (i=0; i<n; ++i)
{
	#pragma omp critical(max_arx);
	if (arx[i] >max_num_x)
	{
		max_num_x = arx[i];
	}
 
	#pragma omp critical(max_ary)
	if (ary[i]>max_num_y)
	{
		max_num_y = ary[i];
	}
}

critical临界区操作能够作用在任意大小的代码块上,而原子操作atomic只能作用在单条赋值语句中。能够使用原子语句的前提条件是相应的语句能够转化成一条机器指令,使得相应的功能能够一次执行完毕而不会被打断。C/C++中可用的原子操作:+、-、*、/、&、^、<<、>>。值得注意的是,当对一个数据进行原子操作保护的时候,就不能对数据进行临界区的保护,OpenMP运行时并不能在这两种保护机制之间建立配合机制。用户在针对同一个内存单元使用原子操作的时候,需要在程序所有涉及到该变量并行赋值的部位都加入原子操作的保护。

1
2
3
4
5
6
7
8
#pragma omp parallel
{
	for (int i=0; i<10000; ++i)
	{
		#pragma omp atomic//atomic operation
		counter++;
	}
}

有时候我们需要显示的路障barrier。只有等所有的线程都完成Initialization()初始化操作以后,才能够进行下一步的处理动作,因此,在此处插入一个明确的同步路障操作以实现线程之间的同步。

1
2
3
4
5
6
#pragma omp parallel
{
	Initialization();
	#pragma  omp barrier
	Process();
}

nowait作为去除隐式路障使用,在前面已经提到过,不再重复。

master制导指令和single制导指令类似,区别在于,master制导指令包含的代码段只由主线程执行,而single制导指令包含的代码段可由任一线程执行,并且master制导指令在结束处没有隐式同步,也不能指定nowait从句。如下例,只由主线程来打印数组结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
#pragma omp parallel
{
	#pragma omp for
	for (i=0; i<5; ++i)
	{
		a[i] = i * i;
	}
	#pragma omp master
	for (i=0; i<5; ++i)
	{
		printf("a[%d]=%d\n", i, a[i]);
	}
}

对于循环代码的任务分担中,某些代码的执行需要按规定的顺序执行。典型的情况如下:在一次循环的过程中大部分的工作是可以并行执行的,而特定部分代码的工作需要等到前面的工作全部完成之后才能够执行。这时,可以使用ordered子句使特定的代码按照串行循环的次序来执行。

1
2
3
4
5
6
7
8
#pragma omp parallel
{
	// some code
	#pragma omp ordered
	for(int i=0;i<5;i++) {
		printf("%d",i);
	}
}

除了atomic和critical编译制导指令,OpenMP还可以通过库函数支持实现互斥操作,方便用户实现特定的同步需求。编译制导指令的互斥支持只能放置在一段代码之前,作用在这段代码之上。而OpenMP API所提供的互斥函数可放在任意需要的位置。程序员必须自己保证在调用相应锁操作之后释放相应的锁,否则就可能造成多线程程序的死锁。互斥锁函数中只有omp_test_lock函数是带有返回值的,该函数可以看作是omp_set_lock的非阻塞版本。示例对for循环中的所有内容进行加锁保护,同时只能有一个线程执行for循环中的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static omp_lock_t lock;
int i;
omp_init_lock(&lock);
#pragma omp parallel for
for (i=0; i<5; ++i)
{
	omp_set_lock(&lock);
	printf("%d +\n", omp_get_thread_num());
	printf("%d -\n", omp_get_thread_num());
	omp_unset_lock(&lock);
}
omp_destroy_lock(&lock);
/* possible result:
0 +
0 -
0 +
0 -
1 +
1 -
3 +
3 -
2 +
2 - */

OpenMP是建立在共享存储结构的计算机之上,使用操作系统提供的线程作为并发执行的基础,所以线程间的全局变量和静态变量是共享的,而局部变量、自动变量是私有的。但是对OpenMP编程而言,缺省变量往往是共享变量,而不管它是不是全局静态变量还是局部自动变量。也就是说OpenMP各个线程的变量是共享还是私有,是依据OpenMP自身的规则和相关的数据子句而定,而不是依据操作系统线程或进程上的变量特性而定。OpenMP的数据处理子句包括private、firstprivate、lastprivate、shared、default、reduction copyin和copyprivate。它与编译制导指令parallel、for和sections相结合用来控制变量的作用范围。

shared(list)子句:用来声明一个或多个变量是共享变量。需要注意的是,在并行域内使用共享变量时,如果存在写操作,必须对共享变量加以保护,否则不要轻易使用共享变量,尽量将共享变量的访问转化为私有变量的访问。循环迭代变量在循环构造的任务分担域里是私有的。声明在任务分担域内的自动变量都是私有的。

default(shared | none)子句:用来允许用户控制并行区域中变量的共享属性。使用shared时,缺省情况下,传入并行区域内的同名变量被当作共享变量来处理,不会产生线程私有副本,除非使用private等子句来指定某些变量为私有的才会产生副本。如果使用none作为参数,除了那些由明确定义的除外,线程中用到的变量都必须显式指定为是共享的还是私有的。

private(list)子句:用来将一个或多个变量声明成线程私有的变量,变量声明成私有变量后,指定每个线程都有它自己的变量私有副本,其他线程无法访问私有副本。即使在并行域外有同名的共享变量,共享变量在并行域内不起任何作用,并且并行域内不会操作到外面的共享变量。出现在reduction子句中的变量不能出现在private子句中。如下例,for循环前的变量k和循环区域内的变量k其实是两个不同的变量。用private子句声明的私有变量的初始值在并行域的入口处是未定义的,它并不会继承同名共享变量的值。

1
2
3
4
5
6
7
int k = 100;
#pragma omp parallel for private(k)
for (k=0; k<8; ++k)
{
	printf("k=%d\n", k);
}
printf("last k=%d\n", k); // 100

firstprivate子句:私有变量的初始化和终结操作,OpenMP编译制导指令需要对这种需求给予支持,即使用firstprivate和lastprivate来满足这两种需求。使得并行域或任务分担域开始执行时,私有变量通过主线程中的变量初始化,也可以在并行域或任务分担结束时,将最后一次一个线程上的私有变量赋值给主线程的同名变量。private声明的私有变量不会继承同名变量的值,于是OpenMP提供了firstprivate子句来实现这个功能。firstprivate子句是private子句的超集,即不仅包含了private子句的功能,而且还要对变量做进行初始化。

lastprivate子句:有时要将任务分担域内私有变量的值经过计算后,在退出时,将它的值赋给同名的共享变量(private和firstprivate子句在退出并行域时都没有将私有变量的最后取值赋给对应的共享变量),lastprivate子句就是用来实现在退出并行域时将私有变量的值赋给共享变量。lastprivate子句也是private子句的超集,即不仅包含了private子句的功能,而且还要将变量从for、sections的任务分担域中最后的线程中复制给外部同名变量。由于在并行域内是多个线程并行执行的,最后到底是将哪个线程的最终计算结果赋给了对应的共享变量呢?OpenMP规范中指出,如果是for循环迭代,那么是将最后一次循环迭代中的值赋给对应的共享变量;如果是sections构造,那么是代码中排在最后的section语句中的值赋给对应的共享变量。注意这里说的最后一个section是指程序语法上的最后一个,而不是实际运行时的最后一个运行完的。如下例,退出for循环的并行区域后,共享变量k的值变成了103,而不是保持原来的100不变。

1
2
3
4
5
6
7
8
int i, k=100;
#pragma omp parallel for firstprivate(k), lastprivate(k)
for (i=0; i<4; ++i)
{
	k += i;
	printf("k=%d\n", k);
}
printf("last k=%d\n", k);

flush:OpenMP的flush制导指令主要与多个线程之间的共享变量的一致性问题。用法:flush[(list)],该指令将列表中的变量执行flush操作,直到所有变量都已完成相关操作后才返回,保证了后续变量访问的一致性。

threadprivate子句:用法:#pragma omp threadprivate(list)。用作threadprivate的变量的地址不能是常数。对于C++的类(class)类型变量,用作threadprivate的参数时有些限制,当定义时带有外部初始化则必须具有明确的拷贝构造函数。对于windows系统,threadprivate不能用于动态装载(使用LoadLibrary装载)的DLL中,可以用于静态装载的DLL中。如下例,实现了一个线程私有的计数器,各个线程使用同一个函数来实现自己的计数。

1
2
3
4
5
6
7
int counter = 0;
#pragma omp threadprivate(counter)
int increment_counter()
{
	counter++;
	return (counter);
}

copyin子句:用来将主线程中threadprivate变量的值复制到执行并行域的各个线程的threadprivate变量中,便于所有线程访问主线程中的变量值。copyin中的参数必须被声明成threadprivate的,对于class类型的变量,必须带有明确的拷贝赋值操作符。如下例,threadprivate中的计数器函数,如果多个线程使用时,各个线程都需要对全局变量counter的副本进行初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int counter = 0;
#pragma omp threadprivate(counter)
int increment_counter()
{
	counter++;
	return (counter);
}
int main()
{
	int iterator;
 
	#pragma omp parallel sections copyin(counter)
	{
		#pragma omp section
		{
			int count1;
 
			for (iterator=0; iterator<100; ++iterator)
			{
				count1 = increment_counter();
			}
 
			printf("count1=%ld\n", count1);
		}
 
		#pragma omp section
		{
			int count2;
 
			for (iterator=0; iterator<200; ++iterator)
			{
				count2 = increment_counter();
			}
 
			printf("count2=%ld\n", count2);
		}
	}
	printf("counter=%ld\n", counter);
}

copyprivate子句:提供了一种机制,即将一个线程私有变量的值广播到执行同一并行域的其他线程。copyprivate子句可以关联single构造,在single构造的barrier到达之前就完成了广播工作。copyprivate可以对private和threadprivate子句中的变量进行操作,但是当使用single构造时,copyprivate的变量不能用于private和firstprivate子句中。如下例,使用copyprivate子句后,single构造内给counter赋的值被广播到了其它线程里,但没有使用copyprivate子句时,只有一个线程获得了single构造内的赋值,其它线程没有获取single构造内的赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int counter = 0;
#pragma omp threadprivate(counter)
int increment_counter()
{
	counter++;
	return (counter);
}
int main()
{
 
	#pragma omp parallel
	{
		int count;
 
		#pragma omp single copyprivate(counter)
		{
			counter = 50;
		}
 
		count = increment_counter();
 
		printf("Threadid:%ld, count=%ld\n", omp_get_thread_num(), count);
	}
	return 0;
}

归约操作:reduction子句主要用来对一个或多个参数条目指定一个操作符,每个线程将创建参数条目的一个私有拷贝,在并行域或任务分担域的结束处,将用私有拷贝的值通过指定的运行符运算,原始的参数条目被运算结果的值更新。列出了可以用于reduction子句的一些操作符以及对应私有拷贝变量缺省的初始值,私有拷贝变量的实际初始值依赖于reduction变量的数据类型(前为运算符,括号内为初值):+(0)、-(0)、*(1)、&(~0)、|(0)、^(0)、&&(1)、||(0)。如果在并行域内不加锁保护就直接对共享变量进行写操作,存在数据竞争问题,会导致不可预测的异常结果。如果共享数据作为private、firstprivate、lastprivate、threadprivate、reduction子句的参数进入并行域后,就变成线程私有了,不需要加锁保护了。

1
2
3
4
5
6
7
int i, sum = 100;
#pragma omp parallel for reduction(+:sum)
for (i=0; i<1000; ++i)
{
	sum += i;
}
printf("sum=%ld\n", sum);

参考资料与扩展阅读

OpenMP编译原理及实现技术[M]. 清华大学出版社, 2012.

OpenMP学习笔记:基本概念

2014-04-08 • 技术文章

简介

OpenMP是由OpenMP Architecture Review Board牵头提出的,并已被广泛接受的,用于共享内存并行系统的多线程程序设计的一套指导性注释(Compiler Directive)。可以说OpenMP制导指令将C语言扩展为一个并行语言,但OpenMP本身不是一种独立的并行语言, 而是为多处理器上编写并行程序而设计的、指导共享内存、多线程并行的编译制导指令和应用程序编程接口(API)。

OpenMP的编程模型以线程为基础,通过编译指导语句来显示地指导并行化,为编程人员提供了对并行化的完整控制。

OpenMP的执行模型采用Fork-Join的形式,Fork-Join执行模式在开始执行的时候,只有一个叫做“主线程”的运行线程存在。主线程在运行过程中,当遇到需要进行并行计算的时候,派生出线程来进行并行执行,在并行执行的时候,主线程和派生线程共同工作,在并行代码结束后,派生线程退出或者是挂起,不再工作,控制流程回到单独的主线程中。

OpenMP的功能由两种形式提供:编译指导语句和运行时库函数,并通过环境变量的方式灵活控制程序的运行。OpenMP同时结合了两种并行编程的方式,通过编译指导语句,可以将串行的程序逐步地改造成一个并行程序,达到增量更新程序的目的,从而减少程序编写人员的一定负担。同时,这样的方式也能将串行程序和并行程序保存在同一个源代码文件当中,减少了维护的负担。OpenMP在运行的时候,需要运行函数库的支持,并会获取一些环境变量来控制运行的过程。

编译指导语句

在C/C++程序中,OpenMP是以#pragma omp开始,后面跟具体的功能指令。在无法识别OpenMP语义的普通编译器中,这些注释被忽略。注释具有如下的形式:

1
#pragma omp directive_name [clause[[,]clause]…s]

其中directive_name部分就包含了具体的编译指导语句,包括parallel, for, parallel for, section, sections, single, master, critical, flush, ordered和atomic。制导指令和子句按照功能可以大体上分成四类:并行域控制类、任务分担类、同步控制类、数据环境类。并行域控制类指令用于指示编译器产生多个线程以并发执行任务,任务分担类指令指示编译器如何给各个并发线程分发任务,同步控制类指令指示编译器协调并发线程之间的时间约束关系,数据环境类指令处理并行域内外的变量共享或私有属性以及边界上的数据传送操作等。

parallel:用在一个结构块之前,表示这段代码将被多个线程并行执行;

for:用于for循环语句之前,表示将循环计算任务分配到多个线程中并行执行,以实现任务分担,必须由编程人员自己保证每次循环之间无数据相关性;

parallel for:parallel和for指令的结合,也是用在for循环语句之前,表示for循环体的代码将被多个线程并行执行,它同时具有并行域的产生和任务分担两个功能;

sections:用在可被并行执行的代码段之前,用于实现多个结构块语句的任务分担,可并行执行的代码段各自用section指令标出;

parallel sections:parallel和sections两个语句的结合,类似于parallel for;

single:用在并行域内,表示一段只被单个线程执行的代码;

critical:用在一段代码临界区之前,保证每次只有一个OpenMP线程进入;

flush:保证各个OpenMP线程的数据影像的一致性;

barrier:用于并行域内代码的线程同步,线程执行到barrier时要停下等待,直到所有线程都执行到barrier时才能继续往下执行;

atomic:用于指定一个数据操作需要原子性地完成;

master:用于指定一段代码由主线程执行;

threadprivate:用于指定一个或多个变量是线程专用。

可选子句clause给出了相应的编译器指导语句的参数,子句可以影响到编译指导语句的具体行为,每个编译指导语句都有一系列适合它的子句。其中有5个编译指导语句不能跟别的子句:master、critical、flush、ordered、atomic。

private:指定一个或多个变量在每个线程中都有它自己的私有副本;

firstprivate:指定一个或多个变量在每个线程都有它自己的私有副本,并且私有变量要在进入并行域或认为分担域时,继承主线程中的同名变量的值作为初值;

lastprivate:是用来指定将线程中的一个或多个私有变量的值在并行处理结束后复制到主线程中的同名变量中,负责拷贝的线程是for或sections任务分担中的最后一个线程;

reduction:用来指定一个或多个变量是私有的,并且在并行处理结束后这些变量要执行指定的归约运算,并将结果返回给主线程同名变量;

nowait:指出并发线程可以忽略其他制导指令暗含的路障同步;

num_threads:指定并行域内的线程的数目;

schedule:指定for任务分担中的任务分配调度类型;

shared:指定一个或多个变量为多个线程间的共享变量;

copyprivate:配合single指令,将指定线程的专有变量广播到并行域内其他线程的同名变量中;

copyin:用来指定一个threadprivate类型的变量需要用主线程同名变量进行初始化;

default:用来指定并行域内的变量的使用方式,缺省是shared。

运行时库函数

要使用运行时函数库所包含的函数,应该在相应的源文件中包含OpenMP头文件即omp.h。OpenMP的运行时库函数的使用类似于相应编程语言内部的函数调用。

API函数

omp_in_parallel:判断当前是否在并行域中;

omp_get_thread_num:返回线程号;

omp_set_num_threads:设置后续并行域中的线程个数;

omp_get_num_threads:返回当前并行区域中的线程数;

omp_get_max_threads:获取并行域可用的最大线程数目;

omp_get_num_procs:返回系统中处理器个数;

omp_get_dynamic:判断是否支持动态改变线程数目;

omp_set_dynamic:启用或关闭线程数目的动态改变;

omp_get_nested:判断系统是否支持并行嵌套;

omp_set_nested:启用或关闭并行嵌套;

omp_init(_nest)_lock:初始化一个(嵌套)锁;

omp_destroy(_nest)_lock:销毁一个(嵌套)锁;

omp_set(_nest)_lock:(嵌套)加锁操作;

omp_unset(_nest)_lock:(嵌套)解锁操作;

omp_test(_nest)_lock:非阻塞的(嵌套)加锁;

omp_get_wtime:获取wall time时间;

omp_set_wtime:设置wall time时间。

环境变量

OMP_SCHEDULE:用于for循环并行化后的调度,它的值就是循环调度的类型;

OMP_NUM_THREADS:用于设置并行域中的线程数;

OMP_DYNAMIC:通过设定变量值,来确定是否允许动态设定并行域内的线程数;

OMP_NESTED:指出是否可以并行嵌套。

ICV

OpenMP规范中定义了一些内部控制变量ICV(Internal Control Variable),用于表示系统的属性、能力和状态等,可以通过OpenMP API函数访问也可以通过环境变量进行修改。但是变量的具体名字和实现方式可以由各个编译器自行决定。

参考资料与扩展阅读

OpenMP编译原理及实现技术[M]. 清华大学出版社, 2012.

将GPT硬盘转换为MBR并安装Windows 7

2014-04-01 • 技术文章

现在的新硬盘基本都采用GPT,在安装Windows 7时会遇到提示无法安装到GPT硬盘这种情况,如果可以接受将硬盘转换为MBR那么建议转换(即没有怕丢失的数据且硬盘小于2TB)。

在进入到选择安装分区步骤时,按下Shift+F10调出命令行,输入diskpart回车,使用list命令调出磁盘列表,选择磁盘编号select disk 0(这里的数字根据列出的表中要修改的那个的编号来写),执行clean完成清理,然后执行convert mbr即可将GPT转换为MBR。

PAT-1001. A+B Format题解

2014-03-31 • 技术文章

给定两个整数a和b,按三位逗号分割的格式将和输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
 
int main() {
	int a,b;
	scanf("%d%d", &a, &b);
	a += b;
	if(a<0) {
		a = -a;
		printf("-");
	}
	char str[10];
	b = sprintf(str, "%d", a);
	for(a=0;a<b;a++) {
		printf("%c", str[a]);
		if(0 == (b-a-1)%3 && b != a+1) {
		 	printf(",");
		}
	}
	return 0;
}

朴素贝叶斯算法特征分类举例

2014-03-03 • 技术文章

贝叶斯公式

贝叶斯公式(Bayes Rule)由英国数学家贝叶斯(Thomas Bayes,1702-1763)发展,用来描述两个条件概率之间的关系。它是概率论中最常用的公式之一,其表达形式是:P(A|B)=P(B|A)*P(A)/P(B)。其中P(A)是A的先验概率或边缘概率,之所以称为"先验"是因为它不考虑任何B方面的因素。P(A|B)是已知B发生后A的条件概率,也由于得自B的取值而被称作A的后验概率。P(B|A)是已知A发生后B的条件概率,也由于得自A的取值而被称作B的后验概率。P(B)是B的先验概率或边缘概率,因为在比较时是个常量可以忽略为1所以也称标准化常量。继续阅读前,本文假定你了解贝叶斯公式,不再对其进行详述。若不了解请参考概率论教材或者查询百科。

朴素贝叶斯分类

贝叶斯常被用来进行特征分类,并且常被作为分类方法可靠性的参照。上面的公式针对的是单一的特征下的情况,当有多个特征时情况则复杂起来。假如这些特征有相互影响则无法通过简单的方式来应用贝叶斯公式求解条件概率,假如特征间没有相互影响则可以通过贝叶斯公式来分特征求积计算,没有影响情况下的分类称朴素贝叶斯分类。其计算公式在多特征情况下被推广为:

bayes.png

用朴素贝叶斯分类进行分类的举例

这里我们引用了加州大学欧文分校的垃圾邮件检测作业来作为朴素贝叶斯分类算法的例子。例子中有两个数据文件,每个都有4601行,其中一个文件有57列分别作为57种特征(每个特征仅有1和2两种取值),另一个文件仅有一列(1代表不是垃圾邮件,2代表是)。我们不妨取其中的前4096行作为分类训练数据,取余下的行进行准确率的检测,当然你也可以取其它的行数。

为了进行训练一个分类器,我们需要编写一个训练的函数,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function [params] = nbayes_learn(traindata,trainlabels)
%  function to learn from data the probabilities for a naive Bayes model 
%
%  Inputs
%     traindata: a n x d data matrix, d features/variables and n observations
%     trainlabels: a n x 1 vector of classlabels for traindata  
% 
%  Output
%     params: a stucture for the parameters for a Naive Bayes classifier
%     params(j).mprobs(k): probability that variable j takes value k
%     params(j).cprobs(k,i): conditional probability
%                          of prob(variable j = value k | class = value i) 
%     params(1).classprobs(i): probability that class variable = i 
 
% ... define global parameters, etc............ 
nclasses = 2;
[n, d] = size(traindata);
% Estimate class probabilities and conditional probabilities  
for i=1:nclasses
    index = trainlabels==i; % 将是/否为垃圾的分类取出
    ni = sum(index);
    params(1).classprobs(i) = ni/n;  % estimate the probability of class i 
    for j = 1:d 
        rowno = find(index==1);  % 获取该分类中满足的行号
        row = traindata(rowno, j); % 取得所有满足行中第j列
        for k=1:2; 
            % estimate prob(variable j = k | class i)
            params(j).cprobs(k,i) = (size(find(row==k), 1) + 0.5)/(ni + 1);
        end
    end
end
 
% Estimate the probabilities p(x_j = value_k)
for j = 1:d 
    for k=1:2; 
        % estimate  prob(variable x_j = k)
        params(j).mprobs(k) = sum(traindata(:,j)==k)/n;
    end
end

接下来是检测是否为垃圾邮件的函数,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function [predictions] = nbayes_predict(params,testdata)
%  function to make class label predictions on test data,
%  using a naive Bayes model (as described by the structure "params") 
%
%  Inputs 
%     params: a stucture for the parameters for a Naive Bayes classifier
%     params(j).mprobs(k): probability that variable j takes value k
%     params(j).cprobs(k,i): conditional probability
%                          of prob(variable j = value k | class = value i) 
%     params(1).classprobs(i): probability that class variable = i 
%
%     testdata: n x d data matrix, d features/variables and n observations 
%
%  Outputs
%     predictions: n x 1 vector of class predictions
 
% .....determine the number of test data points, etc.....
nclasses = 2;
[ntest,d] = size(testdata);
predictions = zeros(ntest, 1);
% for each of the test data points
for m=1:ntest
    x = testdata(m,:);
    prob = zeros(1,2);
    % for each class value calculate log[ p(x|c) p(c) ]
    for classi=1:nclasses; 
        prob(classi) = log(params(1).classprobs(classi)); % 类概率
        for varj=1:d 
            prob(classi) = prob(classi) + log(params(varj).cprobs(x(1,varj), classi));
        end
    end
    % select the maximum value over all classes as the predicted class
    % and store the class prediction for each test data point 
    predictions(m) = find(prob==max(prob)); % 返回最大的下标
end

下面是调用以上两个函数进行计算识别率的文件,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
% 垃圾邮件检测
function spamMail(n)
trainlines = n; % 定义要作为训练集的行数,余下行全用于测试
spam_features = load('spam_features.txt');
traindata = spam_features(1:trainlines, :);
spam_labels = load('spam_labels.txt');
lines = size(spam_labels, 1);
trainlabels = spam_labels(1:trainlines, :);
testdata = spam_features(trainlines+1:lines, :);
testlabels = spam_labels(trainlines+1:lines, :);
params = nbayes_learn(traindata, trainlabels);
predictions = nbayes_predict(params, testdata);
rate = sum(predictions==testlabels)/(lines-trainlines)*100;
fprintf('训练数据 %d 行,余下行全作为测试数据。\n识别准确率为 %.1f%%。\n', trainlines, rate);

输出如下,其说明的问题显而易见不再赘述,当然可更随意设定训练和测试数据集会更好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
>> spamMail(4096)
训练数据 4096 行,余下行全作为测试数据。
识别准确率为 88.3%。
>> spamMail(2048)
训练数据 2048 行,余下行全作为测试数据。
识别准确率为 88.6%。
>> spamMail(1024)
训练数据 1024 行,余下行全作为测试数据。
识别准确率为 89.3%。
>> spamMail(4500)
训练数据 4500 行,余下行全作为测试数据。
识别准确率为 87.1%。
>> spamMail(100)
训练数据 100 行,余下行全作为测试数据。
识别准确率为 88.4%。
>> spamMail(10)
训练数据 10 行,余下行全作为测试数据。
识别准确率为 80.5%。
>> spamMail(3)
训练数据 3 行,余下行全作为测试数据。
识别准确率为 53.5%。