Sistemas Digitais - Otimizacoes e Tradeoffs - Frank Vahid

Digital Design Copyright 2006 Frank Vahid 1 Sistemas Digitais Capítulo 6 Otimizações e Tradeoffs Slides to accompany the textbook Digital Design First Edition by Frank Vahid John Wiley and Sons Publishers 2007 httpwwwddvahidcom Copyright 2007 Frank Vahid Instructors of courses requiring Vahids Digital Design textbook published by John Wiley and Sons have permission to modify and use these slides for customary courserelated activities subject to keeping this copyright notice in place and unmodified These slides may be posted as unanimated pdf versions on publiclyaccessible course websites PowerPoint source or pdf with animations may not be posted to publiclyaccessible websites but may be posted for students on internal protected sites or distributed directly to students by other electronic means Instructors may make printouts of the slides available to students for a reasonable photocopying charge without incurring royalties Any other use requires explicit permission Instructors may obtain PowerPoint source or obtain special use permissions from Wiley see httpwwwddvahidcom for information Prof Luciano C A Pimenta Tradução e Adaptação para o Português Prof Ricardo de Oliveira Duarte DELT EE UFMG Digital Design Copyright 2006 Frank Vahid 2 Introdução Aprendemos como projetar circuitos digitais combinacionais Será que podemos projetar circuitos mais eficientes Vamos considerar dois critérios para tomada de decisões em projetos Atrasos delays o tempo em que uma mudança de valor das entradas produz um valor estável e correto na saída Tamanho o número de transistores Em uma estimativa rápida assuma que Cada porta lógica tem um atraso de 1 atrasoporta Cada entrada de uma porta demanda 2 transistores Ignore portas NOT inversoras 61 16 transistores 2 atrasosporta F1 wxy wxy F1 wxy wxy a 4 transistores 1 atrasoporta F2 F2 wx b w x wxyy wx Transformando F1 em F2 significa uma otimização Melhora em todos os critérios de interesse que acabamos de selecionar c 20 15 10 5 F1 F2 1 2 3 4 Atrasos atrasoportas tamanho transistores Note Slides with animation are denoted with a small red a near the animated items Digital Design Copyright 2006 Frank Vahid 3 Introdução Tradeoff Relação de compromisso entre critérios de otimização Melhora alguns critérios mas piora outros conforme critérios de interesse no projeto Transformando G1 em G2 representa um tradeoff Alguns critérios apresentam resultados melhores enquanto pioram outros 14 transistores 2 atrasosporta 12 transistores 3 atrasosporta G1 G2 w w x y z x w y z G1 wx wy z G2 wxy z 20 15 10 5 G1 G2 1 2 3 4 Atrasos atrasoporta tamanho transistores Digital Design Copyright 2006 Frank Vahid 4 Introdução Preferimos o caso ótimo mas conviveremos com tradeoffs na maioria dos casos Podemos fabricar um carro que é o mais confortável o mais econômico e o mais rápido Mas certamente algumas dessas características serão prejudicadas para se alcançar os objetivos atraso atraso Otimizações Tradeoffs Todos os critérios de interesse são melhorados ou pelo menos mantidos com o mesmo valor Alguns critérios de interesse são melhorados enquanto outros não tamanho tamanho Digital Design Copyright 2006 Frank Vahid 5 Otimizações em Lógica Combinational e Tradeoffs Otimização em Lógica de Doisníveis usando métodos algébricos Objetivo circuito somente com 2 níveis de portas OR de portas AND com o mínimo de transistores Definimos o problema de forma algébrica Soma de produtos gera lógica de 2 níveis F abc abc está na forma de soma de produtos G wxy z não Transforme a equação de soma de produtos de forma a ter menos termos e menos literais Cada literal e cada termo é convertido em uma entrada por porta cada qual é convertido em transistores Ignore portas NOT para simplificar 62 F xyz xyz xyz xyz F xyz z xyz z F xy1 xy1 F xy xy 0 1 x y n y x 0 1 m m n n F 0 1 y m y x x F x y x y m n 4 literais 2 termos 6 entradasporta 6 entradasporta 12 transistores Nota Assumindo 4transistores circuitos ANDOR de 2ientradas Na realidade somente NANDNOR são usadas Exemplo Digital Design Copyright 2006 Frank Vahid 6 Método Algébrico para Minimização de Número de transistores com lógica de 2níveis O exemplo anterior mostrou métodos de otimização algébricos mais comuns Coloque a equação na forma de soma de produtos Simplifique o máximo possível ab ab ab b a1 a Combinando termos para eliminar variáveis Duplicar termos às vezes é necessário para se alcançar uma maior simplificação Note que não altera em nada a função c d c d d c d d d d Após combinar termos repetidos podese alcançar uma maior simplificação F xyz xyz xyz xyz F xyz z xyz z F xy1 xy1 F xy xy F xyz xyz xyz F xyz xyz xyz xyz F xyzz xzyy F xy xz G xyz xyz xyz xyz G xyzz xyzz G xy xy novamente G xyy G x a a a Digital Design Copyright 2006 Frank Vahid 7 Mapas de Karnaugh para Minimização de Número de transistores com lógica de 2níveis Mapas de Karnaugh Mapas K Método Gráfico criado para encontrarmos termos que podem ser combinados para eliminar variáveis de forma a obter o mínimo Mintermos diferindose de uma variável ficam adjacentes vizinhos no mapa Podemos visualizar claramente os casos possíveis de combinação de termos olhamos para os 1s adjacentes Para F vimos duas situações Círculo do topo a esquerda gera a redução de xyzxyz xyzz xy1 xy Desenhe circulos escreva o termo que tem todos os literais exceto os literalis que mudam no interior do círculo Círculo xy x1 y1 em ambas as células do círculo mas z muda z1 em uma célula 0 na outra Função minimizada OR dos termos encontrados F xyz xyz xyz xyz 0 0 0 0 00 01 11 10 0 1 F yz x 1 xy 1 1 0 0 00 01 11 10 0 0 0 1 1 1 F yz x xy xyz 00 01 11 10 0 1 xyz xyz xyz xyz xyz xyz xyz F yz x 1 Note que não fica ordenado de forma binária Considere esquerda e direita também vizinhos 1 1 F xy xy Mais fácil que o método algébrico F xyz xyz xyz xyz F xyz z xyz z F xy1 xy1 F xy xy Kmap a a a Digital Design Copyright 2006 Frank Vahid 8 Mapas K Quatros 1s vizinhos significa que duas variáveis podem ser eliminadas Desenhe um círculo grande envolvendo os 4 1s simplifica a transformação algébrica acima G xyz xyz xyz xyz G xyz yz yz yz deverá ser 1 G xyzz yzz G xyy G x 0 0 0 0 00 01 11 10 1 1 0 1 1 1 G yz x x 0 0 0 0 00 01 11 10 1 1 0 1 1 1 G yz x xy xy Desenhe o maior círculo possível ou você obterá mais termos do que você realmente precisará Digital Design Copyright 2006 Frank Vahid 9 Mapas K Quatro células vizinhas podem aparecer em formato de quadrado É permitido envolver um 1mais de uma vez Assim como um termo duplicado Lembre c d c d d Não há necessidade aparente de se cobrir um 1 mais de uma vez Produz termos adicionais situação não minimizada 0 1 1 0 00 01 11 10 0 1 0 1 1 0 H yz x z H xyz xyz xyz xyz xy aparece em todas combinações 0 1 0 0 00 01 11 10 1 1 0 1 1 1 I yz x x yz Os dois círculos é a forma reduzida de I xyz xyz xyz xyz xyz I xyz xyz xyz xyz xyz xyz I xyz xyz xyz xyz xyz xyz I yz x 1 1 0 0 00 01 11 10 0 1 0 1 1 0 J yz x xz yz xy a a a Digital Design Copyright 2006 Frank Vahid 10 Mapas K Círculos podem atravessar da direita para a esquerda Lembrem os lados são vizinhos Mintermos se diferem em uma única variável Círculos deverão ter 1 2 4 ou 8 células 3 5 ou 7 não são permitidos 357 não correspondem a transformações algébricas válidas para eliminar variáveis Circular todas células também é permitido Produz uma função 1 0 1 0 0 00 01 11 10 1 0 0 1 0 1 K yz x xz xyz 0 0 0 0 00 01 11 10 1 1 0 1 1 0 L yz x 1 1 1 1 1 00 01 11 10 1 1 0 1 1 1 E yz x PROIBIDO Digital Design Copyright 2006 Frank Vahid 11 Mapas K de 4 variáveis Mapas K de 4 variáveis seguem o mesmo princípio Células vizinhas diferemse de uma única variável EsquerdaDireita são vizinhas TopoBase também são Mapas de 5 e 6 também existem Mas são mais difíceis de visualisar mas também são ainda viáveis Mapas de 2 variáveis existem Mas não são muito úteis melhor simplificar algebricamente 0 0 1 0 00 01 11 10 1 1 00 01 1 0 0 0 1 0 0 0 11 10 1 0 F yz wx yz wxy 0 1 1 0 00 01 11 10 0 1 00 01 1 0 0 1 1 0 0 1 11 10 1 0 G yz wx z 0 1 0 1 F z y Gz Fwxyyz Digital Design Copyright 2006 Frank Vahid 12 Mapas K para Minimização de Número de transistores com lógica de 2níveis Método geral 1 Converta a equação na forma de soma de produtos 2 Coloque 1s nas células referentes a cada termo da equação 3 Circule todos os 1s desenhando o menor número de maiores círculos possíveis com cada 1 incluído em pelo menos um círculo Escreva o termo correspondente para cada círculo 4 Faça um OR de todos os termos resultantes para obter a função minimizada Exemplo Minimize G a abc bc bc 1 Converto em soma de produtos G a abc bc bc 2 Coloco 1s nas respectivas células 0 0 00 01 11 10 0 1 G bc a 1 bc 1 abc 1 1 1 1 a a 3 Circulo os 1s 1 0 0 1 00 01 11 10 1 1 0 1 1 1 G bc a a c 4 Faço um OR com os termos circulados G a c Digital Design Copyright 2006 Frank Vahid 19 Conceitos básicos envolvendo Automação de Minimização em Lógica de 2 níveis Definições continuação Implicantes primos PI essenciais O único implicante primo que cobre um mintermo em particular dos elementos do onset Importancia Devemos incluir todos os PI essenciais em um agrupamento gerador cobertura 1 1 0 0 0 00 01 11 10 1 0 1 1 1 G yz x não essencial não essencial yz xy xz xy essencial 1 essencial 1 Digital Design Copyright 2006 Frank Vahid 20 Método de Automação de Minimização em Lógica de 2 níveis Passos 1 e 2 são exatos Passo 3 Complicado Checar todas as possibilidades produz a solução ótima mas é computacionalmente lento Solução Checar algumas soluções mas não todas solução heurística Digital Design Copyright 2006 Frank Vahid 21 Exemplo de Minimização em Lógica de 2 níveis automatizada QuineMcCluskey 1 Determinamos todos os implicantes primos 2 Adicionamos os PIs essenciais ao agrupamento final Marcamos com fonte itálico os 1s que já foram cobertos Somente um único 1 sobrou 3 Cubro o mintermo que sobrou com um Pis não essencial Escolho um dos 2 possíveis PIs 1 1 1 0 00 01 11 10 1 0 0 1 0 1 I yz x yz xz xz c 1 1 0 00 01 11 10 1 0 0 1 0 1 I yz x 1 1 1 0 00 01 11 10 1 0 0 1 0 1 I yz x xy yz xz xz b xy yz xz xz a 1 1 1 Digital Design Copyright 2006 Frank Vahid 22 Problemas de Métodos que enumeram todos os Mintermos ou Computam todos os Implicantes Primos Muitos mintermos para funções de muitas variáveis Funções com 32 variáveis de entrada 232 4 bilhões de mintermos possíveis Muito tempomemória computacional Muito tempo de processamento para gerar todos os implicantes primos Comparando cada mintermo com cada outro mintermo para 32 variáveis é 4 billion2 1 quadrilhão de operações computacionais Funções com muitas variáveis poderiam demandar dias meses anos ou mais em tempo computacional Não é razoável Digital Design Copyright 2006 Frank Vahid 23 Solução para o Problema na forma Computacional Solução Não gerar todos os mintermos nem todos os implicantes primos Em vez disso basta tomar a equação de entrada e tentar iterativamente melhorála Ex F abcdefgh abcdefgh jklmnop Obs 15 variáveis poderia produzir milhares de mintermos Mas pode minimizar apenas combinando os dois primeiros termos F abcdefghh jklmnop abcdefg jklmnop Digital Design Copyright 2006 Frank Vahid 24 Minimização em Lógica de 2 níveis usando o Método Iterativo Método Aleatoriamente faça uma operação de expansão verifique se produziu alguma melhoria Expansão remoção de uma variável de um termo Assim como expandir um círculo em um mapa K ie Expandindo xz para z OK mas expandir xz para x não OK na função mostrada Depois de expandir remova outros termos cobertos pelo novo termo expandido Continue iterando até não obter mais melhorias Ex F abcdefgh abcdefgh jklmnop F abcdefg abcdefgh jklmnop F abcdefg jklmnop 0 1 1 0 00 01 11 10 0 1 0 1 1 0 I yz x 0 1 1 0 00 01 11 10 0 1 0 1 1 0 I yz x xyz xz xyz z a b xyz xyz xz x httpenwikipediaorgwikiEspressoheuristiclogicminimizer Logic Friday Espresso Windows httpsontrakcomdefaultaspx Otimização em Lógica MultiNível Tradeoffs de Velocidade de ProcessamentoTamanho Nem sempre precisamos da velocidade de processamento proporcionada pela lógica de 2 níveis A lógica multinível pode produzir circuitos com um número menor de portas Exemplo F1 ab acd ace F2 ab acd e ab cd e Técnica Eliminar literais xy xz xyz 22 transistores 2 atrasosporta a b c d e 6 4 F1 ab acd ace a 16 transistores 4 atrasosporta F2 abcde b Atraso atrasosporta 4 Transistor atraso 4 F1 F2 F2 F1 c 25 Exemplo multinível Aplique lógica multinível para reduzir o número de transistores de F1 abcd abcef abcd abcef abcd ef Produz um número menor de portas portanto um número menor de transistores 22 transistores 2 atrasosporta 18 transistores 3 atrasosporta F1 F2 20 Transístor atraso a b c d e f 6 4 F1 abcd abcef a 4 F2 abcd ef b Atraso atrasosporta F1 F2 c 26 Exemplo multinível Caminho não crítico Caminho crítico caminho mais lento longo entre uma entrada e a saída Otimização reduzir o número de transistores dos caminhos não críticos usando lógica multinível 26 transit o r s 3 gatedel ays 22 transistor s 3 gatedel ays 6 4 F1 abc dfg efg a 6 4 F2 abc defg b Atraso atrasosporta delay gatedel ays F1 F2 27 Métodos Automatizados para Otimização de Lógica Multinível As principais técnicas usam métodos iterativos heurísticos Baseados em várias operações lógicas Fatoração ou colocar termos em evidência para reduzir o número de portas xy xz xyz Expansões e outras técnicas Aleatoriamente aplique uma operação verifique se produz melhores resultados Eventualmente aceitase situações que possam provocar uma piora localizada desde que essa piora possa gerar uma equação que poderá ser melhor manipulada Continue tentando até não encontrar melhorias Não é garantido de se encontrar o melhor circuito mas certamente um dos melhores 28 Mapas K para Minimização de Número de transistores com lógica de 2níveis Exemplo Minimizar H abcd cd abcd abcd abd abcd 1 Converto para soma de produtos H abcd abcd abcd abcd abd abcd 2 Coloco 1s nas células do Mapa K 3 Circulo os 1s 4 Faço um OR dos termos obtidos H bd abc abd EsquerdaDireita são vizinhos TopoBase são vizinhos 13 Entradas Indiferentes X Dont Cares O que fazer se uma entrada em particular não interessa para uma dada função Ex Minimize F xyz dado que xyz xyz000 não está previsto para ocorrer e xyz xyz101 também não Portanto não importa qual será a saída F quando xyz ou xyz for 1 porque esses casos não estão previstos para ocorrer Logo faça F ser 1 ou 0 para esses caso de forma a melhor minimizar a equação final No mapa K Escreva Xs dont cares para essas Inclua X no círculo SOMENTE se ele contribuir para minimizar a equação Não inclua outros Xs F x y z yz 0 0 0 0 0 1 1 1 x y z yz unneeded x y z yz 0 0 0 0 0 1 1 1 x y z yz 0 0 0 0 0 1 1 1 14 Exemplo de Minimização com Dont Cares Minimizar E abc abc abc Dado as seguintes situações onde ocorre dont cares abc abc Obs Use dont cares com atenção Certifiquese que o termo é realmente irrelevante para a função pedida F bc ac b a 00 01 11 10 0 1 1 1 F ac b 15 Exemplo de Minimização com Dont Cares Chave Deslizante Sliding Switch Chave com 5 posições Produz a posição em binário com 3bits Queremos um circuito que Produza saída 1 quando a chave estiver na posição 2 3 or 4 Produza saída 0 quando a chave estiver na posição 1 or 5 Observe que a entrada de 3bits nunca produzirá uma saída binária para o detector nos casos 0 6 ou 7 Considereas como entradas dont care para essas combinações C G y x 1 234 detector G xy xyz Sem dont cares G xy xyz G y z x 00 01 11 10 1 0 0 0 G y z x 00 01 11 10 1 0 0 0 Com dont cares G y z 16 Automatizando o processo de Minimização em Lógica de 2 níveis Minimizando a mão Complicado para funções com 5 ou mais variáveis Podemos não obter a menor combinação agrupamento de 1s dependendo da ordem que escolhermos Sujeito a erros ser humano Minimização realizada por ferramentas computacionais Algoritmo exato encontra as soluções ótimas Heurísticas encontram boas soluções mas não necessariamente as melhores Somente 3 termos F y z x yz yz xz 00 01 11 10 1 1 1 1 4 termos 1 0 10 17 Conceitos básicos envolvendo Automação de Minimização em Lógica de 2 níveis Definições Onset Todos os mintermos que produzem F1 Offset Todos os mintermos que produzem F0 Implicante Qualquer termo mintermo ou não que produza F1 No mapa K é representado por qualquer círculo válido não necessariamente o maior círculo Cobrir Implicante xyz cobre os mintermos xy e xyz Expandir um termo remover uma variável círculo maior no mapa K xyz xy é uma expansão de xyz 4 implicantes de F Obs Usamos o mapa K aqui somente como uma forma de ilustrar os conceitos ferramentas computacionais não usam mapas K Implicantes primos Máximo Implicante expandido qualquer expansão cobriria 1s não pertencentes a um único onset xyz e xy acima Mas não xyz ou xyz eles poderiam ser expandidos 18