Baixe o app para aproveitar ainda mais
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)?
Compartilhar