Authors: Leo Gold, Adam Bienkowski, David Sidoti, Krishna Pattipati, Omer Khan
Abstract: The Multi-Objective Shortest-Path (MOS) problem finds a set of Pareto-optimal
solutions from a start node to a destination node in a multi-attribute graph.
To solve the NP-hard MOS problem, the literature explores heuristic
multi-objective A*-style algorithmic approaches. A generalized MOS algorithm
maintains a “frontier” of partial paths at each node and performs ordered
processing to ensure that Pareto-optimal paths are generated to reach the goal
node. The algorithm becomes computationally intractable as the number of
objectives increases due to a rapid increase in the non-dominated paths, and
the concomitantly large increase in Pareto-optimal solutions. While prior works
have focused on algorithmic methods to reduce the complexity, we tackle this
challenge by exploiting parallelism using an algorithm-architecture approach.
The key insight is that MOS algorithms rely on the ordered execution of partial
paths to maintain high work efficiency. The OPMOS framework, proposed herein,
unlocks ordered parallelism and efficiently exploits the concurrent execution
of multiple paths in MOS. Experimental evaluation using the NVIDIA GH200
Superchip shows the performance scaling potential of OPMOS on work efficiency
and parallelism using a real-world application to ship routing.
Source: http://arxiv.org/abs/2411.16667v1
