A APLICAÇÃO DE ALGORITMOS GENÉTICOS PARA SÍNTESE DE ALTO NÍVEL

^[1] 

A APLICAÇÃO DE ALGORITMOS GENÉTICOS PARA SÍNTESE DE ALTO NÍVEL

Thiago Lopes Amaral

Resumo— Com o desenvolvimento tecnológico houve o aumento na demanda para desenvolvimento de Circuitos Integrados de Grande Escala (VLSI – Very Large-Scale Integrated) mais complexos, tornando necessária a utilização de ferramentas para o projeto de circuitos com níveis mais altos de abstração. O emprego da síntese de alto nível possibilita a geração de uma rede digital a partir da discrição funcional do circuito, podendo ser inseridas restrições desejadas. A síntese de alto nível apresenta como principais dificuldades o escalonamento e a alocação, pela sua alta complexidade de solução. Existem diversos modos alternativos para alocações e escalonamentos eficientes e de boa qualidade dentro de um tempo otimizado. Nesse trabalho serão apresentadas de forma comparativa as vantagens e desvantagens da aplicação do algoritmo probabilístico chamado de algoritmo genético para a construção de escalonamento que em um tempo aceitável apresente uma solução ótima.

Palavras-chave — Algoritmo de escalonamento, VLSI, Síntese de alto nível, Algoritmos Genéticos.

1. Introdução

A

  síntese de alto nível possibilita gerar automaticamente uma rede digital a partir de uma descrição funcional de alto nível de um circuito, combinada com a possibilidade de usar restrições e objetivos. Resulta em um chamado data-path e uma descrição do controlador. O data-path consiste em blocos de construção, composto por unidades funcionais, memória e uma estrutura de interconexão entre eles. O controlador descreve como o fluxo de dados dentro do data-path é gerenciado e é descrito em termos de estados e transições de estado. A descrição do controlador é traduzida para uma implementação no nível de abstração das portas usando a síntese lógica.

Os blocos de construção dentro de um data-path são criados usando os chamados geradores de módulos. A funcionalidade desejada pode ser descrita por funções booleanas, e a síntese lógica pode ser usada para otimizar e mapear as equações em uma biblioteca de portas, chamada geração comportamental.

Os principais problemas na síntese de alto nível são o escalonamento (determinando a etapa do ciclo em que as tarefas específicas da descrição funcional iniciam sua execução) e alocação (determinando a quantidade de unidades de hardware necessárias para implementar a especificação funcional). O escalonamento e a alocação pertencem à classe de problemas que são difíceis de resolver durante a prática de síntese de alto nível. Portanto, estratégias de escalonamento e alocação eficientes são necessárias, capazes de produzir soluções de boa qualidade em relação aos objetivos e de contornar as restrições gerando dentro de um prazo temporal aceitável.

                        Os algoritmos genéticos são algoritmos de busca probabilísticos inspirados no princípio da "sobrevivência do mais apto", derivado da teoria da evolução descrita por Charles Darwin em “A origem das espécies” (The Origin of Species). Os algoritmos genéticos mantêm uma coleção de soluções potenciais, que evoluem de acordo com uma medida que reflete a qualidade das soluções. O processo de evolução de um algoritmo genético funciona em uma codificação do espaço de busca, representada por um cromossomo.

Os algoritmos genéticos podem ser usados para pesquisar soluções de boa qualidade em relação ao problema de escalonamento e alocação, buscando uma permutação que resulte em uma solução de boa qualidade. O método pode ser empregado a fim de obter-se uma convergência eficiente.

Diante do exposto, o estudo de Heijligers (1996) teve por objetivo utilizar algoritmos genéticos a fim de encontrar resultados de boa qualidade para o problema de escalonamento.

1. Materiais e Métodos

Inicialmente Heijligers (1996) propôs melhorar os resultados produzidos por heurísticas de escalonamento existentes e reduzir o tempo de execução de métodos de busca exaustivos. O autor considerou dois problemas de escalonamento como problemas principais a serem driblados: tempo limitado e escalonamento de recursos restritos.

Vários métodos foram apresentados para determinar o intervalo de operações da programação viável. A ideia central foi utilizar relações de distância a partir de um gráfico de distância, para determinar o intervalo de operações de horário possível em relação a outras operações.

As restrições de tempo foram incorporadas adicionando relações de distância a um gráfico de distância obtido a partir de um gráfico de fluxo de dados. Os algoritmos de caminho mais longo dos pares foram usados ​​para construir uma matriz de distância a partir de um gráfico de distância, conforme demonstrado na Figura 1. Este processo é usado para determinar e atualizar intervalos de operações possíveis de operações de forma muito eficiente.

As restrições de recursos foram usadas para reduzir os intervalos de operações possíveis, usando a análise do intervalo de execução do módulo.

Posteriormente os algoritmos genéticos foram aplicados para procurar permutações de operações, que fornecem um mecanismo para classificar a maneira como os escalonadores constroem sua solução. Foram apresentados escalonadores de algoritmos exatos, algoritmo de aproximação e algoritmo Eurístíco.

Mostrou-se que Algoritmos exatos requerem altos níveis de processamento e tempo, porém apresentam soluções ótimas, já os algoritmos de aproximação apresentam menor incidência de soluções ótimas e ainda assim requerem um alto tempo e processamento. Os algoritmos Eurísticos apresentam uma resposta rápida com baixa requisição de processamento, porém não existe a garantia de uma solução ótima.

Foi apresentada uma classificação de métodos construtivos de escalonamento de síntese de alto nível, com base nas permutações de operações. Esta classificação mostra algumas vantagens de construir um escalonamento de maneira topologicamente ordenada, pois em muitos casos impede a criação de soluções intransitáveis ​​e o esforço de busca pode ser orientado para encontrar soluções de boa qualidade em vez de encontrar soluções viáveis.

[pic 1]

Fig 1. Esquemático de escalonamento

Os métodos apresentados podem ser considerados como um mecanismo para traduzir uma permutação de operações em um escalonamento. A busca de um escalonamento ideal é definida como a busca de uma permutação para o qual o método de escalonamento ira retornar uma solução ótima. No entanto, estratégias heurísticas simples muitas vezes não conseguem encontrar soluções de boa qualidade.