Hydra-MCS: A Hybrid CPU-GPU Approach to Accelerate the Maximum Common Subgraph Computation
Abstract
The Maximum Common Subgraph (MCS) problem is a fundamental challenge in graph theory. It generalizes the subgraph isomorphism problem and is known to be NP-complete and difficult to approximate. This inherent complexity underscores the need for efficient solutions. This work introduces Hydra-MCS, a novel hybrid CPU-GPU approach that significantly accelerates MCS computation. Our method uses a lightweight metric to accurately estimate the remaining computation (RC) for a given solution. Then it uses this metric to offload computations to the GPU, maintain load balancing, and minimize unnecessary task sharing between threads. We identify the essential information the CPU and GPU must share to optimize performance by carefully analyzing our hybrid implementation. Furthermore, we discuss the substantial advantages of offloading computation to the GPU. Our method establishes a new state of the art in performance. Under matched CPU resources, GPU integration provides approximately a <inline-formula><tex-math notation="LaTeX">$3\times$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>3</mml:mn><mml:mo>×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="cardone-ieq1-3729765.gif"/></alternatives></inline-formula> additional speedup over Hydra-MCS CPU and approximately a <inline-formula><tex-math notation="LaTeX">$4\times$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>4</mml:mn><mml:mo>×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="cardone-ieq2-3729765.gif"/></alternatives></inline-formula> speedup over parallel McSplit on the scaling workload; across long-running benchmark instances, speedups over McSplit typically reach 4-<inline-formula><tex-math notation="LaTeX">$5\times$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>5</mml:mn><mml:mo>×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="cardone-ieq3-3729765.gif"/></alternatives></inline-formula>, with peaks exceeding <inline-formula><tex-math notation="LaTeX">$12\times$</tex-math><alternatives><mml:math><mml:mrow><mml:mn>12</mml:mn><mml:mo>×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="cardone-ieq4-3729765.gif"/></alternatives></inline-formula>. We also address scalability and robustness, as our algorithm’s behavior significantly surpasses that of the original as the number of threads increases and the problems become harder. A comprehensive analysis comparing solved instances over time demonstrates that the hybrid implementation consistently solves 30-40% of the instances not yet solved by the original framework, peaking at 70% for the most complex graph pairs as they approach the timeout threshold.