基于切比雪夫距離的支撐點(diǎn)選擇算法的并行優(yōu)化研究

陶順安 李強(qiáng) 尚小敏 周全 張璁

摘要：

求解切比雪夫距離的支撐點(diǎn)選擇算法中，由于計(jì)算量較大，如何快速判斷支撐點(diǎn)的優(yōu)劣是一個(gè)難以解決的問題，為此，提出一套以切比雪夫距離為目標(biāo)函數(shù)的快速支撐點(diǎn)優(yōu)選策略。通過并行化分析找出相對(duì)獨(dú)立的計(jì)算任務(wù)，使用OpenMP對(duì)支撐點(diǎn)的選擇并行化處理；為降低算法層面的時(shí)間復(fù)雜度，將切比雪夫距離轉(zhuǎn)化為曼哈頓距離，減少了總體計(jì)算量；采用多線程的方法對(duì)目標(biāo)函數(shù)值的排序環(huán)節(jié)進(jìn)行總體重構(gòu)，避免了無意義的訪存開銷。實(shí)驗(yàn)結(jié)果表明，相比傳統(tǒng)方法，支撐點(diǎn)優(yōu)選算法具有較為明顯的加速效果，加速比達(dá)到了174.62，并解決了算法的數(shù)據(jù)依賴問題。

關(guān)鍵詞：

切比雪夫距離；支撐點(diǎn)選擇；并行計(jì)算

中圖分類號(hào)：

TP338.6

文獻(xiàn)標(biāo)志碼：A

度量空間的最大優(yōu)勢(shì)在于其高度的普遍適用性，用戶只需提供距離函數(shù)就可以進(jìn)行相似性搜索。然而，度量空間的優(yōu)勢(shì)也是其劣勢(shì)，數(shù)據(jù)被抽象成度量空間中的點(diǎn)，雖然提高了通用性，但同時(shí)損失了坐標(biāo)信息，唯一可用的信息就是距離。由于沒有坐標(biāo)，許多數(shù)學(xué)方法不能直接使用。為此，通常先找出一些參考點(diǎn)（也稱支撐點(diǎn)，Pivot），然后將數(shù)據(jù)到此參考點(diǎn)的距離作為坐標(biāo)。支撐點(diǎn)的好壞對(duì)于度量空間數(shù)據(jù)管理分析的性能發(fā)揮著關(guān)鍵性的影響［1］，支撐點(diǎn)的選取可以從目標(biāo)函數(shù)和選擇算法兩個(gè)方面進(jìn)行研究。常用的目標(biāo)函數(shù)是均值目標(biāo)函數(shù)［2-4］，Bustos［5］研究了k維支撐點(diǎn)空間中的距離對(duì)的均值和方差，以均值作為目標(biāo)函數(shù)值，選出均值最大時(shí)所對(duì)應(yīng)的數(shù)據(jù)作為支撐點(diǎn)，但沒有考慮查詢半徑對(duì)排除效果的影響。常用的支撐點(diǎn)選擇算法［6-7］包括最遠(yuǎn)優(yōu)先遍歷（Farthest First Traversal，F(xiàn)FT）［8］和Incremental［9-10］。FFT可以在線性時(shí)間內(nèi)選出數(shù)據(jù)拐角的點(diǎn)，并且性能有一定的保證，但是，實(shí)驗(yàn)表明最好的支撐點(diǎn)往往不是拐角的點(diǎn)，因而FFT很難選出最優(yōu)點(diǎn)。Incremental是一種增量式選擇支撐點(diǎn)的算法，也能夠快速地選出支撐點(diǎn)，但存在著局部最優(yōu)的問題，即以最優(yōu)目標(biāo)函數(shù)值依次選出的兩個(gè)支撐點(diǎn)組合在一起，不一定是性能最優(yōu)的支撐點(diǎn)組合。采用暴力枚舉法和快速支撐點(diǎn)選擇窮舉算法選取支撐點(diǎn)時(shí)，通過MPI通信在節(jié)點(diǎn)間傳輸數(shù)據(jù)，在節(jié)點(diǎn)內(nèi)采用多進(jìn)程并行的計(jì)算方式，以得到最優(yōu)和最劣支撐點(diǎn)的分布情況，但并沒有解決算法本身的數(shù)據(jù)依賴問題［11-12］。本文改進(jìn)了支撐點(diǎn)選擇的窮舉算法，提出一套支撐點(diǎn)優(yōu)選策略，以任意兩點(diǎn)的重建坐標(biāo)間的切比雪夫距離為目標(biāo)函數(shù)，選出最優(yōu)和最差的支撐點(diǎn)組合，并對(duì)此算法進(jìn)行線程級(jí)并行優(yōu)化［13］，在保證準(zhǔn)確性的前提下解決了數(shù)據(jù)依賴問題，使算法得到了顯著的加速。

1 基于切比雪夫距離的支撐點(diǎn)選擇算法分析

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

在度量空間中，數(shù)據(jù)點(diǎn)沒有坐標(biāo)值，距離是唯一可用的信息，但一些基于數(shù)學(xué)工具的數(shù)據(jù)處理方式難以直接利用。為便于處理和分析數(shù)據(jù)點(diǎn)，提出了支撐點(diǎn)空間的概念［14］，從數(shù)據(jù)集中選取一些點(diǎn)作為支撐點(diǎn)，將任意數(shù)據(jù)點(diǎn)到各支撐點(diǎn)的距離形成的向量作為坐標(biāo)，將數(shù)據(jù)點(diǎn)映射到一個(gè)新的空間中，即支撐點(diǎn)空間（圖1）。

假設(shè)要處理的數(shù)據(jù)集S={xi|i =1， 2，…， n}，共有n個(gè)數(shù)據(jù)點(diǎn)，任意兩點(diǎn)間的距離由距離函數(shù)d（.，.）計(jì)算；選擇k個(gè)點(diǎn)作為支撐點(diǎn)，標(biāo)記為P={pj|j=1， 2，…， k}。對(duì)于S中任意的數(shù)據(jù)點(diǎn)x，基于支撐點(diǎn)組合重建的坐標(biāo)是其到各支撐點(diǎn)的距離形成的量

支撐點(diǎn)優(yōu)選以目標(biāo)函數(shù)值為標(biāo)準(zhǔn)，可以評(píng)估所有支撐點(diǎn)組合的優(yōu)劣。

1.2 支撐點(diǎn)優(yōu)選算法結(jié)構(gòu)

支撐點(diǎn)優(yōu)選算法框架如圖2所示，主要包含四部分：Combination選取不同的支撐點(diǎn)組合，RebuiltCoord計(jì)算每個(gè)數(shù)據(jù)點(diǎn)到支撐點(diǎn)組合的歐氏距離，SumDistance計(jì)算不同支撐點(diǎn)組合的切比雪夫距離和，Sort對(duì)目標(biāo)函數(shù)值進(jìn)行排序。

算法首先讀取并初始化數(shù)據(jù)，然后遍歷所有支撐點(diǎn)，選取不同的支撐點(diǎn)作為支撐點(diǎn)組合，判斷所有支撐點(diǎn)組合是否全部得到目標(biāo)函數(shù)值，若是，則退出循環(huán)，算法結(jié)束；否則，繼續(xù)選取不同的支撐點(diǎn)組合。然后判斷是否選取到最后一個(gè)支撐點(diǎn)，若否，則節(jié)點(diǎn)下移，繼續(xù)遞歸循環(huán)選取支撐點(diǎn)；若是，則把數(shù)據(jù)點(diǎn)到支撐點(diǎn)組合的歐氏距離作為每個(gè)數(shù)據(jù)點(diǎn)的重建坐標(biāo)，然后計(jì)算任意兩點(diǎn)重建坐標(biāo)間的切比雪夫距離之和，再對(duì)其進(jìn)行排序，之后返回上一節(jié)點(diǎn)繼續(xù)遍歷支撐點(diǎn)，直到遍歷所有的支撐點(diǎn)，并判斷所有支撐點(diǎn)的優(yōu)劣。

2 算法的優(yōu)化處理

算法中Combination部分耗時(shí)最多，因?yàn)橹吸c(diǎn)組合有C（n，k）種，導(dǎo)致循環(huán)次數(shù)過多，可以使用OpenMP庫(kù)進(jìn)行多線程加速，并通過給每個(gè)線程分配獨(dú)立的內(nèi)存空間來解決數(shù)據(jù)依賴問題。SumDistance部分也非常耗時(shí)，原因是計(jì)算一次切比雪夫距離需要的時(shí)間復(fù)雜度是O（n2），可將切比雪夫距離轉(zhuǎn)換成曼哈頓距離，然后對(duì)其優(yōu)化。最后Sort部分在調(diào)整算法結(jié)構(gòu)后使用快速排序代替冒泡排序。

2.1 OpenMP并行優(yōu)化

OpenMP（Open Multi-Processing）是一種用于共享內(nèi)存多處理器計(jì)算機(jī)的應(yīng)用程序編程接口（API），可提供一系列的指令集、庫(kù)例程和環(huán)境變量等，能為程序員提供方便靈活的編程方式，實(shí)現(xiàn)多線程、共享內(nèi)存計(jì)算中的并行運(yùn)算。在支撐點(diǎn)優(yōu)選算法中，Combination選取最后一個(gè)支撐點(diǎn)時(shí)，剩下的數(shù)據(jù)點(diǎn)之間是相互獨(dú)立的，因此計(jì)算結(jié)果不會(huì)受到其他數(shù)據(jù)點(diǎn)的影響。這種獨(dú)立性能夠更高效地處理大量數(shù)據(jù)，并可將計(jì)算任務(wù)分配給多個(gè)處理器以加快處理速度。在Combination部分，使用OpenMP指令#pragma omp parallel for可以讓不同的線程同時(shí)處理不同的支撐點(diǎn)組合，從而加快計(jì)算速度。同時(shí)，由于每個(gè)線程都獨(dú)立工作，可以避免數(shù)據(jù)競(jìng)爭(zhēng)的情況。使用多線程計(jì)算時(shí)，為了解決數(shù)據(jù)依賴問題并保證計(jì)算結(jié)果的正確性和穩(wěn)定性，將不同線程的計(jì)算結(jié)果存儲(chǔ)到不同的內(nèi)存空間中。這樣，不同線程之間不會(huì)出現(xiàn)數(shù)據(jù)互相干擾或覆蓋的情況，而且每個(gè)線程計(jì)算完成后，結(jié)果也能夠得以正確保存，供其他線程繼續(xù)使用。

2.2 SumDistance優(yōu)化

本文采用了將切比雪夫距離轉(zhuǎn)換為曼哈頓距離的優(yōu)化方法。設(shè)平面內(nèi)存在兩點(diǎn)，坐標(biāo)為（x1，y1），（x2，y2），則切比雪夫距離為max{|x1-x2|， |y1-y2|}，即兩點(diǎn)橫縱坐標(biāo)差的最大值，曼哈頓距離為|x1-x2|+|y1-y2|，即兩點(diǎn)橫、縱坐標(biāo)差的絕對(duì)值之和。切比雪夫距離和曼哈頓距離可以互相轉(zhuǎn)化，在笛卡爾坐標(biāo)系中，用邊長(zhǎng)為2的正方形表示切比雪夫距離（圖3（a）），用邊長(zhǎng)為 2的正方形表示曼哈頓距離（圖3（b））。

對(duì)比圖3（a）和（b），將點(diǎn)（x，y）的坐標(biāo)變?yōu)椋▁+y，x-y）后，原坐標(biāo)系的曼哈頓距離等于新坐標(biāo)系的切比雪夫距離。將點(diǎn)（x，y）的坐標(biāo)變?yōu)椋?.5（x+y），0.5（x-y））后，原坐標(biāo)系的切比雪夫距離等于新坐標(biāo)系的曼哈頓距離。由于切比雪夫距離在計(jì)算時(shí)需要取最大值，所以不能直接優(yōu)化，對(duì)于一個(gè)點(diǎn)，計(jì)算其他點(diǎn)到該點(diǎn)距離的復(fù)雜度為O（n），計(jì)算任意兩點(diǎn)的切比雪夫距離和時(shí)，復(fù)雜度為O（n2）。而曼哈頓距離只有求和以及取絕對(duì)值兩種運(yùn)算，把坐標(biāo)排序后可以去掉絕對(duì)值的影響，進(jìn)而用前綴和優(yōu)化，可以把復(fù)雜度降為O（1），計(jì)算任意兩點(diǎn)的曼哈頓距離和時(shí)，復(fù)雜度為O（n）。

使用一個(gè)數(shù)組存n個(gè)點(diǎn)對(duì)第一個(gè)支撐點(diǎn)的距離，然后對(duì)數(shù)組從小到大快速排序，以此去掉絕對(duì)值的影響。xi代表第i個(gè)數(shù)據(jù)點(diǎn)（1≤i≤n），前綴和res表示第i個(gè)數(shù)據(jù)點(diǎn)到其他數(shù)據(jù)點(diǎn)距離之和，簡(jiǎn)化為

res=res+xi-x0+xi-x1+xi-x2+xi-x3+…+xi-xi-1（3）

res=res+xi*i-x0+x1+x2+…+xi-1（4）

res=res+xi*i-Si-1（5）

同理，任意兩個(gè)點(diǎn)y坐標(biāo)的曼哈頓距離一樣處理。|x1-x2|+|y1-y2|即為曼哈頓距離，對(duì)所有點(diǎn)的曼哈頓距離優(yōu)化求和即為原坐標(biāo)系的切比雪夫距離之和。由于對(duì)所有點(diǎn)進(jìn)行快速排序的時(shí)間復(fù)雜度為O（nlog n），故求切比雪夫距離和的時(shí)間復(fù)雜度由O（n2）優(yōu)化到O（nlog n）。

2.3 Sort優(yōu)化

對(duì)于串行算法，每得到一個(gè)目標(biāo)函數(shù)值，就對(duì)其進(jìn)行冒泡排序，以得到對(duì)應(yīng)支撐點(diǎn)組合的排序位置。由于總共有C（n，k）種支撐點(diǎn)組合，獲得C（n，k）個(gè)目標(biāo)函數(shù)值，因此需要C（n，k）次冒泡排序，時(shí)間復(fù)雜度為O（n2）。因?yàn)槊看蚊芭菖判虿⒉荒艽_定目標(biāo)函數(shù)值的最終位置，所以出現(xiàn)反復(fù)冒泡交換產(chǎn)生的無意義訪存開銷，效率太低。

對(duì)于Sort部分，本文使用一個(gè)數(shù)組把每種支撐點(diǎn)組合所得到的目標(biāo)函數(shù)值存儲(chǔ)起來，待所有支撐點(diǎn)組合遍歷結(jié)束，數(shù)組中將存儲(chǔ)所有的目標(biāo)函數(shù)值，然后對(duì)這些目標(biāo)函數(shù)值快速排序。

修改后的并行算法使用多線程計(jì)算所有支撐點(diǎn)組合的目標(biāo)函數(shù)值，并將其存儲(chǔ)在一個(gè)數(shù)組中。不同的線程需要將不同的目標(biāo)函數(shù)值存儲(chǔ)在不同的位置，因此需要給每個(gè)線程開辟一個(gè)私有空間存儲(chǔ)數(shù)據(jù)，避免產(chǎn)生數(shù)據(jù)沖突、數(shù)據(jù)覆蓋等問題。經(jīng)過推理，以k=2為例，當(dāng)數(shù)組以C（n，k）-C（n-i，k）+C（n-i-1，k-1）-C（n-j，k-1）（i，j為選取的兩個(gè)支撐點(diǎn)）為索引下標(biāo)時(shí)，每個(gè)線程都可以得到數(shù)組的一段空間來存儲(chǔ)各自的目標(biāo)函數(shù)值。最后對(duì)這個(gè)數(shù)組快速排序，僅需排序一次，時(shí)間復(fù)雜度為O（nlog n）。當(dāng)使用64個(gè)線程存儲(chǔ)數(shù)據(jù)時(shí)，各線程的存儲(chǔ)位置如圖4所示。

3 實(shí)驗(yàn)環(huán)境與結(jié)果

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

硬件環(huán)境，CPU：AMD EPYC 7452 32-Core Processor，雙節(jié)點(diǎn)，每節(jié)點(diǎn)雙socket，每socket 32核心；軟件環(huán)境，OS：CentOS Linux release 7.9.2009；GCC compiler：GCC-8.1.0；實(shí)驗(yàn)規(guī)模，數(shù)據(jù)點(diǎn)n=500，支撐點(diǎn)k=2。

3.2 消融研究

3.2.1 加入OpenMP的多線程優(yōu)化對(duì)比 經(jīng)過實(shí)驗(yàn)測(cè)試，OpenMP對(duì)Combination的加速效果較為明顯。算法的總運(yùn)行時(shí)間隨著線程數(shù)的增加而逐步減少，在線程數(shù)為64時(shí)總運(yùn)行時(shí)間最小，為1 191 ms，如圖5（a）所示。隨著線程數(shù)的增加，加速比最高達(dá)到了37.53，并行效率為58.6%（圖5（b））。

3.2.2 Sort部分優(yōu)化對(duì)比 經(jīng)過測(cè)試，在優(yōu)化前，Sort時(shí)間為272 ms，而優(yōu)化后僅需要14 ms，加速比高達(dá)19.43，如圖6（a）所示。在使用64線程并行計(jì)算的基礎(chǔ)上，算法總運(yùn)行時(shí)間從最初的1 191 ms縮短至571 ms，加速比從37.53提升至78.29（圖6（b））。

3.2.3 SumDistance部分優(yōu)化對(duì)比 在64個(gè)線程的并行環(huán)境下，對(duì)SumDistance部分從根本上進(jìn)行優(yōu)化，算法具體良好的加速趨向，SumDistance時(shí)間由416 ms變?yōu)榱?17 ms，加速比達(dá)到了3.56（圖7（a））；算法總的運(yùn)行時(shí)間最低達(dá)到了256 ms，加速比從78.29增大到了174.62，如圖7（b）所示。

4 結(jié)論

本文主要調(diào)整了支撐點(diǎn)優(yōu)選算法的SumDistance和Sort部分結(jié)構(gòu)，使時(shí)間復(fù)雜度從O（n2）降低到O（nlog n）。針對(duì)算法中的主要瓶頸Combination等進(jìn)行了線程級(jí)并行優(yōu)化，使算法得到了較大的加速。接下來將在超級(jí)計(jì)算機(jī)上進(jìn)行上百節(jié)點(diǎn)的測(cè)試，并使用cpu與gpu（或加速器）的異構(gòu)眾核架構(gòu)進(jìn)行并行加速。

參考文獻(xiàn)

［1］李興亮，毛睿.基于近期最遠(yuǎn)遍歷的支撐點(diǎn)選擇［J］.南京大學(xué)學(xué)報(bào)（自然科學(xué)），2017，53（3）：483-496.

［2］NAVARRO G. Analyzing metric space indexes： What for？［C］// 2nd International Workshop on Similarity Search and Applications. Prague， 2009： 3-10.

［3］VENKATESWARAN J， KAHVECI T， JERMAINE C， et al. Reference-based indexing for metric spaces with costly distance measures［J］. The VLDB Journal， 2008， 17（5）： 1231-1251.

［4］CHEN L， GAO Y J， LI X H， et al. Efficient metric indexing for similarity search［C］// 31st International Conference on Data Engineering. Seoul， 2015： 591-602.

［5］BUSTOS B， NAVARRO G， CHAVEZ E. Pivot selection techniques for proximity searching in metric spaces［J］. Pattern Recognition Letters， 2003， 24（14）： 2357-2366.

［6］ZHU Y F， CHEN L， GAO Y J， et al. Pivot selection algorithms in metric spaces： a survey and experimental study［J］. The VLDB Journal， 2022， 31（1）： 1-25.

［7］JETPJPATTANAPONG D， SRIJUNTONGSIRI G. A new pivot selection algorithm for symmetric indefinite factorization arising in quadratic programming with block constraint matrices［J］. Chiang Mai Journal of Science， 2018， 45（2）： 1181-1193.

［8］BERMAN A， SHAPIRO L G. Selecting good keys for triangle-inequality-based pruning algorithms［C］// IEEE International Workshop on Content-Based Access of Image and Video Database.Bombay， 1998： 12-19.

［9］YANG K Y， DING X， ZHANG Y L， et al. Distributed similarity queries in metric spaces［J］. Data Science and Engineering， 2019， 4（2）： 93-108.

［10］ MAO R， ZHANG P H， LI X L， et al. Pivot selection for metric-space indexing［J］. International Journal of Machine Learning and Cybernetics， 2016， 7（2）： 311-323.

［11］ 李興亮. 度量空間索引支撐點(diǎn)選擇問題研究［D］.合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2017.

［12］ 胡梓良. 度量空間支撐點(diǎn)選擇窮舉算法優(yōu)化及并行化研究［D］. 深圳：深圳大學(xué)， 2019.

［13］ 尚小敏，李強(qiáng)，齊永孟，等.SLIC算法的線程級(jí)并行優(yōu)化研究與實(shí)現(xiàn)［J］.青島大學(xué)學(xué)報(bào)（自然科學(xué)版），2022，35（4）：20-25+32.

［14］ MAO R， MIRANKER W L， MIRANKER D P. Pivot selection： Dimension reduction for distance-based indexing［J］. Journal of Discrete Algorithms， 2012， 13： 32-46.

Research of Parallel Optimization of Pivot Selection Algorithm

Based on Chebyshev Distance

TAO Shun-an，LI Qiang，SHANG Xiao-min，ZHOU Quan，ZHANG Cong

（College of Computer Science and Technology， Qingdao University， Qingdao 266071， China）

Abstract：

In the pivot selection algorithm for solving Chebyshev distance， how to quickly determine the strength and weakness of pivot has always been a difficult problem to solve due to the large amount of calculation. Therefore， a set of fast pivot optimization strategy with Chebyshev distance as the objective function was proposed. Through parallelized analysis， relatively independent computing tasks were found， and OpenMP was used to parallelize the selection of pivot. In order to reduce the time complexity at the algorithm level， the Chebyshev distance was converted into the Manhattan distance， which reduces the overall calculation amount. The multi-threaded method was used to reconstruct the ordering link of the objective function value as a whole， which avoids the meaningless memory fetching overhead. The experimental results show that the pivot optimization algorithm is a more obvious acceleration effect than the traditional method， and the speedup reaches 174.62， and the data dependence problem of the algorithm is solved.

Keywords：

Chebyshev distance; pivot selection; parallel computing

收稿日期：2023-03-07

基金項(xiàng)目：

山東省自然科學(xué)基金面上項(xiàng)目（批準(zhǔn)號(hào)：ZR201910310143）資助。

通信作者：

李強(qiáng)，男，博士，講師，主要研究方向高性能計(jì)算。E-mail： lq.sxt@163.com