Escalonamento e alocação de registradores sob execução condicional

Abstract

Esta dissertação descreve como resolver dois problemas clássicos da Síntese de Alto Nível, através de uma abordagem orientada à exploração de soluções alternativas. O primeiro é o problema de escalonamento de operações de um dado algoritmo sob restrição de recursos físicos, cuja solução define quando cada operação é executada, respeitando a ordem de precedência imposta pelo algoritmo. O segundo é a respectiva alocação de registradores, cuja solução determina quantos registradores são necessários no circuito digital para armazenar todos os valores produzidos por algumas operações até serem consumidos por outras. Como um algoritmo pode conter construções condicionais (ex. "if-then-else"), possivelmente aninhadas, o conceito de predicado é introduzido para permitir a modelagem de execução condicional, substituindo a tradicional noção de dependência de controle, que limita a exploração de paralelismo. Esta dissertação descreve a abordagem proposta, a modelagem que a ampara e a implementação de ferramentas que a suportam (escalonador e alocador). São apresentados resultados experimentais que se mostram promissores quando comparados aos obtidos em outras abordagens.