Metraipolis › archive › dc_7e2cbea15c3e

Vectorizing Recurrences over Semirings — arXiv:2611.02451

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.02451
License (as archived)
CC0-1.0
Archived
2026-11-03T18:59:22.026Z
SHA-256 of the archived text
61d7c040dea47a8e923fbeb106d23eaae7bd27aed5fd2dfcc00abb9b10d55834
Stable URL of this page
https://metraipolis.com/documento/dc_7e2cbea15c3e

How to cite

Vectorizing Recurrences over Semirings — arXiv:2611.02451 — arXiv (en), https://arxiv.org/abs/2611.02451 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7e2cbea15c3e (Metraipolis archive dc_7e2cbea15c3e, sha256 61d7c040dea47a8e923fbeb106d23eaae7bd27aed5fd2dfcc00abb9b10d55834)
BibTeX
@misc{dc7e2cbea15c3e,
  title = {Vectorizing Recurrences over Semirings — arXiv:2611.02451},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02451},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7e2cbea15c3e; sha256 61d7c040dea47a8e923fbeb106d23eaae7bd27aed5fd2dfcc00abb9b10d55834},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02451. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 this http URL 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.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.PL, nuovi lavori del giorno).
Categorie arXiv: Programming Languages (cs.PL).
Pagina del lavoro: https://arxiv.org/abs/2611.02451 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:19:09.693Z dalla pagina https://arxiv.org/list/cs.PL/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).