Uma metodologia de participação para o co-projecto de sistemas digitais embebidos

Abstract

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.

This thesis presents an automatic partitioning methodology included in a broader methodology oriented to the development of data flow dominated embedded systems. It is described the partitioning problem, which depends on the target architecture and is considered a crucial task to implement a system with software and several hardware components. The thesis starts with a survey of the more relevant meta-models used with embedded systems, to justify the option for PSM Lo describe the systems at the interface between the partitioning task and the remaining development methodology. A new meta-model, PSMfg, was developed as an internal way to describe the systems during the partitioning process. A target architecture is presented, based on two types of reconfigurable devices (FPGAs and CPLDs): the EDgAR-2. The prototype system contains an EDgAR-2 platform connected to a PC host system. EDgAR-2 was built Lo support the proposed partitioning methodology. The developed partitioning methodology includes a constructive partitioning algorithm and its closeness function, an iterative partitioning algorithm and its cost function and the metrics estimators. The constructive partitioning algorithm generates an initial solution that iterative algorithm tries to successively improve. A literature review on partitioning a suggested the adoption of the cluster growth constructive algorithm and the tabu search iterative algorithm, as the base foundation for the proposed methodology. The process of creating partitioning solutions with cluster growth constructive algorithm, the applied closeness function and the estimation of the metrics required by this function are presented. Tailoring the tabu search algorithm to the presented partitioning problem is detailed, with an emphasis on the implementation of the tabus, the tabu list, the visited solutions memory, the partial neighbourhood search, the aspiration criteria and the techniques that reinforce the convergence to the optimum solution and the escape from local minima of the cost function. The cost function applied by the tabu search algorithm depends on a set of metrics and on the constraints or requirements associated with these metrics. To estimate the metrics whose cost function depends on, a software model for the processor, a hardware model for the FPGAS and CPLDs and a communication model for the interconnection resources were defined. To reduce the estimation time while providing a high degree of precision, the estimation process is incremental and it is performed at two abstraction levels: (i) at the higher abstraction level, one estimates the hardware partitions data path and control unit area and the system performance and (ii) at the lower abstraction eve1, one estimates values for the system model objects metrics. The validation of the partitioning methodology was carried out through two examples: the convolution of an image and a cryptography algorithm. The quality of the automatically generated partitioning solutions, the precision and fidelity of the estimations, the performance of the developed tool and its support Lo implement the partitioning solutions were evaluated with promising results.