Index

Algoritmo de Euler (05-03-2006 )
Index
  • Introdução
Introdução à temática
Objectivos e consolidação de conhecimentos
  • Algoritmo de Euler
Definição do algoritmo
Algoritmo Passo a Passo
Passos e construção layout
Factores a ter em conta
  • Conclusões
Considerações Finais

Outros Recursos
FAQ
links uteis

<aetheon Design>  by Oscar Brito


Introdução á temática

Introdução à temática
Os programas de CAD de geração automática de layouts de circuitos digitais produzem layouts VLSI de grande qualidade, a partir de descrições do tipo netlist, ou a partir de expressões booleanas. Os layouts gerados podem ser baseados em vários tipos de estruturas, tais como ROMs/RAMs, PLAs, standard-cells, etc.
Esses programas usam métodos sistemáticos para mapear netlists ao nível do transístor, em layouts ao nível físico, com a vantagem de serem isentos de erros e de se diminuir o seu tempo de concepção.
Uma estrutura baseada em standard-cells sintetiza uma função booleana numa estrutura regular, constituída por uma linha de transístores pMOS e uma linha de transístores nMOS.
As fitas de polissilício são verticais (variáveis de entrada), e os sinais VDD e VSS existem na horizontal, nas extremidades superior e inferior, respectivamente.

De forma a permitir a interligação entre transístores é possível "encostar" a "source" de um transistor ao "drain" do outro, e vice-versa, tal como verificamos na figura,

De modo a perceber melhor o que foi aqui descrito, siga o link:
Exemplo união entre transístores

*(como se tratam de transistores em tecnologia CMOS não existe nenhuma diferença fisica, logica,..., entre a "source" e a "drain").

voltar


Algoritmo de Euler

Objectivos e consolidação conhecimentos
De modo a perceber a vantagem que o algoritmo de Euler nos traz, precisamos de ter presentes algumas noções essenciais para a construção de uma ideia bem formada sobre este tema.
Sabemos que uma função lógica, por exemplo, pode assumir muitas representações, sempre garantindo a sua funcionalida.
Portanto podemos dizer que,
  • representação em Standard-cells
  • rede n/p
  • ...
São isomorfismos de uma determinada função lógica. Verificamos atrás que as tiras de polissilício são aquelas que irão conduzir os sinais de entrada, e sabemos que "encostando" os transístores uns aos outros (cuidado!!) reduzimos o número de tiras de metal...como verificamos na figura:

1) "abutment"

2) standard cells com transistores em "abutment"
O exemplo anterior sugere que a optimização de um layout baseado em standard-cells passa por maximizar o número de vezes em que é possível realizar a ligação entre dois transístores por simples abutment. Para que isso seja possível, transístores adjacentes (em série ou em paralelo) devem ser colocados em colunas adjacentes do layout.
Tendo chegado a este raciocínio torna-se trivial que a optimização passa pela ordem onde as tiras de polisilissío interrompam o menor numero de vezes as tiras de difusão n e p, para que figuras como a anterior sejam possíveis.


Exemplo 1
A figura seguinte é uma possível implementação do layout do último andar desse circuito, seguindo a abordagem standard-cells.

Esta abordagem em standard cells é bastante fácil de construir, pois basta apenas interligar os drenos e sources dos transistores tal e qual como estes se encontram na rede n/p.
De forma a visualizar esta construção foi feito um 'gif' exemplificativo. Esta construção foi feita de uma forma mais trivial do que na imagem de cima, de forma a assegurar uma melhor compreensão do tema.

ver GIF com demonstração
Resultados Obtidos

1) rede pMos 2) standard-cells exemplificativo de (1)


Definições e Considerações

Transistor P\Mos e N\Mos

  1. Todos os potenciais da rede n/p são vértices no grafo.

  2. Cada transístor é representado por um arco de dois vértices, ligando os potencias da drain e source. A cada arco corresponde uma label, de forma a identificá-lo.

  3. Tal como na rede n/p, também aqui os grafos da rede n e da rede p são duais.

  4. Os arcos da rede n e rede p são desenhados de forma e em sentidos (horizontal e vertical) diferentes.

Logo para uma rede do tipo:

rede n/p

correspondente grafo

Algumas Considerações

Tal como iremos verificar mais á frente, o caminho de Euler, tem a seguinte definição:
  • Se num grafo todas as séries e todos os paralelos de arcos tiverem um número ímpar de entidades, então existe um caminho de Euler
Encontrar um caminho de Euler, procurando arranjar uma solução que permita arrumar para o início e para o fim do caminho os arcos fictícios; se isto for possível, as fitas de difusão n e p vão ser contíguas, embora o teorema de Euler não o garanta.


Passos do Algoritmo
Recursos Disponíveis:
  • Apresentação PowerPoint explicativa do algoritmo de Euler
  • Video Com explicação dos Passos

De forma simples define-se os passos dos algoritmo de forma recursiva (aplica-se os conceitos apreendidos anteriormente)

  • Regra 1: O número de transístores em paralelo têm de ser impar, senão acrescenta-se um arco fictício.
  • Regra 2: Se não se poder aplicar a regra 1 em mais nenhum sítio, então aplica-se a caminho Euler, senão aplica-se recursivamente a regra 1.
  • Caminho Euler: Definem-se sentidos e a partir destas definições encontra-se um caminho que possa atravessar os potenciais de um lado para o outro. (*)
  • Extrair Ordem das fitas Poly;

(*) arcos ficticios representam interrupções na fita de difusão

Existem contudo alguns factores que devem ser respeitados e tidos em conta para uma boa construção do grafo, seguindo o algoritmo de Euler. Para os consultar siga o link: Factores a ter em conta

Podemos agora passar a exemplificar o modo de funcionamento deste algoritmo. De modo a simplificar este processo, irá apresentar-se um exemplo ilustrativo de todos os passos do algoritmo.

Sendo assim,
1ºPasso
Aplica-se a regra 1 pois o número de transistores em paralelo eram pares, logo criaram-se dois arcos ficticios - p1
2ºPasso (opcional)
Simplificou-se o sub-grafo que representam a rede em paralelo, reescrevendo-as com o arco ficticio p2.
3ºPasso (opcional)
Simplificação igual ao 2ºPasso
4ºPasso
Definição de sentidos:
  • rede P: de baixo para cima
  • rede N: de direito para esquerda
5ºPasso(opcional)
Representação nos arcos com os sentidos definidos.
6ºPasso(opcional)
Encontra-se o caminho de Euler. Verifica-se então onde as interrupções das fitas de difusão se encontram (P1).

A partir do 6ºPasso podemos construir o Stick Diagram da rede n/p em cima descrita,

Reparamos então que mediante a leitura do grafo definido no 6ªPasso se torna trivial a construção do respectivo Stick Diagram.


Factores a ter em conta
Aqui iremos abordar alguns factores que não sendo assim tão evidentes merecem um pouco de atenção.
  • Escolha do caminho de Euler - Arcos Ficticios

Como os arcos fictícios representam as interrupções na fita de difusão, iremos procurar intercalá-los o menos possível, para que não existam conflitos nem uma grande complexidade no esquema do layout.
  • Como retirar a ordem das tiras de polissilício
Tomando este grafo como exemplo, retira-se que a ordem
óptima das tiras de polisilício na rede p-Mos é:
  • A,C,B,D com uma interrupção entre C e B.


FAQ
Qual o objectivo do algoritmo de Euler?
link
O que é o "abutment"?
"abutment" é a palavra chamada ao "encosto" de dois transístores. Normalmente é utilizada uma tira de metal para unir o dreno de um transístor á source de outro. Usando "abutment" estes não precisam de qualquer material para assegurar a sua ligação.
O que significam arcos fictícios?
Arcos ficticios representam as interrupções nas fitas de difusão entre transistores. ver link
Qual o numero minimo de interrupções numa rede p-MOS?
O número mínimo é 1, pois o número mínimo de transístores numa rede p-Mos é 1.
O que é o caminho de Euler?
Se num grafo todas as séries e todos os paralelos de arcos tiverem um número ímpar de entidades, então existe um caminho de Euler, sendo esta a heurística que o define. ver link.
É sempre possivel construir um layout optimizado, segundo este algoritmo?
Falso, o algoritmo de Euler não garante que as fitas de difusão sejam contíguas, embora se trate de um algoritmo com grande fiabilidade.
São precisos cuidados especiais com o adicionar de arcos ficticios?
É necessário intercalar o menos possível estes arcos, pois estes simbolizam as interrupções nas fitas de difusão!!!


Links e Documentação
Links
História e Problemas derivados do algoritmo
Teoria dos Grafos (Algoritmo de Euler)
Ferramentas de Grafos (GraphViz)

Grafos como Estrutura dados (Introdução Teórica)

Documentação

Modulo 4 (Algoritmo de Euler) - PDF
SlidesPowerPoint
Video Demonstrativo


Considerações Finais
Como considerações finais aborda-se os objectivos, bem como todas as características deste algoritmo, sendo este um resumo de tudo o que foi dito antes.
Objectivos do Algoritmo de Euler
  • optimizar a ordem das tiras de polisilíssio: passa por maximizar o número de vezes em que é possível realizar a ligação entre dois transístores por simples "abutment".
Sendo assim podemos concluir que o algoritmo de euler permite um maior aproveitamento das fitas polly, evitando a utilização excessiva deste tipo de material. Podemos também concluir que se trata, na maioria dos casos, de uma simplificação do layout gerado por uma rede n/p. Sendo estas as razões que impõe a utilização desta filosofia.


Algoritmo de Euler definições
Algoritmo de Euler
  • Definições e Considerações
  • Passos do algoritmo


Ulead GIF Animator

voltar


Video

voltar