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

韋華，楊智應

（上海海事大學信息工程學院，上海 201306）

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

韋華，楊智應

（上海海事大學信息工程學院，上海 201306）

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

并行計算；GPU；CUDA；單純形算法

0 引言

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

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

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

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

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

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

1.1 CCUUDDAA編程模型

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

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

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

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

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

上述的代碼是設備端即內(nèi)核函數(shù)中重要代碼。根據(jù)替入變量和替出變量的下標，重寫線性規(guī)劃松馳型，約束等式中的非基本變量的系數(shù)及常數(shù)相應改變，目標函數(shù)中的常數(shù)及非基本變量的系數(shù)也改變。CUDA的每個線程都有自己的線程號Id，通過核函數(shù)里的int tid1=blockDim.x*blockId.x+threadIdx.x和 int tid2=block?Dim.x*blockIdx.x+threadIdx.x語句，每個線程可以獲得自身的Id號，從而找到自己的任務去執(zhí)行。一個線程執(zhí)行一個任務后還要繼續(xù)執(zhí)行余下未執(zhí)行的任務，所以通過blockDim.x*gridDim.x這一遞增量，讓線程知道自己的下一個任務。遞增的步長即為線程格中正在運行的線程數(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 前提假設

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

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

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

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

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

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

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

目標函數(shù)：

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

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

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

3 連續(xù)泊位分配問題的計算實驗

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

[4]張舒，褚艷利等.GPU高性能運算之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].北京：機械工業(yè)出版社，2013.1.

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

[8]劉莉莉，楊智應.集裝箱碼頭連續(xù)泊位[D].上海海事大學,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-），女，山東菏澤人，碩士，研究方向為并行分布式計算與軟件工程

2017-05-04

2017-08-05

Parallel Computing;GPU;CUDA;Simplex Algorithm