Keynote Talk: Parallel Algorithm Engineering Reconsidered

Algorithm engineering is a view on the methodology of algorithmic research. At its core is a feedback cycle of modeling, design, analysis, implementation, and experimental evaluation [1, 3]; see Fig. 1. At each stage, we learn new things about an algorithmic problem that drives the development of better solutions. This is inspired by the hypothesis-driven cycle of scientific discovery prevalent in the natural sciences [2]. The invited talk reflects on the role of algorithm engineering with particular focus on parallel computing. Modeling is particularly important there because no standard model has emerged after more than half a century of research on parallel algorithms. For example, MapReduce computations have become a popular high-level theoretical model but their connection to the real world is an interesting question [4]. On the low-level end of this spectrum, we need models that enable extensive algorithm-hardware codesign needed for future energy-efficient AI hardware. On the design side, it emerges that we do not just need a single algorithm but rather a spectrum of solutions selected from a huge design space of possible algorithms. This spectrum can then cover a range of inputs and machines. To grasp this on the analysis side, we need to take constant factors into account and handle complex models. Implementation has moved from a simple transition stage to extensive performance engineering to take various kinds of parallelism into account, e.g., bits, SIMD, instructions, threads in hierarchies of caches, and multipe compute nodes. This can result in orders of magnitude performance differences, often outstripping asymptotic behavior. Experiments and the entire cycle are now in a revolutionary stage where AI assisted algorithm engineering can drive the cycle at unprecedented speed. As human researchers, we rapidly have to learn how to control it.