張禹堯 毛騰 李俊 蔣玉茹 北京信息科技大學(xué)計(jì)算機(jī)學(xué)院

面向向量相似度計(jì)算的集群系統(tǒng)的研究

張禹堯 毛騰 李俊 蔣玉茹 北京信息科技大學(xué)計(jì)算機(jī)學(xué)院

在大數(shù)據(jù)時(shí)代，基于文本向量空間的分類、聚類、排序與相關(guān)性反饋都需要計(jì)算向量相似度。本文提供一種針對大規(guī)模向量相似度計(jì)算的方法。在該方法中，嘗試?yán)肑etson TK1開發(fā)板構(gòu)建了一個(gè)基于ARM的Hadoop完全分布式集群，并利用CUDA對單一結(jié)點(diǎn)進(jìn)行提速，最終求得與目標(biāo)詞向量最相似的TopN。本文通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性。

向量相似度 ARM集群 Hadoop CUDA

向量相似度，顧名思義是兩個(gè)用向量表示的對象之間的相似程度，常用的向量相似度計(jì)算方案有內(nèi)積、Dice系數(shù)、Jaccard系數(shù)和余弦系數(shù)。

隨著計(jì)算機(jī)軟件和硬件的發(fā)展，數(shù)據(jù)處理的量越來越大，數(shù)據(jù)的結(jié)構(gòu)越來越復(fù)雜，越來越多的計(jì)算模型采用向量模型將非結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)換成計(jì)算機(jī)能夠處理的數(shù)據(jù)。由此，我們將能夠計(jì)算個(gè)體間的差異，進(jìn)而評價(jià)個(gè)體的相似度和分類。在實(shí)際運(yùn)用中，我們可以將一個(gè)人的數(shù)據(jù)表示為具有身高、年齡、ID號等的向量。在處理文本內(nèi)容時(shí)，我們也可將其轉(zhuǎn)化為向量空間中的向量運(yùn)算，并且用空間上的相似度表達(dá)語義的相似度。

本篇論文提出了一種對大規(guī)模向量相似度計(jì)算的方法，即利用基于ARM集群系統(tǒng)的GPU和Map/Reduce方法處理大規(guī)模向量相似度，并以計(jì)算詞向量的相似度為例詳細(xì)說明該方法的工作過程。

1 研究背景與潛在應(yīng)用

在大數(shù)據(jù)時(shí)代，用向量模型表示的數(shù)據(jù)不僅數(shù)據(jù)量大，而且向量維度也在增加，相似度的計(jì)算變成了需要龐大的計(jì)算量的問題。高處理速度已經(jīng)成為不可或缺的要求，而大數(shù)據(jù)處理平臺（例如：Hadoop）的出現(xiàn)能夠幫助解決這個(gè)問題。研究如何提高大規(guī)模處理數(shù)據(jù)的效率是非常有價(jià)值的。

2 研究內(nèi)容

2.1 詞向量

詞向量是將語言中的詞進(jìn)行數(shù)學(xué)化的一種方式，也就是將詞轉(zhuǎn)為計(jì)算機(jī)能夠理解的語言，是語義理解的基礎(chǔ)。

本篇論文中采用的詞向量方式是：深度學(xué)習(xí)中用到的分布式表示方法，其基本思想是：

通過訓(xùn)練將某種語言中的每個(gè)詞映射成一個(gè)固定長度的向量，將所有這些向量放在一起形成一個(gè)詞向量空間，而每一詞向量則為該空間中的一個(gè)點(diǎn)，在這個(gè)空間上引入“距離”，則可以根據(jù)詞之間的距離來判斷它們之間的（詞法、語義上的）相似性。

本篇論文中采用夾角余弦法來衡量向量的距離。兩個(gè)詞相關(guān)或者相似，在詞向量距離上會更接近。詞匯相似度識別便是建立在詞向量基礎(chǔ)之上的數(shù)據(jù)計(jì)算。用此法表示向量，如：“金魚”和“鯉魚”的距離會遠(yuǎn)遠(yuǎn)小于“金魚”和“草地”。

詞義相似度計(jì)算在各領(lǐng)域中都有廣泛的應(yīng)用，例如信息檢索、信息抽取、文本分類、詞義排歧、機(jī)器翻譯等等。由于詞的數(shù)目眾多；存儲詞向量的文件較大；另一方面詞向量相似度的計(jì)算可以拆分成多個(gè)并行的任務(wù)；目標(biāo)詞向量與其他詞向量相似度的計(jì)算是大規(guī)模重復(fù)性計(jì)算（計(jì)算方法一致），因而可以采用Hadoop完全分布式集群和CUDA方法來處理詞匯相似度計(jì)算問題。

2.2 Hadoop

Hadoop是提供以分布式方式存儲和處理大數(shù)據(jù)的標(biāo)準(zhǔn)平臺之一，是Apache的一個(gè)用Java語言實(shí)現(xiàn)的開源軟件框架。Hadoop基于兩個(gè)核心概念：Hadoop分布式文件系統(tǒng)（HDFS）和分布式處理框架Map/Reduce。HDFS以分布式方式處理文件的存儲，Map/Reduce是分布式運(yùn)行在Hadoop集群上的程序。目前，Hadoop已經(jīng)被Yahoo，F(xiàn)acebook和其他大公司使用。

HDFS在兩種類型節(jié)點(diǎn)的幫助下工作，Namenode和Datanode。Namenode是集群中存儲集群上所有文件的詳細(xì)信息的節(jié)點(diǎn)，包括整個(gè)文件系統(tǒng)的名字空間和文件數(shù)據(jù)塊映射(Blockmap)的映像信息和對文件系統(tǒng)元數(shù)據(jù)產(chǎn)生修改的操作信息。Hadoop客戶端通過與此節(jié)點(diǎn)進(jìn)行會話，從數(shù)據(jù)節(jié)點(diǎn)讀取和寫入。Datanode實(shí)際上存儲文件的一部分，它將HDFS數(shù)據(jù)以文件的形式存儲在本地的文件系統(tǒng)中。

通常，Map/Reduce框架和HDFS是運(yùn)行在一組相同的節(jié)點(diǎn)上的，即計(jì)算節(jié)點(diǎn)和存儲節(jié)點(diǎn)通常在一起。這種配置允許框架在那些已經(jīng)存好數(shù)據(jù)的節(jié)點(diǎn)上高效地調(diào)度任務(wù)，這可以使整個(gè)集群的網(wǎng)絡(luò)帶寬被高效地利用。

Map/Reduce就是“任務(wù)的分解與結(jié)果的匯總”。在運(yùn)行一個(gè)Map/Reduce計(jì)算任務(wù)時(shí)候，任務(wù)過程被分為兩個(gè)階段：Map階段和Reduce階段，每個(gè)階段都是用鍵值對＜key,value＞作為輸入（input）和輸出（output）。而要做的就是定義好這兩個(gè)階段的函數(shù)：Map函數(shù)和Reduce函數(shù)。

Map函數(shù)：接受一個(gè)鍵值對（key-value pair），產(chǎn)生一組中間鍵值對。Map/Reduce框架會將map函數(shù)產(chǎn)生的中間鍵值對里鍵相同的值傳遞給一個(gè)Reduce函數(shù)。

Reduce函數(shù)：接受一個(gè)鍵，以及相關(guān)的一組值，將這組值進(jìn)行合并產(chǎn)生一組規(guī)模更小的值（通常只有一個(gè)或零個(gè)值）。

圖1 Map/Reduce處理大數(shù)據(jù)集的過程Fig.1 The process of processing large data sets using Map/Reduce

用Map/Reduce來處理的數(shù)據(jù)集必須具備這樣的特點(diǎn)：待處理的數(shù)據(jù)集可以分解成許多小的數(shù)據(jù)集，而且每一個(gè)小數(shù)據(jù)集都可以完全并行地進(jìn)行處理。而向量相似度的計(jì)算符合這一特點(diǎn)，因此本篇論文利用Map/Reduce分布式處理的優(yōu)點(diǎn)完成相關(guān)工作。

2.3 GPU

隨著顯卡的發(fā)展，GPU越來越強(qiáng)大，在計(jì)算上已經(jīng)超越了通用的CPU。而NVIDIA推出CUDA，讓顯卡可以用于圖像計(jì)算以外的目的。

CUDA（Computer Unified Device Architecture）: 計(jì) 算機(jī)統(tǒng)一設(shè)備架構(gòu)，是NVIDIA在2007年推向市場的并行計(jì)算架構(gòu)。該架構(gòu)使GPU能解決復(fù)雜的計(jì)算問題，它包含了CUDA指令集架構(gòu)(ISA)以及GPU內(nèi)部的并行計(jì)算。通過CUDA，GPU可以很方便地被用來進(jìn)行通用計(jì)算（類似在CPU中進(jìn)行的數(shù)值計(jì)算等等）。開發(fā)人員可以通過調(diào)用CUDA的API，來進(jìn)行并行編程，達(dá)到高性能計(jì)算目的。

在CUDA的架構(gòu)下，程序分為兩個(gè)部分：Host端和Device端。Host端是指在CPU上執(zhí)行的部份；而Device端則是在GPU端執(zhí)行的部分，又稱為Kernel函數(shù)，也就是內(nèi)核函數(shù)。Kernel函數(shù)描述單個(gè)線程的工作，并且通常在數(shù)千個(gè)線程上調(diào)用。在開發(fā)人員定義的線程塊中，這些線程可以共享數(shù)據(jù)并通過內(nèi)置原語來同步它們的動作。

CUDA運(yùn)行時(shí)還提供用于設(shè)備內(nèi)存管理和主機(jī)與計(jì)算設(shè)備之間數(shù)據(jù)傳輸?shù)膸旌瘮?shù)。通常Host端程序會將數(shù)據(jù)準(zhǔn)備好后，先將數(shù)據(jù)通過命令復(fù)制到GPU端已經(jīng)開辟好內(nèi)存的數(shù)組或者變量中，再由GPU端并行執(zhí)行核函數(shù)程序，完成以后再由Host端將計(jì)算結(jié)果從GPU端中取回來。

總之，在CUDA工作過程中，CPU擔(dān)任的工作為控制GPU執(zhí)行，調(diào)度分配任務(wù)，并能做一些簡單的計(jì)算，而大量需要并行計(jì)算的工作都交給GPU實(shí)現(xiàn)。本篇論文中利用CUDA可以大量并行運(yùn)算的優(yōu)點(diǎn)計(jì)算目標(biāo)詞向量和其他向量間余弦值。

2.4 實(shí)驗(yàn)?zāi)康?/h3>

ARM堅(jiān)持以較小的面積實(shí)現(xiàn)更高的性能，同時(shí)堅(jiān)持高能效的策略。ARMG71可以提供最多32核心的GPU設(shè)計(jì)能為VR頭盔提供極致性能表現(xiàn)。

3 方法實(shí)現(xiàn)

3.1 實(shí)驗(yàn)硬件環(huán)境

本系統(tǒng)使用了四臺NVIDIA JETSON TK1開發(fā)板搭建ARM集群。Jetson TK1使用了NVIDIA最新發(fā)布的Tegra K1處理器，可以進(jìn)行每秒326千兆的浮點(diǎn)運(yùn)算。本系統(tǒng)利用其強(qiáng)大的運(yùn)算能力，能夠加快數(shù)據(jù)處理速度。

圖2 集群配置網(wǎng)絡(luò)拓?fù)銯ig.2 The cluster configuration network

3.2 實(shí)驗(yàn)軟件環(huán)境

在每個(gè)Jetson TK1開發(fā)板上安裝ubuntu14.04系統(tǒng)和cuda6.5環(huán)境，同時(shí)利用hadoop2.5.2搭建了完全分布式集群環(huán)境。

圖3 系統(tǒng)框架圖Fig.3 The Flow of System Framework

3.3 系統(tǒng)框架

步驟一：編寫TopNJni.java，并將其編譯為class文件。在TopNJni類中，主要是聲明Jni和Native方法（即：MyMethod函 數(shù)）：public native static String MyMethod(String goal,String data)；MyMethod函數(shù)是在TopNC.cpp中用C語言實(shí)現(xiàn)的；

步驟二：用Javah一jni命令生成頭文件TopNJni.h。在TopNC.cpp中需要調(diào)用TopNJni.h；

步驟三：編寫MODEL.java，并將其編譯為class文件。在MODEL類中分別實(shí)現(xiàn)了兩個(gè)Map和Reduce函數(shù)；在第一個(gè)Map和Reduce中，查詢目標(biāo)詞向量，并將結(jié)果放到Context中；在第二個(gè)Map函數(shù)中要調(diào)用TopNJni類中的Native方法（即：MyMethod方法），將當(dāng)前節(jié)點(diǎn)獲得的文件切片的起始位置和長度傳給MyMethod方法，最后求得與目標(biāo)詞向量最相似的TopN；

步驟四：編寫TopNC.cpp，用g++編譯成TopNC.o。在TopNC.cpp中要聲明調(diào)用Jni.h和TopNJni.h頭文件，聲明extern "C" float c_vectorcos(float h_A[Wordcount], float h_B[Wordcount])方法，該方法在vectorAdd.cu中實(shí)現(xiàn)；實(shí)現(xiàn)Native方法（即：MyMethod方法），在MyMethod方法對從Hadoop2CUDA.Java中傳過來的文件切片進(jìn)行處理，用二維數(shù)組記錄多個(gè)多維詞向量，同時(shí)調(diào)用上述c_vectorcos方法，傳遞處理好的二維數(shù)組，利用GPU計(jì)算詞向量相似度；

步驟五：編寫Vector.cu，用nvcc編譯成Vector.o。在Vector.cu中，編寫kernel函數(shù)：

__global__ void vectorMu（）； 實(shí) 現(xiàn) extern "C" float c_vectorcos(float h_A[Wordcount], float h_B[Wordcount])方法，在該方法中調(diào)用上述kernel函數(shù)，計(jì)算詞向量間的相似度；

步驟六：利用g++將Vector.o和TopNC.o編譯為一個(gè)動態(tài)鏈接庫文件libTopN.so；

步驟七：將 MODEL.java、MODEL.class、TopNJni.java、TopNJni.class打成 jar包：WordCount.jar；

步驟八：將WordCount.jar和libWordCount.so放到Hadoop端運(yùn)行，得到運(yùn)算結(jié)果

3.4 程序分析

（1）Hadoop分配任務(wù)及匯總處理結(jié)果

本系統(tǒng)使用Hadoop基本框架，利用HDFS對原始文件進(jìn)行切片，利用MapReduce實(shí)現(xiàn)分布式計(jì)算。

Hadoop為每一個(gè)切片創(chuàng)建一個(gè)任務(wù)調(diào)用Map計(jì)算，在Map中能夠獲得切片的詳細(xì)信息（切片在原始文件中的起始位置、切片的長度等），Map會將這些信息傳遞給C文件，注意此信息并不是切片的具體記錄，通過這樣的方法能夠減少數(shù)據(jù)傳輸量。

此系統(tǒng)會有兩個(gè)Map/Reduce函數(shù)，第一個(gè)Map/Reduce用于目標(biāo)詞向量的獲得，第二個(gè)Map/Reduce用于目標(biāo)詞向量與其他詞向量的相似度計(jì)算。

圖4 Map/Reduce過程Fig.4 Map/Reduce Experiment

（2）目標(biāo)詞向量的獲?。∕ap/Reduce Ⅰ）

本系統(tǒng)中，用戶自主輸入目標(biāo)單詞，系統(tǒng)在進(jìn)行詞向量的相似度計(jì)算前需要全局查找目標(biāo)單詞的向量表示。此工作是由Map/Reduce函數(shù)完成，其中Hadoop系統(tǒng)負(fù)責(zé)任務(wù)分配，即將目標(biāo)文件切片。在每個(gè)Map中對當(dāng)前獲得的文件切片內(nèi)容進(jìn)行匹配，Reduce獲得最終結(jié)果，并將結(jié)果寫入Context。通過這種方式，將全局查找任務(wù)分成N個(gè)結(jié)點(diǎn)上分布式運(yùn)行的小任務(wù)，提高查找速度。

（3）目標(biāo)詞向量相似度計(jì)算（Map/Reduce Ⅱ）

本系統(tǒng)需要計(jì)算目標(biāo)詞向量與所有其它詞向量的相似度。此任務(wù)可以將所有詞向量數(shù)據(jù)分解成N個(gè)數(shù)據(jù)集，在不同的結(jié)點(diǎn)上計(jì)算目標(biāo)詞向量和當(dāng)前數(shù)據(jù)子集中詞向量的相似度。

（4）CUDA計(jì)算詞向量間相似度

CUDA的優(yōu)點(diǎn)在于處理大量并行化的問題，而在本系統(tǒng)中需要計(jì)算的部分在于計(jì)算兩個(gè)詞的相似度，本系統(tǒng)采用夾角余弦法計(jì)算向量間的相似度，如公式1。

本系統(tǒng)中待處理的詞向量有200個(gè)維度，為核函數(shù)分配N個(gè)區(qū)塊（block）（N為當(dāng)前節(jié)點(diǎn)需要計(jì)算的詞向量個(gè)數(shù)），200個(gè)線程（200為詞向量的維度）。在核函數(shù)中利用線程計(jì)算等待所有線程同步后，每個(gè)區(qū)塊再利用for循環(huán)對做求和，然后求出夾角余弦值并獲得最終結(jié)果。

另外，在利用CUDA做計(jì)算中，一般而言，Host端和Device端間數(shù)據(jù)的復(fù)制會消耗系統(tǒng)時(shí)間，影響計(jì)算速度。而本文采用的Jetson TK1開發(fā)板的優(yōu)點(diǎn)在于Device端可以直接使用Host端的數(shù)據(jù)，無需進(jìn)行Host端和Device端的數(shù)據(jù)傳遞。因此，在本文系統(tǒng)中，在數(shù)據(jù)節(jié)點(diǎn)利用GPU計(jì)算一個(gè)端中詞向量的相似度，必然會提高系統(tǒng)的整體性能。

（5）TopN的計(jì)算

在大規(guī)模的詞向量相似度計(jì)算中，全局有序是極其復(fù)雜的，并且會耗費(fèi)集群中大量的資源。

本系統(tǒng)的Top N模式中不會對整個(gè)詞向量數(shù)據(jù)集進(jìn)行排序，而是每次找出同一個(gè)map實(shí)例中最高價(jià)值的詞向量數(shù)據(jù)集進(jìn)行記錄，另外需要注意的是：每個(gè)Map中的TopN是在c文件中根據(jù)cu文件傳回的計(jì)算結(jié)果去計(jì)算，這樣會減少數(shù)據(jù)的傳輸量。

最后在Reduce階段，合并每個(gè)Map中的TopN得到最終的TopN。在這種模式下，本系統(tǒng)減少了計(jì)算量和數(shù)據(jù)傳輸量，大大提高了效率。

4 實(shí)驗(yàn)結(jié)果

本文實(shí)驗(yàn)中使用的詞向量是經(jīng)過作者利用Word2Vec訓(xùn)練得到的，每個(gè)詞向量有200個(gè)維度。訓(xùn)練中采用的語料主要來自于北京語言大學(xué)語料資源庫，其中包括百科全書、大陸小說、港臺小說、古典文學(xué)、名家小說、人民日報(bào)、外國文學(xué)、武俠小說。另外，本文構(gòu)建了一個(gè)爬取和解析工具，用于獲取百度百科中生物相關(guān)的文本內(nèi)容，得到35，803個(gè)有效網(wǎng)頁，共331，430個(gè)段落，約114.9M字節(jié)。

在實(shí)驗(yàn)中，若輸入數(shù)據(jù)為：鱔魚，實(shí)驗(yàn)結(jié)果如表1所示：

表1 “鱔魚”的Top 10Table 1 Top 10 of “Eel”

5 結(jié)束語

本文利用Hadoop集群的分布式特點(diǎn)和Jetson TK1開發(fā)板的GPU特點(diǎn)，構(gòu)建了一個(gè)面向向量相似度計(jì)算和提取最相似TOPN個(gè)詞向量的系統(tǒng)。該系統(tǒng)的特點(diǎn)是：

①系統(tǒng)可以根據(jù)計(jì)算任務(wù)的規(guī)模彈性擴(kuò)充，當(dāng)計(jì)算資源不足的時(shí)候，可以隨時(shí)向集群中增進(jìn)計(jì)算節(jié)點(diǎn)，擴(kuò)充系統(tǒng)的計(jì)算能力。

②利用Hadoop集群的特點(diǎn)完成文件的分發(fā)和與GPU的整合。

③利用GPU對批量的向量相似度計(jì)算任務(wù)進(jìn)行加速。

④利用Jetson TK1的特點(diǎn)，避免了Host端和Device端之間數(shù)據(jù)傳遞的時(shí)延。

⑤利用MapReduce計(jì)算模式，加速了在大規(guī)模詞向量中進(jìn)行詞向量檢索和TOPN計(jì)算的過程。

[1]William B．Frakes，Ricardo Baeza—yates．Information retrieval：data structures and algorithms．Prentice—HallInc．USA．PP 420—441．

[2]Yang B, Kim H J, Shim J, et al. Fast and scalable vector similarity joins with MapReduce[J]. Journal of Intelligent Information Systems, 2016, 46(3):473-497.

[3]Salton G, Wong A, Yang C S. A vector space model for automatic indexing[J]. Communications of the Acm, 1975,18(11):273-280.

[4]Sharma T, Shokeen V, Mathur S. Multiple K Means++Clustering of Satellite Image Using Hadoop MapReduce and Spark[J]. 2016.

[5]Faruqui M, Dyer C. Non-distributional Word Vector Representations[J]. Computer Science, 2015.

[6] White T. Hadoop: The Definitive Guide[J]. O’reilly Media Inc Gravenstein Highway North, 2010, 215(11):1 - 4.

[7]http://www.cnblogs.com/davidwang456/p/5015018.html.2015-12-03

[8]J Dean,S chemawat.mapreduce:a flexible data processing tool[J].Communications of Acm,2010,53(1):72-77

[9]h t t p://b l o g.c s d n.n e t/o p e n n a i ve/a r t i c l e/details/7514146.2014-10-29

[10]Li Jian-Jiang,Cui Jian,Wang Ran.A review of parallel mapreduce research models. Journal of Electroni cs.2011,39(11):2635-2642

[11]https://my.oschina.net/nyp/blog/534003.2015-11-12

[12]http://product.pconline.com.cn/itbk/diy/graphics/1109/2521869.html.

[13]Ryoo S, Rodrigues C I, Baghsorkhi S S, et al.Optimization principles and application performance evaluation of a multithreaded GPU using CUDA[C]// ACM Sigplan Symposium on Principles and Practice of Parallel Programming,PPOPP 2008, Salt Lake City, Ut, Usa, February. 2008:73-82.

[14]李建江,崔健,王聃.mapreduce并行研究模型綜述.電子學(xué)報(bào).2011,39(11):2635-2642

國家自然科學(xué)基金項(xiàng)目（61602044）；北京市教委科研計(jì)劃面上項(xiàng)目（KM201411231014）；北京信息科技大學(xué)2016年人才培養(yǎng)質(zhì)量提高經(jīng)費(fèi)（5111610800）；北京信息科技大學(xué)2017年人才培養(yǎng)質(zhì)量提高經(jīng)費(fèi)（5111723400）

張禹堯，男，1996—，本科在讀，研究方向?yàn)樽匀徽Z言處理；毛騰，女，1995—，研究生在讀，研究方向?yàn)樽匀徽Z言處理；李俊，男，1994—，研究生在讀，研究方向?yàn)樽匀徽Z言處理；蔣玉茹，女，1978—，博士，講師，研究方向?yàn)槿斯ぶ悄?、自然語言處理。