Fixed priority analysis for real-time multiprocessors

Abstract

MultiProcessor Systems-on-chip (MPSoCs) are versatile and powerful platforms designed to t the needs of modern embedded applications, such as radios and audio/video decoders. However, in a MPSoC running several applications simultaneously, resources must be shared while the timing constraints of each application must be met. Embedded streaming applications mapped on a MPSoC, are often modeled using data ow graphs. Data ow graphs have the expressivity and analytical properties to naturally describe concurrent digital signal processing applications. Many scheduling strategies have been analyzed using data ow models of applications, such as Time Division Multiplexing (TDM) and Non-preemptive Non-blocking Round Robin (NPNBRR). However, few approaches have focused on a preemptive Fixed Priority (FP) scheduling scheme. Fixed Priority scheduling is a simple and often used scheduling scheme. It is easy to implement in any platform and it is quite predictable under overload conditions. This dissertation studies the temporal analysis of a set of data ow modeled applications mapped on the same resources and scheduled with a xed priority scheme. Our objective is to improve the existing analysis for Single Rate Data ow (SRDF) graphs and develop the necessary concepts and techniques to extend it for applications modeled with state-of-art data ow

avor, Mode Controlled Data ow (MCDF). MCDF is a more suitable model than SRDF, since it can capture the natural dynamic behavior of modern streaming applications, and therefore, reduce the gap between model and real application. To reach our main objective we present two contributions: improvement of the existing xed priority scheduling analysis for SRDF and a complete temporal analysis technique for MCDF graphs. We propose a novel method, for a general case of a set of n graphs, to determine the worst-case response time of a low priority task by characterizing the worst-case load that higher priority tasks generated on the processor. We also demonstrate, that in the case of graphs that exhibit a single dominant periodic/sporadic source, it is possible optimize the analysis for tighter results. We validate and compare our analysis with the current state-of-art technique for periodic streaming applications, and conclude that, for all the experimented graphs, our analysis always provides tighter results. Furthermore, we propose an implementation of a complete and optimal temporal analysis technique for MCDF graphs that is based on a nite state machine description of the graphs dynamic behavior. We propose solutions to include in the analysis speci c properties of MCDF graph, such as pipelining execution and intermodal dependencies. Despite being limited to time bounded and strongly connected graphs, results obtained using this analysis are as good or better than any currently used temporal analysis technique.

Os sistemas multiprocessadores (MultiProcessor Systems-on-Chip (MPSoCs)) são plataformas versáteis e potentes desenhadas especialmente para satisfazer as necessidades de aplicações de streaming, como rádios e descodificadores de áudio/vídeo. Contudo, quando se executam várias aplicações em simultâneos num MPSoC, os recursos têm de ser partilhados entre aplicações, ao mesmo tempo que os requisitos temporais de cada aplicação têm de ser cumpridos. As aplicações de streaming mapeadas num MPSoC, são usualmente modeladas usando modelos de computação dataflow. Estes modelos possuem a expressividade e propriedades analíticas necessárias para representar idealmente aplicações de processamento digital de sinal. Até hoje, foram analisados alguns esquemas de escalonamento em modelos de computação dataflow, como Time Division Multiplexing (TDM) e Nonpreemptive Non-blocking Round Robin (NPNBRR). No entanto, poucas tentativas foram feitas no sentido de estudar escalonamentos de prioridade fixa. O escalonamento de prioridade fixa é simples e popular, visto que é de fácil implementação e o seu comportamento em condições de sobrecarga é previsível. Esta dissertação estuda a análise temporal de um conjunto de aplicações modeladas com grafos dataflow, quando mapeadas nos mesmos recursos e escalonadas com um esquema de prioridade fixa. O nosso objectivo é melhorar a análise existente para grafos do tipo Single Rate Dataflow (SRDF) e desenvolver os conceitos e as técnicas necessárias para realizar esta análise utilizando um tipo de dataflow de estado-de-arte, o Mode Controlled Dataflow (MCDF). Os grafos MCDF são mais adequados como modelos de aplicações streaming, visto que conseguem capturar o seu comportamento dinâmico, e consequentemente, reduzir a diferença entre modelo e aplicação real. Para atingir o objectivo apresentamos duas contribuições: melhoramos a análise de escalonamentos de prioridade fixa existente para grafos SRDF e apresentamos uma técnica de análise temporal completa para grafos MCDF. Nesta dissertação apresentamos um método inovador, para o caso genérico de n grafos, para determinar o tempo de resposta máximo de uma tarefa de baixa prioridade, através da caracterização de carga máxima imposta num processador pelas tarefas de mais alta prioridade. Demonstramos ainda, que no caso particular de grafos com fontes dominantes, periódicas ou esporadicamente periódicas, é possível optimizar a análise para obter melhores resultados. A análise é ainda validada e comparada com o actual estado-de-arte, constatando-se que para todos os testes realizados a nossa análise apresenta melhores resultados. Propomos ainda, uma implementação de uma análise temporal completa e óptima para grafos de dataflow do tipo MCDF, baseada na descrição do comportamento dinâmico dos grafos através de uma máquina de estados finitos. Apresentamos soluções para incluir na análise características específicas dos grafos MCDF, como execuções paralelas de tarefas e dependências intermodais. Apesar de limitada a grafos fortemente ligados, os resultados obtidos são iguais ou melhores que os de análises utilizadas actualmente.