Lista de Exerc€ ¢Ã­cios I

Prévia do material em texto

ENGA78 - SÍNTESE DE CIRCUITOS DIGITAIS 
 
Lista de Exercícios I 
 
Data da prova: 21/05/13 
 
1. Sistemas digitais podem ser divididos em 4 classes de sistemas: 
i) Sistemas de computação de propósito geral; 
ii) Computadores servidores; 
iii) Supercomputadores; e 
iv) Sistemas embutidos. 
 Quais as características marcantes de cada uma destas categorias? 
 
2. Os circuitos integrados (CIs) constituintes de sistemas digitais podem ser divididos em 6 
categorias: 
i) Processadores de propósito geral; 
ii) ASICs; 
iii) Core-based ASICs; 
iv) ASICs pré-difundidos; 
v) ASIPs; e 
vi) Processadores de lógica programável. 
 Cite ao menos uma característica básica de cada categoria. 
 
3. O que significa especificação de um sistema digital? 
 
4. O que significa metodologia de projeto de um sistema digital? 
 
5. Qual a ênfase de cada nível de representação de um projeto (comportamental, estrutural 
e física)? 
 
6. O que diferencia os níveis de abstração de um projeto (processador, RTL, lógico e 
transistor)? 
 
7. No que se baseia a metodologia de captura e simulação? E a metodologia de descrição 
e síntese? 
 
8. Diferencie máquinas de estado finitas de Mealy e de Moore. Faça um pequeno exemplo 
de ambas, destacando as diferenças. 
 
9. O que você entende por paralelismo? Máquinas de estado finitas são adequadas para 
representar paralelismo? Explique sua resposta. 
 
10. Qual a ideia básica de uma metodologia em nível de sistema (metodologia de coprojeto 
hardware/software)? Por que modelos conceituais e linguagens de especificação são tão 
importantes para metodologias deste tipo? 
 
11. Em relação a metodologias de coprojeto hardware/software, diferencie abordagem 
unificada de heterogênea. Qual delas é mais viável atualmente? Por que? 
 
12. O que são gargalos num sistema de computador? Dê um exemplo. 
 
13. Qual (ou quais) o(s) resultado(s) gerado(s) por cada uma das seguintes etapas de uma 
metodologia de coprojeto hardware/software genérica? 
i) Especificação do sistema; 
ii) Particionamento hardware/software; 
iii) Escalonamento/alocação; 
iv) Síntese (hardware, software, interface); 
v) Verificação (verificação formal, simulação, prototipação); e 
vi) Avaliação do projeto. 
 
14. O que você entende por particionamento hardware/software? Quais critérios deverão ser 
considerados por um algoritmo de particionamento espacial, para definir se uma dada 
funcionalidade do sistema será implementada em software (a ser executado em um 
processador já existente) ou em hardware (a ser construído/configurado)? 
 
15. Em relação ao projeto de um sistema digital, diferencie simulação, prototipação e 
verificação formal. 
 
16. O que você entende por arquitetura/organização de um sistema computacional? 
 
17. Explique as arquiteturas para controladores simples, dadas na figura abaixo: 
 
 
 
sinais de entrada sinais de saída 
(a) Arquitetura para FSM de Mealy
 
Registrador de Estado 
 
 
Função 
Próximo 
Estado 
 
 
Função 
de 
Saída 
sinais de entrada sinais de saída 
(b) Arquitetura para FSM de Moore
 
Registrador de Estado 
 
 
Função 
Próximo 
Estado 
 
 
Função 
de 
Saída 
18. A figura seguinte ilustra a arquitetura de um FPGA com estruturas DSP, na qual observa-
se a presença de MACs (unidades que fazem a multiplicação, a soma e o 
armazenamento de resultados provenientes de dados que entram em paralelo): 
 
 
 
 Esboce (através de um esquemático) a arquitetura de um componente de hardware 
capaz de fazer a multiplicação de uma matriz 4 x 3 por uma matriz 3 x 1. 
 
19. O que é um pipeline de instrução? 
 
20. Por que o projeto de uma arquitetura RISC busca a construção de um pipeline de 
instrução curto? 
 
21. Como você mediria o balanceamento entre os estágios de um pipeline? 
 
22. Qual (ou quais) o princípio básico do esquema de pipeline? 
 
23. No exemplo da lavanderia com pipeline, como você obteria um melhor balanceamento? 
Considere o uso de recursos adicionais. 
 
24. Quais as vantagens e as desvantagens de máquinas com pipelines extensos? 
 
25. Por que num pipeline de n estágios, o tempo de execução é superior a 
 
(tempo de execução sem pipeline/n) ? 
 
26. No que consiste a criação de bolhas (stall) no pipeline? Quando deve ocorrer uma bolha? 
 
27. Explique como um perigo RAW pode ocorrer em um pipeline. 
 
28. Considerando pipelines, no que consiste a técnica de forwarding (antecipação)? 
 
29. Baseando-se na figura seguinte, explique o ciclo de instrução para a arquitetura DLX 
sem pipeline, para 3 diferentes tipos de instruções. 
 
 
 
 
 
30. Considerando-se a adoção de um mesmo conjunto de etapas no processamento de uma 
instrução de máquina, por que ocorre aumento na latência quando da adoção de uma 
estrutura pipeline? Qual o ganho obtido na adoção de uma estrutura pipeline, uma vez 
que aumenta-se a latência? 
 
31. Como o reescalonamento de software auxilia na execução mais rápida de programas em 
máquinas pipeline? 
 
32. Explique, através de exemplos, o que são dependências de dados verdadeiras, anti-
dependências e dependências de saída. 
 
33. Demonstre a expressão abaixo para ganho potencial de “pipelinização”: 
 
 
 
 
34. Considere duas máquinas Armen-G e Best-A, as quais foram “pipelinizadas”, resultando 
em máquinas com o mesmo número de estágios. No processo de “pipelinização”, a 
máquina Armen-G não sofreu alteração em seu clock, enquanto a máquina Best-A teve 
o período de seu clock reduzido em 20%. Entretanto, a máquina Armen-G possui 
memória de duas portas, possibilitando-a fazer LOADS sem que o pipeline fique 
paralisado (stall). A máquina Best-A, por possuir memória de uma porta, paralisa o 
pipeline por 1 ciclo de clock quando da execução de instruções LOAD. Usando a 
equação de speedup da questão anterior, qual máquina “pipelinizada” é mais rápida, 
considerando-se a execução de um programa no qual a ocorrência de LOADS 
representa 40% das instruções executadas? 
 
35. Qual (ou quais) o aspecto chave de arquiteturas superescalares? 
 
36. O que é uma estação de reserva? 
 
37. Considerando máquinas superescalares, o que é um processador com look-ahead? 
 
38. Considere uma máquina superescalar com duas unidades de decodificação. Suponha 
que duas instruções foram enviadas para execução e que, num determinado momento, 
uma delas finalizou sua execução (a outra continua executando). Em que caso (ou 
casos) é possível enviar uma terceira instrução para execução? Faça as suposições 
devidas. 
 
39. Considere uma máquina superescalar com despacho e término fora de ordem, composta 
por um somador (latência = 1 ciclo), um multiplicador (latência = 2 ciclos) e uma unidade 
load/store (latência = 2 ciclos). Represente o escalonamento, ciclo a ciclo, para cada 
unidade funcional, para o conjunto de instruções a seguir: 
 
ADD R1, R2, R3 
LW R10, 100 (R5) 
ADD R5, R1, R6 
MUL R7, R4, R8 
ADD R9, R4, R10 
ADD R2, R7, R3 
ADD R11, R1, R6 
 
40. Explique como o aumento no número de registradores provoca uma diminuição no 
número de ocorrências de antidependências e de dependências de saída. 
 
41. Qual a importância do mecanismo de renomeação de registradores? 
 
42. Em Tomasulo, qual a importância do barramento de dados comum (CDB)? 
 
43. Quais informações são armazenadas nas estações de reserva do algoritmo de 
Tomasulo? 
44. Considere uma máquina superescalar que implementa o algoritmo de Tomasulo, 
composta por um somador (latência = 1 ciclo), um multiplicador (latência = 2 ciclos) e 
uma unidade load/store (latência = 2 ciclos). Execute o algoritmo de Tomasulo para a 
sequência de instruções da tabela abaixo, completando-acom a informação sobre em 
qual ciclo de clock ocorre cada um dos eventos tabelados, relacionados às instruções. 
 
Programa Despacho (nº do ciclo de clock) 
Término de 
Execução 
(nº do ciclo de clock) 
Armazenamento 
de Resultados 
(nº do ciclo de clock) 
ADD R1, R2, R3 1 2 3 
LW R10, 100 
(R5) 
2 
ADD R5, R1, R6 
MUL R7, R4, R8 
ADD R9, R4, R10 
ADD R2, R7, R3 
ADD R11, R1, R6 
 
 
45. Dada a tabela de estados abaixo, faça o diagrama de estados correspondente como uma 
FSM de Mealy. Considere A = 1 e B = 0 como estado inicial. 
 
Estado Atual Entradas Estado Futuro Saídas 
A B x y AF BF k m 
0 0 0 0 1 1 0 0 
0 0 0 1 0 0 0 0 
0 0 1 0 0 0 0 1 
0 0 1 1 0 0 0 1 
0 1 0 0 0 1 0 1 
0 1 0 1 0 0 0 0 
0 1 1 0 0 1 0 1 
0 1 1 1 0 1 0 0 
1 0 0 0 1 0 0 1 
1 0 0 1 1 0 1 0 
1 0 1 0 1 0 0 1 
1 0 1 1 0 1 0 0 
1 1 0 0 1 1 1 0 
1 1 0 1 1 0 1 0 
1 1 1 0 1 1 0 1 
1 1 1 1 1 1 0 1 
 
 
46. Dado o circuito seguinte, construa o diagrama de estados correspondente, através da 
análise de sua FSM. 
 
 
 
47. Quais são as características que diferem os 3 estilos de implementação em Verilog? 
 
48. Sobre Verilog, coloque Verdadeiro ou Falso: 
( ) A linguagem Verilog fornece uma camada de abstração para o backend. 
( ) Valores somente podem ser atribuídos a um dado do tipo reg dentro de um bloco 
procedural. 
( ) Dados da classe NET representam conexões físicas entre blocos. 
( ) Dados da classe REGISTER atuam como circuitos sequencias para armazenamento. 
( ) Atribuições não-bloqueantes são utilizadas em blocos combinacionais. 
( ) Parâmetros correspondem a restrições usadas pelo simulador ou pelas ferramentas de 
síntese. 
( ) Blocos always podem ser utilizados para representar lógica sequencial ou lógica 
combinacional. 
( ) Atribuições bloqueantes são utilizadas em blocos sequenciais. 
( ) Blocos procedurais initial são sintetizáveis. 
 
49. Assinale quais das seguintes afirmações são boas práticas de codificação em Verilog: 
( ) Identação do código. 
( ) Uso de parâmetros. 
( ) Escrita de atribuições default dentro de blocos always @ (*). 
( ) Uso de atribuições bloqueantes com não-bloqueantes num mesmo bloco procedural. 
( ) Implementação de lógica sequencial com reset assíncrono. 
 
50. Cite 3 construtores não sintetizáveis em Verilog. 
 
51. Usando um waveform, exemplifique porque deve-se ter cuidado com reset assíncrono. 
 
52. Assinale qual o equivalente em Verilog para funções/procedimentos encontrados em 
linguagens de software: 
( ) Blocos procedurais. 
( ) Lógica combinacional. 
( ) Lógica sequencial. 
( ) Módulos. 
( ) Lista de eventos. 
( ) Parâmetros. 
53. Cite ao menos 1 erro em cada um dos trechos de código a seguir. 
 
 
 
 
 
 
54. Escreva blocos always para os seguintes circuitos: 
 
a) b) 
 
 
 
 
 
 
c) d) 
 
 
 
 
 
 
 
 
55. Sobre FSMs, assinale Verdadeiro ou Falso: 
( ) Uma FSM é uma combinação de circuitos sequenciais e combinacionais que modela um 
comportamento composto de um número finito de estados, transições entre estados e 
ações. 
( ) Na codificação one-hot, o número de bits no código é igual ao número de estados. 
 
 
 
 
( ) A tabela de estados e o diagrama de estados são auxiliares dispensáveis no projeto de 
uma FSM. 
( ) Máquinas de Mealy têm saídas que dependem unicamente do estado atual da máquina, 
enquanto máquinas de Moore têm saídas que dependem do estado atual da máquina e 
de suas entradas. 
( ) A codificação de estados é a alocação de códigos binários aos estados - exemplos de 
codificação incluem código binário, código gray e código one-hot. 
 
56. Considere a figura abaixo. A bomba d'água B1 leva água de um riacho até o tanque 
inferior, e a bomba B2 leva água do tanque inferior para o superior. A bomba B1 deve 
ligar com o objetivo de manter a água sempre próxima do nível máximo (S2), desligando 
ao atingir S2. A bomba B2 funciona da mesma forma, baseada nos níveis S3 e S4, mas 
não poderá funcionar caso o nível do tanque inferior esteja abaixo de S1. Se qualquer 
combinação que os sensores enviarem for impossível de ocorrer na prática, as duas 
bombas devem ser imediatamente desligadas, independente de qualquer outra situação. 
 
 Projete o circuito descrito, em Verilog, fazendo as convenções necessárias. 
 
57. Dado o diagrama de estados seguinte, referente a uma máquina de refrigerantes que 
libera a latinha após a inserção de três moedas de R$ 1,00 (com possibilidade de 
desistência), obtenha o circuito correspondente (esquemático ou Verilog). Faça as 
convenções necessárias. 
 
 
 
58. O código de Hamming é um código de detecção, isto é, permite não apenas detectar 
erro de um bit, mas também a localização do bit errado. Parte-se da observação de que, 
dados dois bits A e B, a operação ou exclusivo C = A ⊕ B calcula o bit paridade (no 
caso, par) dos bits dados. 
 
 Calculando o código de Hamming para correção de 1 bit em uma palavra de 8 bits: 
 
Considere uma palavra de 8 bits: m8m7m6m5m4m3m2m1 
 
A esse dado de 8 bits vamos acrescentar 4 bits adicionais, formando o código de 
Hamming de 12 bits, o qual é numerado da seguinte forma: 
 
x12 x11 x10 x9 x8 x7 x6 x5 x4 x3 x2 x1 
 
onde: 
x10 = m8 
x8 = m7 
x7 = m6 
x6 = m5 
x4 = m4 
x3 = m3 
x2 = m2 
x1 = m1 
 
e os 4 bits adicionais x12, x11, x9 e x5 são assim calculados: 
 
x12 = x10 ⊕ x8 ⊕ x6 ⊕ x4 ⊕ x2 
x11 = x10 ⊕ x7 ⊕ x6 ⊕ x3 ⊕ x2 
x9 = x8 ⊕ x7 ⊕ x6 ⊕ x1 
x5 = x4 ⊕ x3 ⊕ x2 ⊕ x1 
 
 
Agora suponha que esses 12 bits são lidos como sendo: 
 
y12 y11 y10 y9 y8 y7 y6 y5 y4 y3 y2 y1 
 
 
Se não houver erro, então cada yi é igual ao seu respectivo xi. 
 
 
Se houver erro em um bit apenas, é possível detectar tal erro e corrigí-lo. Para isso 
fazemos o seguinte cálculo de 4 bits, denominados k1, k2, k3 e k4: 
 
k1 = y12 ⊕ y10 ⊕ y8 ⊕ y6 ⊕ y4 ⊕ y2 
k2 = y11 ⊕ y10 ⊕ y7 ⊕ y6 ⊕ y3 ⊕ y2 
k3 = y9 ⊕ y8 ⊕ y7 ⊕ y6 ⊕ y1 
k4 = y5 ⊕ y4 ⊕ y3 ⊕ y2 ⊕ y1 
 
 
Se k1 = k2 = k3 = k4 = 0, então não há erro. Senão, o número binário codificado pelos 4 
bits 
k4k3k2k1 
 
determinará a posição do bit errado. Isto é, se k4k3k2k1 = 0111, então o bit y7 está errado. 
 
Questão: Usando código Verilog, faça um circuito ECC (Error Correcting Code) de 
detecção simples, correção simples, usando código de Hamming, considerando palavras 
de memória de 8 bits. Uma das entradas do circuito deverá ser R/W: caso R/W = R, o 
circuito deverá detectar e corrigir um eventual erro na palavra de entrada, gerando a 
palavra correta na saída; caso R/W = W, o circuito deverá gerar na saída o código de 
Hamming da palavra de entrada. 
 
59. Deseja-se construir um circuito para cálculo de módulo 4. Este circuito deverá receber 
uma sequência binária (de qualquer tamanho) e gerar, a cada bit recebido, o resultado 
do resto da divisão da sequência já recebida por 4. Considere que o primeiro bit da 
sequência binária recebido corresponde ao bit mais significativo. Faça o diagrama de 
estados (máquina de estados) com todas as convenções bem claras e implemente tal 
FSM em Verilog. 
 
60. Deseja-se construir um circuito detector de sequências de 2 (ou mais) zeros ou 3 (ou 
mais) uns, conforme figura abaixo. 
 
 
 
 
 
 Faça a síntese, em Verilog, da FSM correspondente a DetectorSequencias. 
 
61. Dada a seguinte especificação, faça o diagrama de estados equivalente, assim como o 
código Verilog correspondente. Exponha claramente as convenções que você adotou 
(incluindo o tipo de FSM utilizada, sinais de entrada e de saída, rótulos de transições e 
estados, estado inicial e condições de reset). 
 
Programe um robô para acompanharum muro. A figura abaixo ilustra o problema. Na 
parte a) da figura, o mundo do robô é uma matriz de células, na qual cada componente é 
livre (células brancas) ou ocupado por um muro (células escuras). O robô, mostrado 
como um triângulo, é colocado em qualquer célula livre, respeitando uma das direções 
paralelas ao gradeado da matriz (horizontal ou vertical), com sua frente voltada para 
qualquer um dos 4 sentidos possíveis (para cima, para baixo, para a direita ou para a 
esquerda). 
 
a) Campo de testes do robô. b) Comportamento exigido: dobrar o muro. 
 
 
 
 
CLK 
 
Entrada 
 
 
 
DetectorSequencias 
Saida_00 
 
Saida_111 
 
O robô possui 2 sensores binários: head (sensor situado na frente do robô, que retorna 1 
quando a célula situada à frente do robô está ocupada por um muro - caso contrário, 
retorna 0) e left (sensor situado na lateral esquerda do robô, que retorna 1 quando a 
célula do lado esquerdo do robô é ocupada por um muro - caso contrário, retorna 0). 
 
Em relação à movimentação, o robô é capaz de fazer apenas 2 tipos de movimento: 
avançar para uma célula livre à sua frente ou rotacionar 90º para a esquerda, mantendo-
se na mesma célula em que se encontra. Cada movimento consome 1 pulso de clock. 
 
Ao ligar o robô, 4 casos são possíveis, os quais deverão ser tratados como segue: 
 
Caso 1: robô em uma área livre (ambos sensores retornando 0). Neste caso, o robô 
deverá avançar até o encontro de um muro e acompanhá-lo, dando-lhe o lado 
esquerdo; 
Caso 2: robô com muro à frente e do lado esquerdo (ambos sensores retornando 1). 
Neste caso, o robô deverá rotacionar até encontrar um muro à sua esquerda 
que possa ser acompanhado; 
Caso 3: robô com muro somente à frente (head = 1, left = 0). Mesmo comportamento do 
caso 2; 
Caso 4: robô com muro somente à esquerda (head = 0, left = 1). Neste caso, o robô 
deverá acompanhar o muro. 
 
Em qualquer dos casos acima citados, o robô deverá acompanhar o muro até que um 
novo muro seja encontrado ou até que o muro dobre à esquerda, como na parte b) da 
figura, fazendo com que o robô também dobre à esquerda e prossiga. Como regra 
prioritária, após cada rotação, se houver um muro à esquerda do robô, este deverá ser 
acompanhado. 
 
62. Você será aprovado(a)?