As modern industrial chains become increasingly complex and time-sensitive,traditional transportation planning methods encounter efficiency bottlenecks.To address this,we propose a parallelization approach based on Sp...As modern industrial chains become increasingly complex and time-sensitive,traditional transportation planning methods encounter efficiency bottlenecks.To address this,we propose a parallelization approach based on Sparse Matrix-Vector Multiplication(SpMV)to accelerate the Transportation Simplex Algorithm(TSA)for large-scale transportation problems.Existing methods primarily exploit data parallelism but underutilize GPU computational resources.To overcome the key challenge of breadth-first search(BFS)traversal with node dependencies in the MODI algorithm,we reformulate sequential operations as SpMV computations to enhance parallelism.Branching logic in potential vector computation and closed-loop search is unified through matrix formulations to eliminate divergence,and device-side loops are introduced to accelerate single iteration steps.Experiments on a 5000×10000 dataset demonstrate a 19×speedup for the parallel MODI algorithm and a 20×overall speedup for solving the transportation problem.Furthermore,the parallel TSA outperforms a commercial LP solver by 1.3×to 1.4×on large-scale instances.展开更多
基金supported by the National Key Research and Development Program of China(No.2022YFB3304402)Natural Science Foundation of China(No.12371321)+1 种基金Guangdong Basic and Applied Basic Research Foundation(No.2024A1515030197)Shenzhen research Grant(No.CJGJZD20210408092806017).
文摘As modern industrial chains become increasingly complex and time-sensitive,traditional transportation planning methods encounter efficiency bottlenecks.To address this,we propose a parallelization approach based on Sparse Matrix-Vector Multiplication(SpMV)to accelerate the Transportation Simplex Algorithm(TSA)for large-scale transportation problems.Existing methods primarily exploit data parallelism but underutilize GPU computational resources.To overcome the key challenge of breadth-first search(BFS)traversal with node dependencies in the MODI algorithm,we reformulate sequential operations as SpMV computations to enhance parallelism.Branching logic in potential vector computation and closed-loop search is unified through matrix formulations to eliminate divergence,and device-side loops are introduced to accelerate single iteration steps.Experiments on a 5000×10000 dataset demonstrate a 19×speedup for the parallel MODI algorithm and a 20×overall speedup for solving the transportation problem.Furthermore,the parallel TSA outperforms a commercial LP solver by 1.3×to 1.4×on large-scale instances.
