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
Universidade Federal do Rio Grande do Sul
Porto Alegre - RS - Brasil
1
Introdução
Objetivos
Pesquisar formas de desenvolvimento de software embarcado
que permitam ao projetista, em alto nível, associar no
momento do desenvolvimento do software compromissos
como área de memória, desempenho, potência, etc.
Como
Através da caracterização de uma biblioteca de software
Biblioteca de SW
Composta de um conjunto de algoritmos (utilizados em
diferentes domínios de aplicação) determinar mais de uma
forma de solução para o mesmo problema
Itens avaliados: tamanho de memória (programa e dados),
desempenho e potência
2
Introdução
Algoritmos selecionados
Cálculo do Seno
Algoritmos de Ordenação
Busca em Tabela
Raiz Quadrada
Ferramentas utilizadas
Sashimi
Simulador FemtoJava (CAD – Caco Aided Design)
3
Cálculo do Seno
Estratégias
Busca em Tabela
Algortimo CORDIC
Por Tabela
Os valores do Senos são calculados previamente e armazenados
em uma tabela
static int[] tabelaSenos =
{
0, /* sin
...
0 */
23170, /* sin 45 = 0,7071 */
...
32768
}; /* tabela dos senos */
/* sin 90 = 1 */
4
Cálculo do Seno
Por Tabela
Para determinar o seno de um ângulo deve apenas realizar
uma busca na tabela
public static int senoTab(int grau) {
seno = tabelaSenos[grau];
return seno;
}
5
Cálculo do Seno
Por CORDIC
Algoritmo CORDIC (Coordinate Rotation Digital Computer)
Algoritmo iterativo simples para calcular funções
trigonométricas
public static void algoritmoCordic(int grau) {
...
while (count < 12) {
if (v >= 0) {
x = x - y0;
y = y + x0;
v = v - atansTable[indiceAtans]; indiceAtans++;
} else {
x = x + y0;
y = y - x0;
v = v + atansTable[indiceAtans]; indiceAtans++;
}
count++;
x0 = x;
x0 = x0 >> count;
y0 = y;
y0 = y0 >> count;
}
...
}
6
Cálculo do Seno
Resultados
Prg Mem Data Mem
(bytes)
(Bytes)
Seno Cordic
206
184
Seno Tab (1)
88
220
Seno Tab (0,5)
89
400
Seno Tab (0,1)
89
1840
App
App
Seno Cordic
Seno Tab
Power
ROM
178.480
8.970
Power
RAM
121.440
9.200

Instr
28
8
8
8
Perfor.
(Cycles)
2446
136
136
136
Power
CPU
5.535.442
304.285
Power
(CGs)
5.835.362
322.455
322.455
322.455
Power
TOTAL
5.835.362
322.455
7
Cálculo do Seno
Conclusões
Cálculo por Tabela é excelente para pequenas resoluções
(desempenho, potência e área de memória)
Problema: com a necessidade de aumento da resolução
ocorre o aumento da tabela (maior necessidade de
memória)
Cálculo pelo CORDIC: possui desempenho bem pior que o
cálculo por tabela, porém com o aumento da resolução
os parâmetros (desempenho, potência e área de
memória) não se alteram
Bons para exploração do espaço de projeto
8
Pesquisa em Tabela
Estratégias
Pesquisa seqüencial em tabela não ordenada
Método simples e intuitivo
Pesquisa seqüencial em tabela ordenada
Método simples e intuitivo
Pesquisa Binária
Mé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
Hashing
Método de cálculo de endereço
9
Pesquisa em Tabela
Pesquisa Seqüencial em tabela não ordenada
Realiza uma busca “burra”, porém o processo de inserção é
facilitado
Busca é realizada através de um laço (for):
public static int busca(int arg) {
int i, n, e;
n = tamTAB;
e = 0;
for (i=0; i<=n-1; i++) {
if (tabela[i] == arg) {
e = i;
}
}
return e;
}
10
Pesquisa em Tabela
Pesquisa Seqüencial em tabela não ordenada
Para um novo elemento deve-se inclui-lo no final da tabela
public static int insere(int arg) {
int dev;
if (ultimoElemento < tamTAB) {
// insere
tabela[ultimoElemento] = arg;
ultimoElemento++;
dev = 0;
}
else {
// tabela cheia
dev = 1;
}
return dev;
}
11
Pesquisa em Tabela
Pesquisa Seqüencial em tabela ordenada
Busca é realizada através de um laço (while):
public static int busca(int arg) {
int i, n, e;
n = tamTAB-1;
e = 0;
i = 0;
while ((tabela[i] < arg) && (i < n)) {
i++;
}
if (tabela[i] == arg) {
e = i;
}
return e;
}
12
Pesquisa em Tabela
Pesquisa Seqüencial em tabela ordenada
Um novo elemento deve ser inserido na posição correta da
tabela
public static int insere(int arg) {
int dev, n, i, temp, temp2;
n = tamTAB-1;
i = 0;
if (ultimoElemento < tamTAB) {
while ((tabela[i] < arg) && (i < n)) {
i++;
}
temp2 = arg;
while (i < n) {
temp = tabela[i];
tabela[i] = temp2;
temp2 = temp;
i++;
}
tabela[i] = temp2;
ultimoElemento++;
}
...
13
Pesquisa em Tabela
Pesquisa Binária
Busca é relativamente simples e rápida
public static int busca(int arg) {
int i, n, e, inf, sup, med;
...
while ((inf <= sup) && (e==0))
{
med = (inf + sup) >> 1; // (inf + sup) DIV 2
if (arg == tabela[med]) {
e = med;
} else {
if (arg > tabela[med]) {
inf = med + 1;
}
else {
sup = med - 1;
}
}
}
return e;
}
14
Pesquisa em Tabela
Pesquisa Binária
A inserção é mais lenta pois deve-se inserir o elemento na
posição correta e depois reordenar os demais elementos
public static int insere(int arg) {
int i, n, e, inf, sup, med;
...
if (ultimoElemento < tamTAB) {
while ((inf <= sup) && (e==0)) {
med = (inf + sup) >> 1; // (inf + sup) DIV 2
if (arg > tabela[med]) {
inf = med + 1;
}
else {
sup = med - 1;
}
}
...
while (i < tamTAB-1) {
temp = tabela[i];
tabela[i] = temp2;
temp2 = temp;
i++;
}
...
15
Pesquisa em Tabela
Hashing
Função de cálculo de endereço (simples):
f(C)=(C mod N)+1, onde C é a chave e N é o número de
entradas da tabela
Problema: Colisões
Sem o tratamento de colisões o método é excelente !
Tratamento de Colisões: uso de endereçamento aberto
com busca linear
16
Pesquisa em Tabela
Hashing
Busca com tratamento de colisões: maior complexidade no
código e aumento na memória de dados (tabelas auxiliares:
ocupado e usado)
public static int busca(int arg) {
...
do {
if (tabUsado[endl] == 1) {
if ((tabOcupado[endl] == 1) && (tabela[endl] == arg)) {
e = endl;
} else {
if (endl == n) {
endl = 1;
} else {
endl++;
}
}
...
17
Pesquisa em Tabela
Hashing
Inserção com tratamento de colisões: também maior
complexidade no código e maior memória de dados
public static int insere(int arg) {
...
do {
if (tabUsado[endl] == 1) {
if (tabOcupado[endl] == 1) {
if (tabela[endl] == arg) {
e = endl;
} else {
endl++;
}
} else {
if (marca == 0) {
marca = endl;
endl++;
}
...
18
Pesquisa em Tabela
Resultados (32 entradas)
App
Prg. Mem. (bytes)
 Instructions
Data Mem.
Search
(bytes)
Insert
Perfom.
Search
(cycles)
Insert
Power
Search
(CGs)
Insert
Seq. 1
Seq. 2
Binary
140
201
302
24
26
28
171
168
114
108
240
184
1.121
1.128
602
200
2.629
2.430
2.685.063 2.702.674 1.100.436
470.692 6.249.144 5.744.422
Hashing
278
29
248
254
437
487
1.044.637
1.161.693
OBS: Valores médios de desempenho, área e potência.
19
Pesquisa em Tabela
Resultados para Hashing (32 entradas)
trabalhando com Strings
Utilizando o código ASCII com compressão de chave
alfanumérica agrupando de 2 em 2 bytes
Ex: BRASIL
BR
0100001001010010
AS
0100000101010011
XOR
IL
0100100101001100
0100001001010010 = 1697810
f(C)=(C mod N)+1 = (16978 mod 32)+1 = 14
20
Pesquisa em Tabela
Resultados para Hashing (32 entradas)
trabalhando com Strings
App
Prg. Mem. (bytes)
 Instructions
Data Mem.
Search
(bytes)
Insert
Perfom.
Search
(cycles)
Insert
Power
Search
(CGs)
Insert
Hashing
278
29
248
254
437
487
1.044.637
1.161.693
Hashing
c/ String
371
37
272
272
607
657
1.451.017
1.570.541
21
Pesquisa em Tabela
Resultados (128 entradas)
App
Prg. Mem. (bytes)
 Instructions
Data Mem.
Search
(bytes)
Insert
Perfom.
Search
(cycles)
Insert
Power
Search
(CGs)
Insert
Seq. 1
Seq. 2
Binary
140
201
302
24
26
28
555
552
306
300
816
548
3.905
3.912
770
200
9.937
7.657
9.397.287 9.720.722 1.882.485
470.692 23.716.169 18.151.875
Hashing
278
29
855
862
437
487
992.903
1.162.748
OBS: Valores médios de desempenho, área e potência.
22
Algoritmos de Ordenação
Estratégias
Bubble Sort
Insert Sort
Select Sort
Quick Sort
Resultados Esperados
Associados com a complexidade de cada algoritmo
23
Algoritmos de Ordenação
Bubble Sort
public static int[] sort(int[] estrut, int maxnos) {
int i,j;
int temp;
for (i=0; i<maxnos-1; i++) {
for (j=maxnos-1; j>i; j--) {
if (estrut[j]<estrut[j-1]) {
temp=estrut[j];
estrut[j]=estrut[j-1];
estrut[j-1]=temp;
}
}
}
return estrut;
}
24
Algoritmos de Ordenação
Insert Sort
public static int[] sort(int[] estrut, int maxnos) {
int i,j;
int temp;
for (i=1; i<maxnos;i++) {
j=i;
while (estrut[j]<estrut[j-1] && j!=1) {
temp=estrut[j];
estrut[j]=estrut[j-1];
estrut[j-1]=temp;
j--;
}
}
return estrut;
}
25
Algoritmos de Ordenação
Select Sort
public static int[] sort(int[] estrut, int maxnos) {
int i,j;
int temp, menor;
for (i=1;i<maxnos;i++) {
menor=i-1;
j=i;
while (j<maxnos) {
if (estrut[menor]>estrut[j]) {
menor=j;
}
j++;
}
temp=estrut[i-1];
estrut[i-1]=estrut[menor];
estrut[menor]=temp;
}
return estrut;
}
26
Algoritmos de Ordenação
Quick Sort
public static int[] sort(int l, int r) {
...
i = l;
j = r;
temp = (l+r) >> 1;
// (l+r) DIV 2
x = estrut[temp];
do {
while (estrut[i] < x) { i++; }
while (x < estrut[j]) { j--;}
if (i <= j) {
y = estrut[i];
estrut[i] = estrut[j];
estrut[j] = y;
i++;
j--;
}
} while (i <= j);
if (l < j) { sort(l, j); }
if (i < r) { sort(i, r); }
return estrut;
}
27
Algoritmos de Ordenação
Resultados (10 elementos)
App
Sort Bubble
Sort Insert
Sort Select
Sort Quick
Prg Mem Data Mem
(bytes)
(Bytes)
132
278
129
98
138
98
173
140

Instr
20
20
22
23
Perfor.
(Cycles)
6774
4093
5335
3940
Power
(CGs)
16.348.510
9.754.005
12.929.068
9.485.919
28
Algoritmos de Ordenação
Resultados (100 elementos)
App
Sort Bubble
Sort Insert
Sort Select
Sort Quick
Prg Mem Data Mem
(bytes)
(Bytes)
132
20.434
129
638
138
638
173
336

Instr
20
20
22
23
Perfor.
Power
(Cycles)
(CGs)
892.347 2.096.575.205
856.188 2.044.626.628
408.675 996.468.801
72.186 173.527.751
29
Raiz Quadrada
Utiliza dois Métodos propostos por
Ramamoorthy
Dois métodos muito similares
O desempenho está relacionado a rapidez da
convergência das funções
Resultados:
App
Square 1
Square 2
Prg Mem Data Mem
(bytes)
(Bytes)
100
82
121
82

Instr
22
24
Perfor.
(Cycles)
5335
5335
Power
(CGs)
7.001.414
7.001.414
30
Conclusões
Cálculo do Seno
Permite uma boa exploração do espaço de projeto
Pesquisa em Tabela
O melhor algoritmos dependerá muito da aplicação, mas
também pode-se explorar o espaço de projeto
Algoritmos de Ordenação
Não permitem explorar o espaço de projeto (contraexemplo)
Raiz Quadrada
Dados muitos incipientes
31
Trabalhos Futuros
Expandir a biblioteca com outros algoritmos
Algoritmos aritméticos
Algortimos maiores (DCT, etc...)
Avaliar o impacto dos algoritmos em
problemas maiores
Algortimos de Huffman
MP3 Player
etc ...