title: FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor
    Cores
summary: Convolution models with long filters have demonstrated state-of-the-art
  reasoning abilities in many long-sequence tasks but lag behind the most
  optimized Transformers in wall-clock time. A major bottleneck is the Fast
  Fourier Transform (FFT)--which allows long convolutions to run in O(N logN)
  time in sequence length N but has poor hardware utilization. In this paper,
  we study how to optimize the FFT convolution. We find two key bottlenecks: the
  FFT does not effectively use specialized matrix multiply units, and it incurs
  expensive I/O between layers of the memory hierarchy. In response, we propose
  FlashFFTConv. FlashFFTConv uses a matrix decomposition that computes the FFT
  using matrix multiply units and enables kernel fusion for long sequences,
  reducing I/O. We also present two sparse convolution algorithms--1) partial
  convolutions and 2) frequency-sparse convolutions--which can be implemented
  simply by skipping blocks in the matrix decomposition, enabling further
  opportunities for memory and compute savings. FlashFFTConv speeds up exact FFT
  convolutions by up to 7.93times over PyTorch and achieves up to 4.4times
  speedup end-to-end. Given the same compute budget, FlashFFTConv allows
  Hyena-GPT-s to achieve 2.3 points better perplexity on the PILE and
  M2-BERT-base to achieve 3.3 points higher GLUE score--matching models with
  twice the parameter count. FlashFFTConv also achieves 96.1% accuracy on
  Path-512, a high-resolution vision task where no model had previously achieved
  better than 50%. Furthermore, partial convolutions enable longer-sequence
  models--yielding the first DNA model that can process the longest human genes
  (2.3M base pairs)--and frequency-sparse convolutions speed up pretrained models
  while maintaining or improving model quality.
paper_authors._id: 65519cf643baee6b4d2fa8fd
paper_authors.name: Daniel Y. Fu
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2023-11-13T09:06:03.717Z
paper_authors._id: 633c8d1a475fefe61c597ff7
paper_authors.avatarUrl: /avatars/32157bf89dbe9c7385b4816ea15ec240.svg
paper_authors.fullname: Dan Fu
paper_authors.type: user
paper_authors.user: danfu09
paper_authors._id: 65519cf643baee6b4d2fa8fe
paper_authors.name: Hermann Kumbong
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2023-11-13T09:04:31.542Z
paper_authors._id: 6525fd79e0094b7bf21c01e6
paper_authors.avatarUrl: /avatars/04616a2a0363213ed4e577e92cf8f1b8.svg
paper_authors.fullname: Hermann Kumbong
paper_authors.type: user
paper_authors.user: kumboh
paper_authors._id: 65519cf643baee6b4d2fa8ff
paper_authors.name: Eric Nguyen
paper_authors._id: 65519cf643baee6b4d2fa900
paper_authors.name: Christopher Ré
paper_title: FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor
    Cores
paper_summary: Convolution models with long filters have demonstrated state-of-the-art
  reasoning abilities in many long-sequence tasks but lag behind the most
  optimized Transformers in wall-clock time. A major bottleneck is the Fast
  Fourier Transform (FFT)--which allows long convolutions to run in O(N logN)
  time in sequence length N but has poor hardware utilization. In this paper,
  we study how to optimize the FFT convolution. We find two key bottlenecks: the
  FFT does not effectively use specialized matrix multiply units, and it incurs
  expensive I/O between layers of the memory hierarchy. In response, we propose
  FlashFFTConv. FlashFFTConv uses a matrix decomposition that computes the FFT
  using matrix multiply units and enables kernel fusion for long sequences,
  reducing I/O. We also present two sparse convolution algorithms--1) partial
  convolutions and 2) frequency-sparse convolutions--which can be implemented
  simply by skipping blocks in the matrix decomposition, enabling further
  opportunities for memory and compute savings. FlashFFTConv speeds up exact FFT
  convolutions by up to 7.93times over PyTorch and achieves up to 4.4times
  speedup end-to-end. Given the same compute budget, FlashFFTConv allows
  Hyena-GPT-s to achieve 2.3 points better perplexity on the PILE and
  M2-BERT-base to achieve 3.3 points higher GLUE score--matching models with
  twice the parameter count. FlashFFTConv also achieves 96.1% accuracy on
  Path-512, a high-resolution vision task where no model had previously achieved
  better than 50%. Furthermore, partial convolutions enable longer-sequence
  models--yielding the first DNA model that can process the longest human genes
  (2.3M base pairs)--and frequency-sparse convolutions speed up pretrained models
  while maintaining or improving model quality.
paper_ai_summary: FlashFFTConv optimizes FFT convolutions by leveraging matrix multiply units and sparse techniques, improving speed and model performance across various tasks including long-sequence DNA processing and high-resolution vision.
paper_ai_keywords: FFT convolution matrix decomposition matrix multiply units kernel fusion partial convolutions frequency-sparse convolutions Hyena-GPT-s M2-BERT-base PILE GLUE score Path-512 DNA model