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

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.