2020-04-24

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调度上来，这部分之后再具体整理。