single core with multiprocess

主要记录下multithreading提升performance的一些点。

overlap communication with computing

首先要明确的一点是,一个core在单位时间内只能运行一个thread。如果已经指定好说一个program只能使用一个core,那么multithread仅仅是timeslicing而已,这样到底有没有效率?

具体可以参考这个

整理一下,唯一的好处就是来源于IO与computing的overlapping。如果对于计算密集型的application,那其实没有什么帮助,反而增加了额外的不同thread之间context switching的overhead,对于IO成分比较多的应用,一个thread在IO的时候可以将另外一个thread调度到core上来执行,这样总是保持cpu busy,在总体上可以节省时间。

当然在实际操作中,如果是multithread的program,通常让一个program占用多个cores。在实际的操作中,资源管理的软件cloud的环境中使用k8s+docker比较多,HPC的环境下使用slurm比较多,不管使用哪种软件,对于资源管理的core的划分的本质是类似的。就拿slurm的参数举例子吧,如果用srun启动一个process,然后指定--cpus-per-task为 k,就相当于这个process使用k个cores。

那么还有另外一个问题,同样是k个core,假设在同一个node上,到底是使用k个process 效率比较高还是一个process但通过multithreaing来使用k个cores效率比较高?

利用和前面同样的思路,如果全都是独立的计算类型的任务的话,也就是说彼此之间不存在IO的操作,应该没有什么大的区别,因为所有的core一直再被充分利用。比如相加两个array,总共资源是K个core(假设在一个node上),一种是使用k个MPI process每个process执行对应元素的相加操作,另外一种是启动一个openMP然后吧for loop 并行化了,不考虑cache的细节的话,本质上两个效率应该差不多。但如果有communication的话就不一样了。比如在不同thread之间的communication肯定比在不同process之间的communication要快速。而且task based 的 multithread 模型提供了task run asynchronously 的可能性,可以在一些thread执行computing的时候,另一些thread 执行communication。单纯的MPI的SPMD,并且一个process占用一个core,因为使用的是同样的代码,overlapping IO 和 comuting 的操作就比较困难,常常是要IO就一起IO要计算就一起计算。

有许多work展示了一个MPI+openMP的实际例子

Preissl R, Koniges A, Ethier S, et al. Overlapping communication with computation using OpenMP tasks on the GTS magnetic fusion code[J]. Scientific Programming, 2010, 18(3-4): 139-151.

很明显在multicores的node上,使用MPI+openMP(或者其他thread pool)的方式可以有可能性通过overlapping communication 与 computing 来提升性能,但是需要很好的对于原问题的优化和软件层面的巧妙设计。不同的MPI process 在交换信息的时候,如果使用multiproess,就会有IO和computing过程的overlapping。如果一个core一个MPI process,那不同MPI process在交换数据的时候,因为当前的core上只有一个thread,所以就会block在那里。因为只有这个数据传输完成之后才能进行下一步的迭代操作。

parallelism的类别

这里还要说下parallelism的类别的问题,比如从计算单元的角度来看,MPI使用的process level 的parallel,像openMP以及其他的类似cilk, TBB 这样的library使用的是thread级别的parallel。

从计算形式上来看,可以有structured parallel以及unstructured parallel。openMP 2.x 版本是structured parallel的典型代表,比如把一个for loop去用multithread的形式处理。在3.0版本之后,openMP也支持了task parallelsim也叫做unstructured parallelism在使用形式上就类似与thread pool的形式。从中取一个thread或者是新创建一个thread然后不管内部运行的是什么,具体调度由特定的thread scheduler来完成。这篇论文里介绍了很多相关的细节:

Ayguadé E, Copty N, Duran A, et al. The design of OpenMP tasks[J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 20(3): 404-418.

从数据和task的关系来看,可以是single task multiple data 或者是 single data multiple task。single task(instruction) multiple data 就是说同样的程序代码,然后把它所用与不同的数据分片上。反过来,就是同样的数据,去执行不同的任务。比如同样的数据,一个thread去基于这个数据做新的迭代,一个thread去将这个数据传输给其他的task,进行communication等等,这种形式的parallel更适合用task based 的方式,也就是unstructured parallel的方式。或者可以这么说,data parallelism的好处自不必说,把大的任务分解成小的任务,加快问题解决,这里说到底还是N:N的关系,N个人process对应N个data partition。那么task parallelism 的好处到底在哪里?特别是彼此有依赖关系的task。可能一个点就是在iteration的环境中,比如典型的像simulation,通过overlapping IO以及computing(体系结构课本里的那种pipeline的方式), 能让CPU被更高效的利用,因为毕竟说到底CPU是不同task共同share的资源,N:1的源头是在这里。

从具体使用的硬件来看,就是CPU, GPU , TPU, FPGA 等等,比如MPI+openMP 这是利用multicore的CPU, MPI+CUDA就是利用CPU以及GPU等等,从软件层面上看,还是怎么把问题映射到对应的硬件上,从硬件层面上看就有各种优化比如这里介绍如果通过统一的address space, rdma, gpudirect来实现GPU device上的数据不经过CPU直接传送到其他GPU上。

还有一个有疑惑的地方就是,multithread的scheduler如何知道当前的thread开始执行IO操作了从而把它调离CPU然后再将一个新的thread调度上来,这部分之后再具体整理。

references

https://www.epcc.ed.ac.uk/sites/default/files/PDF/mixedMode3.pdf

http://downloads.hindawi.com/journals/sp/2010/951739.pdf

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.108.1318&rep=rep1&type=pdf

unstructured parallelism in openMP
good explanation
https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4553700

https://www.quora.com/If-a-computer-has-only-one-CPU-do-multi-threaded-programs-provide-any-performance-improvements-over-single-threaded-programs

https://stackoverflow.com/questions/31988595/how-do-multiple-threads-run-on-single-core-cpu

推荐文章