Accelerating TSA via SpMV-based GPU parallelization in the industrial chain context
摘要
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