Universidade Federal de Santa Catarina Departamento de Informática e Estatística Bacharelado em Ciências da Computação

INE5406 - Sistemas Digitais – semestre 2011/1 Prof. José Luís Güntzel guntzel@inf.ufsc.br www.inf.ufsc.br/~guntzel

3a Prova Semestral (05/07/2011)

Nome: ______________________________________________ Turma:__________ Matrícula:______ Instruções e definição de critério de avaliação:

• A interpretação das questões é parte integrante desta avaliação. • Utilizar as convenções vistas em aula. • As respostas devem ser fornecidas nos espaços a elas reservados, junto aos enunciados das respectivas questões.

Respostas fora destes espaços não serão consideradas. Ao final desta prova há uma folha de “rascunho autorizado”. • Nas questões que solicitam resposta e justificativa, a pontuação será obtida somente se a resposta e a respectiva

justificativa estiverem corretas. • Todas as questões são pontuadas com valores múltiplos de 0,5. • O tempo de prova esgota-se pontualmente às 17:40.

Questão 1 (valor total: 6,0 pontos)

A Fig. 1a mostra as interfaces do sistema digital “Interpola”. A memória “Mem_A” armazena um bloco de 256 pixels pertencente a um quadro (bloco A), ao passo que a memória “Mem_B” armazena um bloco de 256 pixels pertencente a outro quadro (bloco B). A memória “Mem_I” armazenará um bloco de 256 pixels correspondente ao resultado da execução. Cada pixel é representado por um número binário inteiro sem sinal, com 8 bits.

(a) (b) Fig. 1 – Interfaces do sistema digital “Interpola” (a) e sua FSMD (b).

A Fig. 1b mostra uma FSMD (versão Moore) para o sistema digital "Interpola". Nesta FSMD, "Mem_A[end]" ("Mem_B[end]", "Mem_I[end]") representa um acesso à linha de "Mem_A" ("Mem_B[end]", "Mem_I[end]") cujo endereço é "end". Além disso, esta FSMD assume que: • Antes que "início=1", "Mem_A" e "Mem_B" são devidamente carregadas. • A leitura de uma linha de "Mem_A" (de "Mem_B") é realizada mantendo-se o endereço ("end")

estável e o sinal lê=1 durante 4ns. Após este tempo, o valor armazenado em "Mem_A[end]" (em "Mem_B[end]") estará disponível na saída pixel_A (na saída pixel_B).

• A escrita em uma linha de "Mem_I" é realizada mantendo-se o endereço ("end") e o valor a ser escrito (pixel_I) estáveis e o sinal escreve=1 durante 4ns. Após este tempo, o valor fornecido em pixel_I terá sido escrito no endereço "end" de "Mem_I" (ou seja, em "Mem_I[end]").

ine5406 - Sistemas Digitais - semestre 2011/1 Prof. José Luís Güntzel 3a Prova Semestral (P3) p.2/6

Para o restante desta questão, assumir que: • As variáveis "end" e "cont" da FSMD da Fig. 1b devem ser implementadas por um único

registrador-incrementador (denominado "cont"), o qual possui reset assíncrono (sinal "zcont") e incremento síncrono (sinal "icont");

• A divisão que aparece em S3 (Fig. 1b) é inteira. Seu resultado deve ser truncado para 8 bits.

a) [Valor: 0,5 ponto] Quantos bits, no mínimo, deve ter o contador "cont" descrito acima?

Resposta: _____ bits

Justificativa/cálculos:

b) [Valor: 1,5 ponto] Com base nas informações das Figs. 1a e 1b, e respeitando as especificações e restrições fornecidas no enunciado anterior, complete o diagrama do bloco operativo (B.O.) de “Interpola” mostrado na Fig. 2. Cada item abaixo receberá 0,5 somente se estiver completamente correto. • Parte do B.O. usada para controlar quantas vezes o laço {S2, S3, S4} é executado. • Elementos que tratam dados e suas conexões. • Sinais de comando e suas respectivas identificações.

Fig. 2 – Diagrama do B.O. de “Interpola” (desenho a ser completado).

c) [Valor: 0,5 ponto] Quantos ciclos de relógio são necessários para que "Interpola" realize uma execução completa, conforme especificado na FSMD da Fig. 1b. (Considere duas execuções de S0: uma no início e uma no fim.) Justifique sua resposta, explicitando o cálculo do número de ciclos.

"Interpola" necessita ______ ciclos de relógio para realizar uma execução completa.

Cálculos:

ine5406 - Sistemas Digitais - semestre 2011/1 Prof. José Luís Güntzel 3a Prova Semestral (P3) p.3/6

d) [Valor: 2,0 pontos] Assumindo os atrasos máximos (i.e., críticos) mostrados na Tab. 1 a seguir, calcule o tempo necessário (em ns) para realizar as operações previstas para os estados S2, S3 e S4 da FSMD da Fig. 1b. Calcule também a frequência máxima do relógio (em MHz) para "Interpola". (Obs: 0,5 ponto para cada item completamente correto.)

Tab.1 – Atrasos máximos para os elementos a serem usados na construção de "Interpola". Componente Característica Símbolo Atraso (máximo)

Mem_A, Mem_B tempo para leitura de uma linha tleit 4 ns Mem_I tempo para escrita de uma linha tesc 4 ns Somador atraso crítico tsoma 2 ns Registradores com carga paralela tempo de setup tsu 0,5 ns Registradores com carga paralela tempo de carga tco 1 ns Registradores com carga paralela tempo de hold th Desprezível (0 ns) Registrador-incrementador tempo para incremento tinc Desprezível (0 ns) Sinais de controle (qualquer um) atraso d Desprezível (0 ns) Outras operações não especificadas acima atraso - Desprezível (0 ns)

Tempo necessário para executar S2=_____ns Cálculo: Tempo necessário para executar S3=_____ns Cálculo: Tempo necessário para executar S4=_____ns Cálculo: Frequência máxima do relógio a ser aplicado em "Interpola" = _______ MHz Justificativa: Considere uma segunda versão de “Interpola”, chamada de "Interpola_v2". Nesta versão, cada memória é capaz de armazenar 256 pixels, porém com 4 pixels por linha. Além disso, o B.O. para esta versão é capaz de processar simultaneamente 4 pares de pixels (4 pixels lidos de “Mem_A” e 4 pixels lidos de “Mem_B”) a cada execução do laço {S2, S3, S4} da FSMD da Fig. 1b.

e) [Valor: 0,5 ponto] Quantos ciclos de relógio são necessários para que "Interpola_v2" realize uma execução completa, considerando ainda a FSMD da Fig. 1b. (Considere duas execuções de S0: uma no início e uma no fim.) Justifique sua resposta, explicitando o cálculo do número de ciclos.

"Interpola_v2" necessita ______ ciclos de relógio para realizar uma execução completa.

Cálculos:

ine5406 - Sistemas Digitais - semestre 2011/1 Prof. José Luís Güntzel 3a Prova Semestral (P3) p.4/6

f) [Valor: 0,5 ponto] Complete a Fig. 3 para que ela represente a parte do B.O. de "Interpola_v2" usada para controlar quantas vezes o laço {S2, S3, S4} é executado. Identifique os sinais envolvidos e os respectivos números de bits.

Fig. 3 – Diagrama da parte do B.O. de “Interpola_v2” que controla o laço (desenho a ser completado).

g) [Valor: 0,5 ponto] Na Fig. 4, complete os elementos do B.O. de "Interpola_v2" que realizam o cálculo sobre os pares de pixels identificados pelos retângulos pontilhados.

Fig. 4 – Diagrama da parte do B.O. de “Interpola_v2” que realiza o cálculo com os pixels (desenho a ser

completado).

Questão 2 (valor total: 2,0 pontos)

A Fig. 5 mostra o diagrama do bloco operativo (datapath) de um sistema digital de propósito geral, normalmente referenciado por microprocessador. A Tab. 2 mostra as operações que a ULA deste microprocessador é capaz de realizar e os respectivos códigos de operação (i,.e., valores para o sinal op). Os registradores são referenciados por R(i), onde i é o endereço do registrador no banco de registradores. O sinal EscReg comanda a escrita de registrador (fazendo-se EscReg=1), sendo sincronizado pela borda de subida do relógio (embora o relógio esteja omitido na Fig. 5).

ine5406 - Sistemas Digitais - semestre 2011/1 Prof. José Luís Güntzel 3a Prova Semestral (P3) p.5/6

Fig.5 – Bloco operativo (datapath) de um microprocessador.

Tab.2 – Operações possíveis na ULA do microprocessador da Fig. 5 e respectivos sinais de controle.

op1 op0 Operação da ULA 0 0 S = A AND B 0 1 S = A OR B 1 0 S = A + B 1 1 S = A – B

Complete os sinais de controle (em binário) na Tab. 3 para que o bloco operativo da Fig. 5 realize as operações entre registradores que aparecem na coluna mais à esquerda desta tabela. Convenção: em R(i) ← R(j) + R(k), R(j) é o "Dado lido #1" e R(k) é o "Dado lido #2" (ver Fig. 5). (Critério de correção: 0,5 para cada linha corretamente preenchida.)

Tab.3 – Sequência de operações a serem realizadas e respectivos valores dos sinais de controle (a completar).

operação Reg a ser lido #1

Reg a ser lido #2 op Reg a ser

escrito EscReg

R(2) ← R(0) + R(1) R(5) ← R(2) + R(2) R(15) ← R(9) – R(5)

R(21) ← R(12) AND R(11)

Questão 3 (valor total: 2,0 pontos) A Fig. 6a mostra o algoritmo da raiz quadrada inteira. A Fig. 6b mostra os sinais de interface de um sistema digital capaz de realizar este algoritmo, doravante denominado "raiz". O dado de entrada (ent) e o resultado (res) são números inteiros sem sinal, com n bits.

0 alg_raiz() { 1 pronto ← 0; 2 x ← ent; r ← 1; d ← 2; s ← 4; 3 while (x >= s) { 4 d ← d + 2; 5 s ← s + d; 6 s ← s + 1; 7 r ← r + 1;} 8 pronto ← 1; res ← r; 9 }

(a) (b) Fig. 6 – Algoritmo da raiz quadrada de um número inteiro (a) e interface do sistema digital raiz (b).

Assuma que o bloco operativo (B.O.) do sistema digital raiz possua as seguintes características: • Possui quatro registradores para armazenar individualmente as variáveis x, s, r e d do algoritmo da

Fig. 6a. Cada um destes registradores possui apenas um sinal de controle (Cx, Cs, Cr e Cd, respectivamente), o qual controla a carga paralela. Isto significa que estes registradores não são capazes de realizar nem incremento, nem set e nem reset.

• Possui apenas uma unidade funcional, do tipo somador.

ine5406 - Sistemas Digitais - semestre 2011/1 Prof. José Luís Güntzel 3a Prova Semestral (P3) p.6/6

• Possui um comparador, o qual é utilizado para realizar a comparação prevista na linha 3 do algoritmo da Fig. 6a.

a) [Valor: 1,0 ponto] Complete o diagrama de estados de alto nível (FSMD), modelo de Moore, do sistema digital raiz mostrado na Fig. 7, satisfazendo às seguintes restrições:

• Esta FSMD deve permitir a execução correta do algoritmo da Fig. 6a , satisfazendo às restrições descritas no enunciado desta questão. (0,5 ponto)

• O número de estados deve ser mínimo. No estado S2, apenas o teste x >= s é realizado (0,5 ponto)

Fig. 7 – FSMD para o algoritmo da Fig. 6a, obedecendo às restrições impostas nesta questão (a ser completado).

Para os itens b e c que seguem, considere que não haja restrição no número de somadores a serem usados no B.O. de raiz, de modo que é possível utilizar tantos somadores quantos se queira. b) [Valor: 0,5 ponto] Nas condições acima enunciadas, qual é o menor número de ciclos de relógio

necessários para executar uma passagem pelo laço do algoritmo da Fig. 6a (i.e., os passos 3 a 7)?

Resposta: _____ ciclos de relógio. Justifique: c) [Valor: 0,5 ponto] Complete a figura abaixo, de modo que ela mostre corretamente a nova versão

da FSMD de raiz.