Maximal Atomic irRedundant Sets: a Usage-based Dataflow Partitioning Algorithm

Autor:	Ferry, Corentin, Derrien, Steven, Rajopadhye, Sanjay
Rok vydání:	2022
Předmět:	Computer Science - Programming Languages Computer Science - Distributed Parallel and Cluster Computing
Druh dokumentu:	Working Paper
Popis:	Programs admitting a polyhedral representation can be transformed in many ways for locality and parallelism, notably loop tiling. Data flow analysis can then compute dependence relations between iterations and between tiles. When tiling is applied, certain iteration-wise dependences cross tile boundaries, creating the need for inter-tile data communication. Previous work computes it as the flow-in and flow-out sets of iteration tiles. In this paper, we propose a partitioning of the flow-out of a tile into the maximal sets of iterations that are entirely consumed and incur no redundant storage or transfer. The computation is described as an algorithm and performed on a selection of polyhedral programs. We then suggest possible applications of this decomposition in compression and memory allocation. Comment: 8 pages, 5 figures, 1 table
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2211.15933 Zobrazit plný text záznamu View this record from Arxiv