基于CPU-GPU的B樣條曲面并行刀具路徑規劃方法

黎振東 俞武嘉 周亞軍

(杭州電子科技大學智能控制與機器人研究所 浙江 杭州 310018)

?

基于CPU-GPU的B樣條曲面并行刀具路徑規劃方法

黎振東 俞武嘉 周亞軍

(杭州電子科技大學智能控制與機器人研究所 浙江 杭州 310018)

針對傳統串行刀具路徑規劃算法效率低下和在異構硬件平臺上的不兼容問題，提出一種基于CPU-GPU異構并行計算的刀具路徑規劃方法。方法針對雙三次均勻B樣條曲面，依據等參數線刀具路徑規劃方法的原理和OpenCL規范設計并行算法，在CPU的邏輯控制下，采用數據并行的編程模型在GPU的多個工作項上并行執行內核，將傳統串行執行的等參數線法進行了并行化重構。仿真實驗結果表明，該算法在CPU-GPU異構平臺上生成刀具路徑的時間較傳統串行算法縮短1.5～11.9倍，對實現刀具路徑的實時或準實時生成具有重大意義。

B樣條曲面 OpenCL 并行計算 刀具路徑規劃

0 引 言

刀具路徑是切削刀具相對于零件輪廓的運動軌跡。目前，刀具路徑的生成方法趨向智能化,現有數控系統可以根據輸入的數控編程數據接口國際標準STEP-NC(STEP-Compliant Data Iterface for Numeric Controls)程序得到自由曲面的幾何信息，然后用等參數法生成刀具路徑[1-2]。對于新一代智能數控加工系統，它要求刀具路徑能夠在線實時或準實時生成，但是現有的串行刀具路徑生成時間較長，不能滿足要求。為了滿足要求，數控系統計算任務的并行化研究在國內外逐漸展開。

近年來，數控系統計算任務的并行化研究得到了快速發展，文獻[3]從系統角度研究了數控系統核心任務的并行處理問題，并建立了并行處理的評價模型。文獻[4]提出基于并行計算的刀具路徑生成算法，實驗結果證明了并行計算技術對于提升刀具路徑規劃算法的執行性能有相當大的作用。但是，這些并行計算都是基于操作系統多線程調度或者應用軟件層面的軟件級并行計算技術，真正的并行計算是硬件級多線程并行計算和異構系統的并行計算，它在數控領域中則還未見涉及[5]，而在圖像學、分子動力學、生物醫藥領域逐漸開展起來[6-7]。如今，隨著IT 行業的飛速發展，越來越多不同硬件體系架構的處理器和控制器應用到數控系統形成異構系統，但傳統的數控軟件的架構和計算模式無法充分發揮這些新硬件的性能，阻礙了數控加工系統的進一步發展，降低了系統的開放性與兼容性。

本文利用開放運算語言OpenCL技術，使中央處理器CPU和圖形處理器GPU不同架構的處理器能協同進行計算，CPU進行邏輯控制和串行計算，GPU的多個工作項執行相同的內核程序來并行求解出B樣條曲面的刀具路徑，實現異構系統的并行計算。實驗結果表明，該并行算法在CPU-GPU異構平臺上生成刀具路徑的時間較傳統串行算法明顯縮短，使刀具路徑生成能滿足準實時要求。OpenCL是一個開放的、面向異構系統的并行計算標準，能充分發揮不同新硬件的性能，使并行算法具有更好的平臺開放性和兼容性。

1 基本原理

1.1 雙三次B樣條曲面方程

給定(m+1)×(n+1)個控制頂點dij(i=0,1,…,m;j=0,1,…,n)的陣列，構成一張控制網格，給定參數u與v的次數分別為k與l，以及兩個節點矢量為:U={u0,u1,…,um+k+1},V={v0,v1,…,vn+l+1}。則定義一張k×l次張量積B樣條曲面，其方程為：

uk≤u≤um+1vl≤v≤vn+1

(1)

對于雙三次均勻B樣條曲面取k=l=3，它是由節點矢量U和V和16個控制頂點決定的，其矩陣表達形式為：

P(u,v)=UMDMTVT

(2)

1.2 刀具路徑規劃方法

刀具路徑規劃方法歸納起來可分為三大類 : 截面法、投影法、參數線法。其中參數線法是將曲面的一個參數方向作為沿切削行的走刀方向，另一個參數方向作為沿切削行的進給方向，然后將加工表面沿著選定的方向在參數定義域內進行參數細分，形成多條參數線信息，最后按照一定的規則連接參數線節點構成了刀具路徑軌跡。

對于B樣條曲面，由式(2)可認為它是由一系列u值不變和v值不變的B樣條曲線構成的網格曲面，因此對于B樣條曲面的求解，可分解為由節點矢量的每個u值和v值對應的B樣條曲線所組成的網格點的求解，與等參數線法刀具路徑規劃方法相吻合。因此對于雙三次均勻B樣條曲面刀具則可以選擇沿著曲面的參數(u或者v)作為沿切削行的方向，(v或者u)方向作為沿切削行的走刀方向，利用等參數線法生成刀具路徑。在對參數u、v進行細分后，可以得到一系列的等u或者等v參數線。由于每條等u參數線或者等v參數線的之間不相關，則每條等u參數線或者等v參數線上對應于v參數或者u參數細分的一系列坐標值，即參數線網格點的坐標信息可以通過并行計算得到。本文取u方向作為沿切削行的進給方向，v方向作為沿切削行的走刀方向，采用等參數線法進行刀具路徑規劃。

1.3 CPU-GPU異構系統

在CPU-GPU異構系統中，CPU是多指令單數據流的體系結構，數據處理基本是單流水線的，更擅長的是做邏輯控制，而GPU是典型的單指令多數據的體系結構，它擅長數據計算。異構系統的體系結構如圖1所示，從圖中可以看出，CPU和GPU通過外部總線互連，各自擁有獨自的存儲空間，分別是主存和顯存。程序在CPU-GPU異構系統中的執行過程大致可以分為三步：首先，將輸入數據從CPU端主存拷貝至GPU端顯存；接著，調用GPU執行；最后，將計算結果從GPU 端顯存拷回到CPU端主存。其中在GPU上含有大量的計算單元，并且每個計算單元可以更進一步劃分為一個或者多個處理單元，而計算最終都是在處理單元中完成，因此可以將程序中計算量大且可并行化執行的部分映射到GPU的多個處理單元上并行執行實現并行計算。

圖1 CPU-GPU異構體系結構示意圖

2 CPU-GPU平臺上并行刀具路徑規劃算法的設計與實現

2.1 并行刀具路徑規劃算法的設計

對于并行程序設計，高度抽象或者模型是它的關鍵，模型可分為任務并行和數據并行。其中任務并行模型，CPU可以通過劃分時間片來進行多線程切換方式設計，優勢較GPU大；由于計算設備是GPU，因此在程序設計時采用數據并行編程模型在GPU上執行，即同一指令對多個數據元素進行操作。

根據B樣條曲面的矩陣表示形式(2)，將所有的u細分值組成的行向量U合并用一個大型矩陣表示，同理所有v細分值組成的列向量VT也用一個大型矩陣表示，其中每個細分值對應于一條參數線，再者系數矩陣為M、控制頂點用矩陣D表示，因此對于B樣條曲面等參數路徑生成抽象為簡單的矩陣相乘，因此并行程序的核心就是矩陣乘法。由于參數u與v不相關，彼此沒有依懶性，則可以利用分配好的工作組和工作項，每個工作項執行相同的矩陣乘法內核函數并行地求出B樣條曲面參數線網格點信息，其中工作組和工作組在硬件上對應GPU的計算單元和處理單元。

2.2 OpenCL實現并行刀具路徑規劃算法

OpenCL作為一種新的并行計算技術,它可以調用計算機內全部計算資源，包括CPU、GPU和其它處理器。在OpenCL的執行模型中，程序分為兩部分來執行，分別是主程序和內核程序，其中主程序運行在宿主機上， 內核程序運行在OpenCL設備(計算設備)上，并且主程序管理著內核程序的運行。由于CPU擅長邏輯控制，而GPU擁有大量的計算核心和強大的線程調度機制，擅長執行并行度很高的大型應用程序，因此本文宿主機選為CPU，OpenCL設備選為GPU。但是對于并行化程度不高或計算量較小的程序，如果移植到GPU上執行，由于無法隱藏多個線程存取數據的開銷，以及PCI-E總線的數據傳輸延遲，反而會帶來額外通信開銷致使程序性能下降，因此對于式(2)中，系數矩陣與控制頂點矩陣相乘的計算量較小，安排在CPU上執行，而與參數矩陣的乘法運算時，參數u與v之間不相關，沒有依懶性，可并行進行計算，并且計算量較大，將它放在GPU上執行。

內核程序為矩陣乘法，程序將參加計算的矩陣元素按照明確的索引代數將一對索引映射到一個索引，從而可以將矩陣轉化為一維數組，因此矩陣相乘進一步轉化為一維數組的運算。

主程序同理將由u、v細分值構成的參數矩陣U、V中的元素，按照明確的索引關系轉化為一維數組U[i]、V[i]，存儲在CPU端存儲器中，其中參數矩陣中每個u、v的細分值對應一條參數線；然后將在CPU端存儲器中的U[i]、V[i]數組拷入已開辟好空間的OpenCL內存對象緩沖區中，該緩沖區上下文相對應，并且對與上下文關聯的設備(GPU)是全局可見的，同時將該緩沖區設置為可并行訪問的存儲體，這樣可以減少不同線程之間訪問沖突或阻塞，從而降低數據傳輸通信開銷；接著從緩沖區讀取數據提供給內核在GPU上執行，多個工作項并行執行相同內核后，得到的結果為所有參數線的信息，其中每個工作項計算出的結果對應矩陣中的一行元素即一條參數線的坐標信息；最后將最終計算結果同樣寫入全局的結果緩沖區，然后將結果緩沖區的數據通過特定函數映射到主機內存提供給其他部分程序使用。

利用OpenCL規范設計主程序和內核的步驟：

1) 按照矩陣乘法邏輯關系編寫內核函數KERNEL(_kernel void Matrixmultipli ())；

2) 調用clGetPlatformIDs()發現計算機系統中OpenCL平臺集合；

3) 通過clCreateContextFromType()建立上下文，用于計算設備與內存對象以及命令隊列之間的通信；

4) 由clCreateProgramWithSource()創建與上下文關聯的程序對象，便于程序關聯的設備編譯內核，利用clBuildProgram()為指定的設備構建程序對象；

5) 由CreateKernel()創建在設備上并行執行的內核，內核為__kernel void Matrixmultipli ()；

6) 由clCreateCommandQueue()創建命令隊列，提交到命令隊列中的命令完成OpenCL的具體操作，這里操作是矩陣乘法；

7) 調用clCreateBuffer()創建緩沖區，方便進行數據的讀寫，通過clSetKernelArg()將內核參數和緩沖區都傳遞到內核，為內核計算做好準備；

8) 調用clEnqueueWriteBuffer()將要參與計算的數據信息寫入緩沖區,這里是u、v細分后的一維數組；

9) 由clEnqueueNDRangeKernel()函數將內核事件加入命令隊列，準備在GPU上執行，該函數的參數設定工作組和工作項的大小，即設定計算單元和處理單元的大小進行并行計算；

10) 由于緩沖區的數據，宿主機不能直接使用，須調用clEnqueueMapBuffer()和memcpy()函數將緩沖區的數據映射到宿主機，提供給CPU使用。

按上述步驟設計好程序并在GPU上執行完畢后，CPU得到所有參數線網格點的坐標信息，接著按規定的走刀方向和進出方向通過Matlab仿真出刀具路徑。

3 仿真結果及分析

加速比是用來衡量程序并行化的性能和效果的一類標準，它通常定義為串行程序執行時間與并行程序執行時間的比值：

(3)

本文測試環境的顯卡使用AMD Radeon(TM) R9 200 series GPU，顯存2 048 MB，內存2 GB，CPU 使用AMD Athlon(TM)3.7 GHz。為模擬不同計算規模下的程序表現,以不同的采樣密度分組對示例曲面進行加工域位置采樣，即通過不同的u、v細分數，對曲面刀具路徑生成時間進行統計，為減小系統中其他應用程序對算法程序運行結果帶來干擾，結合式(3)采取重復三次操作取算術平方值的方法作為實驗取值，數值結果保留小數點后一位，實驗結果如表1所示。由表1數據，將u、v細分數以1 000×1 000作為基，串行程序執行時間與并行程序執行時間對比如圖2所示。

表1 不同執行方式的程序執行時間

圖2 并行算法與串行算法執行時間對比結果

由實驗結果可知，異構平臺下并行程序的執行效率較傳統串行算法明顯提高。通過對加速比和執行時間對比圖分析可得，當點數較少時后，加速效果不是很明顯，當點數繼續增大后，并行計算的優勢逐漸體現。因為參數u、v值細分后，隨著點數的增加，串行程序循環執行的次數增多，花費時間增加快，而并行執行調整工作項的大小，計算單元增加，執行時間增長率遲緩，加速比隨之增大；再者CPU是多指令單數據流體系結構，數據處理基本是單流水線的，循環操作耗時多，而GPU是典型的單指令多數據體系結構，單個指令可同時操作多個數據，耗時較少；最后，當點數較少時，CPU與GPU計算所需的線程數差不多，但GPU線程切換開銷很小，所以時間較短。隨著點數繼續增加，CPU每個核心支持1～2個線程，須通過時間片輪轉的方式來進行多個線程的切換執行串行計算。但是線程之間切換須上百個時鐘周期的時間，而GPU有成千上百個內核，可以同時多個線程同時并行計算，且線程切換開銷很小，因此時間明顯縮短，執行時間的增長率小，加速效果明顯上升。說明CPU-GPU異構并行程序的執行效率明顯提高,可以縮短刀具路徑的生成時間。

利用Matlab繪制出雙三次均勻B樣條曲面實例圖和通過并行計算出的參數u、v不同細分數20×20、40×40、100×100均勻采樣的刀具路徑仿真如圖3-圖5所示。

圖3 B樣條實例曲面圖

圖4 20×20均勻采樣

圖5 40×40均勻采樣

圖6 100×100均勻采樣

4 結 語

本文根據B樣條曲面特性，利用OpenCL技術建立一種基于CPU-GPU的異構并行計算的刀具路徑規劃方法。通過實驗結果分析，本文并行等參數線規劃方法較傳統串行等參數線規劃方法具有更高的效率，并且實現了不同架構處理器的協同并行計算。后續可以根據OpenCL規范對算法進一步優化，進一步提高程序并行度，充分發揮GPU的強大并行計算能力和OpenCL在數控領域的應用優勢，為不同硬件平臺的數控系統提供一致的并行計算模式，促進新一代數控系統標準化。

[1] 富宏亞，胡泊，韓德東．STEP-NC數控技術研究進展[J]．計算機集成制造系統, 2014, 20(3): 569-577.

[2] 王海瀛．STEP-NC 程序生成器及其關鍵技術研究[D]．哈爾濱：哈爾濱工業大學,2014:3-18.

[3] 魏勝利，戴國強． 一種開放式并行數控系統研究[J]．組合機床與自動化加工技術,2013,7(1):65-67.

[4] 余湛悅, 周儒榮, 莊海軍,等．一種數控加工刀軌生成的并行算法[J]．機械科學與技術, 2004,23(3): 266-268.

[5] 俞武嘉．基于 STEP-NC 的五軸加工刀具路徑規劃方法研究[D]．杭州：浙江大學, 2007:95-100.

[6] 邊毅, 袁方, 郭俊霞,等．面向 CPU+GPU 異構計算的多目標測試用例優先排序[J]. 軟件學報,2016,27(4): 943-953.

[7] Munshi A, Gaster B R, Mattson T G. OpenCL Programming Guide[M]．New York :Pearson Education, 2011:76-89.

[8] 歐陽華兵．基于STEP-NC的銑削加工智能化工藝規劃系統及其實現[J]．機床與液壓, 2015,43(16): 22-34.

[9] 范興山．基于異構計算的矩陣廣義逆算法研究及實現[D]．成都：電子科技大學,2014.

[10] 劉文志，陳軼，吳長江．OpenCL異構并行計算：原理、機制與優化實踐[M]．北京:機械工業出版社,2016．

B-SPLINE SURFACES’ PARALLEL TOOL PATH PLANNING METHOD BASED ON CPU-GPU

Li Zhendong Yu Wujia Zhou Yajun

(InstituteofIntelligentControlandRobotics,HangzhouDianziUniversity,Hangzhou310018,Zhejiang,China)

Aiming at the inefficiency of legacy serial tool path algorithms and incompatibility issues on heterogeneous hardware platforms, a tool path planning method based on CPU-GPU heterogeneous parallel computing is proposed. The method contraposes bi-cubic B-spline surface which is abstracted as a matrix multiplication on the principle of isoparametric line tool path planning method, and then designs parallel algorithm in accordance with OpenCL specification. Adopting data parallel programming model, it executes multiple work- items of the GPU on the core under control of the CPU logic, and reconstructs the isoparametric method as parallel execution instead of traditional serial execution. Obviously, simulation results show that this algorithm takes less time to generate tool paths on the CPU-GPU heterogeneous platforms, reduced by 1.5 to 11.9 times compared with traditional serial algorithm and it is of great significance to the tool path planning’s real-time or near real-time generation.

B-spline surfaces OpenCL Parallel computing Tool path planning

2016-07-27。國家自然科學基金項目(51405119)。黎振東，碩士生，主研領域：并行計算，刀具軌跡規劃。俞武嘉，副教授。周亞軍，教授。

TP391.75

A

10.3969/j.issn.1000-386x.2017.07.005