Upload
harper-mckay
View
22
Download
2
Embed Size (px)
DESCRIPTION
Caracterização de uma Biblioteca de Software para Sistemas Embarcados. Júlio Carlos Balzano de Mattos [email protected]. Disciplina de Sistemas Embarcados Profs. Flavio Wagner e Luigi Carro. Programa de Pós-Graduação em Computação Instituto de Informática - PowerPoint PPT Presentation
Citation preview
Caracterização de uma Caracterização de uma Biblioteca de Software para Biblioteca de Software para
Sistemas EmbarcadosSistemas Embarcados
Programa de Pós-Graduação em ComputaçãoPrograma de Pós-Graduação em ComputaçãoInstituto de InformáticaInstituto de Informática
Universidade Federal do Rio Grande do SulUniversidade Federal do Rio Grande do SulPorto Alegre - RS - BrasilPorto Alegre - RS - Brasil
Júlio Carlos Balzano de MattosJúlio Carlos Balzano de [email protected]@inf.ufrgs.br
Disciplina de Sistemas EmbarcadosDisciplina de Sistemas EmbarcadosProfs. Flavio Wagner e Luigi CarroProfs. Flavio Wagner e Luigi Carro
22 IntroduçãoIntrodução
Objetivos Objetivos Pesquisar formas de desenvolvimento de software embarcado Pesquisar formas de desenvolvimento de software embarcado
que permitam ao projetista, em alto nível, associar no que permitam ao projetista, em alto nível, associar no momento do desenvolvimento do software compromissos momento do desenvolvimento do software compromissos como área de memória, desempenho, potência, etc. como área de memória, desempenho, potência, etc.
ComoComoAtravés da caracterização de uma biblioteca de softwareAtravés da caracterização de uma biblioteca de software
Biblioteca de SWBiblioteca de SWComposta de um conjunto de algoritmos (utilizados em Composta de um conjunto de algoritmos (utilizados em
diferentes domínios de aplicação) determinar mais de uma diferentes domínios de aplicação) determinar mais de uma forma de solução para o mesmo problemaforma de solução para o mesmo problema
Itens avaliados: tamanho de memória (programa e dados), Itens avaliados: tamanho de memória (programa e dados), desempenho e potênciadesempenho e potência
33 IntroduçãoIntrodução
Algoritmos selecionadosAlgoritmos selecionadosCálculo do SenoCálculo do Seno
Algoritmos de OrdenaçãoAlgoritmos de Ordenação
Busca em TabelaBusca em Tabela
Raiz QuadradaRaiz Quadrada
Ferramentas utilizadasFerramentas utilizadasSashimiSashimi
Simulador FemtoJava (CAD – Caco Aided Design)Simulador FemtoJava (CAD – Caco Aided Design)
44 Cálculo do SenoCálculo do Seno
EstratégiasEstratégiasBusca em TabelaBusca em Tabela
Algortimo CORDICAlgortimo CORDIC
Por TabelaPor TabelaOs valores do Senos são calculados previamente e armazenados Os valores do Senos são calculados previamente e armazenados
em uma tabelaem uma tabela
static int[] tabelaSenos = static int[] tabelaSenos =
{ 0, /* sin 0 */ { 0, /* sin 0 */
......
23170, /* sin 45 = 0,7071 */23170, /* sin 45 = 0,7071 */
......
32768 /* sin 90 = 1 */32768 /* sin 90 = 1 */
}; /* tabela dos senos */}; /* tabela dos senos */
55 Cálculo do SenoCálculo do Seno
Por TabelaPor TabelaPara determinar o seno de um ângulo deve apenas realizar Para determinar o seno de um ângulo deve apenas realizar
uma busca na tabelauma busca na tabela
public static int senoTab(int grau) {public static int senoTab(int grau) {
seno = tabelaSenos[grau];seno = tabelaSenos[grau];
return seno;return seno;
}}
66 Cálculo do SenoCálculo do Seno
Por CORDICPor CORDICAlgoritmo CORDIC (Coordinate Rotation Digital Computer)Algoritmo CORDIC (Coordinate Rotation Digital Computer)Algoritmo iterativo simples para calcular funções trigonométricasAlgoritmo iterativo simples para calcular funções trigonométricas public static void algoritmoCordic(int grau) {public static void algoritmoCordic(int grau) {
......while (count < 12) {while (count < 12) { if (v >= 0) {if (v >= 0) {
x = x - y0;x = x - y0;y = y + x0;y = y + x0;v = v - atansTable[indiceAtans]; indiceAtans++;v = v - atansTable[indiceAtans]; indiceAtans++;
} else {} else {x = x + y0;x = x + y0;y = y - x0;y = y - x0;v = v + atansTable[indiceAtans]; indiceAtans++;v = v + atansTable[indiceAtans]; indiceAtans++;
}} count++;count++; x0 = x;x0 = x; x0 = x0 >> count;x0 = x0 >> count;
y0 = y;y0 = y; y0 = y0 >> count;y0 = y0 >> count;
}} ......
}}
77 Cálculo do SenoCálculo do Seno
ResultadosResultados
App
Seno CordicSeno Tab (1)
Seno Tab (0,5)Seno Tab (0,1)
Prg Mem(bytes)
206888989
Data Mem(Bytes)
184220400
1840
Instr
28888
Perfor.(Cycles)
2446136136136
App
Seno CordicSeno Tab
PowerROM
178.4808.970
PowerRAM
121.4409.200
PowerCPU
5.535.442304.285
Power(CGs)
5.835.362322.455322.455322.455
PowerTOTAL
5.835.362322.455
88 Cálculo do SenoCálculo do Seno
ConclusõesConclusõesCálculo por Tabela é excelente para pequenas resoluções Cálculo por Tabela é excelente para pequenas resoluções
(desempenho, potência e área de memória)(desempenho, potência e área de memória)
Problema: com a necessidade de aumento da resolução Problema: com a necessidade de aumento da resolução ocorre o aumento da tabela (maior necessidade de ocorre o aumento da tabela (maior necessidade de memória)memória)
Cálculo pelo CORDIC: possui desempenho bem pior que o Cálculo pelo CORDIC: possui desempenho bem pior que o cálculo por tabela, porém com o aumento da resolução cálculo por tabela, porém com o aumento da resolução os parâmetros (desempenho, potência e área de os parâmetros (desempenho, potência e área de memória) não se alterammemória) não se alteram
Bons para exploração do espaço de projetoBons para exploração do espaço de projeto
99 Pesquisa em TabelaPesquisa em Tabela
EstratégiasEstratégias
Pesquisa seqüencial em tabela não ordenadaPesquisa seqüencial em tabela não ordenadaMétodo simples e intuitivo
Pesquisa seqüencial em tabela ordenadaPesquisa seqüencial em tabela ordenadaMétodo simples e intuitivo
Pesquisa BináriaPesquisa BináriaMétodo aplica a tabelas ordenadas que consiste na comparação
do argumento de pesquisa com a chave de entrada localizada no endereço médio da tabela
HashingHashingMétodo de cálculo de endereço
1010Pesquisa em TabelaPesquisa em Tabela
Pesquisa Seqüencial em tabela não ordenadaPesquisa Seqüencial em tabela não ordenadaRealiza uma busca “burra”, porém o processo de inserção é Realiza uma busca “burra”, porém o processo de inserção é
facilitadofacilitado
Busca é realizada através de um laço (for):Busca é realizada através de um laço (for):
public static int busca(int arg) {public static int busca(int arg) { int i, n, e;int i, n, e;
n = tamTAB;n = tamTAB;e = 0;e = 0;
for (i=0; i<=n-1; i++) {for (i=0; i<=n-1; i++) { if (tabela[i] == arg) { if (tabela[i] == arg) { e = i;e = i; }} }}
return e;return e;}}
1111 Pesquisa em TabelaPesquisa em Tabela
Pesquisa Seqüencial em tabela não ordenadaPesquisa Seqüencial em tabela não ordenadaPara um novo elemento deve-se inclui-lo no final da tabelaPara um novo elemento deve-se inclui-lo no final da tabela
public static int insere(int arg) {public static int insere(int arg) {
int dev;int dev;
if (ultimoElemento < tamTAB) { if (ultimoElemento < tamTAB) {
// insere// insere
tabela[ultimoElemento] = arg;tabela[ultimoElemento] = arg;
ultimoElemento++;ultimoElemento++;
dev = 0;dev = 0;
}}
else {else {
// tabela cheia// tabela cheia
dev = 1;dev = 1;
}}
return dev;return dev;
}}
1212Pesquisa em TabelaPesquisa em Tabela
Pesquisa Seqüencial em tabela ordenadaPesquisa Seqüencial em tabela ordenada
Busca é realizada através de um laço (while):Busca é realizada através de um laço (while):
public static int busca(int arg) {public static int busca(int arg) {
int i, n, e;int i, n, e;
n = tamTAB-1;n = tamTAB-1;e = 0;e = 0;i = 0;i = 0;
while ((tabela[i] < arg) && (i < n)) {while ((tabela[i] < arg) && (i < n)) { i++; i++; }}
if (tabela[i] == arg) { if (tabela[i] == arg) { e = i;e = i;}}
return e;return e;}}
1313Pesquisa em TabelaPesquisa em Tabela
Pesquisa Seqüencial em tabela ordenadaPesquisa Seqüencial em tabela ordenadaUm novo elemento deve ser inserido na posição correta da tabela Um novo elemento deve ser inserido na posição correta da tabela public static int insere(int arg) {public static int insere(int arg) {
int dev, n, i, temp, temp2;int dev, n, i, temp, temp2;n = tamTAB-1;n = tamTAB-1;i = 0;i = 0;
if (ultimoElemento < tamTAB) { if (ultimoElemento < tamTAB) { while ((tabela[i] < arg) && (i < n)) {while ((tabela[i] < arg) && (i < n)) { i++; i++; }} temp2 = arg;temp2 = arg; while (i < n) {while (i < n) { temp = tabela[i];temp = tabela[i]; tabela[i] = temp2;tabela[i] = temp2; temp2 = temp;temp2 = temp; i++;i++; }} tabela[i] = temp2;tabela[i] = temp2; ultimoElemento++;ultimoElemento++;
}}......
1414Pesquisa em TabelaPesquisa em Tabela
Pesquisa BináriaPesquisa BináriaBusca é relativamente simples e rápidaBusca é relativamente simples e rápida
public static int busca(int arg) {public static int busca(int arg) {
int i, n, e, inf, sup, med;int i, n, e, inf, sup, med;......
while ((inf <= sup) && (e==0)) while ((inf <= sup) && (e==0)) { {
med = (inf + sup) >> 1; // (inf + sup) DIV 2med = (inf + sup) >> 1; // (inf + sup) DIV 2if (arg == tabela[med]) { if (arg == tabela[med]) { e = med;e = med;} else {} else {if (arg > tabela[med]) {if (arg > tabela[med]) {inf = med + 1;inf = med + 1;}}else {else {sup = med - 1;sup = med - 1;}}}}
}}return e;return e;
}}
1515Pesquisa em TabelaPesquisa em Tabela
Pesquisa BináriaPesquisa BináriaA inserção é mais lenta pois deve-se inserir o elemento na posição correta e A inserção é mais lenta pois deve-se inserir o elemento na posição correta e
depois reordenar os demais elementos depois reordenar os demais elementos public static int insere(int arg) {public static int insere(int arg) {
int i, n, e, inf, sup, med;int i, n, e, inf, sup, med;......if (ultimoElemento < tamTAB) { if (ultimoElemento < tamTAB) { while ((inf <= sup) && (e==0)) { while ((inf <= sup) && (e==0)) { med = (inf + sup) >> 1; // (inf + sup) DIV 2med = (inf + sup) >> 1; // (inf + sup) DIV 2if (arg > tabela[med]) {if (arg > tabela[med]) {inf = med + 1;inf = med + 1;}}else {else {sup = med - 1;sup = med - 1;}}}}......while (i < tamTAB-1) {while (i < tamTAB-1) {temp = tabela[i];temp = tabela[i];tabela[i] = temp2;tabela[i] = temp2;temp2 = temp;temp2 = temp;i++;i++;}}......
1616Pesquisa em TabelaPesquisa em Tabela
HashingHashingFunção de cálculo de endereço (simples):Função de cálculo de endereço (simples):
f(C)=(C mod N)+1, f(C)=(C mod N)+1, ondeonde C C é a chaveé a chave ee N N é o número de é o número de entradas da tabelaentradas da tabela
Problema: ColisõesProblema: Colisões
Sem o tratamento de colisões o método é excelente !Sem o tratamento de colisões o método é excelente !
Tratamento de Colisões: uso de endereçamento aberto Tratamento de Colisões: uso de endereçamento aberto com busca linearcom busca linear
1717Pesquisa em TabelaPesquisa em Tabela
HashingHashingBusca com tratamento de colisões: maior complexidade no Busca com tratamento de colisões: maior complexidade no
código e aumento na memória de dados (tabelas auxiliares: código e aumento na memória de dados (tabelas auxiliares: ocupado e usado)ocupado e usado)
public static int busca(int arg) {public static int busca(int arg) {
......
do {do { if (tabUsado[endl] == 1) {if (tabUsado[endl] == 1) {
if ((tabOcupado[endl] == 1) && (tabela[endl] == arg)) if ((tabOcupado[endl] == 1) && (tabela[endl] == arg)) {{
e = endl;e = endl;} else {} else { if (endl == n) {if (endl == n) { endl = 1;endl = 1; } else {} else { endl++;endl++;}}
}} ......
1818Pesquisa em TabelaPesquisa em Tabela
HashingHashingInserção com tratamento de colisões: também maior Inserção com tratamento de colisões: também maior
complexidade no código e maior memória de dadoscomplexidade no código e maior memória de dados
public static int insere(int arg) {public static int insere(int arg) { ......
do {do {if (tabUsado[endl] == 1) {if (tabUsado[endl] == 1) { if (tabOcupado[endl] == 1) {if (tabOcupado[endl] == 1) { if (tabela[endl] == arg) {if (tabela[endl] == arg) {
e = endl;e = endl; } else {} else {
endl++;endl++; }} } else {} else { if (marca == 0) {if (marca == 0) {
marca = endl;marca = endl;endl++;endl++;
} } ......
1919Pesquisa em TabelaPesquisa em Tabela
Resultados (32 entradas)Resultados (32 entradas)
OBS: Valores médios de desempenho, área e potência.OBS: Valores médios de desempenho, área e potência.
App
Prg. Mem. (bytes)
Data Mem.(bytes)
Seq. 1
140
171108
1.121
Seq. 2
201
168240
1.128
Binary
302
114184602
Hashing
278
248254437
2002.685.063
2.6292.702.674
2.4301.100.436
4871.044.637
470.692 6.249.144 5.744.422 1.161.693
SearchInsert
Perfom.(cycles)
SearchInsert
Power(CGs)
SearchInsert
Instructions 24 26 28 29
2020Pesquisa em TabelaPesquisa em Tabela
Resultados para Hashing (32 entradas) Resultados para Hashing (32 entradas) trabalhando com Stringstrabalhando com StringsUtilizando o código ASCII com compressão de chave Utilizando o código ASCII com compressão de chave
alfanumérica agrupando de 2 em 2 bytesalfanumérica agrupando de 2 em 2 bytes
Ex: BRASILEx: BRASIL
BRBR 01000010010100100100001001010010
ASAS 01000001010100110100000101010011 XORXOR
ILIL 01001001010011000100100101001100
0100001001010010 = 169780100001001010010 = 169781010
f(C)=(C mod N)+1f(C)=(C mod N)+1 = (16978 mod 32)+1 = 14 = (16978 mod 32)+1 = 14
2121Pesquisa em TabelaPesquisa em Tabela
App
Prg. Mem. (bytes)
Data Mem.(bytes)
Hashing
278
248254437487
1.044.637 1.161.693
SearchInsert
Perfom.(cycles)
SearchInsert
Power(CGs)
SearchInsert
Instructions 29
Hashingc/ String
371
272272607657
1.451.017 1.570.541
37
Resultados para Hashing (32 entradas) Resultados para Hashing (32 entradas) trabalhando com Stringstrabalhando com Strings
2222Pesquisa em TabelaPesquisa em Tabela
Resultados (128 entradas)Resultados (128 entradas)
OBS: Valores médios de desempenho, área e potência.OBS: Valores médios de desempenho, área e potência.
App
Prg. Mem. (bytes)
Data Mem.(bytes)
Seq. 1
140
555300
3.905
Seq. 2
201
552816
3.912
Binary
302
306548770
Hashing
278
855862437
2009.397.287
9.937 9.720.722
7.657 1.882.485
487992.903
470.692 23.716.169 18.151.875 1.162.748
SearchInsert
Perfom.(cycles)
SearchInsert
Power(CGs)
SearchInsert
Instructions 24 26 28 29
2323Algoritmos de OrdenaçãoAlgoritmos de Ordenação
EstratégiasEstratégiasBubble SortBubble Sort
Insert SortInsert Sort
Select SortSelect Sort
Quick SortQuick Sort
Resultados EsperadosResultados EsperadosAssociados com a complexidade de cada algoritmoAssociados com a complexidade de cada algoritmo
2424Algoritmos de OrdenaçãoAlgoritmos de Ordenação
Bubble SortBubble Sort
public static int[] sort(int[] estrut, int maxnos) {public static int[] sort(int[] estrut, int maxnos) {
int i,j;int i,j;int temp;int temp;
for (i=0; i<maxnos-1; i++) {for (i=0; i<maxnos-1; i++) { for (j=maxnos-1; j>i; j--) { for (j=maxnos-1; j>i; j--) { if (estrut[j]<estrut[j-1]) { if (estrut[j]<estrut[j-1]) { temp=estrut[j];temp=estrut[j]; estrut[j]=estrut[j-1];estrut[j]=estrut[j-1]; estrut[j-1]=temp;estrut[j-1]=temp; }} }} }}
return estrut;return estrut;}}
2525Algoritmos de OrdenaçãoAlgoritmos de Ordenação
Insert SortInsert Sort public static int[] sort(int[] estrut, int maxnos) {public static int[] sort(int[] estrut, int maxnos) {
int i,j;int i,j;
int temp;int temp;
for (i=1; i<maxnos;i++) {for (i=1; i<maxnos;i++) {
j=i;j=i;
while (estrut[j]<estrut[j-1] && j!=1) {while (estrut[j]<estrut[j-1] && j!=1) {
temp=estrut[j];temp=estrut[j];
estrut[j]=estrut[j-1];estrut[j]=estrut[j-1];
estrut[j-1]=temp;estrut[j-1]=temp;
jj----;;
}}
}}
return estrut;return estrut;
}}
2626Algoritmos de OrdenaçãoAlgoritmos de Ordenação
Select SortSelect Sort public static int[] sort(int[] estrut, int maxnos) {public static int[] sort(int[] estrut, int maxnos) {
int i,j;int i,j;int temp, menor;int temp, menor;
for (i=1;i<maxnos;i++) {for (i=1;i<maxnos;i++) { menor=i-1;menor=i-1; j=i;j=i; while (j<maxnos) {while (j<maxnos) { if (estrut[menor]>estrut[j]) { if (estrut[menor]>estrut[j]) { menor=j;menor=j;
}} jj++++;; }} temp=estrut[i-1];temp=estrut[i-1]; estrut[i-1]=estrut[menor];estrut[i-1]=estrut[menor]; estrut[menor]=temp;estrut[menor]=temp;
}}return estrut;return estrut;
}}
2727Algoritmos de OrdenaçãoAlgoritmos de Ordenação
Quick SortQuick Sort public static int[] sort(int l, int r) {public static int[] sort(int l, int r) {
......i = l;i = l;j = r;j = r;temp = (l+r) >> 1; // (l+r) DIV 2temp = (l+r) >> 1; // (l+r) DIV 2x = estrut[temp];x = estrut[temp];
do {do { while (estrut[i] < x) { while (estrut[i] < x) { i++i++; }; } while (x < estrut[j]) { jwhile (x < estrut[j]) { j----;};} if (i <= j) { if (i <= j) { y = estrut[i];y = estrut[i];
estrut[i] = estrut[j];estrut[i] = estrut[j];estrut[j] = y;estrut[j] = y;
i++i++;;j--j--;;
}} } while (i <= j);} while (i <= j); if (l < j) { sort(l, j); }if (l < j) { sort(l, j); } if (i < r) { sort(i, r); }if (i < r) { sort(i, r); }
return estrut;return estrut;}}
2828Algoritmos de OrdenaçãoAlgoritmos de Ordenação
Resultados (10 elementos)Resultados (10 elementos)
App
Sort BubbleSort InsertSort SelectSort Quick
Prg Mem(bytes)
132129138173
Data Mem(Bytes)
2789898
140
Instr
20202223
Perfor.(Cycles)
6774409353353940
Power(CGs)
16.348.5109.754.005
12.929.0689.485.919
2929Algoritmos de OrdenaçãoAlgoritmos de Ordenação
Resultados (100 elementos)Resultados (100 elementos)
App
Sort BubbleSort InsertSort SelectSort Quick
Prg Mem(bytes)
132129138173
Data Mem(Bytes)20.434
638638336
Instr
20202223
Perfor.(Cycles)892.347856.188408.67572.186
Power(CGs)
2.096.575.2052.044.626.628996.468.801173.527.751
3030Raiz QuadradaRaiz Quadrada
Utiliza dois Métodos propostos por Utiliza dois Métodos propostos por RamamoorthyRamamoorthyDois métodos muito similaresDois métodos muito similares
O desempenho está relacionado a rapidez da O desempenho está relacionado a rapidez da convergência das funçõesconvergência das funções
Resultados:Resultados:
App
Square 1Square 2
Prg Mem(bytes)
100121
Data Mem(Bytes)
8282
Instr
2224
Perfor.(Cycles)
53355335
Power(CGs)
7.001.4147.001.414
3131ConclusõesConclusões
Cálculo do SenoCálculo do SenoPermite uma boa exploração do espaço de projetoPermite uma boa exploração do espaço de projeto
Pesquisa em TabelaPesquisa em TabelaO melhor algoritmos dependerá muito da aplicação, mas O melhor algoritmos dependerá muito da aplicação, mas
também pode-se explorar o espaço de projetotambém pode-se explorar o espaço de projeto
Algoritmos de OrdenaçãoAlgoritmos de OrdenaçãoNão permitem explorar o espaço de projeto (contra-Não permitem explorar o espaço de projeto (contra-
exemplo)exemplo)
Raiz QuadradaRaiz QuadradaDados muitos incipientesDados muitos incipientes
3232Trabalhos FuturosTrabalhos Futuros
Expandir a biblioteca com outros algoritmosExpandir a biblioteca com outros algoritmosAlgoritmos aritméticosAlgoritmos aritméticos
Algortimos maiores (DCT, etc...)Algortimos maiores (DCT, etc...)
Avaliar o impacto dos algoritmos em Avaliar o impacto dos algoritmos em problemas maioresproblemas maioresAlgortimos de HuffmanAlgortimos de Huffman
MP3 PlayerMP3 Player
etc ...etc ...