金屬增材制造負載均衡異構并行切片算法

李慧賢 馬創新 王 碩 馬 良

1.西北工業大學計算機學院，西安，7100722.西北工業大學軟件學院，西安，7100723.西北工業大學凝固技術國家重點實驗室，西安，710072

0 引言

金屬增材制造(metal additive manufacturing)技術作為一種新興制造技術，相比傳統制造工藝，其成本低、材料利用率高，被廣泛應用于航空航天、儀器儀表等領域[1-2]。切片算法是增材制造數據處理過程中非常重要的一步，對于一個3D模型，首先要做的便是將三維模型分成一系列二維平面，得到切片輪廓后便可將三維加工轉為二維加工。

現在金屬增材制造的發展日新月異，隨著打印規模的增大和精度要求的提高，切片算法的數據量也越來越大。目前大多數切片軟件都采用串行切片算法，研究如何提高切片算法的效率是很有必要的。增材制造領域的分層切片算法主要分為以下三類：基于面片拓撲關系的分層切片算法[3-5]、基于模型幾何特征的分層切片算法[6]、基于幾何連續性的分層切片算法[7]。在并行化切片算法研究方向有很多報道。馬旭龍等[8]提出了基于共享存儲并行編程(open multi-processing，OpenMP)的快速并行分層算法，利用CPU多核心建立數據并行模式。馬旭龍等[9]提出了基于流水線的并行分層算法，進一步提高并行效率，可獲得接近CPU核數的加速比。然而CPU更擅長邏輯運算而非數值計算，且CPU核數有限，限制了并行效率的提高。現在基于 GPU并行計算的研究范圍越來越大，各個通用計算領域都開始嘗試使用統一計算設備架構(compute unified device architecture，CUDA)進行GPU加速[10-13]。在增材制造技術方面，ZHANG 等[14]、王碩[15]利用CUDA將傳統切片算法并行化實現，切片效率提高明顯，而且數據量越大該算法越具優勢。但是該算法邏輯判斷較多，且未考慮負載均衡，限制了GPU性能。本文提出了在金屬增材制造中基于模擬退火的負載均衡異構并行化算法，并行處理STL模型切片時的求交問題，以提高后續求取輪廓線的效率。

1 并行化異構切片算法

1.1 數據結構的構建

為了更好地將切片算法并行化，本文在基于面片間拓撲關系的半邊數據結構的基礎上提出了一種改進的數據結構模型。半邊數據結構如圖1所示。

圖1 半邊數據結構Fig.1 Half-edge data structure

根據格式(ASCII碼/二進制)讀取STL文件，在得到該零件模型所有三角面片的同時，也得到該模型的最低點。然后遍歷所有三角面片，利用面片間的拓撲關系建立數據結構。首先遍歷所有三角面片的每個頂點，對每個點的坐標值用哈希函數計算哈希值，然后比對哈希表中是否有該點，若有則使用哈希表中的索引，否則存入哈希表并使用哈希表中的索引代替該點。這樣既可以去除相鄰三角面片之間重復記錄的共用頂點，也可以利用這些三角面片間的共用頂點將相鄰的三角面片聯系起來形成拓撲關系，從而構建基于拓撲關系的數據結構。該零件模型可用點集和面片集合來表示，點集存儲模型中出現的所有點，面片集合中每個面片的頂點則由點集中的索引代替。

在建立該數據結構的同時，為了利于后續并行化切片的流程，記錄每個三角面片在Z軸的最低點Zmin及最高點Zmax，并根據開始記錄的零件模型最低點以及切片層高δthickness，計算得知該三角面片會被哪些層高的切平面切到，以便在并行化切片前統計任務量并分配任務。

1.2 數據預處理

三角面片通常會與多個切平面相交(圖2)，數據結構構建完成后，遍歷其面片集合，根據上一步計算結果將三角面片加入所有相交切平面的求交三角面片集合中。

圖2 三角面片的多個相交切平面Fig.2 Multiple intersecting tangent planes oftriangular patches

為了減少數據在內存和GPU間的頻繁交換，CUDA平臺采取了一次復制進、一次復制出的策略，當某些線程任務量差距巨大時，先完成計算的線程需要等待未完成的線程，整個任務的運算時間取決于運算時間最長的線程。所以在并行計算問題中，對任務量的負載均衡是提高算法效率的關鍵，也是研究的重點。本算法根據線程數分配給每個線程盡量相等的任務量，以減少線程等待時間。該問題可以類似為一個裝箱問題，盡可能提高裝箱填充率，便能使各線程工作量更加均衡。

本文提出的并行化切片算法首先根據任務量和硬件設備確定所需要開辟的線程數N，并根據所有切平面求交集合的累加和得到總任務量P及每個線程的理想任務量Pthread:

Pthread=P/N

(1)

即每個箱子的容量。每個切片層求交集合的長度即為需要裝入箱子的物體的長度，這是一個單維裝箱問題。裝箱問題通常帶有大量的局部極值點，很難得到最優解，反而會在循環過程中陷入局部最優解，模擬退火算法是求解這類問題的通用方法。

該問題與傳統裝箱問題的區別在于可以對每個切片層求交集合進行分割，若某個切片層求交集合過大，則可以切分給多個線程進行運算，但是這種操作會增加運算負擔，應盡量避免。如果第i個切片層求交集合的長度Player[i]大于(1+5%)Pthread時，則對該層任務量進行分割，Player[i]的任務量分割成Pthread的整數倍后剩余的部分則是需要裝箱的部分。算法1具體流程如下。

Algorithm 1任務分割算法Definition1 Pthread=理想的每個線程所需分配任務量;2 PlayerSize=每層任務量3 Pdone=無需重新組合的分割結果集合4 Predo=需要重新組合的分割結果集合5 Mdone=對Pdone的每一項標記,表明其來自哪個切平面的集合6 Mredo=對Predo的每一項標記,表明其來自哪個切平面的集合7 Layers[i] = =每層面片集合8 i=09 Repeat i++10 If PlayerSize[i]>(1.05Pthread); 11 j=0;12 Repeat13 (Layers[i][j],Layers[i][j+Pthread-1])部分集合賦值Ltemp;14 Pdone.push_back(Ltemp);15 Mdone.push_back(Mark(i,Ltemp.size())); 16 j+=Pthread17 until j>PlayerSize[i]18 (Layers[i][j-Pthread],Layers[i][PlayerSize[i]-1])部分集合賦值Ltemp;19 Predo.push_back(Ltemp):20 Mredo.push_back(Mark(i,Ltemp.size()));21 Else if PlayerSize[i]<(0.95Pthread);22 Predo.push_back(Layers[i])23 Mredo.push_back(Mark(i,Ltemp.size()))24 Else25 Pdone.push_back(Layers[i])26 Mdone.push_back(Mark(i,Ltemp.size()))27 until i=PlayerSize.size()28 EndAlgorithm 1

1.3 基于模擬退火的負載均衡算法

模擬退火算法的實質是根據Metropolis準則[16]用概率P來接受更差的結果， 即

(2)

其中，E(·)為評估函數，xnew為新解，xold為原解。P隨著溫度的下降而下降，最后趨于穩定，得到一個近似最優解。本文的問題和原有裝箱問題有所區別，箱子的長度可以在(1±5%)Pthread之間浮動，以盡量減少運算負擔。在得到需要分配給各個線程的切片層求交三角面片集合長度的集合Predo之后，便可以利用下述算法將Predo重新分配，使每個線程的任務量接近(1±5%)Pthread。

首先利用貪心算法[17]中的首次適應法進行第一次裝箱，得到初始解。然后隨機交換物體的排列順序，再次使用貪心算法放入得到新解，得到新解后，計算利用率和原解比較，若更好則接受新解，若更差則以一定概率P來接受較差解。循環重復此過程，每次循環溫度降低，直到溫度為0，狀態趨于穩定。算法2具體流程如下。

Algorithm 2負載均衡算法Definition1 Predo=需要重新組合的分割結果集合;2 Ptemp=臨時保存集合;3 Mredo=保存的Predo中每一項所處切平面的標記集合;4 Mtemp=臨時保存標記集合;5 S=當前解6 S'=新解7 T=初始溫度;8 r=退火速度;9 Tmin=最低溫度;10 times=迭代次數;11 FF(vector>P,vectorM,int Pthread) ∥首次適應函數12 change(vector>P,vectorM,int swapT) ∥交換函數13 Eva(S) ∥評估函數14 S=FF(Predo,Mredo, Pthread)15 Ptemp←Predo16 Mtemp←Mredo17 Repeat18 IfEva(S)>0.95&&Eva(S)<1.05;19 EndAlgorithm 2;20 j=021 Repeat j++22 change(Ptemp, Mtemp,swapT);23 S'=FF(Ptemp, Mtemp,Pthread);24 Δt=Eva(S')-Eva(S);25 IfΔt≤026 S=S'27 Predo←Ptemp28 Mredo←Mtemp29 Else30 Ifexp(-Δt/T)>random(0.0, 1.0)31 S=S'32 Predo←Ptemp33 Mredo←Mtemp34 until j=times35 T=rT;36 until T≤Tmin37 EndAlgorithm 2

1.4 CUDA并行化切片

使用自適應負載均衡算法得到每個線程所需計算的任務集合后，將任務集合利用CUDA傳入GPU中進行并行化求交運算。前一過程求得的任務集合包含了每個線程所要計算的一個或多個求交三角面片集合以及每個求交三角面片集合的標記。求交三角面片集合的標記包括其切平面高度以及該切平面高度需要進行求交計算的次數。根據任務集合，將每一項中的面片集合及標記集合轉換為一維數組，并按照此計算結果提前申請結果數組，用來保存計算結果，同時將保存的標記中記錄的切平面高度賦值給每一項切片結果的Z值。傳入GPU后，各個線程得到自己的存儲位置下標，計算完成得到結果后依次存儲，待所有線程都計算完成后將結果傳回CPU。該部分算法在CUDA中運行的各線程內核函數如算法3所示。

Algorithm 3CUDA內核函數Deition1 i=線程索引;2 k=當前存儲位置3 layersSize=切平面集合的個數4 Result=結果數組5 Index=索引數組6 i=threadIdx.x+blockIdx.x×blockDim.x7 If i≥layerSize; 8 EndAlgorithm 3;9 k=Index[i]10Repeat11 Result[k]=S[k]與Result[k].z的求交結果;12 k++ ;13until k=Index[i+1]14EndAlgorithm 3

由算法3可見，各線程的運算量和邏輯判斷大大減少，所有線程計算完成后將計算結果傳回主機端，再按照集合中保存的標記信息將計算結果恢復為按切平面高度存儲的計算結果集合。得到每一層切平面與該層相交的所有三角面片的相交線段的計算結果后，即可按照每層與切平面相交的三角面片間的拓撲關系，快速尋找各個相交線段的相鄰線段，從而連接成切片輪廓。至此本文研究的自適應負載均衡異構并行切片算法全部完成。

2 實驗結果

2.1 實驗數據與環境

實驗環境：操作系統Win10 64位，處理器Intel Core i7-8750H，內存16G，顯卡NVIDIA GTX 1050 Ti with Max-Q Design，CUDA版本8.0，編程平臺Visual Studio 2015。本次實驗所用的STL文件來源于網絡，文件大小100～750MB。

2.2 實驗內容

2.2.1模擬退火算法參數實驗

模擬退火算法的運算效率和準確性由初始溫度、退火速度等參數決定，為得到最適合的參數，首先對該自適應負載均衡算法中的這兩組參數進行對比實驗。修改參數值，將各個模型使用1.2節所述的數據預處理算法處理后得到其Predo集合，記錄填充率、耗時及迭代次數等，其中參數初始溫度T的對比實驗結果見表1，該實驗中退火速度r設為固定值0.9。退火速度r的對比實驗結果見表2，該實驗初始溫度T設為固定值200。

由上述對比實驗可以得出，退火速度和初始溫度的改變會對算法用時產生比較大的影響。當模型數據非常巨大時，所要處理的計算量很大，對任務分配的優化很有意義，可以犧牲自適應負載均衡算法的運算時間來提高切片過程的運行效率，所以應該升高初始溫度，降低退火速度，使得算法更大概率地計算出近似最優解；當模型數據量較小時，可適當降低初始溫度，提高退火速度。

表1 模擬退火算法處理不同模型時初始溫度的對比

表2 模擬退火算法處理不同模型時退火速度的對比

2.2.2算法對比實驗

本節對比實驗中所要對比的算法有以下4種：①基于面片間拓撲關系的串行算法；②基于CUDA的普通切片算法；③基于拓撲關系的GPU并行切片算法；④自適應負載均衡異構切片算法。首先對其求交過程進行對比測試，實驗結果見表3。由表3可以看出，本文算法在單純的求交運算方面由于傳入數據含有多個變量且數據結構較為復雜，計算速度慢于算法②，因為算法②單純計算求交結果，不含拓撲結構；在處理模型1、2、4時，算法④所耗時間短于算法③，是因為模型1、2、4結構較為復雜，算法③中沒有對這些模型進行優化，而算法④縮短了線程等待時間，加快了切片速度。

表3 不同切片算法對不同模型的求交過程耗時對比

對4種算法的整體分層切片過程進行測試，耗時對比如圖3所示?？梢钥闯?，各算法耗時隨模型體積增加都呈線性遞增趨勢。普通并行切片算法耗時最多，這是由于輪廓形成過程需要進行大量的數組遍歷操作。三角面片間的拓撲關系有利于快速尋找各個相交線段的相鄰線段，從而連接成切片輪廓，因此，基于面片間拓撲關系的串行算法效率提升較大。

圖3 不同切片算法處理不同模型耗時對比Fig.3 Time consuming comparison of different slicingalgorithms for different models

算法③和算法④將求交部分并行化，相比算法①，加速比達到3左右。對比算法③，在處理不規則模型(圖4a)時，由于模型曲率變化明顯，不同切片層間的運算量差異很大，算法④效果較好，它會消耗少量的時間來換取后面切片時不同進程間的負載均衡，在CUDA中并行求交的過程效率可再提高20%～30%。圖4b所示是采用本文算法獲得的切片結果，本文算法能正確地利用STL模型進行分層切片。

3 結 論

(a)霸王龍STL模型

(b)霸王龍切片數據圖4 模型切片實例Fig.4 Model slice example

本文提出了自適應負載均衡異構切片算法，采用模擬退火算法來解決任務重組問題，將并行計算時所有線程的任務總量盡量平均分配給每個線程，使得每個線程所需計算的任務量差距在可接受范圍內，避免線程等待等問題。在對不規則模型數據分層切片時可以得到較好的加速比，且實驗模型體積越大，算法的加速比越明顯。