PopSparse Matrix Multiplication (Dynamic Pattern) on the IPU

This document is a fairly high-level description of the algorithmic design of the dynamic sparse matrix multiplication in the Graphcore PopSparse library. It provides a guide to the code and some pointers to the implementation.

Contents

• 1. Overview
• 2. Background
• 3. Known limitations
• 4. Implementation
  • 4.1. The Plan & Device implementation
    • 4.1.1. Format of the sparse operand on the device
    • 4.1.2. Encoding a pattern and distributing non-zero values
  • 4.2. Implementation on the device
  • 4.3. Details of exchanges to shift buckets during the propagation phase
  • 4.4. Details of vertices
    • 4.4.1. Element-wise sparsity (1x1 granularity)
    • 4.4.2. Block sparsity (anything but 1x1)
    • 4.4.3. Vertex specialisations
  • 4.5. Performance characteristics
  • 4.6. SparsePartitioner spilling method
  • 4.7. GradW pass
  • 4.8. Planning
• 5. Trademarks & copyright