foolyc

alphago mcts and python parallel

发表于 | 分类于 |
python的并性计算和Alphago的APV-MCTS算法

因为最近需要实现alphago中的apv-mcts算法的并行计算。刚好借此机会对python的并行/并发计算整理一番。

基本概念

进程与线程

在目前的冯洛伊曼计算机架构中，进程就是一个程序在一个数据集上的一次动态执行过程。 进程一般由程序、数据集、进程控制块三部分组成。我们编写的程序用来描述进程要完成哪些功能以及如何完成；数据集则是程序在执行过程中所需要使用的资源；进程控制块用来记录进程的外部特征，描述进程的执行变化过程，系统可以利用它来控制和管理进程，它是系统感知进程存在的唯一标志。

线程也叫轻量级进程，它是一个基本的CPU执行单元，也是程序执行过程中的最小单元，由线程ID、程序计数器、寄存器集合 和堆栈共同组成。线程的引入减小了程序并发执行时的开销，提高了操作系统的并发性能。 线程没有自己的系统资源，只拥有在运行时必不可少的资源。但线程可以与同属与同一进程的其他线程共享进程所拥有的其他资源。

线程是属于进程的，进程中所有线程共享同一个数据集，当进程退出时，其属所有线程均会清除。

并发与并行

并发是指，程序在运行的过程中存在多于一个的执行上下文。这些执行上下文一般对应着不同的调用栈。在单处理器上，并发程序虽然有多个上下文运行环境，但某一个时刻只有一个任务在运行。但在多处理器上，因为有了多个执行单元，就可以同时有数个任务在跑。

并行则指物理上同一时刻有多个任务同时运行的方式就是并行，和并发相比，并行更加强调多个任务同时在运行。

一般来说对于消耗IO资源的任务（比如网站服务器）属于并发，而消耗计算资源（比如神经网络的训练）的任务属于并行。

python的多线程和多进程

python的多线程的实现主要是基于threading类和thread类，其中threading是对thread的包装。这里对该模块不做太多介绍，网上例子很多。

cpython的多线程实现中使用了global interpreter lock（GIL),使得在同一时刻CPU只会执行一个线程，并没有实现并行，但是对于消耗IO的并发任务，还是能有效的提高效率。

因此如果要实现并行，必须要采用python的多进程模块，即python 2.6以后增加的multiprocessing模块，但是进程间内存块是独立的，如果要同时操作数据，必须进行通信，而进程通信开销比较大，因此使用多进程时需要合理划分系统任务，减少多进程之间的通信。

另外如果要采用多线程，方便共享内存数据，又希望多CPU运行，可以考虑python的其他实现版本，比如JPython等。

函数参数传递

函数

我们知道，python普通的函数调用，对于结构体参数，参数传递的实际是内存地址，也就是通常意义的指针或引用，而普通int等数据类型，则会对传入参数进行拷贝（或者认为函数调用时对参数进行了简单拷贝操作，但是python中就结构数据必须要深拷贝才能完全独立），比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def func(a):
    a*=2
    print a
if __name__=="__main__":
    a=1
    func(a)
    func(a)
    b= np.ones([4])
    func(b)
    func(b)
    c= [1, 2]
    func(c)
    func(c)

输出结果：

1
2
3
4
5
6
2
2
[ 2.  2.  2.  2.]
[ 4.  4.  4.  4.]
[1, 2, 1, 2]
[1, 2, 1, 2, 1, 2, 1, 2]

线程

采用多线程启动该函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if __name__=="__main__":
    a=1
    t1 = threading.Thread(target=func, args=(a,))
    t1.start()
    t2 = threading.Thread(target=func, args=(a,))
    t2.start()
    t1.join()
    t2.join()
    b= np.ones([4])
    t1 = threading.Thread(target=func, args=(b,))
    t1.start()
    t2 = threading.Thread(target=func, args=(b,))
    t2.start()
    t1.join()
    t2.join()
    c= [1, 2]
    t1 = threading.Thread(target=func, args=(c,))
    t1.start()
    t1.join()
    t2 = threading.Thread(target=func, args=(c,))
    t2.start()
    t2.join()

输出结果与直接函数调用一致，与前面对于线程的描述相符和。

进程

采用多进程启动函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if __name__=="__main__":
    a=1
    t1 = Process(target=func, args=(a,))
    t1.start()
    t1.join()
    t2 = Process(target=func, args=(a,))
    t2.start()
    t2.join()
    b= np.ones([4])
    t1 = Process(target=func, args=(b,))
    t1.start()
    t1.join()
    t2 = Process(target=func, args=(b,))
    t2.start()
    t2.join()
    c= [1, 2]
    t1 = Process(target=func, args=(c,))
    t1.start()
    t1.join()
    t2 = Process(target=func, args=(c,))
    t2.start()
    t2.join()

输出结果如下：

1
2
3
4
5
6
2
2
[ 2.  2.  2.  2.]
[ 2.  2.  2.  2.]
[1, 2, 1, 2]
[1, 2, 1, 2]

进程启动，拥有独立的内存空间。

总结

因此我们在实现alphago的APV-MCTS算法时采用多进程的话，不能将backup过程放在不同进程中，否则需要在进程间大量通信，保证Monte Carlo Tree的同步。合理的分配方案是，master process 负责in-tree search（即selection部分),将到达的leaf node 传给专门rollout policy 的一些进程和专门执行value network evaluation 的进程，将需要expand的节点传给执行 SL network的进程，同时接收三类进程返回数据， 接收rollout和value network返回的评估outcome进行backup，及用SL network计算得到的概率分布替换掉master process中临时用tree policy计算得到的概率分布，另外master process 中可以参用lock free 的多线程来执行selection 和backup.

这种框架也适合今后的分布式计算，配上分布式计算框架（比如RQ），是可以实现多机分布式APV-MCTS算法的。

本文由foolyc创作和发表,采用BY-NC-SA国际许可协议进行许可
转载请注明作者及出处,本文作者为foolyc
本文标题为alphago mcts and python parallel
本文链接为http://foolyc.com//2017/01/05/alphago-mcts-and-python-parallel-program/.