陶順安 李強 尚小敏 周全 張璁

摘要：

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

關鍵詞：

切比雪夫距離；支撐點選擇；并行計算

中圖分類號：

TP338.6

文獻標志碼：A

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

1 基于切比雪夫距離的支撐點選擇算法分析

1.1 算法設計

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

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

支撐點優(yōu)選以目標函數(shù)值為標準，可以評估所有支撐點組合的優(yōu)劣。

1.2 支撐點優(yōu)選算法結構

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

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

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

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

2.1 OpenMP并行優(yōu)化

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

2.2 SumDistance優(yōu)化

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

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

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

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）

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

2.3 Sort優(yōu)化

對于串行算法，每得到一個目標函數(shù)值，就對其進行冒泡排序，以得到對應支撐點組合的排序位置。由于總共有C（n，k）種支撐點組合，獲得C（n，k）個目標函數(shù)值，因此需要C（n，k）次冒泡排序，時間復雜度為O（n2）。因為每次冒泡排序并不能確定目標函數(shù)值的最終位置，所以出現(xiàn)反復冒泡交換產(chǎn)生的無意義訪存開銷，效率太低。

對于Sort部分，本文使用一個數(shù)組把每種支撐點組合所得到的目標函數(shù)值存儲起來，待所有支撐點組合遍歷結束，數(shù)組中將存儲所有的目標函數(shù)值，然后對這些目標函數(shù)值快速排序。

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

3 實驗環(huán)境與結果

3.1 實驗環(huán)境設置

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

3.2 消融研究

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

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

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

4 結論

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

參考文獻

［1］李興亮，毛睿.基于近期最遠遍歷的支撐點選擇［J］.南京大學學報（自然科學），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］ 李興亮. 度量空間索引支撐點選擇問題研究［D］.合肥：中國科學技術大學，2017.

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

［13］ 尚小敏，李強，齊永孟，等.SLIC算法的線程級并行優(yōu)化研究與實現(xiàn)［J］.青島大學學報（自然科學版），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

基金項目：

山東省自然科學基金面上項目（批準號：ZR201910310143）資助。

通信作者：

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