-
Cache Blocking of Distributed-Memory Parallel Matrix Power Kernels
Authors:
Dane C. Lacey,
Christie L. Alappat,
Florian Lange,
Georg Hager,
Holger Fehske,
Gerhard Wellein
Abstract:
Sparse matrix-vector products (SpMVs) are a bottleneck in many scientific codes. Due to the heavy strain on the main memory interface from loading the sparse matrix and the possibly irregular memory access pattern, SpMV typically exhibits low arithmetic intensity. Repeating these products multiple times with the same matrix is required in many algorithms. This so-called matrix power kernel (MPK) p…
▽ More
Sparse matrix-vector products (SpMVs) are a bottleneck in many scientific codes. Due to the heavy strain on the main memory interface from loading the sparse matrix and the possibly irregular memory access pattern, SpMV typically exhibits low arithmetic intensity. Repeating these products multiple times with the same matrix is required in many algorithms. This so-called matrix power kernel (MPK) provides an opportunity for data reuse since the same matrix data is loaded from main memory multiple times, an opportunity that has only recently been exploited successfully with the Recursive Algebraic Coloring Engine (RACE). Using RACE, one considers a graph based formulation of the SpMV and employs s level-based implementation of SpMV for reuse of relevant matrix data. However, the underlying data dependencies have restricted the use of this concept to shared memory parallelization and thus to single compute nodes. Enabling cache blocking for distributed-memory parallelization of MPK is challenging due to the need for explicit communication and synchronization of data in neighboring levels. In this work, we propose and implement a flexible method that interleaves the cache-blocking capabilities of RACE with an MPI communication scheme that fulfills all data dependencies among processes. Compared to a "traditional" distributed memory parallel MPK, our new Distributed Level-Blocked MPK yields substantial speed-ups on modern Intel and AMD architectures across a wide range of sparse matrices from various scientific applications. Finally, we address a modern quantum physics problem to demonstrate the applicability of our method, achieving a speed-up of up to 4x on 832 cores of an Intel Sapphire Rapids cluster.
△ Less
Submitted 22 May, 2024; v1 submitted 21 May, 2024;
originally announced May 2024.
-
Position: Why We Must Rethink Empirical Research in Machine Learning
Authors:
Moritz Herrmann,
F. Julian D. Lange,
Katharina Eggensperger,
Giuseppe Casalicchio,
Marcel Wever,
Matthias Feurer,
David Rügamer,
Eyke Hüllermeier,
Anne-Laure Boulesteix,
Bernd Bischl
Abstract:
We warn against a common but incomplete understanding of empirical research in machine learning that leads to non-replicable results, makes findings unreliable, and threatens to undermine progress in the field. To overcome this alarming situation, we call for more awareness of the plurality of ways of gaining knowledge experimentally but also of some epistemic limitations. In particular, we argue…
▽ More
We warn against a common but incomplete understanding of empirical research in machine learning that leads to non-replicable results, makes findings unreliable, and threatens to undermine progress in the field. To overcome this alarming situation, we call for more awareness of the plurality of ways of gaining knowledge experimentally but also of some epistemic limitations. In particular, we argue most current empirical machine learning research is fashioned as confirmatory research while it should rather be considered exploratory.
△ Less
Submitted 25 May, 2024; v1 submitted 3 May, 2024;
originally announced May 2024.
-
Modeling the Quality of Dialogical Explanations
Authors:
Milad Alshomary,
Felix Lange,
Meisam Booshehri,
Meghdut Sengupta,
Philipp Cimiano,
Henning Wachsmuth
Abstract:
Explanations are pervasive in our lives. Mostly, they occur in dialogical form where an {\em explainer} discusses a concept or phenomenon of interest with an {\em explainee}. Leaving the explainee with a clear understanding is not straightforward due to the knowledge gap between the two participants. Previous research looked at the interaction of explanation moves, dialogue acts, and topics in suc…
▽ More
Explanations are pervasive in our lives. Mostly, they occur in dialogical form where an {\em explainer} discusses a concept or phenomenon of interest with an {\em explainee}. Leaving the explainee with a clear understanding is not straightforward due to the knowledge gap between the two participants. Previous research looked at the interaction of explanation moves, dialogue acts, and topics in successful dialogues with expert explainers. However, daily-life explanations often fail, raising the question of what makes a dialogue successful. In this work, we study explanation dialogues in terms of the interactions between the explainer and explainee and how they correlate with the quality of explanations in terms of a successful understanding on the explainee's side. In particular, we first construct a corpus of 399 dialogues from the Reddit forum {\em Explain Like I am Five} and annotate it for interaction flows and explanation quality. We then analyze the interaction flows, comparing them to those appearing in expert dialogues. Finally, we encode the interaction flows using two language models that can handle long inputs, and we provide empirical evidence for the effectiveness boost gained through the encoding in predicting the success of explanation dialogues.
△ Less
Submitted 1 March, 2024;
originally announced March 2024.
-
Data Availability Sampling in Ethereum: Analysis of P2P Networking Requirements
Authors:
Michał Król,
Onur Ascigil,
Sergi Rene,
Etienne Rivière,
Matthieu Pigaglio,
Kaleem Peeroo,
Vladimir Stankovic,
Ramin Sadre,
Felix Lange
Abstract:
Despite their increasing popularity, blockchains still suffer from severe scalability limitations. Recently, Ethereum proposed a novel approach to block validation based on Data Availability Sampling (DAS), that has the potential to improve its transaction per second rate by more than two orders of magnitude. DAS should also significantly reduce per-transaction validation costs. At the same time,…
▽ More
Despite their increasing popularity, blockchains still suffer from severe scalability limitations. Recently, Ethereum proposed a novel approach to block validation based on Data Availability Sampling (DAS), that has the potential to improve its transaction per second rate by more than two orders of magnitude. DAS should also significantly reduce per-transaction validation costs. At the same time, DAS introduces new communication patterns in the Ethereum Peer-to-Peer (P2P) network. These drastically increase the amount of exchanged data and impose stringent latency objectives. In this paper, we review the new requirements for P2P networking associated with DAS, discuss open challenges, and identify new research directions.
△ Less
Submitted 20 June, 2023;
originally announced June 2023.
-
Modeling Appropriate Language in Argumentation
Authors:
Timon Ziegenbein,
Shahbaz Syed,
Felix Lange,
Martin Potthast,
Henning Wachsmuth
Abstract:
Online discussion moderators must make ad-hoc decisions about whether the contributions of discussion participants are appropriate or should be removed to maintain civility. Existing research on offensive language and the resulting tools cover only one aspect among many involved in such decisions. The question of what is considered appropriate in a controversial discussion has not yet been systema…
▽ More
Online discussion moderators must make ad-hoc decisions about whether the contributions of discussion participants are appropriate or should be removed to maintain civility. Existing research on offensive language and the resulting tools cover only one aspect among many involved in such decisions. The question of what is considered appropriate in a controversial discussion has not yet been systematically addressed. In this paper, we operationalize appropriate language in argumentation for the first time. In particular, we model appropriateness through the absence of flaws, grounded in research on argument quality assessment, especially in aspects from rhetoric. From these, we derive a new taxonomy of 14 dimensions that determine inappropriate language in online discussions. Building on three argument quality corpora, we then create a corpus of 2191 arguments annotated for the 14 dimensions. Empirical analyses support that the taxonomy covers the concept of appropriateness comprehensively, showing several plausible correlations with argument quality dimensions. Moreover, results of baseline approaches to assessing appropriateness suggest that all dimensions can be modeled computationally on the corpus.
△ Less
Submitted 24 May, 2023;
originally announced May 2023.
-
Massively Scalable Inverse Reinforcement Learning in Google Maps
Authors:
Matt Barnes,
Matthew Abueg,
Oliver F. Lange,
Matt Deeds,
Jason Trader,
Denali Molitor,
Markus Wulfmeier,
Shawn O'Banion
Abstract:
Inverse reinforcement learning (IRL) offers a powerful and general framework for learning humans' latent preferences in route recommendation, yet no approach has successfully addressed planetary-scale problems with hundreds of millions of states and demonstration trajectories. In this paper, we introduce scaling techniques based on graph compression, spatial parallelization, and improved initializ…
▽ More
Inverse reinforcement learning (IRL) offers a powerful and general framework for learning humans' latent preferences in route recommendation, yet no approach has successfully addressed planetary-scale problems with hundreds of millions of states and demonstration trajectories. In this paper, we introduce scaling techniques based on graph compression, spatial parallelization, and improved initialization conditions inspired by a connection to eigenvector algorithms. We revisit classic IRL methods in the routing context, and make the key observation that there exists a trade-off between the use of cheap, deterministic planners and expensive yet robust stochastic policies. This insight is leveraged in Receding Horizon Inverse Planning (RHIP), a new generalization of classic IRL algorithms that provides fine-grained control over performance trade-offs via its planning horizon. Our contributions culminate in a policy that achieves a 16-24% improvement in route quality at a global scale, and to the best of our knowledge, represents the largest published study of IRL algorithms in a real-world setting to date. We conclude by conducting an ablation study of key components, presenting negative results from alternative eigenvalue solvers, and identifying opportunities to further improve scalability via IRL-specific batching strategies.
△ Less
Submitted 5 March, 2024; v1 submitted 18 May, 2023;
originally announced May 2023.
-
Interpolation of Dense and Sparse Rational Functions and other Improvements in $\texttt{FireFly}$
Authors:
Jonas Klappert,
Sven Yannick Klein,
Fabian Lange
Abstract:
We present the main improvements and new features in version $\texttt{2.0}$ of the open-source $\texttt{C++}$ library $\texttt{FireFly}$ for the interpolation of rational functions. This includes algorithmic improvements, e.g. a hybrid algorithm for dense and sparse rational functions and an algorithm to identify and remove univariate factors. The new version is applied to a Feynman-integral reduc…
▽ More
We present the main improvements and new features in version $\texttt{2.0}$ of the open-source $\texttt{C++}$ library $\texttt{FireFly}$ for the interpolation of rational functions. This includes algorithmic improvements, e.g. a hybrid algorithm for dense and sparse rational functions and an algorithm to identify and remove univariate factors. The new version is applied to a Feynman-integral reduction to showcase the runtime improvements achieved. Moreover, $\texttt{FireFly}$ now supports parallelization with $\texttt{MPI}$ and offers new tools like a parser for expressions or an executable for the insertion of replacement tables.
△ Less
Submitted 3 May, 2021; v1 submitted 3 April, 2020;
originally announced April 2020.
-
Reconstructing Rational Functions with $\texttt{FireFly}$
Authors:
Jonas Klappert,
Fabian Lange
Abstract:
We present the open-source $\texttt{C++}$ library $\texttt{FireFly}$ for the reconstruction of multivariate rational functions over finite fields. We discuss the involved algorithms and their implementation. As an application, we use $\texttt{FireFly}$ in the context of integration-by-parts reductions and compare runtime and memory consumption to a fully algebraic approach with the program…
▽ More
We present the open-source $\texttt{C++}$ library $\texttt{FireFly}$ for the reconstruction of multivariate rational functions over finite fields. We discuss the involved algorithms and their implementation. As an application, we use $\texttt{FireFly}$ in the context of integration-by-parts reductions and compare runtime and memory consumption to a fully algebraic approach with the program $\texttt{Kira}$.
△ Less
Submitted 11 October, 2019; v1 submitted 29 March, 2019;
originally announced April 2019.
-
T-Reqs: Tool Support for Managing Requirements in Large-Scale Agile System Development
Authors:
Eric Knauss,
Grischa Liebel,
Jennifer Horkoff,
Rebekka Wohlrab,
Rashidah Kasauli,
Filip Lange,
Pierre Gildert
Abstract:
T-Reqs is a text-based requirements management solution based on the git version control system. It combines useful conventions, templates and helper scripts with powerful existing solutions from the git ecosystem and provides a working solution to address some known requirements engineering challenges in large-scale agile system development. Specifically, it allows agile cross-functional teams to…
▽ More
T-Reqs is a text-based requirements management solution based on the git version control system. It combines useful conventions, templates and helper scripts with powerful existing solutions from the git ecosystem and provides a working solution to address some known requirements engineering challenges in large-scale agile system development. Specifically, it allows agile cross-functional teams to be aware of requirements at system level and enables them to efficiently propose updates to those requirements. Based on our experience with T-Reqs, we i) relate known requirements challenges of large-scale agile system development to tool support; ii) list key requirements for tooling in such a context; and iii) propose concrete solutions for challenges.
△ Less
Submitted 20 July, 2018; v1 submitted 7 May, 2018;
originally announced May 2018.
