graph processing teams

Abstract: For every effectively nowhere dense class $\mathcal{C}$ of relational structures, we present an algorithm that runs an almost-linear-time preprocessing step on a given structure $\mathcal{A} \in \mathcal{C}$ and a first-order formula $φ(x_1, \dots, x_k, y_1, \dots, y_\ell)$. After the preprocessing, whenever given a tuple $\bar{v} \in A^k$, the algorithm computes the number of tuples $\bar{w} \in A^\ell$ that satisfy $\mathcal{A} \models φ(\bar{v}, \bar{w})$ in constant time. Building on this, we provide an algorithm for constant-time query answering and constant-delay enumeration after almost-linear-time preprocessing for the recently introduced logic clique-guarded first-order logic with counting (cgFOC) on effectively nowhere dense classes. This generalises the testing and enumeration results for first-order logic [Schweikardt, Segoufin, and Vigny, JACM 2022] and the evaluation result for the first-order logic with counting FOC1 [Grohe and Schweikardt, PODS 2018] on nowhere dense classes.

Abstract: While accelerators for AI have seen great commercial success, it is challenging to replicate that success for other specialized domains due to a number of factors. We make the case that barriers for new accelerators can be lowered by starting with a baseline AI accelerator, and adding minimal logic to support new operators demanded by new specialized domains. This leads to a versatile chip that can be manufactured at high volume and deployed for a range of popular applications. We refer to this as the AI+X approach. This paper explores its potential for the emerging domain of Computational Pathology, which involves analysis of large whole-slide tissue images with a multi-stage pipeline. The pipeline requires support for a number of different kernels and operators - early stages perform segmentation and feature extraction, followed by graph creation with k nearest neighbor (kNN) algorithms, and finally inference with an iterative graph convolutional network (GCN) that alternates between Aggregation and Combination. We show that these stages execute inefficiently on a range of baseline CPU, GPU, AI, and GCN accelerators. That inefficiency is addressed with a combination of software re-structuring and small modifications to a baseline systolic AI accelerator. Many of the above kernels can be mapped to a systolic accelerator by offering a flexible datapath between processing elements and register access mechanisms. We add support for feature aggregation, load balanced execution, Euclidean distance calculation, binning, and counter aggregation. This additional flexibility and logic grows the area of a baseline AI chiplet by 1.1x, but by avoiding the memory wall and offering high parallelism, the proposed accelerator BEACON yields over an order of magnitude higher throughput for Computational Pathology than baseline CPU and GPU platforms.