Algorithms for processors pipeline synthesis of embedded systems : cost, number of processors and latency minimization

Resumo: Este trabalho descreve três algoritmos para a síntese de sistemas embutidos atendendo à restrição de desempenho representada pela taxa de chegada dos dados, através de uma estrutura de pipeline de processadores para execução das tarefas, ao mesmo tempo em que minimizam diferentes parâmetros de qualidade dos sistemas: número de processadores; custo e latência total. Os algoritmos realizam o particionamento hardware-software das tarefas, a alocação dos processadores, o mapeamento e escalonamento das tarefas. A alocação de processadores e o mapeamento e escalonamento de tarefas são problemas classificados como NP-Completo e, portanto, foram aplicados métodos heurísticos para suas resoluções. Como exemplos de aplicação são apresentados os pipelines sintetizados pelos algoritmos para grafos sintéticos e para um compressor de áudio digital (AC3). Os pipelines sintetizados atingem métricas de qualidade superiores a outros algoritmos publicadosAbstract: This work presents three heuristics for sinthesizing pipelined embedded systems that satisfy a throughput constraint derived from the maximum input data are adopting a pipeline structure of processors while minimizing system quality parameters: cost, number of processors, or number of stages. The algorithms perform tasks hardware-software partitioning, processors allocation and task mapping and scheduling. Since processors allocation and task mapping and scheduling are NP-Complete problems, heuristics methods were applied. The examples present the pipelines synthesized by the algorithms for large synthetic systems comparing the quality parameters minimization results and for a real audio compressor (AC3) application. The pipelines reached quality metrics higher than other published algorithm