基于切比雪夫距離的支撐點選擇算法的并行優化研究

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

摘要：

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

關鍵詞：

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

中圖分類號：

TP338.6

文獻標志碼：A

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

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

1.1 算法設計

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

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

支撐點優選以目標函數值為標準，可以評估所有支撐點組合的優劣。

1.2 支撐點優選算法結構

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

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

2 算法的優化處理

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

2.1 OpenMP并行優化

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

2.2 SumDistance優化

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

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

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

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|即為曼哈頓距離，對所有點的曼哈頓距離優化求和即為原坐標系的切比雪夫距離之和。由于對所有點進行快速排序的時間復雜度為O（nlog n），故求切比雪夫距離和的時間復雜度由O（n2）優化到O（nlog n）。

2.3 Sort優化

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

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

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

3 實驗環境與結果

3.1 實驗環境設置

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

3.2 消融研究

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

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

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

4 結論

本文主要調整了支撐點優選算法的SumDistance和Sort部分結構，使時間復雜度從O（n2）降低到O（nlog n）。針對算法中的主要瓶頸Combination等進行了線程級并行優化，使算法得到了較大的加速。接下來將在超級計算機上進行上百節點的測試，并使用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］ 胡梓良. 度量空間支撐點選擇窮舉算法優化及并行化研究［D］. 深圳：深圳大學， 2019.

［13］ 尚小敏，李強，齊永孟，等.SLIC算法的線程級并行優化研究與實現［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