Vectorizing recurrences accelerates computations across multiple fields
Vectorizing Recurrences over Semirings
Programming Languages
Summary
Some computer calculations called recurrences usually have to happen one step at a time, which means they can be slow. The authors created a new way to rewrite these calculations using math rules that let many steps happen at once using special computer instructions. They built a tool called VecRec that automatically changes these calculations into faster, parallel versions. Tests show that VecRec can make these calculations up to ten times faster, even beating specialized existing programs in some cases.
What this means in practice
- •For bioinformatics teams: Generate faster sequence alignment and analysis tools by vectorizing recurrent computations automatically with VecRec.
- •For numerical computing engineers: Speed up simulation and optimization codes that use recurrences by integrating VecRec-generated vectorized kernels.
Authors
Yihong Zhang, Bala Vinaithirthan, Karima Ma, Zachary Tatlock, Maaz Bin Safeer Ahmad, Andrew Adams
Abstract
Recurrences are ubiquitous in signal and image processing, bioinformatics, numerical computing, combinatorial optimization, and many other domains. Because recurrences seem inherently sequential, they are often implemented serially and thus do not leverage vector instructions in modern hardware. This leaves much of the available, often highly parallel, hardware underutilized. In this paper, we present an algebra of recurrences over semirings and study algebraic identities that enable vectorization. Using our algebraic framework, we present a number of vectorizing transformations that yield efficient, vectorized implementations across various settings. These transformations naturally extend to 2D recurrences and mutual recurrences. We implement the recurrence algebra and the vectorizing transformations in a compiler called VecRec.VecRec compiles recurrence programs to efficient vectorized C++ implementations. The generated kernels can achieve up to an order-of-magnitude speedup over serial implementations across a wide variety of recurrences. A case study in bioinformatics shows that they are competitive with, and in many cases better than, existing libraries with manually-crafted vectorization.