Search

High-performance sparse matrix-matrix (SpMM) multiplication is paramount for science and industry, as the ever-increasing sizes of data prohibit using dense data structures. Yet, existing hardware, such as Tensor Cores (TC), is ill-suited for SpMM, as it imposes strict constraints on data structures that cannot be met by unstructured sparsity found in many applications. To address this, we introduce (S)parse (Ma)trix Matrix (T)ensor Core-accelerated (SMaT): a novel SpMM library that utilizes TCs for unstructured sparse matrices. Our block-sparse library leverages the low-level CUDA MMA (matrix-matrix-accumulate) API, maximizing the performance offered by modern GPUs. Algorithmic optimizations such as sparse matrix permutation further improve performance by minimizing the number of non-zero blocks. The evaluation on NVIDIA A100 shows that SMaT outperforms SotA libraries (DASP, cuSPARSE, and Magicube) by up to 125x (on average 2.6x). SMaT can be used to accelerate many workloads in scientific computing, large-model training, inference, and others., Comment: Accepted by 2024 International Conference on High Performance Computing, Networking, Storage and Analysis, 2023 (SC'24)

We define reduced and essential Banach algebras associated to a twisted \'{e}tale (not necessarily Hausdorff) groupoid $(\mathcal{G},\mathcal{L})$ and extend some fundamental results from $C^*$-algebras to this context. For instance, we prove that for topologically free and minimal groupoids every essential Banach algebra is simple, and we give conditions under which reduced algebras are essential (for example Hausdorffness of $\mathcal{G}$ is sufficient). This in particular solves the simplicity problem posed recently by Gardella-Lupini for $L^p$-operator algebras associated to $\mathcal{G}$. In addition, using either the $n$-filling or locally contracting condition we give pure infiniteness criteria for essential simple Banach algebras associated to $(\mathcal{G},\mathcal{L})$. This extends the corresponding $C^*$-algebraic results that were previously known to hold in the untwisted Hausdorff case. The results work nicely, and allow for characterisation of the generalized intersection property, in the realm of $L^P$-operator algebras where $P \subseteq [1,\infty]$ is a non-empty set of parameters. Such algebras cover in particular $L^p$-operator algebras, for $p\in [1,\infty]$, and their Banach $*$-algebra versions. We apply our results to Banach algebra crossed products by twisted partial group actions, Roe-type Banach algebras with coefficients in finite-rank operators on a Banach space, twisted tight $L^P$-operator algebras of inverse semigroups, graph $L^P$-operator algebras, and algebras associated to self-similar group actions on graphs. We also interpret our results in terms of twisted inverse semigroup actions and their crossed products., Comment: Comments welcome

We extend the theory of Fourier--Stieltjes algebras to the category of twisted actions by \'etale groupoids on arbitrary C*-bundles, generalizing theories constructed previously by B\'{e}dos and Conti for twisted group actions on unital C*-algebras, and by Renault and others for groupoid C*-algebras, in each case motivated by the classical theory of Fourier--Stieltjes algebras of discrete groups. To this end we develop a toolbox including, among other things, a theory of multiplier C*-correspondences, multiplier C*-correspondence bundles, Busby--Smith twisted groupoid actions, and the associated crossed products, equivariant representations and Fell's absorption theorems. For a fixed \'etale groupoid $G$ a Fourier--Stieltjes multiplier is a family of maps acting on fibers, arising from an equivariant representation. It corresponds to a certain fiber-preserving strict completely bounded map between twisted full (or reduced) crossed products. We establish a KSGNS-type dilation result which shows that the correspondence above restricts to a bijection between positive-definite multipliers and a particular class of completely positive maps. Further we introduce a subclass of Fourier multipliers, that enjoys a natural absorption property with respect to Fourier--Stieltjes multipliers and gives rise to `reduced to full' multiplier maps on crossed products. Finally we provide several applications of the theory developed, for example to the approximation properties, such as weak containment or nuclearity, of the crossed products and actions in question, and discuss outstanding open problems., Comment: 76 pages

The field of natural language processing (NLP) has witnessed significant progress in recent years, with a notable focus on improving large language models' (LLM) performance through innovative prompting techniques. Among these, prompt engineering coupled with structures has emerged as a promising paradigm, with designs such as Chain-of-Thought, Tree of Thoughts, or Graph of Thoughts, in which the overall LLM reasoning is guided by a structure such as a graph. As illustrated with numerous examples, this paradigm significantly enhances the LLM's capability to solve numerous tasks, ranging from logical or mathematical reasoning to planning or creative writing. To facilitate the understanding of this growing field and pave the way for future developments, we devise a general blueprint for effective and efficient LLM reasoning schemes. For this, we conduct an in-depth analysis of the prompt execution pipeline, clarifying and clearly defining different concepts. We then build the first taxonomy of structure-enhanced LLM reasoning schemes. We focus on identifying fundamental classes of harnessed structures, and we analyze the representations of these structures, algorithms executed with these structures, and many others. We refer to these structures as reasoning topologies, because their representation becomes to a degree spatial, as they are contained within the LLM context. Our study compares existing prompting schemes using the proposed taxonomy, discussing how certain design choices lead to different patterns in performance and cost. We also outline theoretical underpinnings, relationships between prompting and other parts of the LLM ecosystem such as knowledge bases, and the associated research challenges. Our work will help to advance future prompt engineering techniques.

We generalize the well known $C^*$-algebraic result of Kawamura-Tomiyama and Archbold-Spielberg for crossed products of discrete transformation groups to the realm of Banach algebras and twisted actions. Namely we show that topological freeneess is equivalent to the intersection property for all reduced twisted Banach algebra crossed products coming from subgroups, and in the untwisted case to a generalized intersection property for a full $L^p$-operator algebra crossed product for some (and hence any) $p\in [1,\infty]$. This gives efficient simplicity criteria for various Banach algebra crossed products. We also use it to identify the prime ideal space of some crossed products as the quasi-orbit space of the action. For amenable actions we prove that the full and reduced twisted $L^p$-operator algebras coincide., Comment: 25 pages

We introduce Banach algebras associated to a twisted \'etale groupoid $(\mathcal{G},\mathcal{L})$ and to twisted inverse semigroup actions. This provides a unifying framework for numerous recent papers on $L^p$-operator algebras and the theory of groupoid $C^*$-algebras. We prove a disintegration theorem that allows us to study Banach algebras associated to $(\mathcal{G},\mathcal{L})$ as universal Banach algebras generated by $C_0(X)$ and a twisted inverse semigroup $S$ of partial isometries subject to some relations. Our theory works best when the groupoid is ample or when the target of a representation is a dual Banach algebra $B$, so for instance $B=B(E)$ where $E$ is a reflexive Banach space. In particular, it implies that in the constructions of $L^p$-analogues of Cuntz or graph algebras, by Phillips and Corti\~{n}as--Rodr\'{\i}guez, the use of \emph{spatial partial isometries} is not an assumption, in fact it is forced by the relations. We establish fundamental norm estimates and hierarchy for full and reduced $L^p$-operator algebras for $(\mathcal{G},\mathcal{L})$ and $p \in [1,\infty]$, whose special cases have been studied recently by Gardella--Lupini, Choi--Gardella--Thiel and Hetland--Ortega. We also introduce tight inverse semigroup Banach algebras that cover ample groupoid Banach algebras, and we discuss Banach algebras associated to twisted partial group actions, twisted Renault--Deaconu groupoids and directed graphs. Our Banach Cuntz algebras are related to the construction of Daws--Horv\'{a}th. We aim for a high degree of generality throughout: our results cover non-Hausdorff \'{e}tale groupoids and both real and complex algebras. Some of our results seem to be absent from the literature even for $C^*$-algebras., Comment: The definition of a groupoid Banach algebra now involves a specified inverse semigroup, which allows us to correct a problem in Proposition 4.21 of the previous version. A question concerning the real case (Remark 2.13 of the previous version) is now solved. Updates to the rest of the manuscript reflect these two main changes

Important graph mining problems such as Clustering are computationally demanding. To significantly accelerate these problems, we propose ProbGraph: a graph representation that enables simple and fast approximate parallel graph mining with strong theoretical guarantees on work, depth, and result accuracy. The key idea is to represent sets of vertices using probabilistic set representations such as Bloom filters. These representations are much faster to process than the original vertex sets thanks to vectorizability and small size. We use these representations as building blocks in important parallel graph mining algorithms such as Clique Counting or Clustering. When enhanced with ProbGraph, these algorithms significantly outperform tuned parallel exact baselines (up to nearly 50x on 32 cores) while ensuring accuracy of more than 90% for many input graph datasets. Our novel bounds and algorithms based on probabilistic set representations with desirable statistical properties are of separate interest for the data analytics community., Comment: Best Paper Award at ACM/IEEE Supercomputing'22 (SC22)

GaN nanowires (NWs) grown by molecular beam epitaxy on Ti films sputtered on Al$_{2}$O$_{3}$ are studied by X-ray diffraction (XRD) and grazing incidence small-angle X-ray scattering (GISAXS). XRD, performed both in symmetric Bragg reflection and at grazing incidence, reveals Ti, Ti$_{3}$O, Ti$_{3}$Al, and TiO$_x$N$_y$ crystallites with in-plane and out-of-plane lattice parameters intermediate between those of Al$_{2}$O$_{3}$ and GaN. These topotaxial crystallites in Ti film, formed due to interfacial reactions and N exposure, possess fairly little misorientation with respect to Al$_{2}$O$_{3}$. As a result, GaN NWs grow on the top TiN layer possessing a high degree of epitaxial orientation with respect to the substrate. The measured GISAXS intensity distributions are modeled by the Monte Carlo method taking into account the orientational distributions of NWs, a variety of their cross-sectional shapes and sizes, and roughness of their side facets. The cross-sectional size distributions of the NWs and the relative fractions of $(1\bar{1}00)$ and $(11\bar{2}0)$ side facets are determined.

Multilinear algebra kernel performance on modern massively-parallel systems is determined mainly by data movement. However, deriving data movement-optimal distributed schedules for programs with many high-dimensional inputs is a notoriously hard problem. State-of-the-art libraries rely on heuristics and often fall back to suboptimal tensor folding and BLAS calls. We present Deinsum, an automated framework for distributed multilinear algebra computations expressed in Einstein notation, based on rigorous mathematical tools to address this problem. Our framework automatically derives data movement-optimal tiling and generates corresponding distributed schedules, further optimizing the performance of local computations by increasing their arithmetic intensity. To show the benefits of our approach, we test it on two important tensor kernel classes: Matricized Tensor Times Khatri-Rao Products and Tensor Times Matrix chains. We show performance results and scaling on the Piz Daint supercomputer, with up to 19x speedup over state-of-the-art solutions on 512 nodes.

Our initial data is a transfer operator $L$ for a continuous, countable-to-one map $\varphi:\Delta \to X$ defined on an open subset of a locally compact Hausdorff space $X$. Then $L$ may be identified with a `potential', i.e. a map $\varrho:\Delta\to X$ that need not be continuous unless $\varphi$ is a local homeomorphism. We define the crossed product $C_0(X)\rtimes L$ as a universal $C^*$-algebra with explicit generators and relations, and give an explicit faithful representation of $C_0(X)\rtimes L$ under which it is generated by weighted composition operators. We explain its relationship with Exel-Royer's crossed products, quiver $C^*$-algebras of Muhly and Tomforde, $C^*$-algebras associated to complex or self-similar dynamics by Kajiwara and Watatani, and groupoid $C^*$-algebras associated to Deaconu-Renault groupoids. We describe spectra of core subalgebras of $C_0(X)\rtimes L$ and use it to characterise simplicity of $C_0(X)\rtimes L$ and prove the uniqueness theorem for $C_0(X)\rtimes L$. We give efficient criteria for $C_0(X)\rtimes L$ to be a Kirchberg algebra, and we discuss relationship between KMS states on the core subalgebra of $C_0(X)\rtimes L$ and conformal measures for $\varphi$., Comment: 38 pages

C is the lingua franca of programming and almost any device can be programmed using C. However, programming mod-ern heterogeneous architectures such as multi-core CPUs and GPUs requires explicitly expressing parallelism as well as device-specific properties such as memory hierarchies. The resulting code is often hard to understand, debug, and modify for different architectures. We propose to lift C programs to a parametric dataflow representation that lends itself to static data-centric analysis and enables automatic high-performance code generation. We separate writing code from optimizing for different hardware: simple, portable C source code is used to generate efficient specialized versions with a click of a button. Our approach can identify parallelism when no other compiler can, and outperforms a bespoke parallelized version of a scientific proxy application by up to 21%.

Let $A\subseteq B$ be a $C^*$-inclusion. We give efficient conditions under which $A$ separates ideals in $B$, and $B$ is purely infinite if every positive element in $A$ is properly infinite in $B$. We specialise to the case when $B$ is a crossed product for an inverse semigroup action by Hilbert bimodules or a section $C^*$-algebra of a Fell bundle over an \'etale, possibly non-Hausdorff, groupoid. Then our theory works provided $B$ is the recently introduced essential crossed product and the action is essentially exact and residually aperiodic or residually topologically free. These last notions are developed in the article., Comment: An error in the earlier version of Proposition 4.2 is fixed (we thank Alcides Buss, Diego Mart\'inez and Jonathan Taylor for pointing it to us). To appear in Journal of Noncommutative Geometry

Matrix factorizations are among the most important building blocks of scientific computing. State-of-the-art libraries, however, are not communication-optimal, underutilizing current parallel architectures. We present novel algorithms for Cholesky and LU factorizations that utilize an asymptotically communication-optimal 2.5D decomposition. We first establish a theoretical framework for deriving parallel I/O lower bounds for linear algebra kernels, and then utilize its insights to derive Cholesky and LU schedules, both communicating N^3/(P*sqrt(M)) elements per processor, where M is the local memory size. The empirical results match our theoretical analysis: our implementations communicate significantly less than Intel MKL, SLATE, and the asymptotically communication-optimal CANDMC and CAPITAL libraries. Our code outperforms these state-of-the-art libraries in almost all tested scenarios, with matrix sizes ranging from 2,048 to 262,144 on up to 512 CPU nodes of the Piz Daint supercomputer, decreasing the time-to-solution by up to three times. Our code is ScaLAPACK-compatible and available as an open-source library., Comment: 15 pages (including references), 11 figures. arXiv admin note: substantial text overlap with arXiv:2010.05975

Link prediction is one of the central problems in graph mining. However, recent studies highlight the importance of higher-order network analysis, where complex structures called motifs are the first-class citizens. We first show that existing link prediction schemes fail to effectively predict motifs. To alleviate this, we establish a general motif prediction problem and we propose several heuristics that assess the chances for a specified motif to appear. To make the scores realistic, our heuristics consider - among others - correlations between links, i.e., the potential impact of some arriving links on the appearance of other links in a given motif. Finally, for highest accuracy, we develop a graph neural network (GNN) architecture for motif prediction. Our architecture offers vertex features and sampling schemes that capture the rich structural properties of motifs. While our heuristics are fast and do not need any training, GNNs ensure highest accuracy of predicting motifs, both for dense (e.g., k-cliques) and for sparse ones (e.g., k-stars). We consistently outperform the best available competitor by more than 10% on average and up to 32% in area under the curve. Importantly, the advantages of our approach over schemes based on uncorrelated link prediction increase with the increasing motif size and complexity. We also successfully apply our architecture for predicting more arbitrary clusters and communities, illustrating its potential for graph mining beyond motif analysis.

Determining I/O lower bounds is a crucial step in obtaining communication-efficient parallel algorithms, both across the memory hierarchy and between processors. Current approaches either study specific algorithms individually, disallow programmatic motifs such as recomputation, or produce asymptotic bounds that exclude important constants. We propose a novel approach for obtaining precise I/O lower bounds on a general class of programs, which we call Simple Overlap Access Programs (SOAP). SOAP analysis covers a wide variety of algorithms, from ubiquitous computational kernels to full scientific computing applications. Using the red-blue pebble game and combinatorial methods, we are able to bound the I/O of the SOAP-induced Computational Directed Acyclic Graph (CDAG), taking into account multiple statements, input/output reuse, and optimal tiling. To deal with programs that are outside of our representation (e.g., non-injective access functions), we describe methods to approximate them with SOAP. To demonstrate our method, we analyze 38 different applications, including kernels from the Polybench benchmark suite, deep learning operators, and -- for the first time -- applications in unstructured physics simulations, numerical weather prediction stencil compositions, and full deep neural networks. We derive tight I/O bounds for several linear algebra kernels, such as Cholesky decomposition, improving the existing reported bounds by a factor of two. For stencil applications, we improve the existing bounds by a factor of up to 14. We implement our method as an open-source tool, which can derive lower bounds directly from provided C code., Comment: 13 pages, 4 figures, published at Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'21)

Simple graph algorithms such as PageRank have been the target of numerous hardware accelerators. Yet, there also exist much more complex graph mining algorithms for problems such as clustering or maximal clique listing. These algorithms are memory-bound and thus could be accelerated by hardware techniques such as Processing-in-Memory (PIM). However, they also come with nonstraightforward parallelism and complicated memory access patterns. In this work, we address this problem with a simple yet surprisingly powerful observation: operations on sets of vertices, such as intersection or union, form a large part of many complex graph mining algorithms, and can offer rich and simple parallelism at multiple levels. This observation drives our cross-layer design, in which we (1) expose set operations using a novel programming paradigm, (2) express and execute these operations efficiently with carefully designed set-centric ISA extensions called SISA, and (3) use PIM to accelerate SISA instructions. The key design idea is to alleviate the bandwidth needs of SISA instructions by mapping set operations to two types of PIM: in-DRAM bulk bitwise computing for bitvectors representing high-degree vertices, and near-memory logic layers for integer arrays representing low-degree vertices. Set-centric SISA-enhanced algorithms are efficient and outperform hand-tuned baselines, offering more than 10x speedup over the established Bron-Kerbosch algorithm for listing maximal cliques. We deliver more than 10 SISA set-centric algorithm formulations, illustrating SISA's wide applicability., Comment: Proceedings of the 54th IEEE/ACM International Symposium on Microarchitecture (MICRO'21), 2021

We propose GraphMineSuite (GMS): the first benchmarking suite for graph mining that facilitates evaluating and constructing high-performance graph mining algorithms. First, GMS comes with a benchmark specification based on extensive literature review, prescribing representative problems, algorithms, and datasets. Second, GMS offers a carefully designed software platform for seamless testing of different fine-grained elements of graph mining algorithms, such as graph representations or algorithm subroutines. The platform includes parallel implementations of more than 40 considered baselines, and it facilitates developing complex and fast mining algorithms. High modularity is possible by harnessing set algebra operations such as set intersection and difference, which enables breaking complex graph mining algorithms into simple building blocks that can be separately experimented with. GMS is supported with a broad concurrency analysis for portability in performance insights, and a novel performance metric to assess the throughput of graph mining algorithms, enabling more insightful evaluation. As use cases, we harness GMS to rapidly redesign and accelerate state-of-the-art baselines of core graph mining problems: degeneracy reordering (by up to >2x), maximal clique listing (by up to >9x), k-clique listing (by 1.1x), and subgraph isomorphism (by up to 2.5x), also obtaining better theoretical performance bounds.

Function-as-a-Service (FaaS) is one of the most promising directions for the future of cloud services, and serverless functions have immediately become a new middleware for building scalable and cost-efficient microservices and applications. However, the quickly moving technology hinders reproducibility, and the lack of a standardized benchmarking suite leads to ad-hoc solutions and microbenchmarks being used in serverless research, further complicating metaanalysis and comparison of research solutions. To address this challenge, we propose the Serverless Benchmark Suite: the first benchmark for FaaS computing that systematically covers a wide spectrum of cloud resources and applications. Our benchmark consists of the specification of representative workloads, the accompanying implementation and evaluation infrastructure, and the evaluation methodology that facilitates reproducibility and enables interpretability. We demonstrate that the abstract model of a FaaS execution environment ensures the applicability of our benchmark to multiple commercial providers such as AWS, Azure, and Google Cloud. Our work facilities experimental evaluation of serverless systems, and delivers a standardized, reliable and evolving evaluation methodology of performance, efficiency, scalability and reliability of middleware FaaS platforms., Comment: Extended version of the paper accepted at Middleware 2021

Dense linear algebra kernels, such as linear solvers or tensor contractions, are fundamental components of many scientific computing applications. In this work, we present a novel method of deriving parallel I/O lower bounds for this broad family of programs. Based on the X-partitioning abstraction, our method explicitly captures inter-statement dependencies. Applying our analysis to LU factorization, we derive COnfLUX, an LU algorithm with the parallel I/O cost of $N^3 / (P \sqrt{M})$ communicated elements per processor -- only $1/3\times$ over our established lower bound. We evaluate COnfLUX on various problem sizes, demonstrating empirical results that match our theoretical analysis, communicating asymptotically less than Cray ScaLAPACK or SLATE, and outperforming the asymptotically-optimal CANDMC library. Running on $1$,$024$ nodes of Piz Daint, COnfLUX communicates 1.6$\times$ less than the second-best implementation and is expected to communicate 2.1$\times$ less on a full-scale run on Summit., Comment: 13 pages without references, 12 figures, submitted to PPoPP 2021: 26th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming

We prove implications among the conditions in the title for an inclusion of a C*-algebra A in a C*-algebra B, and we also relate this to several other properties in case B is a crossed product for an action of a group, inverse semigroup or an \'etale groupoid on A. We show that an aperiodic C*-inclusion has a unique pseudo-expectation. If, in addition, the unique pseudo-expectation is faithful, then A supports B in the sense of the Cuntz preorder. The almost extension property implies aperiodicity, and the converse holds if B is separable. A crossed product inclusion has the almost extension property if and only if the dual groupoid of the action is topologically principal. Topologically free actions are always aperiodic. If A is separable or of Type I, then topological freeness, aperiodicity and having a unique pseudo-expectation are equivalent to the condition that A detects ideals in all intermediate C*-algebras. If, in addition, B is separable, then all these conditions are equivalent to the almost extension property., Comment: Title modified and figure 1 moved to the introduction, what has been imposed by the editors

We introduce the Haagerup property for twisted groupoid $C^*$-dynamical systems in terms of naturally defined positive-definite operator-valued multipliers. By developing a version of `the Haagerup trick' we prove that this property is equivalent to the Haagerup property of the reduced crossed product $C^*$-algebra with respect to the canonical conditional expectation $E$. This extends a theorem of Dong and Ruan for discrete group actions, and implies that a given Cartan inclusion of separable $C^*$-algebras has the Haagerup property if and only if the associated Weyl groupoid has the Haagerup property in the sense of Tu. We use the latter statement to prove that every separable $C^*$-algebra which has the Haagerup property with respect to some Cartan subalgebra satisfies the Universal Coefficient Theorem. This generalises a recent result of Barlak and Li on the UCT for nuclear Cartan pairs., Comment: 40 pages; v2 introduces many small corrections and updates references. The final version of the paper will appear in the Journal of Functional Analysis

Data movement is the dominating factor affecting performance and energy in modern computing systems. Consequently, many algorithms have been developed to minimize the number of I/O operations for common computing patterns. Matrix multiplication is no exception, and lower bounds have been proven and implemented both for shared and distributed memory systems. Reconfigurable hardware platforms are a lucrative target for I/O minimizing algorithms, as they offer full control of memory accesses to the programmer. While bounds developed in the context of fixed architectures still apply to these platforms, the spatially distributed nature of their computational and memory resources requires a decentralized approach to optimize algorithms for maximum hardware utilization. We present a model to optimize matrix multiplication for FPGA platforms, simultaneously targeting maximum performance and minimum off-chip data movement, within constraints set by the hardware. We map the model to a concrete architecture using a high-level synthesis tool, maintaining a high level of abstraction, allowing us to support arbitrary data types, and enables maintainability and portability across FPGA devices. Kernels generated from our architecture are shown to offer competitive performance in practice, scaling with both compute and memory resources. We offer our design as an open source project to encourage the open development of linear algebra and I/O minimizing algorithms on reconfigurable hardware platforms.