Data-Parallel Algorithms for String Diagrams
Paul Wilson, Fabio Zanasi
We give parallel algorithms for string diagrams represented as structured
cospans of ACSets. Specifically, we give linear (sequential) and logarithmic
(parallel) time algorithms for composition, tensor product, construction of
diagrams from arbitrary $\Sigma$-terms, and application of functors to
diagrams. Our datastructure can represent morphisms of both the free symmetric
monoidal category over an arbitrary signature as well as those with a chosen
Special Frobenius structure. We show how this additional (hypergraph) structure
can be used to map diagrams to diagrams of optics. This leads to a case study
in which we define an algorithm for efficiently computing symbolic
representations of gradient-based learners based on reverse derivatives. The
work we present here is intended to be useful as a general purpose
datastructure. Implementation requires only integer arrays and well-known
algorithms, and is data-parallel by constuction. We therefore expect it to be
applicable to a wide variety of settings, including embedded and parallel
hardware and low-level languages.