智能计算机与应用
智能計算機與應用
지능계산궤여응용
Computer Study
2013年
1期
29-32
,共4页
KSP问题%Yen算法%CUDA
KSP問題%Yen算法%CUDA
KSP문제%Yen산법%CUDA
随着民航业的蓬勃发展,形成了庞大的航线网络,在众多城市间有很多航线可供选择.如何快速地从如此庞大的网络中得到K条最短路径(K-Shortest-Path,简称KSP)成了联程路径搜索的瓶颈.采用Yen算法求解航线网络中的KSP问题,并在CUDA平台下实现其并行化.并行的基本策略是借助GPU平台并行的松弛每个节点的相关边.最后,通过在CUDA平台下的实验结果表明,与串行Yen算法计算相比,基于CUDA的并行Yen的计算速度得到了很大的提高.
隨著民航業的蓬勃髮展,形成瞭龐大的航線網絡,在衆多城市間有很多航線可供選擇.如何快速地從如此龐大的網絡中得到K條最短路徑(K-Shortest-Path,簡稱KSP)成瞭聯程路徑搜索的瓶頸.採用Yen算法求解航線網絡中的KSP問題,併在CUDA平檯下實現其併行化.併行的基本策略是藉助GPU平檯併行的鬆弛每箇節點的相關邊.最後,通過在CUDA平檯下的實驗結果錶明,與串行Yen算法計算相比,基于CUDA的併行Yen的計算速度得到瞭很大的提高.
수착민항업적봉발발전,형성료방대적항선망락,재음다성시간유흔다항선가공선택.여하쾌속지종여차방대적망락중득도K조최단로경(K-Shortest-Path,간칭KSP)성료련정로경수색적병경.채용Yen산법구해항선망락중적KSP문제,병재CUDA평태하실현기병행화.병행적기본책략시차조GPU평태병행적송이매개절점적상관변.최후,통과재CUDA평태하적실험결과표명,여천행Yen산법계산상비,기우CUDA적병행Yen적계산속도득도료흔대적제고.
