Resumo
Esta tese propõe uma metodologia de partição automática, que é parte integrante duma metodologia mais abrangente orientada para o desenvolvimento de sistemas embebidos predominantemente de fluxo de dados. É formulado o problema de partição, tarefa que depende da arquitectura alvo e que se integra na fase de implementação dos sistemas com múltiplos componentes de hardware e/ou de software.
A partir do levantamento sobre os meta-modelos mais utilizados em sistemas embebidos, justifica-se a selecção de PSM para representação de interface entre a tarefa de partição e a restante metodologia de desenvolvimento. Para representar os sistemas internamente ao processo de partição desenvolveu-se o meta-modelo PSMfg.
Apresenta-se a arquitectura alvo actualmente suportada pela metodologia de partição proposta, a qual é composta por uma plataforma EDgAR-2 ligada a um sistema hospedeiro.
A organização da metodologia de partição desenvolvida inclui um algoritmo de partição construtivo e a respectiva função de proximidade, um algoritmo de partição iterativo e a correspondente função de custo e os estimadores de métricas. O algoritmo construtivo gera uma solução de partição inicial, que o algoritmo iterativo procura melhorar em sucessivas tentativas.
Mostra-se como é que, partindo dum conjunto de algoritmos de partição referenciados na bibliografia, se chegou à selecção do algoritmo construtivo de crescimento de grupos e do algoritmo iterativo de pesquisa tabu.
Descreve-se o processo de construção de soluções de partição com o algoritmo construtivo de crescimento de grupos, a função de proximidade por ele utilizada e a estimação das métricas necessárias a esta função.
A adaptação do algoritmo de pesquisa tabu ao presente problema de partição é explicada, sendo de destacar a implementação dos tipos de tabu, da lista tabu, do historial de soluções visitadas, da pesquisa na subvizinhança, dos critérios de aspiração e dos mecanismos de convergência para a solução óptima e de fuga a mínimos locais. A função de custo utilizada pelo algoritmo de pesquisa tabu é definida a partir dum conjunto de métricas e dos condicionalismos ou requisitos que lhe estão associados.
Para estimar as métricas da função de custo definiram-se modelos de software para o processador, de hardware para as FPGAs e os CPLDs e de comunicação para os recursos de interligação. Para reduzir o tempo de cálculo e manter uma precisão elevada nas estimativas, a estimação é incremental e funciona em dois níveis de abstracção: (i) no nível de abstracção mais elevado, obtêm-se estimativas para o espaço ocupado pelo caminho de dados e pela unidade de controlo das partições de hardware e para o desempenho do sistema e (ii) no nível de abstracção mais baixo, obtêm-se estimativas para métricas relativas aos objectos do modelo do sistema.
A validação da metodologia de partição traduziu-se no estudo de dois exemplos: a convolução duma imagem e um algoritmo de criptografia. Os aspectos avaliados foram a qualidade das soluções de partição geradas automaticamente, a precisão e a fidelidade das estimativas, o desempenho da ferramenta desenvolvida e o apoio que presta à implementação das soluções de partição.
Palavras-chave: metodologia de partição, estimação de métricas, co-projecto de hardware e de software, sistemas digitais embebidos, algoritmo de pesquisa tabu, algoritmo de crescimento de grupos, meta-modelo PSM, meta-modelo PSMfg, FPGA, CPLD, arquitectura alvo reconfigurável.
Copyright © 2001, António J A Esteves.
Última alteração: 15 de Julho 2001