蔡德霞， 鐘 誠， 韋興柳， 林孔升

（廣西大學(xué) 計算機(jī)與電子信息學(xué)院，廣西 南寧 530004）

任意2序列公共元素的查找問題可應(yīng)用于數(shù)據(jù)庫、統(tǒng)計、運籌學(xué)和組合學(xué)等領(lǐng)域。文獻(xiàn)［1］研究了由有序序列x和y組成的排序矩陣上的并行查找問題，并指出可使用排序矩陣上的并行查找思想來實現(xiàn)任意2序列公共元素的查找問題。文獻(xiàn)［2］設(shè)計了PRAM模型上任意2序列公共元素的并行查找算法。近年來，多核結(jié)構(gòu)發(fā)展成為微處理器的主流，它支持緩存高效和線程級并行［3］，具有高度的并行處理能力［4］。文獻(xiàn)［5］采取將線性方程組的增廣矩陣按行劃分并合理分布到各級緩存，各個處理核以多線程方式并行計算矩陣行的方法，設(shè)計了多核系統(tǒng)上線程級并行求解n階線性方程組的算法。文獻(xiàn)［6］利用軟件多線程技術(shù)和多核結(jié)構(gòu)中的多級Cache機(jī)制，基于可分負(fù)載理論的最優(yōu)原則，針對Multisets數(shù)據(jù)序列的特點，提出一種多輪非周期性的數(shù)據(jù)序列最優(yōu)分配模型，進(jìn)而設(shè)計實現(xiàn)進(jìn)程級與線程級并行的Multisets排序算法。文獻(xiàn)［7］從綜合提高多核計算機(jī)共享二級緩存的利用率、矩陣存儲的數(shù)據(jù)結(jié)構(gòu)優(yōu)化、計算與訪存重疊操作、緩存無關(guān)等角度出發(fā)，提出適合矩陣乘積問題并行計算的數(shù)據(jù)分布和調(diào)度策略，設(shè)計實現(xiàn)非遞歸、高效和可擴(kuò)展的矩陣乘積并行算法。

本文采用數(shù)據(jù)多級分塊技術(shù)、數(shù)據(jù)局部性原理和循環(huán)并行優(yōu)化方法，充分利用多核處理器的多級存儲和多線程技術(shù)，設(shè)計實現(xiàn)多核系統(tǒng)上存儲高效、線程級并行、擴(kuò)展性好的任意2序列公共元素的并行查找算法。

1 算法的設(shè)計與分析

1.1 算法的設(shè)計

多核系統(tǒng)上任意2序列公共元素并行查找算法描述為：

（1）p個處理核心應(yīng)用并行快速排序算法［8］分別對數(shù)據(jù)序列a、b進(jìn)行排序。

（2）如果排序后的數(shù)據(jù)序列a的最小值大于排序后的數(shù)據(jù)序列b的最大值，或者數(shù)據(jù)序列a的最大值小于排序后的數(shù)據(jù)序列b的最小值，則數(shù)據(jù)序列a和數(shù)據(jù)序列b無公共元素。

（3）將主存中的數(shù)據(jù)序列b根據(jù)二級緩存大小的利用率來進(jìn)行分塊，每組數(shù)據(jù)塊的大小為θC2，數(shù)據(jù)序列b分為m／（θC2）組，依次從主存調(diào)入二級緩存。接著對分配到二級緩存的數(shù)據(jù)再進(jìn)行分塊，劃分的依據(jù)是一級緩存大小的利用率，每塊數(shù)據(jù)塊的大小為βC1，共θC2／（pβC1）塊，各個數(shù)據(jù)塊分別映射到各個處理器核心。因為進(jìn)行數(shù)據(jù)劃分后映射到各個處理器核心的數(shù)據(jù)在處理過程中不需要進(jìn)行交換，因此各個處理器核心之間不存在數(shù)據(jù)的移動問題。

（4）求出序列b劃分后存到各處理器核心一級緩存中的數(shù)據(jù)塊bi的最小值min和最大值max，min＝b［（i－1）βC1］，max＝b［iβC1－1］。為減少序列b中元素的移動，應(yīng)將序列a進(jìn)行分塊，將序列a中符合區(qū)間（b（i－1）βC1，b（iβC1－1）］的數(shù)據(jù)映射到數(shù)據(jù)塊bi所在的處理器核心。

（5）各個處理器核心并行調(diào)用串行的二分查找方法，查找數(shù)據(jù)塊ai和bi是否具有公共元素，如果存在，將公共元素保存并統(tǒng)計公共元素個數(shù)k。因為并行調(diào)用串行的二分查找方法，在各個處理器核心查找數(shù)據(jù)塊ai和bi的公共元素操作結(jié)束時不能立即確定出公共元素的數(shù)目，所以需要設(shè)定一個共享數(shù)組c［i］（i的取值為數(shù)據(jù)序列b劃分到一級緩存的總塊數(shù)）來保存數(shù)據(jù)塊ai和bi的公共元素的個數(shù)，在查找操作前需給數(shù)組c中各元素賦以初值零。在數(shù)據(jù)序列a和數(shù)據(jù)b的所有數(shù)據(jù)塊都完成查找操作后，c［i］保存各個數(shù)據(jù)塊的查找結(jié)果，根據(jù)c數(shù)組可以統(tǒng)計出數(shù)據(jù)序列a和數(shù)據(jù)序列b的公共元素的總數(shù)k。

1.2 算法的正確性

本算法的關(guān)鍵點是要保證公共元素個數(shù)k≠0或者k≠n時k值的正確性，而保證k≠0或者k≠n的正確性的關(guān)鍵操作是要保證劃分到一級緩存中的數(shù)據(jù)塊ai的元素的取值范圍為（b（i－1）βC1，b（iβC1－1）］，查找成功后元素保存到數(shù)組c［i］中。

中國在棉紡織業(yè)的發(fā)展戰(zhàn)略上指出要充分利用“一帶一路”的戰(zhàn)略機(jī)遇，與棉紡織業(yè)成長迅速的發(fā)展中國家進(jìn)行合作，實現(xiàn)資源優(yōu)化配置；發(fā)展新疆及西部紡織行業(yè)。新疆自治區(qū)在2016年發(fā)布了關(guān)于紡織服裝產(chǎn)業(yè)補(bǔ)貼管理辦法。其中提到在原有的相關(guān)優(yōu)惠政策不變的前提下。同時新增了預(yù)撥補(bǔ)貼資金、加快兌付進(jìn)度、對運費補(bǔ)貼實行動態(tài)管理以及簡化資金撥付程序等方面的內(nèi)容。

因為數(shù)據(jù)序列a元素分塊時的劃分是依據(jù)當(dāng)前存儲在一級緩存中的數(shù)據(jù)塊bi的最小值min和最大值max，所以在進(jìn)行查找公共元素操作時，能保證數(shù)據(jù)塊ai和bi的元素處于相同的取值區(qū)間，這樣就能保證查找的正確性。因為算法執(zhí)行過程中各個處理器核心是并行進(jìn)行二分查找操作，查找成功后，為了防止并行寫沖突，采用中間數(shù)組c來保存查找結(jié)果可解決并行寫沖突問題。數(shù)組c的下標(biāo)取值范圍為［0，m／（pβC1）］，每一組數(shù)據(jù)塊ai和bi成功查找后的結(jié)果保存于c［i］（i為數(shù)據(jù)序列b劃分后的第i個數(shù)據(jù)塊），這樣可以保證各個處理器核心查找成功后的結(jié)果能并行地寫入數(shù)組c。

1.3 算法復(fù)雜度分析

算法步驟（1）中p個處理核心對整數(shù)序列a和b排序的時間為O（n＋nlb（n／p））；步驟（2）可在O（1）時間內(nèi)完成；步驟（3）對整數(shù)序列a和整數(shù)序列b進(jìn)行數(shù)據(jù)劃分后映射到各3個處理器核心，使得整數(shù)序列a和整數(shù)序列b中的數(shù)據(jù)在處理過程中不需要進(jìn)行交換，該步驟可在減少主存和L2Cache、L2Cache和L1Cache之間數(shù)據(jù)交換的同時也使得各個處理器核心之間不存在數(shù)據(jù)的移動問題。因此，對于支持的多核系統(tǒng)，算法（3）～（4）步的完成時間為O（m／（θC2））×O（θC2／（p2βC1））＝O（m／（p2βC1））。步驟（5）每個處理核心調(diào)用二分查找算法查找數(shù)據(jù)塊ai和bi的公共元素，假設(shè)數(shù)據(jù)塊ai的規(guī)模為si，數(shù)據(jù)塊bi的規(guī)模為sj＝βC1，于是該步驟可在O（silb（βC1））時間內(nèi)完成。

本文給出的并行算法的加速度為：

本文給出的并行算法的執(zhí)行代價為：當(dāng)處理核心數(shù)目p＜lbn時，本文給出的并行算法獲得了線性加速并且執(zhí)行代價是最優(yōu)的。

2 實驗

2.1 實驗環(huán)境

實驗的硬件平臺為Intel（R）Xeron（R）E5405 2.0GHz四核計算機(jī)，二級緩存容量為12Mb，一級緩存容量為128kb，操作系統(tǒng)為Red Hat Enterprise Linux 5，采用OpenMP和C語言編程實現(xiàn)本文的多核系統(tǒng)上任意2序列公共元素并行查找算法。

2.2 實驗結(jié)果與分析

實驗假設(shè)數(shù)據(jù)序列a和b的數(shù)據(jù)規(guī)模相等，在四核計算機(jī)上，通過采用動態(tài)關(guān)閉處理核的方法，考慮了處理器核數(shù)、數(shù)據(jù)序列的規(guī)模及線程數(shù)等因素，測試了多核系統(tǒng)上任意2序列公共元素的并行查找算法的運行時間和加速比，并與非分塊的任意2序列公共元素的并行查找算法（簡稱非分塊算法）［2］的運行時間進(jìn)行了對比。

不同數(shù)據(jù)規(guī)模，線程數(shù)增加，運行不同的處理器核數(shù)時，多核系統(tǒng)上任意2序列公共元素的并行查找算法的運行時間如圖1所示。

圖1 運行不同數(shù)量處理核本文算法所需的時間

從圖1a可看出，對不同數(shù)據(jù)規(guī)模，運行4個處理核時，線程數(shù)為7～12時算法的運行時間較好，其中線程數(shù)為7時最佳。從圖1b可看出，對不同數(shù)據(jù)規(guī)模，運行3個處理核時，線程數(shù)為6～10時算法的運行時間較好，其中線程數(shù)為6時最佳。從圖1c可看出，對不同數(shù)據(jù)規(guī)模，運行2個處理核時，線程數(shù)為4～7時算法的運行時間較好，其中線程數(shù)為4時最佳。由圖1可看出，對于不同處理核數(shù)目，其最佳線程數(shù)也不同，線程數(shù)約為2倍處理核數(shù)目時，算法的運行時間最少。此外，當(dāng)線程數(shù)大于3倍處理核數(shù)目時，隨著線程數(shù)目的增加，線程對處理器的競爭會隨之增大，線程的啟動／停止、上下文切換會產(chǎn)生更大的額外開銷，因此，算法的運行時間會逐漸上升。

輸入數(shù)據(jù)規(guī)模分別為 1×107、2×107、4×107、8×107、12×107個整數(shù)時，隨著處理核數(shù)目的增加，采用最佳線程數(shù)執(zhí)行多核系統(tǒng)上任意2序列公共元素的并行查找算法所消耗的執(zhí)行時間如圖2所示。

圖2 采用最佳線程數(shù)執(zhí)行本文查找算法的運行時間

從圖2可看出，隨著處理核數(shù)目的增加，多核系統(tǒng)上任意2序列公共元素的并行查找算法顯著下降，運行時間下降趨勢變得緩慢。這是因為多核系統(tǒng)的通信開銷會隨著處理核心數(shù)目的增加而變得越來越大，并且多個處理核心訪問共享資源也會逐漸增大時間開銷。

不同數(shù)據(jù)規(guī)模，隨著處理核數(shù)目的增加，采用最佳線程數(shù)運行多核系統(tǒng)上任意2序列公共元素的并行查找算法的加速比如圖3所示。

圖3 采用最佳線程數(shù)執(zhí)行本文算法的加速比

圖3的實驗結(jié)果表明，隨著處理核數(shù)目的增加，多核系統(tǒng)上任意2序列公共元素的并行查找算法的加速比逐漸增大，接近于對數(shù)加速。

多核系統(tǒng)上任意2序列公共元素的并行查找算法的等效率函數(shù)曲線如圖4所示。從圖4可以看出，對于2個任意規(guī)模的輸入數(shù)據(jù)序列，為了維持等效率，本文提出算法的工作量隨著處理核數(shù)目呈現(xiàn)近似亞線性的增長。這表明本文所提出的算法具有較好的可擴(kuò)展性。

圖4 采用最佳線程數(shù)執(zhí)行本文算法的等效率曲線

對于相同數(shù)據(jù)序列，在四核計算機(jī)上，采用最佳線程數(shù)執(zhí)行本文提出的多核系統(tǒng)上任意2序列公共元素的并行查找算法與非分塊算法在運行時間上的對比如圖5所示。

圖5 采用最佳線程數(shù)執(zhí)行本文算法和非分塊算法的運行時間

從圖5可知，本文算法明顯優(yōu)于非分塊算法，這是因為本文算法充分利用二級緩存和一級緩存來提高數(shù)據(jù)的局部性，避免緩存缺失性，能減少非分塊算法中出現(xiàn)的數(shù)據(jù)頻繁交換操作。此外，隨著數(shù)據(jù)規(guī)模的增加，本文算法的優(yōu)異性更加明顯，這說明當(dāng)數(shù)據(jù)規(guī)模很大時，在多核系統(tǒng)上有效利用二級緩存，采用數(shù)據(jù)多級分塊技術(shù)可以更有效地求解任意2序列公共元素的并行查找問題。

運行4個處理核時，對不同的數(shù)據(jù)規(guī)模，采用最佳線程數(shù)，二級緩存利用率θ增加時運行本文算法所需要的時間如圖6所示。從圖6可看出，二級緩存的利用率對本文算法的性能是一個很重要的影響因素。當(dāng)θ＝0.6時，本文算法的運行時間效果較好，當(dāng)θ＞0.6，隨著θ的增大，本文算法的時間性能下降。由此可知，在算法運行過程中，對于數(shù)據(jù)劃分，應(yīng)分配合適的數(shù)據(jù)存儲到二級緩存，劃分時要預(yù)留一定的空間來存放中間結(jié)果、指令代碼以及算法運行過程中所產(chǎn)生的一些額外開銷。

圖6 二級緩存利用率增加時本文算法的運行時間

3 結(jié)束語

本文充分利用多核計算機(jī)的多級存儲和數(shù)據(jù)多級分塊技術(shù)以及數(shù)據(jù)局部性方法，將給定的2序列劃分適合于二級緩存大小的數(shù)據(jù)塊以減少主存和二級緩存之間數(shù)據(jù)的交換；通過將存儲在二級緩存中的數(shù)據(jù)平均分配給一級緩存，減少了二級緩存和一級緩存數(shù)據(jù)交換，使得大大減少處理核之間通信時間的同時，能確保處理核之間的數(shù)據(jù)負(fù)載均衡。并行多線程技術(shù)和循環(huán)并行優(yōu)化方法設(shè)計的多核系統(tǒng)上任意2序列公共元素并行查找算法高效、可擴(kuò)展。進(jìn)一步的工作是基于多核機(jī)群系統(tǒng)，研究設(shè)計存儲和通信高效、加速比和可擴(kuò)展性好的任意2序列公共元素的并行查找算法。

［1］Cosnard M，F(xiàn)erreira A.Parallel algorithms for searching inx＋y［C］／／Proc of the 1989International Conference on Parallel Processing，1989：16－19.

［2］鐘 誠.任意兩序列公共元素的并行查找［J］.微電子學(xué)與計算機(jī)，1993（9）：18－20.

［3］Akhter S，Robert J.Multi－core programming：increasing performance through software multi－threading［M］.北京：電子工業(yè)出版社，2007：45－70.

［4］李曉明，王 韜，劉 東，等.走進(jìn)多核時代［J］.計算機(jī)科學(xué)與探索，2008，2（6）：562－570.

［5］馮 佩，鐘 誠，韋 偉.多核多線程并行求解線性方程組［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2011，34（2）：237－240，250.

［6］Zhong Cheng，Qu Zengyan，Yang Feng，et al.Parallel multisets sorting using aperiodic multi－round distribution strategy on heterogeneous multi－core clusters［C］／／Proc of 3rd International Symposium on Parallel Architectures，Algorithms and Programming.IEEE Computer Society Press，2010：247－254.

［7］鹿中龍，鐘 誠，黃華林.多核計算機(jī)上非遞歸并行計算矩陣乘積［J］.小型微型計算機(jī)系統(tǒng)，2011，32（5）：860－866.

［8］陳國良，安 虹，陳 崚，等.并行算法實踐［M］.北京：高等教育出版社，2004：185－187.