Semiring optimization: dynamic elision of expressions with identity and absorbing elements

• Ano de defesa: 2019
• Autor(a) principal: Guilherme Vieira Leobas
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal de Minas Gerais; Brasil; ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO; Programa de Pós-Graduação em Ciência da Computação; UFMG
• Palavras-chave em Português: Compilers; Code optimization; Semiring; Code generation; Computação – Teses; Otimização – Teses; Compiladores (Computadores) - Teses; Anéis semilocais – Teses
• Link de acesso: http://hdl.handle.net/1843/72182; https://orcid.org/0000-0001-7626-5281

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.