A Parallel Scan Algorithm in the Tensor Core Unit Model
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909406085513216 |
|---|---|
| author | Zouzias, Anastasios McColl, William F. |
| author_facet | Zouzias, Anastasios McColl, William F. |
| contents | We present a parallel scan (prefix sum) algorithm in the Tensor Core Unit (TCU) model of computation. The TCU model assumes that multiplication between two square matrices of constant size $s$ is a basic operation. In the $(s^2, \ell)$-TCU model, we show that for inputs of size $n$, the algorithm has depth at most $2\lfloor \log_s (n)\rfloor$ and runs in $O(n(1 + \ell /s^2)/p + (s^2 + \ell) \log_s (n))$ time assuming $p$ tensor core units. Equivalently, the algorithm performs $O(n/s^2)$ multiplications of square matrices of size s. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_17887 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Parallel Scan Algorithm in the Tensor Core Unit Model Zouzias, Anastasios McColl, William F. Distributed, Parallel, and Cluster Computing Data Structures and Algorithms We present a parallel scan (prefix sum) algorithm in the Tensor Core Unit (TCU) model of computation. The TCU model assumes that multiplication between two square matrices of constant size $s$ is a basic operation. In the $(s^2, \ell)$-TCU model, we show that for inputs of size $n$, the algorithm has depth at most $2\lfloor \log_s (n)\rfloor$ and runs in $O(n(1 + \ell /s^2)/p + (s^2 + \ell) \log_s (n))$ time assuming $p$ tensor core units. Equivalently, the algorithm performs $O(n/s^2)$ multiplications of square matrices of size s. |
| title | A Parallel Scan Algorithm in the Tensor Core Unit Model |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.17887 |