Amazon在hogwild、hogbatch之后,提出了《BlazingText: Scaling and Accelerating Word2Vec using Multiple GPUs 》,利用多GPU来加速word2vec的训练。
介绍
Word2vec是流行的算法。原始google c实现、以及facebook fastText可以利用多核cpu架构来并行化。还有一少部分实现方式则利用GPU并行化,但会牺牲accuracy和可扩展性。本paper提出了BlazingText,一个使用CUDA高度优化的word2vec实现,可以利用多GPU进行训练。BlazingText可以在8GPU上达到43M words/sec的训练速度,达到了8线程CPU实现的9倍,并且对embeddings的质量影响很小。
word2vec的最优化通过SGD完成,它会进行迭代式求解;在每一个step,会选取一个词对(pair of words):一个输入词和一个目标词,它们来自于window或一个随机负样本。接着根据选中的两个词来计算目标函数的梯度,然后基于该梯度值更新两个词的词表示(word representations)。该算法接着使用不同的word pair来处理下一次迭代。
SGD的一个主要问题是,它的顺序性;这是因为它在这一轮迭代的更新、与下一轮迭代的计算之间存在着依赖关系(他们可能遇到相同的词表示),每一轮迭代必须潜在等待前一轮迭代的更新完成。这不允许我们使用硬件并行资源。
然而,为了解决上述问题,word2vec使用Hogwild,它使用不同线程来并行处理不同的word pairs,并忽略任何在模型更新阶段中发生的冲突。理论上,对比起顺序运行,这会让算法的收敛率下降。然而,对于跨多线程更新不可能会是相同的词的这种情况,Hogwild方法已经得到验证能运行良好;对于大词汇表size,冲突相对较少发生,收敛通常不受影响。
Hogwild方法在多核架构上的成功,使得该算法利用GPU成为可能,GPU比CPU提供更强的并行化。在该paper中,我们提出了一种有效的并行化技术来使用GPU加速word2vec。
在深度学习框架中使用GPU加速,对于加速word2vec来说并不是好选择[6]。这些框架通常更适合于“深度网络(deep networks)”,它们的计算量主要由像卷积(conv)以及大矩阵乘法(large matrix multiplications)等重型操作主宰。而word2vec则是一个相对浅层的网络(shallow network),每一个training step包含了一个embedding lookup、梯度计算(gradient computation)、以及最终为word pair进行权重更新(weight updates)。梯度计算和更新涉及很小的点乘操作,使用cuDNN[7]或cuBLAS[8]并不能受益。
深度学习框架的限制导致我们探索CUDA C++ API。我们从头设计了训练算法,以便最优利用CUDA多线程能力,并且防止对GPU并行化的过度利用,从而不伤害输出的accuracy。
最终,我们开发了BlazingText,它处理文本语料的速率能达到数百万 words/sec,我们演示了使用多GPU来执行数据并行训练的可能性。我们对比了开源的工具与BlazingText之间的benchmark。
2.word2vec模型
word2vec有两种不同的模型架构:Contextual Bag-Of-Words (CBOW)以及Skip-Gram with Negative Sampling (SGNS) 。CBOW的目标函数是由给定上下文去预测一个词,而Skipgram则给定一个词去预测它的上下文。实际上,Skipgram会给出更好的效果,我们会在下面描述它。
给定一个大型训练语料,它由一个words序列\(w_1, w_2, ..., w_T\)组成。skipgram模型的目标是最大化log似然:
\[\sum_{t=1}^T \sum_{c \in C_t} log p(w_c | w_t)\]其中,T是词汇表size,上下文\(C_t\)是围绕\(w_t\)的词的集合。给定\(w_t\)所观察到的一个上下文词\(w_c\)的概率可以使用上述的词向量进行参数化。假设我们给定一个得分函数s,它将(word, context)的pairs映射到得分\(s \in R\)。定义一个上下文词的概率的一个可能的选择是:
\[p(w_c|w_t) = \frac{exp(s(w_t,w_c))}{\sum_{j=1}^W exp(s(w_t,j))}\]然而,这样的模型不适合我们的case中,因为它意味着,给定一个词\(w_t\),我们只能预测一个上下文词\(w_c\)。
预测上下文词(context words)的问题可以通过构建独立的二分类任务集合来替代。接着,该目标是独立地预测上下文词是否出现。对于在位置t处的词,我们会考虑所有的上下文词作为正例,并从字典中随机抽样负样本。对于一个选中的上下文位置c,使用binary logistic loss,我们可以获取以下的negative log-likelihood:
\[log(1 + e^{-s(w_t,w_c)}) + \sum_{n \in N_{t,c}} log(1 + e^{s(w_t,n)})\]其中\(N_{t,c}\)是从词汇表中抽取的负样本的一个集合。通过表示logistic loss function l:\(x \rightarrow log(1+e^{-x})\),我们可以重写目标函数:
\[\sum_{t=1}^T \sum_{c \in C_t} [l(s(w_t,w_c)) + \sum_{n \in N_{t,c}} l(-s(w_t,n))]\]对于在词\(w_t\)和它的一个上下文词\(w_c\)之间的scoring function s的一个天然参数化方案是,使用词向量(word vectors)。假设在词汇表中的每个词w,定义两个向量\(u_w in R^D\)和\(v_w \in R^D\)。这两个向量有时被称为是输入向量(input vector)和输出向量(output vector)。特别的,我们的向量\(u_{w_t}\)和\(u_{w_c}\)分别对应于词\(w_t\)和\(w_c\)。接着,score可以使用在该词与上下文向量间的点乘(dot product)来表示:\(s(w_t,w_c) = u_{w_t}^T v_{w_c}\)。
3.相关工作
一些已经存在的word2vec系统被限制在只能在单机CPU上运行,而一些使用多核cpu多节点来加速word2vec的方式则进行分布式数据并行训练。这些方法包含了Spark MLLib和Deeplearning4j。这些系统在每轮iteration后依赖reduce操作在所有executors间同步模型。将所有的word vectors跨节点广播(broadcast)的这种方式限制了可扩展性,因为通常网络带宽只比CPU内存要低一阶。另外,模型的accuracy会大幅下降,因为使用了更多节点来增加吞吐。
Intel的工作[11]展示了通过基于minibatching和shared negative samples的scheme可在多CPU节点上进行极强地扩展。该方法将level-1 BLAS操作转换成level-3 BLAS矩阵乘法操作,从而有效地利用现代架构的向量乘法/加法指令(vectorized multiply-add instructions)。然而,该方法仍不能利用GPUs,而且他们的实现只能在Intel BDW和KNL处理器上扩展良好,而这些处理器比GPU要昂贵,不会被主流的云服务平台所提供。借鉴他们提出的思想,我们可以通过一个minibatch共享negative samples,并使用高度优化的cuBLAS level-3矩阵乘法核(matrix multiplication kernels),但由于要进行乘法操作的矩阵size很小,CUDA核启动(kernel-launches)的开销会剧烈降低性能和可扩展性。
其它一些工作[12,13]已经利用像tensorflow, keras, theano等深度学习库,但展示出的性能要比fasttext的CPU实现要慢。由于word2vec的一轮迭代计算并不非常密集,需要使用一个很大的batch size来完全利用GPU。然而,对训练数据进行mini-batching会急剧降低收敛率,而如果batch size=1, 训练又会非常慢。
4. 使用CUDA进行GPU并行化
由于GPU架构比CPU cores提供了更强的(多好多阶)并行机制,word2vec看起来能很好地使用GPU进行加速,算法本身展示了可以通过异步SGD(asynchronous SGD)或Hogwild进行很好的并行化。然而,如果使用更多的并行化,不同线程之间在读取和更新词向量时可能会发生冲突,从而对accuracy产生大幅下降。因而,必须仔细考虑,如何在并行化级别上和同步机制间做好权衡。
深度学习框架没有像CUDA C++ API那样,提供在GPU的可扩展性与并行化之间的细粒度控制。有必要对算法设计进行大幅重构,从而允许最大化并行吞吐,而强制同步会阻止accuracy的降低。我们控制了以下两种方法来基于CUDA实现。
4.1 每个词一个线程块(one thread block per word)
原始的word2vec实现按顺序处理一个句子,例如:对于中心词\(w_t\),它会考虑围绕中心词作为目标词的window size(ws)中的所有词,这意味着在\([w_{t-ws}, w_{t+ws}]\)所有的词向量,会在一个step中获得更新。相似的在下一step中,对于中心词\(w_t + 1\),在范围\([w_{t-ws+1}, w_{t+ws+1}]\)内的所有向量都将被更新。这意味着,当处理一个句子时,一个词向量可以被修改2ws+1次,理想的,每个连续的step都应使用被前一step修改更新后的向量(updated vectors)。
从头设计一个CUDA程序需要我们对网格结构(grid)和线程块(thread blocks)做总体规划。在相同线程块中的线程可以相互进行同步,但如果属于不同线程块的线程不能相互通信,使得线程块相互独立。在该方法中,我们选择为每个词分配一个线程块,在一个块内的线程数可以是乘以32, 相当有效。随着在一个块内的线程数与向量维度(通常100)越来越接近,每个线程会映射到一个向量维度上,并做element-wise乘法操作。这种单独的乘法接着使用一个reduce kernel来计算任意2个给定向量间的点乘来进行有效求和。我们探索了一些并行reduction技术,最终使用采用一个高度优化过的completely unrolled reduce kernel。该算法设计采用并行机制能达到峰值,因为每个词会通过一个线程块进行独立处理,在线程块中的线程只有当执行reduce操作时会进行同步(synchronize)。然而,该方法会有一个主要缺点,它能极大地破坏embeddings的质量。不同的线程块可以独立的修改词向量,没有同步机制,它对于accuracy是有害的,因为随着窗口沿着句子进行滑动,每个向量可以更新2w+1次。这会产生大量线程覆盖写(overwrites)和非最新读取(stale reads)。
4.2 每个句子一个线程块
在之前章节讨论过,没有任何同步机制的词向量更新,可以充分利用CUDA并行机制,但是会由于竞争条件(race conditions),会降低embeddings的accurary。随着窗口沿着句子滑动,当处理后一个词时,应使用前面已经更新(updated)的词向量。因而,为了解决顺序依赖(sequential dependency),与前面的方法类似,该方法会将每个句子映射到一个CUDA线程块上,它会将该向量的每一维映射到一个线程上。因此,不同线程块相互并行处理句子,而在一个句子中,线程块会根据词进行循环来顺序更新向量。该方法仍会导致一些竞争条件(race conditions),但由于不同句子通常不会有许多词相同,它实际上不会造成收敛问题。
由于文本语料对于驻在GPU内存中来说可能很大,数据从磁盘到GPU中会流式化(streamed),并且许多句子会进行batch化,以分摊数据在CPU和GPU间传输的开销。为了评估accuracy和throughput间进行平衡,线程块、或者句子被并行处理的最优化数目,通过经验选择。并发处理越多勉励子,会增加throughput,但会产生accuracy的降低,因为不同线程块更新相同的词向量的机率会增加。
一些其它的最优化(optimizations),可以使该方法更有效。如果kernel的执行时间比数据传输时间要少,那么GPU会空闲等待下一batch的句子。为了避免这种情况,我们尝试通过使用多CPU线程和CUDA streams,将数据传输和在GPU上进行kernel execution的过程进行重叠(overlap),它允许数据传输到GPU时仍在忙着运行kernels,这样GPU时间不会空闲。我们使用多CPU线程来从磁盘读取数据,并准备下一batch的句子,它可以使用多个CUDA streams来并发传输数据给GPU。
我们将在第5节描述上述方法的实验。
4.3 在多GPU上的分布式训练
在多GPU分布式系统上扩展BlazingText是很关键的,因为在单GPU上训练一些工业界特别大的数据集时(数T),它仍可能花费数天时间。为了扩展BlazingText,我们探索了不同的分布式训练范式——模型并行化(model parallelism) 和 数据并行化(data parallelism)。由于向量维度通常很小,点乘的规模也不会很大,因而将向量的不同维量进行分布式,不会带来很多的性能增益。因而,我们使用数据并行化,当使用N个GPU时,我们将数据集等分为N份相等的shards。对于词汇表中的所有词,输入向量和输出向量的模型参数,会被复制到每个GPU上;每个设备接着独立处理它所拥有的数据分区,并更新它的局部模型(local model),然后与其它N-1个GPU周期性同步局部模型(local model)。
数据并行化要解决的主要问题是,如何在GPU间有效进行模型同步。它可以使用NVIDIA的NCCL库[15]来有效解决,该库提供了AllReduce方法,它可以基于GPU网络拓朴以一种最优的方法,来处理在GPU间的peer-to-peer数据传输。如果GPU没有通过相同的PCIe swith或者相同的IOH chip进行连接,那么数据会通过host CPU进行传输。由于模型参数的size可能是数百MB,同步机制可能开销很大,因而决定合理的同步间隔十分重要。频繁的同步将产生更好的收敛,但会减慢训练,反之亦然。出于简洁性,我们选择在每轮迭代后进行同步,并在后续会继续探索更有效的同步机制。
5.实验
我们使用上述提到的方法,为单GPU和多GPU系统进行最优化BlazingText。在本节中,我们会展示throughput(单位:百万 words/sec)和所学到的embeddings的accuracy(在标准word similarity和word analogy test上)。我们会对BlazingText和FastText CPU(没有subword embeddings的版本)实现进行benchmark。
硬件:所有的实验都在AWS p2.8xlarge GPU实例上运行,它具有8个NVIDIA K80 GPU卡,以及Intel Xeon CPU E5-2684 v4@2.3GHz 16核(32线程)。
软件:BlazingText使用C++编写,使用CUDA compiler:NVCC v8.0编译。
训练语料:我们使用两个不同语料进行训练:(1) 来自Wikipedia的包含1700w个词的Text8数据集[16],(2) 一个十亿词的benchmark dataset[17]。
测试集:学到的embedding会在word similarity和word analogy任务上进行评估。对于word similarity,我们使用WS-353[18],它是最流行的测试数据集。它包含了人工审核过的相似word pairs。词表示的评估通过根据cosine相似度对这些pairs进行排序,并使用Spearman’s rank相关系数进行评估。我们使用google analogy dataset来进行word analogy评估。
超参数:对于所有的实验,我们展示了使用CBOW和Skipgram算法(negative sampling)和FastText的缺省参数设置(dim=100,window size=5, sampling threold=1e-4, inital learning rate=0.05)。我们为Text8数据集使用20个epochs,One Billion Words Benchmark则使用10个epochs。
5.1 Throughput
图1
图1和图2展示了BlazingText on GPU和FastText on CPU的throughput以百万 words/sec测量。分别跨多GPU和多CPU运行,分别跑SKipgram和CBOW。当扩展到多GPU时,我们的实现达到了接近线性的加速。使用8个GPU,Skipgram可以达到1.32 亿 words/sec,而CBOW可以达到4.25 亿 words/sec,它比32线程的FastText要快3倍。如表1所示,跨多GPU扩展在accuracy上影响很小,因为我们的实现可以有效利用多GPU架构。随着在throughput和accuracy间进行平衡,我们进一步通过降低同步频率来增加throughput,只要accuracy的下降是可接受的。
图2
5.2 Accuracy
表1
我们评估了从fasttext实现以及我们的实现(随GPU数目不同)中训练得到的该模型,并在表1中展示了他们在word similarity和word analogy任务上的预测效果。为了确保我们的实现可以很好泛化,我们会使用2个不同的语料来训练模型——text8和1B words benchmark。
由于GPU并行化,为了消除随机性,我们运行每个实验多次(n=10),并展示了平均结果。如表1所示,BlazingText展示了在多GPU上的效果与FastText CPU上的效果相近。当使用4GPU时,性能几乎相同,在一些情况下比CPU版本要好。如你所料,预测的效果会随着使用更多GPU而减少,但在可接受范围内。对于相似度评估,使用8 GPUs会达到2%更差的accurary,但会比32 CPU线程超过3倍加速。
对于analogy评估,在多GPU和CPU上的不同更显著。在我们的实验中,我们主要关注可扩展性,因而当扩展到更多GPU时,我们不会增加同步频率。增量同步频率可以维持一个可接受的accuracy,但会在扩展性上可降,导致一个sub-linear scaling。然而,取决于终端应用,可以调整同步频率。