PaperlayerView exact revision on arXiv

Source-linked AI summary

Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems

Swetha Varadarajan, Darrell Whitley

arXiv:2608.21233v1cs.AIcs.NE

TL;DR

GPU-based TSP solvers have limited scalability because crossover operations involve irregular graph computation, while existing approaches mainly parallelize population-level work. This paper implements GPX partitioning as a fine-grain CUDA graph-parallel process, achieving 48×–625× speedups over a sequential CPU implementation on instances up to 2 million cities.

  • Problem

    Crossover operators are difficult to scale on GPUs because they involve irregular memory access, graph traversal, and synchronization, while existing TSP solvers mainly use population-level parallelism.

  • Method

    The paper reformulates GPX partitioning as a fine-grain graph-parallel CUDA process using coalesced edge tables, ghost-node transformations, and connected-component analysis.

  • Results

    48×–625× speedups over a sequential CPU implementation were achieved on benchmark instances ranging from 10,000 to 2 million cities, with reduced memory consumption.

  • Takeaways & Limitations

    Operator-level GPU parallelization can substantially accelerate large-scale GA-based TSP solvers by targeting the GPX crossover bottleneck.

  • Takeaways & Limitations

    The current implementation accelerates only GPX partitioning; recombination remains unparallelized, and multi-GPU extension is left for future work.

Abstract

from arXiv · show

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.

1 Introduction

TSP genetic algorithms perform strongly, but GPU scalability is constrained by difficult crossover operations and limited fine-grain parallelization. This work addresses that gap with a CUDA implementation of GPX partitioning.

  • TSP is an NP-hard optimization problem involving the shortest Hamiltonian tour through all cities.
  • GA-based TSP solvers perform strongly, but EAX and GPX crossovers are computationally expensive and difficult to parallelize efficiently on GPUs.
  • Existing GPU TSP solvers mainly parallelize independent population evolution, while fine-grain operator-level parallelization remains underexplored because crossover has irregular graphs and synchronization requirements.
  • The GPX partition phase is a dominant bottleneck for very large instances, motivating efficient GPU implementations of crossover operators.
  • The paper presents a fine-grain CUDA implementation of the GPX partition phase using graph-parallel computation.
  • The framework combines graph-parallel formulation, coalesced edge-table organization, CUDA connected-component identification, and evaluation on instances up to 2 million cities.
  • Operator-level GPU parallelization accelerates GA-based TSP solvers by targeting the GPX partition phase rather than only population evolution and fitness evaluation.

2 Related Work

Prior GPU TSP work primarily exploits coarse-grain population parallelism, whereas this framework applies fine-grain graph parallelism directly to the GPX crossover bottleneck.

  • Earlier GPU TSP solvers parallelized fitness evaluation, mutation, and independent local-search operations across independently evolving tours.
  • Parallel genetic algorithms and hybrid GPX/EAX frameworks scale on large TSP instances but primarily exploit coarse-grain parallelism without directly accelerating crossover operators.
  • GPU graph frameworks efficiently parallelize connected components, pointer jumping, and traversal, but evolutionary crossover remains difficult because of dynamic topology, synchronization, and irregular traversal.
  • The proposed framework reformulates GPX partitioning as a graph-parallel problem and targets the dominant bottleneck in large-scale GPX solvers.

3 Background

GPX partitions the union of two parent tours into recombining AB-cycles, but its graph transformations and traversals create irregular structures that motivate specialized parallel treatment.

  • Genetic Algorithms evolve candidate TSP tours through selection, crossover, and mutation while minimizing total tour length.
  • GPX preserves high-quality edge structures from parent solutions rather than primarily preserving tour ordering.
  • GPX constructs offspring by partitioning the union graph of two parent tours into recombining components called AB-cycles.
  • The GPX partition phase constructs the parent-tour union and splits degree-four vertices.
  • It then removes common edges and identifies recombining components.
  • Degree-four vertices complicate traversal because multiple alternating paths can pass through the same vertex.
  • Partitioning combines graph traversal, edge deletion, vertex transformation, and connected-component discovery, producing irregular memory accesses and dynamic graph structures.
  • Ghost-node transformations simplify degree-four traversal, while profiling identifies GPX partitioning as the bottleneck for very large instances.

4 Challenges in GPU Parallelization

GPX is difficult to execute efficiently on GPUs because its graph operations require irregular access, divergent control flow, dynamic component handling, and synchronization.

  • GPX graph computations involve dynamic traversals, irregular memory accesses, and synchronization-intensive operations unlike dense SIMD or SIMT workloads.
  • Non-contiguous, data-dependent edge and neighbor accesses reduce memory throughput and make traditional adjacency lists and pointer-based structures poorly suited to GPUs.
  • Degree variation across vertices causes warp-level branch divergence and serializes conditional traversal and partitioning branches.
  • Variable AB-cycle topology complicates parallel traversal, while connected-component identification requires iterative label propagation and synchronization that can reduce occupancy and scalability.
  • The implementation parallelizes edge-table construction, ghost-node splitting, common-edge removal, and iterative component-label updates.

5 GPU Design

The GPU design assigns GPX partitioning to the GPU while retaining recombination on the CPU, using coalesced edge tables, ghost nodes, and parallel component identification.

  • GPU Design: The hybrid framework executes GPX partitioning on the GPU and recombination on the CPU.This design accelerates partitioning while avoiding excessive synchronization during offspring reconstruction.
  • GPU Design: Fixed-width edge tables store four parent-tour neighbors per city in contiguous memory for coalesced global accesses.The layout replaces pointer-based graph structures with predictable connectivity storage.
  • GPU Design: One GPU thread per city independently constructs the union edge-table entries with linear computational complexity.Figure 2 presents the corresponding thread and memory mapping strategy.
  • GPU Design: Ghost-node representations split degree-four vertices into simpler degree-two partitions while preserving graph connectivity.The transformation reduces branch divergence and simplifies traversal operations.
  • GPU Design: Parallel pointer jumping and hooking iteratively identify recombining components and partition the graph into alternating AB-cycles.Each GPU thread updates component labels until convergence.

6 CUDA Implementation

The CUDA implementation maps graph processing to one thread per city, uses contiguous edge-table storage, and parallelizes linear-work stages plus connected-component identification.

  • CUDA Implementation: The CUDA implementation uses one thread per city, with each thread processing graph structures associated with a single city.Kernels use blocks of 256 threads to balance occupancy, register usage, and memory throughput.
  • CUDA Implementation: Contiguous global-memory edge tables maximize memory coalescing, while shared memory supports synchronization-intensive label propagation.Shared memory is used selectively during connected-component identification.
  • CUDA Implementation: Fixed-width edge tables replace pointer-based traversals with predictable memory access patterns for GPU execution.The representation is intended to improve efficiency over irregular graph structures.
  • CUDA Implementation: Union construction, vertex splitting, and edge deletion each require O(N) work and expose independent thread-level parallelism.Connected components use iterative pointer-jumping and hooking operations inspired by parallel graph-connectivity algorithms.
  • CUDA Implementation: The CUDA design focuses on maximizing memory throughput, minimizing branch divergence, and exposing fine-grain operator-level parallelism.

7 Experimental Setup

The evaluation uses 14 large-scale TSP benchmarks on a single Tesla K80, compares against sequential CPU execution, and averages 30 runs per instance.

  • Experimental Setup: 14 TSP benchmark instances spanning 10,000 to 2 million cities evaluate scalability across multiple graph characteristics.The suite includes TSPLIB, large Art TSP, and 3D Star TSP instances.
  • Experimental Setup: Experiments run on a single NVIDIA Tesla K80 GPU using 256 threads per block and 104 CUDA blocks during kernel execution.The selected device contains 2,496 CUDA cores and 12 GB of global memory.
  • Experimental Setup: The sequential CPU baseline uses an Intel Xeon E5-2680v3 processor, although only sequential execution is used for comparison.
  • Experimental Setup: The CPU framework replaces GPX partitioning with the CUDA implementation while retaining recombination on the CPU.
  • Experimental Setup: Performance evaluation measures execution time, partitions, fusion operations, and solution quality, with partition and recombination times reported separately.Each benchmark instance is executed 30 times and averaged.

8 Results

The GPU implementation accelerates the GPX partition phase relative to sequential CPU execution, scales to million-city instances, and reduces memory consumption.

  • As problem size increases, the GPX partition phase becomes the primary crossover bottleneck, motivating GPU acceleration.For smaller instances, recombination dominates execution time.
  • 48× to 625× speedups were achieved for the GPU partition phase over the sequential CPU implementation.The implementation used 26,624 GPU threads organized into 104 CUDA blocks of 256 threads each.
  • Eliminating reverse traversal substantially reduced execution time while having little impact on solution quality.The GPU performed only forward partition traversal, whereas the CPU performed both forward and reverse traversals.
  • 1.2× to 3× overall crossover speedups were achieved for large instances including GPU–CPU communication and memory-allocation overhead.Smaller instances occasionally slowed down because the fixed GPU thread configuration underutilized hardware resources.
  • The GPU implementation scales to instances containing up to 2 million cities.Figure 7 reports scalability of the GPU implementation.
  • 17N to 28N memory units were saved using fixed-width edge tables and lookup-table-based transformations.The contiguous edge-table representation reduces memory overhead and enables coalesced accesses.

9 Discussion

The work shows that fine-grain operator-level GPU parallelism can accelerate large-scale GPX solvers by targeting the partition bottleneck, while the current implementation remains limited to that phase.

  • Operator-level parallelism substantially accelerates large-scale GPX-based TSP solvers by parallelizing the crossover operator itself.This targets the bottleneck that emerges for large problem sizes.
  • Fixed-width edge tables and ghost-node transformations replace irregular graph structures with contiguous layouts and reduce irregular accesses, branch divergence, and synchronization overhead.The representation improves memory throughput and traversal efficiency.
  • The partition phase increasingly dominates crossover execution time as problem sizes grow, making GPU acceleration more effective for very large TSP instances.The discussion connects increasing partition dominance with the effectiveness of GPU acceleration.
  • Avoiding dynamic graph restructuring provides memory savings during execution.
  • The current implementation accelerates only the partition phase, leaving recombination and multi-GPU execution as possible extensions.The passage presents these extensions as potential sources of additional gains.

10 Conclusion

The paper demonstrates a fine-grain GPU framework for GPX partitioning that combines graph-parallel computation with specialized memory and graph transformations. On large TSP instances, it achieves substantial speedups while reducing memory consumption, while several GPX stages remain targets for future GPU implementation.

  • The framework reformulates GPX partitioning through graph-parallel computation, coalesced edge-table layouts, ghost-node transformations, and parallel connected-component discovery.
  • 48×–625× speedups over a sequential CPU implementation were demonstrated on benchmark instances ranging from 10,000 to 2 million cities, alongside reduced memory consumption.
  • The recombination phase remains on the CPU, with future work targeting GPU-based offspring evaluation, Hamiltonian subpath detection, and partition selection.
  • Fully GPU-resident evolutionary frameworks could eliminate CPU–GPU memory transfers by moving selection, crossover, mutation, and population management onto the GPU.
  • Multi-GPU execution, asynchronous island-model strategies, adaptive scheduling, and workload-aware kernels are proposed to improve scalability or GPU utilization.
  • Mapping the GPX3 variant that avoids partitioning degree-four edges to GPUs remains an open direction that may provide further performance gains.
Loading 2608.21233v1…