Discrete algorithms developed within the scope of combinatorial scientific computing, applied discrete mathematics, algorithm engineering, combinatorial optimization and theoretical computer science have been growing in importance over the past decades and are highly likely to continue doing so in the future. Graph algorithms and sparse linear algebra have become significant components of emerging applications such as scientific machine learning, data analytics, computational biology, cybersecurity and a myriad of other fields. Continuous numerical simulations in computational science and engineering often yield discrete sub-problems related to optimized mapping of the given algorithm to the available compute infrastructure comprising the hardware (combining CPU hosts with a variety of dedicated accelerators via high-speed interconnects and featuring an often complex distributed memory hierarchy) as well as associated system software (operating system, programming models and languages, compilers, runtime support libraries).

In-depth understanding of both hardware and system software layers turns out to be essential. A variety of conceptual as well as technical challenges need to be addressed. Emerging compute infrastructure imposes constraints on the design of discrete algorithms. Future developments are likely to imply even more fundamental adaptations of existing and emerging algorithms. Close collaboration of developers of algorithms with their colleagues from the high-performance computer industry turns out to be crucial for the formulation of meaningful requirements on both sides.

We intend to focus on sparse linear algebra and graph algorithms while reaching out to a diverse set of representatives from industry combining expertise in modern accelerators, next-generation silicon, quantum and neuromorphic computing. Specific questions to be addressed include the following:

How do today's discrete algorithms have to be re-designed in order to meet the requirements of emerging compute infrastructure?

• Can lessons learned while mapping discrete algorithms onto modern compute infrastructure be (partially) generalized for emerging compute infrastructure?
• What are implications for (combinations of) deterministic, stochastic and data-driven methods?
• What impact on the design of discrete algorithms and their implementation can be expected from hierarchy / heterogeneity in emerging compute infrastructure?

How can emerging compute infrastructure be tailored towards the needs of practically relevant discrete problems and their algorithmic solution?

• How to support irregularity and dynamics inherent in sparse linear algebra and graph problems by suitable hardware architecture / system software?
• What do suitable programming models / languages look like?
• How to account for memory-boundedness?

We aim for improved mutual understanding through closer collaboration between researchers in discrete and combinatorial algorithms and developers of high-performance compute infrastructure. The findings of this Dagstuhl Seminar are meant to be formulated as a road map supporting the coordinated evolution of discrete algorithms and compute infrastructure.

Creative Commons BY 4.0

Kathrin Hanauer, Uwe Naumann, Alex Pothen, and Robert Schreiber