基于共享内存的多核并行计算

19.2　基于共享内存的多核并行计算

对于基于共享内存的并行计算主要通过在程序设计时的多线程机制来实现。具体实现层面，在C＋＋编译器g＋＋中，POSIX线程作为一个POSIX标准线程，被广泛应用于对线程进行操作，我们通常称之为pthread，通过对相关API的调用可以很方便地创建和操作线程。

在多线程处理时，其中最需要注意的就是对临界区的处理。pthread中，临界区的处理多是通过加锁来实现的，这也是我们在编程时尤其要注意的地方，在同一组API下，采用不同的锁机制产生的效果可能不尽相同。在pthread中，提供了多种锁机制：互斥锁（Mutex Lock）、自旋锁（Spin Lock）、条件变量（Condition Variable）和读写锁（Read/Write Lock）等。

在程序中，我们用得较多的是互斥锁和自旋锁，即pthread_mutex_lock和pthread_spin_lock，在很多应用中，两者间的区别并不明显，但是在计算机围棋程序的开发中，由于我们要追求的是效率，也就是在单位时间内可以完成的模拟次数，这两者的不同就凸显出来。

互斥锁属于阻塞型的锁，当两个线程共同对一个临界区进行操作的时候，如果临界区被其中一个线程所持有，那么当另外一个线程也运行到临界区时，另外一个线程就被阻塞，而进入等待队列重新排队。而自旋锁则采用另一种机制，也就是非阻塞型的锁，当遇到被占有的临界区时并不会被阻塞，而是不断地进行锁请求，直到得到这个锁为止。

互斥锁和自旋锁的差别主要在多核时表现比较明显，对于单核的情况则差别不大，但也要根据实际情况来具体选择。比如，在一个双核的机器上有两个线程（线程A和线程B），它们分别运行在核0与核1上，当线程B遇到一个临界区想要对其加锁时，如果发现这个临界区正被线程A所持有，那么：①对于互斥锁的情况而言，线程B就会被阻塞，从而进入等待队列，而核1则会进行一个上下文切换，去执行其他的任务；②对于自旋锁的情况，线程B则一直占有核0，并不断地进行锁请求的操作，直至获得对临界区的操作权。从这个例子中，我们可以发现，对于一个核的情况，基本上不会产生很大的差别，而当处理器的核数超过两个之后，便可以很明显地感觉到其不同。

在蒙特卡洛博弈树搜索中，我们需要的是尽量让程序榨取CPU的计算能力，也就是尽量的让所有的核都以百分百的精力为围棋程序服务，从这个目的上看，自旋锁才是我们在围棋程序中所需要的。通过采用自旋锁可以保证每个线程能在临界区被释放后立即占有临界区，而互斥锁则将线程阻塞并放到等待队列中，在其所等待的临界区被解锁后还需要等待一定时间才能被CPU所执行，然后对临界区进行操作。

采用pthread实现并行策略，需要对原有代码做稍许调整。对root节点的simulate从只启用一个线程变为启动多个线程，同时保证线程数目不超过CPU核的数目。

Listing19.1　创建多线程伪码

除了要创造出多个线程进行模拟操作以外，还需要找到所涉及到的临界区，包括树的生长导致的节点数目的改变，以及每个节点访问信息等属性的变化。通过对临界区进行加锁处理，来保证对临界区的原子操作，其中，Listing17.5中的第18～20行就是该需要加锁的临界区，通过在这个临界区首尾分别进行加锁和解锁操作，来保证对临界区操作的原子性。

Listing19.2　临界区