基于CUDA的計(jì)算架構(gòu)求解集裝箱碼頭連續(xù)泊位分配問題

韋華，楊智應(yīng)

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

基于CUDA的計(jì)算架構(gòu)求解集裝箱碼頭連續(xù)泊位分配問題

韋華，楊智應(yīng)

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

具有強(qiáng)大并行計(jì)算能力的GPU成為高性能計(jì)算的重要平臺之一。基于CUDA的計(jì)算架構(gòu)，實(shí)現(xiàn)求解線性規(guī)劃問題的單純形算法。在此基礎(chǔ)上，實(shí)現(xiàn)求解整數(shù)規(guī)劃問題的分支定界法，并將它應(yīng)用于求解集裝箱碼頭連續(xù)泊位分配問題。實(shí)驗(yàn)結(jié)果表明，基于CUDA的計(jì)算架構(gòu)可大大縮短計(jì)算時(shí)間。

并行計(jì)算；GPU；CUDA；單純形算法

0 引言

并行計(jì)算已廣泛應(yīng)用于許多領(lǐng)域。海量的信息及數(shù)據(jù)蘊(yùn)藏著無法估量的價(jià)值，如何及時(shí)高效地分析處理是高性能計(jì)算所面臨的重要問題。隨著計(jì)算架構(gòu)的演進(jìn)，需求變得多樣化、復(fù)雜化，并行編程模型也隨之動態(tài)改變，應(yīng)用領(lǐng)域也不斷地延伸、擴(kuò)大[1]。從單核到多核再到眾核，從串行、單線程到并行、大規(guī)模多線程，求解問題的模式的轉(zhuǎn)換，以往的串行編程模型正在被替代。

中央處理器（Central Processing Unit,CPU）有強(qiáng)大的算術(shù)運(yùn)算單元，邏輯運(yùn)算單元和大容量的緩存。在復(fù)雜的邏輯運(yùn)算方面CPU擁有強(qiáng)大的優(yōu)勢；圖形處理器（Graphics Processing Unit,GPU）擁有巨大的浮點(diǎn)計(jì)算性能和極高的存儲器帶寬，與生俱來就擁有大規(guī)模并行的處理器核心，在計(jì)算密集型及易于并行的程序上具有明顯的優(yōu)勢。在浮點(diǎn)處理能力上GPU有強(qiáng)大的優(yōu)勢，低端的GPU能和主流的CPU相媲美，主流的GPU與同期的主流CPU就性能而言，竟能相差10倍左右。

自2006年11月NVIDIA公布了第一個(gè)基于CU?DA架構(gòu)的GPU—GeForce 8800 GTX，打破了只能執(zhí)行傳統(tǒng)圖形計(jì)算的局限，繼而使得GPU在通用計(jì)算中廣泛使用，且獲得了令人驚喜的成績。這也吸引了更多不同領(lǐng)域的學(xué)者基于CUDA進(jìn)行研發(fā)，取得了令人矚目的成績，不僅在性能上提升了多個(gè)數(shù)量級，而且就單位成本和能耗與傳統(tǒng)的CPU運(yùn)行程序相比較而言都要低好多[3]。它不僅可以獲得計(jì)算性能收益，而且可以充分利用能耗，這種基于CUDA的GPU計(jì)算將是計(jì)算機(jī)界的一大里程碑[4]。

線性規(guī)劃問題是工業(yè)生產(chǎn)和經(jīng)濟(jì)管理中常見的最優(yōu)化問題。它由一組線性約束和一個(gè)線性目標(biāo)函數(shù)構(gòu)成。需要求決策變量的值使得目標(biāo)函數(shù)最大化（最小化）。單純形算法[5]是解決線性規(guī)劃問題的經(jīng)典高效算法。它的求解過程是一個(gè)不斷迭代的過程，直到最優(yōu)解出現(xiàn)。在迭代的操作中是不斷重復(fù)換元操作，這一過程能利用并行計(jì)算以加快其速度。

求解整數(shù)規(guī)劃問題的分支定界法以單純形算法為基礎(chǔ)。當(dāng)規(guī)模很大時(shí)，整數(shù)規(guī)劃的求解是非常費(fèi)時(shí)的。本文基于CUDA的計(jì)算架構(gòu)，實(shí)現(xiàn)求解線性規(guī)劃問題的單純形算法。在此基礎(chǔ)上，實(shí)現(xiàn)求解整數(shù)規(guī)劃問題的分支定界法，并將它應(yīng)用于求解集裝箱碼頭連續(xù)泊位分配問題。實(shí)驗(yàn)結(jié)果表明，基于CUDA的計(jì)算架構(gòu)可大大縮短計(jì)算時(shí)間。

1 基于CUDA計(jì)算架構(gòu)的單純形算法的實(shí)現(xiàn)

1.1 CCUUDDAA編程模型

雖說GPU的浮點(diǎn)處理能力強(qiáng)于CPU，但是一個(gè)完整的CUDA程序，還是離不開CPU的。在CUDA編程模型中，CPU與GPU協(xié)調(diào)工作、各司其職[4]。作為主機(jī)（Host）的CPU負(fù)責(zé)將部分串行代碼完成，及內(nèi)核函數(shù)啟動前設(shè)備端所需數(shù)據(jù)的準(zhǔn)備及初始化工作；GPU作為設(shè)備端（Device）或協(xié)處理器，完成并行性的計(jì)算。具體功能如下：

（1）Host端完成的功能：啟動CUDA、分配內(nèi)存空間、顯存空間及初始化內(nèi)存數(shù)據(jù)、利用CudaMemcpy（）復(fù)制數(shù)據(jù)到顯存、調(diào)用內(nèi)核函數(shù)、將結(jié)果利用Cu?daMemcpy（）復(fù)制數(shù)據(jù)到內(nèi)存、釋放空間、退出CUDA。

（2）Device端完成的功能：讀數(shù)據(jù)到GPU片內(nèi)、處理數(shù)據(jù)、將結(jié)果寫回顯存。

1.2 基于CCUUDDAA的單純形算法實(shí)現(xiàn)

單純形算法是一個(gè)不斷進(jìn)行迭代的過程，迭代的次數(shù)與目標(biāo)函數(shù)非基本變量的系數(shù)相關(guān)。單純形算法的基本思想[6]：在與原規(guī)劃等價(jià)的松馳型中，換元操作按照選擇標(biāo)準(zhǔn)，選擇一個(gè)非基本變量作為替入變量和一個(gè)基本變量作為替出變量，重寫松弛型。然后將非基本變量設(shè)為0，求得基本變量的值，得到一個(gè)基本可行解，判斷重寫后的目標(biāo)函數(shù)中非基本變量的系數(shù)是否有正數(shù)，如有則繼續(xù)換元迭代，重復(fù)上述過程；反之，停止迭代，得到最優(yōu)解。單純形算法主要的三個(gè)操作是：找到替入變量、替出變量和重寫等式。尋找替入變量這一過程并不適宜使用并行計(jì)算，尋找替出變量，即是找到最緊約束，首先并行計(jì)算得出每個(gè)式子的約束，然后并行縮減，得出最近約束，但是可能數(shù)據(jù)在GPU中讀取寫入的時(shí)間里CPU已經(jīng)完成了相當(dāng)數(shù)量的工作。因此，這種簡單，數(shù)據(jù)量少的計(jì)算不適宜在GPU上執(zhí)行。重寫等式的數(shù)據(jù)量多且計(jì)算量大，在GPU上運(yùn)行具有明顯的優(yōu)勢，所以，本文將重寫等式[5]這一操作并行計(jì)算。在這一過程中具體的并行過程的核心代碼如下：

上述的代碼是設(shè)備端即內(nèi)核函數(shù)中重要代碼。根據(jù)替入變量和替出變量的下標(biāo)，重寫線性規(guī)劃松馳型，約束等式中的非基本變量的系數(shù)及常數(shù)相應(yīng)改變，目標(biāo)函數(shù)中的常數(shù)及非基本變量的系數(shù)也改變。CUDA的每個(gè)線程都有自己的線程號Id，通過核函數(shù)里的int tid1=blockDim.x*blockId.x+threadIdx.x和 int tid2=block?Dim.x*blockIdx.x+threadIdx.x語句，每個(gè)線程可以獲得自身的Id號，從而找到自己的任務(wù)去執(zhí)行。一個(gè)線程執(zhí)行一個(gè)任務(wù)后還要繼續(xù)執(zhí)行余下未執(zhí)行的任務(wù)，所以通過blockDim.x*gridDim.x這一遞增量，讓線程知道自己的下一個(gè)任務(wù)。遞增的步長即為線程格中正在運(yùn)行的線程數(shù)量。其中g(shù)ridDim.x、blockDim.x、threadIdx.x為內(nèi)建函數(shù)，它們代表的含義分別為網(wǎng)格中x軸上塊的數(shù)量、塊中x軸上線程數(shù)量、線程所在塊（block）中的索引號。

2 集裝箱碼頭連續(xù)泊位分配問題建模

集裝箱碼頭泊位分配問題分為離散泊位分配和連續(xù)泊位分配[8]。下面簡述連續(xù)泊位分配模型。

2.1 前提假設(shè)

連續(xù)泊位分配模型基于以下假設(shè)條件：

（1）港口的船舶數(shù)、岸線長度、時(shí)間周期、橋吊數(shù)及每條船的長度、到港時(shí)間、作業(yè)路數(shù)、作業(yè)量都是已知的；

（2）泊位岸線的水面深度滿足船的吃水深度且泊位是連續(xù)的；

（3）將船之間的安全距離算入船舶的長度，允許零距離泊位；

（4）船舶到港后，沒有合適的泊位，就等待，直到有合適的泊位，船舶只有一次靠泊機(jī)會，且在作業(yè)期間，橋吊要一直服務(wù)，直到船舶離港；

2.2 連續(xù)泊位分配模型

基于以上連續(xù)泊位分配模型的假設(shè)條件建立以下模型：

目標(biāo)函數(shù)：

TSi為船舶i開始工作的時(shí)間；BSi為船舶i開始工作的泊位；WTi為船舶i的工作時(shí)間；Li為船舶i的長度；Ti為船舶i的到港時(shí)間；CRi為船舶i的工作路數(shù)即橋吊數(shù)；B、S為岸線長；T為時(shí)間周期；A為船的個(gè)數(shù)；CRS為總的橋吊數(shù)；σij表示船i在船j的下方且不重疊即兩條船在時(shí)間方向上不重疊，則為1，否則為0；δij表示船i在船j的左側(cè)且不重疊即兩條船在泊位空間上不重疊，則為1，否則為0。

式（1）表示最小化所有船舶開始泊位工作的時(shí)間之和；式（2）保證任意兩船不交疊；式（3）表示船舶到港后才可以進(jìn)泊位分配，開始工作，式（4）表示船舶工作的結(jié)束時(shí)間不大于T，即所有船舶必須在計(jì)劃期內(nèi)完成裝卸作業(yè)；式（5）表示任意船舶的船頭部分不超出總的泊位空間；式（6）表示泊位后，任意船舶的船尾部分不超出總的泊位空間；式（7）表示任意時(shí)刻，所有在泊的船的工作路數(shù)之和不超過橋吊總數(shù)。

在上述模型中，目標(biāo)函數(shù)是一個(gè)線性函數(shù)，約束條件為線性不等式，它們是一個(gè)整數(shù)規(guī)劃問題。劉莉莉等應(yīng)用分支定界法[8]求解以上整數(shù)規(guī)劃模型。但其編程主要是串行模式，當(dāng)船舶數(shù)量較大時(shí)，問題的求解變得很慢，效率較差。為此，本文基于CUDA的計(jì)算架構(gòu)實(shí)現(xiàn)求解整數(shù)規(guī)劃問題的分支定界法，并將它應(yīng)用于求解集裝箱碼頭連續(xù)泊位分配問題，以期能大大縮短計(jì)算時(shí)間。

3 連續(xù)泊位分配問題的計(jì)算實(shí)驗(yàn)

本文實(shí)驗(yàn)環(huán)境是VS2010+CUDA6.5+NVIDIA Ge?Force 610M,文中的實(shí)驗(yàn)部分?jǐn)?shù)據(jù)是采用文[7]中實(shí)現(xiàn)的算例，如5,7,9條船。其中的單純性算法是基于CUDA而實(shí)現(xiàn)，得出如表1的統(tǒng)計(jì)結(jié)果。當(dāng)船的數(shù)量增加至9條船時(shí)，文[8]中的實(shí)驗(yàn)時(shí)間在4小時(shí)以上；而在本文的實(shí)驗(yàn)中，9條船的泊位分配策略在數(shù)秒內(nèi)就得以實(shí)現(xiàn)了。具體的實(shí)驗(yàn)結(jié)果如下表1：

表1 基于CUDA的單純性算法的分枝定界法實(shí)驗(yàn)結(jié)果與劉的SBB算法實(shí)驗(yàn)結(jié)果

本文又繼續(xù)做了實(shí)驗(yàn)，以測試基于CUDA的計(jì)算架構(gòu)的性能，11條到港作業(yè)船泊的基本信息如下表2所示，在這里 A=11，S=80，T=24，CRS=12。

表2 十一條船舶的基本信息

基于CUDA的計(jì)算架構(gòu)的單純形算法的分支定界法11條船泊的泊位分配計(jì)劃信息如圖1所示，其中time1即為運(yùn)行時(shí)間。

基于CUDA的單純形算法的分支定界法的十一條船舶二維直觀圖泊位分配圖如圖2所示：

圖1 十一條船基于CUDA的單純形算法的分支定界法泊位分配計(jì)劃信息圖

圖2 十一條船基于CUDA的單純形算法的分支定界法泊位分配圖

12條到港作業(yè)船舶的基本信息如表3所示，在這里 A=12，S=80，T=36，CRS=20。

表3 十二條船舶的基本信息

基于CUDA的計(jì)算架構(gòu)的單純形算法的分支定界法12條船泊的泊位分配計(jì)劃如下圖3所示，其中time1即為運(yùn)行時(shí)間。

圖3 十二條船基于CUDA的單純形算法的分支定界法泊位分配計(jì)劃信息圖

基于CUDA的單純形算法的分支定界法的十二條船舶二維直觀圖泊位分配圖如圖4所示：

圖4 十二條船基于CUDA的單純形算法的分支定界法泊位分配圖

上述實(shí)驗(yàn)結(jié)果表明，基于CUDA的計(jì)算架構(gòu)能大大縮短連續(xù)泊位分配模型的計(jì)算時(shí)間。文[8]中的實(shí)驗(yàn)并沒有給出11，12條船舶的實(shí)驗(yàn)數(shù)據(jù)，且在9條船時(shí)，實(shí)驗(yàn)所用時(shí)間就相當(dāng)?shù)拇?。本文基于CUDA的計(jì)算架構(gòu)的分支定界法求解連續(xù)泊位分配問題，對11和12條船的情況仍然可以在理想的時(shí)間里獲得泊位分配計(jì)劃。通過分析實(shí)驗(yàn)結(jié)果，明顯的突出了利用GPU進(jìn)行并行計(jì)算的優(yōu)勢，挖掘出了GPU高性能的特點(diǎn)。

4 結(jié)語

本文利用GPU強(qiáng)勁的并行處理能力，基于CUDA的計(jì)算架構(gòu)實(shí)現(xiàn)求解線性規(guī)劃問題的單純形算法，在此基礎(chǔ)上實(shí)現(xiàn)分支定界法求解集裝箱碼頭連續(xù)泊位分配問題。使得計(jì)算時(shí)間大大縮短。對提高集裝箱港口生產(chǎn)管理效率有著重要的應(yīng)用價(jià)值。本文的后續(xù)研究工作將建立一個(gè)完善的港口集裝箱碼頭岸邊資源分配系統(tǒng)，并將基于CUDA的計(jì)算架構(gòu)計(jì)算模式加以應(yīng)用。

[]金晶,陳山枝.并行計(jì)算普適編程模型及系統(tǒng)架構(gòu)研究[D].北京：北京郵電大學(xué),2012.

[2]Shane Cook.CUDA Programming：A Developer's Guide to Parallel Computing with GPUs[M].蘇統(tǒng)華，李東等譯.北京：機(jī)械工業(yè)出版社，2014.1.

[3]Jason Sanders、Edward Kandrot.CUDA By Example：an Introduction to General-Purpose GPU Programming[M].聶雪軍等譯.北京：北京工業(yè)出版社，201.1.

[4]張舒，褚艷利等.GPU高性能運(yùn)算之CUDA[M].北京：中國水利水電出版社，2009.10.

[5]A Fast Simplex Algorithm for Linear Programming[J].Journal of Computational Mathematics,2010,v.2806：837-847.

[6]Thomas H.Cormen,Charles E.Leisersonet，殷建平等譯.Introduction to Algorithm，Third Edition[M].北京：機(jī)械工業(yè)出版社，2013.1.

[7]吳慶豐.改進(jìn)的單純形法迭代計(jì)算方法[J].計(jì)算機(jī)工程與應(yīng)用，2014，50，No.81718：59-62+69.

[8]劉莉莉，楊智應(yīng).集裝箱碼頭連續(xù)泊位[D].上海海事大學(xué),2010.

Solution of Container Terminal Berth Allocation Problem Based on CUDA Calculation Architecture

WEI Hua，YANG Zhi-ying
（College of Information Engineering,Shanghai Maritime University,Shanghai 201306）

GPU with the powerful ability of parallel computing is one of the most important platforms for high performance computing.Based on the CUDA computing architecture,realizes the simplex algorithm for solving linear programming problems.On that basis,presents the branch and bound method for solving integer programming problems,which is applied to solve the problem of continuous berth allocation in con?tainer terminals.The experimental results show that the computing architecture based on CUDA can greatly reduce the computation time.

1007-1423（2017）23-0017-05

10.3969/j.issn.1007-1423.2017.23.004

韋華（1990-），女，山東菏澤人，碩士，研究方向?yàn)椴⑿蟹植际接?jì)算與軟件工程

2017-05-04

2017-08-05

Parallel Computing;GPU;CUDA;Simplex Algorithm