并行编程实战记录
工作半年以来，大部分时间都在做RNN的研究，尤其是通过lstm（long-short term memory）构建识别模型。我专注的是使用rnnlib工具开展模型的训练工作，以搭建有效的识别模型。Rnnlib（http://sourceforge.net/projects/rnnl/）由Alex Graves提供，是解决序列识别问题的RNN工具包，尤其是对隐含层提供了lstm的算法实现。在Alex Graves的博士论文中（Supervised Sequence Labelling with Recurrent Neural Networks），他提出了CTC（Connectionisttemporal classification）算法，克服了传统识别算法中序列数据需要预先分割的缺陷。在rnnlib中，CTC也得到了实现。
当识别问题的类别非常多时，隐含层到输出层的连接边数目大幅增加，这也使得反向更新权重时需要耗费更多的时间。实际上，这是一个计算密集型的任务。典型地，在我们的训练中，训练样本为十万级别的规模。在双CPU--Xeon(R) CPU E5(2.60GHz，8核16线程)、x64的服务器平台下，一次迭代需要花费18h左右的时间。而这里训练一个模型需要至少100多次的迭代，因此这个训练效率是难以忍受的。实际上，在rnnlib源代码中，作者实现的是一个单线程版本。于是，我开始了漫长的并行编程实战，通过将rnnlib并行化以提高计算的效率。在这里，我将摸索的过程进行了总结。
首先对模型训练的过程进行一下简单的描述。每次迭代都是一样的过程，根据所有训练样本前向计算输出、CTC计算误差项、反向更新权重。在每次迭代中，可以采取一种近似于随机梯度SGD的方式，也就是设置一个batchsize，每批batchsize个样本更新一次模型，而不是对所有样本计算一次更新。
1. 多线程
1.1 多线程框架
在这里，我们写好了多线程的接口框架，使用了线程池的方式。主线程不停读取任务并保存在线程池的任务列表中。线程池中的线程不断从任务列表中读出任务并执行。在读出任务时，需要使用锁实现互斥访问，以保证安全性。此外，主线程存储任务与其他线程读出任务也需要通过锁实现任务列表访问的互斥性。当任务列表中的任务全部读出后，通过条件变量使线程陷入等待，而新存储的任务会通过notify信号量重新激活线程。
当batchsize个样本读入完毕后，通过条件变量试主线程陷入等待而不继续读入任务。直至所有其他线程将手头的任务执行完毕，通过判断等待线程数与总线程数相等而激活主线程，完成一次同步操作。由主线程将本批计算得到的误差derivative用于计算权重weights。然后继续以上循环，执行下一批batchsize，直至所有训练样本执行完毕。
以上多线程接口可移植性比较好，直接将任务替换为rnnlib中相应的计算函数（包括前向计算输出、CTC计算误差项）即可。在我们的服务器平台下，双CPU共包含16核32线程，所以将多线程程序中的线程数设为32。通过实验发现，此时一次迭代所需时间下降到约8h4m。显然，运行时间不会以32倍提高，因为线程调度也需要花费时间。
1.2 进一步优化：分块读取样本数据
通过阅读rnnlib源代码，发现DataList在处理sequence时会以NetcdfDataset的结构一次性读入整个nc文件。如果nc文件比较大，那么一次性读入将会占用较大内存空间，可能影响CPU的运行速度。而nc文件中的训练样本是按顺序依次处理的，因此靠后的训练样本只会空占内存。所以，我们将nc文件进行了分块，将训练样本按序平均分配到子nc文件中。在运行时，保证同一时刻内存中只有两个子nc文件，一个是当前正处理的子nc文件，另一个是下一个将要处理的子nc文件。当前子nc文件处理完毕后，直接开始处理下一个子nc文件，同时释放前一个子nc所占用的内存，并准备好下一个将要处理的子nc文件，将其读入内存。具体来说，通过两个NetcdfDataset指针即可实现。
这样，占用内存的训练样本大大减少，而比较靠后的训练样本则停留在磁盘空间中，在需要时调入内存即可。为了节省时间，可以专门开一个线程用于读取下一个子nc文件，使得当前子nc文件的处理与下一子nc文件的读取同时进行。但是要通过条件变量做好逻辑控制，保证在处理下一子nc文件之前，该子nc文件读入内存已完毕。通过这些优化，运行效率又一次得到了提高。通过实验发现，当将训练样本分成60个部分时，一次迭代所需时间下降最多，耗时约6h50m。
2. MPI多进程
以上单次迭代所需时间仍然较多。实际上以上分析已经发现，在一个batchsize中，所有sequence是完全可以并行的。所以，我们想到通过多机并行进一步提高运行效率。在不同机器中，程序分属于不同进程，它们并不能共享内存，我们有必要先了解一下线程与进程的概念与区别。
2.1 线程与进程的区别
进程是一个具有独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的一个独立单位。进程是一个动态的概念，是一个活动的实体。它不只是程序的代码，还包括当前的活动，通过程序计数器的值和处理寄存器的内容来表示。进程是一个“执行中的程序”。程序是一个没有生命的实体，只有处理器赋予程序生命时，它才能成为一个活动的实体，我们称其为进程。
通常在一个进程中可以包含若干个线程，它们可以利用进程所拥有的资源。在引入线程的操作系统中，通常都是把进程作为分配资源的基本单位，而把线程作为独立运行和独立调度的基本单位。由于线程比进程更小，基本上不拥有系统资源，故对它的调度所付出的开销就会小得多，能更高效的提高系统内多个程序间并发执行的程度。
进程和线程的区别归纳：1.地址空间和其它资源：进程间相互独立，同一进程的各线程间共享。某进程内的线程在其它进程不可见；2.通信：进程间通信IPC，线程间可以直接读写进程数据段（如全局变量）来进行通信（需要进程同步和互斥手段的辅助，以保证数据的一致性）；3.调度和切换：线程上下文切换比进程上下文切换要快得多。
对于单核机器，通过多线程可以减少I/O等阻塞时间，有利于人机交互。此时的多线程叫做“并发”，通过单核分时间轮转调度来实现。看似并行，实则单核一次仍然只处理一个线程，只是切换快速难以察觉而已。而对于计算密集型任务，单个任务已经将单核接近占满，因此多线程难以提高效率。
在多核机器上，Linux2.6和WindowsNT4.0以上已经可以将不同线程交给不同的核心去处理，因此多线程可以提高计算密集型任务的处理效率。并行计算可以看成是多进程，每个进程交给一个核（或者超线程技术下的虚拟内核）去执行，这种方式是真正意义上的并行。需要注意的是，描述CPU性能中的几核几线程与多线程编程中的线程是两个不同的概念，前者指的是虚拟内核。
2.2 MPI协议及MPICH框架
在这里，我们选择使用MPI来实现多机并行。MPI（MessagePassing Interface）是一个跨语言的通讯协议，用于编写并行计算机，支持点对点和广播。MPI只是一个协议，有不同的实现版本。这里采用MPICH（http://www.mpich.org/）进行多机并行的编程，比较有用的参考博客文章有http://blog.csdn.net/morewindows/article/details/6823436。MPI并行环境配置的参考博客文章http://blog.sina.com.cn/s/blog_7f40d1c10101f18x.html。要注意安装过程中的passphrase在各台server上必须设置为一样的口令，否则将连接不上。
在MPICH执行前，将程序的可执行文件及所需的数据文件部署到每台服务器上。在主机上通过cmd运行mpiexec.exe –hosts n serverip_1 procnum_1 serverip_2 procnum_2 …serverip_n procnum_n –noprompt yourprogram.exe开始执行。MPICH会根据-hosts的设定为每个进程分配rank_id，每个进程会根据自己的rank_id去执行程序中的不同部分。通过MPI中的通信函数可以实现进程之间的数据传输。
我们并行框架如下图所示：
我们把训练程序和训练样本提前部署到服务器上，每个进程处理训练样本中的一部分。每一个batchsize平均分配给所有的进程部处理，待所有进程均处理完毕之后，由主进程收集误差数据并用于更新权重。更新后的权重广播到所有进程，再开始下一个batchsize。注意，这里有一个同步操作，即等待所有进程处理完毕，才能由主进程开始权重更新。这个同步操作是很好理解的，但也不可缺少。部署好之后，我们用两台服务器进行了实验。这里我们的服务器有32个线程（包括物理的和虚拟的，注意与多线程编程中的线程不是一个概念），所以将两台服务器的线程数都设为32。需要注意的是，在第一台服务器上只有31个线程是用来计算sequence的，因为要牺牲一个进程作为主进程。这样，一次迭代所需的时间约为6h。
2.3 进一步优化：样本数据预排序
可以发现，多机并行实验结果不够理想，并不明显优于单机的多线程。这是为什么呢？通过打印调试，我们发现前述同步操作花费了较多的时间。即便我们将进程间的通信不断进行优化，实验结果也没有提升。所以，我们基本可以确定效率被同步操作耽误了。
仔细思考，不难发现样本越长（时间点越多），前向计算输出和CTC计算前向变量、后向变量都需要更多的时间。而同步操作所需时间是由耗时最长的那一个进程决定的。极端情况下，每次batchsize时，都有一个进程处理较长的样本，哪怕是其他的样本都很短。因此处理短样本的进程在处理完之后将陷入等待，而每次batchsize的耗时都会很长。
而我们这里采用的优化办法就是对样本进行预处理，使得每次batchsize中的样本的长度都大致相当，这样就可以减少等待时间。实现的方式是根据timestep长度对样本进行预排序，然后按序逐一分配给所有进程。在实际操作时，比如两台服务器共有32*2-1=63个从进程，那么我们将预排序后的训练样本逐一分配给63个section，然后利用这63个section分别制作nc文件，然后提前部署到服务器上，由进程各自处理属于自己的那一个nc文件。可以发现，经过这样的处理之后，63个nc文件的大小几乎没有差异。
可惜的是，经过这样的优化处理之后，多机并行的效率并没有多大改观，反而下降到7h7m。但是，通过观察打印输出，我们发现前800个batchsize都执行的非常快，基本上都在20s以内，但最后的200多个batchsize由于都是大样本，一个需要一两分钟，严重拖慢了效率。也就是说，一半以上的时间都用来处理最后这20%的样本了。经过思考，我们决定对每个section内部的样本序列进行随机打乱，以避免某些batchsize过大。实验证明我们的尝试是正确的，一次迭代所需时间下降到4h40m左右。需要说明的是，虽然最后又将各个section内部的样本顺序打乱，但最开始的完全排序是有必要的，它可以使各个section的样本规模大致相当。因此，我们最后的样本预处理策略是：先对所有的样本进行升序排序，然后逐一分配到各个section，然后在各个section内分别打乱顺序，然后制作nc文件，用于MPI多进程处理。最后，有理由相信，通过更多服务器的多机并行，运行效率会得到进一步的提升。
3. 总结
通过这一个多月的学习与摸索，我对多线程和多机并行有了更深的理解。通过实战，我发现多机并行编程是一个很有意思的事情，与算法研究是两个不同类型的事情，需要考虑的实际情况更复杂，有助于加深对计算机体系的认识。而这其中碰到问题分析问题解决问题的过程让我受益匪浅。MPI只是一个比较底层的并行协议，后续，我将继续学习hadoop和spark。