Back to AI Research

AI Research

Fine-Grain GPU Parallelization of the Generalized P... | AI Research

Key Takeaways

  • Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems addresses the computational bottleneck in G...
  • The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard optimization problems.
  • Genetic Algorithm (GA)-based solvers, such as the Edge Assembly Crossover (EAX), achieve state-of-the-art performance on many benchmark instances.
  • However, the scalability of these approaches in massively parallel architectures remains limited because crossover operations involve irregular memory access patterns, graph traversals, and sequential dependencies.
  • Existing GPU-based TSP solvers primarily exploit population-level parallelism and are limited to relatively small problem sizes.
Paper AbstractExpand

The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard optimization problems. Genetic Algorithm (GA)-based solvers, such as the Edge Assembly Crossover (EAX), achieve state-of-the-art performance on many benchmark instances. However, the scalability of these approaches in massively parallel architectures remains limited because crossover operations involve irregular memory access patterns, graph traversals, and sequential dependencies. Existing GPU-based TSP solvers primarily exploit population-level parallelism and are limited to relatively small problem sizes. This work presents a fine-grain GPU implementation of the partition phase of the Generalized Partition Crossover (GPX) operator for large-scale TSP instances. The proposed approach reformulates GPX partitioning as a graph-parallel problem using coalesced memory layouts, ghost-node transformations, and connected-component analysis. The im- plementation parallelizes the union of parent tours, the splitting of degree- four vertices, the deletion of common edges, and the identification of recombining components using CUDA. Experimental results on instances ranging from 10,000 to 2 million cities demonstrate substantial acceleration over a naive sequential CPU imple- mentation. The proposed GPU partitioning achieves speedups between 48x and 625x while significantly reducing memory overhead. The re- sults demonstrate that operator-level parallelism can substantially im- prove the scalability of GA-based TSP solvers on modern many-core architectures.

Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems addresses the computational bottleneck in Genetic Algorithm (GA) solvers for the Traveling Salesman Problem (TSP). While existing GPU-based solvers typically focus on population-level parallelism, this research introduces a fine-grain approach that parallelizes the partition phase of the Generalized Partition Crossover (GPX) operator, which is the most time-consuming part of the process for large-scale instances.

Accelerating the Crossover Bottleneck

The GPX operator creates new candidate solutions by partitioning the union of two parent tours into recombining components. This process involves complex graph traversals and edge manipulations that are difficult to execute on GPUs due to irregular memory access patterns and branch divergence. Swetha Varadarajan and Darrell Whitley reformulate this partition phase as a graph-parallel problem. By moving this specific operator from the CPU to the GPU, the researchers aim to overcome the scalability limits that occur when solving TSP instances with millions of cities.

Graph-Parallel Design

The implementation uses a one-thread-per-city execution model to process the GPX partition phase. To handle the irregular nature of the graph, the researchers utilize several key techniques:

  • Edge-Table Representation: Instead of using pointer-based structures, which cause inefficient memory access, the team uses a fixed-width edge-table layout. This stores connectivity information in contiguous memory, allowing for coalesced memory access that maximizes GPU throughput.

  • Ghost-Node Transformations: To manage degree-four vertices—which complicate graph traversal—the researchers apply ghost-node transformations to split these vertices into simpler degree-two structures.

  • Connected-Component Analysis: The framework identifies recombining components using parallel pointer jumping and hooking operations, allowing threads to update component labels iteratively until convergence.

Performance and Scalability

The researchers tested their implementation on 14 TSP benchmark instances, ranging from 10,000 to 2 million cities. The GPU-based partition phase achieved speedups between 48x and 625x compared to a sequential CPU implementation. Additionally, the use of the edge-table representation reduced memory overhead by 17N to 28N units, where N is the number of cities. While the partition phase is now accelerated, the recombination phase of the GPX operator remains on the CPU, which limits the total speedup of the overall crossover operation to between 1.2x and 3x for large instances.

Future Directions

The current framework is limited to the partition phase of the crossover operator. The authors note that further performance gains could be realized by parallelizing the recombination phase, implementing GPU-based offspring evaluation, and developing fully GPU-resident evolutionary frameworks. Such advancements would eliminate the need for CPU-to-GPU memory transfers, potentially allowing for even greater scalability in solving massive combinatorial problems.

Comments (0)

No comments yet

Be the first to share your thoughts!