TL;DR
Automated Algorithm Design (AAD) is often bottlenecked by the grueling process of evaluating thousands of candidate heuristics. This paper introduces BlockEval, a framework that accelerates this process by parallelizing entire algorithm runs on GPUs, achieving up to a 16.5x speedup over a 32-core CPU for Genetic Programming-designed Ant Colony Optimization (ACO) rules.
What Problem Does This Paper Address?
In the world of Automated Algorithm Design, we use meta-heuristics like Genetic Programming (GP) or even Large Language Models (LLMs) to "evolve" or "write" better algorithms. However, generating a candidate algorithm is now much faster than testing it. To see if a new rule for Ant Colony Optimization (ACO) actually works, you have to run a full simulation—thousands of iterations across multiple problem instances.
The challenge is that these rules are often state-dependent. An ant doesn't just look at pheromones; it looks at its own construction state (e.g., "how many cities have I visited?"). Existing GPU accelerations for ACO typically assume a fixed, precomputed rule or parallelize the ants within a single run. When you try to evaluate a whole population of different rules, these traditional methods fall apart due to massive data movement overhead between the CPU and GPU and synchronization bottlenecks.
Methods
The authors propose BlockEval, a batch evaluation framework designed to treat a complete algorithm run as the unit of parallelism.
- One Run per Thread Block: Instead of spreading one ACO run across the whole GPU, BlockEval maps one program running on one instance to a single GPU thread block. This keeps the entire simulation "local" to the multiprocessor.
- Runtime Compilation (NVRTC): Since GP rules change every generation, BlockEval uses the CUDA Runtime Compilation library to bake the entire population of GP trees into a single CUDA module at the start of each generation. This allows the rules to be executed directly inside the GPU kernel without constant communication with the host.
- Warp-Cooperative Fallback (WCF): In ACO, ants usually pick from a "candidate list" of nearby cities. If those are all visited, the ant must "fallback" and scan every city in the graph—a computationally expensive and divergent branch. WCF allows threads within a GPU warp to handle this scan cooperatively, ensuring that one ant's expensive fallback doesn't stall the entire thread block.
- CPU Backend: For a fair comparison, they also developed a high-performance CPU backend using Numba (JIT compilation) and Threading Building Blocks (TBB) for multi-core scaling.
Datasets
The framework was evaluated using Euclidean Traveling Salesman Problem (TSP) instances from the ML4CO-Bench-101 benchmark.
- Problem Sizes: 50, 100, 200, 500, and 1000 cities.
- Workload: 256 GP programs evaluated on 32 instances per generation.
Key Insights and Ideas
- Data Movement is the Bottleneck: The "Aha!" moment here is realizing that arithmetic is cheap, but moving data is expensive. By keeping the entire ACO loop, the pheromone updates, and the GP rule evaluation inside a single kernel, BlockEval drastically reduces the "memory wall" effect.
- Granularity Shift: Moving the unit of parallelism from the "ant" level to the "run" level is a better fit for the high-throughput requirements of evolutionary computation.
- The Cost of Divergence: The paper quantifies how much "waiting" occurs when ants take different paths. Their WCF mechanism proves that even highly divergent iterative algorithms can be made GPU-friendly if the synchronization is handled at the warp level rather than the block level.
Key Results
- Vs. Optimized CPU: The GPU backend was 4.1x to 16.5x faster than the 32-core CPU backend.
- Vs. Existing GPU Methods: It outperformed the state-of-the-art baseline (EvoGP + TensorACO-CL) by 11.2x to 17.8x.
- Compilation Efficiency: While compiling at every generation sounds slow, it only accounted for about 1.4% of the total evaluation time for larger (1000-city) problems.
- Throughput: The system reaches 90% of its maximum throughput at approximately 1,024 simultaneous tasks, showing excellent scalability for large GP populations.
Limitations and Future Work
- Memory Constraints: As problem sizes grow beyond 1000 cities, the pheromone matrices and candidate lists may eventually exceed the shared memory or L2 cache limits of a single thread block/SM, potentially degrading performance.
- Algorithm Scope: This study focused on ACO for TSP. While the authors suggest the techniques apply to other iterative algorithms (like job shop scheduling or routing), those specific cases haven't been tested yet.
- Multi-GPU Scaling: The current work focuses on a single GPU; extending BlockEval to distribute tasks across a cluster of GPUs is a logical next step for even larger-scale automated design.
Summary updated