ALUPAS: UM SIMULADOR ESTOCASTICO¶ PARA …tg/2008-2/bcsn.pdf · para obten»c~ao do grau de Bacharel em Engenharia da ... 5.1 Assembler ... cotidiano e exemplos destes sistemas podem

Universidade Federal de PernambucoCentro de Informatica

Graduacao em Engenharia da Computacao

ALUPAS: UM SIMULADOR ESTOCASTICOPARA ANALISE DO CONSUMO DE

ENERGIA E DESEMPENHO DE SOFTWAREPARA SISTEMAS EMBARCADOS

Bruno Costa e Silva Nogueira

TRABALHO DE GRADUACAO

Recife1 de dezembro de 2008

Universidade Federal de PernambucoCentro de Informatica

Bruno Costa e Silva Nogueira

ALUPAS: UM SIMULADOR ESTOCASTICO PARA ANALISE DOCONSUMO DE ENERGIA E DESEMPENHO DE SOFTWARE

PARA SISTEMAS EMBARCADOS

Trabalho apresentado ao Programa de Graduacao em En-

genharia da Computacao do Centro de Informatica da Uni-

versidade Federal de Pernambuco como requisito parcial

para obtencao do grau de Bacharel em Engenharia da

Computacao.

Orientador: Paulo Romero Martins Maciel

Recife1 de dezembro de 2008

Dedico a minha famılia.

AGRADECIMENTOS

Agradeco primeiramente aos meus pais, por tudo. Agradeco tambem ao pessoal doMoDCS, com quem convivi nos ultimos dois anos e que me ajudaram muito, em es-pecial, meu orientador Prof. Paulo Maciel, Gustavo Callou e Ermeson Carneiro. E quevenha o mestrado! Agradeco tambem aos amigos que fiz na graduacao, principalmenteo companheiro de todas as horas Eduardo Fonseca. Um agradecimento especial a minhanamorada, Renata Veras, pela ajuda e compreensao.

iv

RESUMO

Com a proliferacao de equipamentos portateis operados por baterias, o projeto de sistemasembarcados de baixo consumo de energia tem despertado muito interesse nos ultimosanos. A fim de atender aos requisitos de baixo consumo de energia, e essencial dispor,ainda nas fases iniciais de desenvolvimento, de mecanismos que auxiliem de forma rapidae precisa a analise de possıveis alternativas de projeto. Este trabalho apresenta ALUPAS,um simulador estocastico baseado nas Redes de Petri Coloridas (CPN) para estimar odesempenho e consumo de energia de softwares para sistemas embarcados. Os resulta-dos dos experimentos mostram uma exatidao em media de 94% utilizando o simuladorproposto em comparacao aos valores reais medidos no hardware.

Palavras-chave: Simulacao, Sistemas Embarcados, Redes de Petri Coloridas, Avaliacaode Desempenho

v

ABSTRACT

Due to the widespread expansion of battery operated mobile devices, the low powerdesign of embedded system has been gaining close attention in recent years. In order toattend the low power requirements, it is essential, in earlier phases of design, to count onfast and accurate mechanisms to help the analysis of possible design alternatives. Thiswork presents ALUPAS, a stochastic simulator based on Coloured Petri Nets (CPN)for performance and energy consumption estimating of embedded system applications.Experiment results have demonstrated an average accuracy of 94% using the proposedsimulator in comparison with the real values measured on hardware.

Keywords: Simulation, Embedded Systems, Coloured Petri Nets, Performance Evalu-ation

vi

SUMARIO

Capıtulo 1—Introducao 1

1.1 Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Trabalhos relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Estrutura do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Capıtulo 2—Fundamentos 6

2.1 Estimativa de desempenho e consumo de energia . . . . . . . . . . . . . . 62.2 Modelos de simulacao e simulacao estocastica . . . . . . . . . . . . . . . 72.3 Processos estocasticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4 Redes de Petri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.5 Redes de Petri Coloridas (Coloured Petri Nets - CPN ) . . . . . . . . . . 12

2.5.1 Reducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Capıtulo 3—Metodologia de desenvolvimento para sistemas embarcados - MEM-BROS 16

Capıtulo 4—Modelo da simulacao 19

4.1 Modelo proposto: modelos basicos e composicao dos modelos basicos . . 194.2 Processo de reducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.3 Parametros da simulacao e analise dos resultados . . . . . . . . . . . . . 24

4.3.1 Consideracoes finais . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Capıtulo 5—ALUPAS 27

5.1 Assembler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.2 Compilador Binario-CPN . . . . . . . . . . . . . . . . . . . . . . . . . . . 285.3 Simulador-CPN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.4 GUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.5 Integracao dos componentes . . . . . . . . . . . . . . . . . . . . . . . . . 31

5.5.1 Consideracoes finais . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Capıtulo 6—Experimentos 34

6.1 Experimento 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346.1.1 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

vii

SUMARIO viii




6.5 Experimento 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416.5.1 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436.5.2 Consideracoes finais . . . . . . . . . . . . . . . . . . . . . . . . . . 45

Capıtulo 7—Conclusao 47

Apendice A—Caracterizacao do microprocessador 54

LISTA DE FIGURAS

1.1 Visao geral dos nıveis de abstracao. Retirado de [Bose et al. 2001]. . . . 3

2.1 Elementos de uma Rede de Petri: (a)Lugar, (b)Transicao, (b)Arco, (d)Token. 102.2 Exemplo de uma Rede de Petri . . . . . . . . . . . . . . . . . . . . . . . 102.3 Problema do jantar dos filosofos modelado em uma CPN. . . . . . . . . . 142.4 Exemplo de reducao preservando muitas das propriedades dinamicas da

rede. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.1 Diagramas de atividade da metodologia. . . . . . . . . . . . . . . . . . . 16

4.1 Modelo de instrucao ordinaria. . . . . . . . . . . . . . . . . . . . . . . . . 194.2 Modelo de desvio condicional. . . . . . . . . . . . . . . . . . . . . . . . . 204.3 Modelo de desvio com retorno . . . . . . . . . . . . . . . . . . . . . . . . 214.4 Modelo de retorno para instrucoes de desvio com retorno . . . . . . . . . 214.5 Trecho de codigo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.6 Modelo CPN do fluxo de controle: composicao dos modelos basicos. . . . 224.7 (a)Trecho de um exemplo de modelo, (b)Trecho do mesmo exemplo, depois

do processo de reducao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

5.1 Assembler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.2 Compilador Binario-CPN. . . . . . . . . . . . . . . . . . . . . . . . . . . 285.3 Simulador-CPN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295.4 Algoritmo de simulacao. . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.5 Interface de entrada do ALUPAS. . . . . . . . . . . . . . . . . . . . . . . 315.6 Interface de saıda do ALUPAS. . . . . . . . . . . . . . . . . . . . . . . . 325.7 (a)Menu File, (b)Menu Project, (c)Menu Help. . . . . . . . . . . . . . . . 325.8 Componentes integrados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

6.1 Codigo do experimento 1. . . . . . . . . . . . . . . . . . . . . . . . . . . 356.2 Comparativo entre o CPN Tools e ALUPAS. . . . . . . . . . . . . . . . . 366.3 Codigo do assembly anotado do Busca Binaria. . . . . . . . . . . . . . . 376.4 Busca Binaria na linguagem C. . . . . . . . . . . . . . . . . . . . . . . . 386.5 Busca Binaria - Tempo de execucao: estimado x medido. . . . . . . . . . 396.6 Busca Binaria - Consumo de energia: estimado x medido. . . . . . . . . . 396.7 Consumo de energia: pior caso. . . . . . . . . . . . . . . . . . . . . . . . 406.8 Tempo de execucao: pior caso. . . . . . . . . . . . . . . . . . . . . . . . . 406.9 BCNT - Tempo de execucao: estimado x medido. . . . . . . . . . . . . . 416.10 BCNT - Consumo de energia: estimado x medido. . . . . . . . . . . . . . 41

ix

LISTA DE FIGURAS x

6.11 Estrutura do Oxımetro de Pulso, retirado de [Junior 1998]. . . . . . . . . 42

A.1 Esquema de medicao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54A.2 Tela do Agilent DS0302A durante o processo de medicao. . . . . . . . . . 55A.3 Exemplo de codigo para medicao. . . . . . . . . . . . . . . . . . . . . . . 55

LISTA DE TABELAS

2.1 Clientes de Banco em um Sistema de Fila de Atendente Unico . . . . . . 82.2 Interpretacoes para os lugares e transicoes. Retirado de [Murata 1989] . . 11

6.1 Comparativo dos resultados para o exemplo 1. . . . . . . . . . . . . . . . 356.2 Comparativo do tempo de simulacao. . . . . . . . . . . . . . . . . . . . . 366.3 Resultados do exemplo 5 - Oxımetro de Pulso. . . . . . . . . . . . . . . . 436.4 Excitacao - comparacao do tempo de execucao. . . . . . . . . . . . . . . 446.5 Excitacao - comparacao do consumo de energia. . . . . . . . . . . . . . . 446.6 Amostragem - comparacao do tempo de execucao. . . . . . . . . . . . . . 446.7 Amostragem - comparacao do consumo de energia. . . . . . . . . . . . . 446.8 Controle - comparacao do tempo de execucao. . . . . . . . . . . . . . . . 456.9 Controle - comparacao do consumo de energia. . . . . . . . . . . . . . . . 45

xi

CAPITULO 1

INTRODUCAO

Este Capıtulo prove uma breve introducao aos sistemas embarcados, destacando as prin-cipais restricoes a serem consideradas no desenvolvimento de projetos para estes sistemas,alem de ressaltar a atual necessidade de baixo consumo de energia em grande parte detais projetos. A Secao 1.2 apresenta os objetivos deste trabalho. A Secao 1.3 apresentaos trabalhos relacionados. E por fim, a Secao 1.4 resume o que sera visto nos outrosCapıtulos deste trabalho.

1.1 CONTEXTO

Sistemas embarcados sao sistemas de computacao dedicados a realizar um determinadoconjunto pre-estabelecido de tarefas, como monitorar e/ou controlar os ambientes nosquais estao inseridos. Eles estao presentes em praticamente todas as areas do nossocotidiano e exemplos destes sistemas podem ser encontrados nos celulares, microondas,alarmes e players de mp3. Com o surgimento de novas tecnologias e metodologias dedesenvolvimento, a presenca de tais sistemas em nossas vidas tende a crescer cada vezmais. Em [Krishnan 2005], o mercado mundial de sistemas embarcados foi avaliado em$ 45,9 bilhoes em 2004, com previsao de dobrar e chegar a $ 88,8 bilhoes em 2009.

Tipicamente os sistemas embarcados sao de tempo-real [Shaw 2000] e apresentam umaserie de restricoes, tais como: baixa capacidade de memoria, fonte de energia, baixo pro-cessamento, dentre outras. Com a proliferacao de equipamentos portateis operados porbaterias, o projeto de sistemas embarcados de baixo consumo de energia tem despertadomuito interesse nos ultimos anos. O maior problema e que a evolucao da tecnologia dasbaterias nao vem acompanhado a crescente demanda por maior autonomia e mais de-sempenho nestes dispositivos [Jayaseelan et al. 2006b]. Alem dos aspectos relacionadosa demanda do mercado, a propria evolucao das tecnologias dos sistemas semicondutores,em funcao da maior funcionalidade que se coloca por unidade de area dos circuitos inte-grados, tem levado ao crescimento constante da potencia dissipada destes sistemas.

Frequentemente a otimizacao do consumo de energia em projetos de sistemas embar-cados e feita atraves do uso de prototipos. A utilizacao de prototipos prove resultadoscom bastante exatidao para o consumo de energia de um projeto, porem o custo de umprototipo e o tempo despendido para a sua criacao torna impossıvel a analise de todas aspossıveis solucoes em produto comercial. Isso dificulta a tomada de decisao do projetista.Neste contexto, a simulacao e uma interessante alternativa ao uso de prototipos, pois ebarata, rapida e os resultados sao tao exatos quanto se queira.

Os metodos de estimativa do consumo de energia utilizando simulacao podem ser clas-sificados em: (i) um metodo onde as estimativas sao realizadas atraves de um modelo dohardware da arquitetura alvo, e (ii) um segundo metodo onde as estimativas sao baseadas

1

1.2 OBJETIVOS 2

em medicoes previamente feitas no proprio hardware [Nikolaidis and Neofotistos 2002]. Aexatidao das analises feitas atraves do primeiro metodo depende da precisao do modeloutilizado. No entanto, e difıcil construir um modelo com razoavel exatidao, devido aoaumento da complexidade das arquiteturas atuais. Outra dificuldade e a necessidade dese ter acesso a detalhes da tecnologia de implementacao do hardware que constituem,normalmente, propriedades intelectuais. As estimativas feitas pelo segundo metodo saoconsideradas mais exatas, pois os dados sao gerados diretamente pelo proprio hardware.Apesar de existirem varios trabalhos que utilizam tais metodos, ate onde o autor conhece,poucos utilizam uma abordagem formal para a simulacao.

De acordo com [Sangiovanni-Vincentelli and Martin 2001], nos dias atuais, 80% deum sistema embarcado convencional e composto por software. A utilizacao de softwareem comparacao a componentes de hardware possui diversas vantagens, pois software ebarato e mais flexıvel. Isso e conveniente quando sao necessarias mudancas de projetono final do ciclo de desenvolvimento e, tambem, nas fases de manutencao do projeto.Uma vez que grande parte das funcionalidades dos sistemas embarcados e implementadapor software, o consumo de energia devido ao software pode ter uma grande influenciano consumo total do projeto. Isso faz com que ainda nas fases iniciais de projeto, sejaessencial analisar de forma rapida e exata este consumo a fim de otimizar e, tambem,reduzir os riscos do projeto vir a ser mal sucedido.

1.2 OBJETIVOS

O objetivo deste trabalho e a criacao de um simulador, denominado ALUPAS, paraestimar o desempenho (tempo de execucao) e consumo de energia de softwares parasistemas embarcados de tempo-real com restricoes de consumo de energia. Um modeloformal de simulacao baseado nas Redes de Petri Coloridas (CPN - Coloured Petri Nets)[Jensen 1992] sera adotado.

A escolha das CPN para modelagem e justificada por elas possuırem as seguintescaracterısticas: (i) formalismo, atraves de um consolidado conjunto de regras; (ii) rep-resentacao grafica, facilitando a cognicao do modelo; (iii) representacao hierarquica, su-portando modelos complexos; (iv) unir funcionalidades semelhantes as das linguagens deprogramacao [Wells 2002]. Dado o codigo fonte do software (com anotacoes sobre seucomportamento em um formato pre-definido) a ser avaliado, ALUPAS gera um modeloCPN do codigo e simula estocasticamente tal modelo com a finalidade de estimar o tempode execucao e consumo de energia do software.

O alvo deste trabalho e o LPC2106 [Semiconductors ] um microprocessador da famıliaARM7 largamente utilizado em projetos de baixo consumo de energia. No entanto, asmetodologias aqui propostas nao se restringem somente a tal microprocessador. Estudosde caso serao realizados neste microprocessador com o intuito de validar os modelospropostos. Uma vez validados, o simulador sera utilizado para avaliar um estudo de casoreal.

1.3 TRABALHOS RELACIONADOS 3

1.3 TRABALHOS RELACIONADOS

O projeto de sistemas embarcados de baixo consumo pode ser classificado nos seguintesnıveis de abstracao [Bose et al. 2001]:

� Nıvel de aplicacao/sistema - o consumo de energia para executar uma aplicacao eum sistema operacional em particular pode ser reduzidos neste nıvel.

� Nıvel de algoritmo/comportamental - neste nıvel o consumo de energia e reduzidoatraves da analise do consumo de energia de diferentes algoritmos para resolver umdeterminado problema.

� Nıvel de arquitetura - aqui o consumo de energia nas caches e barramentos, porexemplo, sao analisados e otimizados.

� Nıvel logico - neste nıvel o estilo e a funcao do circuito sao definidos. Existem variosestilos de projeto, cada um com seus pros e contras.

� Nıvel de transistores - este e o nıvel mais baixo de abstracao. Existem tecnicasespecıficas neste nıvel para limitar o consumo de energia como, por exemplo, areordenacao de transistores.

A Figura 1.1 exibe uma visao geral dos nıveis de abstracao mencionados e faz umacomparacao com relacao a velocidade de analise, exatidao, capacidade, recursos e reducaodo consumo.

Figura 1.1 Visao geral dos nıveis de abstracao. Retirado de [Bose et al. 2001].

Ao longo dos ultimos anos, varias metodologias para estimar o consumo de ener-gia tem sido desenvolvidas, no entanto, poucas destas metodologias foram associadasa uma ferramenta. Algumas ferramentas utilizam a abordagem de simulacao do hard-ware, na qual o simulador e baseado em uma descricao (modelo) do hardware do proces-sador. Neste tipo de simulacao, o modelo de consumo e construıdo com base no modelomatematico do circuito (mais baixo nıvel) e/ou descricoes de mais alto nıvel (RTL- Regis-ter Transfer Level). QuickPower [Mentor ] e PowerMill [Huang et al. 1995] sao exemplosde ferramentas em nıvel de circuito, ambas atuam no nıvel de abstracao logico. Ja asferramentas SimplePower [Irwin et al. 2001], Wattch [Brooks et al. 2000] e PowerTimer[Brooks et al. 2003], necessitam de um modelo RTL da arquitetura alvo para possibilitar

1.4 ESTRUTURA DO TRABALHO 4

as estimativas de potencia e sao ferramentas que atuam no nıvel abstracao arquitetural.Apesar da boa exatidao dos resultados apresentados, o baixo nıvel dos modelos demandaum grande esforco computacional. Nestas ferramentas, o comportamento do processadore simulado ciclo a ciclo. Desta forma, pequenos trechos de codigo podem ser facilmenteanalisados, mas para programas maiores a simulacao pode se tornar impraticavel. Alemdisto, neste tipo de simulacao e necessario ter acesso a descricoes de baixo-nıvel da ar-quitetura, o que nem sempre e possıvel.

Outra forma de simulacao consiste em caracterizar o modelo de consumo do proces-sador de acordo com o consumo associado as suas instrucoes [Tiwari et al. 1994]. Essemodelo alimenta um simulador de instrucoes e a analise e realizada com base nos padroesde saıda desse simulador. As ferramentas que utilizam este tipo de simulacao atuam nonıvel de abstracao comportamental. A ferramenta JouleTrack [Sinha and Chandrakasan 2001]e um exemplo deste tipo de simulador. Outro exemplo e a metodologia baseada nas CPNdesenvolvida por [Oliveira et al. 2006], na qual a modelagem estocastica do conjunto deinstrucoes de microcontroladores da famılia 8051 foi demonstrada. A metodologia apre-sentada permite que o projetista associe probabilidades as instrucoes condicionais pararepresentar os mais diversos cenarios de execucao do software. As desvantagens do referidotrabalho, sao que alem de ter sido utilizado uma ferramenta de uso geral (CPN Tools[Ratzer et al. 2003]) para realizar as simulacoes, os modelos propostos ficaram muitocomplexos. Como consequencia direta, inviabilizou a aplicacao da metodologia propostaem projetos reais.

Uma terceira forma de estimar o consumo de energia e utilizando a metodologia FLPA(Functional-Level Power Analysis) [Laurent et al. 2001, Steinke et al. 2001]. A definicaodo modelo de consumo segundo a metodologia FPLA e feita em dois passos. O primeiropasso consiste em dividir o processador em varios blocos funcionais, para, em seguida,agrupar os componentes que sao ativados em conjunto quando um codigo esta sendoexecutado. Depois, os blocos funcionais sao descritos por funcoes matematicas baseadasem parametros arquiteturais e algorıtmicos. Os parametros algorıtmicos dependem docodigo executado (taxa de cache hit/misses, por exemplo), e os parametros arquiteturaissao definidos pelo projetista (frequencia do processador, por exemplo). O segundo passo ea caracterizacao do modelo de consumo do processador quando estes parametros variam.Estas variacoes sao obtidas estimulando cada bloco individualmente atraves de codigosassembly, denominados cenarios. E assim, as funcoes matematicas e seus parametrossao deduzidos atraves dos dados adquiridos. Uma vez definido o modelo de consumo, aestimativa do consumo de energia de um codigo e feita extraindo alguns parametros docodigo a ser avaliado, para que, em seguida, estes parametros sejam inseridos no modelo.Mais descricoes sobre a metodologia FLPA e sua integracao a ferramentas de analises saodescritas em [Senn et al. 2004, Senn et al. 2002].

1.4 ESTRUTURA DO TRABALHO

Este trabalho esta organizado como se segue. O Capıtulo 2 descreve os principais con-ceitos utilizados neste trabalho tais como estimativa de consumo de energia e desempenho,simulacao estocastica e Redes de Petri Coloridas. O Capıtulo 3 descreve a metodologia

1.4 ESTRUTURA DO TRABALHO 5

de desenvolvimento para sistemas embarcados na qual este trabalho esta inserido. OCapıtulo 4 apresenta o modelo da simulacao e como seus resultados sao avaliados. Aplataforma de simulacao ALUPAS, proposta por este trabalho, e apresentada no Capıtulo5. No Capıtulo 6 sao descritos alguns experimentos para validar o ALUPAS e demonstrara metodologia de avaliacao de um codigo. O Capıtulo 7 conclui este trabalho. Adicional-mente, o Apendice A mostra como a caracterizacao do processador alvo deste trabalhofoi realizada.

CAPITULO 2

FUNDAMENTOS

Neste Capıtulo serao apresentados os principais conceitos deste trabalho. Primeiramente,uma apresentacao sobre a abordagem de avaliacao de consumo de energia e feita na Secao2.1. Nas Secoes 2.2 e 2.3 sao apresentados os conceitos de modelo, simulacao estocasticae processo estocastico. Nas Secoes 2.4 e 2.5 e apresentada uma visao geral das Redes dePetri e Redes de Petri Coloridas.

2.1 ESTIMATIVA DE DESEMPENHO E CONSUMO DE ENERGIA

O desenvolvimento de projetos de sistemas de tempo real de baixo consumo de ener-gia pode ser auxiliado por ferramentas, cujas funcoes principais sao analisar e otimizaro sistema sendo construıdo. A analise esta relacionada a mecanismos de estimativas dedesempenho e consumo de energia nas varias fases do projeto. E atraves das metricas ger-adas pelos mecanismos de analise que o projetista consegue inferir onde o projeto precisaser otimizado. A otimizacao refere-se aos processos que buscam melhorar o desempenhoe consumo de energia, sem que isto afete as especificacoes do sistema.

Um objetivo central da analise nesses sistemas e prover ao projetista, informacoessobre a operacao do sistema nos cenarios habituais e mais pessimistas. Em sistemas detempo real crıticos, uma metrica amplamente utilizada para informar o tempo de respostaao cenario mais pessimista e o WCET (Worst Case Execution Time) [Colin and Puaut 2000].

Um conceito comumente utilizado para estimar o consumo de energia devido aosoftware e associar as instrucoes executando no processador ao seu respectivo custo[Nikolaidis et al. 2002]. A estas instrucoes sao associados dois custos principais: (1)o custo basico de uma instrucao, que e proporcional ao consumo da corrente geradopelo processador e ao tempo de execucao, e (2) o custo inter-instrucao decorrente doschaveamentos do circuito, devido as mudancas de estado interna do processador quandouma nova instrucao esta sendo colocada para executar. A estes dois custos somam-se os custos que dependem da arquitetura especıfica do processador, e.g., bolhas nopipeline e cache misses. Todos estes custos sao resumidos na Equacao 2.1, proposta por[Laopoulos et al. 2002] para calcular o consumo total de energia de um software.

Ep =∑

i

(Bi ×Ni) +∑i,j

(Oi,j ×Ni,j) +∑

h

Eh (2.1)

Onde Bi e o custo basico associado a instrucao i e Ni e o numero de vezes em que ie executada, Oi,j e custo inter-instrucao associado ao par de instrucoes i e j e Ni,j e onumero de vezes que esta combinacao ocorre, Eh e o custo dependente da arquitetura doprocessador (bolhas no pipeline ou cache misses, por exemplo).

E importante ressaltar que este metodo nao demanda nenhum tipo de conhecimentosobre os detalhes de implementacao do hardware processador.

6

2.2 MODELOS DE SIMULACAO E SIMULACAO ESTOCASTICA 7

2.2 MODELOS DE SIMULACAO E SIMULACAO ESTOCASTICA

De acordo com [Banks 1999], simulacao e a imitacao do funcionamento de um sistema(ou processo) real ao longo do tempo. Na simulacao, tentamos reproduzir as carac-terısticas ou propriedades em estudo do sistema real e gerar um historico artificial destefuncionamento. Este historico e posteriormente analisado, para que, em seguida, os resul-tados sejam inferidos. Assim, as simulacoes permitem que as inferencias sobre os sistemasreais sejam feitas sem a necessidade de construı-los, sem perturba-los ou destruı-los.

Exemplo

Considere um sistema de fila de atendente unico, aonde os clientes chegam entre ostempos 0 e 20, espacados no tempo e cada tempo de chegada com igual probabilidadede acontecer. Na chegada, os clientes entram em uma fila unica defronte ao caixa e saoatendidos sequencialmente, por ordem de chegada. O tempo de servico e entre 0 e 7,tambem com probabilidade igual de acontecer. Suponha que o banco abra no tempo 0 efeche no tempo 20, atendendo os clientes que restam. O objetivo e simular a operacaodo banco e calcular medidas de desempenho, como o tempo medio de espera e tempomaximo de espera. Para simular este sistema e necessario gerar tempos de chegada etempos de servico aleatorios.

Dada as especificacoes acima, suponha que os seguintes tempos de chegada foramgerados [Hines et al. 2006]:

3 4 6 10 15 20

E os tempos de atendimento correspondentes aos que clientes que chegam foram:

7 6 4 6 1 2

A Tabela 2.1 exibe a evolucao do sistema ao longo do tempo. A Tabela mantemo registro dos tempos nos quais os clientes chegam, sao atendidos e saem. Note que ocliente i so pode comecar a ser atendido no tempo max(Ai, Di−1), isto e, o maximo entreseu tempo de chegada e o tempo de partida do cliente anterior. A Tabela e de facilinterpretacao. Por exemplo, o sistema esta vazio ate o tempo 3, quando chega o cliente1. No tempo 4, chega o cliente 2, mas este deve esperar na fila ate que o cliente 1 terminede ser atendido no tempo 10. O tempo medio de espera e

∑6i=1 Wi/6 = 44/6 e o tempo

maximo de espera e W5 = 11.Para estudar cientificamente um sistema, geralmente e necessario fazer suposicoes

sobre como ele funciona. Estas suposicoes normalmente sao constituıdas por relacoesmatematicas ou logicas e sao chamadas de modelo da simulacao [Law and Kelton 1997].O modelo da simulacao pode ser classificado em tres dimensoes:

� Modelos estaticos e dinamicos - Modelos dinamicos representam sistemas quevariam seu estado com o tempo. Modelos estaticos representam o oposto, isto e,sistemas que nao variam com o tempo.

2.2 MODELOS DE SIMULACAO E SIMULACAO ESTOCASTICA 8

Tabela 2.1 Clientes de Banco em um Sistema de Fila de Atendente Unico

ii Cliente Ai Tempo Bi Inıcio Si Tempo Di Tempo Wi Esperade Chegada do Atendimento de Atendimento de Saıda

1 3 3 7 10 02 4 10 6 16 63 6 16 4 20 104 10 20 6 26 105 15 26 1 27 116 20 27 2 29 7

� Modelos discretos e contınuos - Nos modelos discretos, o estado do sistemae modificado instantaneamente e em pontos espacados no tempo. Nos modeloscontınuos, o estado do sistema e modificado continuamente ao longo do tempo.

� Modelos estocasticos e determinısticos - Se o modelo da simulacao nao possuinenhum componente aleatorio (randomico), o modelo e dito ser determinıstico.Quando ha componentes aleatorios envolvidos, o modelo e estocastico.

O mundo e cheio de incertezas e a maioria (se nao todos) os modelos realısticosincorporam algum tipo aleatoriedade [Sanchez 1999]. As classes de modelos utilizadaspor este trabalho sao os modelos dinamicos, discretos e estocasticos. Na classe de modelosestocasticos, duas distincoes podem ser feitas - as simulacoes podem ser de natureza:

� Terminal (ou transiente) - As simulacoes terminais sao aquelas em que existeum evento natural para definir quando a simulacao esta completa.

� Nao-terminal - Nas simulacoes nao-terminais nao existe um evento natural paradefinir quando a simulacao esta completa. Alguns sistemas nao-terminais de sim-ulacao exibem um comportamento chamado estacionario, onde a longo prazo dosistema, as saıdas possuem distribuicao independente do tempo.

Em um projeto de simulacao, o objetivo final dos dados de entrada e conduzir asimulacao. Este processo envolve a coleta de dados de entrada, analise dos dados deentrada e o uso da analise dos dados de entrada no modelo da simulacao. A coleta de dadospode ser feita de registros historicos ou atraves da realizacao de experimentos especıficospara coleta de dados. A analise envolve a identificacao da suposta distribuicao querepresenta os dados de entrada. E o uso envolve a especificacao da suposta distribuicaono modelo da simulacao. Uma questao comum e: se a coleta de dados ja foi feita, quala necessidade do encaixe dos dados de entrada a uma suposta distribuicao? A razaoprincipal e que na etapa de coleta de dados, apenas uma amostra da real distribuicao dosdados foi coletada [Chung 2004].

A analise da saıda da simulacao e um dos aspectos mais importantes de qualquerprojeto de simulacao adequado. Como os processos de entrada que conduzem a simulacao

2.3 PROCESSOS ESTOCASTICOS 9

sao variaveis aleatorias, devemos considerar a saıda da simulacao tambem como aleatoria.Assim, rodadas da simulacao resultam apenas em estimativas de medidas de desempenho.Estes estimadores sao, eles mesmos, variaveis aleatorias e estao, portanto, sujeitos ao erroamostral - e o erro amostral deve ser levado em conta para se fazer inferencias validasem relacao ao desempenho do sistema [Hines et al. 2006]. A maneira correta de resumira saıda de uma simulacao envolve usualmente a construcao de intervalos de estimativas,ao inves de meros pontos de estimativa [Sanchez 1999].

2.3 PROCESSOS ESTOCASTICOS

Na avaliacao de desempenho utilizando modelagem analıtica, nao e usual utilizar apenasvariaveis aleatorias, mas tambem muitas sequencias diferentes (ou famılias de variaveisaleatorias) que sao funcoes do tempo. Por exemplo, seja n(t) o numero de tarefas emuma CPU de um sistema computacional. Se fossem selecionados sistemas identicos aeste e, em seguida, fosse observado o numero de tarefas na CPU em funcao do tempo,chegar-se-ia a conclusao de que o numero n(t) e uma variavel aleatoria. Para modelareste comportamento e necessario especificar a funcao de distribuicao de probabilidadede n(t) para todos os possıveis valores de t. Tais funcoes do tempo ou sequencias saochamadas processos estocasticos [Jain 1991].

Definicao 2.1. (Processo estocastico): Um processo estocastico e uma famılia devariaveis aleatorias {X(t), t ∈ T} definidas em um dado espaco de probabilidade e index-adas por um parametro t, em que t varia em um conjunto de ındices T .

Em um processo estocastico {X(t), t ∈ T}, o conjunto T e chamado de ındices doprocesso estocastico. Os valores assumidos por X(t) sao chamados de estados e oconjunto de todos os possıveis estados e chamado de espaco de estados E do processoestocastico.

Se o espaco de estados E for discreto, entao o processo e dito ser um processo deestado discreto. Por exemplo, o numero de tarefas n(t) em um sistema so pode assumirvalores discretos 0, 1, 2, .... Assim, n(t) e um processo de estado discreto. Se E for umconjunto contınuo, tem-se um processo de estado contınuo. Se o conjunto dos ındices Tfor discreto (enumeravel), entao o processo e dito ser um processo de parametro discretoou tempo discreto. Se T for um conjunto contınuo, tem-se um processo de parametrocontınuo.

Em geral, a descricao probabilıstica completa de um processo aleatorio generico naoe factıvel. Processos Markovianos sao uma classe especial de processo estocastico, para oqual a descricao probabilıstica e simples e de relevancia particular.

Definem-se processos Markovianos como os processos estocasticos que satisfazemas propriedades Markovianas:

� Propriedade 1: A evolucao futura dos estados nao depende dos estados anteriores;

� Propriedade 2: A evolucao futura dos estados nao depende do tempo de per-manencia no estado atual.

2.4 REDES DE PETRI 10

As propriedades Markovianas facilitam a analise de um processo, ja que nao e necessariolembrar completamente a trajetoria anterior. Sabendo apenas o estado presente e sufi-ciente. Um processo Markoviano de estado discreto e chamado de Cadeias de Markov[Jain 1991].

2.4 REDES DE PETRI

As Redes de Petri consistem em uma ferramenta matematica e grafica que permitemodelar diferentes tipos de sistemas, tais como: paralelos, concorrentes, assıncronos enao-determinısticos. O conceito das Redes de Petri [Murata 1989] foi inicialmente intro-duzido por Carl Adam na sua tese de doutoramento intitulada de Kommunikation mitAutomaten (Comunicacao com Automatos), em 1962 na Universidade de Damstadt, Ale-manha [Petri 1962]. Deste entao, elas tem sido amplamente utilizadas nas mais diversasareas, como matematica, engenharia, manufatura dentre outras.

Figura 2.1 Elementos de uma Rede de Petri: (a)Lugar, (b)Transicao, (b)Arco, (d)Token.

Graficamente, as Redes de Petri classicas sao representadas por lugares (Figura 2.1(a)),transicoes (Figura 2.1(b)), arcos (Figura 2.1(c)) e tokens (marcacoes) (Figura 2.1(d)).Uma Rede de Petri e um grafo dirigido, onde os lugares e transicoes sao seus vertices,interligados atraves de arcos dirigidos. Se a origem de um arco for um lugar, seu destinoprecisa necessariamente ser uma transicao, e vice-versa. A distribuicao dos tokens noslugares da Rede de Petri determinam o estado do sistema. As transicoes e os lugarespodem ser conectados por multiplos arcos (arcos multivalorados) que podem ser com-pactados em um unico arco rotulado. Os lugares correspondem as variaveis de estado dosistema e as transicoes as acoes do sistema [MACIEL et al. 1996].

Figura 2.2 Exemplo de uma Rede de Petri

A Figura 2.2 apresenta uma Rede de Petri que modela o funcionamento de uma

2.4 REDES DE PETRI 11

lampada. Os lugares representam os possıveis estados da lampada: aceso e apagado.As transicoes representam as acoes sobre a lampada: ligar e desligar. A posicao dotoken na rede indica o estado atual da lampada. Neste exemplo, o arco partindo deaceso para desligar, indica que a transicao desligar so pode ser disparada se houver umtoken no lugar aceso. De maneira analoga, o arco partindo de apagado para ligar, indicaque e necessario que haja um token no lugar apagado para que a transicao ligar sejadisparada. Quando uma transicao e disparada, ela consome os tokens dos lugares deentrada, colocando outros tokens nos lugares de saıda. No exemplo, quando a transicaoapagar e disparada, um token do lugar ligado e removido e um token no lugar apagadoe adicionado. Analogamente, quando a transicao ligar e disparada, um token do lugardesligado e removido e um token no lugar ligado e adicionado.

Tabela 2.2 Interpretacoes para os lugares e transicoes. Retirado de [Murata 1989].

Lugares de Entrada Transicoes Lugares de Saıdapre-condicoes eventos pos-condicoesdados de entrada passo e computacao dados e saıdasinal de entrada processamento de sinal sinal de saıdadisponibilidade de recursos tarefa liberacao de recursoscondicao clausula logica conclusoesbuffers processador buffers

Na modelagem de um sistema, lugares e transicoes podem ter inumeras interpretacoes.Utilizando o conceito de condicoes e eventos, lugares representam condicoes e transicoeseventos, tal que, um evento pode ter varias pre-condicoes e pos-condicoes. Para maisinterpretacoes, a Tabela 4.1 exibe outras interpretacoes para os lugares e transicoes[Murata 1989].

Formalmente, as Rede de Petri podem ser definidas conforme mostra a Definicao 2.2.

Definicao 2.2. (Redes de Petri) Uma Rede de Petri e uma 5-tupla, PN = (P, T, F, W,M0),onde:

� P = {p1, p2, ..., pn}, e um conjunto finito de lugares;

� T = {t1, t2, ..., tn}, e um conjunto finito de transicoes;

� F ⊆ (P × T ) ∪ (T × P ), e um conjunto de arcos;

� W : F → {1, 2, 3, 4, ..., n}, e a funcao de atribuicao de peso aos arcos;

� M0 : P → {0, 1, 2, 3, ..., n}, e a marcacao inicial, onde: P ∩ T = ∅ e P ∪ T 6= ∅.

2.5 REDES DE PETRI COLORIDAS (COLOURED PETRI NETS - CPN ) 12

2.5 REDES DE PETRI COLORIDAS (COLOURED PETRI NETS - CPN)

Desde o modelo inicial das Redes de Petri proposto por Carl Adam, varias extensoes temsido propostas para permitir descricoes mais concisas e representar caracterısticas naocontempladas nos primeiros modelos. Algumas das deficiencias dos primeiros modelossao: (i) nao ha conceitos de dados, tornando os modelos excessivamente grandes, poistoda manipulacao de dados precisa ser representada diretamente na estrutura da rede, e(ii) nao ha conceito de hierarquia, nao sendo possıvel construir modelos grandes a partir desub-modelos separados com interfaces bem definidas [MACIEL et al. 1996]. Entre umadas extensoes aos primeiros modelos, destacam-se as redes de alto-nıvel de [Jensen 1992],chamadas Redes de Petri Coloridas (CPN).

As CPN unem o poder das Redes de Petri ao poder das linguagens de programacao.As Redes de Petri fornecem os fundamentos para a descricao da sincronizacao de processosconcorrentes e as linguagens de programacao fornecem os fundamentos para a definicaode tipos de dados e a manipulacao de seus valores. Em uma Rede de Petri classica, tokenssao indistinguıveis. Em uma CPN, tokens sao associados a valores, e estes valores podemser testados e manipulados atraves de linguagens de programacao funcional. As CPNstambem podem utilizar a decomposicao hierarquica sem comprometer as qualidades dasRedes de Petri originais.

As CPNs sao compostas por tres diferentes partes: estrutura, declaracoes e inscricoes[MACIEL et al. 1996]. As inscricoes e declaracoes geralmente sao feitas utilizando lin-guagens baseadas na linguagem funcional Standard ML [Paulson 1996] 1. A estrutura deuma CPN consiste em um grafo dirigido com dois tipos de vertices: lugares e transicoes.Cada lugar pode estar marcado com um ou mais tokens, e cada token possui um valorassociado a si, este valor e chamado de cor do token. A faixa de cores de tokens (val-ores) que um lugar pode ter e determinada pelo conjunto de cores do lugar. Estesconjuntos de cores sao semelhantes aos tipos das linguagens de programacao. O estadodo sistema, chamado de marcacao do modelo CPN, e representado pela quantidade ecor dos tokens presentes em cada lugar. O estado inicial do sistema e chamado marcacaoinicial da CPN.

As declaracoes compreendem a declaracao dos conjuntos de cores, funcoes, variaveise constantes do modelo. Cada declaracao de um conjunto de cores introduz um novoconjunto de cores, onde seus elementos sao chamados de cores. Assim, uma declaracaode conjunto de cores define implicitamente uma restricao [JENSEN ]. Dois exemplos dedeclaracoes de conjuntos de cores sao feitos a seguir:

colset NUMEROS = int;colset NOMES = string;

O primeiro conjunto de cores, NUMEROS, pode ter valores inteiros como cores. Osegundo conjunto de cores, NOMES, pode ter strings como cores. Adicionalmente, umconjunto de cores pode ter um tempo associado, bastando adicionar a expressao timed

1Os exemplos apresentados neste trabalho utilizarao uma variante da linguagem Standard MLchamada CPN ML [Ratzer et al. 2003].


ao final da declaracao.Cada variavel declarada introduz uma ou mais variaveis, onde o tipo da variavel

declarada precisa ser um dos conjuntos de cores ja declarados. Estas variaveis sao uti-lizadas nas expressoes de guarda e de arco (explicadas mais a frente). Um exemplo dedeclaracao de variavel e feito a seguir:

var idade : NUMEROS;

Onde a variavel idade pode conter cores do conjunto de cores NUMEROS, i.e., podepossuir valores inteiros. Adicionalmente, e possıvel declarar tambem funcoes e constantes.

As inscricoes sao associadas aos elementos da rede: lugares, transicoes e arcos. Asintaxe das inscricoes depende do elemento ao qual elas estao sendo associadas. Umlugar pode ter tres inscricoes, duas opcionais e uma essencial: (i) inscricao de nome,define um nome para o lugar; (ii) inscricao de tipo, define o conjunto de cores do lugar(essencial); (iii) inscricao de marcacao inicial, define a marcacao inicial do lugar.

Existe apenas uma inscricao para os arcos, chamada inscricao de arco. A inscricaode arco e uma expressao que e avaliada para um unico elemento ou um multiconjunto.Esta inscricao e essencial.

As transicoes possuem quatro inscricoes, todas opcionais: (i) inscricao de nome,define um nome para a transicao; (ii) inscricao de guarda, uma guarda e uma expressaobooleana que pode ser avaliada para falso ou verdadeiro; (iii) inscricao de tempo, defineum tempo de atraso quando a transicao e disparada, a partir do tempo em que ela se tornahabilitada; (iv) segmento de codigo, define um trecho de codigo para ser executadoquando a transicao for disparada.

Uma transicao so pode ser disparada se sua guarda e avaliada como verdadeira e se oslugares de entrada possuem os tokens necessarios para o disparo. Os tokens necessariossao definidos a partir das expressoes dos arcos de entrada da transicao, dado que umatransicao so pode estar habilitada a disparar se for possıvel associar valores as variaveisdas expressoes dos arcos de entrada conectados a transicao. Quando a transicao e dis-parada, tokens do lugar de entrada sao removidos e outros tokens nos lugares de saıdasao adicionados. Os tokens removidos e adicionados sao definidos pelas expressoes nosarcos de entrada e saıda, respectivamente.

Definicao 2.3. (Redes de Petri Coloridas) A definicao nao-hierarquica das Redes dePetri Coloridas e uma 9-tupla CPN = (

∑, P, T, A, N,C,G, E, I), onde:

� ∑e um conjunto finito de tipos nao-vazios, chamado Conjunto de Cores;

� P e um conjunto finito de elementos, chamado Lugares;

� T e um conjunto finito de elementos, chamado Transicoes;

� A e um conjunto finito de arcos tal que P ∩ T = P ∩ A = T ∩ A = Ø, N : A →P × T → T × P e uma funcao de no;

� C : P → ∑e uma funcao de cor; G e uma funcao de guarda, que e definida a partir

de T em expressoes tais quais ∀t ∈ T : [Tp(G(t)) = Bool ∧ Tp(V ar(G(t))) ⊆ ∑];


� E e uma funcao de arco, definida a partir de A em expressoes tais quais ∀a ∈ A :[Tp(E(a)) = C(p(s))MS∧Tp(V ar(E(a))) ⊆ ∑

], onde p(a) e o lugar de N(a) e CMS

denota o conjunto de todos os multiconjuntos sobre C;

� I e a funcao de inicializacao, definida a partir de P em expressoes tais quais ∀p ∈P : [Tp(I(p)) = C(p(s))MS ∧ V ar(I(p)) = ∅], onde Tp(expr) denota o tipo de umaexpressao, V ar(expr) denota o conjunto de variaveis em uma expressao, C(p)MS

denota o multiconjunto sobre C(p).

Adicionalmente, as CPN tambem permitem modelar estruturas hierarquicas ondetransicoes, chamadas transicoes de substituicao, podem representar modelos com-plexos. O modelo representado pelas transicoes de substituicao e chamado de subpagina.O nıvel mais alto, constituıdo por transicoes de substituicao e chamado de pagina. Estaspaginas sao conectadas, umas com as outras por lugares, chamados portas, que podemser dos tipos porta de entrada ou porta de saıda.

Exemplo

Figura 2.3 Problema do jantar dos filosofos modelado em uma CPN.

Um modelo CPN e apresentado na Figura 2.3 com a finalidade de exemplificar umasolucao formal para o classico problema do jantar dos filosofos [Silberschatz and Galvin 1994].Lugares sao representados graficamente por elipses, transicoes por retangulos e arcos porsetas. O modelo possui 3 lugares, 2 transicoes e 6 arcos (de entrada e saıda) que realizama conexao de lugares as suas respectivas transicoes. Alem disso, tambem e possıvel ob-servar a presenca das declaracoes a esquerda da rede (Declarations) e inscricoes ao ladodos lugares, das transicoes e dos arcos.


Figura 2.4 Exemplo de reducao preservando muitas das propriedades dinamicas da rede.

Na Figura 2.3, um filosofo pode esta comendo ou pensando. Esse comportamento erepresentado atraves dos lugares Pensando e Comendo. O numero de talheres disponıveise modelado pela presenca de tokens no lugar Talheres livres. Os lugares Pensando eComendo tem o conjunto de cores (colset) FILOSOFO, e o lugar Talheres livres temconjunto de cores TALHER. As acoes e eventos do modelo sao modelados atraves dastransicoes Pega Talheres e Libera Talheres. A funcao Talheres mapeia cada filosofo a doistalheres ao seu lado. Quando, por exemplo, a transicao Pega talheres ocorre, e removidoum token do lugar Pensando, dois do lugar Talheres livres e um token e colocado no lugarComendo.

2.5.1 Reducao

As CPN tambem podem ser analisadas por meio de reducoes. A ideia principal e definiras propriedades que serao investigadas e, depois, aplicar um conjunto de regras parasimplificar a CPN sem que as propriedades que estao sobre investigacao sejam modificadas[Jensen 1992, Murata 1989].

Um exemplo e exibido na Figura 2.4. Neste exemplo, uma rede que possui um lugarQ, duas transicoes T1 e T2, e dois arcos identicos com expressoes Expr e substituıdapor uma rede que possui apenas uma unica transicao T3. No exemplo, T3 recebe umarco de entrada para cada entrada de T1 e um arco de saıda para cada arco de saıda deT2. Cada novo arco possui a mesma expressao e o mesmo lugar correspondente ao arcoremovido. A guarda de T3 e identica a de T1.

CAPITULO 3

METODOLOGIA DE DESENVOLVIMENTO PARASISTEMAS EMBARCADOS - MEMBROS

Este capıtulo apresenta a metodologia MEMBROS (Methodology for Embedded CriticalSoftware Construction) de desenvolvimento de sistemas embarcados, na qual este trabalhoesta inserido. Serao discutidos brevemente cada atividade do fluxo de tarefas e seusrespectivos artefatos de entrada e saıda.

A Figura 3.1 apresenta as atividades principais da metodologia MEMBROS, cuja or-ganizacao e feita em tres grupos: (i) validacao de requisitos; (ii) avaliacao de desempenho;e (iii) sıntese do software. A seguir, uma visao geral de cada grupo e feita.

Análise de Requisitos

Criação dosDiagramas da SysML

Análises e Verificações

Avaliação

[Inconsistência dosRequisitos]

[Inconsistência dos Diagramas]

Desenvolvimento do Software Embarcado

Copilação do Código Fonte

Anotado

Modelagem Estocástica

Simulação

Comparação com os Resultados da Avaliação

dos Requisitos

[Inconsistência

dos Requisitos]

Especificação

Modelagem do Escalonamento

Escalonamento

Geração de Código

Validação

Análises eVerificações das

Propriedades

[Verificação das Propriedades]

[Propriedades não Encontradas]

[Propriedades ok]

[Escalonamentonão Encontrado]

[Inconsistência das Restrições]

Validação de Requisitos Avaliação de Desempenho Síntese de Software

MEMBROS

Análise do Código

[Inconsistênciado Código]

[Inconsistência doComportamento]

Associação de Informações de Energia e Tempo aos Diagramas usando MARTE

Implementação

Mapeamento dos Diagramas em

um Modelo ETPN

Figura 3.1 Diagramas de atividade da metodologia.

Inicialmente, as atividades relacionadas a validacao dos requisitos sao realizadas. De-pois da analise de requisitos, o sistema e projetado utilizando um conjunto de diagramasSysML (Systems Modeling Language Diagrams - SDs) [Friedenthal et al. 2006]. A SysMLe uma extensao da UML para a engenharia de sistemas. Estes diagramas representam as

16

METODOLOGIA DE DESENVOLVIMENTO PARA SISTEMAS EMBARCADOS - MEMBROS 17

funcionalidades do projeto a ser codificado e proveem ao desenvolvedor uma linguagemamigavel e intuitiva para modelagem dos requisitos.

Uma vez que restricoes de tempo e consumo de energia sao de extrema importanciano desenvolvimento de sistemas embarcados, os diagramas SysML sao anotados com in-formacoes sobre o consumo de energia e tempo de execucao, utilizando MARTE (Modelingand Analysis of Real-Time and Embedded Systems). Em seguida, o diagrama SysML an-otado e automaticamente mapeado em uma Rede de Petri Temporizada com restricoesde Energia (ETPN) [Tavares et al. 2008]. De posse do modelo ETPN, analises quanti-tativas e qualitativas das propriedades do modelo sao realizadas, permitindo a validacaodos requisitos do projeto. E importante ressaltar que as analises qualitativas capturamos aspectos logicos da evolucao dos sistemas. Entre as propriedades de interesse, pode-sedestacar a analise da existencia deadlock, repetitividade e a reversibilidade, por exem-plo. As analises quantitativas, por outro lado, tem por principal objetivo a analise dedesempenho. Mais informacoes sobre este grupo de tarefas podem ser encontradas em[Andrade et al. 2009].

Terminada a fase de projeto do sistema, inicia-se a fase de codificacao e tambem osegundo grupo de atividades da metodologia. Este grupo de tarefas tem como objetivoestimar o consumo de energia e tempo de execucao do codigo do projeto. As atividadesdeste grupo correspondem as atividades nas quais este trabalho esta inserido e que seraomais detalhadas em Capıtulos especıficos (ver Capıtulo 4 e Capıtulo 5).

De posse do codigo ou de trechos do codigo do sistema, o projetista analisa estescodigos de modo a atribuir probabilidades as estruturas iterativas e condicionais. Emseguida, o codigo e automaticamente traduzido para um modelo em Redes de Petri Colori-das, a fim de fornecer os fundamentos para a simulacao estocastica do software. Emboranao esteja representado na Figura 3.1, uma atividade de caracterizacao da arquiteturatambem e considerada (ver Apendice A). Em seguida, uma simulacao estocastica e real-izada, considerando as caracterısticas da plataforma alvo. Se os resultados da simulacaoestiverem de acordo com as exigencias, a sıntese do software e realizada.

A sıntese de software consiste em traduzir uma especificacao de alto nıvel em codigofonte, incluindo todo o suporte operacional necessario para execucao do software embar-cado. A sıntese de software tambem e conhecida como geracao automatica de codigo.

As atividades de sıntese do software sao compostas por dois subgrupos de atividades:(i) tratamento das tarefas, e (ii) geracao de codigo. O tratamento das tarefas e responsavelpelo escalonamento das tarefas, gerencia dos recursos, e a comunicacao inter-tarefa. Ageracao de codigo trata da geracao estatica do codigo fonte final, que inclui um mecanismoauxiliar de suporte em tempo de execucao, denominado despachante. E importanteressaltar que o conceito de tarefa e semelhante a de um processo, no sentido de que euma unidade ativada concorrentemente durante a execucao do sistema. Para as seguintesatividades, assume-se que o software foi implementado como um conjunto de tarefasconcorrentes de tempo-real.

De posse das informacoes do tempo de execucao das tarefas, bem como as informacoessobre o consumo de energia do hardware obtidas atraves do grupo de tarefas anterior, oprojetista especifica as restricoes do sistema. Esta especificacao consiste de um conjuntode tarefas concorrentes com suas respectivas restricoes, descricoes comportamentais, in-

METODOLOGIA DE DESENVOLVIMENTO PARA SISTEMAS EMBARCADOS - MEMBROS 18

formacoes relacionadas com a plataforma alvo (tensao/nıveis de frequencia), bem comoas restricoes de energia.

Em seguida, a especificacao e traduzida em um modelo ETPN capaz de representaras atividades concorrentes, as informacoes de tempo de execucao, as relacoes inter-tarefa,tais como a exclusao mutua e de precedencia, bem como as restricoes de energia.

Apos gerar o modelo, o projetista pode primeiramente escolher realizar a analise/verificacao das propriedades ou realizar atividade de escalonamento das tarefas. Ametodologia proposta adota o metodo off-line de escalonamento para encontrar umaescala exequıvel que satisfaca as restricoes de tempo, energia e relacoes inter-tarefa. Maisespecificamente, o algoritmo de escalonamento adotado na modelagem e um algoritmode busca em profundidade que tenta encontrar uma escala exequıvel a partir do modelode Rede de Petri. O resultado da etapa de escalonamento e uma escala exequıvel quesatisfaca as restricoes. Em seguida, a escala e passada para o mecanismo gerador au-tomatico de codigo, o qual produz um codigo customizado previsıvel para a aplicacao.O codigo resultante contem apenas os servicos estritamente necessarios para execucaoda aplicacao, ou seja, a etapa de geracao de codigo tem como resultado o codigo dodespachante customizado para a execucao das tarefas de tempo real crıtico. Por ultimo,a aplicacao e validada na plataforma a fim de verificar o comportamento do sistema, bemcomo as respectivas restricoes. Uma vez validado o sistema, ele pode ser implantado emum ambiente real. Mais informacoes sobre este grupo de tarefas podem ser encontradasem [Tavares et al. 2008].

CAPITULO 4

MODELO DA SIMULACAO

Este Capıtulo apresenta o modelo de simulacao proposto para estimar o consumo de en-ergia e tempo de execucao de softwares para sistemas embarcados. A Secao 4.1 apresentaos modelos basicos e a composicao destes modelos basicos para modelar a fluxo de con-trole do software. A Secao 4.2 apresenta o processo de reducao do modelo. Por fim, aSecao 4.3 descreve os parametros da simulacao e como e feita a analise dos resultados.

4.1 MODELO PROPOSTO: MODELOS BASICOS E COMPOSICAO DOS MOD-ELOS BASICOS

No modelo proposto, o fluxo de controle do software e representado por um modeloCPN com dois nıveis de hierarquia. No nıvel mais baixo, estao os modelos basicos e nonıvel mais alto, a composicao destes modelos basicos. Os modelos basicos modelam asinstrucoes do microprocessador Philips LPC2106. Quatro modelos basicos foram con-struıdos para representar o conjunto de instrucoes do LPC2106: (i) modelo de instrucaoordinaria, (ii) modelo de desvio condicional, (iii) modelo de desvio com retorno, e (iv)modelo de retorno para instrucoes de desvio com retorno. Cada um destes modelos com-puta o consumo de energia e tempo de execucao de uma instrucao ou bloco de instrucoesdurante a avaliacao do modelo. Os modelos basicos foram alimentados com dados so-bre o tempo de execucao e consumo de energia das instrucoes do LPC2106, seguindo ametodologia de medicoes no hardware descrita no Apendice A.

Figura 4.1 Modelo de instrucao ordinaria.

A Figura 4.1 exibe o modelo de instrucao ordinaria. Este modelo representa as in-strucoes nao condicionais do processador e apresenta apenas duas portas, uma e do tipoentrada e a outra do tipo saıda. Durante a simulacao, este modelo computa o consumo de

19

4.1 MODELO PROPOSTO: MODELOS BASICOS E COMPOSICAO DOS MODELOS BASICOS 20

energia (val energy) e tempo de execucao (val cy) atraves da funcao addData(energy,cy).O mesmo modelo tambem e utilizado para representar um conjunto de instrucoes agru-padas em um unico bloco basico, depois que a rede sofre o processo de reducao (ver Secao4.2).

Figura 4.2 Modelo de desvio condicional.

A Figura 4.2 exibe o modelo de desvio condicional. Este modelo representa as in-strucoes condicionais do processador e possui tres portas, uma do tipo entrada e duas dotipo saıda. E possıvel notar que os registradores do processador nao sao armazenadospelos modelos basicos. Ao inves de se comparar valores armazenados nos registradores,uma abordagem estocastica e adotada. Para determinar o fluxo de execucao do codigodurante a simulacao, sao associadas probabilidades as instrucoes condicionais (val prob).Como pode ser visto na Figura 4.2, durante a simulacao do modelo de desvio condicional,um numero aleatorio entre 0 e 1 com distribuicao uniforme e gerado e, em seguida, estenumero e comparado com a probabilidade associada (uniform(0.0,1.0) <= prob) do mod-elo. Caso o numero aleatorio seja menor ou igual a esta probabilidade, a condicao deexecucao e avaliada como verdadeira e ocorre desvio no fluxo de execucao, caso contrarionao ha desvio. Como sera explicado na Secao 4.3, as probabilidades sao definidas peloprojetista, atraves das anotacoes no codigo. No modelo, aval recebe ”1”(verdadeiro) casoa condicao de desvio seja satisfeita e ”0”(falso), caso contrario. O consumo de energia etempo de execucao e computado de forma condicional e depende do valor de aval. Nomodelo, as transicoes Jump e Not Jump, possuem expressoes de guarda que definem qualdas duas transicoes deve ser disparada durante a avaliacao. Estas expressoes de guardatambem dependem do valor de aval.

O modelo basico desvio com retorno (ver Figura 4.3) representa a instrucao de chamadade procedimento do LPC2106. Quando este tipo de instrucao ocorre, e feito um desviono fluxo de execucao e o endereco de retorno e guardado em uma pilha para que pos-teriormente o fluxo seja continuado de onde foi interrompido. O endereco de retorno eo endereco da instrucao que ocorreria em seguida a instrucao atual, caso o desvio nao

4.1 MODELO PROPOSTO: MODELOS BASICOS E COMPOSICAO DOS MODELOS BASICOS 21

Figura 4.3 Modelo de desvio com retorno

ocorresse. No modelo, o empilhamento do endereco de retorno e feito atraves da funcaopush.

Figura 4.4 Modelo de retorno para instrucoes de desvio com retorno

A Figura 4.4 exibe o modelo de retorno para instrucoes de desvio com retorno. Estemodelo representa a instrucao de retorno de procedimento do LPC2106. Quando umprocedimento chega ao fim, esta instrucao desempilha o endereco de retorno empilhadopor uma instrucao de chamada de procedimento e realiza um desvio para este endereco.Diferentemente dos outros modelos apresentados, o numero de lugares, arcos e transicoesdeste modelo nao e estatico e depende do codigo a ser analisado. Se, por exemplo, umprocedimento e chamado mais de uma vez em diferentes partes do codigo, este modeloe ligado a mais de um lugar. No exemplo apresentado, o modelo esta ligado a doislugares, indicando que o procedimento foi chamado em duas partes distintas do codigo.

4.2 PROCESSO DE REDUCAO 22

As transicoes do modelo apresentam expressoes de guarda que definem para qual enderecoo fluxo sera desviado.

Figura 4.5 Trecho de codigo.

Figura 4.6 Modelo CPN dofluxo de controle: composicao dosmodelos basicos.

A Figura 4.6 exibe o fluxo de controle no modelo proposto para o trecho de codigo emassembly da Figura 4.5. A Figura 4.6 apresenta o nıvel mais alto do modelo onde cadatransicao e uma instancia de um dos modelos basicos apresentados. Para automatizar ageracao de modelos, um compilador (denominado Compilador Binario-CPN) foi criado eintegrado ao simulador ALUPAS (ver Secao 5.2). Este compilador recebe como entradao codigo binario do software (com anotacoes) a ser avaliado e gera a composicao dosmodelos basicos CPN.

4.2 PROCESSO DE REDUCAO

Como apresentado na Secao 4.1, com excecao dos modelos que representam as instrucoesde chamada de procedimento e retorno de procedimento, os modelos basicos propostos naorealizam uma simulacao comportamental das instrucoes (operacoes com os registradoresdo microprocessador nao sao simuladas), isto e, eles apenas computam o consumo de

4.2 PROCESSO DE REDUCAO 23

energia e tempo de execucao. Tal comportamento faz com que seja possıvel modelarblocos de instrucao por apenas um modelo basico.

O processo de reducao consiste em transformar o modelo original, em um modelomais simples e com tempo de simulacao menor, onde todas as caracterısticas necessariaspara estimar o tempo de execucao e consumo de energia sao preservadas. Um trecho decodigo com um unico ponto de entrada e um unico ponto de saıda e candidato a sofrero processo de reducao e se tornar um bloco basico. Os blocos basicos utilizam o modelode instrucao ordinaria (ver Secao 4.1) para computar o consumo de energia e tempo deexecucao.

A Figura 4.7 exibe o que acontece com um trecho de modelo depois do processo dereducao. Neste exemplo, as transicoes Inst 0 MOV R1, ]1, Inst 1 MOV R1, ]1, Inst 2MOV R1, ]1, e seus respectivos arcos e lugares de entrada e saıda, sao substituıdos por ummodelo que possui apenas uma transicao (BLOCK ID7209 ), um arco de saıda, um arcode entrada e dois lugares. O consumo de energia e tempo de execucao deste trecho queantes seria computado por Inst 0 MOV R1, ]1, Inst 1 MOV R1, ]1 e Inst 2 MOV R1, ]1,agora e igualmente computado apenas por BLOCK ID7209.

Figura 4.7 (a)Trecho de um exemplo de modelo, (b)Trecho do mesmo exemplo, depois doprocesso de reducao.

4.3 PARAMETROS DA SIMULACAO E ANALISE DOS RESULTADOS 24

Os elementos de um trecho do modelo candidatos a sofrerem o processo de reducaodevem satisfazer tres regras: (i) qualquer lugar do trecho a ser reduzido, nao pode termais que um arco de entrada, (ii) qualquer transicao do trecho a ser reduzido, nao podeter mais que um arco de saıda e (iii) trechos que possuam transicoes que sejam instanciasdos modelos basicos: modelo de retorno para instrucoes de desvio com retorno, ou modelode desvio com retorno, nao podem ser reduzidos. Assim, se estas regras forem satisfeitas,estes elementos sao agrupados para se tornarem um bloco basico.

4.3 PARAMETROS DA SIMULACAO E ANALISE DOS RESULTADOS

Anotacoes no codigo fonte do software permitem que o projetista possa definir o cenariode execucao a ser avaliado e o criterio de parada da avaliacao. A Figura 6.1 exibe umexemplo de codigo anotado. As anotacoes da forma <@ Prob @> associam probabilidadeProb a uma instrucao de desvio condicional. Assim, a probabilidade do desvio ocorrer eigual a Prob. Este tipo anotacao permite que o projetista avalie os mais diversos cenariosde execucao do software, bastando apenas modificar os valores destas probabilidades.As probabilidades de cada cenario podem ser obtidas por meio de: (i) inferencias doprojetista com base em seu conhecimento sobre o codigo e/ou (ii) analise do perfil deexecucao (profiling) do codigo utilizando ferramentas externas.

Devido a natureza estocastica do modelo proposto, os resultados das simulacoes apre-sentam variacoes (ver Secao 2.2). Sendo assim, as estimativas geradas por ALUPAS naopodem ser baseadas em apenas uma unica simulacao. Portanto, para que as estimativassejam confiaveis, e necessario que a simulacao seja replicada um certo numero de vezes,e entao utilizar os resultados de todas as replicacoes para conduzir as inferencias. Duasquestoes que se colocam sao: (i) o que fazer com os resultados das replicacoes? e (ii) qualo numero ideal de replicacoes para se obter estimativas confiaveis? A primeira pergunta efacilmente respondida utilizando a media amostral das replicacoes. O segundo problemae contornado gerando tantas replicacoes quantas forem necessarias ate que um criterio deparada seja satisfeito. O criterio de parada adotado por ALUPAS se baseia no metodode replicacao independente (RI) [Hines et al. 2006].

Baseado na RI, a media amostral e definida atraves da realizacao de b replicacoes, emque cada replicacao consiste em m simulacoes do codigo a ser avaliado. Assim, a mediaamostral da i-esima replicacao e dada por:

Zi =1

m

m∑j=1

Yi,j (4.1)

onde Yi,j e o resultado da simulacao j da replicacao i, para i=1,2,...,b e j=1,2,...,m.Segue que a variancia amostral e:

Vr =1

b− 1

b∑i=1

(Zi − Zb)2 (4.2)

, em que a media amostral geral Zb e dada por:


Zb =1

b

b∑i=1

Zi. (4.3)

Utilizando o Teorema do Limite Central, pode-se mostrar que o erro maximo absolutopara a media, com 100(1 - α)% de confianca, e dado por:

|E| = tα/2,b−1

√Vr

b(4.4)

, em que tα/2,b−1 e o ponto percentual 1 - α/2 da distribuicao t com b - 1 graus deliberdade.

O processo de avaliacao e baseado nas equacoes acima e leva em consideracao osparametros definidos pelo projetista atraves de anotacoes no codigo na forma <$ NConf| EMax | TMax $> (ver linha 1 da Figura 6.1). Onde EMax e TMax definem o erromaximo absoluto para energia e o erro maximo absoluto para o tempo, respectivamente,isto e, definem a exatidao da simulacao, e NConf define o nıvel de confianca. O processode avaliacao segue gerando novas replicacoes (inicialmente sao dez) ate que o erro maximoabsoluto para a energia e para o tempo de execucao, calculados pela a Equacao 4.4, sejammenores ou iguais aqueles definidos pelo projetista.

Assim, ao final do processo de avaliacao, obtem-se as seguintes metricas para o nıvel deconfianca especificado (NConf ): media amostral (Zb) e o erro maximo absoluto (|E|). Apartir destes dados pode-se construir o seguinte intervalo de confianca [Zb−|E|; Zb+ |E|].Este intervalo informa que o valor a ser medido esta com (100 × NConf)% de certezaentre [Zb−|E|; Zb+ |E|]. No caso geral, e recomendado utilizar o valor da media amostralcomo resultado da avaliacao. No caso especıfico em que se esta querendo medir os cenariosde pior caso, como o WCET de um software, e recomendado utilizar o limite superiordeste intervalo, isto e, Zb + |E|. Assim garante-se com (100×NConf)% de certeza queno pior caso o resultado e Zb + |E|.

4.3.1 Consideracoes finais

Este Capıtulo apresentou o modelo de simulacao proposto para estimar o consumo deenergia e tempo de execucao de softwares para sistemas embarcados, alem de mostrar oprocesso de reducao e como os resultados da simulacao sao analisados.

O modelo proposto consiste em um modelo CPN com dois nıveis de hierarquia, ondecada instrucao do LPC2106 foi modelada de forma a reproduzir o comportamento daexecucao de um codigo durante a simulacao. Este modelo adota uma abordagem proba-bilıstica para determinar o fluxo de execucao nos pontos de decisao do codigo. Os pontosde decisao referem-se as instrucoes de desvio condicional do codigo. A estas instrucoessao associadas probabilidades por meio de anotacoes no codigo. Estas probabilidadesdeterminam se a condicao para realizacao do desvio deve ser avaliada como verdadeiraou nao durante a simulacao.

O processo de reducao do modelo consiste em transformar o modelo original, em ummodelo mais simples e com tempo de simulacao menor, onde todas as caracterısticasnecessarias para estimar o tempo de execucao e consumo de energia sao preservadas.


O criterio de parada da simulacao e baseado no metodo de replicacoes independentesem conjunto com as especificacoes de exatidao feitas pelo projetista (atraves de anotacoesno codigo). Sao geradas tantas replicacoes da simulacao quantas forem necessarias ateque o criterio de parada seja satisfeito.

CAPITULO 5

ALUPAS

O ambiente de simulacao ALUPAS e composto pelos seguintes componentes: Assembler,Compilador Binario-CPN, Simulador-CPN e GUI (Graphical User Interface). Exceto oAssembler, todos os componentes foram feitos em Java, devido as diversas facilidades queesta linguagem prove. As Secoes a seguir detalham cada componente e por fim, a Secao5.5 descreve como estes componentes sao integrados para formar o ALUPAS.

5.1 ASSEMBLER

Assemblers sao programas responsaveis por transformar o codigo fonte do software escritoem assembly para linguagem de maquina. Estes programas funcionam substituindo asinstrucoes do codigo por opcodes (operation codes) do processador, e nomes das variaveise outros nomes simbolicos pelos enderecos de memoria correspondentes [Barron 1978].

Figura 5.1 Assembler.

ARM/Thumb Macro Assembler foi o Assembler utilizado neste trabalho. Este As-sembler faz parte do pacote de ferramentas RealView Compilation Tool 3.0 da ARM[ARM ], sendo este pacote largamente utilizado em projetos de sistemas embarcados.Alem de gerar codigo binario, este Assembler foi configurado para gerar arquivos de list-ing (ver Figura 5.1). Um listing e um tipo de arquivo de saıda dos compiladores onde saocolocadas informacoes sobre uma compilacao em particular. Estes arquivos sao utiliza-dos para auxiliar na identificacao de erros de compilacao. Neste trabalho, os arquivos delisting foram utilizados para extrair as anotacoes do codigo fonte do software (ver Secao4.3), ja que somente utilizando o codigo binario isto nao seria possıvel.

27

5.2 COMPILADOR BINARIO-CPN 28

5.2 COMPILADOR BINARIO-CPN

O Compilador Binario-CPN tem por finalidade transformar o codigo binario do softwareem analise no modelo CPN proposto (ver Capıtulo 4) para a avaliacao. Este compiladorrecebe como entrada o codigo binario e o arquivo de listing produzidos depois da com-pilacao do software pelo Assembler, e gera como saıda a composicao dos modelos basicosCPN (ver Figura 5.2).

Figura 5.2 Compilador Binario-CPN.

A transformacao do codigo binario no modelo CPN e feita em tres etapas. Na primeiraetapa o compilador extrai do arquivo de listing, as probabilidades das instrucoes condi-cionais e as informacoes sobre o criterio de parada da simulacao. Estas informacoes saoregistradas em um arquivo XML para serem utilizadas na segunda etapa.

O compilador possui internamente uma base de dados com os modelos basicos querepresentam as instrucoes do LPC2106 e uma tabela que mapeia os opcodes de cadainstrucao ao seu respectivo modelo basico. Na segunda etapa, o compilador utiliza esteselementos para construir a composicao dos modelos basicos. No inıcio da segunda etapa,o modelo inicia vazio, e a medida que o Compilador-CPN vai lendo o codigo binario (op-codes) do software, os modelos basicos correspondentes a cada opcode do codigo vao sendoincluıdos e ligados entre si no modelo. Quando e encontrado um opcode de uma instrucaocondicional, antes de incluir o correspondente modelo basico ao modelo, o CompiladorBinario-CPN busca no arquivo XML (primeira etapa) sua respectiva probabilidade eatribui esta probabilidade ao modelo basico. So entao este modelo basico e inserido aomodelo. Ao final deste processo, as informacoes sobre o criterio de parada tambem saoinseridas ao modelo.

Na terceira etapa, o processo de reducao (ver Secao 4.2) e executado para que omodelo seja simplificado. Ao final da terceira etapa, o compilador gera dois arquivos desaıda, um compatıvel com o CPN Tools e outro compatıvel com o ALUPAS. O formatocompatıvel com o CPN Tools foi necessario pois esta ferramenta permite a visualizacao esimulacao grafica do modelo. Assim, o modelo e suas propriedades puderam ser avaliadas

5.3 SIMULADOR-CPN 29

e validadas.

5.3 SIMULADOR-CPN

A simulacao do modelo poderia ser feita utilizando o CPN Tools, no entanto, esta ferra-menta apresentou serios problemas de desempenho. Devido as limitacoes de desempenhoapresentadas pelo CPN Tools, foi criado um simulador especıfico, denominado Simulador-CPN. Este simulador recebe como entrada o modelo e gera como saıda as metricas emavaliacao: media amostral, erro absoluto e desvio padrao para o tempo de execucao econsumo de energia (ver Figura 5.3).

Figura 5.3 Simulador-CPN.

O algoritmo [Law and Kelton 1997] de simulacao do Simulador-CPN e composto pelasseguintes componentes:

� Estado da simulacao: Conjunto de variaveis necessarias para descrever o es-tado da simulacao em um tempo particular, que no ALUPAS e representado pelamarcacao do modelo;

� Tempo da simulacao: Variavel que representa o valor atual do tempo simulado;

� Agenda de eventos: Lista contendo o tempo de simulacao em que cada transicaodo modelo estara habilitada;

� Contadores estatısticos: Variaveis utilizadas para alocar informacoes estatısticassobre as metricas a serem avaliadas;

� Criterio de parada: Sao criadas varias replicacoes da simulacao ate que o criteriode parada seja satisfeito (ver Secao 4.3).

A Figura 5.4 descreve o algoritmo de simulacao do ALUPAS.

5.4 GUI 30

Figura 5.4 Algoritmo de simulacao.

5.4 GUI

O ALUPAS prove uma interface grafica para facilitar a interacao projetista-simulacao.Esta interface foi desenvolvida de forma a permitir que os detalhes do modelo e dasimulacao ficassem transparentes ao projetista. Assim, nao e necessario que o projetistapossua qualquer conhecimento sobre as CPN para utilizar o ALUPAS.

A Figura 5.5 exibe a tela de entrada do ALUPAS (aba Input ativa). Para realizar umasimulacao, o projetista primeiro cria um novo projeto, insere seu codigo, depois insereas anotacoes sobre as probabilidades e criterio de parada, e finalmente, basta compilar(botao Compile) e simular o codigo (botao Simulate). Adicionalmente, existe a opcao desalvar um projeto e/ou abrir um projeto salvo atraves do menu File. O campo Status,situado na parte inferior desta aba, e utilizado para exibir mensagens de sucesso e/ouerros na compilacao/simulacao.

O ALUPAS permite que o projetista faca varias simulacoes em um mesmo codigo. Osresultados destas simulacoes ficam registrados e podem, posteriormente, ser consultadose comparados entre si, facilitando a avaliacao dos cenarios de execucao do codigo. AFigura 5.6 exibe a tela de saıda do ALUPAS (aba Output ativa), onde sao exibidos osresultados das simulacoes. O campo Simulation Results, ao lado esquerdo da interface,permite que o projetista visualize os resultados das metricas em avaliacao. Nesta aba(Output) tambem e possıvel plotar os graficos das simulacoes (ver Simulation Plots, aolado direito da interface). Existem dois tipos de graficos possıveis: histograma e grafico

5.5 INTEGRACAO DOS COMPONENTES 31

Figura 5.5 Interface de entrada do ALUPAS.

de caixa.A Figura 5.7 exibe os menus File, Project e Help expandidos. O menu File, possui

opcoes que permitem, por exemplo, criar um novo projeto e abrir um projeto. O menuProject permite, dente outras opcoes, visualizar o modelo CPN da simulacao. Pelo menuHelp e possıvel acessar informacoes sobre a versao do ALUPAS.

5.5 INTEGRACAO DOS COMPONENTES

O ALUPAS e composto por varios componentes independentes: Compilador Binario-CPN, Simulador-CPN e outros. A Figura 5.8 exibe como cada um destes componentesse relacionam para formar o ALUPAS.

Resumidamente, o processo de avaliacao de um codigo segue os seguintes passos.Primeiro, o codigo anotado a ser avaliado e compilado pelo Assembler. Em seguida, ocodigo binario gerado no primeiro passo e utilizado pelo Compilador Binario-CPN paragerar a composicao dos modelos basicos, gerando o modelo CPN que servira para realizaras avaliacoes. O ultimo passo e avaliar o modelo gerado pelo Compilador Binario-CPNutilizando o Simulador-CPN e apresentar os resultados.

Varios avancos foram feitos no sentido de tambem avaliar codigos em C. Ao concluireste trabalho, esta funcionalidade encontrava-se quase finalizada, restando apenas au-tomatiza-la no ALUPAS, pois algumas tarefas do processo ainda precisavam ser feitasmanualmente. O processo de avaliacao de codigos em C e identico ao descrito anterior-mente. As unicas diferencas sao que no lugar de um Assembler, e necessario utilizar umcompilador para a linguagem C, e, tambem, ao inves de utilizar codigos assembly comanotacoes, sao utilizados codigos em C com anotacoes. As anotacoes sobre o criterio deparada sao inseridas no inıcio do codigo em C e as probabilidades sao colocadas ao lado


Figura 5.6 Interface de saıda do ALUPAS.

Figura 5.7 (a)Menu File, (b)Menu Project, (c)Menu Help.

dos comandos de controle.


Este Capıtulo apresentou o ambiente de simulacao ALUPAS, cada componente do am-biente (Assembler, Compilador-CPN, Simulador-CPN e GUI) foi detalhado. Adicional-mente, este Capıtulo mostrou como cada um destes componentes se relacionam paraformar o ALUPAS. O Capıtulo apresentou tambem a metodologia adotada por ALUPASpara estimar o consumo de energia e tempo de execucao de um codigo. A metodologiaconsiste, principalmente, na representacao do codigo anotado no modelo CPN apresen-tado no Capıtulo 4 e a posterior simulacao deste modelo pelo Simulador-CPN para geraras estimativas de desempenho e consumo de energia.

O ambiente de simulacao ALUPAS foi desenvolvido em Java e possui uma interfacegrafica para facilitar a interacao projetista-simulacao, permitindo que os detalhes dasimulacao e do modelo formal da simulacao ficassem transparentes ao projetista. Assim,nao e necessario que o projetista possua qualquer conhecimento sobre as Redes de Petri


Figura 5.8 Componentes integrados.

Coloridas para utilizar o ALUPAS.

CAPITULO 6

EXPERIMENTOS

Alguns experimentos foram realizados a fim de demonstrar e validar o funcionamento doALUPAS. Todos os experimentos foram feitos utilizando uma maquina com a seguinteconfiguracao: Pentium IV HT 3Ghz, 1.5 Gb RAM e sistema operacional Windows XP.

6.1 EXPERIMENTO 1

O primeiro exemplo tem por finalidade exemplificar a metodologia de avaliacao e, tambem,comparar os resultados do ALUPAS com os do CPN Tools. A Figura 6.1 exibe o codigoassembly com anotacoes a ser avaliado. Na primeira linha do codigo, esta a definicaodo criterio de parada. Note que o nıvel de confianca foi ajustado para 95% e os errosmaximos admitidos para o consumo de energia e tempo de execucao ajustados para 200nJ e 0.2 µs, respectivamente.

Como explicado na Secao 4.1, os registradores nao sao armazenados pelo modelo,ao inves disso, uma abordagem probabilıstica e adotada. No codigo deste experimento,existe um loop (linhas 16-20), que e iterado 10 vezes. Dentro do loop, o valor armazenadono registrador r4 e incrementado de um 1 a cada iteracao, ate este valor chegar a 10(inicialmente o valor e 1). O controle das iteracoes e feito pela instrucao blt na linha 20(ver anotacao de probabilidade nesta linha). Durante a execucao do codigo, esta instrucaoverifica o valor armazenado em r4 e desvia o fluxo para uma nova iteracao caso este valorseja diferente de 10, caso contrario, a condicao e avaliada como falsa e nao ocorre odesvio. Este comportamento pode ser modelado probabilisticamente e a probabilidadedesta instrucao pode ser calculada atraves da frequencia relativa com que a condicao dedesvio e avaliada como verdadeira. Para o presente caso, a probabilidade e p = 9

10, isto e,

a cada 10 avaliacoes, a condicao e satisfeita em 9. Apesar de loop ser iterado 10 vezes, acondicao para uma nova iteracao e satisfeita apenas em 9, isso acontece pois a condicaoso e avaliada apos a primeira iteracao.

Durante a compilacao do codigo pelo Compilador Binario-CPN (ver Secao 5.2), aprobabilidade calculada e inserida na variavel prob do modelo basico de desvio condi-cional (ver Secao 4.1). A Figura 4.6 exibe o fluxo de controle deste loop no modeloproposto. O modelo exibido nesta Figura, nao foi reduzido (ver Secao 4.2) para ummelhor entendimento.

6.1.1 Resultados

O codigo foi avaliado de tres formas diferentes: (i) utilizando o CPN Tools e o modelonao reduzido (sem aplicar o processo de reducao ao modelo), (ii) utilizando o CPN Toolse o modelo reduzido e (iii) utilizando o ALUPAS e o modelo reduzido.

34

6.1 EXPERIMENTO 1 35

Figura 6.1 Codigo do experimento 1.

A Tabela 6.1 exibe um comparativo dos resultados. E possıvel observar que os resulta-dos do CPN Tools utilizando os modelos reduzidos e nao reduzidos sao iguais, mostrandoque a reducao do modelo pelo processo de reducao preservou as caracterısticas necessariaspara estimar o tempo de execucao e consumo de energia.

O resultado utilizando o ALUPAS apresentou um consumo medio de energia de 167.3nJ e erro de 7 nJ. Como o nıvel de confianca foi ajustado para 95% (ver linha 1 docodigo), ALUPAS informa que o valor que estamos querendo medir, com 95% de certezaesta entre [160.3;174.3] nJ. Ja a simulacao utilizando o CPN Tools apresentou um consumomedio de 167.4 nJ, com erro de 10 nJ, informando que, com 95% de certeza, o valor queestamos querendo medir esta entre [157.3;177.3] nJ. As mesmas inferencias podem serfeitas para o tempo de execucao. A diferenca entre os resultados apresentados pelo CPNTools e ALUPAS foram menores que 2% mostrando que as duas ferramentas apresentamresultados semelhantes.

Tabela 6.1 Comparativo dos resultados para o exemplo 1.

Modelo nao reduzido Modelo reduzidoMetrica CPN Tools CPN Tools ALUPAS

Consumo medio 167.4008 nJ 167.4008 nJ 167.2632 nJDesvio padrao p/ consumo 14.1533 nJ 14.1533 nJ 10.7243 nJErro p/ media do consumo 10.1240 nJ 10.1240 nJ 7.6717 nJTempo medio 2.2320 µs 2.2320 µs 2.2279 µsDesvio padrao p/ tempo 0.1905 µs 0.1905 µs 0.1444 µsErro p/ media do tempo 0.1363 µs 0.1363 µs 0.1033 µs


6.2 EXPERIMENTO 2

O segundo experimento tem como objetivo fazer um comparativo entre a velocidade desimulacao do ALUPAS e o CPN Tools. Ele tambem demonstra a importancia do processode reducao do modelo. Este experimento e formado por codigos que possuem instrucoesrepresentadas apenas pelo modelo de instrucao ordinaria (ver Figura 4.1). O tamanhodos codigos avaliados varia em ordem crescente de 10 a 400 instrucoes.

Tabela 6.2 Comparativo do tempo de simulacao.

Modelo CPN Modelo CPN reduzidoN Inst. CPN Tools ALUPAS CPN Tools ALUPAS

10 17s 187ms 6s 187ms20 21s 219ms 6s 187ms30 30s 234ms 6s 187ms40 41s 281ms 6s 187ms50 56s 297ms 6s 187ms

100 1min 51s 515ms 6s 187ms200 5min 6s 1s 219ms 6s 187ms400 17min 25s 3s 438ms 6s 187ms

6.2.1 Resultados

Figura 6.2 Comparativo entre o CPN Tools e ALUPAS.

Os codigos foram simulados de quatro formas diferentes: i) Usando o CPN Tools commodelo nao reduzido; ii) Usando CPN Tools e o modelo reduzido; iii) Usando ALUPAScom o modelo nao reduzido; iv) Utilizando o ALUPAS com o modelo reduzido. A Tabela6.2 exibe o comparativo dos tempos de simulacao dos modelos, onde se observa que oALUPAS foi entre 32 e 303 vezes mais rapido que o CPN Tools. Essa diferenca aumenta


a medida que o tamanho do modelo cresce. Tambem, e possıvel verificar a importanciado processo de reducao e que as simulacoes utilizando o modelo reduzido apresentaramtempo de simulacao constante. Isto e explicado pelo fato de os codigos simulados naoapresentarem instrucoes de desvio condicional. Este padrao permitiu que o processo dereducao agrupasse as instrucoes do codigo em apenas um bloco basico.

A Figura 6.2 exibe graficamente um comparativo entre o tempo de simulacao do CPNTools e ALUPAS, ambos utilizando o modelo nao reduzido.

6.3 EXPERIMENTO 3

Figura 6.3 Codigo do assembly anotado do Busca Binaria.

O terceiro experimento tem como objetivo validar o simulador e consiste em avaliaro codigo assembly do Busca Binaria para um vetor com 255 elementos (ver Figura 6.3).Seu equivalente na linguagem C e exibido na Figura 6.4. O comportamento da execucaodo codigo assembly depende do elemento buscado (chave) e dos elementos presentes novetor. Esta variacao e definida pelas instrucoes de desvio condicional: Inst14 (linha 14) eInst23 (linha 23) e Inst30 (linha 30). Durante a execucao, o fim das iteracoes e definidopor Inst30 ou Inst14. Se o elemento for localizado em uma determinada iteracao, Inst14


Figura 6.4 Busca Binaria na linguagem C.

nao realiza o desvio e a busca termina com sucesso nesta iteracao. Se o elemento buscadonao for encontrado em nenhuma das iteracoes, Inst30 e quem limita o numero maximode iteracoes. Inst23 define se a busca deve continuar na metade posterior ou inferior dovetor.

O codigo foi avaliado em tres cenarios diferentes: melhor caso (BCET - Best CaseExecution Time), caso medio (TCET - Typical Case Execution Time) e pior caso (WCET- Worst Case Execution Time). Para cada cenario foram associadas as instrucoes condi-cionais um conjunto especıfico de probabilidades. Estas probabilidades representam ofluxo de execucao do codigo para o cenario escolhido.

O pior caso ocorre na busca de um elemento inexistente. No pior caso, o numero deiteracoes e 8 (log2(255)). Em contrapartida a este cenario, no melhor caso, o elemento eencontrado na primeira iteracao, isto e, no meio do vetor. No caso tıpico, a probabilidadede um elemento ser localizado na i-esima iteracao e 2i−1

255. Assim, o numero medio de

iteracoes necessarias para localizar um elemento e∑8

i=1 i · 2i−1

255∼= 7.

No pior caso, Inst30 e quem delimita o fim das iteracoes. Para que sejam executadas 8iteracoes, e necessario que a condicao utilizada por Inst30 seja avaliada como verdadeira8 vezes. Assim, probabilidade de Inst30 e p = 8

9. Sabendo que a chave nao devera

ser encontrada no vetor, a probabilidade de Inst14 e ”1”. Nao e possıvel identificarde imediato se o tempo de execucao e maior caso o desvio especificado por Inst23 sejaefetuado. Para responder a esta questao, foram testadas duas probabilidades para Inst23:”1” e ”0”. Verificou-se que quando Inst14 tem probabilidade ”0” o tempo de execucaoe maior. Figura 6.3 exibe o codigo anotado com as probabilidades que representam ocenario de pior caso.


No melhor caso, so ha uma iteracao. O desvio especificado por Inst28 sempre ocorre elogo em seguida o elemento e identificado por Inst12. Desta forma, para avaliar o melhorcaso, as probabilidades das instrucoes Inst28 e Inst12 devem ser ”1” e ”0” respectiva-mente. A probabilidade de Inst21 e irrelevante, ja que no melhor caso, o fluxo nuncachegara a este ponto.

No caso tıpico, quem delimita o fim das iteracoes e Inst12. Assim, Inst28 tem prob-abilidade ”1”. Havendo em media 7 iteracoes, Inst12 tem probabilidade ”6

7” de realizar

o desvio. Isto e, na setima verificacao Inst12 nao realiza o desvio e a busca terminacom sucesso. No caso tıpico, Inst21 tem probabilidade ”0.5”, ja que a busca possui igualprobabilidade de continuar na metade posterior ou inferior do vetor.

6.3.1 Resultados

Figura 6.5 Busca Binaria - Tempo de execucao: estimado x medido.

Figura 6.6 Busca Binaria - Consumo de energia: estimado x medido.

Para cada cenario, Figura 6.5 e Figura 6.6 exibem os resultados reais medidos nohardware e as estimativas geradas por ALUPAS. Analisando as figuras, e possıvel observarque as estimativas foram bastante exatas. Os erro entre o que foi medido e estimado foiem media de 3%.


Os resultados do hardware para o caso tıpico foram obtidos atraves do valor medio de50 execucoes do Busca Binaria, onde os elementos buscados eram elementos aleatorios,com distribuicao uniforme.

Figura 6.7 Consumo de energia: pior caso.

Figura 6.8 Tempo de execucao: pior caso.

Uma vez validados os resultados para um vetor de 255 elementos, o ALUPAS foiutilizado para estimar o pior caso para vetores de outros tamanhos. Utilizando as mesmasprobabilidades ja inferidas do pior caso para um vetor de 255 elementos, as simulacoesforam feitas apenas variando-se apenas a probabilidade de Inst30. As probabilidadesassociadas a Inst30 para estas simulacoes foram: p = 4/5 (15 elementos), p = 5/6(31 elementos), p = 6/7 (63 elementos), e assim sucessivamente ate p = 10/11 (1023elementos). A Figura 6.8 e Figura 6.7 exibem os resultados das simulacoes.

6.4 EXPERIMENTO 4

O quarto experimento consiste em avaliar o algoritmo BCNT. O BCNT foi proposto pelaMotorola e e parte do pacote Power Stone Benchmark [Malik et al. 2000]. Este pacote


utiliza algoritmos de diferentes segmentos do mercado de sistemas embarcados como,por exemplo, algoritmos de processamento de sinais, imagem e automacao, para medir oconsumo de energia de uma arquitetura.

O algoritmo do BCNT adota um serie de comparacoes entre dois arrays, explora amanipulacao do espaco de estado da memoria e, tambem, adota comparacoes bitwise.A avaliacao consistiu na analise do caso medio de execucao do BCNT, dado que estealgoritmo possui apenas um fluxo de execucao.

6.4.1 Resultados

As Figuras 6.9 e 6.10 exibem os resultados da simulacao do BCNT. O erro em relacaoas medidas estimadas e medidas foi de %2.2 para o consumo de energia e %4.1 para otempo de execucao.

Figura 6.9 BCNT - Tempo de execucao: estimado x medido.

Figura 6.10 BCNT - Consumo de energia: estimado x medido.

6.5 EXPERIMENTO 5

O quinto experimento objetiva validar o ALUPAS atraves da avaliacao de uma aplicacaoembarcada real: o Oxımetro de Pulso [Junior 1998]. O oxımetro e um equipamentoresponsavel por medir o nıvel de saturacao do oxigenio utilizando um metodo nao invasivo.Esta aplicacao utiliza duas categorias tecnologicas distintas: a tecnologia analogica e adigital. A aquisicao e condicionamento do sinal proveniente do meio biologico e feitapor estruturas analogicas devido a natureza analogica do sinal de interesse. A extracaoda informacao de saturacao e frequencia cardıaca e realizada mediante a digitalizacao


do sinal e seu processamento por algoritmos computacionais especıficos. Sendo assim,o instrumento e formado por um modulo analogico e um microprocessado (digital). NaFigura 6.11 observa-se a estrutura generica de um oxımetro de pulso.

Figura 6.11 Estrutura do Oxımetro de Pulso, retirado de [Junior 1998].

A unidade microprocessada cumpre o papel de controlar os padroes de excitacaode forma a manter a melhor situacao de leitura possıvel. A interface com o usuarioe constituıda de mostradores de sete segmentos e chaves de programacao de alarmesmaximos e mınimos para a saturacao e frequencia cardıaca. Alguns oxımetros oferecemtambem a apresentacao do sinal fotopletismografico em um mostrador grafico.

O sistema do oxımetro de pulso e dividido em tres partes distintas, denominadasplanos. Os planos sao procedimentos que executam independentemente um dos outros.Cada um destes planos e dividido em sub-tarefas. Seguindo este conceito, nomeia-se osplanos de acordo com a atividade macro que eles desempenham. Sao elas:

� Plano 1 - Rotina de Excitacao;

� Plano 2 - Rotinas de Amostragem e Controle;

� Plano 3 - Programa Gerenciador.

Neste estudo de caso, considerou-se para avaliacao apenas o Plano 1 e o Plano 2,dado que o Plano 3 diz respeito a inicializacao do sistema, atendimento aos comandos dousuario entre outras atividades de menor relevancia neste contexto.

No Plano 1 - Rotina de Excitacao sao realizadas as seguintes tarefas:

� Geracao dos pulsos de excitacao, vermelho e infravermelho;

� Temporizacao entre os pulsos de excitacao vermelho e infravermelho;

� Controle da frequencia dos pulsos de excitacao: vermelho e infravermelho;

� Leitura do conversor digital/analogico.


O Plano 2 - Rotinas de Amostragem e Controle e composto por dois procedimentos.Estes dois procedimentos sao executados em sequencia e realizam as seguintes tarefas:

� Amostragem

– Disparo de Conversao A/D;

– Aguarda conversao;

– Le conversor;

– Carrega vetores;

� Controle

– Regula varredura;

– Mostra resultados/curva.

– Gerenciamento;

– Cardiobeep.

6.5.1 Resultados

Foram avaliados os casos medios de execucao dos Planos 1 e 2. Fluxos de excecao queocorrem, por exemplo, quando a aplicacao esta calibrando o circuito de excitacao ouquando sao detectados erros no recebimento dos sinais de entrada, nao foram considera-dos.

Tabela 6.3 Resultados do exemplo 5 - Oxımetro de Pulso.

Tempo de execucao Consumo de energia Erro: estimado x medidoPlano Estimado Medido Estimado Medido Energia Tempo

Excitacao 38.89 µs 38.88 µs 2.29 µJ 2.25 µJ 1.8% 0.02%Amostragem 86.61 µs 91.18 µs 5.16 µJ 5.55 µJ 7.5% 5.27%Controle 12410.78 µs 12745.99 µs 708.59 µJ 779.46 µJ 10% 0.27%

A Tabela 6.3 exibe os resultados do experimento. Para validar este estudo de caso,um intervalo de confianca para diferenca entre os valores estimados e medidos utilizandoo teste-t nao-emparelhado [Lilja 2000] foi construıdo. Adotando esta abordagem buscou-se quantificar a probabilidade dos valores estimados e medidos serem estatisticamentediferentes.

Excitacao

Para o procedimento Excitacao, as Tabela 6.4 e 6.5 exibem os dados de entrada parao teste. Aplicando o teste-t nao-emparelhado nos dados do tempo de execucao com con-fianca de 95%, obtem-se o seguinte intervalo para a diferenca das medias: [-0.293; 0.313].


Tabela 6.4 Excitacao - comparacao do tempo de execucao.

Numero de amostras Media Desvio padrao

Simulador 416 38.89 3.14Hardware 1000 38.88 0.007

Tabela 6.5 Excitacao - comparacao do consumo de energia.


Simulador 416 2.29 0.18Hardware 1000 2.25 0.06E-5

Como o intervalo inclui o 0, e possıvel afirmar com 95% de certeza que estatisticamentenao ha diferenca significativa entre os resultados para o tempo de execucao. Aplicando oteste-t para os dados do consumo de energia com confianca de 95%, obtem-se o seguinteintervalo para a diferenca das medias: [0.023; 0.059]. Como o intervalo nao inclui o 0, naoe possıvel afirmar que nao ha diferenca significativa nos resultados, no entanto, e possıvelinferir, que esta diferenca e de no maximo 0.059, com 95% de certeza. Isto e, a diferencae de no maximo 2.5%, com 95% de certeza.

Amostragem

Tabela 6.6 Amostragem - comparacao do tempo de execucao.


Simulador 2225 86.61 5.62Hardware 1000 91.18 3E-7

Tabela 6.7 Amostragem - comparacao do consumo de energia.



As Tabelas 6.8 e 6.9 exibem os dados de entrada para o teste nos resultados do proced-imento Amostragem. Realizando o mesmo procedimento do exemplo anterior, obtem-seos intervalos [-4.802; -4.338] e [-0,403; -0,376] para as diferencas do tempo de execucao e


consumo de energia, respectivamente. Como nenhum dos dois intervalos inclui o 0, nao epossıvel afirmar que nao ha diferenca significativa nos resultados. No entanto, e possıvelafirmar com 95% de certeza que a diferenca maxima entre os resultados para o tempo deexecucao e consumo de energia sao respectivamente de 5.5% e 7.8%.

Controle

Tabela 6.8 Controle - comparacao do tempo de execucao.


Simulador 92 12411 1708Hardware 1000 12746 1.1E-6

Tabela 6.9 Controle - comparacao do consumo de energia.



As Tabelas 6.8 e 6.9 exibem os dados de entrada para o teste nos resultados do proced-imento Controle. Realizando o mesmo procedimento dos exemplos anteriores, obtem-seos intervalos [-689; 18] e [-91,1; -50,7] paras as diferencas do tempo de execucao e con-sumo de energia, respectivamente. Como o primeiro intervalo inclui o 0, e possıvel afirmarcom 95% de certeza que nao ha diferenca significativa nos resultados para o tempo deexecucao. O segundo intervalo nao inclui o 0 e infere-se a partir daı que com 95% decerteza a diferenca maxima para o consumo de energia e de 11%.


Este Capıtulo apresentou alguns experimentos que foram realizados a fim de demonstrare validar o funcionamento do ALUPAS. O primeiro experimento objetivou exemplificarmetodologia de avaliacao e comparar os resultados gerados por ALUPAS e o CPN Tools.O segundo experimento consistiu em comparar a velocidade do ALUPAS e o CPN Tools,alem de mostrar a importancia do processo de reducao. O terceiro, quarto e quintoexperimento tiveram como objetivo validar o ALUPAS atraves da comparacao dos resul-tados estimados por ALUPAS e os resultados reais medidos no hardware. E importanteressaltar que no quinto experimento uma aplicacao embarcada real foi avaliada.

Os resultados estimados foram bem proximos dos reais, com erro em media de 6% eerro maximo de 10%. O ALUPAS tambem apresentou desempenho bastante superior aoCPN Tools, em alguns casos o ALUPAS foi 303 vezes mais rapido que o CPN Tools. Esta


diferenca de desempenho ocorreu devido ao fato do ALUPAS utilizar um simulador es-pecıfico (Simulador-CPN) criado para avaliar os modelos gerados conforme a metodologiaexplicada no Capıtulo 5. E, por se tratar de uma ferramenta generica para edicao e sim-ulacao de CPN, o CPN Tools possui funcionalidades (nao existentes no Simulador-CPN)que fazem com seu desempenho seja inferior ao do ALUPAS.

CAPITULO 7

CONCLUSAO

Este trabalho apresentou o ALUPAS, um simulador estocastico cujo objetivo e estimar odesempenho e consumo de energia em softwares para sistemas embarcados. A modelagemda simulacao foi feita atraves de uma abordagem formal utilizando as Redes de PetriColoridas (CPN), onde cada instrucao de um microcontrolador da famılia ARM7 foimodelada de forma a reproduzir o comportamento da execucao de um codigo durante asimulacao. Utilizando uma abordagem estocastica, mostrou-se que os varios cenarios deexecucao do software podem ser analisados de maneira simples.

Uma interface grafica para o simulador foi construıda, permitindo que os detalhes dasimulacao e do modelo formal da simulacao ficassem transparentes ao projetista. Assim,nao e necessario que o projetista possua qualquer conhecimento sobre as Redes de PetriColoridas para utilizar o ALUPAS.

O ALUPAS apresentou desempenho bem superior ao CPN Tools - em alguns casosALUPAS chegou a ser 304 vezes mais rapido que o CPN Tools. Esta diferenca de desem-penho ocorreu devido ao fato do ALUPAS utilizar um simulador especıfico (Simulador-CPN) criado para avaliar os modelos gerados. E, por se tratar de uma ferramenta genericapara edicao e simulacao de CPN, o CPN Tools possui funcionalidades adicionais (nao ex-istentes no Simulador-CPN) que fazem com seu desempenho seja inferior ao do ALUPAS.

Os resultados dos experimentos mostraram-se bastante precisos em comparacao aosvalores reais medidos no hardware (exatidao em media de 94%). Estes resultados mostramclaramente que o simulador ALUPAS pode ser utilizado para analisar e, assim: (i) verificarse o projeto atende aos requisitos de baixo consumo de energia e (ii) fundamentar asotimizacoes com relacao ao consumo de energia que o projeto pode sofrer. E importanteressaltar que a analise pode ser feita ainda nas fases iniciais de desenvolvimento, ondemuitas vezes o hardware nao esta disponıvel.

Com base nas analises obtidas por ALUPAS e possıvel tambem construir compiladoresque otimizem o codigo com relacao ao consumo de energia e nao apenas com relacao aotamanho ou tempo de execucao do codigo, como usualmente e feito. Com o objetivo deotimizar o consumo de energia do codigo gerado, inumeras tecnicas de codificacao podemsistematicamente ser avaliadas no ALUPAS e integradas a estes compiladores.

Como trabalho futuro e em andamento, e preciso ressaltar que o ALUPAS esta sendoestendido de forma a aceitar nao apenas codigos fonte em formato Assembly, mas tambemcodigos em C. Outra funcionalidade que ja esta sendo desenvolvida e logo sera incluıda aoALUPAS e a possibilidade de analise por blocos de instrucao, ao inves da analise em todosoftware como unica opcao. Com esta nova funcionalidade pretende-se identificar quaistrechos de codigo estao gastando muita energia e/ou com baixo desempenho para queassim o projetista reconheca com mais exatidao quais trechos precisam ser otimizados.

Uma vez que as Redes de Petri Coloridas fornecem o formalismo ideal para modelar

47

CONCLUSAO 48

sistemas concorrentes, paralelos e assıncronos, uma extensao natural deste trabalho eestender os modelos atuais para que seja possıvel a analise em sistemas embarcadosmultiprocessados (multiplos processadores). Neste contexto, outras questoes devem serlevadas em consideracao no modelo da simulacao como, por exemplo, a comunicacaointer-processador.

REFERENCIAS BIBLIOGRAFICAS

[Andrade et al. 2009] Andrade, E., Maciel, P., Callou, G., and Nogueira, B. (2009). Map-ping uml sequence diagram to time petri net for requirement validation of embeddedreal-time systems with energy constraints. Proceedings of the 24th Annual ACM Sym-posium on Applied Computing, 2009.

[ARM ] ARM. Realview compilation tool 3.0. http://www.arm.com/.

[Banks 1999] Banks, J. (1999). Introduction to simulation. In Proceedings of the 31stconference on Winter simulation: Simulation—a bridge to the future-Volume 1, pages7–13. ACM New York, NY, USA.

[Barron 1978] Barron, D. (1978). Assemblers and Loaders. Elsevier Science Inc. NewYork, NY, USA.

[Bose et al. 2001] Bose, P., Brooks, D., Irwin, M., Kandemir, M., Martonosi, M., andVijaykrishnan, N. (2001). Power-efficient design: Modeling and optimizations. 28thInternational Symposium on Computer Architecture.

[Brooks et al. 2003] Brooks, D., Bose, P., Srinivasan, V., Gschwind, M., Emma, P., andRosenfield, M. (2003). Microarchitecture-level power-performance analysis: the pow-ertimer approach. IBM J. Research and Development, 47(5/6):653–670.

[Brooks et al. 2000] Brooks, D., Tiwari, V., and Martonosi, M. (2000). Wattch: a frame-work for architectural-level power analysis and optimizations. Proceedings of the 27thannual international symposium on Computer architecture, pages 83–94.

[Chung 2004] Chung, C. (2004). Simulation Modeling Handbook: A Practical Approach.CRC Press.

[Colin and Puaut 2000] Colin, A. and Puaut, I. (2000). Worst Case Execution TimeAnalysis for a Processor with Branch Prediction. Real-Time Systems, 18(2):249–274.

[Florescu et al. 2006] Florescu, O., de Hoon, M., Voeten, J., and Corporaal, H. (2006).Probabilistic modelling and evaluation of soft real-time embedded systems. Proceedingsof SAMOS VI.

[Friedenthal et al. 2006] Friedenthal, S., Moore, A., and Steiner, F. (2006). OMG Sys-tems Modeling Language (OMG SysML) Tutorial. In INCOSE Intl. Symp.

[Hines et al. 2006] Hines, W. W., Montgomery, D. C., Goldsman, D. M., and Borror,C. M. (2006). Probabilidade e Estatıstica na Engenharia.

49

REFERENCIAS BIBLIOGRAFICAS 50

[Huang et al. 1995] Huang, C., Zhang, B., Deng, A., and Swirski, B. (1995). The designand implementation of PowerMill. Proceedings of the 1995 international symposiumon Low power design, pages 105–110.

[Huber et al. 1991] Huber, P., Jensen, K., and Shapiro, R. (1991). Hierarchies inColoured Petri Nets. Proceedings on Advances in Petri nets 1990 table of contents,pages 313–341.

[Irwin et al. 2001] Irwin, M., Kandemir, M., and Vijaykrishnan, N. (2001). SimplePower:A Cycle-Accurate Energy Simulator. IEEE CS Technical Committee on ComputerArchitecture Newsletter.

[Jain 1991] Jain, R. (1991). The art of computer system performance analysis: techniquesfor experimental design, measurement, simulation and modeling. John Wiley and Sons,Inc., New York USA.

[Jayaseelan et al. 2006a] Jayaseelan, R., Mitra, T., and Li, X. (2006a). Estimating theworst-case energy consumption of embedded software. In IEEE Real-Time and Embed-ded Technology and Applications Symposium, pages 81–90. IEEE Computer Society.

[Jayaseelan et al. 2006b] Jayaseelan, R., Mitra, T., and Li, X. (2006b). Estimating theworst-case execution energy of embedded software. In Proceedings of the Twelfth Real-Time and Embedded Technology and Applications Symposium (RTAS’06).

[JENSEN ] JENSEN, K. A Brief Introduction to Coloured Petri Nets, Tools and Al-gorithms for the Construction and Analysis of Systems. Proceeding of the TACAS,97:203–208.

[Jensen 1992] Jensen, K. (1992). Coloured Petri Nets: Basic Concepts, Analysis Methods,and Practical Use, volume 1 of EATCS Monographs in Computer Science. Springer-Verlag.

[Junior 1998] Junior, M. N. O. (1998). Desenvolvimento de um prototipo para a me-dida nao invasiva da saturacao arterial de oxigenio em humanos - oxımetro de pulso.Master’s thesis, Departamento de Biofısica e Radiobiologia, Universidade Federal dePernambuco.

[Krishnan 2005] Krishnan, R. (2005). Future of embedded systems technology. Technicalreport, BCC Research Group.

[Laopoulos et al. 2002] Laopoulos, T., Neofotistos, P., Kosmatopoulos, C., and Niko-laidis, S. (2002). Current variations measurements for the estimation of software-relatedpower consumption. Instrumentation and Measurement Technology Conference, 2002.IMTC/2002. Proceedings of the 19th IEEE, 2.

[Laurent et al. 2001] Laurent, J., Senn, E., Julien, N., and Martin, E. (2001). High LevelEnergy Estimation for DSP Systems. In Proc. Int. Workshop on Power And TimingModeling, Optimization and Simulation PATMOS, pages 311–316.


[Law and Kelton 1997] Law, A. and Kelton, W. (1997). Simulation Modeling and Anal-ysis. McGraw-Hill Higher Education.

[Lilja 2000] Lilja, D. (2000). Measuring computer performance. Cambridge UniversityPress New York.

[Limited 2001] Limited, A. (2001). Arm7tdmi technical reference manual. ARM DDI0210A.

[Lu and De Micheli 2001] Lu, Y. and De Micheli, G. (2001). Comparing System-LevelPower Management Policies. IEEE DESIGN & TEST OF COMPUTERS, pages 10–19.

[MACIEL et al. 1996] MACIEL, P., LINS, R., and CUNHA, P. (1996). Introducao asRedes de Petri e Aplicacoes. X Escola de Computacao, Campinas, SP.

[Malik et al. 2000] Malik, A., Moyer, B., and Cermak, D. (2000). A low power unifiedcache architecture providing power and performance flexibility (poster session). InProceedings of the 2000 international symposium on Low power electronics and design,pages 241–243. ACM New York, NY, USA.

[Marculescu and Nandi 2001] Marculescu, R. and Nandi, A. (2001). Probabilistic appli-cation modeling for system-level perfromance analysis. Design, Automation, and Testin Europe: Proceedings of the conference on Design, automation and test in Europe,2001:572–579.

[Mentor ] Mentor. http://www.mentor.com/.

[Murata 1989] Murata, T. (1989). Petri nets: Properties, analysis and applications.Proceedings of the IEEE, 77(4):541–580.

[Nikolaidis and Neofotistos 2002] Nikolaidis, N. and Neofotistos, P. (2002). Instruction-level Power Measurement Methodology. Electronics Lab, Physics Dept., Aristotle Uni-versity of Thessaloniki, Greece, March.

[Nikolaidis et al. ] Nikolaidis, S., Kavvadias, N., and Neofotistos, P. Instruction levelpower models for embedded processors. Technical report, IST-2000-30093/EASYProject, Deliv. 21, Dec. 2002. http://easy. intranet. gr.

[Nikolaidis et al. 2002] Nikolaidis, S., Kavvadias, N., and Neofotistos, P. (2002). In-struction level power models for embedded processors. Technical report, IST-2000-30093/EASY Project, Deliv. 21, Dec. 2002. http://easy. intranet. gr.

[Oliveira et al. 2006] Oliveira, M., Neto, S., Maciel, P., Lima, R., Ribeiro, A., Barreto,R., Tavares, E., and Braga, F. (2006). Analyzing software performance and energyconsumption of embedded systems by probabilistic modeling: An approach based oncoloured petri nets. ICATPN 2006, LNCS, 4024:261281.

[Paulson 1996] Paulson, L. (1996). ML for the Working Programmer. Cambridge Uni-versity Press.


[Petri 1962] Petri, C. (1962). Kommunikation mit Automaten. PhD thesis, Rheinisch-Westfalisches Institut f. instrumentelle Mathematik an d. Univ.

[Ratzer et al. 2003] Ratzer, A., Wells, L., Lassen, H., Laursen, M., Qvortrup, J., Stissing,M., Westergaard, M., Christensen, S., and Jensen, K. (2003). CPN Tools for Editing,Simulating, and Analysing Coloured Petri Nets. Applications and Theory of Petri Nets,2003:24th.

[Russell and Jacome 1998] Russell, J. and Jacome, M. (1998). Software power estimationand optimization for high performance, 32-bit embedded processors. In Proc. Int. Conf.Computer Design, pages 328–333.

[Sanchez 1999] Sanchez, S. (1999). ABC’s of output analysis. In Simulation ConferenceProceedings, 1999. Winter, volume 1.

[Sangiovanni-Vincentelli and Martin 2001] Sangiovanni-Vincentelli, A. and Martin, G.(2001). Platform-Based Design and Software Design Methodology for Embedded Sys-tems. IEEE DESIGN & TEST OF COMPUTERS, pages 23–33.

[Semiconductors ] Semiconductors, P. Philips LPC2106/2105/2104 User Manual [Z/OL].

[Senn et al. 2002] Senn, E., Julien, N., Laurent, J., and Martin, E. (2002). Power Con-sumption Estimation of a C Program for Data-Intensive Applications. LECTURENOTES IN COMPUTER SCIENCE, pages 332–341.

[Senn et al. 2004] Senn, E., Laurent, J., Julien, N., and Martin, E. (2004). SoftExplorer:Estimation, Characterization, and Optimization of the Power and Energy Consumptionat the Algorithmic Level. LECTURE NOTES IN COMPUTER SCIENCE, pages 342–351.

[Shaw 2000] Shaw, A. (2000). Real-Time Systems and Software. John Wiley & Sons, Inc.New York, NY, USA.

[Silberschatz and Galvin 1994] Silberschatz, A. and Galvin, P. (1994). Operating SystemConcepts. Addison Wesley Publishing Company.

[Sinha and Chandrakasan 2001] Sinha, A. and Chandrakasan, A. (2001). JouleTrack-A Web Based Tool for Software Energy Profiling. Proceedings of the 38th DesignAutomation Conference (DAC 2001), pages 220–225.

[Steinke et al. 2001] Steinke, S., Knauer, M., Wehmeyer, L., and Marwedel, P. (2001).An accurate and fine grain instruction-level energy model supporting software opti-mizations. Proc. of PATMOS.

[Tavares 2007] Tavares, E. (2007). Amalghma tool.http://www.cin.ufpe.br/∼eagt/tools/.


[Tavares et al. 2008] Tavares, E., Maciel, P., Silva, B., and Oliveira, M. (2008). Hard real-time tasks’ scheduling considering voltage scaling, precedence and exclusion relations.Information Processing Letters.

[Tiwari et al. 1994] Tiwari, V., Malik, S., and Wolfe, A. (1994). Power analysis of em-bedded software: a first step towards software power minimization. Very Large ScaleIntegration (VLSI) Systems, IEEE Transactions on, 2(4):437–445.

[Wells 2002] Wells, L. (2002). Performance Analysis Using Coloured Petri Nets. PhDthesis, PhD thesis, University of Aarhus, July 2002.

[Yamamoto et al. 2006] Yamamoto, K., Ishikawa, Y., and Matsui, T. (2006). Portableexecution time analysis method. Proceedings of the 12th International Conference onEmbedded and Real-Time Computing and Applications, Sydney, Australia, Aug.

[Zhou et al. 1999] Zhou, T., Hu, X., and Sha, E. (1999). A probabilistic performancemetric for real-time system design. Hardware/Software Codesign, 1999.(CODES’99)Proceedings of the Seventh International Workshop on, pages 90–94.

[ZUBEREK 1991] ZUBEREK, W. (1991). Timed Petri Nets definitions, properties, andapplications. Microelectronics and reliability, 31(4):627–644.

APENDICE A

CARACTERIZACAO DO MICROPROCESSADOR

Como mencionado na Secao 1.2, o alvo deste trabalho e o microprocessador LPC2106.O LPC2106 e um microprocessador RISC de 32-bits, com pipeline de 3 estagios e semmemoria cache, baseado no ARMTDMI-S. Apesar de nao existir cache no LPC2106, estemicroprocessador possui um mecanismo de busca rapida na memoria, chamado MAM(Memory Accelerator Module). Este mecanismo permite que o microprocessador executecodigos em sua frequencia mais alta. Por questoes de escopo, a caracterizacao destemicroprocessador foi feita com o MAM desligada.

O LPC2106 permite ao projetista o desenvolvimento de aplicacoes de alto desempenhoe baixo consumo de energia. A escolha deste microprocessador por este trabalho e devidaa sua grande utilizacao em aplicacoes de tempo-real, onde o consumo de energia e umaquestao central.

Figura A.1 Esquema de medicao.

A caracterizacao foi realizada por meio da plataforma de medicao AMALGHMA (verFigura A.1) [Tavares 2007]. Para medir o consumo de energia de um codigo, um PCe conectado ao osciloscopio digital Agilent DS0302A. Sao utilizados dois canais do os-ciloscopio, um para a medicao da tensao e o outro como trigger na porta de Entrada/Saıdade comando de inıcio e fim da medicao. A medida da tensao e feita medindo a tensao emum resistor colocado em serie com o dispositivo. Tal processo reproduziu basicamenteas tecnicas apresentadas em [Tiwari et al. 1994, Russell and Jacome 1998]. O AMAL-GHMA captura os dados adquiridos pelo osciloscopio e faz um tratamento estatısticonestes dados para obter medidas com confianca.

Na medicao pelo AMALGHMA, o codigo a ser medido deve ser inserido no corpo deum loop. No inıcio do loop um pino de uma porta de Entrada/Saıda do microprocessador

54

CARACTERIZACAO DO MICROPROCESSADOR 55

Figura A.2 Tela do Agilent DS0302A durante o processo de medicao.

deve ser levantado e ao final do loop o mesmo pino deve ser abaixado. Adicionalmente,uma guarda (delay) entre as iteracoes tambem deve ser inserida no corpo do loop. AFigura A.2 exibe a tela do osciloscopio durante uma medicao. Assim, quando o pino daporta de Entrada/Saıda e levantado, AMALGHMA fica sabendo que o codigo comecoua executar, quando ele e abaixado, AMALGHMA fica sabendo que o codigo terminou.Desta forma, alem do consumo de energia e possıvel tambem capturar o tempo de ex-ecucao do codigo.

Para medir o consumo de energia e tempo de execucao de uma instrucao o mesmoprocedimento descrito acima e realizado. Cada instrucao e medida individualmente.Para eliminar o efeito do pipeline sobre as medidas, o corpo do loop e formado por 10000instancias da instrucao a ser medida. Ao final do processo de medicao as medidas saodivididas por 10000 para obter o custo individual de uma instrucao. A Figura A.3 exibeum exemplo de codigo de caracterizacao. E importante ressaltar que os dados relativosao tempo de execucao de cada instrucao foram validados atraves da comparacao destesvalores com os disponıveis no datasheet [Limited 2001] de especificacao do ARM7TDMI-S.

Figura A.3 Exemplo de codigo para medicao.

Documents

ALUPAS: UM SIMULADOR ESTOCASTICO¶ PARA …tg/2008-2/bcsn.pdf · para obten»c~ao do grau de Bacharel em Engenharia da ... 5.1 Assembler ... cotidiano e exemplos destes sistemas podem