結(jié)構(gòu)化非線性規(guī)劃的CPU-GPU協(xié)同并行內(nèi)點(diǎn)算法研究.pdf

1、近年來，圖形處理器(Graphics Processing Units，GPU)在非圖形處理的通用計(jì)算領(lǐng)域取得了豐碩的研究成果，與此同時，在最優(yōu)化計(jì)算領(lǐng)域，只依靠CPU對大規(guī)模問題進(jìn)行求解遇到了計(jì)算資源不足的困難。因此，本文設(shè)計(jì)了基于CPU與GPU協(xié)同并行的方法來求解結(jié)構(gòu)化非線性規(guī)劃。結(jié)構(gòu)化非線性規(guī)劃的所有約束條件構(gòu)成約束集合，約束集合中的約束項(xiàng)具有一定的耦合性和獨(dú)立性，采用高效的內(nèi)點(diǎn)算法求解該類問題時，其形成的修正方程系數(shù)矩陣具有分塊

2、帶邊的箭型結(jié)構(gòu)。在工程應(yīng)用上，許多實(shí)際問題具有這樣的特征，比如:電力系統(tǒng)的機(jī)組組合問題、最優(yōu)潮流問題、物流管理中的多商品網(wǎng)絡(luò)流問題以及通信中的網(wǎng)絡(luò)保護(hù)問題等，且其中機(jī)組組合問題是該類問題的典型代表。因此，對結(jié)構(gòu)化非線性規(guī)劃的研究可以幫助工程更好的做決策。
　　利用原始-對偶內(nèi)點(diǎn)法求解諸如連續(xù)松弛的機(jī)組組合問題之類的結(jié)構(gòu)化非線性規(guī)劃時，通過合理的對變量和約束進(jìn)行分組，可使得迭代過程中產(chǎn)生的牛頓修正方程的系數(shù)矩陣具有分塊帶邊的特殊結(jié)構(gòu)

3、。本文基于快速解耦技術(shù)將該牛頓修正方程進(jìn)行解耦，可以得到多個相互獨(dú)立的子問題，從而采用CPU與GPU協(xié)同粗粒度并行的方式實(shí)現(xiàn)問題的快速求解。
　　針對粗粒度并行計(jì)算子線性系統(tǒng)難以充分利用GPU資源的問題，本文在粗粒度并行模式上進(jìn)一步的優(yōu)化研究。對求解過程中耗時最長的牛頓修正方程的子問題求解進(jìn)行獨(dú)立分析，設(shè)計(jì)并行高斯-約旦算法從細(xì)粒度的層面對其進(jìn)行并行計(jì)算。
　　本文利用CPU-GPU從粗粒度的層面，分別協(xié)同并行求解帶稀疏型和