Alguns Experimentos em Compactação de Microcódigo Local para Máquinas Horizontais

A compactação de microcódigo é uma ferramenta essencial para a compilação de microprogramas de linguagem de alto nível em microinstruções com microoperações paralelas. O objetivo da pesquisa relatada neste artigo é comparar quatro métodos de compactação de microcódigo encontrados na literatura: primeiro a chegar, primeiro a ser servido, caminho crítico, ramificação e limite, e agendamento em lista. Para isso, foi necessário desenvolver um método completo, independente da máquina, de representar as microoperações de máquinas reais; e os algoritmos de compactação tiveram que ser reformulados para usar essa representação. Os algoritmos de compactação foram então implementados e testados em microcódigo produzido por um compilador para uma linguagem de microprogramação de alto nível. Os resultados desses experimentos indicaram que, em todos os casos examinados, os algoritmos de primeiro a chegar e de agendamento em lista produziram microcódigo compactado em um número mínimo de microinstruções em um tempo que era uma função polinomial de ordem dois do número de microoperações de entrada.