Pior caso de tempo de execução - Worst-case execution time

O pior caso de tempo de execução ( WCET ) de uma tarefa computacional é o tempo máximo que a tarefa pode levar para ser executada em uma plataforma de hardware específica .

Para que é usado

O tempo de execução do pior caso é normalmente usado em sistemas confiáveis de tempo real , onde entender o comportamento do tempo do software no pior caso é importante para a confiabilidade ou o comportamento funcional correto.

Por exemplo, um sistema de computador que controla o comportamento de um motor em um veículo pode precisar responder às entradas em um determinado período de tempo. Um componente que compõe o tempo de resposta é o tempo gasto na execução do software - portanto, se o tempo de execução do pior caso do software pode ser determinado, o designer do sistema pode usar isso com outras técnicas, como análise de escalonabilidade para garantir que o sistema responda rápido o suficiente.

Embora o WCET seja potencialmente aplicável a muitos sistemas de tempo real, na prática, uma garantia do WCET é usada principalmente por sistemas de tempo real relacionados à alta confiabilidade ou segurança. Por exemplo, em software aerotransportado, alguma atenção ao software é exigida pelo DO178B seção 6.3.4. O crescente uso de software em sistemas automotivos também está levando à necessidade de usar a análise WCET de software.

No projeto de alguns sistemas, WCET é frequentemente usado como uma entrada para a análise de escalonabilidade , embora um uso muito mais comum de WCET em sistemas críticos é garantir que os orçamentos de tempo pré-alocados em um sistema de partição programada como ARINC 653 sejam não violado.

Cálculo

Desde os primeiros dias da computação embarcada, os desenvolvedores de software embarcado têm usado:

  • medições de ponta a ponta do código, por exemplo, realizadas definindo um pino de I / O no dispositivo para alto no início da tarefa e para baixo no final da tarefa e usando um analisador lógico para medir o pulso mais longo largura, ou medindo dentro do próprio software usando o relógio do processador ou contagem de instruções.
  • técnicas manuais de análise estática, como contar instruções do montador para cada função, loop etc. e, em seguida, combiná-las.

Ambas as técnicas têm limitações. As medições de ponta a ponta colocam uma grande carga nos testes de software para alcançar o caminho mais longo; as instruções de contagem só se aplicam a software e hardware simples. Em ambos os casos, uma margem de erro é freqüentemente usada para contabilizar código não testado, aproximações de desempenho de hardware ou erros. Uma margem de 20% é freqüentemente usada, embora haja muito pouca justificativa usada para este número, exceto para a confiança histórica ("funcionou da última vez").

Conforme o software e o hardware aumentaram em complexidade, eles geraram a necessidade de suporte de ferramenta. A complexidade está se tornando cada vez mais um problema tanto na análise estática quanto nas medições. É difícil julgar quão ampla deve ser a margem de erro e quão bem testado é o sistema de software. Os argumentos de segurança do sistema com base em uma marca d'água alta alcançada durante o teste são amplamente usados, mas se tornam mais difíceis de justificar à medida que o software e o hardware se tornam menos previsíveis.

No futuro, é provável que um requisito para sistemas críticos de segurança seja que eles sejam analisados ​​usando abordagens estáticas e baseadas em medição.

Considerações

O problema de encontrar WCET por análise é equivalente ao problema da parada e, portanto, não tem solução em geral. Felizmente, para o tipo de sistema para o qual os engenheiros normalmente desejam encontrar o WCET, o software é normalmente bem estruturado, sempre será encerrado e pode ser analisado.

A maioria dos métodos para encontrar um WCET envolve aproximações (geralmente um arredondamento para cima quando há incertezas) e, portanto, na prática, o WCET exato em si é frequentemente considerado como inalcançável. Em vez disso, diferentes técnicas para encontrar o WCET produzem estimativas para o WCET. Essas estimativas são tipicamente pessimistas, o que significa que o WCET estimado é conhecido por ser maior do que o WCET real (que geralmente é o desejado). Muito trabalho na análise WCET consiste em reduzir o pessimismo na análise de forma que o valor estimado seja baixo o suficiente para ser valioso para o projetista do sistema.

A análise WCET geralmente se refere ao tempo de execução de uma única thread, tarefa ou processo. No entanto, em hardware moderno, especialmente multi-core, outras tarefas no sistema terão impacto no WCET de uma determinada tarefa se compartilharem cache, linhas de memória e outros recursos de hardware. Além disso, eventos de agendamento de tarefas, como bloqueio ou interrupções, devem ser considerados na análise WCET, se puderem ocorrer em um sistema específico. Portanto, é importante considerar o contexto em que a análise WCET é aplicada.

Abordagens automatizadas

Existem muitas abordagens automatizadas para calcular WCET além das técnicas manuais acima. Esses incluem:

  • técnicas analíticas para melhorar os casos de teste para aumentar a confiança nas medições de ponta a ponta
  • análise estática do software (significado “estático” sem executar o software).
  • abordagens combinadas, muitas vezes referidas como análise "híbrida", sendo uma combinação de medições e análise estrutural

Técnicas de análise estática

Uma ferramenta WCET estática tenta estimar o WCET examinando o software do computador sem executá-lo diretamente no hardware. As técnicas de análise estática dominaram a pesquisa na área desde o final dos anos 1980, embora em um ambiente industrial, as abordagens de medição de ponta a ponta fossem a prática padrão.

As ferramentas de análise estática funcionam em alto nível para determinar a estrutura da tarefa de um programa , trabalhando em uma parte do código-fonte ou em um executável binário desmontado . Eles também funcionam em um nível inferior, usando informações de tempo sobre o hardware real no qual a tarefa será executada, com todos os seus recursos específicos. Ao combinar esses dois tipos de análise, a ferramenta tenta fornecer um limite superior no tempo necessário para executar uma determinada tarefa em uma determinada plataforma de hardware.

No nível inferior, a análise WCET estática é complicada pela presença de recursos arquitetônicos que melhoram o desempenho de caso médio do processador : caches de instrução / dados , previsão de desvio e pipelines de instrução , por exemplo. É possível, mas cada vez mais difícil, determinar limites estreitos de WCET se esses recursos arquitetônicos modernos forem levados em consideração no modelo de tempo usado pela análise.

As autoridades de certificação, como a Agência Europeia para a Segurança da Aviação , portanto, contam com pacotes de validação de modelo.

A análise estática resultou em bons resultados para hardware mais simples, no entanto, uma possível limitação da análise estática é que o hardware (a CPU em particular) atingiu uma complexidade extremamente difícil de modelar. Em particular, o processo de modelagem pode introduzir erros de várias fontes: erros no design do chip, falta de documentação, erros na documentação, erros na criação do modelo; todos levando a casos em que o modelo prevê um comportamento diferente daquele observado no hardware real. Normalmente, onde não é possível prever com precisão um comportamento, um resultado pessimista é usado, o que pode fazer com que a estimativa WCET seja muito maior do que qualquer coisa alcançada em tempo de execução.

Obter estimativas estáticas de WCET é particularmente difícil em processadores multi-core.

Existem várias ferramentas comerciais e acadêmicas que implementam várias formas de análise estática.

Medição e técnicas híbridas

As abordagens baseadas em medição e híbridas geralmente tentam medir os tempos de execução de segmentos de código curto no hardware real, que são então combinados em uma análise de nível superior. As ferramentas levam em consideração a estrutura do software (por exemplo, loops, ramificações), para produzir uma estimativa do WCET do programa maior. O raciocínio é que é difícil testar o caminho mais longo em um software complexo, mas é mais fácil testar o caminho mais longo em muitos componentes menores dele. Um efeito de pior caso só precisa ser visto uma vez durante o teste para que a análise seja capaz de combiná-lo com outros eventos de pior caso em sua análise.

Normalmente, as pequenas seções do software podem ser medidas automaticamente usando técnicas como instrumentação (adicionando marcadores ao software) ou com suporte de hardware como depuradores e módulos de rastreamento de hardware de CPU. Esses marcadores resultam em um traço de execução, que inclui o caminho percorrido no programa e o momento em que os diferentes pontos foram executados. O rastreamento é então analisado para determinar o tempo máximo que cada parte do programa levou para executar, qual é o tempo máximo de iteração observado de cada loop e se há alguma parte do software que não foi testada ( cobertura de código ).

A análise WCET baseada em medição resultou em bons resultados para hardware simples e complexo, embora, como a análise estática, possa sofrer pessimismo excessivo em situações de múltiplos núcleos, onde o impacto de um núcleo sobre o outro é difícil de definir. Uma limitação da medição é que ela depende da observação dos efeitos do pior caso durante o teste (embora não necessariamente ao mesmo tempo). Pode ser difícil determinar se os efeitos do pior caso foram necessariamente testados.

Existem várias ferramentas comerciais e acadêmicas que implementam várias formas de análise baseada em medição.

Pesquisar

Os grupos de pesquisa mais ativos estão na Suécia (Mälardalen, Linköping), Alemanha (Saarbrücken, Dortmund, Braunschweig), França (Toulouse, Saclay, Rennes), Áustria (Viena), Reino Unido (Universidade de York e Rapita Systems Ltd), Itália ( Bolonha), Espanha (Cantábria, Valência) e Suíça (Zurique). Recentemente, o tópico da análise de tempo em nível de código recebeu mais atenção fora da Europa por grupos de pesquisa nos EUA (Carolina do Norte, Flórida), Canadá, Austrália, Bangladesh (MBI LAB e RDS), Reino da Arábia Saudita-UQU (HISE LAB) e Cingapura.

Desafio da ferramenta WCET

O primeiro WCET Tool Challenge internacional ocorreu durante o outono de 2006. Foi organizado pela Universidade de Mälardalen e patrocinado pela Rede de Excelência em Design de Sistemas Embarcados ARTIST2. O objetivo do Desafio era inspecionar e comparar diferentes abordagens na análise do tempo de execução do pior caso. Todas as ferramentas e protótipos disponíveis capazes de determinar limites superiores seguros para o WCET das tarefas participaram. Os resultados finais foram apresentados em novembro de 2006 no Simpósio Internacional ISoLA 2006 em Paphos , Chipre.

Um segundo Desafio ocorreu em 2008.

Veja também

Referências

  1. ^ " O problema de tempo de execução de pior caso - visão geral de métodos e pesquisa de ferramentas ", Wilhelm, Reinhard, et al., ACM Transactions on Embedded Computing Systems (TECS), Vol. 7, No. 3, 2008.
  2. ^ "Cópia arquivada" (PDF) . Arquivado do original (PDF) em 01-10-2011 . Página visitada em 2010-08-15 .CS1 maint: cópia arquivada como título ( link )
  3. ^ "Cópia arquivada" . Arquivado do original em 16/02/2012 . Página visitada em 2008-08-16 .CS1 maint: cópia arquivada como título ( link )

Artigos e white papers

links externos