Exemplo de um projeto de
sistema completo
Aula - 4
Introdução
•
O projeto de sistemas dedicados é baseado no uso de vários tipos de
técnicas de desenvolvimento:
–
–
–
–
–
–
–
•
Seleção de representação de dados
Geração ou seleção de algoritmos
Seleção de plataforma de hardware
Particionamento de Hardware-software
Geração de programa
Síntese do novo hardware
Cossimulação, coemulação e prototipação
Essas atividades tem uma relação íntima com os algoritmos e circuitos
aritméticos, especialmente no caso de sistemas incluindo uma grande
quantidade de processamento de dados (por exemplo, criptografia e
decriptografia, processamento de imagens, assinatura digital e biometria).
Representação de dados
– Quando se usa um computador de uso geral, o projetista tem
poucas chances de escolha quanto a representação interna de
dados.
• Devemos nos conformar com os tipos de dados fixos e predefinidos
tais como integer, floating-point, double precision, e character.
– Ao contrário, se um sistema específico está em desenvolvimento,
o projetista pode escolher para cada dado, o tipo mais conveniente
de representação.
• Não é necessário escolher sobre um sistema de numeração padrão
de ponto fixo ou ponto-flutuante. Formatos específicos e não-padrões
podem ser usados.
Algoritmos
• Cada operação de processamento de dados complexos deve ser
decomposto em operações simples:
– primitivas computacionais – executáveis ou pelo processador
principal ou por algum coprocessador específico.
• A forma com que as primitivas computacionais são usadas para
realizar a operação complexa representa o algoritmo.
• Obviamente, o conhecimento sobre os algoritmos é de fundamental
importância para o desenvolvimento de procedimentos aritméticos e
circuitos.
Plataforma de Hardware
• A seleção de uma plataforma de hardware é baseada no seguinte:
– obtenção de um comportamento desejado com menor custo,
preenchendo algumas restrições:
• conceito de menor custo depende de cada caso particular, cobrindo: custo
de produção unitária, o custo de engenharia não recorrente (NRE), e o
custo para introdução do produto no mercado.
• alguns exemplos de restrições técnicas adicionais são o tamanho do
sistema, o consumo de energia, confiabilidade e possibilidade de
manutenção.
•
•
Para sistemas de pequena capacidade de processamento de dados,
podem ser usados:
– microcontroladores e microprocessadores de baixa capacidade.
Se a computação é mais intensa:
– microprocessadores potentes, ou mesmo processadores de sinais
digitais (DSPs) devem ser considerados.
• A solução de microprocessadores e DSPs é muito flexível uma vez que o
trabalho de desenvolvimento se restringe basicamente em gerar programas.
•
Para obter desempenhos maiores, é necessário o desenvolvimento de
circuitos específicos:
– FPGAs (pequena quantidade), e
– ASICs (grande quantidade).
Particionamento Hardware-Software
• O particionamento hardware-software consiste em decidir:
– quais operações serão executados pela CPU (software) e quais, pelos
coprocessadores específicos (hardware).
• A seleção da plataforma e o particionamento hardware-software são
decisões fortemente relacionadas.
• Para sistemas requerendo pequena capacidade de processamento,
o sistema completo pode ser implementado em software.
• Se um desempenho alto é necessário:
– as operações não-críticas, bem como o controle da sequência de
operações são executadas na CPU, enquanto que
– as operações críticas são implementadas em coprocessadores
específicos.
Geração de software e Síntese de Hardware
• As operações relativas ao software devem ser programadas.
• Todas as tarefas destinadas ao hardware devem ser traduzidas em
descrição de circuitos.
Exemplo: sistema digital de ‘marca ou assinatura’ (signature)
•
O sistema exemplo tem 3 entradas:
– Character: um vetor de 8 bits,
– New_caracter: um sinal usado para sincronizar a entrada dos caracteres
sucessivos,
– Sign: um sinal de controle para computar uma signature digital
e 2 saídas:
– done: variável status indicando que a computação foi completada e
– Signature: um vetor de 32 bits.
Funcionamento do Sistema
•
•
•
Uma sequência de n caracteres (mensagem), sincronizada pelo sinal
new_character, é introduzida.
Quando o sinal de controle sign sobe, o ‘flag’ done cai e a signature da
mensagem é computada.
O ‘flag’ done sobe quando a signature s é disponível.
Funções: hash e codificação
• Para calcular a signature duas funções são definidas:
– Uma função hash associando um vetor resumo de 32 bits (summary) a
todas as mensagens, independente do comprimento
– Uma função de codificação computando a signature correspondente ao
summary.
Algoritmo: Função hash
summary := 0;
while not(end_of_message) loop
get(character);
a:= (summary (7 downto 0) + character) mod 256;
summary (23 downto 16):= summary (31 downto 24);
summary (15 downto 8):= summary (23 downto 16);
summary (7 downto 0):= summary (15 downto 8);
summary (31 downto 24):= a;
end loop:
31-24
23-16
novo character
15-8
7-0
summary
+
a
novo summary
31-24
23-16
15-8
7-0
Exemplo
Assumir que a mensagem seja:
12, 45, 216, 1, 107, 55, 10, 9, 34, 72, 215, 114, 13,13, 229,18
computação de
summary
summary = (0, 0 , 0, 0)
summary = (12, 0 , 0, 0)
summary = (45, 12 , 0, 0)
summary = (216, 45, 12, 0)
summary = (1, 216, 45, 12)
summary = (107+12, 1, 216, 45)
summary = (55+45, 107+12, 1, 216)
summary = (10+216, 55+45, 107+12, 1)
summary = (9+1, 10+216, 55+45, 107+12)
summary = (34+119, 9+1, 10+216, 55+45)
summary = (72+100, 34+119, 9+1, 10+216)
summary = (215+226, 72+100, 34+119, 9+1)
summary = (114+10, 215+226, 72+100, 34+119)
summary = (13+153,114+10, 215+226, 72+100)
summary = (13+172, 13+153,114+10, 215+226)
summary = (229+185, 13+172, 13+153,114+10)
summary = (18+124, 229+185, 13+172, 13+153)
summary = (142,158, 185, 166)
Em decimal, summary = 142x2563+158x2562+185x256+ 166= 2392766886
Função de codificação
A função de codificação computa:
encode (y) = yx mod m
sendo y = summary, x uma chave privada, e m um número de 32 bits.
Como y = 2392766886, assumindo que x = 1937757177 e
m = 232 -1 = 4294967295
a signature da mensagem é
signature = (2392766886)1937757177 mod 4294967295
s = signature = 37998786
Representação do número
• Todos os dados são ou vetores de 8 bits (caracteres) ou vetores de
32 bits (y=summary , x=chave, m=módulo)
• Assim, usamos a representação binária ou equivalentemente a
hexadecimal.
• Mensagem em hexadecimal:
0C, 2D, D8, 01, 6B, 37, 0A, 09, 22, 48, D7, 72, 0D, 0D, E5, 12
summary = 8E9EB9A6
chave = 737FD3F9
m = FFFFFFFF
s = 0243D0C2
Algoritmos
A função hash resulta em adição módulo 256, uma adição simples de 8
bits sem vai-um.
Operação de exponenciação módulo m é mais complexa:
Assumir que x, y e m são números de n bits. Então
x = x(0) + 2.x(1) + ... + 2n-1 . x (n-1)
e e = (encode (y) = yx mod m)
pode ser escrito da seguinte forma:
e = ((...((12.yx(n-1))2.yx(n-2))2...)2.yx(1))2.yx(0) mod m
Exponenciação
Algoritmo: Exponenciação
e:=1;
for i in 1..n loop
e:= (e*e) mod m;
If x(n-i) =1 then e := (e*y) mod m; end if;
end loop;
e*y
e*e
Lembrando que:
e = ((...((12.y x(n-1) )2.y x(n-2) )2...)2.y x(1) )2.y x(0) mod m
Multiplicação módulo m
A computação (e*y) mod m, é equivalente a uma multiplicação de números
naturais seguida da redução módulo m, ou seja, divisão inteira por m.
Algoritmo para computar r = x.y mod m:
multiply (x, y, z);
divide (z, m, q, r);
onde z = q.m + r com r < m (q é o quociente e r = x.y mod m).
O algoritmo clássico para computar a multiplicação de números naturais é o
algoritmo de deslocamento e soma.
Algoritmo:
p (0) := 0;
for i in 0..n-1 loop
p (i + 1) := (p(i) +x(i)*y)/2;
end loop;
z := p(n) * (2**n);
Exemplo
Aplicação do algoritmo de multiplicação de números naturais
p (0) := 0;
for i in 0..n-1 loop
p (i + 1) := (p(i) +x(i)*y)/2;
end loop;
z := p(n) * (2**n);
x = 1011, y = 0101
0101
x 1011
----------010.1
0101
----------011.11
0000
----------001.111
0101
----------011.0111
p(0) = 0
p(1) = (p(0) + x(0)*y)/2 = (0 + 1*0101)/2 = 0101/2 = 010.1
p(2) = (p(1) + x(1)*y)/2 = (010.1 + 1*0101)/2 = (010.1 + 0101)/2 = 0111.1/2 = 11.11
p(3) = (p(2) + x(2)*y)/2 = (011.11 + 0*0101)/2 = (011.11 + 0)/2 = 1.111
p(4) = (p(3) + x(3)*y)/2 = (1.111 + 1*0101)/2 = (1.111 + 0101)/2 = 110.111/2 = 11.0111
z = 11.0111*(2**4) = 110111
Para computar q e r tal que z = q.m + r, com r < m, pode ser usado o algoritmo
clássico de divisão. Dados x e y tais que x < y, e p, a precisão desejada, a
divisão computa q e r tais que x.2p = q.y + r.
No algoritmo da exponenciação:
e:=1;
for i in 1..n loop
e:= (e*e) mod m;
If x(n-i) =1 then e := (e*y) mod m; end if;
end loop;
os operandos e e y são números de n bits. Além disso, e é sempre menor que
m = FFFFFFFF, tal que ambos os produtos z = e*e ou z = e * y sejam
números de 2n bits satisfazendo a relação z < m.2n
Assim, substituindo x por z, p por n, e y por m.2n, o algoritmo da divisão
computa q e r’ tais que
x.2p = q.y + r
Isto é:
z.2n = q.(m.2n) + r’ com r’ < m.2n,
z = q.m + r com r = r’.2-n < m.
Algoritmo clássico de divisão
O algoritmo é similar ao método de papel e lápis.
A cada passo, o último resto obtido, digamos r(i-1), é multiplicado por 2 e
comparado com o divisor y.
– Se 2.r(i-1) é maior que ou igual a y, então o novo resto é r(i) = 2.r(i-1) – y e
o correspondente bit quociente é igual a 1.
– Caso contrário, o novo resto é r(i) = 2.r(i-1) e o bit quociente
correspondente é igual a 0.
O resto inicial r(0) é o dividendo.
Exemplo: 12/15 em binário
x.2p=x.24
11000000
1111
010010
1111
0001100
1111
1100
r(4)
r(i-1) divisor y
r(0) = 12
2 *12  15  0   q(1)  1 r (1)  24  15  9
2 * 9  15  0   q(2)  1 r (2)  18 15  3
2 * 3  15  0   q(3)  0
r (3)  6
2 * 6  15  0   q(4)  0
r (4)  12
Algoritmo da divisão
r(0) := z; y := m * (2**n);
for i in 1..n loop
if 2* r (i -1) – y < 0 then q(i) := 0; r(i) := 2 * r (i-1); else
q(i) := 1; r(i) := 2 * r (i -1) –y ; end if;
end loop;
r := r (n) / (2**n);
Algoritmo da multiplicação e divisão
Algoritmo da divisão
Algoritmo da multiplicação: r(0) := z; y := m * (2**n);
p (0) := 0;
for i in 1..n loop
for i in 0..n-1 loop
if 2* r (i -1) – y < 0 then q(i) := 0; r(i) := 2 * r (i-1); else
p (i + 1) := (p(i) +x(i)*y)/2; q(i) := 1; r(i) := 2 * r (i -1) –y ; end if;
end loop;
end loop;
z := p(n) * (2**n);
r := r (n) / (2**n);
p(0):= 0;
for i in 0..n-1 loop
p(i+1):= (p(i) + x(i) * y)/2;
end loop;
r (0):= p(n) * (2**n); y:= m*(2**n);
for i in 1..n loop
If 2* r(i-1) – y < 0 then q (i) := 0; r(i) := 2 * r (i-1); else
q(i) := 1; r(i) := 2 * r(i-1) – y; end if;
end loop;
r := r(n)/(2**n);
Plataforma de Hardware
• Para o protótipo será usada a placa XSA-100 da XESS Corporation,
que inclui um FPGA XC2S100 (família Spartan-II da Xilinx).
• O ambiente de projeto inclui os componentes virtuais, dentre os
quais, PicoBlaze, um microprocessador de 8 bits, e sua memória de
programa.
• A operação complexa é a computação de yx módulo m que deve
ser realizada em FPGA.
• Todas as outras operações podem ser feitas no processador.
Arquitetura do sistema
Arquitetura (cont.)
PicoBlaze faz a leitura da entrada do character no endereço 0, e a
entrada de command no endereço 1, onde
command = 000000 sinaliza novo caracter
Computa o summary de 32 bits, e faz a sua escrita, na forma de quatro
bytes separados:
summary = Y(3) Y(2) Y(1) Y(0)
em quatro registradores cujos endereços são 3, 2, 1 e 0,
respectivamente.
Um coprocessador específico recebe o sinal start do PicoBlaze no
endereço 4 e computa
s = (summary)737FD3F9 mod FFFFFFFF,
e gera o ‘flag’ done.
Geração de programa
O programa executado pelo PicoBlaze é constituído de 3 partes:
– Leitura dos sinais de entrada de new_character e sign,
– Leitura da entrada de character e atualização de summary,
– Escrita de summary e o início do comando de start nos registradores de
interface:
summary:= (0, 0, 0, 0);
start := 0;
loop
elsif command = 2 then
-- wait for command = 0
Y(3) := summary (3);
while command > 0 loop null; end loop;
Y(2) := summary (2);
-- wait for command = 1 (new_character) or 2 (sign)
Y(1) := summary (1);
while command = 0 loop null; end loop;
Y(0) := summary (0);
if command =1 then
start := 1;
a:= (summary(0) + character) mod 256;
summary := (0, 0, 0, 0);
summary (0) := summary (1);
start := 0;
summary(1):= summary (2);
end if;
summary(2):= summary (3);
end loop;
summary(3) := a;
Síntese
O bloco exponenciador inclui:
•
dois registradores de 32 bits:
registrador paralelo para guardar e,
e um registrador de deslocamento
carregável, inicialmente
armazenando o valor x e
permitindo a leitura sucessiva de
valores x(n-1), x(n-1),..., x(0)
•
um multiplicador mod m com um
sinal de entrada start e um ‘flag’ de
saída done
•
um multiplexador 2x1 de 32 bits
selecionando entre e ou y como o
segundo operando, multiplicador
zoom
Circuito completo em VHDL
entity exponentiator is
port (
x, y, m: in std_logic_vector (n-1 downto 0);
z : inout std_logic_vector (n-1 downto 0);
clk, reset, start: in std_logic;
done: out std_logic
);
end exponentiator;
Architecture
architecture circuit of exponentiator is
component sequential_mod_mult..end component;
signal start_mult, sel_y, done_mult: std_logic;
signal reg_x, input_y, output_z: std_logic_vector (n-1 downto 0);
subtype step_number is natural range 0 to n;
signal count: step_number;
subtype internal_states in natural range 0 to 14;
signal state: internal_states;
begin
label_1: sequential_mod_mult port map (z, input_y, m, output_z, clk, reset,
start_mult, done_mult);
with sel_y select input_y <= z when ‘0’ , y when others;
-- (continua pagina seguinte)
Cont.
process (clk, reset)
begin
if reset=‘1’ then
state <= 0; done <= ‘0’;start_mult <= ‘0’; count <= 0;
elsif clk’event and clk = ‘1’ then
case state is
when 0 => if start = ‘0’ then state <= state +1; end if;
when 1 => if start = ‘1’ then state <= state +1; end if;
when 2 => z <= conv_std_logic_vector (1,n); reg_x<=x; count <= 0; done <= ‘0’; state<=state +1;
when 3 => sel_y <= ‘0’; start_mult<=‘1’; state <= state +1;
when 4 => state <= state + 1;
when 5 => start_mult <=‘0’; state<= state+1;
when 6 => if done_mult = ‘1’ then state <= state + 1; end if;
when 7 => z <= output_z; if reg_x (n-1) =‘1’ then state <= state +1; else state <= 13; end if;
when 8 => sel_y <= ‘1’ ; start_mult <= ‘1’; state <= state + 1;
when 9 => state <= state + 1;
when 10 => start_mult <= ‘0’; state <= state + 1;
when 11 => if done_mult =‘1’ then state <= state + 1; end if;
when 12 => z <= output_z; state<= state + 1;
when 13 => reg_x (0) <= reg_x (n-1);
when 14 => if count >= n then done <= ‘1’; state <= 0;
else state <= 3; end if;
end case;
end if;
end process;
end circuit;
Zoom – case state
case state is
when 0 => if start = ‘0’ then state <= state +1; end if;
when 1 => if start = ‘1’ then state <= state +1; end if;
when 2 => z <= conv_std_logic_vector (1,n); reg_x<=x; count <= 0; done <=
‘0’; state<=state +1;
when 3 => sel_y <= ‘0’; start_mult<=‘1’; state <= state +1;
when 4 => state <= state + 1;
when 5 => start_mult <=‘0’; state<= state+1;
when 6 => if done_mult = ‘1’ then state <= state + 1; end if;
when 7 => z <= output_z; if reg_x (n-1) =‘1’ then state <= state +1; else
state <= 13; end if;
when 8 => sel_y <= ‘1’ ; start_mult <= ‘1’; state <= state + 1;
when 9 => state <= state + 1;
when 10 => start_mult <= ‘0’; state <= state + 1;
when 11 => if done_mult =‘1’ then state <= state + 1; end if;
when 12 => z <= output_z; state<= state + 1;
when 13 => reg_x (0) <= reg_x (n-1);
when 14 => if count >= n then done <= ‘1’; state <= 0;
else state <= 3; end if;
end case;
Protótipo
Todos os arquivos necessários para programar uma placa XSA100 são
disponíveis:
– exponentiator.vhd: uma descrição completa do circuito de
exponenciação;
– signatu.psm – é o programa em linguagem assembly;
– kcpsm.vhd é o modelo PicoBlaze;
– signatu.vhd é o modelo de programa de memória gerado do programa
em linguagem assembly com kcpsm.exe (Assembler PicoBlaze liberado
pela Xilinx).
Protótipo (cont.)
Para testar o sistema completo, foi sintetizado o circuito incluindo PicoBlaze, a sua
memória de programa, os registradores de interface, e o exponenciador;
Uma máquina de estado finito gerando os comandos e caracteres correspondentes ao
exemplo;
Um circuito que faz a interface da placa com sinais d(7..0) controlável pelo computador
hospedeiro:
d(7) não pode ser usado,
d(3..0) usado para selecionar uma das saídas (out_0 a out_15) ou entradas (in_0 a in_15),
d(6..4) são sinais de controle,
d (6..4)
000
001
010
011
100
comando
nop
write
read
reset
address strobe
Na aplicação vista, os comandos write e address strobe não são usados. Quando o
comando read é ativo, a representação hexadecimal do vetor de 4 bits selecionado
com d(3..0) é mostrado no LED da placa.
O decodificador de 7-segmentos para LED.
p
r
o
t
ó
t
i
p
o