Linear Assignment on Tile-Centric Accelerators: Redesigning Hungarian Algorithm on IPUs

TY - GEN

T1 - Linear Assignment on Tile-Centric Accelerators

T2 - 2025 SIAM Symposium on Algorithm Engineering and Experiments, ALENEX 2025

AU - Huang, Cheng

AU - Mathiasen, Alexander

AU - Dean, Josef

AU - Langguth, Johannes

AU - Mottin, Davide

AU - Assent, Ira

N1 - Publisher Copyright: Copyright © 2025.

PY - 2025

Y1 - 2025

N2 - The Hungarian algorithm is a popular solution for the linear assignment problem that finds correspondences between sets of items. Despite its popularity, this algorithm suffers from significant efficiency shortcomings which hinders its application to large datasets. To overcome this challenge, we design a parallel version of the algorithm for novel tile-centric accelerators which consist of thousands of small processing cores equipped with memory that is local to each core. This allows them to overcome the memory latency and bandwidth limits of CPUs and GPUs, but, in turn, data and work must be carefully distributed among the many cores. We select the tile-centric Intelligence Processing Unit and discuss its capabilities and the challenges for algorithm design. We then present HunIPU, which outperforms the best GPU algorithm running 6× faster on synthetic datasets and up to 32× on real-world datasets for graph alignment. The code is available at https://zenodo.org/records/13832045.

AB - The Hungarian algorithm is a popular solution for the linear assignment problem that finds correspondences between sets of items. Despite its popularity, this algorithm suffers from significant efficiency shortcomings which hinders its application to large datasets. To overcome this challenge, we design a parallel version of the algorithm for novel tile-centric accelerators which consist of thousands of small processing cores equipped with memory that is local to each core. This allows them to overcome the memory latency and bandwidth limits of CPUs and GPUs, but, in turn, data and work must be carefully distributed among the many cores. We select the tile-centric Intelligence Processing Unit and discuss its capabilities and the challenges for algorithm design. We then present HunIPU, which outperforms the best GPU algorithm running 6× faster on synthetic datasets and up to 32× on real-world datasets for graph alignment. The code is available at https://zenodo.org/records/13832045.

UR - https://www.scopus.com/pages/publications/85216398094

M3 - Article in proceedings

AN - SCOPUS:85216398094

SP - 107

EP - 119

BT - SIAM Symposium on Algorithm Engineering and Experiments, ALENEX 2025

PB - Society for Industrial and Applied Mathematics Publications

Y2 - 12 January 2025 through 13 January 2025

ER -