Conceitos Basicos de Processamento de Dados-Tipos-Componentes-Funcionamento

1 Capítulo 1 Conceitos Básicos Objetivos Introduzir os conceitos básicos de processamento de dados Apresentar um modelo e componentes lógicos de um computador Mostrar o princípio de funcionamento de um computador Tipos de computador Computadores digitais representam informações através de grandezas discretas maior precisão e maior capacidade de armazenamento de dados Computadores analógicos representam informações através de grandezas contínuas maior velocidade Computadores híbridos reúnem as características dos dois tipos acima Sistema computacional HARDWARE conjunto de componentes eletroeletrônicos eou eletromecânicos com os quais são construídos os computadores e seus periféricos SOFTWARE conjunto de programas e sua documentação Processamento de dados Os conceitos básicos de processamento de dados são os de codificar armazenar e transformar de informação AMBIENTE HARDWARE PESSOA SOFTWARE AMBIENTE EXTERNO COMPUTADOR DADOS REPRESENTAÇÃO DE DADOS RESULTADOS REPRESENTAÇÃO DE RESULTADOS PROCESSAMENTO entradas saídas 2 Modelo para o processamento de dados O processamento de dados pode ser organizado em níveis para melhor se situar os componentes e ações envolvidas Nível Niveis de processamento PROBLEMA SOFTWARE 7 Aplicação tradução 6 Linguagem orientada ao problema compilação 5 Linguagem de montagem assembly compilação 4 Sistema operacional interpretação 3 Conjunto de instruções interpretação 2 Arquitetura microarquitetura HARDWARE 1 Lógica digital 0 Transistores SOUÇÃO Funcionamento do computador O computador seguindo instruções colocadas em sua memória pode receber dados por meio de unidades de entrada ligadas às interfaces de entrada armazenálos em sua memória principal transformálos através de operações aritméticas e decisões lógicas e colocar os resultados obtidos em unidades de saída de dados ligadas às interfaces de saída As ligações entre unidades são feitas através das vias ou barramento por onde passam as informações relativas ao conteúdo dados ou de sua localização endereços e da via de controle por onde passam as informações relativas ao comando das unidades A sequência de instruções colocada na memória do computador que serve para manipular os dados é denominada programa que é a tradução de um algoritmo mediante uso de uma linguagem de programação 3 Conceitos importantes BIT BInary digiT dígito binário unidade de informação tem somente pode receber os valores 0 ou 1 BYTE BinarY Term termo binário conjunto de bits que serve para representar os números as letras os sinais de pontuação etc Palavra WORD conjunto de bytes que pode ser tratado como uma unidade Algoritmo conjunto de instruções que atendem a um objetivo definido Linguagens de programação Linguagem de máquina Linguagens simbólicas Linguagem de montagem ASSEMBLY ou de máquina Linguagem algorítmica programador Tradutor compiladorinterpretador programa que traduz outro escrito em uma linguagem de programação programa fonte para um terceiro escrito em linguagem de máquina ou outra qualquer programa objeto o processo de tradução pode ser feito por COMPILAÇÃO cada comando é convertido em uma série de instruções em linguagem da máquinaobjetivo em uma série de etapas Executa a decodificação uma só vez para cada comando mas tem que guardar todo o código gerado Pode otimizar o código gerado e tem depuração mais complexa INTERPRETAÇÃO cada comando da linguagem é diretamente executado produzindo um resultado imediato Economiza memória mas a rapidez de execução é comprometida e tem depuração mais simples Programa Fonte Tradutor Programa Objeto 4 Arquiteturas de computadores As arquiteturas típicas de computadores podem ser agrupadas em três tipos arquiteturas sequenciais arquiteturas com paralelismo em baixo nível arquiteturas paralelas Classificação segundo Flynn para fluxos de dados e instruções SISD Single Instruction Single Data stream SIMD Single Instruction Multiple Data stream MISD Multiple Instruction Single Data stream MIMD Multiple Instruction Multiple Data stream com memória compartilhada programação mais simples com compartilhamento de recursos limitações barramentomemória cache com memória distribuída programação mais complexa múltiplos usosusuários limitações devido às necessidades de comunicação entre componentes Separação segundo o conjunto de instruções CISC RISC conjunto de instruções mais complexo conjunto de instruções mais simples conjunto de instruções mais numeroso conjunto de instruções reduzido instruções mais longas mais bits instruções menores menos bits requer mais ciclos de clock requer menos ciclos de clock mais rápido menos ortogonal instruções específicas e pouco usadas mais ortogonal mais potência e maior flexibilidade 5 Modelo de computador de arquitetura sequencial As unidades funcionais se comunicam através de vias ou barramentos de dados e endereços de controle e pelas interfaces de entrada ou saída com componentes periféricos UNIDADE DE CONTROLE UNIDADE LÓGICA E ARITMÉTICA MEMÓRIA PRINCIPAL MEMÓRIA SECUNDÁRIA INTERFACES UNIDADES DE ENTRADA UNIDADES DE SAÍDA Unidade Central de Processamento PERIFÉRICOS MODELO DE COMPUTADOR UNIDADE DE CONTROLE UNIDADE LÓGICA E ARITMÉTICA MEMÓRIA PRINCIPAL INTERFACES DE ENTRADA INTERFACES DE SAÍDA Barramento de Controle Barramento de Dados e Endereços Unidade Central de Processamento Periféricos Periféricos 6 Unidades de entrada e saída Unidade de fita magnética DAT Unidade de disco magnético rígido ou flexível Unidade de disco ótico CDROM CDRW DVDROM DVDRW BlueRay Leitora e perfuradora de cartões Leitora e perfuradora de fita de papel Terminal de apresentação visual vídeo Leitora ótica e leitora de caracteres magnéticos Impressora Tabletes e mesa digitalizadora Manipuladores gamepad joystick touchpad mouse trackball pen Unidade de fotocomposição Unidade de captura e processamento de somvoz Unidade de captura e processamento de imagens Unidade de captura de movimentos Sensores Atuadores Unidade aritmética e lógica É a unidade encarregada de realizar operações aritméticas e lógicas elementares Unidade de controle É a unidade encarregada de coordenar os diversos componentes Memória principal É a unidade encarregada de guardar os dados recebidos das unidades de entrada para imediato processamento Um dado a ser processado pelo computador pode ser colocado na memória na hora de se executar as ações de transformação e também um resultado de uma transformação pode ser armazenado antes que passe para as unidades de saída A memória é considerada um meio temporário de armazenamento de dados que permanecem alí durante o tempo em que estiverem sendo processados Tipos de memória RAM Random Access Memory leitura e gravação ROM ReadOnly Memory apenas leitura PROM Programmable ReadOnly Memory ROM programável pelo usuário EPROM Erasable Programmable ReadOnly Memory PROM apagável por luz ultravioleta EAPROM Eletrically Alterable ReadOnly Memory PROM apagável eletricamente 7 Transferência de dados Em qualquer computador dados são transferidos entre a unidade de armazenamento memória e as outras unidades O esquema de seleção de dados a serem transferidos para ou da memória é conhecido como endereçamento Se for desejado saber um conteúdo de memória o processador coloca o endereço correspondente no barramento de endereços e a memória responde colocando no barramento de dados uma cópia da palavra contida naquela posição Se for desejado guardar um conteúdo na memória o processador coloca o endereço correspondente no barramento de endereços e o dado no barramento de dados Vários sinais de controle são usados para controlar a direção e a temporização das transferências Memória secundária A memória secundária pode ser composta por vários tipos de dispositivos capazes de ampliar a capacidade de armazenamento da memória principal Essas memórias auxiliares podem armazenar grandes quantidades de dados e programas permitindo que sejam solicitados diretamente pela memória principal quando necessários Outra função da memória secundária é oferecer expansão virtual da memória principal MEMÓRIA Endereço Dado LEITURA MEMÓRIA Endereço Dado GRAVAÇÃO 8 Componentes básicos Os registradores são os blocos básicos com os quais são construídos os computadores Qualquer computador pode ser entendido como um conjunto de registradores e linhas de comunicação vias ou barramentos entre eles Exemplos para controle apontador de instrução AI PC Program Counter serve para guardar o endereço da instrução que vai ser executada registrador de instrução RI IR Instruction Register serve para guardar uma cópia da instrução que vai ser executada para operações registrador principal acumulador registrador auxiliar ACUMULADOR SOMADOR COMPARADOR REGISTRADOR AUXILIAR Barramento de Controle Barramento de Dados e Endereços Unidade Lógica e Aritmética Palavra de Controle Temporização APONTADOR DE INSTRUÇÃO CONTROLADOR SEQÜENCIALIZADO R REGISTRADOR DE INSTRUÇÃO Barramento de Controle Barramento de Dados e Endereços Unidade de Controle Palavra de Controle Temporização 9 para armazenamento e organização do acesso à memória registrador de endereço REM NR Index Register registrador de dados RDM DR Data Register Instruções Tipos de instrução carga e armazenamento lógicoaritméticas teste e desvio Instruções Tipos de instrução carga e armazenamento lógicoaritméticas teste e desvio Formatos de instrução código da operação código da operação endereço de operando ou instrução código da operação endereço de operando endereço de operando ou instrução código da operação endereço de operando endereço de operando endereço do resultado ou instrução REGISTRADOR DE ENDEREÇOS ARMAZENAMENTO REGISTRADOR DE DADOS Barramento de Controle Barramento de Dados e Endereços Memória Principal Palavra de Controle Temporização 10 Ciclo básico de execução de uma instrução Ciclo de memória Tempo requerido para uma operação elementar Tamanho de palavra É o número de bits de informação instrução ou dado que um registrador ou posição de memória é capaz de armazenar Exemplos Computadores com palavras de 08 bits baseados no microprocessador Zilog Z80 16 bits baseados no microprocessador Intel 8086 32 bits baseados no microprocessador Intel 80386 64 bits baseados no microprocessador Intel Itanium 52 bits UNISYS B6910 Tipos de operandos dados e operações Os operandos podem ter tamanhos variando de 1 bit a vários bytes e representar valores de diversas naturezas segundo uma codificação Podem ser simples ou agrupados Podem conter os valores diretamente ou serem referências para onde esses estão guardados na memória Tipos referência valor primitivos agrupados homogêneos heterogeneos lógico literal inteiro real APONTADOR DE INSTRUÇÃO BUSCA NA MEMÓRIA FETCH DECODIFICAÇÃO CÁLCULO DE ENDEREÇOS DE OPERANDOS EXECUÇÃO NOVO ENDEREÇO 11 Pilha A pilha em um computador é uma parte da memória usada também por subrotinas e para tratar interrupções O conceito é simples a cada vez que um dado é colocado na pilha push ele é posto em cima de outros já armazenados Só o topo da pilha é acessível a cada momento e pode ser retirado pop Quando isto acontece o dado é removido da pilha e o dado imediatamente abaixo desse seerá indicado como o topo A vantagem da pilha é o acesso rápido ao conteúdo Capacidade de endereçamento Referese a quantidade de memória que o computador é capaz de endereçar Exemplo Se um apontador de instrução tem 16 bits nenhum programa pode usar mais de 65536 posições de uma só vez Velocidade Depende de dois fatores número de ciclos gastos em uma instrução e da velocidade de operação geral do computador Exemplo Se um computador opera a 1 Ghz o tempo de um ciclo de instrução é 1 nanossegundo MEMÓRIA elemento N elemento 2 APONTADOR DA PILHA stack pointer TOPO elemento 1 primeiro a ser executado último a ser executado 12 Programação Exemplo Supor para o modelo de computador descrito acima as seguintes instruções Mnemônico Código Significado nop 0000 0000 passar adiante não fazer nada out 0001 0000 copiar o conteúdo do acumulador para o registrador de saída inc 0010 0000 incrementar de uma unidade o valor no acumulador dec 0011 0000 incrementar de uma unidade o valor no acumulador load xx 0100 xxxx carregar o acumulador com o conteúdo da memória na posição xxxx store xx 0101 xxxx carregar o conteúdo do acumulador na memória na posição xxxx add xx 0110 xxxx carregar o registrador B com o conteúdo da memória na posição xxxx e somálo ao acumulador sub xx 0111 xxxx carregar o registrador B com o conteúdo da memória na posição xxxx e subtraílo do acumulador not 1000 0000 complementar o conteúdo do acumulador or 1001 0000 disjunção do acumulador com o conteúdo da memória na posição xxxx and 1010 0000 conjunção do acumulador com o conteúdo da memória na posição xxxx xor 1011 0000 disjunção exclusiva do acumulador com o conteúdo da memória na posição xxxx jump xx 1100 xxxx carregar o apontador de instrução como endereço da posição xxxx e executar a instrução que ali estiver jumpS xx 1101 xxxx testar se o sinal do acumulador é negativo se for saltar para a instrução na posição xxxx senão executar a próxima instrução jumpZ xx 1110 xxxx testar se o acumulador é igual a zero se for saltar para a instrução na posição xxxx senão executar a próxima instrução halt 1111 0000 parar a execução 13 Aplicação 1 Escrever um programa capaz de calcular 10 4 6 3 Ações a serem processadas Mapeamento das ações na memória Endereços Conteúdo Significado Descrição 00 0000 0100 1100 load 12 guardar 10 01 0001 0111 1101 sub 13 subtrair 4 02 0010 0110 1110 add 14 somar 6 03 0011 0110 1111 add 15 somar 3 04 0100 0001 0000 out mostrar resultado 05 0101 1111 0000 halt parar 06 0110 0000 0000 nop 07 0111 0000 0000 nop 08 1000 0000 0000 nop 09 1001 0000 0000 nop 10 1010 0000 0000 nop 11 1011 0000 0000 nop 12 1100 0000 1010 10 valor 10 13 1101 0000 0100 04 valor 04 14 1110 0000 0110 06 valor 06 15 1111 0000 0011 03 valor 03 guardar 10 no acumulador subtrair 4 ao acumulador somar 6 ao acumulador somar 3 ao acumulador mostrar valor do acumulador parar 14 Aplicação 2 Escrever um programa capaz de calcular 3 x 5 Ações a serem processadas por o total no acumulador somar 3 ao acumulador guardar o resultado por o contador no acumulador diminuir um do acumulador guardar o contador acumulador é zero por o total no acumulador mostrar o resultado parar sim não 15 Mapeamento das ações na memória Endereços Conteúdo Significado Descrição 00 0000 0100 1111 load 15 pegar o total 01 0001 0110 1100 add 12 somar 3 02 0010 0101 1111 store 5 guardar resultado 03 0011 0100 1101 load 13 pegar contador 5 04 0100 0111 1110 sub 14 diminuir 1 05 0101 0101 1101 store 13 guardar contador 06 0110 1110 1000 jumpZ 08 testar se é zero 07 0111 1100 1001 jump 00 se não for voltar a 00 08 1000 0100 1111 load 15 pegar o total 09 1001 0001 0000 out mostrar resultado 10 1010 1111 0000 halt parar 11 1011 0000 0000 nop 12 1100 0000 0011 03 parcela a somar 13 1101 0000 0101 05 vezes a somar 14 1110 0000 0001 01 unidade 15 1111 0000 0000 00 total valor inicial Modelos de arquiteturas de computadores Há três modelos de arquiteturas que se destacam o de von Neumann ou de Princeton com uma unidade central de processamento CPU e uma unidade de armazenamento memória para dados e instruções usado nos primeiros computadores como o Mark I ENIAC EDSAC e ENIAC o de Harvard com unidades de armazenamento separadas para dados e instruções geralmente empregado em processadores de sinais DSP e microcontroladores PIC o de Harvard Modificado com uma só unidade de armazenamento mas com a capacidade da CPU acessar concorrentemente dois ou mais barramentos de dados Inclui dispositivos separados caches para acessar dados como no modelo de von Neumann e instruções como no modelo de Harvard Empregado nas famílias de processadores x86 e ARM Histórico dos principais microprocessadores A partir do início dos anos 1960 fabricantes de componentes eletrônicos começaram a colocar vários transistores em pastilhas de silício com 14 de área circuito integrado aumentando progressivamente o número de elementos por pastilha circuitos integrados em larga escala Esses circuitos foram os modelos para a maioria dos microprocessadores modernos Em 1971 a INTEL Co apresentou o primeiro microprocessador de 4 bits o 4004 Em 1973 foi lançado o de 8 bits o 8008 Em seguida apareceram no mercado microprocessadores como o INTEL 8080 e INTEL 8085 o ZILOG Z80 e o MOTOROLA 6800 Essas linhas de produtos evoluíram naturalmente para os microprocessadores de 16 bits como os INTEL 8088 8086 80186 80286 o ZILOG Z8000 e o MOTOROLA 68000 Em seguida surgiram os microprocessadores de 32 bits os INTEL 80386 80486 e Pentium o INTEL i860 e a família MOTOROLA 680xx e os de 64 bits como a família Alpha da DEC Ultra da Sun Itanium da Intel e Opteron da AMD Nos últimos anos têm sido introduzidos microprocessadores cada vez mais rápidos e mais complexos que seus predecessores bem como arranjos de multiprocessadores Intel Dual Core Core Duo Quad Core e AMD Turion e Fusion Isso se reflete diretamente na capacidade de endereçamento de memória na rapidez de execução e na complexidade de funções desempenhadas 16 Organização básica de um computador digital von Neumann Usa a máquina para guardar dados e os códigos de uma sequência de operações instruções que atuam sobre dados que representam a solução algorítmica do problema programa A Acumulador ou registrador A Dedicado às tarefas de cálculo e manipulação de dados B Registrador B Auxiliar para operações com dois operandos Ai Apontador de instrução Guarda o endereço da posição de memória que contém o código da próxima instrução a ser executada Após a execução dessa ele passará a indicar a próxima Ri Registrador de instrução Guarda uma cópia da instrução a ser decodificada e interpretada pela Unidade de Controle Cc Códigos de condição ZERO NEGATIVO CARRY OVERFLOW Registra ocorrências excepcionais flags ou status REM Registrador de Endereços da Memória Guarda o endereço da palavra a ser manipulada RDM Registrador de Dados da Memória Guarda cópia do conteúdo de um endereço da memória ULA ES Periféricos B Cc Ri A Ai U Controle sinais de controle Memória REM RDM dados endereços 17 Sistemas operacionais Sistema operacional é o programa ou a coleção de programas responsável pela supervisão dos processos computacionais em progresso em um computador digital de uso geral Funções tornar a comunicação do homem com a máquina interface mais natural e inteligível apresentando ao usuário uma máquina mais flexível para se utilizarprogramar possibilitar o uso eficiente e controlado dos seus diversos recursos É o principal responsável pela alocação e controle dos recursos físicos hardware de modo a homogeneizar e compatibilizar as diferentes velocidades de operação permitindo ao computador funcionar na sua capacidade máxima ou próximo a ela possibilitar o uso compartilhado e protegido dos diversos recursos ainda assim eficiente e que os usuários possam se beneficiar do trabalho conjunto de outros e cooperando entre si na execução de projetos complexos A sua comunicação com o usuário se faz através de uma linguagem de controle declarações ou comandos simples shell que levam o sistema operacional a executar uma ação específica Tipos de sistemas operacionais monolíticos em camadas micronúcleo microkernel clienteservidor máquina virtual exonúcleo máquinas virtuais separadas por recursos Limitado pela unidade central de processamento CPUbound ES UCP processo processo Limitado por entradassaídas IObound ES UCP processo chamadas de sistema comandos HARDWARE KERNEL SHELL APLICATIVOS USUÁRIOS serviços processos instruções interface SISTEMA OPERACIONAL 18 Classificação 1 Sistemas com monoprogramação monotarefa Possuem apenas uma unidade central de processamento ativa todo o tempo monoprocessamento mas pode ficar livre quando há operações de entradasaída Permitem a execução de apenas um processotarefa de cada vez por usuário monousuário ES processo 1 UCP processo 1 livre processo 1 2 Sistema com multiprogramação multitarefamultitasking Geralmente com uma unidade central de processamento ativa ao mesmo tempo Permitem a execução de dois ou mais processos tarefas concorrentemente multiprocessamento de um ou mais usuários multiusuário Realizam uma única tarefa de cada vez em termos de processamento ES processo 1 UCP processo 1 processo 2 processo1 21 Sistemas do tipo lote batch Neste sistema as tarefas atividades computacionais solicitadas de uma só vez por um usuário externo através de uma sequência de comandos são agrupadas fisicamente e processadas seqüencialmente Têm por objetivo maximizar o número de tarefas processadas por unidade de tempo e minimizar o tempo médio de espera para execução de cada tarefa 22 Sistemas de tempo compartilhado timesharing Neste sistema há várias tarefas ativas que devido ao tempo relativamente longo entre comandos think time são atendidas por intervalos de tempo definidos suspensas e colocadas à espera de um novo ciclo ou ao atendimento de prioridades Devem ter um tempo de resposta por comando dentro de limites aceitáveis 23 Sistemas de tempo real realtime Semelhantes ao de tempo repartido mas com um intervalo de tempo prefixado para a resposta após o qual poderá haver perda de informação ou operação incorreta e até catastrófica sobre o objeto monitorado 24 Smartcards embedded embutidos 3 Sistemas com múltiplos processadores Possuem mais de uma unidade central de processamento ativa ao mesmo tempo Podem atender vários usuários simultaneamente 31 Fracamente acoplados loosely coupled Sistemas interconectados de tempo uniforme SMP ou de tempo variável NUMA 32 Fortemente acoplados tightly coupled Sistemas interconectados em clusters em rede ou distribuídos nuvem 19 Modelo de memória com sistema operacional e espaço de trabalho O modelo abaixo procura situar uma possível localização relativa de elementos de um sistema operacional e o espaço de trabalho de um programa incluindo suas áreas de dados estáticos e dinâmicos bem como a área livre cujo uso poderá ser compartilhado por ambos Sobre essa área livre poderão atuar estruturas gerenciadoras de espaço chamadas de stack e heap Parte da memória poderá ser apenas para leitura de dados ROM e outra parte poderá servir para se escrever e ler dados RAM Quer sejam dados ou instruções as representações desses conteúdos serão feitas por valores em binário associados cada um a endereços A quantidade de bits usados nessas representações poderá variar de acordo com a arquitetura do sistema computacional Modelo de memória endereços conteúdo software Sistema operacional nnnn nnnn RAM Área de processos stack Área livre heap 0111 1111 0100 0000 0000 0000 0000 0000 Área de dados dinâmicos 0011 0000 0100 0010 programa Área de dados estáticos 0010 0000 0000 1111 Área de instruções 0001 0000 0000 0000 hardware Sistema básico de entradas e saídas 0000 0000 ROM Para o acionamento de módulos procedimentos e funções uma porção da área livre stack é usada para se guardar os contextos das chamadas os argumentos parâmetros e os resultados retornos das funções Acionamento de módulos Procedimento Função resultado retorno contexto contexto parâmetros argumento parâmetros argumento argumento argumento método dados locais função dados locais stack Área livre stack Área livre Para a alocação dinâmica uma porção da área livre heap é reservada para guardar dadosobjetos 20 Modelos de representações de dados na memória Exemplo de modelo físico de dados simples na memória endereço endereço memória representação interna valor hexadecimal binário 0x0C 0000 1100 0x0B 0000 1011 0x0A 0000 1010 1111 1111 byte max 0b1111 1111 max 255 0x09 0000 1001 0100 0001 literal símbolo 0x00 41 simbolo A 0x08 0000 1000 0000 0000 simbolo 0x08 endereço do símbolo 0x07 0000 0111 0000 0011 inteiro y 0x0000 000A y 10 0x06 0000 0110 0000 0000 0x05 0000 0101 0000 0000 0x04 0000 0100 0 000 0000 y 0b0000 0100 endereço de y 0x03 0000 0011 0000 0101 inteiro x 0x0000 0005 x 5 0x02 0000 0010 0000 0000 0x01 0000 0001 0000 0000 0x00 0000 0000 0 000 0000 x 0b0000 0000 endereço de x Exemplo de modelo físico de dados agrupados na memória endereço memória arranjo inteiro v3 binário 0000 1100 0000 1011 0000 0001 v2 1 0000 1010 0000 0000 0000 1001 0000 0000 endereço do indexado referência indexada 0000 1000 0 000 0000 v2 v02tamanhointeiro 24 bytes 0000 0111 0000 0011 v1 3 0000 0110 0000 0000 0000 0101 0000 0000 endereço do indexado referência indexada 0000 0100 0 000 0000 v1 v01tamanhointeiro 14 bytes 0000 0011 0000 0101 v0 5 0000 0010 0000 0000 0000 0001 0000 0000 endereço de base referência primária 0000 0000 0 000 0000 v0 0x00 Exemplo de modelo físico de objeto referência para outros dadosmétodos na memória endereço memória dados referência atributo 3 atributo 2 base dos atributos atributo 1 método 1 base dos métodos construtor padrão endereço base do descritor de métodos base do objeto endereço base do descritor de atributos 21 Exercícios propostos 1 O que significa endereçamento de memória 2 Para que serve um registrador 3 Quais os dois principais tipos de memória 4 Relacionar os itens abaixo a PROGRAMA unidade de informação b PALAVRA unidade de representação c BIT unidade de tratamento interno d DADO conjunto de instruções e BYTE conjunto de informações 5 Diferenciar compilador de interpretador 6 Qual o tamanho de uma memória com 16 bits de endereço 7 Qual a velocidade de processamento de um computador que trabalha a 2 GHz 8 Descrever o que acontece na fase de busca de instrução 9 Escrever um programa capaz de calcular 3 x 5 4 10 Citar as principais funções de sistemas operacionais 11 Relacionar pelo menos 03 sistemas operacionais atuais 12 Procurar definições para CONECTIVITY DOWSIZING OUTSOURCING RIGHTSIZING DBMS RESIZING LAN WAN TOPDOWN BOTTOMUP 21 Capítulo 2 Sistemas de Numeração Objetivos Fornecer o conceito de número e de base de sistema de numeração Mostrar os sistemas de numeração decimal binário octal e hexadecimal Mostrar técnicas para conversão de números em bases diferentes Mostrar as operações aritméticas básicas em outras bases Notação posicional e o sistema decimal Sistema decimal Base 10 Algarismos 0 1 2 3 4 5 6 7 8 9 Notação posicional O número da base não pode ser representado por um único algarismo Formase mediante uma combinação de outros algarismos disponíveis nesta base A regra básica de formação permite escrever qualquer valor utilizandose dos algarismos e de suas posições relativas às potências da base Exemplos 1986 1 10 9 10 8 10 6 10 3 2 1 0 x x x x ou em outra notação 3 0 10 1986 i i aix para a a a a 3 2 1 0 1 9 8 6 para valores com parte fracionária 01986 1 10 9 10 8 10 6 10 1 2 3 4 x x x x ou também em outra notação 01986 10 0 4 a x j j j para a a a a 1 2 3 4 1 9 8 6 Generalizando a notação para qualquer número N a xb a xb i i j j j q i p 1 0 22 ou de forma mais simplificada N a xb q Z q k k k q p 0 onde N uma quantidade qualquer p maior potência positiva na qual existe um algarismo significativo diferente de zero q menor potência negativa na qual existe um algarismo significativo diferente de zero a um algarismo qualquer 0b1 da base b b base de um sistema de numeração Com tal generalização é possível representar qualquer quantidade em qualquer base desde que conhecidos os algarismos e suas posições relativas à base Sistema binário Base 2 Algarismos 0 1 A partir da regra básica de formação podese escrever qualquer valor usando apenas os elementos desta base Qualquer número na base 10 pode ser representado por um equivalente na base 2 Exemplos 13 1 2 1 2 0 2 1 2 1101 10 3 2 1 0 2 x x x x 0 625 1 2 0 2 1 2 0101 10 1 2 3 2 x x x Observação Os números abaixo representam valores diferentes 1010 10 e 102 2 Exercício Escrever em notação posicional e o valor decimal a 11101012 b 0011012 c 1101012 d 0100102 e 1110012 23 Sistema octal Base 8 Algarismos 0 1 2 3 4 5 6 7 A partir da regra básica de formação podese escrever qualquer valor usando apenas os elementos desta base Exemplos 13 1 8 5 8 15 10 1 0 8 x x 0 625 5 8 0 5 10 1 8 x Sistema hexadecimal Base 16 Algarismos 0 1 2 3 4 5 6 7 8 9 A10B11C12D13E14F15 A partir da regra básica de formação podese escrever qualquer valor usando apenas os elementos desta base Exemplos 1986 7 16 16 2 16 7 2 2 1 0 x Cx x C 16 13 625 D A16 24 Conversão entre bases Conversão de base 10 para uma base b Parte inteira Dividir o número decimal pela base b tomando o resto e o quociente separadamente Continuar a dividir o quociente obtido pela base guardando os novos resto e quociente até que o quociente seja igual a zero 0 Tomar os restos na ordem inversa em que forem sendo calculados Exemplo Quociente Resto 13 2 6 1 06 2 3 0 03 2 1 1 01 2 0 1 1310 11012 13 2 1 6 2 0 3 2 1 1 2 1 0 1310 11012 dividir pela base guardar o resto quociente é zero tomar os restos na ordem inversa sim não fazer o dividendo igual ao quociente 25 Parte fracionária Multiplicar a parte fracionária do número decimal pela base b tomando apenas a parte inteira produzida Continuar o processo até obter apenas zeros na parte fracionária ou obter um número cuja representação esteja dentro de uma precisão aceitável Esta última condição atende ao fato de que alguns números terem como representação uma dízima Tomar as partes inteiras na ordem em que forem sendo calculadas Exemplo 03520 x 2 0 07040 07040 x 2 1 04080 04080 x 2 0 08160 08160 x 2 1 06320 06320 x 2 1 02640 Supondo uma aproximação razoável de 5 dígitos 0352010 0010112 multiplicar pela base guardar a parte inteira parte fracionária é zero tomar as partes inteiras em ordem sim não multiplicando igual à parte fracionária 26 Exercício Converter para os binários equivalentes a 1234 b 035 c 127 d 2525 e 103412 Conversão de uma base b para a base 10 Parte inteira Multiplicar o dígito mais a esquerda do número na base b pela própria base Somar o próximo dígito ao produto e continuar o processo até que o último dígito à direita seja somado O número decimal será o resultado destas operações Exemplo 11012 1310 0 1 x 2 2 2 1 x 2 6 6 0 x 2 12 12 1 13 ou 1 2 1 2 0 2 1 2 13 3 2 1 0 x x x x 10 multiplicar pela base guardar o total parte inteira acabou parar sim não somar o total com um dígito 27 Parte fracionária Multiplicar o dígito mais a direita do número na base b pelo inverso da própria base 1b Somar o próximo dígito à esquerda ao produto e continuar o processo até que o último dígito à esquerda seja somado e a soma multiplicada por 1b O número decimal será o resultado destas operações Exemplo Supondo uma precisão de 104 011012 0812510 0 1 x 12 05 05 1 x 12 025 025 0 x 12 0625 0625 1 08125 ou 1 2 1 2 0 2 1 2 0 8125 1 2 3 4 x x x x 10 Exercício Converter para os decimais equivalentes a 10101102 b 0011012 c 1101112 d 110010112 e 1100112 multiplicar pela base guardar o total parte fracionária acabou parar sim não somar o total com um dígito 28 Conversão de uma base b para uma base bn Parte inteira Agrupar os dígitos do número na base b em grupos de n dígitos a partir da direita completando com zeros à esquerda os dígitos que faltarem Converter cada um dos grupos para o algarismo correspondente na outra base Exemplo Converter o número 111110000012 para a base 4 01 11 11 00 00 012 1 3 3 0 0 14 Portanto 111110000012 1330014 Parte fracionária Agrupar os dígitos do número na base b em grupos de n dígitos a partir da vírgula completando com zeros à direita os dígitos que faltarem Converter cada um dos grupos para o algarismo correspondente na outra base Exemplo Converter o número 000110010112 para a base 8 001 100 101 1002 1 4 5 48 Portanto 000110010112 014548 Parte inteira e fracionária Agrupar os dígitos do número na base b em grupos de n dígitos completando com zeros os dígitos que faltarem tanto á esquerda quanto á direita Converter cada um dos grupos para o algarismo correspondente na outra base Exemplo Converter o número 1111100000100110010112 para a base 16 0111 1100 0001 0011 0010 11002 7 C12 1 3 2 C16 Portanto 11111000001001100101100 2 7C132C16 Exercício Fazer as conversões de base a 1021301224 para a base 8 b 1110101112 para a base 16 c 1221223204 para a base 16 d AB50F97C16 para a base 8 29 O quadro abaixo resume as primeiras representações equivalentes em cada base base 1016 23 22 21 20 base 0 0 0 0 0 1 0 0 0 1 2 2 0 0 1 0 3 0 0 1 1 4 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 8 1 0 0 0 9 1 0 0 1 10A 1 0 1 0 11B 1 0 1 1 12C 1 1 0 0 13D 1 1 0 1 14E 1 1 1 0 15F 1 1 1 1 16 Operações aritméticas em base 2 Soma e multiplicação 0 0 0 0 x 0 0 0 1 1 0 x 1 0 1 0 1 1 x 0 0 1 1 10 1 x 1 1 Exemplos vaium 111 111010 1010 101100 x 101 1100110 1010 0000 1010 110010 Exercício Efetuar as operações binárias a 1101010 101101 b 011011 00101 c 111101 x 101 d 10111 x 101 10101 e 10111 x 101 10101 30 Subtração A subtração binária é feita da mesma forma que a decimal lembrando que se o minuendo for menor que o subtraendo podese tomar uma unidade emprestada à casa seguinte se houver Exemplo 1011 0110 0101 11x2 vemum 101 1 10 1 1 1 0 11 010 11 010 11 011 0 01 1 0 0 1 10 0 1 10 0 1 10 1 0 1 01 1 01 0 1 01 Exercício Efetuar as subtrações binárias a 1001100 1111 b 011001 001 c 101011 111 Divisão A divisão pode ser feita com subtrações sucessivas Exemplo 1011010 10 10 101101 0011 10 010 10 0010 10 00 Exercício Efetuar as divisões binárias a 1101110 100 b 011011 011 c 111011 11 31 Representação de um número em ponto fixo A representação de qualquer símbolo em um computador digital é feita através de uma seqüência de dígitos 0 ou 1 Esta representação é ambígua servindo tanto para números como para letras ou outros sinais Além disso o tamanho desta seqüência é bastante limitado Tomando a representação de números em particular notase que não há uma forma padrão que indique o sinal pois outro símbolo não pode ser empregado Por isso desenvolveram se métodos para o tratamento de sinal em números binários Cada um deles toma por princípio que o número tenha uma representação com ponto fixo ou seja o ponto ou vírgula decimal tem uma posição bem definida e as operações têm que levála em consideração No caso desta posição ser a mais à direita os números serão quantidades inteiras positivas ou negativas Representação em sinal e amplitude Nessa representação o dígito mais à esquerda indica o sinal do número segundo a convenção abaixo 0 positivo 1 negativo Exemplo Representar os binários equivalentes aos valores 5 e 5 com 6 dígitos e tamanho fixo Sinal Amplitude 0 0 0 1 0 1 0 0 0 1 0 1 5 1 0 0 1 0 1 1 0 0 1 0 1 5 Observação O zero tem duas representações 0 00000 e 1 00000 Noção de complemento Considerase complemento de um número em relação a outro a diferença entre os dois É útil para aplicação em computadores Exemplo 1 O complemento de dez de 2 é 10 2 8 E a noção de complemento é aplicável à subtração 9 9 9 17 2 10 2 8 10 x 10 x 10 7 x Considerandose o que falta para completar 10 1710 o resultado é correto Exemplo 2 O complemento de dez de 9 é 10 9 1 Essa noção de complemento aplicada à operação 2 2 2 3 9 10 9 1 10 x 10 x 10 7 x Considerandose o que falta para completar 10 310 o resultado é correto Exemplo 3 O complemento de dez de 9 é 10 9 1 E aplicando novamente a noção de complemento 2 10 2 8 9 9 10 9 1 20 x 20 920 11 x Considerandose o que falta para completar cada complemento de 10 resultado é correto 32 Representação em complemento de 2 Seja m o tamanho fixo da representação e 2m um valor não representável nesse tamanho Os números positivos estarão no intervalo 02m1 1 ou seja todos os números entre zero e o maior valor capaz de ser representado sem contar com uma casa para o sinal Os números negativos estarão no intervalo 2m1 1 Sua representação será feita tomando o equivalente binário para o resultado da soma deste número com o valor máximo Exemplo Representar os binários equivalentes a 5 e 5 com 6 dígitos e tamanho fixo sinal amplitude 0 0 0 1 0 1 0 0 0 1 0 1 5 1 1 1 0 1 1 1 1 1 0 1 1 5 A representação de 5 é obtida por 26 5 64 5 5910 1 110112 Observação O zero tem representação única 0 00000 No entanto não existe simetria 2m1 tem representação mas 2m1 não Regra prática Para converter um número binário para a seu simétrico em complemento de 2 trocar todos os zeros por uns e uns por zeros acrescentando mais uma unidade ao resultado Exemplo 0 0 0 1 0 1 0 0 0 1 0 1 5 1 1 1 0 1 0 1 1 1 0 1 0 trocados 0s e 1s 1 1 1 0 1 1 1 1 1 0 1 1 5 Representação em complemento de 1 Seja m o tamanho fixo da representação e 2m um valor não representável nesse tamanho Os números positivos estarão no intervalo 02m1 1 ou seja todos os números entre zero e o maior valor capaz de ser representado sem contar com uma casa para o sinal Os números negativos estarão no intervalo 2m1 11 Sua representação será feita tomando o equivalente binário para o resultado da soma deste número com o valor máximo Exemplo Representar os binários equivalentes a 5 e 5 com 6 dígitos e tamanho fixo sinal amplitude 0 0 0 1 0 1 0 0 0 1 0 1 5 1 1 1 0 1 1 1 1 1 0 1 0 5 A representação de 5 é obtida por 26 1 5 63 5 5810 1 110102 Observação O valor zero terá duas representações 0 00000 e 1 11111 33 Regra prática Para converter um número binário para a seu simétrico em complemento de 1 trocar os zeros por uns e uns por zeros Exemplo 0 0 0 1 0 1 0 0 0 1 0 1 5 1 1 1 0 1 0 1 1 1 0 1 0 5 A subtração pode ser feita utilizandose a representação em complemento de 2 somando se o número e seu complemento e desprezandose o vaium na última casa se houver Exemplo 1 1 1 0 110 6 0 110 0 101 5 1 011 0 1115 1 011 complemento de 2 de 0 101 1 0 001 Exemplo 2 0 101 5 0 101 0 110 6 1 010 0 110 6 1 010 complemento de 2 de 0 110 1 111 Recorrendase usar a relação inversa do complemento de 2 subtraindo um do número trocando zeros por uns e viceversa 1 111 1 1 110 0 001 1 portanto 1 111 é representação de 1 o que também pode ser verificado assim 1 111 15 15 24 1 Exemplo 3 1 1 1 011 5 1 011 0 101 5 1 011 complemento de 2 de 0 101 0 010 2 1 110 0 010 2 1 110 complemento de 2 de 0 010 11 001 Recorrendase nesse caso usar a relação inversa do complemento de 2 1 001 1 1 000 0 111 7 portanto 1 001 é representação de 7 O que também pode ser verificado assim 1 001 9 9 24 7 34 Comparação entre as duas representações em complemento Exemplo Para um tamanho de representação igual a 4 em complemento de 2 temse que 3 5 00112 01012 00112 10112 3 11 Exemplo Supondo um tamanho de representação igual a 4 em complemento de 1 temse que 3 5 00112 01012 00112 10102 3 10 Corrigese a diferença acrescentandose mais um deslocamento o que também é feito no complemento de 2 adicionandose mais uma unidade 1000 07 8 0000 00 8 0010 02 8 0011 03 8 0100 04 8 0101 05 8 0110 06 8 0111 07 8 0001 01 8 1111 00 8 1110 01 8 1101 02 8 1100 03 8 1011 04 8 1010 05 8 1001 06 8 1000 08 8 0000 00 8 0010 02 8 0011 03 8 0100 04 8 0101 05 8 0110 06 8 0111 07 8 0001 01 8 1111 01 8 1110 02 1101 03 8 1100 04 8 1011 05 8 1010 06 8 1001 07 8 35 Exercício Efetuar as subtrações propostas anteriormente utilizando complemento de 2 É importante notar que a representação de um mesmo valor negativo varia de acordo com a quantidade de bits usados Exemplo 1 112 com 2 bits 1112 com 3 bits 11112 com 4 bits O diagrama abaixo ilustra essas diferentes representações 0000 000 00 10 100 1000 01 010 0100 01 01 11 110 1100 111 1110 1111 1101 36 Representação de um número em ponto flutuante A representação em ponto flutuante permite representar valores que dificilmente caberiam em notação de ponto fixo devido ao tamanho limitado da palavra do computador Entretanto ela também tem um número limitado de bits significativos Existem normas como ANSIIEEE 754854 19851987 que estabelecem o formato desta representação entretanto usaremos uma forma simplificada com 1em bits Sinal Expoente Mantissa S E M 1 e m N M S p 1 2 1 2 1 M p E e 2 1 o excesso de 2e1 e E 0 Exemplo 1 Dado o número 0 1010 1100000 com e 4 e m 7 determinar o valor representado N 2 01100000 2 0 75 30 1000 2 10 24 1 1010 Exemplo 2 Dado o número 170 com e 4 e m 7 representálo em ponto flutuante 170 2 p M o menor valor de p possível neste caso é 1 logo M 085 que pode ser aproximado com 7 casas por 011001102 e o expoente deve ser p E E 1 2 2 9 1 24 1 representado por 10012 assim a representação final será N 0 1001 11100112 Exemplo 3 Dado o número 1 0011 1100000 com e 4 e m 7 determinar o valor representado com três casas decimais N 2 01100000 2 0 75 0 023 0011 1000 2 3 24 1 Exemplo 4 Dado o número 025 representálo em ponto flutuante em sinal e amplitude 0 25 2 0 01 2 0 01 2 0 2 p M Mas esse valor não está de acordo com as especificações não está normalizado pois não pertence ao intervalo 12 1 e o expoente é nulo Se tomado o menor valor do intervalo M 010000002 05 o expoente deve ser p x x 1 2 2 7 1 24 1 representado por 01112 e o valor normalizado com o primeiro dígito mais à esquerda diferente de zero na mantissa para e 4 e m 7 será N 1 0111 1000000 37 O quadro abaixo resume as diferentes representações binárias de inteiros e expoentes base 1016 23 22 21 20 base x 1 x 2 x 3 x 4 2x 4 2x 3 2x 2 2x 1 e1 2 0 0 0 0 0 0 0 0 8 4 2 1 0 0 0 1 2 1 1 1 7 3 1 2 0 0 1 0 2 2 2 6 2 0 2 3 0 0 1 1 4 1 3 3 5 1 1 4 0 1 0 0 4 4 4 0 4 5 0 1 0 1 3 5 3 1 6 0 1 1 0 2 6 2 2 7 0 1 1 1 8 1 7 1 3 8 1 0 0 0 8 0 8 9 1 0 0 1 7 1 10A 1 0 1 0 6 2 11B 1 0 1 1 5 3 12C 1 1 0 0 4 4 13D 1 1 0 1 3 5 14E 1 1 1 0 2 6 15F 1 1 1 1 16 1 7 Os padrões ANSIIEEE754 e ANSIIEEE854 O padrão ANSIIEEE754 1985 estabelece representações para pontoflutuante bits formato bias precisão intervalo aproximado ano 16 1 4 11 15 meia 108 até 65504 1985 32 1 8 23 127 simples 1044 até 1038 1985 64 111 52 1023 dupla 10323 até 10308 1985 128 115112 16383 quádrupla 104965 até 104932 2008 256 119236 262143 óctupla 1078984 até 1078913 2008 Além disso aplicamse as seguintes regras sinal S expoente E mantissa M representação qualquer 255 ou 2047 zero NaN número inválido 1 255 ou 2047 zero Infinitiy infinito negativo 0 255 ou 2047 zero Infinitiy infinito positivo 1 0 zero 0 zero negativo 0 0 zero 0 zero qualquer 0 zero não normalizada 0 2 1 126 F N S qualquer no intervalo0255 zero normalizada 1 2 1 127 F N E S O padrão ANSIIEEE854 1987 é uma generalização que estabelece normas para as operações em pontoflutuante independente da base do sistema de numeração utilizada A última revisão do padrão ANSIIEEE ocorreu em 2019 para ajustes aritméticos 38 Erros em representação numérica As representações e as aritméticas de ponto fixo são convenientes para se tratar o conjunto dos números inteiros Z ou seja números sem parte fracionária dentro de certo intervalo de valores dependente do tamanho da representação m A representação e aritmética em ponto flutuante são convenientes para se tratar o conjunto dos números reais R ou seja números com parte fracionária dentro de certo intervalo de valores representáveis Durante as operações aritméticas devese manter o cuidado de se alinhar as vírgulas ajustandose as mantissas segundo os valores dos expoentes e realizar uma verificação extra do sinal dependendo da comparação de seus valores O resultado também poderá requerer normalização após ser calculado A dificuldade básica na representação numérica é que os valores deverão ser necessariamente armazenados em uma quantidade finita m de dígitos binários Isso significa que há uma limitação quanto ao número de representações distintas e que cada número representável deverá ter no máximo m dígitos significativos Assim poderão ocorrer vários tipos de erros relacionados com a representação Intervalo O número de dígitos significativos limita também o intervalo de valores representáveis tanto em ponto fixo como em ponto flutuante onde o expoente é o principal fator determinante Exemplo Dispondose de uma representação em complemento de 2 com tamanho m de 16 dígitos 1 para o sinal e 15 para a amplitude podese representar valores inteiros dentro do intervalo 215 215 1 32768 32767 Dispondose de uma representação em complemento de 2 com tamanho m de 4 bytes 11 dígitos decimais significativos podese representar valores reais no intervalo 1038 1038 Arredondamento e truncamento Tanto em ponto fixo como em ponto flutuante podem acontecer erros devido ao tamanho finito da representação Exemplo Para o valor representado em binário 087 011011110102 considerando uma representação com 8 dígitos 011011110 086718752 e precisão de 3 casas decimais 087 0867 truncamento 087 0867 0005 0872 arredondamento Mas para o valor representado em binário a 086 011011100002 considerando uma representação com 8 dígitos 0110111002 0859375 e precisão de 3 casas decimais 086 0859 truncamento 086 0859 0005 0864 arredondamento 39 Precisão A precisão está relacionada com o número de dígitos significativos No caso de números inteiros limitase aos m1 dígitos da palavra de representação no caso de números com parte fracionária limitase a 1m1 para representação em ponto fixo Exemplo Para o valor abaixo representado em binário 087 011011110102 considerando uma representação com apenas 8 dígitos 0110111102 08671875 a precisão será de 28 390625x103 Transbordamento Os erros de transbordamento ocorrem geralmente durante a utilização da representação numérica para fins aritméticos Exemplo Somar X e Y binários com representação em complemento de dois com seis dígitos 1 1 1 X 0 11111 31 Y 0 01100 12 1 01011 21 ERRADO O erro verificado devese a uma situação de transbordamento overflow em relação ao tamanho da representação Não há casas da amplitude suficientes para conter o resultado Por isso o vaium na casa do sinal ao invés de servir para corrigir o sinal do resultado passará a ser um dígito significativo fará parte da representação da quantidade O mesmo tipo de erro poderá ocorrer quando se operam números binários negativos 1 em complemento de dois X 1 00001 31 Y 1 10100 12 0 10101 21 ERRADO Na subtração poderá ocorrer erro semelhante devido à insuficiência ou falta underflow OVERFLOW negativo negativos possíveis UNDERFLOW negativo ZERO UNDERFLOW positivo positivos possíveis OVERFLOW positivo 2M 2m 0 2n 2N Nãoassociatividade É possível na aritmética computacional que para alguns valores não todos a b c a b c a x b x c a x b x c Poderão ocorrer erros de transbordamento por excesso overflow ou falta underflow Acumulação Para sequências de operações os erros de acumulação poderão ocorrer com grande rapidez anulandose ou não de forma imprevisível 40 Representação de letras e símbolos Para a representação de letras e outros símbolos utilizamse tabelas de equivalências onde cada letra ou símbolo corresponde a um código numérico Há vários códigos BCD Binary Coded Decimal EBCDIC Extended Binary Coded Decimal Interchange Code ASCII American Standard Code for Information Interchange UNICODE Por exemplo em ASCII tabela hexadecimal 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 A B C D E F G H I J K L M N O 1 P Q R S t U V W X Y Z 2 3 0 1 2 3 4 5 6 7 8 9 4 A B C D E F G H I J K L M N O 5 P Q R S T U V W X Y Z 6 a b c d e f g h I j k l m n o 7 p q r s t u v w x y z Nesse padrão temse hexadecimal decimal A S C I I 41 53 43 49 49 65 83 67 73 73 a s c i i 61 73 63 69 69 97 115 99 105 105 1 9 8 6 31 39 38 36 49 57 56 54 Observação importante Reparar que os símbolos que representam os algarismos têm em código ASCII valores diferentes de seus equivalentes binários por exemplo zero será representado por 3016 48 41 Exercícios propostos 1 Construir uma tabela de 0 a 15 nas bases 2 4 8 10 e 16 acrescentar a representação em complemento de 1 e 2 de cada número 2 Fazer as conversões de base a 13245 para a base 10 b 35738 para a base 16 c 895711 para a base 7 d 22013 para a base 9 e B8C013 para a base 14 3 Verificar a divisibilidade dos números abaixo a 0111 10002 por 4 b 31324 por 8 c 1608 por 16 d 1B9A16 por 2 4 Efetuar as operações abaixo a 24125 56278 b 0134 x 0112 c 1247 1145 d 1D4F16 81319 5 Efetuar as operações abaixo em binário a 1000102 111012 b 1010102 101102 c 11012 x 1012 d 1011002 1002 6 Efetuar as operações abaixo em binário a 1001102 110112 b 1010102 10112 c 11012 x 1012 d 1011002 1012 7 Resolver a equação abaixo em binário 1011102 100112 x 112 111002 X2 8 Resolver a equação abaixo 1011102 328 x A16 20134 X2 42 9 Representar em complemento de 2 os números binários abaixo a 0 1101 b 0 10110 c 0 111011 d 0 1001010 10Converter a representação em sinal e amplitude e em ponto flutuante abaixo para decimal 0 10101 1111001 11Converter o valor decimal abaixo para ponto flutuante em complemento de 2 com a menor representação 3025 12Converter o número decimal abaixo para ponto flutuante padrão IEEE754 3025 13 Representar o número abaixo em binário com precisão de 4 casas decimais 0374 14Qual a precisão decimal do número binário abaixo 1101110112 15Qual dos números abaixo apresenta a melhor precisão decimal a 14568 b 1010101112 c 1A1416 d 323314 16Decifrar a frase abaixo codificada em ASCII 4E616F206861207365677265646F20616C67756D2021 17Codificar em ASCII a expressão abaixo 123222 4 18Codificar em ASCII a frase abaixo O computador é uma máquina 19Identificar os símbolos contidos no seguinte padrão de bytes em código ASCII FE 81 80 80 8F 81 81 FF 20Codificar a letra F em um padrão de 8 x 8 bits equivalentes a pixels Pontifícia Universidade Católica de Minas Gerais 41 Capítulo 3 Álgebra de proposições Projetos de Circuitos Objetivos Apresentar os conceitos básicos da álgebra de proposições Mostrar as principais propriedades da álgebra de proposições Estudar expressões e circuitos lógicos Álgebra de proposições Em Matemática chamase proposição ao enunciado de uma verdade que se quer demonstrar ou como usaremos uma sentença que pode ser falsa 0 ou verdadeira 1 mas nunca ambos ao mesmo tempo Correspondência entre as principais relações e portas lógicas A conjunção determina que se duas proposições p e q forem verdadeiras 1 a conjunção de ambas também o será basta que uma delas seja falsa 0 para que a conjunção s também o seja A porta AND E implementa essa relação pode ter duas p q ou mais entradas e a saída s assumirá o valor 1 se e somente se todas as entradas forem iguais a 1 caso uma ou mais entradas sejam iguais a 0 a saída terá valor 0 A disjunção determina que se duas proposições p e q forem falsas 0 a disjunção de ambas s também o será basta que uma delas seja verdadeira 1 para que a disjunção também o seja A porta OR OU implementa essa relação pode ter duas p q ou mais entradas e a saída s assumirá o valor 0 se e somente se todas as entradas forem iguais a 0 caso uma ou mais entradas forem iguais a 1 a saída terá valor 1 A negação determina que se uma proposição p for falsa 0 a negação s será verdadeira 1 ou viceversa A porta NOT NÃO implementa essa relação é também chamada de INVERTER INVERSOR e só tem uma entrada p e a saída assumirá o valor 1 se a entrada for igual a 0 senão a saída terá valor 0 Analogias com circuitos elétricos O primeiro circuito a seguir conjunção determina que se duas chaves p e q forem fechadas 1 o resultado s será o de um circuito fechado com uma lâmpada acesa 1 por exemplo basta que uma delas seja aberta 0 para que o circuito se abra e a lâmpada apague 0 O circuito poderá ter duas p q ou mais chaves em série que a saída s terá o mesmo resultado 1 se e somente se todas as chaves forem fechadas 1 caso uma ou mais chaves forem abertas 0 o resultado será um circuito aberto com a lâmpada apagada 0 O segundo circuito a seguir disjunção determina que se duas chaves p e q forem abertas 0 o resultado s será o de um circuito aberto com uma lâmpada apagada 0 por exemplo basta que uma delas seja fechada 1 para que o circuito se feche O circuito poderá ter duas p q ou mais chaves em paralelo que a saída s terá o mesmo resultado 0 se e somente se todas as entradas forem abertas 0 caso uma ou mais chaves forem fechadas 1 o resultado será um circuito fechado coma lâmpada acesa 1 O terceiro circuito a seguir negação determina que se uma chave p for acionada 1 o resultado s será o de um circuito aberto com uma lâmpada apagada 0 caso contrário o circuito permanecerá fechado e a lâmpada se manterá acesa 1 Pontifícia Universidade Católica de Minas Gerais 42 Representações de circuitos Circuito série AND Circuito paralelo OR Curtocircuito NOT Conjunção Disjunção Negação Representações de relações lógicas Conjunção Disjunção Negação p e q p q p q ou p q p ou q p q p q não p p p ou p ou p p q s p q s p s 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 1 1 p p q p 1 0 q 1 1 0 1 1 1 1 Porta AND E Porta OR OU Porta NOT NÃO Diagramas de tempo para as portas lógicas 1 1 1 p 0 p 0 p 0 1 1 q 0 q 0 1 1 1 s 0 s 0 s 0 p s p q s p q s p q s p 1 q s s p q p s p q s p 1 s Pontifícia Universidade Católica de Minas Gerais 43 Prioridade de conectivos Estabelecese que a ordem de avaliação de uma expressão envolvendo conectivos lógicos será da esquerda para a direita respeitandose as prioridades dos conectivos na ordem mostrada abaixo sendo a primeira a mais alta quando aplicada imediatamente a um valor NÃO E OU Podese mudar a ordem de avaliação por meio de parênteses Exemplo Considere a expressão x y z A sua avaliação será feita na seguinte ordem de prioridade negação de y y conjunção com z y z disjunção com x y z x A expressão também poderá ser representada na forma tabular tabelaverdade x y z y y z y z x 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 A representação por um circuito lógico poderá ser a mostrada abaixo Se fosse desejado que a operação de disjunção ocorresse antes da conjunção seria necessário o uso de parênteses e o circuito seria diferente x y z Se fosse desejado negar toda a expressão também se usaria parênteses e essa ação seria a última a ser avaliada O circuito resultante seria o mesmo acima com mais um inversor x y z y z x s Pontifícia Universidade Católica de Minas Gerais 44 Exercício Construir tabela e circuito para as proposições a p q b p q c r p q d p q e p q f r r q p Principais propriedades Idempotência Comutativa Associativa p p p p q q p pqr pqr p p p p q q p pq r p qr Distributiva Absorção Identidade pqrpq pr p pq pq p0 p p0 0 pqrpqpr p p q p q p1 1 p1 p p p q p Complementar De Morgan p p 1 tautologia p q q p p p 0 contradição q p p q Observação As regras de absorção são aplicadas em geral para se efetuar simplificações normalmente ao se levar em conta a precedência de operadores a conjunção tem prioridade sobre a disjunção e as regras de absorção não se aplicam Exercício Simplificar pelas propriedades da álgebra a p q b p q c p q q p d p q p p q e p q p q f p q pq r Pontifícia Universidade Católica de Minas Gerais 45 Outras relações lógicas importantes É comum usar as negações das portas principais e definir outras relações lógicas Porta NOR Porta NAND Porta XNOR NEXOR Função de Peirce Função de Sheffer Equivalência Igualdade p q p y p q p y p q p xor y 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 Além delas também se pode definir p q pq p q p implica q p q pqqp p equivale a q 0 0 1 se p então q ou q se p ou 1 se p então q e se q então p ou 0 1 1 q dado p ou 0 q é condição necessária 1 0 0 p é condição suficiente para q ou 0 e suficiente para p 1 1 1 q é condição necessária para p 1 A prioridade dessas últimas relações normalmente é inferior às das anteriores Universalidade das portas NAND e NOR A universalidade das portas NAND e NOR permite que todas as funções lógicas básicas possam ser substituídas por composições equivalentes como se mostrará a seguir Porta NÃO NOT Porta NÃO NOT Porta NÃO NOT Porta AND Porta AND Porta AND Porta OR Porta OR Porta OR p q s p q s p q s p s p s p s p q s p q s p q s p q s p q s p q s Pontifícia Universidade Católica de Minas Gerais 46 Analogias com transistores CMOS Tipo P Tipo N NAND NOR NOT Projeto de circuitos lógicos A síntese de circuitos lógicos pode ser executada em cinco níveis Nível Atividades Sistema especificação de requisitos particionamento Algoritmo especificação de comportamento concorrência complexidade representação de dados Arquitetura representação de dados sinais e controle paralelismo e pipelining data paths Lógico circuitos otimizações em portas e transistores mapeamento em bibliotecas Físico otimização lógica planejamento de layout fabricação e encapsulamento G S D P 0 o G D S N 1 o o Vdd Gnd p q sab o o Vdd Gnd sab p q o Vdd Gnd p s Pontifícia Universidade Católica de Minas Gerais 47 Aplicações aritméticas de expressões e circuitos lógicos Dado o circuito lógico As relações abaixo descrevem os sinais de saída em função dos sinais de entrada s0 s2 s3 s2 s4 x y x y a s1 s4 x y b s2 x y s3 s4 s4 x y A partir das relações a e b podese construir a tabelaverdade x y xy s1xy xy s0xyxy 0 0 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 e os diagramas or árvores de decisão BDDs Binary Decision Diagrams s1 s1 compacto s0 s0 compacto x x x x 0 1 0 1 0 1 0 1 y y y y y y y 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 O resultado também poderá ser apresentado de outra forma x y s1 s0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 ou seja o circuito é o responsável por uma soma binária de dois dígitos binários bits e é chamado de circuito de meiasoma halfadderPara se operar três ou mais bits vários desses serão combinados em cascata para formar um circuito de somacompleta descrito mais adiante x y s4 s0 s1 s2 s3 Pontifícia Universidade Católica de Minas Gerais 48 A equação da saída s0 do circuito poderá ser simplificada pelas propriedades da álgebra x y x y Propriedades x y xy De Morgan xx yx xy yy Distributiva 0 yx xy 0 Complementar 0 yx xy 0 Associativa yx xy Identidade xy xy Comutativa A relação obtida também serve para descrever uma outra porta lógica OU exclusivo XOR cuja representação encontrase abaixo Porta OUexclusivo XOR Antivalência Diferença x y x y mintermos MAXTERMOS N 0 0 0 0 XY 0 0 1 1 xy 1 1 1 0 1 xy 1 2 1 1 0 0 X Y 3 Essa relação poderá ser definida por uma soma dos produtos SoP 0 xy xy 0 xy xy 2 1 ou definida por um produto das somas PoS XY11 XYXXXYYX YYXYYX 3 0 O circuito de meiasoma poderá ser refeito com a porta XOR O circuito de somacompleta fulladder para somar 3 bits também poderá ser feito com essa porta x y s x y s0 s1 s0 s1 x y vaium Pontifícia Universidade Católica de Minas Gerais 49 As relações expressas pelo circuito de somacompleta poderão ser encontradas abaixo vaium x y s1 s0 mintermos MAXTERMOS N 0 0 0 0 0 vxy V X Y 0 0 0 1 0 1 vxy V X Y 1 0 1 0 0 1 vx y V X Y 2 0 1 1 1 0 vx y V X Y 3 1 0 0 0 1 v xy V X Y 4 1 0 1 1 0 v xy V X Y 5 1 1 0 1 0 v x y V X Y 6 1 1 1 1 1 v x y V X Y 7 A relação s0 poderá ser definida por uma soma dos produtos SoP vxy vx y v xy v x y 4 7 2 1 ou definida por um produto das somas PoS V X Y V X Y V X Y V X Y 5 6 3 0 A relação s1 também poderá ser definida por uma soma dos produtos SoP vx y v xy v x y v x y 6 7 5 3 ou definida por um produto das somas PoS V X Y V X Y V X Y V X Y 2 4 1 0 O diagrama de blocos abaixo resume esse circuito soma completa vin x y soma vout Pontifícia Universidade Católica de Minas Gerais 50 A diferença entre dois bits também pode ser projetada de modo semelhante x y d v mintermos MAXTERMOS N 0 0 0 0 x y X Y 0 0 1 1 1 x y X Y 1 1 0 1 0 x y X Y 2 1 1 0 0 x y X Y 3 A diferença d poderá ser definida por uma soma dos produtos SoP xy xy 2 1 ou definida por um produto das somas PoS XY XY 3 0 A necessidade de empréstimo vemum poderá ser expressa pela relação xy v O circuito de meiadiferença halfdifference é mostrado a seguir O circuito de diferençacompleta xyempréstimo fulldifference terá a definição abaixo x y vemum s1 s0 mintermos MAXTERMOS N 0 0 0 0 0 xyv X Y V 0 0 0 1 1 1 xyv X Y V 1 0 1 0 1 1 xy v X Y V 2 0 1 1 1 0 xy v X Y V 3 1 0 0 0 1 x yv X Y V 4 1 0 1 0 0 x yv X Y V 5 1 1 0 0 0 x y v X Y V 6 1 1 1 1 1 x y v X Y V 7 A relação s0 também poderá ser definida pela soma dos produtos SoP xyv xy v x yv x y v 4 7 2 m 1 ou ainda definida pelo produto das somas PoS X Y V X Y V X Y V X Y V 5 6 3 M 0 x y d v Pontifícia Universidade Católica de Minas Gerais 51 A relação s1 poderá ser definida pela soma dos produtos SoP xyv xy v xy v x y v 3 7 2 m 1 ou definida por um produto das somas PoS X Y V X Y V X Y V X Y V 5 6 4 M 0 O circuito equivalente é mostrado abaixo O diagrama de blocos descrito a seguir resume esse circuito diferença completa vin x y diferença vout vemum y s0 s1 x y Pontifícia Universidade Católica de Minas Gerais 52 Equivalências em lógica exclusiva Axiomas Complementares Associativa p 0p p q p qp q p q rp q r p p0 p qpq p q p q pq p 1 p p q pq p q Comutativa p p 1 p q p q pq p qq p Complementares p q p q p p qpq p p q p q p q p q p pq p q p pq p q p q p q pp qpq p p q p q Exercício Verificar pelas equivalências em lógica exclusiva a p q p q p q p q b pq p q pq p q c pq p q p q p q A relação complementar à relação XOR é chamada XNOR ou também NEXOR e descreve uma outra porta lógica cuja representação encontrase abaixo Porta XNOR NEXOR x y x y 0 0 1 0 1 0 1 0 0 1 1 1 Porta XOR com NAND Porta XNOR com NAND Porta XOR com NOR Porta XNOR com NOR p q s p q s p q s p q s x y s Pontifícia Universidade Católica de Minas Gerais 53 Operações aritméticas em paralelo Um circuito para a adição de dois pares de bits poderia operar em paralelo Um circuito para a subtração de dois pares de bits também pode usar o esquema acima Entretanto se for desejado otimizar os recursos envolvidos a base do circuito de adição também poderá realizar a soma algébrica através da implementação da regra para a operação de soma utilizando o complemento de 2 Nesse caso a saída de cada bloco implementará a relação s x inverso y vaium para prover a soma adicional de uma unidade ao bit mais à direita bit0 a entrada em 0 do primeiro bloco à direita deverá alterada para 1 Esse valor poderá ser fornecido por uma linha adicional de controle sub que também servirá para tomar os inversos dos valores dos subtraendos yi os valores dos minuendos xi deverão ser tomados sem outras alterações O circuito abaixo ilustra essas modificações soma completa x0 y0 s0 0 vaium0 soma completa x1 y1 s1 vaium1 s2 s0 s1 s2 soma completa x0 y0 sub 1 v0 soma completa x1 y1 v1 Pontifícia Universidade Católica de Minas Gerais 54 Códigos de condição flags É conveniente observar que o circuito de soma algébrica anterior não considera as verificações de códigos de condições flags como a possibilidade de ocorrência de erro por transbordamento de representação overflow ocorrência de resultado nulo zero flag e vaium carry flag A situação de transbordamento overflow por exemplo poderá ocorrer na adição quando os bits mais significativos MSB dos operandos x y forem ambos iguais a 0 e o do resultado s for 1 na subtração quando o bit mais significativo MSB do primeiro operando x for positivo o do segundo operando y for negativo e o do resultado s também for negativo A tabela abaixo resume algumas das condições para ocorrência de transbordamento overflow xMSB yMSB operação sMSB overflow 0 0 0 soma 1 1 0 1 1subtração 1 1 O circuito mostrado abaixo implementa essas condições para verificação de overflow A ocorrência de resultado nulo zero flag possui várias aplicações práticas como a verificação de testes ou o controle de repetições Para implementar essa verificação basta testar se todos os bits do resultado são iguais a zero como indicado no circuito abaixo xMSB overflow op yMSB sMSB s0 zero s1 s2 Pontifícia Universidade Católica de Minas Gerais 55 Simplificação por agregação de produtos adjacentes mapas de VeitchKarnaugh Expressões do tipo XYXY podem ser simplificadas pelos mapas de VeitchKarnaugh abcd 00 01 11 10 ab 0 1 abc 00 01 11 10 00 abcd abcd abc d abc d 0 ab ab 0 abc abc ab c ab c 01 ab cd ab cd a b c d ab c d 1 a b a b 1 a bc a bc a b c a b c 11 a b cd a b cd a b c d a b c d 10 a bcd a bcd a bc d a bc d 2 variáveis 3 variáveis 4 variáveis Exemplo 1 Simplificar a expressão abaixo s1 abab s2 aba b ab 0 1 ab 0 1 0 1 1 s1 abb a 0 1 0 s2 baa b 1 0 0 1 1 0 Exemplo 2 Simplificar as expressões abaixo s21 abcabcab ca b c abc 00 01 11 10 0 1 1 0 1 s21 abccb caa abb c 1 0 0 0 1 s22 abc abca bca bcab ca b c abc 00 01 11 10 0 1 1 0 1 s22 abcca bccb caa 1 1 1 0 1 aba bb c baab c bb c Exemplo 3 Simplificar as expressões abaixo s31 abcdabc da bcda bc d abcd 00 01 11 10 00 1 0 0 1 s31 cdaba bc daba b 01 0 0 0 0 cdc dbaa 11 0 0 0 0 dccb 10 1 0 0 1 db bd s32 abc dab cdab c da b c da bc d abcd 00 01 11 10 00 0 0 0 1 s32 c dababa ba bab cd 01 1 0 0 1 c dabbabbab cd 11 0 0 0 1 c daaab cd c dab cd 10 0 0 0 1 dc ab c dcab c dab d s33 ab cdab c da b cda b c d abcd 00 01 11 10 00 0 0 0 0 s33 b cdaab c daa 01 0 1 1 0 b c db c d 11 0 1 1 0 b dcc 10 0 0 0 0 b d Pontifícia Universidade Católica de Minas Gerais 56 Resumo dos mapas de VeitchKarnaugh dependendo do número de variáveis ab 0 1 0 00 01 1 02 03 2 variáveis abc 00 01 11 10 00 00 01 03 02 01 04 05 07 06 3 variáveis abcd 00 01 11 10 00 00 01 03 02 01 04 05 07 06 11 12 13 15 14 10 08 09 11 10 4 variáveis abcde 000 001 011 010 110 111 101 100 00 00 01 03 02 06 07 05 04 01 08 09 11 10 14 15 13 12 11 24 25 27 26 30 31 29 28 10 16 17 19 18 22 23 21 20 5 variáveis abcdef 000 001 011 010 110 111 101 100 000 00 01 03 02 06 07 05 04 001 08 09 11 10 14 15 13 12 011 24 25 27 26 30 31 29 28 010 16 17 19 18 22 23 21 20 110 48 49 51 50 54 55 53 52 111 56 57 59 58 62 63 61 60 101 40 41 43 42 46 47 45 44 100 32 33 35 34 38 39 37 36 6 variáveis Pontifícia Universidade Católica de Minas Gerais 57 Simplificação pela lógica de ReedMüller Expressões do tipo XYXY podem ser simplificadas pela lógica de ReedMüller Exemplo 1 Simplificar a configuração abaixo ab 00 01 11 10 0 1 0 1 s01 aba b a xor b De outro modo trocando as colunas ab 00 01 10 11 0 1 1 0 s01 aba b a xor b Exemplo 2 Simplificar a configuração abaixo cab 00 01 11 10 0 0 1 0 1 s21 ab c a b c ab c a b c 1 1 0 1 0 a xor b xor c De outro modo trocando as colunas cab 00 01 10 11 0 1 1 0 s21 ab ca b cab ca b c 1 0 0 1 a xor b c a xnor b c a xor b xor c Exemplo 3 Simplificar a configuração abaixo cdab 00 01 11 10 00 0 1 0 1 s32 ab cda bcd abcd a b cd 01 1 0 1 0 ab c d a bc d abc da b c d 11 0 1 0 1 a xor b xor c xor d 10 1 0 1 0 De outro modo trocando as colunas e as linhas11 e 10 cdab 00 01 10 11 00 0 1 1 0 s32 aba bcd aba bc d 01 1 0 0 1 abcdc d a bcdc d 10 1 0 0 1 a xor bcdc d c xor daba b 11 0 1 1 0 a xor bc xnor d c xor da xnor b a xor b xor c xor d Pontifícia Universidade Católica de Minas Gerais 58 Exemplo 4 Simplificar a configuração abaixo cdab 00 01 11 10 00 0 1 0 1 S42 ab cda bcd ab cd a bcd 01 0 1 0 1 ab c d a bc d abc da bc d 11 0 1 0 1 a xor b 10 0 1 0 1 De outro modo trocando as colunas e as linhas11 e 10 cdab 00 01 10 11 00 0 1 1 0 s42 aba b 01 0 1 1 0 a xor b 10 0 1 1 0 11 0 1 1 0 Exemplo 5 Simplificar a configuração abaixo cdab 00 01 11 10 00 0 0 1 1 s52 a b cda bcd a b cd a bcd 01 0 0 1 1 abc d ab c d abc dab c d 11 1 1 0 0 a xor c 10 1 1 0 0 De outro modo trocando as colunas e as linhas11 e 10 cdab 00 01 10 11 00 0 0 1 1 s52 a cac 01 0 0 1 1 a xor c 10 1 1 0 0 11 1 1 0 0 Exemplo 6 Simplificar a configuração abaixo cdab 00 01 11 10 00 0 1 0 1 s62 ab cda bcd ab cd a bcd 01 0 1 0 1 abc d a b c d abc da b c d 11 1 0 1 0 a xor b xor c 10 1 0 1 0 De outro modo trocando as colunas e as linhas11 e 10 cdab 00 01 10 11 00 0 1 1 0 s62 a xor b c a xnor b c 01 0 1 1 0 a xor b xor c 10 1 0 0 1 11 1 0 0 1 Pontifícia Universidade Católica de Minas Gerais 59 Simplificação pelo método de QuineMcCluskey Mapas de VeitchKarnaugh podem ser aplicados para até 5 ou 6 variáveis mas para um número maior outros métodos deverão ser aplicados Um método que pode ser implementado de maneira sistemática é o de QuineMcCluskey o qual pode ser resumido pelos seguintes passos produzir uma expansão de uma função na forma de soma de produtos SoP reduzir ao máximo os termos do tipo XYXY identificar um conjunto mínimo de fatores primos implicantes equivalente à função Exemplo Dada a função abaixo identificar um conjunto de fatores primos implicantes f a b c d 9 10 14 8 7 6 5 2 1 m 0 1º passo Identificar os grupos que possuem a mesma quantidade de 1s N a b c d f abcd Termos N Grupos 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 bit em 1 1 0 0 0 1 1 0 0 0 1 2 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 bit em 1 3 0 0 1 1 0 2 0 0 1 0 4 0 1 0 0 0 8 1 0 0 0 5 0 1 0 1 1 0 1 0 1 6 0 1 1 0 1 0 1 1 0 5 0 1 0 1 2 bits em 1 7 0 1 1 1 1 0 1 1 1 6 0 1 1 0 8 1 0 0 0 1 1 0 0 0 9 1 0 0 1 9 1 0 0 1 1 1 0 0 1 10 1 0 1 0 10 1 0 1 0 1 1 0 1 0 11 1 0 1 1 0 7 0 1 1 1 3 bits em 1 12 1 1 0 0 0 14 0 1 1 1 13 1 1 0 1 0 14 1 1 1 0 1 1 1 1 0 15 1 1 1 1 0 2º passo Agrupar os termos com os mesmos bits de diferença N Grupos Grupos I 1 bit Grupos II 2 bits OBS 0 0 0 0 0 0 1 0 0 0 X 0 1 8 9 X 0 0 X 0 2 0 0 X 0 0 2 8 10 X 0 X 0 1 0 0 0 1 0 8 X 0 0 0 0 8 1 9 repetido 2 0 0 1 0 0 8 2 10 repetido 8 1 0 0 0 1 5 0 X 0 1 1 9 X 0 0 1 2 6 10 14 X X 1 0 5 0 1 0 1 2 6 0 X 1 0 2 10 6 14 repetido 6 0 1 1 0 2 10 X 0 1 0 9 1 0 0 1 8 9 1 0 0 X 10 1 0 1 0 8 10 1 0 X 0 7 0 1 1 1 5 7 0 1 X 1 14 1 1 1 0 6 7 0 1 1 X 6 14 X 1 1 0 10 14 1 X 1 0 Pontifícia Universidade Católica de Minas Gerais 60 3º passo Agrupar Identificar os termos não utilizados em algum agrupamento f a b c d 15 57 67 0189 02810 261014 acd ab d a b c bc bd c d 4º passo Montar a tabela de primos implicantes não cobertos por outros termos primos mintermos 0 1 2 5 6 7 8 9 10 14 0 1 8 9 b c X X X X 0 2 8 10 b d X X X X 2 6 10 14 c d X X X X 1 5 a c d X X 5 7 a b d X X 6 7 a b c X X 5º passo Identificar os mintermos cobertos por apenas um único conjunto de primos primos mintermos 0 1 2 5 6 7 8 9 10 14 0 1 8 9 b c X X X X 0 2 8 10 b d X X X X 2 6 10 14 c d X X X X 1 5 a c d X X 5 7 a b d X X 6 7 a b c X X Há dois mintermos essenciais que satisfazem a condição bc e c d e por isso devem estar presentes na resposta f abcd bc c d 6º passo Eliminar todos os termos redundantes cobertos por esses primos mintermos 0 1 2 5 6 7 8 9 10 14 0 1 8 9 b c X X X X 0 2 8 10 b d X X X X 2 6 10 14 c d X X X X 1 5 a c d X X 5 7 a b d X X 6 7 a b c X X 7º passo Escolher outros mintermos que possam eliminar redundâncias primos mintermos 0 1 2 5 6 7 8 9 10 14 0 1 8 9 b c 0 2 8 10 b d 2 6 10 14 c d 1 5 a c d X 5 7 a b d X X 6 7 a b c X A função equivalente será dada por f abcd bc c d a b d Um inconveniente deve ser indicado devido ao crescimento exponencial do número de combinações a solução encontrada pelo método de QuineMcCluskey pode não ser única Pontifícia Universidade Católica de Minas Gerais 61 Uma maneira de demonstrar a afirmação anterior é aplicando o método de Petrick 1º passo Eliminar as linhas com os mintermos essenciais e colunas correspondentes primos mintermos 0 1 2 5 6 7 8 9 10 14 0 1 8 9 b c X X X X 0 2 8 10 b d X X X X 2 6 10 14 c d X X X X 1 5 a c d X X 5 7 a b d X X 6 7 a b c X X 2º passo Rotular as linhas restantes primos mintermos 0 1 2 5 6 7 8 9 10 14 1 5 a c d K X 5 7 a b d L X X 6 7 a b c M X 3º passo Construir a soma de produtos das linhas adicionando as colunas K L L M 4º passo Simplificar a soma de produtos X XY X KL LL KM LM KL L KM LM L KM 5º passo Escolher as soluções com as menores quantidades de termos L KM L 6º passo Expandir a solução e contar o número de variáveis L a b d 3 termos 7º passo Escolher as soluções com as menores quantidades de variáveis L a b d Após a escolha montar a função equivalente final com todos os termos selecionados f abcd a b d bc c d Pontifícia Universidade Católica de Minas Gerais 61 Codificadores e decodificadores Sequências de bits podem ser usadas para codificar valores numéricos Dois códigos binários têm aplicações especiais o BCD BinaryCoded Decimal e o de Gray Código BCD O código BCD é basicamente uma forma de codificar valores numéricos na base 10 em seus equivalentes binários Decimal BCD 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 Exemplo Codificar o valor decimal 369 em código BCD 369 0011 0110 1001 Um circuito codificador decimalparaBCD é aquele capaz de mapear um conjunto de entradas 09 em um outro conjunto de quatro valores binários s3s2s1s0 se apenas uma das entradas for acionada 0 s1 s0 s2 s3 1 2 3 4 5 6 7 8 9 Pontifícia Universidade Católica de Minas Gerais 62 Código de Gray O código de Gray serve para expressar sequências binárias nas quais dois valores sucessivos tenham apenas um bit de diferença distância de Hamming 1 Decimal Binário Gray 0 000 000 1 001 001 2 010 011 3 011 010 4 100 110 5 101 111 6 110 101 7 111 100 Esse código também é conhecido com código binário refletido por causa da característica abaixo 000 001 00 011 0 01 010 1 11 110 10 111 101 100 eixo de reflexão Pontifícia Universidade Católica de Minas Gerais 63 Decodificadores em geral são circuitos lógicos capazes de ativar uma saída de acordo com uma seleção de sinais de entrada Um decodificador de nível alto ativa uma saída quando uma das entradas estiver em nível 1 e as outras em nível 0 Exemplo Montar um decodificador em nível alto para a tabela abaixo e1 e0 s3 s2 s1 s0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 Um decodificador de nível baixo ativa uma saída quando uma das entradas estiver em nível 0 e as outras em nível 1 Exemplo Montar um decodificador em nível baixo para a tabela abaixo e1 e0 s3 s2 s1 s0 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 e1 e0 s3 s2 s1 s0 e1 e0 s3 s2 s1 s0 Pontifícia Universidade Católica de Minas Gerais 64 Multiplexadores MUX e demultiplexadores DEMUX Multiplexadores ou seletores de dados são circuitos lógicos capazes de atuar como chaves digitais recebem várias entradas e selecionam uma delas em certo instante e realizam sua transferência para a saída mediante um código de seleção Podem ser usados para rotear dados sequenciar operações realizar conversões do tipo paralelosérie e gerar tabelas ou formas de ondas Exemplo Dados os sinais de entrada x e y escolher a saída mediante um sinal de seleção e s x e y e 0 y 1 x Multiplexadores podem selecionar mais sinais dependendo do número de bits tamanho da chave de seleção Exemplo Dados os sinais de entrada xyvw escolher a saída mediante um sinal de seleção e1 e0 s xe1e0 ye1e0 ve1e0 we1e0 0 0 x 0 1 y 1 0 v 1 1 w e w e1 e0 s v y x x y s Pontifícia Universidade Católica de Minas Gerais 65 Demultiplexadores ou distribuidores de dados são circuitos capazes de receber um sinal de entrada e distribuílo em uma dentre várias saídas segundo um código de seleção Podem ser usados para distribuir um mesmo sinal de ativação ou sequenciamento clock para vários circuitos Exemplo Dados um sinal de entrada x e dois sinais de ativação e0 e e1 distribuílo à saída e1 e0 e1 e0 x s3 s2 s1 s0 0 0 s3 0 0 X X 0 0 0 0 1 s2 0 1 X 0 X 0 0 1 0 s1 1 0 X 0 0 X 0 1 1 s0 1 1 X 0 0 0 X x e1 e0 s3 s2 s1 s0 Pontifícia Universidade Católica de Minas Gerais 66 Dispositivos lógicos programáveis PLDs Programmable Logic Devices ou FPGAs Field Programmable Gate Arrays são arranjos de portas lógicas que servem para uma rápida implementação de circuitos razoavelmente complexos A figura abaixo ilustra uma organização de um arranjo de portas AND e OR Há três tipos comuns de arranjos lógicos combinacionais PLA Programmable Logic Array ANDs e ORs programáveis ROM ReadOnly Memory ANDs fixas e ORs programáveis PAL Programmable Array Logic ANDs programáveis e ORs fixas PLA a3 xy a2 xy a1 x y a0 x y x b3 xy x y y b0 xy x y a3 a2 a1 a0 e1 e1 b3 b2 e0 e0 b1 b0 Pontifícia Universidade Católica de Minas Gerais 67 a3 a2 a1 a0 a3 xy a2 xy a1 x y a0 x y x b3 y b0 ROM x y b1 b2 b3 b0 PAL b1 b2 Pontifícia Universidade Católica de Minas Gerais 68 Circuitos com chaveamento As portas lógicas básicas podem ser usadas para controlar a passagem chavear de um sinal de entrada p para a saída se a outra entrada q for usada como o controle chave desabilitada 1 habilitada 0 1 chave 0 0 chave 1 habilitada 1 desabilitada 0 1 chave 0 0 chave 1 desabilitada 1 habilitada 0 1 chave 0 0 chave 1 habilitada 1 desabilitada 0 1 chave 0 0 chave 1 Exemplo Montar um circuito direcionador de pulsos envia um pulso de entrada p para uma saída ou outra dependendo de uma chave de controle q pulso saída 1 1 1 0 0 1 1 0 0 chave saída 2 p q s p q s p q s p q s p q s p q s p q s p q s s2 s1 Pontifícia Universidade Católica de Minas Gerais 69 Circuitos sequenciais Um circuito combinacional é aquele em que as saídas dependem de uma combinação das entradas Um circuito sequencial além de uma combinação das entradas depende de uma combinação de outras variáveis que definem o estado em que o sistema se encontrava Isto significa que um sistema deverá ter memória para passar ao próximo estado precisará guardar informações sobre o estado atual Basicamente há dois tipos de circuitos sequenciais assíncronos em que os estados podem mudar a qualquer instante síncronos em que os estados mudam em instantes bem determinados As mudanças de estados que ocorrerão em instantes determinados serão orientadas por um sinal de temporização clock Se ocorrerem as transições ocorrerem durante uma variação de 0 para 1 borda de subida o sistema será dito de nível alto caso contrário durante uma variação de 1 para 0 borda de descida o sistema será dito de nível baixo As especificações de tempo para circuitos sequenciais também incluirão o tempo para a transição se estabilizar setup time e o tempo após a transição em que o sinal deve se mantiver constante hold time 1 setup time 1 clock 0 0 ideal hold time 1 clock 0 real variáveis de entrada variáveis de saída circuito sequencial x1 xn z1 zm realimentação realimentação estados atuais próximos estados memória variáveis de entrada variáveis de saída circuito sequencial x1 xn z1 zm y1t yk t y1 t1 yk t1 z g x y yi t1 h x yi t variáveis de entrada variáveis de saída circuito combinacional x1 xn z1 zm z f x Pontifícia Universidade Católica de Minas Gerais 70 Máquinas de estados finitos Finite State Machines Uma máquina de estados finitos ou simplesmente autômato finito é um modelo de comportamento composto de estados transições e ações Um estado armazena uma informação sobre a história de um sistema reflete como as mudanças nas entradas trouxeram o sistema até o estado atual Uma transição indica uma mudança de estado e é descrita por uma condição que a permite Uma ação é a descrição de uma atividade executada em certo instante Máquinas de estados finitos podem ser usadas para descrever circuitos sequenciais pois suas saídas e seus novos estados são funções de suas entradas e de seus estados atuais Diagrama de estados Tabela de estados entrada x estado atual y yt1z Os modelos de Mealy e Moore são comumente usados para descrever máquinas de estados finitos Se a saída for função apenas do estado o modelo de Moore é melhor empregado Caso a saída seja função do estado da máquina e de suas entradas então o modelo de Mealy é melhor empregado Na prática esses dois modelos são combinados para oferecer uma descrição do funcionamento de uma máquina de estados finitos condições de saída condições de transição estados entradas saídas Modelo de Mealy Modelo de Moore xz yt yt1 Pontifícia Universidade Católica de Minas Gerais 71 Exemplo Considerar um circuito capaz de identificar a sequência binária abcd1101 Modelo de Mealy Tabela de Estados estado entradas x atual código nome y x0 x1 0 0 início início s0 id1 s0 0 1 id1 início s0 id11 s0 1 0 id11 id110 s0 id11 s0 1 1 id110 início s0 id1 s1 Diagrama de estados Mealy Modelo de Moore Tabela de Estados estado entradas x atual código nome y x0 x1 0 0 0 início início s0 id1 s0 0 0 1 id1 início s0 id11 s0 0 1 0 id11 id110 s0 id11 s0 0 1 1 id110 início s0 id1101 s0 1 0 0 id1101 início s0 id1 s1 Diagrama de estados Moore 000 001 010 011 10 10 00 encontrado 11 01 encontrado 100 00 10 10 00 10 00 01 10 11 10 10 00 encontrado 11 00 não encontrado 00 10 00 Pontifícia Universidade Católica de Minas Gerais 72 Latches Um latch é uma estrutura lógica capaz de armazenar um bit Constituise de um circuito que muda de estado apenas devido às variações das entradas Os latches são geralmente empregados para se construir chaveadores sem ressaltos debounced Os ressaltos são variações de natureza oscilatória que podem ocorrer durante uma transição e poderão ser interpretados erroneamente por um circuito 1 clock 0 real O esquema abaixo ilustra a composição de um latch implementado com dois inversores Se for imposto que a saída Q tenha valor igual a 1 o seu complemento Q terá valor igual a 0 Caso contrário se Q for igual a 0 então Q será igual a 1 Dessa forma uma unidade mínima de informação bit poderá ser guardada Um latch constitui um elemento básico de memória e opera enquanto determinado nível de sinal 0 ou 1 for mantido De modo geral um elemento de memória pode ser descrito como um circuito capaz de receber escrita armazenar um valor binário e fornecer cópia leitura do valor armazenado Construção de um latch do tipo setreset Com porta OR Substituindo por porta NOR Q Q entrada escrever saída ler memória armazenar habilitação 0 0 S0 Q realimentação início 1 S1 1 Q set 1 S0 1 Q hold reset set hold 0 0 0 1 R 0 Q Q 0 1 0 S 0 Q Q 1 0 1 R 1 Q Q 0 1 Pontifícia Universidade Católica de Minas Gerais 73 No mapa de Karnaugh set S 0 SQ 1Q Q Q S R 0 0 0 1 1 1 1 0 R 0 QQ 1Q Q 0 0 0 X 1 S0R1 Q SQ 01 0 1 1 0 X 1 S1R0 Q RQ 01 0 0 0 0 1 1 1 1 0 S 1 SQ 0Q 1 reset R 1 QQ 0Q 1 Na tabela de estados S R Qt Qt1 0 0 0 0 hold 0 0 1 1 0 1 0 0 reset 0 1 1 0 1 0 0 1 set 1 0 1 1 1 1 0 X unused 1 1 1 X Latch SR Um latch SR SetReset pode ser construído com portas NOR Latch SR com NORs Tabela característica S R Qt1 Qt1 Obs 0 0 Qt Qt hold 0 1 0 1 reset 1 0 1 0 set 1 1 unused X Qt1 S R Qt Equação característica Um latch SR SetReset também pode ser construído com portas NAND Latch SR com NANDs Tabela característica S R Qt1 Qt1 Obs 0 0 unused X 0 1 1 0 set 1 0 0 1 reset 1 1 Qt Qt hold Qt1 S R Qt Equação característica Q Q S R Q Q S R Tecnica para transformar tabelaverdade em expressao logica Pontifícia Universidade Católica de Minas Gerais 74 Um problema que pode ser observado pelas tabelas é a indicação de estado indefinido não utilizado ou X Uma tentativa de solução é o acréscimo de uma entrada de controle habilitação cujo objetivo é tentar evitar que valores das entradas S e R possam levar ao estado não definido X Latch SR com habilitação Tabela característica C S R Qt1 Qt1 Obs 0 X X Qt Qt no change 1 0 0 Qt Qt hold 1 0 1 0 1 reset 1 1 0 1 0 set 1 1 1 X X unused X A representação genérica do latch SR com habilitação pode ser a mostrada abaixo O latch SR também pode ser construído com mais duas entradas assíncronas uma para estabelecer certo valor inicial PReset e outra para limpar CLear o conteúdo armazenado Latch SR com entradas assíncronas Tabela característica PR CL C S R Qt1 Qt1 Obs 0 0 X X X X 0 1 0 X X 1 0 set 1 0 0 X X 0 1 reset 1 1 0 X X Qt Qt hold 0 1 1 0 1 X 1 0 1 1 0 X 1 1 1 0 0 Qt Qt hold 1 1 1 0 1 0 1 reset 1 1 1 1 0 1 0 set 1 1 1 1 1 X A configuração com habilitação tem como vantagem não necessitar de uma configuração especial dos sinais S e R para manter o estado anterior Contudo ainda há desvantagem a existência de um estado não utilizado O circuito a seguir procura resolver esse problema vinculando as entradas S Q R Q habilitação Enable Q Q S R C PR CL Q Q S R C Pontifícia Universidade Católica de Minas Gerais 75 Latch tipo D Um latch tipo D mantém a vantagem de manter o estado atual hold mesmo que desabilitado além disso é capaz de impedir a ocorrência do estado inválido por vincular as entradas S e R em uma única D e sua inversão Latch tipo D Tabela característica C D Qt1 Qt1 Obs 0 X Qt Qt hold 1 0 0 1 reset 1 1 1 0 set Há entretanto uma desvantagem se o sinal de controle for mantido em 1 e o sinal de entrada flutuar as saídas também o farão O latch tipo D não oferece estabilidade A representação genérica do latch tipo D pode ser a mostrada abaixo Q D Q habilitação Enable Q Q D C Pontifícia Universidade Católica de Minas Gerais 76 Flipflops Flipflop é um elemento de memória cujas atualizações de estado ocorrem somente durante as transições positivasubida ou negativadescida de um sinal de temporização clock Isso permite que os sinais possam ter pequenas variações arbitrárias sem que isto possa afetar seus estados Dessa forma é possível ditar com maior precisão o momento em que os dados poderão ser armazenados no dispositivo A detecção de variação de borda do pulso é normalmente associada ao sinal de habilitação Flipflop SR A representação genérica do flipflop SR com clock CLK pode ser a mostrada abaixo Flipflop tipo SR Tabela característica Tabela de transição Equação característica Qt1 S R Qt SR 0 S R Qt1 Qt1 Obs Qt Qt1 S R 0 0 Qt Qt hold 0 0 0 X 0 1 0 1 reset 0 1 1 0 1 0 1 0 set 1 0 0 1 1 1 unused 1 1 X 0 O diagrama de estados do flipflop SR está mostrado abaixo Diagrama de estados do flipflop SR Carta de tempo 1 CLK 0 1 S 0 1 R 0 1 Q 0 1 Q 0 Obs Carta de tempo obtida com flipflop sensível à borda de descida sem atraso lag 0 1 10 01 00 10 00 01 S Q R Q CLK Pontifícia Universidade Católica de Minas Gerais 77 Flipflop D A representação genérica do flipflop tipo D com clock pode ser a mostrada abaixo Flipflop tipo D Tabela característica Tabela de transição Equação característica Qt1 D Qt Qt1 D D Qt1 Qt1 Obs 0 0 0 0 0 1 reset 0 1 1 1 1 0 set 1 0 0 1 1 1 O diagrama de estados do flipflop tipo D está mostrado abaixo Diagrama de estados do flipflop tipo D Carta de tempo 1 CLK 0 1 D 0 1 Q 0 1 Q 0 Obs Carta de tempo obtida com flipflop sensível à borda de subida sem atraso lag 0 1 1 0 1 0 Q D Q CLK Pontifícia Universidade Católica de Minas Gerais 78 Flipflop T toggle O flipflop tipo T é um circuito com apenas uma entrada Toda vez que a entrada for igual a 1 ou seja quando houver variação de clock de 0 para 1 as saídas serão invertidas A representação genérica do flipflop tipo T com clock pode ser a mostrada abaixo Flipflop tipo T Tabela característica Tabela de transição Equação característica Qt1 T xor Qt Qt Qt1 T T Qt1 Qt1 Obs 0 0 0 0 Qt Qt hold 0 1 1 1 Qt Qt toggle 1 0 1 1 1 0 O diagrama de estados do flipflop tipo T está mostrado abaixo Diagrama de estados do flipflop tipo T Carta de tempo 1 CLK 0 1 T 0 1 Q 0 1 Q 0 Obs Carta de tempo obtida com flipflop sensível à borda de descida sem atraso lag 0 1 1 1 0 0 Q T Q CLK Pontifícia Universidade Católica de Minas Gerais 79 Flipflop JK O flipflop tipo JK é uma modificação do flipflop SR que é capaz de inverter toggle as entradas quando ambas forem iguais a 1 Flipflop tipo JK Tabela característica Tabela de transição Equação característica Qt1 J Qt K Qt J K Qt1 Qt1 Obs Qt Qt1 J K 0 0 Qt Qt hold 0 0 0 X 0 1 0 1 reset 0 1 1 X 1 0 1 0 set 1 0 X 1 1 1 Qt Qt toggle 1 1 X 0 O diagrama de estados do flipflop tipo JK está mostrado abaixo Diagrama de estados do flipflop JK Carta de tempo 1 CLK 0 1 J 0 1 K 0 1 Q 0 1 Q 0 Obs Carta de tempo obtida com flipflop sensível à borda de descida sem atraso lag O flipflop tipo JK é considerado modelo universal e usado para construir os outros tipos O flipflop tipo JK também pode apresentar um comportamento indesejado quando entra no estado de toogle as saídas Q e Q podem entrar em oscilação até que as entradas voltem a zero Isso pode ser resolvido através do uso de arranjos do tipo mestreescravo a seguir 0 1 10 11 01 11 00 10 00 01 Q Q J CLK K Flipflop tipo JK J Q K Q CLK Flipflop tipo D J Q K Q CLK D Flipflop tipo T J Q K Q CLK T Pontifícia Universidade Católica de Minas Gerais 80 Flipflop mestreescravo Em um flipflop mestreescravo o primeiro bloco mestre é utilizado para receber uma entrada de dados e armazenálo Em um instante posterior o dado será transferido ao escravo Ambas as ações são sincronizadas pelo sinal de clock Flipflop mestreescravo tipo D Flipflop mestreescravo tipo JK mestre ativo escravo dado saída clockt dado mestre escravo ativo novo dado dado clockt1 dado CLK D Q Q mestre escravo CLK J Q Q mestre K escravo Pontifícia Universidade Católica de Minas Gerais 81 Registradores Um registrador é um arranjo de elementos lógicos capaz de armazenar uma palavra binária de N bits Registradores para armazenamento Um registrador para armazenamento é construído com células sensíveis à transição utilizadas em conjunto O esquema abaixo sugere um arranjo com quatro células Identificadores de sequências Um identificador reconhecedor de sequência é uma máquina de estados finitos serve para receber entradas de dados em série e testar se formam determinado valor Dois modelos de identificadores já foram mencionados anteriormente Mealy e Moore Identificador de sequência abcd1101 segundo Mealy Identificador de sequência abcd1101 segundo Moore CLK saída entrada Q3 d Q2 c Q1 b Q0 a CLK x s o CLK CLR D Pr Q Cl Q D Pr Q Cl Q D Pr Q Cl Q D Pr Q Cl Q d b c a D Pr Q Cl Q CLK CLR D Pr Q Cl Q D Pr Q Cl Q D Pr Q Cl Q D Pr Q Cl Q d b c a x s o Pontifícia Universidade Católica de Minas Gerais 82 Conversão paralelosérie Um arranjo particular de entradas síncronas e assíncronas pode ser construído para realizar a conversão paralelosérie dados são carregados load simultaneamente e em seguida passados à saída um de cada vez CLK CLR Load d c b a d0 c1 b1 a0 Load CLK CLR D Pr Q Cl Q D Pr Q Cl Q D Pr Q Cl Q D Pr Q Cl Q d b c a Pontifícia Universidade Católica de Minas Gerais 83 Registradores de deslocamento shift register Registradores podem realizar rotações de bits para direita ou para esquerda Um registrador de deslocamento serve para mover dados para as células vizinhas quando houver variação pulsos do clock O esquema abaixo sugere um arranjo com quatro células CLK dado d c b a Se as entradas de dados também variarem ao longo do tempo mais de uma informação estará passando pelo conjunto de registradores em um mesmo instante tempo entradas d c b a saídas 0 0 1 1 1 t 0 1 1 1 2t 0 1 1 1 3t 0 1 1 1 4t 0 1 1 1 5t 0 1 1 1 6t 0 1 1 1 7t 0 1 1 1 8t 0 1 1 1 FF0 FF1 FF2 FF3 FF0 FF1 FF2 FF3 CLK J Q K Q J Q K Q J Q K Q J Q K Q d b c a dado Pontifícia Universidade Católica de Minas Gerais 84 Contadores de pulsos Contadores são arranjos de registradores capazes de contar pulsos presentes nas entradas A saída pode ser vista como um número em binário crescente ou decrescente A seguir um exemplo de contador de pulsos em ordem crescente de 0 a 15 Reset Pulso a b c d O esquema abaixo ilustra um contador de pulsos decrescente de 15 a 0 Reset Pulso d c b a J Pr Q K Cl Q J Pr Q K Cl Q J Pr Q K Cl Q J Pr Q K Cl Q d b c a o o o o o o o o RESET PULSO 1 J Pr Q K Cl Q J Pr Q K Cl Q J Pr Q K Cl Q J Pr Q K Cl Q a c b d o o o o o o o o RESET PULSO 1 o o o o Pontifícia Universidade Católica de Minas Gerais 85 Contadores decádicos Contadores decádicos ou em décadas são contadores que voltarão a zero reset quando o valor das entradas for igual a dez pulsos ou 1010 em binário Esses contadores também podem contar dez pulsos em ordem decrescente Nesse caso a contagem deverá reiniciar o contador quando o valor equivalente a cinco ou 0101 em binário J Pr Q K Cl Q J Pr Q K Cl Q J Pr Q K Cl Q J Pr Q K Cl Q a c b d o o o o o o o o RESET PULSO 1 o o o o J Pr Q K Cl Q J Pr Q K Cl Q J Pr Q K Cl Q J Pr Q K Cl Q d b c a o o o o o o o o RESET PULSO 1 o o Pontifícia Universidade Católica de Minas Gerais 86 Contadores assíncronos Contadores assíncronos são circuitos lógicos cujas flipflops não atuam nas mesmas freqüências de clock Exemplo Supor o arranjo de quatro flipflops tipo JK mestreescravo em cascata Como esse tipo de flipflop só mudará de estado na descida do clock o resultado será uma seqüência de pulsos com o dobro da largura inicial ou metade da freqüência do circuito anterior Pulso d c b a Pulso a b c d 0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0 11 1 0 1 1 12 1 1 0 0 13 1 1 0 1 14 1 1 1 0 15 1 1 1 1 16 0 0 0 0 J Q K Q J Q K Q J Q K Q J Q K Q d b c a PULSO 1 Pontifícia Universidade Católica de Minas Gerais 87 Contadores assíncronos decrescentes Contadores assíncronos decrescentes são circuitos cujas saídas são os complementos das saídas de contadores assíncronos como mostrado anteriormente Isso pode ser feito tomando os valores das saídas complementadas Q ou invertendose os sinais de clock Contadores síncronos Em freqüências mais altas os contadores assíncronos podem apresentar pequenas variações nos tempos de resposta e com isso gerar erros Nos contadores síncronos isso pode ser minimizado pois todos os blocos funcionarão na mesma freqüência Contadores síncronos decádicos Para projetar um contador síncrono decádico será preciso voltar à tabela característica de um flipflop JK e reorganizála em uma tabela de transições como se mostrará abaixo Caso J K Qt1 Casos Qt Qt1 J K A 0 0 Qt A e B 0 0 0 X B 0 1 0 C e D 0 1 1 X C 1 0 1 B e D 1 0 X 1 D 1 1 Qt A e C 1 1 X 0 Os valores representados por X indicam que o valor 0 ou 1 não importa dont care Pulso a b c d J3 K3 J2 K2 J1 K1 J0 K0 1 0 0 0 0 0 X 0 X 0 X 1 X 2 0 0 0 1 0 X 0 X 1 X X 1 3 0 0 1 0 0 X 0 X X 0 1 X 4 0 0 1 1 0 X 1 X X 1 X 1 5 0 1 0 0 0 X X 0 0 X 1 X 6 0 1 0 1 0 X X 0 1 X X 1 7 0 1 1 0 0 X X 0 X 0 1 X 8 0 1 1 1 1 X X 1 X 1 X 1 9 1 0 0 0 X 0 0 X 0 X 1 X 10 1 0 0 1 X 1 0 X 0 X X 1 11 0 0 0 0 J Pr Q 0 K Cl Q J Pr Q 1 K Cl Q J Pr Q 2 K Cl Q J Pr Q 3 K Cl Q d b c a CLK J Q K Q J Q K Q J Q K Q J Q K Q d b c a PULSO 1 Pontifícia Universidade Católica de Minas Gerais 88 J3 K3 c c c c c c c c a 0 0 0 0 b a X X X X b a 0 0 1 0 b a X X X X b a X X X X b a X X X X b a X X X X b a 0 1 X X b d d d d d d d d J2 K2 c c c c c c c c a 0 0 1 0 b a X X X X b a X X X X b a 0 0 1 0 b a X X X X b a X X X X b a 0 0 X X b a X X X X b d d d d d d d d J1 K1 c c c c c c c c a 0 1 X X b a X X 1 0 b a 0 1 X X b a X X 1 0 b a X X X X b a X X X X b a 0 0 X X b a X X X X b d d d d d d d d J0 K0 c c c c c c c c a 1 X X 1 b a X 1 1 X b a 1 X X 1 b a X 1 1 X b a X X X X b a X X X X b a 1 X X X b a X 1 X X b d d d d d d d d O circuito mostrado abaixo implementa essas simplificações d b c a J Pr Q 1 K Cl Q J Pr Q 2 K Cl Q J Pr Q 0 K Cl Q CLK J Pr Q 3 K Cl Q 1 Pontifícia Universidade Católica de Minas Gerais 89 Contadores em anel O contador em anel uma vez ativado deslocará um bit por vez e será reinicializado ao final da seqüência de bits CLK CLR PR d c b a O contador em anel torcido fará o mesmo mas não necessitará de um sinal de preset CLK CLR d c b a D Pr Q Cl Q D Pr Q Cl Q D Pr Q Cl Q D Pr Q Cl Q d b c a o o o o o CLR PULSO PR D D Pr Q Cl Q D Pr Q Cl Q D Pr Q Cl Q D Pr Q Cl Q d b c a o o o o CLR PULSO D Pontifícia Universidade Católica de Minas Gerais 89 Análise e síntese de circuitos sequenciais As técnicas para análise de circuitos sequenciais que implementam uma certa máquina de estados finitos em geral dividemse em duas etapas 1 determinar as funções que determinam o próximo estado e as saídas especificar as equações que representem a lógica do circuito e as saídas de cada flipflop estado corrente especificar as equações que determinem as transições entre dois pulsos de clock construir a tabela de transições para cada uma das combinações das entradas indicando quais os próximos estados identificar todas as combinações que representem um mesmo estado e reescrevê las em uma tabela de estados 2 construir as tabelas de estadossaídas que especifiquem o comportamento do circuito para todas as combinações das entradas e do estado corrente verificar as funções das saídas em relação às entradas e aos estados correntes após avaliar todas as combinações de entradas e estados combinar a tabela de estados com essas informações e criar a tabela de estadossaídas relacionando cada saída ao proximo estado Exemplo 1 Considerar o circuito abaixo com um flipflop tipo D Tabela de transições Equações de transições Qtxy 00 01 10 11 D xQ yQ 0 0 1 0 1 1 1 1 0 0 Qt1 x Qt y Qt Qt1 Tabela de estadossaídas Diagrama de estados Qtxy 00 01 10 11 A A0 B1 A0 B1 B B1 B1 A0 A0 estados Qt1 saída A0 B1 y x x y x y CLK D Q Q saída Pontifícia Universidade Católica de Minas Gerais 90 Considerar o circuito abaixo com dois flipflops tipo JK Tabela de transições Equações de transições saída s1 s2x s1 s2 x s1 s2 saída J1 s2 x e K1 s2 x t t t1 t1 J2 s1 x e K2 x 0 0 0 0 0 0 0 1 0 0 1 0 1 0 Qt1 J1 Qt K1 Qt 2 0 1 0 1 0 0 s1 s2xs1 s2 xs1 3 0 1 1 0 1 0 s2xs1 s2 x s1 4 1 0 0 1 1 0 x s2 s1 s2 s1 5 1 0 1 0 1 0 x s1 xor s2 6 1 1 0 0 0 0 7 1 1 1 0 1 1 Qt1 J2 Qt K2 Qt s2 xs1s2 xs2 xs2s1s2xs2 xs2s2 s1s2 x s1 s2 Tabela de estadossaídas Diagrama de estados s1 s2 x0 x1 saída 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 2 1 0 1 1 0 1 0 3 1 1 0 0 0 1 01 J Q 1 K Q J Q 2 K Q x saída s1 s2 11 0 01 01 x x x x 00 0 10 0 x x x x x Pontifícia Universidade Católica de Minas Gerais 91 Exemplo 2 Projetar um contador crescente módulo 4 01230 com flipflops tipo D Tabela de transições Diagrama de estados s1 s2 evento s1 s2 t t t1 t1 a b c a b 0 0 0 0 0 0 1 0 0 1 0 1 2 0 1 0 0 1 3 0 1 1 1 0 4 1 0 0 1 0 5 1 0 1 1 1 6 1 1 0 1 1 7 1 1 1 0 0 Equações de transições sinais SoP mintermos simplificação s1 3456 abcabcabcabc acababc s2 1256 abcabcabcabc bcbc Circuito 0 11 01 0 1 00 10 1 1 1 0 0 c CLK D Q Q s1 a a ca bab c D Q Q s2 b b cbc Pontifícia Universidade Católica de Minas Gerais 92 Exemplo 3 Projetar um contador decrescente módulo 4 03210 com flipflops tipo D Tabela de transições Diagrama de estados s1 s2 evento s1 s2 t t t1 t1 a b c a b 0 0 0 0 0 0 1 0 0 1 1 1 2 0 1 0 0 1 3 0 1 1 0 0 4 1 0 0 1 0 5 1 0 1 0 1 6 1 1 0 1 1 7 1 1 1 1 0 Equações de transições sinais SoP mintermos simplificação s1 1467 abcabcabcabc acababc s2 1256 abcabcabcabc bcbc Circuito 0 11 01 0 1 00 10 1 1 1 0 0 c CLK D Q Q s1 a a ca babc D Q Q s2 b b cbc Pontifícia Universidade Católica de Minas Gerais 91 Controle de temporização de circuitos Um dos circuitos integrados mais versáteis para controle de tempo é o 555 capaz de funcionar em três modos monoestável modo no qual o circuito produz um único disparo aplicações temporização chaveamento sem ressaltos divisores de frequência modulação de largura de pulso PWM etc astável modo no qual o circuito opera como um oscilador capaz de alternar regularmente entre estados altos e baixos aplicações acionamentos de LEDs geradores de tons alarmes modulação de posição de pulso clocks etc biestável modo no qual o circuito opera como um flipflop capaz de permanecer em um de dois estados indefinidamente aplicações chaveamento sem ressaltos bouncefree latched e registradores memória O diagrama abaixo representa a configuração típica para um oscilador em modo astável O capacitor C1 é carregado pela corrente que passa por R1 e R2 Quando a carga alcança 23 da tensão de alimentação V o limiar é atingido a saída vai para nível baixo e o pino de descarga é conectado a 0V Quando a descarga da corrente que passa por R2 atinge 13 da tensão de alimentação a saída vai para nível alto e cessa a descarga permitindo a recarga do capacitor O ciclo se repetirá continuamente até que o pino de reset seja conectado a 0V V GND saída reset controle 0V V gatilho limiar descarga 8 4 1 5 3 7 6 2 555 R1 R2 C1 C2 capacitor 13V 23V carga descarga t carga Tmark Tspace V 0V TTmarkTspace saída t Pontifícia Universidade Católica de Minas Gerais 92 Um ciclo de trabalho carga e recarga ocorre durante o período T da onda quadrada o qual inclui o tempo de marcação Tm e o tempo de espaçamento Ts 2 2 1 70 1 2 70 1 2 1 70 R R C R C R R Ts Tm T onde T período s Tm tempo de marcação s Ts tempo de espaçamento s R1 resistor ohms R2 resistor ohms C1 capacitor F A frequência de oscilação Hz é o número de ciclos de trabalho por segundo 1 2 2 1 41 1 C R R T f Para que o circuito funcione no modo astável o tempo de marcação Tm deverá ser praticamente igual ao tempo de espaçamento Ts Isso acontecerá se o valor de R2 for muito maior que R1 nesse caso o valor da frequência será dado por 1 2 70 C R f Exemplo Com os valores dados abaixo R1 1 KΩ R2 68 KΩ C1 10 μF C2 01 μF para estabilização A frequência será de f 07 68x103 x 10x106 1 Hz Pontifícia Universidade Católica de Minas Gerais 93 Exemplos de usos do temporizador ASTÁVEL BIESTÁVEL FLIPFLOP NOT GATE Pontifícia Universidade Católica de Minas Gerais 94 Modelos de computador Modelo de computador baseado em operação 1 Modelo de computador com armazenamento de dados e instruções 2 Armazenamento Operação Instruções Dados Resultados Operação Instruções Resultados Dados 3 2 1 Pontifícia Universidade Católica de Minas Gerais 95 Modelo de computador com banco de registradores para dados 3 Modelo de computador com registradores para instrução e códigos de condição 4 Códigos de Condição flags Unidade Lógica e Aritmética Instruções Dados Resultados Registrador de Instrução Registradores Unidade Central de Processamento Memória Unidade Central de Processamento Memória Unidade Lógica e Aritmética peração Instruções Dados Resultados Registradores Pontifícia Universidade Católica de Minas Gerais 96 Modelo de computador com apontador de instrução e memória 5 Modelo de computador e fases de funcionamento 6 decodificação busca execução reescrita fases endereço do operando Unidade Central de Processamento Memória Unidade Lógica e Aritmética peração dado Resultados Registrador de Instrução Registradores Registrador de Dados da Memória Registrador de Endereços da Memória Códigos de Condição flags Apontador de Instrução instrução endereço endereço do operando Unidade Central de Processamento Memória Unidade Lógica e Aritmética peração dado Resultados Registrador de Instrução Registradores Registrador de Dados da Memória Registrador de Endereços da Memória Códigos de Condição flags Apontador de Instrução instrução endereço Pontifícia Universidade Católica de Minas Gerais 97 Modelo de computador com barramentos e registradores operacionais 7 Busca de instrução REM AI endereço da instrução RDM MEM REM RI RDM cópia da instrução AI AI 1 endereço da próxima instrução Decodificação identificar operandos e operação Execução de instrução sem reaproveitamento com reaproveitamento R1 MEM REM REM RI endereço do operando R2 MEM REM AC R1 R2 R1 AC REM RI endereço do operando R2 MEM REM AC R1 R2 armazenamento Barramento de Controle operando 1 Registrador de Dados da Memória Registrador de Endereços da Memória Unidade Central de Processamento Unidade Lógica e Aritmética peração resultado Registrador de Instrução Apontador de Instrução Códigos de Condição flags Memória operando 2 Acumulador Barramento de Dados Barramento de Endereços registrador 2 registrador 1 instrução dado endereço instrução endereço Pontifícia Universidade Católica de Minas Gerais 98 Modelo de computador com unidades funcionais 8 Barramento de Controle operando 1 Registrador de Dados da Memória Registrador de Endereços da Memória Unidade Central de Processamento Unidade Lógica e Aritmética resultado Registrador de Instrução Apontador de Instrução Códigos de Condição flags Memória operando 2 Acumulador Barramento de Dados Barramento de Endereços registrador 2 registrador 1 instruçãodado endereço instrução endereço palava de controle Decodificador e Temporizador operações Unidade de Controle armazenamento sinais Pontifícia Universidade Católica de Minas Gerais 99 Modelo de computador com controle de periféricos Barramento de Dados Registrador de Entrada Barramento de Controle operando 1 Registrador de Dados da Memória Registrador de Endereços da Memória Unidade Central de Processamento Unidade Lógica e Aritmética resultado Registrador de Instrução Apontador de Instrução Códigos de Condição flags Memória operando 2 Acumulador Barramento de Endereços registrador 2 registrador 1 instruçãodado endereço instrução endereço palava de controle Decodificador e Temporizador operações Unidade de Controle Registrador de Saída de dispositivo para dispositivo dado dado Interfaces com Periféricos e Aritmética para dispositivo de dispositivo sinais e interrupções sinais e interrupções Controlador de Dispositivos armazenamento Pontifícia Universidade Católica de Minas Gerais 100 Modelo de computador com cache e controle de avanços e desvios 10 Barramento de Dados Registrador de Entrada Barramento de Controle operando 1 Registrador de Dados da Memória Registrador de Endereços da Memória Unidade Central de Processamento Unidade Lógica e Aritmética resultado Apontador de Instrução Códigos de Condição flags Memória operando 2 Acumulador Barramento de Endereços registrador 2 registrador 1 instruçãodado endereço endereço operações Unidade de Controle Registrador de Saída de dispositivo para dispositivo dado dado Interfaces com Periféricos e Aritmética para dispositivo de dispositivo sinais e interrupções Controlador de Dispositivos armazenamento Prefetch Cache Memória Principal Registrador de Instrução instrução palava de controle Decodificador e Temporizador sinais e interrupções avanços desvios Apontador de Pilha endereço Pontifícia Universidade Católica de Minas Gerais 101 Modelo do ciclo de busca decodificação e execução de instruções Ciclo de busca por instrução próxima instrução em RI desvio próxima instrução em RI início REM AI RDM MEM REM IR MDR AI AI1 REM endereço decodificar e executar não não não sim sim sim instrução Pontifícia Universidade Católica de Minas Gerais 102 Decodificar e executar desvio RDM MEM REM AC RDM REM endereço decodificador instrução operação endereço registrador de instrução RI AI endereço sim não decodificar e executar retornar Pontifícia Universidade Católica de Minas Gerais 103 Memória Apontador de Instrução Registrador de Instrução Temporizador Circuitos Lógicos Sinais de Controle Decodificação por circuitos lógicos hardwired demux Decodificação por microcódigo microcoded ou softwired Memória Apontador de Instrução Registrador de Instrução Temporizador Endereço Controle Memória com microcódigo de instruções Decodificador Sinais de Controle Pontifícia Universidade Católica de Minas Gerais 104 Interface softwarehardware ISA Instruction Set Architecture O nível ISA define como uma máquina se apresentará ao programador quais as instruções em linguagem de máquina qual o modelo de memória quantidade de bits alinhamento etc quantidade e tipos dos registradores uso geral apontadores pilha de estado tipos de dados disponíveis numéricos e nãonuméricos lógicos cadeias etc aplicativos software sistema operacional compilador firmware Instruction Set Architecture ISA conjunto de Instruções sistema de entradas e saídas controle e datapath hardware projeto lógico projeto físico circuitos layout transistores De forma simplificada o nível ISA estabelece os limites entre software e hardware Programa fonte em linguagem de alto nível Programa fonte em linguagem de montagem compilação nível ISA Programa objeto em linguagem de máquina software hardware interpretação por microprograma ou execução pelos circuitos circuitos lógicos Em termos práticos uma instrução será executada por circuitos lógicos embora cada nível possa ter uma forma diferente para sua expressão linguagem de alto nível A 10 linguagem de montagem LDA 0ah linguagem de máquina 00110011 00001010 Pontifícia Universidade Católica de Minas Gerais 105 Evolução dos conjuntos de instruções acumulador simples EDSAC 1950 acumulador registradores de índice Mark I IBM S700 1953 separação modelo implementação baseado em linguagem de alto nível B500 1954 baseado em uma família IBM 3601963 registradores de uso geral conjuntos de instruções complexas VAX Intel 432 197780 arquiteturas loadstore CDC 6600 Cray I 196376 CISC Intel x86 Pentium RISC MIPS PowerPC 1987 Pontifícia Universidade Católica de Minas Gerais 106 Classificação de ISAs C A B Instrução Descrição 1 Acumulador antes de 1960 68HC11 load A AC mem A 1 endereço add B AC AC mem B store C mem C AC 2 Pilha de 1960 a 1970 push A SP SP1 stackSP mem A push B SP SP1 stackSP mem B 0 endereço add stackSP1 stackSP1 stackSP pop C SP SP1 mem C stackSP 3 MemóriaMemória de 1970 a 1980 2 endereços add A B mem A mem A memB 3 endereços add A B C mem A mem B memC 4 RegistradorMemória 1970 em diante 80x86 load R1 A R1 mem A 2 endereços add R1 B R1 R1 mem B store C R1 mem C R1 5 RegistradorRegistrador loadstore 1960 em diante MIPS load R1 A R1 mem A load R2 B R2 mem B 3 endereços add R3 R1 R2 R3 R1 R2 store C R3 mem C R3 Tipo Vantagens Desvantagens Acumulador boa densidade de código compilador simples de escrever acumulador é gargalo dificulta paralelismo e pipelining compilador otimizado é difícil alto tráfego com a memória Pilha boa densidade de código poucos requisitos de hardware compilador simples de escrever pilha é gargalo dificulta paralelismo e pipelining compilador otimizado é difícil operações complementares para movimentar dados na pilha MemóriaMemória boa densidade de código 3 compilador simples de escrever tempo variável por instrução operações complementares para lidar poucos operandos alto tráfego com a memória RegistradorMemória boa densidade de código possível acessar dado sem carregar tempo variável por instrução baixa ortogonalidade limitado em registradores RegistradorRegistrador loadstore boa densidade de código mesmo tempo por instrução fácil paralelismo e pipelining instruções numerosas nem sempre três operandos dependente de bom compilador Registradores 1980 em diante mais rápidos do que cache tráfego de memória reduzido limitados em quantidade salvar e restaurar contexto dependente de bom compilador Pontifícia Universidade Católica de Minas Gerais 107 Modelo ISA baseado em Acumulador Modelo ISA baseado em Pilha Modelo ISA baseado em MemóriaMemória ALU Memória 0 Memória 1 Memória 2 Memória n Memória Principal ALU Acumulador Memória Principal ALU Topo da Pilha Pilha 1 Pilha 2 Pilha n1 Pontifícia Universidade Católica de Minas Gerais 108 Modelo ISA baseado em RegistradorMemória Modelo ISA baseado em RegistradorRegistrador loadstore Memória Principal ALU Registrador 0 Registrador 1 Registrador 2 Registrador n1 Memória Principal ALU Registrador 0 Registrador 1 Registrador 2 Registrador n1 Pontifícia Universidade Católica de Minas Gerais 109 Formatos de instruções O formato das instruções está relacionado ao modelo de memória à quantidade de processadores ao tempo de decodificação ao tempo de execução busca de operandos e à quantidade de memória endereçável Os formatos podem ser constituídos por códigos de instrução opcode e operandosendereços Os formatos podem ser fixos ou variados com 0 1 2 ou mais operandosendereços dependendo da arquitetura e dos modos de endereçamento memória e registradores código opcode código opcode operando endereço código opcode endereço1 endereço2 código opcode endereço1 endereço2 endereço3 Tipos de formatos de instrução Pontifícia Universidade Católica de Minas Gerais 110 Modos de endereçamento 1 Implícto instrução traz o próprio o endereçamento não há operando instrução Exemplo No Intel 8080 STC Set Carry Flag RAL Rotate Accumulator Left RLC Rotate Accumulator through Carry DAA Decimal Adjust Accumulator 2 Imediato instrução traz o próprio operando dadoconstante instrução X X X X X X X X operando instrução A A A A A A A A operandoendereço A A A A A A A A Exemplo No Intel 8080 ADI data Add Immediate to accumulator LDI data Load Immediate to accumulator JMI address Jump Immediate to address CPI data Compare Immediate with accumulator Uso valor constante valor inicial para contador armazenar endereço ponteiro em registrador indicar quantidade de posições em deslocamento de bits Vantagens uso com valores constantes operando obtido durante o ciclo de busca apenas 1 acesso Desvantagens tamanho do dado limitado à quantidade de bits não há flexibilidade para se alterar dados que variem a cada execução do programa Pontifícia Universidade Católica de Minas Gerais 111 3 Direto opcode endereço Memória operando instrução traz o endereço do operando dado na memória instrução A A A A A A A A operandoendereço A A A A A A A A Exemplo No Intel 8080 LDA address Load accumulator with Address content JMP address Jump to address Uso indicar posição em memória Vantagens referência direta à memória Desvantagens tamanho do endereço limitado à quantidade de bits mais lento que o modo imediato mais ciclos para busca do operando durante execução 4 Indireto opcode endereço 1 Memória endereço 2 operando instrução indica o endereço 1 de outro 2 onde está o dado na memória Exemplo No Z80 LD A address Load Accumulator Indirect from memory Uso indicação do endereço do dado Vantagens referência indireta à memória estruturas de dados mais complexas com um endereço menor apontador indicar dado em um espaço de endereçamento maior Desvantagens mais lento que o modo imediato mais ciclos para busca do operando durante execução Pontifícia Universidade Católica de Minas Gerais 112 5 Indireto via registrador opcode registrador Registradores Memória endereço operando instrução indica os registradores que contém o endereço apontador do dado na memória R R r r instruçãoregistradores Exemplo No Intel 8080 ADD M Add Memory addressed by register pair HL to accumulator MOV M register Move register to Memory addressed by register pair HL Uso indicação do dado Vantagens referência indireta à memória estruturas de dados mais complexas Desvantagens tamanho de registradores limitado mais lento que o modo imediato mais ciclos para busca do operando durante execução 6 Direto via registrador opcode registrador Registradores operando instrução indica o registrador que contém o dado R R R instruçãoregistrador Exemplo No Intel 8080 ADD register Add register to accumulator DCR register Decrement register Uso contador Vantagens tamanho da instrução pequeno referência direta a registrador não faz acesso à memória Desvantagens quantidade de registradores limitada mais lento que o modo imediato mais ciclos para busca do operando durante execução Pontifícia Universidade Católica de Minas Gerais 113 7 Indexado instrução opera sobre o endereço obtido pela soma do operando a um registrador índice Exemplo No Intel 8086 LDX register operand Load register with memory addressed by registeroperand ADX register operand Add register with memory addressed by registeroperand Uso para acessar dado em arranjo Vantagens referência rápida para acesso a dados contíguos na memória Desvantagens tamanho 8 Relativo modo basedeslocamento opcode base deslocamento Registradores Memória endereço operando instrução opera sobre o endereço obtido pela soma do operando deslocamento ao endereço contido em um registrador base Exemplo ADD baseindexregisteroffset register Add register to memory address Uso para segmentação e para realocação de dadosprogramas na memória Vantagens referência rápida para acesso a porções contíguas na memória Desvantagens tamanho limitado 9 Combinados instruções que combinam modos de endereçamento direto ou imediato indireto via pilha instruções que combinam deslocamento relativo ao contador de programa PC instruções que combinam deslocamento com um registrador de base ou a um registrador de base e outro indexador por exemplo para acesso a colunas de arranjos instruções que possuem endereçamento relativo com autoincremento ou autodecremento de registrador instruções que referemse a blocos de memória página base página corrente registrador de página instruções com indexação direta ou indireta préindexada ou pósindexada Pontifícia Universidade Católica de Minas Gerais 114 Tipos de instruções Em termos gerais há três tipos básicos de instruções controle escalares e vetoriais As instruções de controle do fluxo de execução das ações podem ser sequenciais ou de desvios condicionais incondicionais ou chamadas a métodos procedimentos ou funções As instruções de controle irão alterar no endereço da instrução a ser executada cujo código está armazenado no endereço indicado pelo Apontador de Instrução Instruction Pointer ou Contador de Programa Program Counter ou PC Essas alterações poderão ser indicadas por uma tupla PCatual PCdesvio PCatual1 onde é uma condição qualquer expressa por operação lógica válida cujo resultado possa ser verdadeiro V ou falso F PCatual é o endereço da instrução corrente PCdesvio será o endereço da próxima instrução a ser executada se a condição resultar em valor verdadeiro V ou o endereço da próxima instrução caso a condição tiver valor falso F PCatual1 o endereço da próxima instrução ou endereço de parada ou para tratamento de situações de erro Uma constante arbitrária 0 será tomada a seguir como endereço de parada ou também poderá ser usada para indicar situação de erro Em situação normal sequencial sem desvios a próxima instrução será aquela seguinte a do endereço atual V PCatual PCatual1 0 V V PCatual PC atual1 F PCatual 0 Se houver um desvio condicional e a condição avaliada for verdadeira V o valor atual será igual ao indicado pelo desvio senão o endereço da próxima instrução será o seguinte ao atual PCatual PCdesvio PCatual1 V PCatual PCdesvio F PCatual PCatual1 Se houver desvio incondicional a próxima instrução será aquela indicada pelo desvio V PCatual PCdesvio 0 V V PCatual PCdesvio F PCatual 0 Uma chamada de procedimento fará um desvio para outro trecho de memória executará outras instruções e deverá retornar à instrução prevista para ser executada seguinte à chamada se não houver erros ou seja V PCatual PCdesvio 0 V PCdesvio PCdesvio1 0 V PCdesvion1 PCdesvion 0 V PCdesvion PC atual1 0 Pontifícia Universidade Católica de Minas Gerais 115 Uma instrução escalar poderá ser representada como R0 R1 R2 ou pela tupla R0 R1 R2 onde indicará qualquer operação válida como soma ou subração por exemplo e R0 R1 R2 indicarão registradores envolvidos na operação tal que R0 R1 R2 Exemplos Registradores Acumulador R1 2 AC 2 R2 3 RDM 3 R0 R1 R2 AC AC RDM R0 R1 R2 AC AC RDM Uma instrução vetorial poderá ser representada como V0 V1 V2 ou pela tupla V0 V1 V2 onde indicará qualquer operação válida sobre esses dados V0 V1 V2 indicarão grupos de dados homogêneos arranjos vetores ou listas tal que Vk Rk1 Rk2 Rkn Exemplo Produto interno de cada valor em um vetor V1 com o correspondente em V2 e armazenar o resultado em V0 supondo todos do mesmo tamanho V0 V1 V2 V0 R01 R11 R21 R02 R12 R22 R0n R1n R2n Os principais modos de endereçamento também podem ser expressos de forma compacta pelo emprego da notação de tuplas como mostrado a seguir Principais modos de endereçamento revistos para a representação por tuplas Modo de endereçamento Exemplo Uso Registrador R0 R1 R2 com dados em registradores Imediato R0 R1 0 com constantes Deslocamento R0 R1 MbaseR2 com variáveis locais Registrador indireto R0 R1 M R2 com acesso a dado via apontador Indexado R0 R1 M R2 R3 com endereçamento de arranjo Direto ou absoluto R0 R1 M8080 com acesso à memória estática Indireto em relação à memória R0 R1 M M R2 com combinações de apontadores Dessa forma podese definir um modelo de instrução servirá para especificar qualquer dos tipos básicos de operações quer sejam essas sequenciais ou paralelas sobre dados singulares ou múltiplos independente da arquitetura específica do conjunto de instruções Pontifícia Universidade Católica de Minas Gerais 116 Modelos de arquitetura de computadores Um modelo simplificado de uma arquitetura genérica para computador procura agregar os seguintes componentes principais Unidade Central de Processamento UCP o Unidade de Controle o Unidade Lógica e Aritmética Memória Periféricos Organização de computador 1 Esses componentes são conectados por vias ou barramentos por onde passam as informações entre eles Organização de computador 2 Unidade de Controle Unidade Lógica e Aritmética Unidade Central de Processamento barramento interno barramento externo entradas saídas Memória Periféricos Unidade de Controle Unidade Lógica e Aritmética Memória e Periféricos Unidade Central de Processamento Pontifícia Universidade Católica de Minas Gerais 117 Embora a distinção entre barramento interno e externo exista e a comunicação entre os componentes na Unidade Central de Processamento seja favorecida pela disponibilidade de um barramento interno exclusivo a generalização das conexões por barramentos será empregada a seguir Os barramentos podem ser separados segundo especificidades em de controle de endereços de dados Organização de computador 3 Organização de computador 4 Memória Periféricos barramento de endereços entradas saídas barramento de controle barramento de dados Unidade de Controle Unidade Lógica e Aritmética Unidade Central de Processamento Unidade de Controle Unidade Lógica e Aritmética Periféricos Unidade Central de Processamento barramentos entradas saídas Memória Pontifícia Universidade Católica de Minas Gerais 118 A Unidade de Controle conta com elementos adicionais para ajustar a sincronização das transferências timing entre componentes e para administrar os sinais para ativaçãodesativação de cada um deles datapath Organização de computador 5 O modelo a seguir dispõe os elementos para permitir futuras expansões Organização de computador 6 Memória Periféricos barramento de endereços entradas saídas barramento de controle barramento de dados Unidade de Controle Unidade Lógica e Aritmética Unidade Central de Processamento timing datapath Unidade Central de Processamento UCP Memória Periféricos entradas saídas barramento de controle barramento de dados barramento de endereços D A T A P A T H T I M I N G Pontifícia Universidade Católica de Minas Gerais 119 Modelos de arquiteturas de computador sequencial Arquitetura de Computador Harvard Arquitetura de Computador Princeton von Neumann Memória RAM ROM Pilha dados endereços controle Decodificador Processador dados endereços controle Registradores Memória Memória ROM RAM Pilha Unidade de Interface com a Memória dados endereços controle Decodificador Processador e Registradores Pontifícia Universidade Católica de Minas Gerais 120 Comparação entre modelos de arquiteturas de computador sequencial Harvard Princeton memória com código e dados com barramentos separados memória com apenas um barramento potencialmente mais eficiente paralelismo menor quantidade de ciclos de memória para se executar instruções instruções e dados são tratados iguais uso de caches de instruções e dados prébuscas de instruções e dados modelo de projeto de processador com mais detalhes modelo de projeto de processador mais simples exemplo Microchip PIC exemplo Motorola 68HC11 80x86Pentium exceto IO Comparação entre os principais tipos de arquitetura de conjunto de instruções ISAs segundo o conjunto de instruções CISC Complex Instruction Set Computer RISC Reduced Instruction Set Computer conjunto numeroso e variado de instruções conjunto simples e pequeno de instruções conjunto único de registradores 16 múltiplos conjuntos de registradores 256 fracamente paralelizado altamente paralelizado pipeline tempos de execução diferentes quase o mesmo tempo de execução instruções com múltiplos ciclos mais lentas instruções com menos ciclos mais rápidas instruções com tamanho variado instruções com tamanho fixo instruções típicas com 1 ou 2 operandos instruções típicas com 3 operandos complexidade no código complexidade no compilador acesso à memória por várias instruções acesso à memória por poucas instruções múltiplos modos de endereçamento poucos modos de endereçamento controle microprogramado controle embutido no hardware menos ortogonal instruções específicas e pouco usadas mais ortogonal mais potência e maior flexibilidade Combinações dos tipos acima constituem arquiteturas híbridas e servem para possibilitar melhor compatibilidade entre hardware e software para possibilitar a construção e uso de diferentes linguagens para aumentar a capacidade de processamento Pontifícia Universidade Católica de Minas Gerais 121 Classificação de tipos de arquitetura de conjunto de instruções ISAs segundo a complexidade ISA Detalhes CISC Complex Instruction Set Computer muitas instruções especializadas algumas raramente utilizadas RISC Reduced Instruction Set Computer processador simplificado com implementação eficiente apenas do que for mais usado VLIW VLIW Very Long Instruction Word projetada para explorar o paralelismo no nível de instruções ILP compiladores mais complexos hardware simplificado para aproveitar o paralelismo conceito inventado por Josh Fisher e sua equipe na Universidade de Yale no começo dos anos 1980 Princípios identificar paralelismo além de um bloco básico e desenvolver um compilador capaz de organizar a ordem de execução o compilador e a arquitetura alvo deverão ser desenvolvidos em conjunto Exemplos de implementações Intel i860 1990 HP PARISC 1990 SOC SystemOnaChip GPU Graphics Processing Unit da Nvidia e da AMDATI EPIC Explicity Parallel Instruction Computing termo cunhado em 1997 pela aliança entre HP e Intel para o desenvolvimento de uma arquitetura com maior independência entre o hardware e o software compilador Princípios explorar o paralelismo ao nível de instruções eliminar a necessidade de circuitos complexos para organizar a ordem de execução de instruções em paralelo Exemplo Intel Itanium IA64 MISC Minimal Instruction Set Computer conjunto bem pequeno de instruções básicas geralmente orientadas para execução em pilha e com modo de endereçamento do tipo loadstore Exemplos Manchester Baby University of Manchester 1948 EDSAC University of Cambridge 1949 Mark1 University of Manchester 1949 EDVAC Ballistic Research Laboratory 1951 ORDVAC University ou Illinois 1951 IAS Princeton University 1952 MANIAC I Los Alamos Scientific Laboratory 1952 ILLIAC University of Illinois 1952 OISC One Instruction Set Computer máquina abstrata que tem apenas uma instrução dispensando a necessidade de um código de operação em linguagem de máquina empregado no ensino de arquitetura de computadores e em modelos computacionais para pesquisas em computação estrutural Categorias máquinas para manipulação de bits máquinas ativadas por transporte TTATransport Triggered Architecture máquinas de Turing completas baseadas em aritmética Exemplos de instruções subtrair e desviar se menor ou igual a zero subtrair e desviar se diferente de zero subtrair e desviar se negativo subtrair e desviar se positivo Pontifícia Universidade Católica de Minas Gerais 122 Os componentes principais para controle operações e memória apresentamse melhor agrupados por unidades funcionais Componentes principais para controle e operações A unidade da Memória segundo sua constituição pode ser separada em memória de programa ReadOnly Memory ROM memória de dados RandomAccess Memory RAM Registrador de Endereços Registrador de Endereços Registrador de Dados ROM interna Registrador de Dados ROM externa Memória Memória de programa Memória de dados Registrador de Endereços Registrador de Endereços Registrador de Dados RAM externa Registrador de Dados RAM interna funções especiais uso geral e pilha Acumulador Registrador Auxiliar Contador de Programa Apontador de pilha Temporização e Controle Unidade Lógica e Aritmética FLAGS Decodificador de Instruções Registrador de Instruções Registradores de Uso Geral Unidade Central de Processamento Unidade de Controle Unidade de Lógica e Aritmética Pontifícia Universidade Católica de Minas Gerais 123 Tipos de componentes de memória Tipos de memórias Tipo de memória Operação Apagamento Escrita Volatilidade RAM leitura e escrita elétricobyte elétrica volátil temporária ROM leitura indisponível por máscara PROM não volátil EPROM leitura ultravioletachip elétrica microprogramação EEPROM preferencial elétricobyte flash elétricobloco As memórias do tipo RAM podem ser classificadas como dinâmicas ou estáticas RAM dinâmica RAM estática necessita refrescamento dispensa refrescamento construção simples construção complexa menor áreabit maior áreabit mais barata mais cara mais lenta mais rápida memória principal memória cache Hiearquia de memória Custo Velocidade Capacidade registradores registradores cache nível 1 L1 nível 2 L2 nível 3 L3 memória principal RAM ROM flash SSD cache de disco memória secundária disco Pontifícia Universidade Católica de Minas Gerais 124 Princípio da localidade de referência A hierarquia de memória poderá funcionar bem se a grande maioria de dadosinstruções puderem estar disponíveis nos níveis mais altos enquanto as requisições que necessitem de acessos à memória em níveis mais baixos sejam bem reduzidas É tendência da execução sequencial de programas que haja reutilização de dados e instruções que tenham sido referenciados recentemente Isso se deve em boa parte ao uso de estruturas de controle repetitivas geralmente curtas e executadas numerosas vezes ou também pelo uso de estruturas de dados como arranjos listas e tabelas É possível prever com razoável precisão quais instruções ou dados serão usados em futuro próximo e com isso aperfeiçoar o desempenho de certos programas Há dois aspectos comuns a serem considerados 1 Localização temporal representa a alta probabilidade de que uma instrução executada recentemente seja realizada novamente em um curto espaço de tempo repetições por exemplo 2 Localização espacial representa a alta probabilidade de que instruções próximas àquela executada recentemente sejam executadas também em futuro próximo Do primeiro aspecto decorre o objetivo de se manter instruçõesdados acessados recentemente em local mais próximo para execução Do segundo aspecto decorre o objetivo de se mover blocos de instruçõesdados para níveis mais altos na hierarquia de memória na expectativa de que venham a ser usados proximamente Para favorecer a obtenção desses objetivos memórias caches e memórias virtuais vêm sendo projetadas e utilizadas No caso das caches quando um item instruçãodado é requerido pela primeira vez também será instalado na cache para permanecer em disponibilidade caso houver nova solicitação para uso Por outro lado para se reduzir cargas frequentes da memória principal mais lenta é conveniente carregar em cache mais rápida um grupo de itens bloco que residam em endereços adjacentes O projeto de uma hierarquia de memória deve levar em consideração a unidade mínima de informação presente ou ausente em cada nível bloco para memória cache páginas para memória virtual as taxas de tentativas de acesso com sucesso hit rate no nível superior as taxas de tentativas de acesso sem sucesso miss rate no nível superior miss para memória cache page fault para memória virtual penalização no desempenho quando a tentativa não tiver sucesso miss penalty incluindo o tempo clocks necessário para substituir aquilo que estiver em falta O tempo médio de execução CPUtime dependerá do número de instruções do período de clock Tclock e dos custos médios por instrução CPI para sua execução e para a espera por acesso aos dados CPUtime instruções Tclock CPIexecuçãoCPImemória e CPImemória acessos instruções miss rate miss penalty Melhor desempenho poderá resultar da minimização da miss rate eou miss penalty bem como da seleção adequada das dimensões dos blocos pelo melhor aproveitamento da largura de banda para acesso Pontifícia Universidade Católica de Minas Gerais 125 Memória cache A memória cache serve como dispositivo auxiliar para melhorar a velocidade de acesso à informação Com capacidade menor que a da memória principal guarda cópia de uma porção dessa Se durante uma operação de leitura o conteúdo já estiver na mesma hit não é necessário buscálo na memória principal barramento buffers barramento de endereços desabilitados do sistema MAR cache memória CPU hit leitura principal MDR barramento de dados Caso contrário ao ser necessário buscar um conteúdo não disponível miss ela também deverá ser atualizada barramento buffers barramento de endereços habilitados do sistema MAR cache memória CPU miss leitura principal MDR barramento de dados Pontifícia Universidade Católica de Minas Gerais 126 Ao ser realizada uma operação de escrita tanto o conteúdo da cache hit quanto da memória principal devem ser atualizados para manter coerência barramento buffers barramento de endereços habilitados do sistema MAR cache memória CPU hit escrita principal MDR barramento de dados Caso o conteúdo não esteja disponível na cache miss a atualização será executada apenas na memória principal barramento buffers barramento de endereços habilitados do sistema MAR cache memória CPU miss escrita principal MDR barramento de dados Pontifícia Universidade Católica de Minas Gerais 127 Tipos de memórias caches Os tipos de memórias caches mais conhecidos são 1 mapeamento direto 2 mapeamento associativo 3 mapeamento associativo por grupo Nway Exemplos 1 Mapeamento direto Cada bloco só pode ser colocado em um lugar na cache A função de mapeamento é geralmente uma função modular Os bits de mais alta ordem podem ser recuperados pela etiqueta tag O bit de validade dirtybit serve para indicar se o dado é válido ou não Memória Cache addr data 0 00 00 0000 0000 1 00 01 2 00 10 3 00 11 4 01 00 0001 0100 5 01 01 tag dbit 6 01 10 00 00 1 0000 0000 7 01 11 01 0 8 10 00 0010 1000 10 0 9 10 01 11 0 A 10 10 B 10 11 C 11 00 0011 1100 D 11 01 E 11 10 F 11 11 Para ser instalada na cache juntamente com a etiqueta tag na posição indicada pela função de mapeamento verificase se a linha está livre caso ocupada será substituída A procura por uma palavra é feita comparandose os bits de etiqueta tag se houver coincidência hit o bloco terá sido identificado Tem por vantagens requerer um circuito simples para testar etiqueta uma de cada vez economizar energia pois não testa todos os endereços e ter políticas simples para instalação e substituição Tem por desvantagem uma pequena taxa de acessos com sucesso hit rate e toda vez que houver não encontrar miss promoverá substituição Pontifícia Universidade Católica de Minas Gerais 128 2 Mapeamento associativo Cada bloco só pode ser colocado em um lugar na cache A função de mapeamento é geralmente uma função modular Memória Cache addr data 0 000 0 0000 0000 1 000 1 0000 0001 2 001 0 3 001 1 4 010 0 5 010 1 0010 0101 tag offset dbit 6 011 0 0011 0000 000 1 1 0000 0001 7 011 1 000 0 01 0000 0000 8 100 0 010 1 0 0010 0101 9 100 1 011 0 0 0011 0000 A 101 0 B 101 1 C 110 0 D 110 1 E 111 0 F 111 1 Para ser instalada na cache juntamente com a etiqueta tag e o deslocamento offset na posição indicada pela função de mapeamento verificase se a linha está livre caso ocupada outra posição será usada Se todas estiverem ocupadas se aplicará a política de substituição A procura por uma palavra é feita comparandose todos os bits de etiqueta tag em paralelo se houver coincidência hit o bloco terá sido identificado pelo uso do deslocamento Tem por vantagens oferecer flexibilidade para instalação em qualquer posição e portanto permitir o uso integral da cache ter taxa de acessos com sucesso melhor e permitir que a política para substituição possa empregar vários algoritmos Tem por desvantagens o custo maiores gastos de tempo e energia para localizar um bloco Pontifícia Universidade Católica de Minas Gerais 129 3 Mapeamento associativo por grupos Nway Solução de compromisso entre as anteriores buscando unir vantagens de ambos Memória Cache addr data 0 000 0 0000 0000 1 000 1 0000 0001 2 001 0 3 001 1 4 010 0 5 010 1 0010 0101 tag offset dbit 6 011 0 0011 0000 000 0 1 0000 0000 7 011 1 0011 0001 grupo 0 011 0 1 0011 0000 8 100 0 000 1 0 0000 0001 9 100 1 grupo 1 A 101 0 B 101 1 C 110 0 D 110 1 E 111 0 F 111 1 Para ser instalada na cache juntamente com a etiqueta tag e o deslocamento offset no grupo indicado pela função de mapeamento verificase se a linha está livre caso ocupada outra posição será usada Se todas estiverem ocupadas se aplicará a política de substituição A procura por uma palavra é feita comparandose todos os bits de etiqueta tag em paralelo apenas para os elementos pertencentes ao grupo se houver coincidência hit o bloco terá sido identificado pelo uso do deslocamento Tem por vantagens a combinação de características das outras formas de mapeamento além de permitir que a política para substituição possa empregar vários algoritmos Tem por desvantagens a possibilidade de não usar todas as posições disponíveis e promover substituição quando houver falta miss Pontifícia Universidade Católica de Minas Gerais 130 Algoritmos para substituição Dentre os algoritmos para substituição destacamse 1 LRU Least Recently Used a linha há mais tempo utilizada será a escolhida 2 LRR Least Recently Replaced a linha trocada há mais tempo FIFO será a escolhida 3 LFU Least Frequently Used a linha menos referenciada será a escolhida 4 Random uma linha qualquer será escolhida aleatoriamente Técnicas de escrita de dados em cache Técnicas de Write Hit 1 WriteBack Cache Essa esta técnica escreve dados diretamente em cache cabendo ao sistema posteriormente a atualizar a memória principal Ficase livre mais rapidamente para executar outras operações embora a latência do controlador possa trazer problemas de consistência de dados na memória principal como em sistemas multiprocessados com memória compartilhada que deverão ser tratados por protocolos de consistência de cache Vantagens a escrita ocorre conforme a velocidade da cache múltiplas escritas em um endereço requerem apenas uma escrita na memória menor consumo de largura de banda Desvantagens mais difícil para implementar problemas de consistência entre os dados existentes no cache e na memória leituras de blocos em cache podem resultar em escritas de blocos inválidos dirty na memoria 2 WriteThrough Cache Ao escrever em uma região de memória que está contida em cache escrevese tanto na linha específica de cache como na região memória correspondente ao mesmo tempo Vantagens mais fácil de implementar uma falta miss nunca resulta em escritas na memória a memória tem sempre a informação mais recente sincronizada Desvantagens a escrita é lenta cada escrita necessita de um acesso à memória maior consumo de largura de banda da memória Técnicas de Write Miss 1 Write Allocate O bloco de endereços é carregado seguido de uma ação de write hit Frequentemente usado em caches com Write Back 2 No Write Allocate O bloco de endereços é diretamente modificado na memória não é carregado em cache Frequentemente usado em caches com Write Through Pontifícia Universidade Católica de Minas Gerais 131 Memória virtual Memória virtual é uma técnica que busca combinar recursos de hardware e software para usar a memória secundária como cache para armazenamento secundário Com isso é possível o compartilhamento seguro e eficiente da memória entre vários programas e superar limites de memória principal Três funções básicas são oferecidas 1 expansão permitir a utilização de memória maior que a fisicamente disponível 2 realocação proporcionar um espaço de endereçamento próprio para cada processo aplicação 3 proteção oferecer limites para utilização apenas do espaço concedido e evitar invasões de outros Os principais mecanismos empregados para implementála são 1 paginação paging divisão da memória física em blocos de bytes page frames e ajuste da memória de processo em páginas nesses blocos valores típicos podem ser 4K x86x64 ou 8K RISC 2 segmentação divisão dos espaços de endereçamento em porções segmentos para cada aplicação o endereço será composto de uma base origem do segmento e de um deslocamento o par segmentodeslocamento é convertido para um endereço linear virtual o endereço virtual é convertido para o correspondente físico enquadrado em um bloco A conversão de endereços fica a cargo de uma unidade para gerenciamento de memória MMU Memory Management Unit que utilizará tabelas de páginas pelo menos uma tabela por processo relacionando o endereço virtual com o endereço físico do bloco correspondente ou da localização da página em armazenamento secundário Para ajudar na tradução de endereços também faz uso de uma memória cache associativa TLB Translation Lookaside Buffer no qual mantém cópias dos valores mais recentes dos endereços virtuais e físicos solicitados endereço lógico dado tabela de páginas TLB miss TLB TLB hit page fault cache hit page hit cache cache miss disco miss memória principal hit Pontifícia Universidade Católica de Minas Gerais 132 Tradução do endereço virtual em endereço físico page table register virtual address virtual page number page offset 31 12 11 0 20 12 valid physical page number page table 18 if 0 page is not physical address present in memory physical page number page offset 29 12 11 0 Pontifícia Universidade Católica de Minas Gerais 133 Acesso Direto à Memória DMA Através do Acesso Direto à Memória DMA é possível transferir dados entre a memória e dispositivos periféricos sem a participação do processador O dispositivo responsável pelo controle da atividade de acesso direto à memória é chamado de controlador de DMA Há dois outros modos de se transferir dados entre memória e dispositivos de entrada e saída o programado ou o controlado por interrupções No modo de transferência programado o processador verifica se há algum dispositivo pronto para transferir dados Se houver o processador se ocupará totalmente da transferência o que ocorrerá rapidamente mas ficará empenhado durante todo o tempo em que isso durar No modo de transferência controlado por interrupções quando um dispositivo estiver pronto para transferir dados sinalizará uma interrupção ao processador O processador continuará na execução da instrução atual salvará o contexto só então permitirá a transferência o que ocorre portanto após certo atraso O processador ainda estará totalmente envolvido no processo Esses modos não são úteis para se transferir blocos de dados maiores o que poderá ser obtido pelo controlador de DMA por meio de três modos 1 burst mode uma vez no controle do barramento de sistema o controlador de DMA só irá liberálo após completar a transferência até então o processador esperará pelo uso do barramento 2 cycle stealing mode nesse modo o controlador de DMA forçará o processador a suspender suas operações e liberar o controle do barramento Após concluir a transferência devolverá o controle Permanecerá nisso subtraindo ciclos de clock a cada byte transferido 3 transparent mode o controlador de DMA tomará o acesso do barramento do sistema somente se o processador não o estiver utilizando Vantagens 1 A transferência sem o envolvimento do processador serve para aumentar velocidade da tarefa de leituraescrita 2 O acesso direto à memória reduz os ciclos de clock requeridos para se ler ou escrever um bloco de dados 3 A implementação de acesso direto à memória reduz a sobrecarga do processador Desvantagens 1 Há um custo adicional para a implementação do controlador de DMA 2 Pode ocorrer problema de coerência de cache durante o uso do controlador de DMA Pontifícia Universidade Católica de Minas Gerais 134 HLD processador HLDA controlador de DMA IOWR DRQ DACK memória dispositivo de entrada saída Quando um dispositivo de entradasaída tiver quer transferir dados depara a memória enviará ao controlador de DMA uma requisição DRQ Se o controlador a aceitar solicitará ao processador que aguarde alguns ciclos de clock enviandolhe uma solicitação HLD Ao receber a solicitação HLD do controlador de DMA o processador liberará o barramento e responderá com uma confirmação HLDA Depois que receber a confirmação o controlador de DMA informará ao dispositivo DACK que a transferência poderá ser realizada e se encarregará do barramento durante a transferência Quando concluir a operação o controlador de DMA informará ao processador e devolverá o controle do barramento para que o processamento continue a partir de onde tiver parado contador de palavras linha de dados registrador de dados linha de endereços endereço inicial read DMA request unidade de DMA acknowledgement controle interrupt write Sempre que um processador receber solicitação para ler ou gravar um bloco de dados deverá sinalizar o controlador DMA enviando as seguintes informações 1 se os dados deverão ser lidos da memória ou se serão gravados Isso seguirá por meio de linhas de controle de leitura ou escrita gravação entre o processador e a unidade lógica do controlador de DMA 2 O processador também fornecerá o endereço inicial depara o bloco de dados na memória bem como de onde deverá ser lido ou onde deverá ser escrito O controlador DMA armazenará isso em seu registro de endereço 3 O processador também enviará a quantidade de palavras ou seja quantas palavras deverão ser lidas ou escritas Isso será armazenado no contador de dados ou registrador de contagem de palavras 4 O mais importante é o endereço do dispositivo de entradasaída que deseja ler ou gravar dados Isso será armazenado no registrador de dados Pontifícia Universidade Católica de Minas Gerais 135 Paralelismo Tipos de paralelismo Há quatro tipos básicos de paralelismo ao nível de bits o qual se obtém pelo aumento da palavra do processador permitindose executar operações com dados maiores que o comprimento da mesma ao nível de instrução o qual se obtém otimizando os passos básicos para o tratamento de uma instrução busca IF instruction fetch decodificação ID instruction decode execução EX execute acesso à memória MEM e reescrita WB writeback Subescalar IF ID EX MEM WB IF ID EX MEM WB Superescalar IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB de dados o qual se obtém distribuindose dados entre diversos nodos computacionais para que sejam processados em paralelo de tarefas o qual se obtém executandose processamentos diferentes sobre um mesmo conjunto de dados ou sobre diferentes conjuntos de dados Tipos de computadores paralelos Os tipos mais comuns de computadores paralelos são com vários núcleos multicore simétricos vários processadores com uma mesma memória compartilhada distribuídos conectados por rede cluster massivamente paralelos grid e os especializados reconfiguráveis de uso geral específicos para aplicações e vetoriais Pontifícia Universidade Católica de Minas Gerais 136 Taxonomia segundo Flynn SISD SIMD Single Instruction Single Data Single Instruction Multiple Data MISD MIMD Multiple Instruction Single Data Multiple Instruction Multiple Data Single Instruction Single Data Single instruction apenas uma sequência de instruções pode ser executada por uma unidade de controle durante um ciclo de clock Single data apenas uma sequência de dados pode ser usada como entrada durante um ciclo de clock Tipo de problema uso geral Tipo de execução determinística Tipo de computador mainframes minicomputadores e a maioria dos computadores atuais Single Instruction Multiple Data Single instruction apenas uma sequência de instruções pode ser executada emr todas as unidades de controle durante o mesmo ciclo de clock Multiple data apenas uma sequência de dados pode ser usada como entrada durante o mesmo ciclo de clock Tipo de problema com grande regularidade tais como os de processamento de imagens Tipo de execução síncrona lockstep e determinística Tipo de computador arranjos de processadores pipelines vetoriais processadores com GPUs Multiple Instruction Single Data Multiple instruction sequências independentes de instruções podem ser executadas em todas as unidades de controle durante o mesmo ciclo de clock Single data apenas uma sequência de dados pode ser usada como entrada durante um ciclo de clock Tipo de problema filtros de frequência e decifrar mensagem por vários algoritmos Tipo de execução assíncrona Tipo de computador CarnegieMellon Cmmp Computer 1971 Multiple Instruction Multiple Data Multiple instruction sequências independentes de instruções podem ser executadas em todas as unidades de controle durante o mesmo ciclo de clock Single data sequências independentes de dados podem ser usadas como entrada durante um ciclo de clock Tipo de problema filtros de frequência e decifrar mensagem por vários algoritmos Tipo de execução síncrona e assíncrona determinística ou nãodeterminística Tipo de computador supercomputadores clusters grids computadores com múltiplos núcleos Pontifícia Universidade Católica de Minas Gerais 137 Taxonomia adaptada segundo Tanenbaum SISD SIMD MISD MIMD Processador Vetorial Processador Matricial Memória Compartilhada multiprocessadores Memória Distribuída multicomputadores UMA COMA NUMA MPP COW barramento comutador CC NUMA NCCNUMA Grid Hipercubo Arquiteturas de Máquinas Paralelas Pontifícia Universidade Católica de Minas Gerais 138 Arquiteturas de memória para computadores paralelos Memória compartilhada shared memory Vantagens espaço de endereçamento global facilitado para o usuário compartilhamento rápido e uniforme pelos processadores coerência de cache mantida por hardware Desvantagens falta de escalibilidade aumentar processadores implica maior tráfego no barramento maior responsabilidade para o programador para garantir acesso correto controle de sincronização maior custo para projetar e produzir memórias com múltiplos acessos Modelo UMA Uniform Memory Access Tipo de memória a mesma com tempo de acesso igual para todos os processadores Tipo de computador multiprocessadores simétricos SMP Modelo NUMA NonUniform Memory Access Tipo de memória a mesma com tempo de acesso diferente entre processadores Tipo de computador conexões entre multiprocessadores simétricos SMP barramento Memória UCP UCP UCP UCP Memória UCP UCP UCP UCP Memória UCP UCP UCP UCP Memória UCP UCP UCP UCP barramento de interconexão Memória UCP UCP UCP UCP Pontifícia Universidade Católica de Minas Gerais 139 Memória distribuída distributed memory Vantagens escalabilidade acesso rápido à memória local pelo processador não há trabalho extra overhead para manter coerência custo compatível com processadores comuns e recursos de rede Desvantagens maior responsabilidade para o programador para garantir comunicação de dados entre processadores dificuldade em manter estruturas de dados baseadas em memória global tempo de acesso não uniforme Memória híbrida hybrid distributedshared memory Modelo comum à maioria dos processadores simétricos SMP atuais Os requisitos de acesso à memória dependem da infraestrutura de rede Memória UCP Memória UCP Memória UCP Memória UCP barramento rede Memória UCP UCP UCP UCP Memória UCP UCP UCP UCP Memória UCP UCP UCP UCP barramento Memória UCP UCP UCP UCP rede Pontifícia Universidade Católica de Minas Gerais 140 Modelos de programação paralela Um modelo de programação paralela é uma abstração de arquitetura de computadores também paralela cujo objetivo é facilitar a expressão de algoritmos e a composição de programas As características de um bom modelo de programação podem ser avaliadas pelo menos dois aspectos 1 generalidade relativa à variedade de problemas que podem ter soluções expressas em diferentes arquiteturas 2 desempenho relativo à eficiência do código a ser executado em diferentes arquiteturas Formas pelas quais um modelo de programação paralela pode ser implementado podem ser 1 biblioteca adaptada para uma linguagem de programação sequencial 2 extensão de uma linguagem de programação convencional 3 linguagem de programação nova naturalmente paralela A classificação de modelos de programação pode ser feita mediante o emprego de duas grandes categorias 1 interação de processos relativa aos mecanismos pelos quais processos paralelos possam se comunicar 11 pelo uso eficiente de memória compartilhada espaço global de endereçamento onde os processos possam ler e escrever de modo assíncrono com arbítrio de condições para regular as tentativas de acessos simultâneos a fim de evitar conflitos mediante o emprego de intertravamentos semáforos e monitores exemplos Cilk CUDA OpenMP processadores convencionais com vários núcleos geralmente oferecem suporte nativo à memória compartilhada 12 por trocas de dados através de mensagens assíncronas quando a mensagem pode ser enviada antes que o receptor esteja pronto para recebêla como no caso da formalização feita em CSP Communicating Sequential Processes exemplos D Erlang Scala síncronas quando a mensagem será enviada contando que o receptor esteja pronto para recebêla como no caso de emprego do modelo de atores exemplos Ada Go Occam VerilogCSP 13 por interação implícita na qual a interação entre processos ainda que complexa e difícil de gerenciar não fique aparente ao programador e dependa mais do compilador eou do ambiente de execução linguagens para domínios específicos podem oferecer mecanismos para a execução concorrente de operações em níveis mais altos linguagens de programação funcionais procuram evitar a ocorrência de efeitos colaterais quando da execução em paralelo de funções não dependentes exemplos Concurrent Haskell Concurrent ML Pontifícia Universidade Católica de Minas Gerais 141 2 decomposição de problemas em processos executáveis paralelamente 21 Paralelismo de tarefas tem foco na execução de processos ou threads mediante comunicação por trocas de mensagens ou sinais em circuitos exemplos Verilog VHDL 22 Paralelismo de dados tem foco na execução de operações sobre grupos de dados arranjos ou matrizes nas quais se possa trabalhar de modo independente sobre partições disjuntas exemplo Tensorflow 23 Paralelismo implícito depende mais do compilador por exemplo na paralelização automática de código do ambiente de execução ou de características próprias do hardware como o paralelismo em nível de instruções oferecidos por arquiteturas superescalares Linguagens de programação paralela podem combinar mais de uma maneira de oferecer paralelismo Pontifícia Universidade Católica de Minas Gerais 142 Principais tipos de paralelistmos Memória compartilhada Tarefas compartilham um espaço de endereçamento comum no qual podem ler e escrever assincronamente Mecanismos como travas locks e semáforos semaphores podem ser usados para o controle de acesso à memória compartilhada Vantagens simplicidade no desenvolvimento de programas não há necessidade de um controle explícito da comunicação entre tarefas Desvantagens dificuldade em gerenciar a localidade dos dados manter dados locais conserva os acessos à memória evita refrescamento de cache e tráfego no barramento mas isso pode ser dificultado pelo uso de vários processadores ao mesmo tempo Threads Um processo simples pode ter múltiplas sequências de execução concorrentes cada um com acesso a dados locais mas compartilhando recursos de um mesmo programa como o espaço de memória global através do qual se comunicam usando mecanismos de sincronização Troca de mensagens Um conjunto de tarefas que trabalham sobre suas próprias memórias locais podem se comunicar através de troca de mensagens e assim agir de forma cooperativa Dados paralelos Um conjunto de tarefas trabalha sobre o mesmo conjunto de dados mas cada uma delas lida com uma porção específica da estrutura de dados Híbridos Combinações de dois ou mais modelos de programação paralela como por exemplo troca de mensagens com threads ou memória compartilhada Outro modelo pode combinar dados paralelos com troca de mensagens SPMD Single Program Multiple Data Um mesmo programa é executado por todas as tarefas simultaneamente mas não exatamente as mesmas instruções ao mesmo tempo uma vez que cada tarefa lidará com uma porção diferente do conjunto de dados MPMD Multiple Program Multiple Data Vários programas podem estar ativos trabalhando em paralelo Pontifícia Universidade Católica de Minas Gerais 143 Prova de teoremas As relações descritas podem ser utilizadas em Lógica Formal para provar teoremas Exemplo 1 Provar s dados 1 t premissa 2 t q premissa 3 q s premissa 4 q modus ponens entre 1 e 2 5 s modus ponens entre 3 e 4 cqd Exemplo 2 Provar a dados 1 a b premissa 2 b c premissa 3 c premissa 4 b modus tolens entre 2 e 3 5 a modus tolens entre 1 e 4 6 a dupla negação cqd Quantificadores A Lógica de Predicados ou Lógica de Primeira Ordem associa o uso de quantificadores Quantificador Universal x S P x para todo x em S Px é verdadeiro Quantificador Existencial x S P x para algum x em S Px é verdadeiro Os quantificadores admitem complementação não x P x x não Px não x P x x não Px Exemplo Supor o predicado abaixo devidamente quantificado x R x x 2 2 1 0 não x R x x 2 2 1 0 x R x x 2 2 1 0 o que pode ser verificado quando x 0 Pontifícia Universidade Católica de Minas Gerais 144 Exercícios propostos 1 Provar pela álgebra que a p q p p q b p p q p q c p q p q p q d p q r p q r 0 e p q r p q r p r p r 2 Fazer as tabelas e os circuitos do exercício anterior 3 Demonstrar as relações abaixo através de tabelas a x x y x absorção b x x y x absorção c x y x z x y z d x x y x y e x y y z y z x y z 4 Verificar o resultado das seguintes relações a x y x y modus ponens b x y y x modus tolens c x y x y silogismo disjuntivo d x y y z x z silogismo hipotético e x y w z xw yz dilema f x y x x y absorção g x y x simplificação h x x y adição i x x x contradição j x y x y x contradição h y y x z y xz x contradição i x y x y y y redução ao absurdo Pontifícia Universidade Católica de Minas Gerais 145 5 Verificar o resultado das seguintes relações a x y z x y z associatividade b x y z x y z associatividade c x y y x comutatividade d x y y x comutatividade e xyz xy xz distributividade f xy z xy xz distributividade g x y x y De Morgan h xy x y De Morgan i x x involução j x x x idempotência k x x x idempotência l x y x y implicação m xy xy yx equivalência n x y x y contraposição o x y z xyz exportação 6 Transformar as afirmativas abaixo em proposições a A soma de dois inteiros é maior que o primeiro b A soma de dois inteiros é maior que a diferença entre eles c O produto de um inteiro por zero é menor que outro inteiro d Se um de dois números são nulos o produto deles é zero e Se dois números são iguais a um terceiro então são iguais 7 Construir um circuito para identificar se dois bits são iguais 8 Construir um circuito capaz de fornecer a tabela abaixo x y z f xyz 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 Pontifícia Universidade Católica de Minas Gerais 146 9 Simplificar a expressão lógica abaixo x 0 e y 0 ou não x 0 ou z 0 10 Identificar a equação do circuito abaixo pela soma de produtos SoP 11 Identificar a equação do circuito anterior pelo produto das somas PoS 12 Construir um circuito equivalente ao da questão 10 usando apenas portas NAND 13 Construir um circuito equivalente ao da questão 10 usando apenas portas NOR 14 Montar um diagrama de um somador completo de 2 palavras de 2 bits cada 15 Construir um circuito equivalente ao da questão 14 usando apenas portas NAND 16 Construir um circuito equivalente ao da questão 14 usando apenas portas NOR 17 Simplificar por mapa de Karnaugh abcdabcda bcda b cda b c da b cda b c d 18 Demonstrar a validade do seguinte argumento 1 x 6 2 y 7 ou x y y 4 e x y 3 y 4 x 6 4 x 6 x y x y 19 Verificar se as proposições são falsas ou verdadeiras a n N n4 3 b n N n3 7 c n N n4 7 d n N n3 2 20 Sendo A 12345 determinar a negação de a n A x4 10 b n N x4 10 y z x s