多核系統(tǒng)上任意2序列公共元素的并行查找

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

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

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

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

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

1.1 算法的設(shè)計(jì)

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

（1）p個(gè)處理核心應(yīng)用并行快速排序算法［8］分別對(duì)數(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í)緩存大小的利用率來進(jìn)行分塊，每組數(shù)據(jù)塊的大小為θC2，數(shù)據(jù)序列b分為m／（θC2）組，依次從主存調(diào)入二級(jí)緩存。接著對(duì)分配到二級(jí)緩存的數(shù)據(jù)再進(jìn)行分塊，劃分的依據(jù)是一級(jí)緩存大小的利用率，每塊數(shù)據(jù)塊的大小為βC1，共θC2／（pβC1）塊，各個(gè)數(shù)據(jù)塊分別映射到各個(gè)處理器核心。因?yàn)檫M(jìn)行數(shù)據(jù)劃分后映射到各個(gè)處理器核心的數(shù)據(jù)在處理過程中不需要進(jìn)行交換，因此各個(gè)處理器核心之間不存在數(shù)據(jù)的移動(dòng)問題。

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

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

1.2 算法的正確性

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

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

因?yàn)閿?shù)據(jù)序列a元素分塊時(shí)的劃分是依據(jù)當(dāng)前存儲(chǔ)在一級(jí)緩存中的數(shù)據(jù)塊bi的最小值min和最大值max，所以在進(jìn)行查找公共元素操作時(shí)，能保證數(shù)據(jù)塊ai和bi的元素處于相同的取值區(qū)間，這樣就能保證查找的正確性。因?yàn)樗惴▓?zhí)行過程中各個(gè)處理器核心是并行進(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個(gè)數(shù)據(jù)塊），這樣可以保證各個(gè)處理器核心查找成功后的結(jié)果能并行地寫入數(shù)組c。

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

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

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

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

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)環(huán)境

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

2.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖6 二級(jí)緩存利用率增加時(shí)本文算法的運(yùn)行時(shí)間

3 結(jié)束語

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

［5］馮 佩，鐘 誠，韋 偉.多核多線程并行求解線性方程組［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(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ì)算矩陣乘積［J］.小型微型計(jì)算機(jī)系統(tǒng)，2011，32（5）：860－866.

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