黎振東 俞武嘉 周亞軍

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

?

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

黎振東 俞武嘉 周亞軍

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

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

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

0 引 言

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

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

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

1 基本原理

1.1 雙三次B樣條曲面方程

給定(m+1)×(n+1)個控制頂點dij(i=0,1,…,m;j=0,1,…,n)的陣列，構(gòu)成一張控制網(wǎng)格，給定參數(shù)u與v的次數(shù)分別為k與l，以及兩個節(jié)點矢量為: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，它是由節(jié)點矢量U和V和16個控制頂點決定的，其矩陣表達(dá)形式為：

P(u,v)=UMDMTVT

(2)

1.2 刀具路徑規(guī)劃方法

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

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

1.3 CPU-GPU異構(gòu)系統(tǒng)

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

圖1 CPU-GPU異構(gòu)體系結(jié)構(gòu)示意圖

2 CPU-GPU平臺上并行刀具路徑規(guī)劃算法的設(shè)計與實現(xiàn)

2.1 并行刀具路徑規(guī)劃算法的設(shè)計

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

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

2.2 OpenCL實現(xiàn)并行刀具路徑規(guī)劃算法

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

內(nèi)核程序為矩陣乘法，程序?qū)⒓佑嬎愕木仃囋匕凑彰鞔_的索引代數(shù)將一對索引映射到一個索引，從而可以將矩陣轉(zhuǎn)化為一維數(shù)組，因此矩陣相乘進一步轉(zhuǎn)化為一維數(shù)組的運算。

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

利用OpenCL規(guī)范設(shè)計主程序和內(nèi)核的步驟：

1) 按照矩陣乘法邏輯關(guān)系編寫內(nèi)核函數(shù)KERNEL(_kernel void Matrixmultipli ())；

2) 調(diào)用clGetPlatformIDs()發(fā)現(xiàn)計算機系統(tǒng)中OpenCL平臺集合；

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

4) 由clCreateProgramWithSource()創(chuàng)建與上下文關(guān)聯(lián)的程序?qū)ο螅阌诔绦蜿P(guān)聯(lián)的設(shè)備編譯內(nèi)核，利用clBuildProgram()為指定的設(shè)備構(gòu)建程序?qū)ο螅?/p>

5) 由CreateKernel()創(chuàng)建在設(shè)備上并行執(zhí)行的內(nèi)核，內(nèi)核為__kernel void Matrixmultipli ()；

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

7) 調(diào)用clCreateBuffer()創(chuàng)建緩沖區(qū)，方便進行數(shù)據(jù)的讀寫，通過clSetKernelArg()將內(nèi)核參數(shù)和緩沖區(qū)都傳遞到內(nèi)核，為內(nèi)核計算做好準(zhǔn)備；

8) 調(diào)用clEnqueueWriteBuffer()將要參與計算的數(shù)據(jù)信息寫入緩沖區(qū),這里是u、v細(xì)分后的一維數(shù)組；

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

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

按上述步驟設(shè)計好程序并在GPU上執(zhí)行完畢后，CPU得到所有參數(shù)線網(wǎng)格點的坐標(biāo)信息，接著按規(guī)定的走刀方向和進出方向通過Matlab仿真出刀具路徑。

3 仿真結(jié)果及分析

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

(3)

本文測試環(huán)境的顯卡使用AMD Radeon(TM) R9 200 series GPU，顯存2 048 MB，內(nèi)存2 GB，CPU 使用AMD Athlon(TM)3.7 GHz。為模擬不同計算規(guī)模下的程序表現(xiàn),以不同的采樣密度分組對示例曲面進行加工域位置采樣，即通過不同的u、v細(xì)分?jǐn)?shù)，對曲面刀具路徑生成時間進行統(tǒng)計，為減小系統(tǒng)中其他應(yīng)用程序?qū)λ惴ǔ绦蜻\行結(jié)果帶來干擾，結(jié)合式(3)采取重復(fù)三次操作取算術(shù)平方值的方法作為實驗取值，數(shù)值結(jié)果保留小數(shù)點后一位，實驗結(jié)果如表1所示。由表1數(shù)據(jù)，將u、v細(xì)分?jǐn)?shù)以1 000×1 000作為基，串行程序執(zhí)行時間與并行程序執(zhí)行時間對比如圖2所示。

表1 不同執(zhí)行方式的程序執(zhí)行時間

圖2 并行算法與串行算法執(zhí)行時間對比結(jié)果

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

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

圖3 B樣條實例曲面圖

圖4 20×20均勻采樣

圖5 40×40均勻采樣

圖6 100×100均勻采樣

4 結(jié) 語

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

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

[2] 王海瀛．STEP-NC 程序生成器及其關(guān)鍵技術(shù)研究[D]．哈爾濱：哈爾濱工業(yè)大學(xué),2014:3-18.

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

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

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

[6] 邊毅, 袁方, 郭俊霞,等．面向 CPU+GPU 異構(gòu)計算的多目標(biāo)測試用例優(yōu)先排序[J]. 軟件學(xué)報,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的銑削加工智能化工藝規(guī)劃系統(tǒng)及其實現(xiàn)[J]．機床與液壓, 2015,43(16): 22-34.

[9] 范興山．基于異構(gòu)計算的矩陣廣義逆算法研究及實現(xiàn)[D]．成都：電子科技大學(xué),2014.

[10] 劉文志，陳軼，吳長江．OpenCL異構(gòu)并行計算：原理、機制與優(yōu)化實踐[M]．北京:機械工業(yè)出版社,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。國家自然科學(xué)基金項目(51405119)。黎振東，碩士生，主研領(lǐng)域：并行計算，刀具軌跡規(guī)劃。俞武嘉，副教授。周亞軍，教授。

TP391.75

A

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