Discrete Algorithms on Modern and Emerging Compute Infrastructure

The first and foremost topic of the working group was to define tile-centric computing (TCC) and tile-centric architectures (TCAs). It is widely agreed that TCAs consist of a large number of relatively small cores which directly connected to SRAM that is used as memory. Together, a cores with its SRAM is referred to as a tile. There are some instances of such TCAs in use today; these include the Graphcore Intelligence Processing Unit (IPU) and the Cerebras Systems Wafer-Scale Engine (WSE).

This implies a focus on MIMD processing, although many candidate architectures also have SIMD capabilities. TCAs thus differ from GPUs which strongly rely on wide SIMD and typically contain small amounts of SRAM. They also differ from CPUs, despite the fact that modern CPUs often contain a large number of cores connected to SRAM. The crucial difference is the use of SRAM as user-controlled memory, rather than cache that buffers accesses to larger DRAM or HBM in the case of CPUs.

The definition of interconnects between tiles made for a more lively discussion, especially because the IPU and WSE differ substantially in this regard. While communication between any pair of tiles on the IPU is almost equal, the 2D interconnect of the WSE makes physical location in the tile grid very important. Furthermore, devices from several other vendors, including SambaNova, Tenstorrent, and Groq, have a grid structure that is somewhat similar to the WSE, although it is not yet clear which of these architectures are suitable for graph algorithms. Thus, the consensus was that data location in the tile grid is a crucial part of TCC and that the IPU is an outlier in this regard. In any case, previous work has shown that when using multiple IPUs, the locality problem again becomes highly relevant.

The accepted term for this idea is spatial computing, but since Apple is currently using the term for its augmented reality product, some felt that the use of the term in a general discussion is discouraged to avoid confusion. While this is similar to standard distributed memory computation, it is important to stress that the tile-centric view considers the computation to be shared among the tiles, rather than composed of independent computations on e.g. MPI ranks, as is the case in message passing. While this distinction may sound overly fine, an important consequence is that for tile-centric computation, different groups of tiles having completely different functions is the norm rather than the exception.

Having defined, loosely, the class of TCAs and shared an understanding of the specifics of some instances, the discussion focused on the implications: what questions do TCAs raise for the graph algorithms community. There was a wide agreement that some sort of abstraction layer such as graphBLAS is needed since the low level implementation on TCAs clearly seems more difficult that on CPUs and likely also on GPUs. W.r.t. memory, a SHMEM or PGAS-like interface would be desirable. In addition, there is a need for adapting existing partitioning algorithms to the requirements of tile-centric devices. The the 2D interconnect of the WSE also calls for algorithms that embed graphs into 2D space. Finally it was agreed that advanced and unconventional algorithmic concepts such as temporal data sharing are worth investigating on the new devices, although nothing concrete has been discussed so far

Adjoints of arbitrary differentiable programs can be computed by an algorithm similar to backpropagation in artificial neural networks. They are crucial ingredients of the CSE toolbox. A major obstacle for an efficient implementation is the need for reversal of the data flow, which yields a number of hard combinatorial optimization problems.

We were a group of six individuals. Although we had a prearranged list of topics, we commenced by brainstorming the most engaging and promising subjects for the group. Ultimately,we delved deeply into two main topics: [A] The use of Automatic Adjoint Differentiation (AAD) in finance, focusing on its hardware implications and the challenges associated with the Partial Differential Equations (PDE) approach to Stochastic Differential Equations (SDEs). And [B], the propagation of compressed Jacobians through a chain of sparse Jacobians. Our discussions on both topics were productive and led to the following outcomes: For [A], a sub-group consisting of Uwe Naumann, Johannes Lotz, and Jason Charlesworth decided to schedule a follow-up meeting. And for [B], despite the initial promise of the idea, the group thoroughly analyzed it and concluded that it did not contain any further significant potential.

Hypergraphs generalize graphs by allowing edges (also called hyperedges) to include an arbitrary number of nodes, rather than just two. Hypergraph representations and algorithms have been used in scientific computing applications for decades, and have recently have been growing in popularity within the machine learning and data mining communities.

The working group on hypergraph algorithms specifically explored various extensions and algorithms for a clustering framework called edge colored clustering (ECC) [1, 2]. The input to the problem is a hypergraph in which every edge is associated with a color, and the goal is to assign colors to nodes in order to maximize the number of satisfied edges, where a satisfied edge is one in which all nodes within the edge are assigned the same color as the edge. This framework has been used as a model for clustering objects based on the group interactions they participate in (the hyperedges) as well as the type or category of interaction (represented by the hyperedge color).

During our working group discussions we made progress on several variants and extensions of the ECC problem. This includes (1) identifying new connections between a variant of ECC with overlapping clusters and the concept of b-matchings in hypergraphs; (2) developing a new streaming model for the problem and providing an initial analysis of the tradeoffs between space and number of passes in designing approximation algorithms; and (3) identifying key challenges in extending parameterized algorithms for the graph version of the problem to the hypergraph setting. For the latter direction, we designed a polynomial kernel for checking whether $t$ hyperedges can be satisfied in a given hypergraph, whose size depends explicitly on the rank $r$ (the maximum hyperedge size).

A combination of technological and market forces are driving rapid changes in computer architectures and system designs. These changes will have significant impacts for algorithms and software. This session reviewed the drivers behind these changes and provided some thoughts on what the future might look like. The goal of this session was to provide context for much of the remainder of the Dagstuhl program.

The session involved four presentations and lots of discussion. Bruce Hendrickson of Lawrence Livermore National Lab moderated the session and provided an overview / introductory talk. This was followed by presentations from employees of three major computing companies sharing their thoughts on potential future paths. Chris Goodyer of ARM spoke on “Building the future of computing.” Oded Green of Nvidia talked about “The Future of Accelerated Combinatorial and Sparse Applications.” And Jakob Engblom of Intel covered “Just Add Accelerators – The Answer to Everything?”

I. Safro: This is an introductory talk on the basics of quantum computing. We will introduce qubits, quantum gates, circuits, basic principles of quantum mechanics for computing, entanglement and several algorithms including Bernstein-Vazirani, Simon’s problem, Shor’s algorithm, Hidden Subgroup Problem and Grover search.

I. Safro: Learning the problem structure at multiple levels of coarseness to inform the decomposition-based hybrid quantum-classical combinatorial optimization solvers is a promising approach to scaling up variational approaches. We introduce a multilevel algorithm reinforced with the spectral graph representation learning-based accelerator to tackle large-scale graph maximum cut instances and fused with several versions of the quantum approximate optimization algorithm (QAOA) and QAOA-inspired algorithms. The graph representation learning model utilizes the idea of QAOA variational parameters concentration and substantially improves the performance of QAOA. We demonstrate the potential of using multilevel QAOA and representation learning-based approaches on very large graphs by achieving high-quality solutions in a much faster time. This talk is based on several recent works [1],[2],[3], and [4].

E. Rieffel: The talk begins with an overview of the status of current quantum processors, followed by a vision of future quantum computers. We will discuss commonalities and differences between application-scale fault-tolerant quantum computing architectures (which will necessarily contain many networked quantum and classical (non-quantum) processors) and supercomputer architectures. We will then discuss the status of quantum algorithms generally, before focusing on quantum and hybrid quantum-classical optimization algorithms, with a mention of ties to sampling and machine learning. We then highlight quantum-inspired classical algorithms and hardware. The last part of the talk gives brief glimpses of other topics with relation to discrete problems and algorithms, including compilation of algorithms to quantum hardware, quantum error correction, and polytopes arising in fundamental quantum mechanics and quantum information theory.

I will explain how wafer-scale computing currently works by detailing the hardware, architecture, and programming paradigms of the Cerebras machines, the only instance of commercial wafer-scale computers today.

The CS-3 incorporates all memory and processing on one wafer, a wafer that contains 900,000 processing elements. With 48KB of local memory, a PE cannot hold very much data. On the other hand, access to that data is at the same rate as peak speed computation. Most interesting, the mesh interconnect has single-clock latency for sending a message (of 4 bytes) to a mesh neighboring PE, and the network can sustain a 4 byte message to and from each neighbor on every clock.

The wafer is therefore a working instance of processing co-located with memory. While it is distributed memory from the addressing perspective, the extreme interconnect performance allows programmers to treat distributed tensors as if they were shared – shared objects in a distributed memory substrate. This finds uses in graph computing, sparse matrix vector products, neutron transport applications, for some examples.

The absence of both memory walls and slow, high-overhead, high-latency interconnect permits very fine grained parallel applications that achieve excellent performance. This in turn allows strong scaling in which each PE holds only a few words of the problem data, taking full advantage of the easy accessibility of data on near neighbor PEs. Thus, strong scaling is quite successful, which reduces runtimes for problems of the scale that fit the wafer by two orders of magnitude, allowing applications that are impossible with conventional systems. I will cover some use cases and give an outline of how the system can be programmed using the Cerebras SDK.