整理一下看过的论文

还是得多看别人的论文,看多了等自己有东西能写的时候才能写得出来。

迷迷糊糊地就发出去第一篇 Paper 了。。。回想起来也算是幸运吧。

把以前看过的论文都理一理,共享在 OneDrive 上了(似乎被墙了):

【My Paper Reading List - OneDrive】


Top Conference

嗯。。。当年曾经想看看顶会上的文章的,但是那时候水平有限,只是简单地翻了一下,以后有机会再多看看吧。

RDMA

这几篇文章主要都是我改 RDMA 版 TensorFlow 的时候看的,借鉴其中的通信协议的设计思路,这里面的很多想法其实都是大同小异。

用 RDMA 有个比较严重的问题是:为了做到 kernel bypass,通信用到的内存都必须提前注册成 MR,这样 IB 卡就能直接读写内存而不用通过 CPU。现场注册内存是一件比较耗时的事情,如果处理不好会在这里浪费很多时间。

大致的想法很简单,这下面的几篇文章讲的也都差不多是类似的内容:内存管理/通信/计算 overlap。

主要是实现起来还是有点麻烦。

2001 - An introduction to the infiniband architecture

IB 架构的介绍,没怎么看,这条就纯用来引用。

2004 - Host-Assisted Zero-Copy Remote Memory Access Communication on InfiniBand

To be read.

2006 - RDMA Read Based Rendezvous Protocol for MPI over InfiniBand Design Alternatives and Benefits

在 MPI 库层面做的工作,改的是 MVAPICH,可能到今天已经整合进 MPI 的官方 RDMA 实现里面了吧。

主要内容是用 RDMA_READ 换掉原本 MPI 实现中的 RDMA_WRITE 协议,配合中断机制,达到计算和通信的最大程度 overlap。

To be read.

2007 - Memory Management Strategies for Data Serving with RDMA

To be read.

2008 - An efficient design for fast memory registration in RDMA

跟前面的 RDMA_READ 不同,这篇文章主要讲了一种 Conditional RDMA Write 的机制,目标也是在用 RDMA_WRITE 的时候 overlap 通信和计算。

关于 CRW 这种机制,RDMA 的官方文档里面我没找到,不知道这种方案是不是他们自己实现的。

To be read.

2009 - Minimizing the Hidden Cost of RDMA

主要还是针对 RDMA 通信过程中的内存管理进行优化,方案基本上还是那几个:

  1. 根据发送的数据大小决定是重用 buffer 还是创建一个新的。例如小数据直接 memcpy 到注册好的内存里,大数据创建新的 MR;
  2. 把通信和内存管理 overlap 开;
  3. 注册内存的时候考虑内存在物理上的分页;
  4. 并行注册 MR。

嗯,有一种道理我们都懂,关键看你怎么实现的感觉。

To be read.

2011 - Scalable Memory Registration for High Performance Networks Using Helper Threads

创建一个新线程来专门维护 RDMA 通信用到的内存,MR 的注册什么的都通过新线程来做。

其他的大同小异。

To be read.

2016 - Revisiting RDMA Buffer Registration in the Context of Lightweight Multi-kernels

To be read.


Deep Learning

2012 Alexnet - Imagenet classification with deep convolutional neural networks

大名鼎鼎的 Alexnet。

2012 年 ImageNet 的冠军算法,这一历史性的事件似乎可以看成是深度学习热潮的起点。

最早我开始接触深度学习方面的知识的时候分析过 Alexnet 的结构,事实上我对 CNN、卷积、全连接等等有个比较明确的认识也就是从这个网络开始的,之后在我的文章里面也是拿 Alexnet 作为我的 Benchmark。

Alexnet 比较突出的贡献还有就是提出了一些防止过拟合的方法:

  1. 对整个 256x256 的图片做一遍水平翻转,同时按照 224x224 做滑窗,相当于把原本的 1 张图变成了 2048 张
  2. Dropout 层!!

嗯,跑完整个 ImageNet 的数据集,作者用 2 块 GTX 580 跑了五六天。

2014 - Adam: A Method for Stochastic Optimization

一种效果比梯度下降更好的优化修正方法。

To be read.

2014 Baidu - Deep Speech Scaling up end-to-end speech recognition

百度做的端到端语音识别框架。

Mozilla 用 TensorFlow 把他们的这个工作实现了一遍,在这里

To be read.

2017 HKBU - Benchmarking State-of-the-Art Deep Learning Software Tools

香港浸会大学对几个主流 DL 框架做的一些对比评测,实验室师兄据说看出问题来了。详细的还没仔细看。

也就是 DLBench 项目

To be read.

2017 Facebook - Accurate, Large Minibatch SGD Training ImageNet in 1 Hour

Facebook 做的大规模 GPU 集群训练,顺便推一波 Caffe2。

256 块 GPU,1 小时内跑完整个 ImageNet 的数据集训练,想想都可怕。

这个回头得作为重点好好看看。

To be read.


TensorFlow

花了比较多的时间在 TensorFlow 这个框架上,源码也折腾过很久,但是最后还是觉得这玩意改起来过于复杂。

首先是 TF 的 Google 4 部曲:

1 - TensorFlow A System for Large-Scale Machine Learning

TensorFlow 开山之作,TF 本体也是跟着一起发布,基本把整个框架的情况都讲了一遍。

2 - TensorFlow Large-Scale Machine Learning on Heterogeneous Distributed Systems

TensorFlow 分布式版的介绍,v0.8 版 TF。

话说其实在第一篇里面就已经介绍过分布式了,这篇是更详细地介绍其运行机制。

3 - Deep Learning with Dynamic Compution Graphs

TF 的动态图功能。

暂时还没研究过。

4 - In-Datacenter Performance Analysis of a Tensor Processing Unit

TPU 的介绍。

发布这篇文章的时候其实 TPU 在 Google 内部已经测试了快一年了,基本上可以说是跟 TF 同期开始做的东西。

可怕。

2016 - DeepSpark A Spark-Based Distributed Deep Learning Framework for Commodity Clusters

用 Spark 来做上层框架,底下跑单节点版的 TF 来完成多节点分布式。

2016 - Distributed TensorFlow with MPI

跟上面那篇 Spark 的类似,这是用 MPI 做上层框架(大概是 Python-MPI),底下跑单节点版的 TF 来完成多节点分布式。


Algorithm & Math

1991 - Wait-free parallel algorithms for the union-find problem

多线程下的并行并查集实现,说起来这个也是该花时间好好研究一下。

下面有个别人的实现 Lock-free parallel disjoint set data structure

1971 ~ Today - Tarjan’s Algorithm & Data Structure

Robert E Tarjan,1986 年图灵奖得主,发明了一堆经典算法(主要是图和树的)。


Other

帮本科生看 SCC17 赛题的时候读的论文:

2014 - A practical guide to identifying members of the Bemisia tabaci species complex and other morphologically identical species

一篇有关一种白蚁物种分类的综述。

某个白蚁种群中有大约 34 种不同的种类,区分这些种类并且对一个未知个体来说,如果能快速识别出属于哪一个种类对于生物学研究来说至关重要。但从形态学和种系演变方面很难做到。

为了生物研究能够继续做下去,科学家开始从基因和概率分析方面想办法。

在已有一个成熟的线粒体 DNA 库的基础上,目前可行的方案是对个体进行 DNA 采样和 PCR 倍增,然后用 HPC 的技术来分析 DNA 的结构,找出进化树,最后判别属于哪个种群。

2001 - An Introduction to Bayesian Inference of Phylogeny

介绍了如何用贝叶斯推论的方法来分析物种的种系进化,就是上面那篇综述中的可行方案。

贝叶斯推论这种方法大概是:根据看到的现象来反推出初始情况(?我的理解可能有误)

文中一开始是拿骰子举例,假设盒子里面有 100 个骰子,90 个是正常的,10 个是有偏重的。从中随机取出一个骰子投两次,根据这两次投出的结果,我们可以算出正常骰子出现这种结果的概率和偏重骰子出现这种结果的概率,再反推出这个骰子是正常的还是偏重的的概率。

大概是这么个问题,实际情况下会更难一点,假定我们不知道 90/10 这个数量信息,也不知道偏重骰子投出每个点数的概率,然后还要根据观察到的现象推断出骰子的情况(。。。666)。

种系生成学中,物种的进化关系可以用一棵生成树来表示,每种基因都有一定概率突变成其他的基因,生成树上的分支就是由于基因突变产生的。跟贝叶斯推论的方法结合在一起,就是事先根据一定的模型定下生成树的结构,然后枚举所有进化情况的概率(?大概是这样),从里面找出似然度最大的一种,就是最终的进化推断了。

嗯,上面这个方法看上去就很有问题。。。首先,只要用于分析的 DNA 链不短,那么进化树的可能情况应该是指数上涨的,并且贝叶斯推论需要的后验概率也没有办法确定下来。

所以就需要马尔科夫链蒙特卡洛方法。构造一条马尔科夫链,用它的平稳分布作为问题所需要的后验分布,基于马尔科夫链达到平稳分布时的有效样本进行蒙特卡洛积分(?其实并不是很懂)。

马尔科夫链有个初始状态,然后计算转化到下一个状态的概率,如果超过某个值就是可以接受的,马尔科夫链转化成下一个状态然后继续进行下一轮迭代。在这个迭代过程中,对马尔科夫链进行采样(?),采样出的分布作为进化树的后验分布然后计算贝叶斯推论(?)。

例如 MrBayes 中的几个参数:马尔科夫链迭代多少代,每多少代采样一次

后面又举了个实际的例子:用 5 条 DNA 数据进行分析,分别来自鱼、青蛙、鸟、鼠类和人。这 5 个物种的进化树有 15 种可能(根据某种模型计算出来的)。马尔科夫链迭代 100000 代,跑完 10000 代之后开始每 100 代采样一次,这样就得到了 900 个采样结果(900 棵进化树?)用这 900 个采样的数据作为后验分布进行贝叶斯推论分析就得到了最后的结果。(某一条进化枝的后验概率,就是所有树中包含这条进化枝的概率和?)(最后结果大概就是这 15 种可能的进化树分别的概率,概率最高的一种就是推论得出的进化树答案了)


Mine

2017 - Improving the performance of distributed TensorFlow with RDMA

16 年参加 RDMA 竞赛的时候,赛题就是分布式版 TensorFlow 的 RDMA 实现。当时采用的方法是把 TF 中的通信模块 gRPC 改成 RDMA 的,这样 TF 本体就不用动了(事实上当时试过直接改 TF,但是不知道该从什么地方下手)。

当时比赛结束之后没有放弃这个题目,继续尝试从 TF 本体上下手,把整个 gRPC 给干掉。

最后终于成功做出来了,想想也是悲惨。。。如果重新经历一遍我不敢说能不能再做到了。

后来发现了 Yahoo 的 RDMA 版 TF 项目,跟我们做的工作基本上是一样的,心里一凉,不过东西都做了大半年了,想想还是硬着头皮把文章写完了。投文章的时候看着他们的项目从 pull request 开始,一点点被 TF 官方的 Repo 吸收,最后终于在 1.2.0-rc0 收录了。特别煎熬。

最后中了 NPC 有很大的运气成分吧。


To be continued.

Show comments from Gitment
0%