Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/72182
Type: | Dissertação |
Title: | Semiring optimization: dynamic elision of expressions with identity and absorbing elements |
Other Titles: | Otimização de semi-anel: elisão dinâmica de expressões com identidade e elementos absorventes |
Authors: | Guilherme Vieira Leobas |
First Advisor: | Fernando Magno Quintão Pereira |
First Referee: | Edson Borin |
Second Referee: | George Luiz Medeiros Teodoro |
Abstract: | This dissertation describes a compiler optimization to eliminates dynamic occurrences of expressions in the format a ← a ⊕ b ⊗ c. The operation ⊕ must admit an identity element z, such that a ⊕ z = a. Also, z must be the absorbing element of ⊗, such that b ⊗ z = z ⊗ c = z. Semirings where ⊕ is the additive operator and ⊗ is the multiplicative operator meet this contract. This pattern is common in high-performance benchmarks— its canonical representative being the multiply-add operation a ← a + b × c. However, several other expressions involving arithmetic and logic operations satisfy the required algebra. We show that the runtime elimination of such assignments can be implemented in a performance-safe way via online profiling. The elimination of dynamic redundancies involving identity and absorbing elements in 35 programs of the LLVM test suite that present semiring patterns brings an average speedup of 1.19x (total optimized time over total unoptimized time) on top of clang -O3. When projected onto the entire test suite (259 programs) the optimization leads to a speedup of 1.025x. Once added onto clang, semiring optimizations approximates it to TACO, a specialized tensor compiler. |
Abstract: | Essa dissertação descreve uma técnica de otimização que elimina ocorrências dinâmicas de expressões no formato a = a ⊕ b ⊗ c. A operação ⊕ deve admitir um elemento identidade z, de forma que a ⊕ z = z ⊕ a = a. Além disso, z deve ser o elemento anulador da operação ⊗, de forma que b ⊗ z = z ⊗ c = z. Semi anéis onde ⊕ é a operação de adição e ⊗ é o operador de multiplicação cumprem esse contrato. Esse padrão é muito comum em benchmarks de alta performance – seu representante canônico é a operação de adição e multiplicação a = a + b × c. No entanto, várias outras expressões envolvendo operações aritméticas e lógicas podem ser agrupadas dentro da álgebra necessária. Nós mostramos que a eliminação em tempo de execução de tais atribuições pode ser implementada de uma maneira segura do ponto de vista de performance utilizando perfilamento in-loco. A eliminação dinâmica de expressões redundantes envolvendo identidade e elemento anulador em 35 programas da suíte de testes do LLVM é responsável por um ganho de velocidade de 1.19x (tempo total otimizado sobre tempo total não otimizado) quando comparado com o clang -O3. Quando aplicado a toda a suíte de testes (259 programas), a otimização leva a um ganho de 1.025x. Quando adicionadas ao clang, a otimização de semi anel aproxima aquele sistema de TACO, um compilador especializado de álgebra tensorial. |
Subject: | Computação – Teses Otimização – Teses Compiladores (Computadores) - Teses Anéis semilocais – Teses |
language: | eng |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/72182 |
Issue Date: | 3-Oct-2019 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
ppgccufmg_main.pdf | 2.2 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.