面向向量相似度計算的集群系統的研究

張禹堯 毛騰 李俊 蔣玉茹 北京信息科技大學計算機學院

面向向量相似度計算的集群系統的研究

張禹堯 毛騰 李俊 蔣玉茹 北京信息科技大學計算機學院

在大數據時代，基于文本向量空間的分類、聚類、排序與相關性反饋都需要計算向量相似度。本文提供一種針對大規模向量相似度計算的方法。在該方法中，嘗試利用Jetson TK1開發板構建了一個基于ARM的Hadoop完全分布式集群，并利用CUDA對單一結點進行提速，最終求得與目標詞向量最相似的TopN。本文通過實驗驗證了該方法的有效性。

向量相似度 ARM集群 Hadoop CUDA

向量相似度，顧名思義是兩個用向量表示的對象之間的相似程度，常用的向量相似度計算方案有內積、Dice系數、Jaccard系數和余弦系數。

隨著計算機軟件和硬件的發展，數據處理的量越來越大，數據的結構越來越復雜，越來越多的計算模型采用向量模型將非結構化數據轉換成計算機能夠處理的數據。由此，我們將能夠計算個體間的差異，進而評價個體的相似度和分類。在實際運用中，我們可以將一個人的數據表示為具有身高、年齡、ID號等的向量。在處理文本內容時，我們也可將其轉化為向量空間中的向量運算，并且用空間上的相似度表達語義的相似度。

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

1 研究背景與潛在應用

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

2 研究內容

2.1 詞向量

詞向量是將語言中的詞進行數學化的一種方式，也就是將詞轉為計算機能夠理解的語言，是語義理解的基礎。

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

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

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

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

2.2 Hadoop

Hadoop是提供以分布式方式存儲和處理大數據的標準平臺之一，是Apache的一個用Java語言實現的開源軟件框架。Hadoop基于兩個核心概念：Hadoop分布式文件系統（HDFS）和分布式處理框架Map/Reduce。HDFS以分布式方式處理文件的存儲，Map/Reduce是分布式運行在Hadoop集群上的程序。目前，Hadoop已經被Yahoo，Facebook和其他大公司使用。

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

通常，Map/Reduce框架和HDFS是運行在一組相同的節點上的，即計算節點和存儲節點通常在一起。這種配置允許框架在那些已經存好數據的節點上高效地調度任務，這可以使整個集群的網絡帶寬被高效地利用。

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

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

Reduce函數：接受一個鍵，以及相關的一組值，將這組值進行合并產生一組規模更小的值（通常只有一個或零個值）。

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

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

2.3 GPU

隨著顯卡的發展，GPU越來越強大，在計算上已經超越了通用的CPU。而NVIDIA推出CUDA，讓顯卡可以用于圖像計算以外的目的。

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

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

CUDA運行時還提供用于設備內存管理和主機與計算設備之間數據傳輸的庫函數。通常Host端程序會將數據準備好后，先將數據通過命令復制到GPU端已經開辟好內存的數組或者變量中，再由GPU端并行執行核函數程序，完成以后再由Host端將計算結果從GPU端中取回來。

總之，在CUDA工作過程中，CPU擔任的工作為控制GPU執行，調度分配任務，并能做一些簡單的計算，而大量需要并行計算的工作都交給GPU實現。本篇論文中利用CUDA可以大量并行運算的優點計算目標詞向量和其他向量間余弦值。

2.4 實驗目的

ARM堅持以較小的面積實現更高的性能，同時堅持高能效的策略。ARMG71可以提供最多32核心的GPU設計能為VR頭盔提供極致性能表現。

3 方法實現

3.1 實驗硬件環境

本系統使用了四臺NVIDIA JETSON TK1開發板搭建ARM集群。Jetson TK1使用了NVIDIA最新發布的Tegra K1處理器，可以進行每秒326千兆的浮點運算。本系統利用其強大的運算能力，能夠加快數據處理速度。

圖2 集群配置網絡拓撲Fig.2 The cluster configuration network

3.2 實驗軟件環境

在每個Jetson TK1開發板上安裝ubuntu14.04系統和cuda6.5環境，同時利用hadoop2.5.2搭建了完全分布式集群環境。

圖3 系統框架圖Fig.3 The Flow of System Framework

3.3 系統框架

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

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

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

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

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

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

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

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

步驟八：將WordCount.jar和libWordCount.so放到Hadoop端運行，得到運算結果

3.4 程序分析

（1）Hadoop分配任務及匯總處理結果

本系統使用Hadoop基本框架，利用HDFS對原始文件進行切片，利用MapReduce實現分布式計算。

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

此系統會有兩個Map/Reduce函數，第一個Map/Reduce用于目標詞向量的獲得，第二個Map/Reduce用于目標詞向量與其他詞向量的相似度計算。

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

（2）目標詞向量的獲取（Map/Reduce Ⅰ）

本系統中，用戶自主輸入目標單詞，系統在進行詞向量的相似度計算前需要全局查找目標單詞的向量表示。此工作是由Map/Reduce函數完成，其中Hadoop系統負責任務分配，即將目標文件切片。在每個Map中對當前獲得的文件切片內容進行匹配，Reduce獲得最終結果，并將結果寫入Context。通過這種方式，將全局查找任務分成N個結點上分布式運行的小任務，提高查找速度。

（3）目標詞向量相似度計算（Map/Reduce Ⅱ）

本系統需要計算目標詞向量與所有其它詞向量的相似度。此任務可以將所有詞向量數據分解成N個數據集，在不同的結點上計算目標詞向量和當前數據子集中詞向量的相似度。

（4）CUDA計算詞向量間相似度

CUDA的優點在于處理大量并行化的問題，而在本系統中需要計算的部分在于計算兩個詞的相似度，本系統采用夾角余弦法計算向量間的相似度，如公式1。

本系統中待處理的詞向量有200個維度，為核函數分配N個區塊（block）（N為當前節點需要計算的詞向量個數），200個線程（200為詞向量的維度）。在核函數中利用線程計算等待所有線程同步后，每個區塊再利用for循環對做求和，然后求出夾角余弦值并獲得最終結果。

另外，在利用CUDA做計算中，一般而言，Host端和Device端間數據的復制會消耗系統時間，影響計算速度。而本文采用的Jetson TK1開發板的優點在于Device端可以直接使用Host端的數據，無需進行Host端和Device端的數據傳遞。因此，在本文系統中，在數據節點利用GPU計算一個端中詞向量的相似度，必然會提高系統的整體性能。

（5）TopN的計算

在大規模的詞向量相似度計算中，全局有序是極其復雜的，并且會耗費集群中大量的資源。

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

最后在Reduce階段，合并每個Map中的TopN得到最終的TopN。在這種模式下，本系統減少了計算量和數據傳輸量，大大提高了效率。

4 實驗結果

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

在實驗中，若輸入數據為：鱔魚，實驗結果如表1所示：

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

5 結束語

本文利用Hadoop集群的分布式特點和Jetson TK1開發板的GPU特點，構建了一個面向向量相似度計算和提取最相似TOPN個詞向量的系統。該系統的特點是：

①系統可以根據計算任務的規模彈性擴充，當計算資源不足的時候，可以隨時向集群中增進計算節點，擴充系統的計算能力。

②利用Hadoop集群的特點完成文件的分發和與GPU的整合。

③利用GPU對批量的向量相似度計算任務進行加速。

④利用Jetson TK1的特點，避免了Host端和Device端之間數據傳遞的時延。

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

[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并行研究模型綜述.電子學報.2011,39(11):2635-2642

國家自然科學基金項目（61602044）；北京市教委科研計劃面上項目（KM201411231014）；北京信息科技大學2016年人才培養質量提高經費（5111610800）；北京信息科技大學2017年人才培養質量提高經費（5111723400）

張禹堯，男，1996—，本科在讀，研究方向為自然語言處理；毛騰，女，1995—，研究生在讀，研究方向為自然語言處理；李俊，男，1994—，研究生在讀，研究方向為自然語言處理；蔣玉茹，女，1978—，博士，講師，研究方向為人工智能、自然語言處理。