Speeding up Automated Algorithm Design by Batch Evaluation: A Case Study of Genetic Programming for Ant Colony Optimisation
Authors: Bo-Cheng Lin, Yi Mei, Mengjie Zhang
Organizations: Centre for Data Science and Artificial Intelligence, and the School of Engineering and Computer Science, Victoria University of Wellington, Wellington, 6140, New Zealand
Evaluation is becoming the bottleneck of automated algorithm design, especially for iterative algorithms such as ant colony optimisation (ACO), which must run to completion on multiple instances. A transition rule designed by genetic programming reads the construction state of each ant and must be evaluated at every step. However, existing GPU methods for ACO precompute a fixed rule and parallelise the ants of one run. To address this issue, we propose BlockEval, a batch evaluation framework with GPU and CPU backends. The GPU backend executes many runs simultaneously, each as a whole in one thread block, and compiles one module per generation. When an ant has visited all its candidate cities, a warp-cooperative fallback stalls only its warp where possible. On travelling salesman problems with 50--1000 cities, the GPU backend is 4.1--16.5 times faster than the CPU backend on 32 cores and 11.2--17.8 times faster than EvoGP+TensorACO-CL.
Figures & tables
Figure 1: Existing GPU methods for the two parts of the evaluation, and their combination. Blue cells denote work, dark cells denote ants falling back to the full graph, and light grey cells denote waiting. All three are parallel, but none treats a complete run as the unit of parallelism. (a) TensorACO processes the ants of one run in parallel. Its rule is fixed and is read from a table computed once per iteration, and every ant considers all cities in every step. (b) EvoGP evaluates all trees on a batch of inputs in one call. Each thread copies a tree into local memory and interprets it node by node. (c) EvoGP+TensorACO-CL executes all runs of a generation as one batch, but advances them one construction step at a time, and calls EvoGP at every step with one tree copy per candidate. Double-headed arrows are the reads and writes of the kernels, and the marks on the host line are kernel launches and the points where the host waits. All data pass through GPU memory, the host waits once in every step, and all other ants wait while some fall back. EvoGP+TensorACO executes the same steps without candidate lists, and every ant considers all cities as in (a).
Figure 2: Overall framework of BlockEval. (a) One generation consists of P×B tasks, each of which runs ACO once. (b) In the GPU backend, all programs of a generation are compiled into one module by NVRTC, the runtime compilation library of CUDA. Each task is executed by a thread block on a streaming multiprocessor (SM). The ant groups in a warp are synchronised, and when one group falls back to the full graph, the other groups need to wait. The arrows between the kernels and the GPU memory are the reads and writes of a kernel, and the marks on the host line are the kernel launches and the single point where the host waits. (c) In the CPU backend, the Threading Building Blocks (TBB) library assigns the tasks dynamically to 32 cores.
N
Existing GPU methods
BlockEval (Ours)
TensorACO (fixed rule)
EvoGP+ TensorACO
EvoGP+ TensorACO-CL
CPU (32 cores)
GPU
Time
Mem.
Time
Mem.
Time
Mem.
Time
Time
Comp.
Mem.
50
3.21 ± 0.05
1.73
44.83 ± 1.94
3.04
44.33 ± 1.67
1.66
43.34 ± 2.74
3.07 ± 0.17
1.77
0.69
100
9.67 ± 0.17
4.91
172.5 ± 8.6
7.18
92.77 ± 5.37
1.78
77.23 ± 8.01
5.23 ± 0.23
1.82
0.76
200
33.84 ± 0.41
17.66
694.3 ± 34.0
20.63
192.4 ± 11.7
2.15
129.0 ± 8.6
11.27 ± 0.41
1.61
1.03
500
250.2 ± 1.8
17.66 †
4477.6 ± 198.3
20.04 †
514.6 ± 18.9
6.35
351.0 ± 34.1
39.57 ± 2.38
1.64
2.79
Table 1: Evaluation time per generation (s) and peak GPU memory (GB) under the default configuration of AS ( P=B=A=32 ). TensorACO runs its own fixed rule without programs as a reference. The times are the mean ± standard deviation over 10 runs and exclude the one-time compilation of the existing GPU methods. Comp. is the compilation time per generation of the GPU backend (s), which is included in its time. The memory is the sampled peak held by the process, and for a generation executed in batches ( † ) it is that of one batch. The best value in each row is in bold.
N=50
100
200
500
1000
Time per construction step (ms)
TensorACO (fixed rule)
0.131
0.195
0.340
1.00
2.24
EvoGP+TensorACO
1.83
3.49
6.98
17.9
35.4
EvoGP+TensorACO-CL
1.81
1.87
1.93
2.06
2.53
BlockEval (Ours) , CPU backend (32 cores)
1.77
1.56
1.30
1.41
1.68
BlockEval (Ours) , GPU backend
0.125
0.106
0.113
0.159
0.228
Table 2: One construction step under the default configuration of AS. The time per step is the time per generation divided by the I(N−1) construction steps of a run, as means over 10 runs. The shares are measured in one generation, as the time for which the kernels run on the GPU divided by the time of a step (Table S7 ). The last row is the percentage of steps in which at least one ant of EvoGP+TensorACO-CL falls back.
Design choice of the GPU backend
Variant
Time ratio
One run per thread block
One ant per thread block
1.70
Programs compiled into the kernel
Interpreter
1.38
Scoring loop kept
Unrolled scoring loop
1.15
All runs executed simultaneously
One run at a time
40.0
WCF
Direct port
8.30
8 threads per ant group
4 threads per ant group
1.60
Table 3: Ablation study on TSP500 (AS, P=B=A=32 , RTX A5000). Each variant changes one design choice of the GPU backend, and the time ratio is its evaluation time per generation divided by that of the GPU backend. All variants are listed in Table S9 .
Figure 3: Evaluation time per generation against (a) the problem size N and (b) the number of ants A . (c) Throughput against the number of tasks per generation PB ( N=100 , A=32 ). Solid lines correspond to varying B and dotted lines to varying P (only B for the CPU backend). The vertical line is the number of resident tasks S=192 . Colours denote the ACO variants. Dashed lines show the CPU backend on 32 cores, and the other coloured lines the GPU backend. The grey line with crosses shows EvoGP+TensorACO-CL for AS, excluding its one-time compilation, with medians over three runs in (b) and (c). Error bars show the standard deviation over 10 runs.
Figure 4: Effect of the fallback to the full graph (RTX A5000, P=B=A=32 ). (a) Cost per transition of AS. The shading shows the standard deviation, and the numbers give the increase from N=50 to 1000. (b) Fraction of waiting steps. The grey lines show Eq. ( 4 ) for m synchronised ant groups. The markers show the measured fraction of steps in which a warp ( m=4 ) or a thread block ( m=32 ) contains a fallback, over three generations of one run, against the measured q . Colours denote the method and the ACO variant, and shapes denote N .
Figure S1: (a) Evaluation time per generation of the sequential Python implementation and the CPU backend (AS, N=100 , P=4 , B=8 , A=8 ), and their ratios. (b) Speedup of the CPU backend over a single core ( P=B=A=32 ) on TSP100 (solid) and TSP500 (dotted), with the values at 32 cores. The grey dashed line shows linear speedup. Error bars show the standard deviation.
TensorACO (fixed rule)
EvoGP+TensorACO
N
As released (s)
Speedup of stacking
Runs per batch
Revisiting tours (%)
Runs per batch
Time / fixed rule
Revisiting tours (%)
50
283.2
88
1,024
1.3
1,024
14.0
1.3
100
552.6
57
1,024
4.6
1,024
17.8
4.5
200
948.1
28
1,024
15.2
1,024
20.5
14.9
500
–
–
256
62.1
256
17.9
61.8
1000
–
–
64
95.2
32
15.8
95.1
Table S3: The two methods without candidate lists under the default configuration of AS. As released is the time per generation when the released code of TensorACO executes one run at a time, measured in the first generation of three runs for N≤200 only. The speedup of stacking is this time divided by the time with the runs stacked in Table 1 of the main paper. Revisiting tours is the percentage of tours in the last iteration that visit a city more than once. Time / fixed rule is the time per generation of EvoGP+TensorACO divided by that of TensorACO with its fixed rule.
Execution
N=100 (s)
Ratio
N=500 (s)
Ratio
Eager
188.4
37.7
1016.3
24.4
CUDA graph
163.5
32.1
906.4
22.4
torch.compile
91.93
18.4
512.3
12.8
BlockEval (Ours) , GPU backend
4.99
1
40.37
1
Table S4: Evaluation time per generation of EvoGP+TensorACO-CL in three execution modes (AS, P=B=A=32 , RTX A5000). The values are medians over three runs and exclude the one-time cost of the first generation. The ratio is the time divided by that of the GPU backend of BlockEval, paired by run.
CPU backend, identical tours (%)
EvoGP+TensorACO-CL (AS)
N
AS
ACS
MMAS
Identical tours (%)
Ratio of fallbacks
Mean gap difference
Largest for a program
50
70.7
99.6
99.6
69.8
1.0001
0.002
0.34
100
11.4
98.9
98.1
11.3
1.0000
0.005
0.98
200
5.5
94.8
95.2
5.5
1.0000
0.000
1.36
500
7.7
82.0
85.6
7.7
0.9998
− 0.043
1.08
1000
34.0
66.7
72.0
32.4
0.9996
− 0.116
1.15
Table S5: Consistency of the implementations on the same workload under the default configuration ( P=B=A=32 ). Identical tours is the percentage of tasks for which the CPU backend or EvoGP+TensorACO-CL constructs exactly the same tours as the GPU backend. For EvoGP+TensorACO-CL, which runs AS on the 10 runs of Table 1 of the main paper, the ratio of fallbacks is its total number of fallbacks divided by that of the GPU backend. The gap difference is the average gap of the same program minus that in the GPU backend, in percentage points, given as the mean over all programs and as the largest absolute value for a single program. The last row gives the mean and the largest absolute value of the gap difference between the two backends (GPU minus CPU) over all 111 configurations.
Nodes of the program
Batches
Time per step (ms)
1
82
23.5
2–4
315
26.9
5–8
1096
30.4
9–12
815
35.6
13–16
520
40.8
17–24
282
49.8
Table S6: Time per construction step of EvoGP+TensorACO against the size of the programs. The upper part groups the batches at N=1000 by the number of nodes of their program. At this size, a batch contains the 32 runs of one program, and the time of a batch is converted to the time in which all 1,024 runs advance one step. The lower part gives a linear fit of the time of a batch to the mean number of nodes of its programs at each problem size, with the intercept, which does not depend on the program, the slope per node and the share of the intercept at the mean program size.
N=50
100
200
500
1000
GPU idle, waiting for the host to launch the next kernel, in the runs of Table 1 (%)
TensorACO (fixed rule)
5.3
2.8
1.2
1.4
0.5
EvoGP+TensorACO
0.6
0.3
0.0
0.0
0.1
EvoGP+TensorACO-CL
43.1
43.1
37.4
20.7
7.2
BlockEval (Ours) , GPU backend
57.9
35.0
13.7
4.3
1.4
Share of compilation, GPU backend (timers)
57.5
34.9
14.3
4.1
1.4
Table S7: A construction step of EvoGP+TensorACO-CL under the default configuration of AS ( P=B=A=32 , torch.compile mode, RTX A5000). The upper part is the share of the time in which the GPU is idle, waiting for the host to launch the next kernel, in the runs of Table 1 of the main paper. The driver reports once per second the share of the last period in which at least one kernel was running, and the table gives its complement, averaged over the measured generations of each run and then over the runs. The last row of this part is the share of the compilation in the evaluation time of the GPU backend, measured by the timers. The middle part is the kernel time per construction step by stage, from one generation at each problem size in which every kernel is recorded in 10 evenly sampled iterations. The time per step of this generation is taken from the same generation of the runs of Table 1 , and its difference to the time of all kernels is the time in which the GPU is idle. The lower part gives the kernels launched, the waits of the host and the bytes copied to the host per step, and the time per step when only the calls to EvoGP of a generation are executed (means over 10 runs).
AS
ACS
MMAS
N
TensorACO (fixed rule)
EvoGP+ TensorACO
EvoGP+ TensorACO-CL
CPU backend (32 cores)
CPU backend (32 cores)
CPU backend (32 cores)
50
1.05
14.61
14.45
14.14
10.76
13.94
100
1.85
33.04
17.76
14.78
11.80
16.52
200
3.01
61.65
17.09
11.45
8.95
13.94
500
6.34
113.5
13.04
8.88
6.14
10.20
1000
9.86
156.0
11.16
7.39
4.08
8.19
Table S8: Evaluation time per generation of each method divided by that of the GPU backend of BlockEval under the default configuration ( P=B=A=32 ). The ratios are paired by run and averaged over 10 runs, and the ratios of the CPU backend on 32 cores are the speedups of the GPU backend. The last row gives the ranges over all configurations of Fig. 3 of the main paper, with medians over three runs for EvoGP+TensorACO-CL.
Design choice
Variant
Time ratio
Threads per block
Registers per thread
Blocks per SM
GPU backend
–
1
256
78–80
3
All tasks at once
One run at a time
40.0
8
128–159
12–16
Batches of 256 tasks
1.22
256
80
3
Batches of 512 tasks
1.07
256
80
3
One task per block
1 ant per block
1.70
8
128–159
12–16
4 ants per block
1.19
32
115–128
16
Table S9: All variants of the ablation study on TSP500 (AS, P=B=A=32 , RTX A5000). The time ratio is the evaluation time per generation of the variant divided by that of the GPU backend, as the mean over paired runs for the direct port and the unrolled scoring loop, and as the median over three runs for the others. The last three columns give the number of threads per thread block, the number of registers per thread and the number of thread blocks that can reside on an SM for the construction kernel of each variant. A range is given when the number of registers changes with the programs of a generation.
N
EvoGP+TensorACO-CL compiled once (s)
CPU backend compile (s)
CPU backend compile share (%)
Speedup without CPU compilation
50
33.2
16.0
37.0
8.92
100
34.5
18.0
23.4
11.33
200
37.4
15.8
12.3
10.05
500
35.8
16.9
4.8
8.46
1000
39.8
16.8
2.0
7.24
Table S10: Compilation time under AS. The upper part gives the one-time compilation of EvoGP+TensorACO-CL by torch.compile , the compilation time per generation of the CPU backend on 32 cores, its share of the evaluation time, and the speedup of the GPU backend when the compilation is excluded from the CPU time only ( P=B=A=32 , means over 10 runs). The compilation time of the GPU backend is given in Table 1 of the main paper. The lower part gives the number of copies of each program in three kernels and their compilation time per generation at P=1 , 32 and 256, as means over all configurations with the same P .
GPU
Arch.
SMs
L2 (MB)
BW (GB/s)
Relative speed
N=100
N=500
N=1000
L4
Ada
58
48
300
0.92
0.83
0.74
RTX A5000
Ampere
64
6
768
1.00
1.00
1.00
A40
Ampere
84
6
696
1.12
1.13
1.11
RTX A6000
Ampere
84
6
768
1.26
1.20
1.21
RTX PRO 5000
Blackwell
110
96
1,344
1.30
1.30
1.46
Table S11: Speed of each GPU relative to the RTX A5000 under the default configuration ( P=B=A=32 ), as medians over the three variants, sorted by the speed at N=1000 . The speed is the device time on the A5000 divided by that on the GPU, and a value greater than 1 means faster. Arch. is the architecture and BW the memory bandwidth. The numbers of SMs, the L2 cache and the bandwidth are obtained from the CUDA device properties.
Figure S2: Expression tree of the GP-ACO champion rule with the lowest validation gap (12.324%) among the 10 independent runs on TSP500.