張正東

（貴陽學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，貴陽 550005）

0 引言

隨著大數(shù)據(jù)和人工智能技術(shù)的快速發(fā)展，其應(yīng)用范圍越來越廣，產(chǎn)生和匯集了海量數(shù)據(jù)，數(shù)據(jù)屬性越來越多，維度越來越大，如何表示和處理海量高維數(shù)據(jù)以挖掘數(shù)據(jù)價值是我們面臨的一大挑戰(zhàn)［1］。張量因其多維特性是解決這一問題的有效方法。張量在數(shù)學(xué)上是多維數(shù)組或多維陣列，可用多個下標表示，是向量和矩陣概念向高維空間的推廣。張量的維數(shù)稱為階（order）或模（mode）［2］，高階張量具有多個維度，非常適合用來表示現(xiàn)實世界中的多維、復(fù)雜數(shù)據(jù)，如復(fù)雜網(wǎng)絡(luò)、多維社交關(guān)系等。張量在人工智能中得到了廣泛應(yīng)用，現(xiàn)在流行的深度學(xué)習(xí)框架TensorFlow就將張量作為一種基本數(shù)據(jù)模型［3］。高階張量隨著維度的增加，表示的多維關(guān)系越來越復(fù)雜，存儲的數(shù)據(jù)量也越來越大，如5階張量，每階數(shù)據(jù)量為1 000，總數(shù)據(jù)量為103*103*103*103*103=1015，如此海量數(shù)據(jù)對存儲和計算提出了更高要求。實際應(yīng)用中，高階張量往往是稀疏的，也即只有一部分元素是非0值。在此情況下，我們需要設(shè)計一種有效的存儲方案以擴大張量的應(yīng)用范圍，并能以并行計算或分布式計算方式進行數(shù)據(jù)處理。

并行計算是處理海量數(shù)據(jù)的常用方法之一。隨著CPU和GPU技術(shù)的發(fā)展，其核心數(shù)越來越多，特別是在GPU計算中，可以開啟幾十、幾百上甚至千個線程并行處理數(shù)據(jù)［4］，能大大降低計算時間。采用并行方式處理數(shù)據(jù)，數(shù)據(jù)在本地完成處理，可避免數(shù)據(jù)在集群中傳播、計算任務(wù)分發(fā)和結(jié)果收集的時間開銷，同時也能更好的發(fā)揮機器算力。在集群環(huán)境中，計算節(jié)點上開啟多線程進行并行計算能更好的提高數(shù)據(jù)處理效率［5］，這也是很多流行的分布式計算框架采用的方法，比如分布式內(nèi)存計算框架Spark。

張量的一種基本運算是與向量相乘，以此達到對張量降維的目的，是最頻繁的張量運算之一，該步驟的計算速度對整體性能有較大影響。本文的研究內(nèi)容即是如何用key-value對表示高階張量并實現(xiàn)張量與向量的并行相乘。

1 算法實現(xiàn)

1.1 算法描述

對于N維空間張量X∈RI1×I2×…×I N和1維空間向量v∈RI n，張量和向量的mode-n相乘規(guī)則為公式（1）。mode-n是指向量和張量的哪個維度相乘。

從公式（1）可以看出，張量與向量相乘的結(jié)果也是張量，但已經(jīng)沒有n維度了，即消去了n維度，結(jié)果張量少了一個維度，對張量進行了降維。張量和向量mode-n相乘的過程是固定張量其他維度下標，遍歷n維度下標，用此下標到向量中取值并和張量元素值相乘，最后將下標相同的元素求和。這就要求張量n維度的元素個數(shù)和向量元素個數(shù)相同。如張量X∈R2×2×2和向量v∈R2的mode-2相乘，結(jié)果為張量X'∈R2×2，如公式（2）所示。其中，張量和向量元素值用下標表示。

為了采用多線程技術(shù)實現(xiàn)張量與向量的并行相乘，我們可以用key-value對表示張量元素，其中key為張量元素下標組合，value為元素值。這樣張量就可以轉(zhuǎn)換成Map或者列表（列表元素是自定義的JavaBean，包含key和value屬性）。通過將Map或者列表均勻分割，開啟多線程，每個線程處理一部分，最后匯聚，從而實現(xiàn)張量和向量并行相乘。公式（1）表明，采用分割-匯聚策略，對最終結(jié)果沒有影響。我們只對張量中非0值元素進行轉(zhuǎn)換，對于0值元素，根據(jù)公式（1），其和向量元素相乘結(jié)果也為0，對求和結(jié)果沒有影響。張量與向量并行相乘過程如算法1。算法1采用了線程池技術(shù)對線程進行管理和復(fù)用，避免多次創(chuàng)建線程開銷，并在每個線程中進行局部匯聚，實現(xiàn)局部優(yōu)化，進而提高計算效率。

算法1張量與向量并行相乘。

1.定義包含key和value屬性的JavaBean，表示張量非0值元素。

2.將張量轉(zhuǎn)換為列表。

3.將列表均勻分割，啟動線程池，每部分用一個線程計算。

4.對于每一個計算線程，遍歷列表元素：

5. 對于每一個key-value對，將key分割成張量下標。

6. 用n維度下標到向量中取值并和value相乘，得到新值value'。

7.去除n維度下標，重新生成key'。

8.將key'-value'放到Map中，進行局部匯聚。

9.收集線程計算結(jié)果，進行全局匯聚。

10.生成結(jié)果。

1.2 實現(xiàn)代碼

算法1程序?qū)崿F(xiàn)主要包括兩部分，一是均勻分割張量元素列表，每部分對應(yīng)一個計算線程，通過線程池管理；二是在每個線程內(nèi)部實現(xiàn)張量和向量相乘。第一部分實現(xiàn)程序為：

private Map＜String,Integer>computeInThread（List＜Element>dataList,int threadCount,final int［］vector,final int modeN）{

int cpuCore=Runtime.get Runtime（）.availableProcessors（）;//獲取CPU核心數(shù)

//計算線程池最大容量

int pool Size=threadCount＜=cpuCore?thread-Count:cpuCore;

int threadSize=dataList.size（）/threadCount;//每個線程處理數(shù)據(jù)量

//創(chuàng)建固定大小的線程池

ExecutorService executorService = Executors.new-FixedThreadPool（poolSize）;

for（int index=0;index＜threadCount;index++）{

//根據(jù)線程數(shù)量，計算每部分開始和結(jié)束下標

int fromIndex=index*threadSize;

int toIndex=（index+1）*threadSize;

if（index==threadCount-1）{

toIndex=dataList.size（）;

}

if（fromIndex＜toIndex）{

//通過下標取列表部分，分割列表

final List＜Element>tensor=dataList.subList（fromIndex,toIndex）;

//以lambda表達式形式向線程池提交一個計算線程任務(wù)

executorService.execute（（）->ttv（tensor,vector,modeN））;

}

}

executorService.shutdown（）;//關(guān)閉線程池，等待計算完成

while（true）{

if（executorService.isTerminated（））{

break;

}

}

//全局結(jié)果

Map＜String,Integer>result Map=new HashMap＜>（）;

//tmpResultList是全局列表，存放了每個線程計算結(jié)果

for（Map＜String,Integer> tmpResult Map:tmpResultList）{

for（String key:tmpResultMap.keySet（））{

int tmpValue=tmpResultMap.get（key）;

//全局匯聚

processMapElement（resultMap,key,tmpValue）;

}

}

return result Map;

}

上述程序中的processMapElement函數(shù)進行Map中元素匯聚，將相同key的元素值求和，程序代碼為：

private void processMapElement（Map＜String,Integer>map,String key,int value）{

int rValue=value;

if（map.containsKey（key））{

//若key已經(jīng)存在，將值求和

rValue+=map.get（key）;

}

map.put（key,rValue）;

}

ttv函數(shù)為張量和向量相乘，也即第二部分，程序代碼為：

private void ttv（List＜Element>tensor,int［］vector,int modeN）{

Map＜String,Integer>resultMap=new HashMap＜>（）;

//局部結(jié)果map

for（Element element:tensor）{//遍歷張量元素

String［］keySplits=element.getKey（）.split（"#"）;

//分割key

int value=element.getValue（）;

//到向量中取值并和張量值相乘

int mValue=value*vector［Integer.parseInt（key-Splits［modeN-1］）］;

String mKey="";

//去除相乘維度下標，組合新的key

for（int index=0;index＜keySplits.length;index++）{

if（index!=modeN-1）{

mKey=mKey+keySplits［index］+"#";

}

}

//去除結(jié)尾的分隔符

if（mKey.endsWith（"#"））{

mKey=mKey.substring（0,mKey.length（）-1）;

}

//局部匯聚

processMapElement（result Map,mKey,mValue）;

}

tmpResultList.add（resultMap）;

}

ttv函數(shù)中，我們定義了一個全局列表，用于收集每個線程的計算結(jié)果。由于多個線程都會向全局列表中添加數(shù)據(jù)，為了避免數(shù)據(jù)混亂，我們采用了具有線程寫安全性的CopyOnWriteArray List。我們將張量與向量乘積結(jié)果放在Map中，其中key為張量元素下標組合，value為值。結(jié)果Map可以很容易轉(zhuǎn)換為元素列表，或者將key拆分還原到張量中，以進行下一步處理。

2 結(jié)果與分析

算法采用了Java實現(xiàn)，JDK版本為8u181，機器內(nèi)存為16 G，CPU為Intel i7-7700HQ，核心數(shù)為8。我們進行了兩次運算，一次是低階張量和向量相乘，用于測試算法的準確性，張量X∈R2×2×2和向量v∈R2，元素值隨機產(chǎn)生，進行mode-2相乘，結(jié)果如圖1所示。

圖1 張量和向量mode-2相乘的結(jié)果

其中，冒號（：）表示所有下標，x是原張量，v是向量，x'是結(jié)果張量。

另一次運算是測試計算規(guī)模和時間，我們分別設(shè)置計算線程數(shù)為6、10和16，線程池容量為線程數(shù)和機器核心數(shù)的最小值，非0元素下標和值以及向量值均隨機產(chǎn)生，對于每個線程數(shù)計算三次，取平均時間，計算結(jié)果如表1所示。數(shù)據(jù)表明，我們實現(xiàn)的并行算法可用于大規(guī)模張量與向量相乘，隨著線程數(shù)的增加，計算的并行度提高，計算時間也進一步降低。實際應(yīng)用中可根據(jù)機器配置，設(shè)置合適的線程數(shù)量。因為算法1只對張量中的非0值進行處理，對于稀疏張量，由于大部分是0值，算法的性能會更高，能處理的數(shù)據(jù)規(guī)模也更大。

表1 大規(guī)模高階稀疏張量與向量相乘數(shù)據(jù)