Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

Tools of the trade

本篇是对《Is parallel programming hard》第四章《Tools of the trade》的总结,不是单纯的翻译,算是读书笔记,并且略有补充。

本章介绍了并行编程的工具和途径,具体包括

  • Shell Script Languages
  • POSIX 多进程
  • POSIX 多线程
  • 原子操作

Shell Script Language

如果不同的执行单元之间没有过多的数据交互,待执行的任务分区性较好,那么我们可以考虑通过Shell创建多个进程来完成任务。例如,我们需要计算每连续的100个元素的和,需要计算3组,好吧,比如说我们需要计算1+2+3+…+100101+102+…200201+201+…+300,那么我们可以编写一个程序,然后通过Shell创建3个进程,通过命令行传入参数(比如这里的待求和的元素的起点)。

compute 1 > compute_1.out &
compute 101 > compute_2.out &
compute 201 > compute_3.out &
wait

其中compute是可执行程序名,1101201是命令行参数,> x.out代表将输出结果重定向到文件x.out中,&表示程序后台运行。wait表示等待运行程序结束。

那么多进程的并行设计有什么缺点呢?

1,创建进程的时间略长。在Intel Core Duo Laptop上创建一个最小C程序需要大概480ms。当你的任务执行时间和进程启动时间相比反而不值一提时,这时候创建进程所需的时间就显得很尴尬。多线程VS多进程也是SparkHadoop相比的一个不同。

2,进程间不共享内存,不利于通信和数据交互。

3,多进程间的同步相对费事复杂。

POSIX 多进程

可以通过forkkillwait等原语来创建、管理进程。书里简单介绍了这几个原语的使用,小结一下就是:

1,fork会有两次返回,一次对child process,一次对parent processfork的返回值为0代表在child process的上下文中,负数代表错误,正数代表parent process上下文中,并且返回值就是child processpid

2,parent processchild process并不share memory

POSIX 多线程

可以通过pthread_mutex_lock以及pthread_mutex_unlock等原语,以加锁和释放锁的方式,使用多线程来并行设计。

锁有多种,除了互斥锁,读写锁也是常见的一种。读写锁的特点是:

1,同一个时刻,允许多个读线程。当然,此时不能有写线程。

2,同一个时刻,最多只能有一个写线程进行更新操作。

也就是说写写互斥,写读互斥,读读不互斥。换句话说,要么多个读线程,要么一个写线程。

那么读写锁的scalability如何呢?作者写了一个程序来分析,程序运行在64cores,一共n个读线程,每个读线程的流程大概是:

while(not terminated)
{
  acquire the lock;
  do something;//t1
  release the lock;
  wait some time;//t2
  ++count of acquisitions;
}

把其中t2的时间设置为0t1的控制则是通过更改调整执行循环次数(图上所谓的100K100M神马的)。图上的横坐标为线程数目,纵坐标代表 $\frac {C}{nc}$ ,其中Cn个线程总共的acquisition数目,c是单个线程acquisition数目。

理想情况下,这个值应该是1.0

expriments for rwl

实验表明,当读线程的数目增多,每次acquire lock时,花在修改数据结构(锁也是一种数据结构实现,当一个读线程acquire或者release成功显然需要对数据结构进行修改,加加减减神马的)的时间将显著影响scalability。极端情况下,当n个读线程同时acquire时,第n个线程需要等前面的n-1个线程都修改完毕,它才能修改。

同时,注意到线程有n个,而CPU cores只有64个,因此当n<=64时,每个thread可以独享一个core,当n>64后,根据鸽巢原理,至少有一个core上有多个thread在运行,这也会带来性能下降。

因此,读写锁比较适合临界区比较大的情形(有文件IO或者网络访问等)。

如果临界区比较短呢?比如我仅仅是加加一个变量呢?哦,那么原子操作可能是一个很好的选择。

原子操作

gcc内置提供了一系列的原子操作。很多操作有两个版本,比如说:

__sync_fetch_and_sub()__sync_sub_and_fetch(),如名字所说,一个是先减,然后获得减之后的新值;一个是减,返回的是减之前的old value

此外,非常有名的CAS操作:

__sync_bool_compare_and_swap()__sync_val_compare_and_swap(),前者返回是否操作成功(待修改变量被替换为新值),而后者返回的是老值。

由于原子操作是让多个步骤看起来是一次的行为,因此往往包含Memory Barrier以保证语句的执行顺序。