Aula 27: Seleção de Instruções
Objetivos
- Otimizar a seleção de instruções usando Tree Covering.
- Programação Dinâmica para custo mínimo.
Motivação
Seleção de instruções avançada é o ponto em que conhecimento da ISA (Instruction Set Architecture) é explorado ao máximo:
- Aproveita instruções complexas (CISC) ou combinadas (MAC, FMA) para reduzir ciclos.
- Explora instruções vetoriais e especializadas presentes em arquiteturas modernas de alto desempenho e embarcadas.
Conteúdo
Mapear cada operação da IR para uma sequência fixa de instruções (template) é simples mas subótimo. Seleção de instruções avançada usa o conhecimento da ISA: instruções compostas (ex.: multiply-accumulate), endereçamento e custos por instrução.
flowchart LR
IR[IR / árvore] --> Tiles[Tiles padrões]
Tiles --> Custo[Custo por tile]
Custo --> Cover[Cobertura mínima]
Cover --> Inst[Instruções]Ex: Multiply-Accumulate (MAC) faz a + b*c em 1 ciclo. Se usarmos expansão simples, geramos um MUL e um ADD (2 ciclos + latência).
Tree Covering (Cobertura de Árvore)
- Representamos a expressão IR como uma árvore.
- Temos uma biblioteca de “Tiles” (padrões), onde cada tile corresponde a uma instrução de máquina e tem um custo.
- Objetivo: Cobrir a árvore inteira gastando o menor custo acumulado.
Isso é resolvido com programação dinâmica (ou geradores como BURS): custo ótimo para cada subárvore (bottom-up) e escolha do melhor tile na raiz.
Resumo
- Tree covering: expressão como árvore; cada tile é um padrão que casa com uma subárvore e corresponde a uma instrução; objetivo é cobrir a árvore com custo total mínimo.
- Permite explorar instruções complexas (MAC, FMA) e reduzir número de instruções e ciclos.
Referências
- Aho et al. (2006); Cooper & Torczon (2011).
Materiais da aula
Última atualização: 08/03/2026