Capítulo 6 - sites.poli.usp.brsites.poli.usp.br/d/psi5742/pdf/cap6.pdf · 133 Capítulo 6 Mapeamento Tecnológico A síntese lógica pode ser divida em duas tarefas principais. A

133

Capítulo 6

Mapeamento Tecnológico

A síntese lógica pode ser divida em duas tarefas principais. A decomposição lógica e a

minimização multinível formam a primeira etapa, que constitui o que se chama de

síntese

independente da tecnologia

. A segunda etapa é a fase ligada à tecnologia onde o circuito será

implementado. É chamada de

mapeamento tecnológico

, ou apenas de mapeamento, para

simplificar. O mapeamento consiste na implementação de uma rede Booleana em termos de

dispositivos providos pela tecnologica alvo.

Existem diversas técnicas para realizar o mapeamento. Estas são adaptadas para explorar

aspectos específicos da tecnologia de implementação associada a uma função custo que deverá

ser minimizada. As tecnologias ou estilos de implementação, como poderíamos também chamá-

las, provêem dispositivos para implementação de circuitos lógicos que podem ser bastante

diferenciados. Uma taxonomia que divide os componentes em função da sua natureza poderia

ser como segue:

•

dispositivos programáveis

: define toda uma gama de componentes cuja

característica principal é que sua funcionalidade pode ser especificada pelo

mapeador. Duas famílias principais aqui são os dispositivos de programação fixa

e os reprogramáveis. Os de programação fixa não podem ser alterados uma vez

definida a sua programação. Os dispositivos reprogramáveis podem ter seu

comportamento alterado por ocasião da sua utilização, podendo ser reutilizados

em outras aplicações. Normalmente os dispositvos programáveis são baseados em

um único módulo para implementação de funções lógicas que é arranjado em

forma de matriz sobre a pastilha de silício. Em algumas tecnologias as

interconexões entre os módulos também são programáveis [ElG89, Xil94].

•

biblioteca de células

: são tecnologias onde os componentes são pré-definidos e

disponibilizados através de uma biblioteca finita de dispositivos. Cabe ao

134

Capítulo 6. Mapeamento Tecnológico

mapeamento selecionar dentre os dispositivos disponíveis o conjunto que melhor

implementa a rede Booleana.

•

geradores de módulos

: em estilos de implementação baseados em geradores de

módulos não existe um dispositivo base prédefinido como nos casos acima. O

gerador é um programa que cria um módulo que implementa uma determinada

função lógica, especificada usualmente como uma rede de transistores [Mor93].

Geradores parametráveis são aqueles onde algumas características do módulo

podem ser especificadas ou onde alguns limites de granzedas físicas podem ser

estipulados. Por exemplo, restrições derivadas do planejamento da planta baixa do

circuito podem indicar que o módulo tenha uma largura aproximadamente igual

ao dobro da altura, ou que determinados transistores devem ser dimensionados

para ter uma capacidade de acionamento maior do que outros. Geradores de

módulo, portanto, oferecem maior flexibilidade em termos de dispositivos do que

os estilos de implementação anteriores.

O mapeamento pode ser modelado como um processo que recebe como entrada uma rede

Booleana e produz como saída uma rede de dispositivos da tecnologia selecionada. Os

algoritmos de mapeamento se preocupam apenas com a seleção dos dispositivos que

implementam a rede da maneira mais econômica. O processo de estipular a localização dos

dispositivos na pastilha de silício e realizar a sua interconexão física é uma etapa posterior ao

mapeamento, realizada pelo sistema de síntese de leiaute ou síntese física. Uma ilustração do

processo de síntese é apresentada na figura 6.1.

Figura 6.1. Mapeamento tecnológico.

O estilo de leioute mais utilizado é certamente o de biblioteca de células. As bibliotecas

de células contém tipicamente as portas elementares E, OU e NÃO, suas negações NE, NOU e

um conjunto de portas mais complexas. É comum encontrar-se também OU-exclusivo e portas

y2 x1 y1⋅=

y1 x2 x3∨=

x2

x3

y3 x4 y1∨=

x1

x4

y4 y2 y3 x5∨⋅=

f

Biblioteca

x5

x4

x1

x2

x3 f

y2

y3

y1


135

complexas do estilo EOUI (inversor), OUEI, eventualmente com inversores nas entradas. A

complexidade da biblioteca é um fator importante durante o mapeamento, uma vez que ela será

consultada diversas vezes durante o processo.

Na verdade, o termo biblioteca de células é bastante genérico, pois mesmo dispositivos

programáveis podem ser fornecidos ao mapeamento na forma de biblioteca. Basta predefinir

uma série de configurações para os dispositivos e arranjá-los na forma de uma biblioteca,

abstraindo do mapeamento a tarefa de programá-los. Esta abordagem é utilizada algumas vezes

pois permite adaptar as técnicas de mapeamento em biblioteca, mais amadurecidas, para

elementos programáveis. A tendência, entretanto, é o desenvolvimento de algoritmos

específicos não apenas para dispositivos programáveis em geral, mas para cada tipo particular

de dispositivo.

Neste capítulo analisaremos técnicas genéricas de mapeamento que foram derivadas do

mapeamento em biblioteca de células, mas que podem igualmente ser aplicadas a outros estilos

de implementação de circuitos. O ponto de partida é uma rede Booleana otimizada durante a

síntese multinível. Esta rede é manipulada de forma a associar a cada nó ou conjunto de nós um

dispositivo da tecnologia alvo. O processo de encontrar um determinado dispositivo que

implemente uma subfunção da rede é chamado de

casamento ou mapeamento de portas

. Um

dispositivo

casa

com uma subfunção se esta pode ser implementada através do dispositivo. No

momento em que associamos um subconjunto de nós a um dispositivo dizemos que os nós

foram

cobertos

com o dispositivo. O mapeamento termina quando todos os nós da rede forem

cobertos. Por esse motivo denomina-se este processo de

cobertura da rede

.

Para exemplificar o processo, considere a rede da figura 5.2 composta por nós que

realizam operações E com apenas duas entradas e uma biblioteca hipotética que implementa

portas E com 2, 3 e 4 entradas. A associação de uma porta com cada nó é o que se chama de

mapeamento

trivial

, que é mostrado em (a). Naturalmente, é necessário que cada nó descreva

uma função simples o suficiente para ser implementada por uma única porta. Diversos sistemas

de mapeamento partem deste princípio, ou seja, decompor primeiro a rede Booleana em uma

rede de portas simples cujo mapeamento é trivial e, a seguir, procurar otimizar o mapeamento

inicial. Em (b) e (c) temos mapeamentos alternativos, onde mais de um nó é coberto por uma

mesma porta. Em (b) dois nós implementando a função E com suas entradas são agrupados,

formando um único nó com três entradas. Utiliza-se aqui a propriedade da operação E de que

. O resultado é que a rede de 4 funções E conectadas segundo

mostra a rede pode ser implentada através de duas portas E com 3 entradas. Outra alternativa,

mostrada em (c), é agrupar 3 funções E em uma porta de 4 entradas, conforme indicado. (a), (b)

e (c) ilustram 3 coberturas alternativas da rede. A escolha dos componentes da biblioteca que

podem implementar agrupamentos de nós caracteriza o processo de casamento de portas.

A avaliação do custo de cada mapeamento depende do custo de cada porta. A biblioteca

de células contém informações relativas ao tamanho, tempo de resposta e potência dissipada

pelos componentes. Estas figuras de mérito podem ser utilizadas para uma primeira estimativa

a b⋅( ) c⋅ a b c⋅( ) a= b c⋅ ⋅ ⋅=

136


do custo da rede. Outro fator importante para a avaliação de custo são as interconexões. Durante

longo tempo as grandezas acima era determinadas predominantemente pelos dispositivos. A

influência na área do circuito e no atraso de sinais devido às conexões era relativamente

pequena se comparada com a influência das portas. Desta forma, era perfeitamente razoável

estimar-se o custo do circuito como sendo a soma dos custos individuais de cada porta que o

constitui. Isso era particularmente possível devido a dois fatores: o tamanho dos dispositivos e

a baixa complexidade do circuito. Atualmente, a evolução tecnológica está atingindo os limites

onde o atraso introduzido por portas lógicas é da mesma ordem de grandeza que o atraso

introduzido pelas interconexões. Circuitos integrados (CI) estão ficando tão complexos que a

área devida a interconexões começa a ser o fator dominante na superfície total do CI. Como

resultado, uma avaliação mais precisa da superfície do circuito só pode ser feita com estimativas

de posicionamento das portas na partilha de silício, tornando o processo mais complexo.

˙

Figura 6.2. Exemplos de mapeamento.

O circuito da figura 6.2 é organizado segundo uma estrutra em árvore. Este tipo de circuito é

mais simples de se tratar, existindo métodos para cálculo exato da melhor cobertura [Keu87].

Circuitos práticos não são em geral tão bem comportados. Sua estrutura corresponde a um

grafo

acíclico direcionado

(GAD), em vez de uma árvore. O problema adicional introduzido pelo

GAD para o mapeamento é a possibilidade de termos

fanout múltiplo

. Um exemplo de

fanout

múltiplo é apresentado na figura 6.3. O problema para a cobertura da rede é que o nó com mais

de um arco na saída não pode ser agrupado com outro sem ser duplicado. O exemplo mostra o

mapeamento trivial juntamente com a duplicação e mapeamento em porta complexa.

Em geral, a duplicação de um nó com múltiplo

fanout

não é viável pois implica não

apenas na duplicação do nó, mas de toda a porção da rede no

fanin

transitivo do nó, como é

ilustrado na figura 6.4. Neste caso, o custo da duplicação é muito alto, sendo preferível o

mapeamento de cada subrede em forma de árvore (ou

cones

da rede) em separado. Como cada

cone lógico é uma rede estruturada em forma de árvore, a decomposição da rede em cones gera

.

.

..

Biblioteca

.

.

..

.

.

..

(a) (b) (c)


137

uma “floresta” de árvores lógicas. Uma abordagem muito utilizado para mapeamento é

desmembrar o circuito em uma floresta de árvores e mapear cada árvore separadamente. Esse

foi o método adotado no trabalho seminal de Keutzer [Keu87], que serviu de base para o

desenvolvimento de diversos outros mapeadores.

Figura 6.3. Fanout reconvergente e duplicação de nós.

Figura 6.4. Duplicação de subrede.

Podemos classificar o tipo de mapeamento de acordo com o método utilizado para

cobertura da rede e para casamento de portas. O casamento de portas pode ser:

• estrutural

• Booleano

O problema básico do casamento (de portas, bem entendido) é que tanto as portas quanto

as funções a serem casadas devem ser descritas usando uma mesma forma de representação para

poderem ser comparadas. Uma alternativa é descrever as portas e funções na forma de uma

árvore de portas elementares. Esta abordagem caracteriza o casamento estrutural, pois não se

compara a função Booleana mas uma estrutura que a descreve. Uma solução comumente

adotada é utilizar portas NE de duas entradas como elemento de contrução da árvore. A porta

NE (assim como a NOU) é interessante para essa aplicação porque é uma primitiva universal,

ou seja, é possível descrever qualquer função Booleana utilizando apenas portas NE (ou NOU)

∨

.

.∨

Biblioteca

∨

.

.

∨∨

duplica

trivial

mapeia

138


de duas entradas

1

.

Uma vez que a primitiva utilizada para descrição é a mesma, basta verificar se as árvores

são isomórficas para ver se a porta e a função a serem casadas são equivalentes. A descrição

estrutural apresenta, entretanto, algumas restrições. A representação em árvore não se presta

para descrever portas que tem fanout múltiplo interno, como o OU-exclusivo. Além disso, uma

porta complexa pode ser descrita através de diversas árvores alternativas, o que aumenta o

número de comparações a se realizar. Uma última restrição para o mapeamento é a

impossibilidade de tratar funções incompletamente especificadas. A utilização de não-

especificações aumenta o espectro de alternativas para o casamento, pois uma função

incompleta pode ser compatível com mais de uma porta diferente.

A forma mais genérica de mapeamento de portas é o mapeamento Booleano. Neste caso

se compara a função a ser mapeada com a função Booleana que descreve a porta. É uma

abordagem muito mais geral, pois pode se representar qualquer tipo de porta (combinacional)

com uma função Booleana. Não existe igualmente a restrição de se mapear funções

incompletas. O preço a pagar pelo mapeamento Booleano é um custo computacional mais alto.

Um dos primeiros trabalhos na área foi [Mai88], onde inicialmente se realizava a comparação

entre as funções através da espansão de Shannon. Versões posteriores do mapeador - chamado

CERES - passaram a utilizar BDDs para esta tarefa. Desde então uma série de trabalhos

baseados em mapeamento Booleano foram publicados [Sav92, Jac93, Che93]

A cobertura da rede é um processo que está interligado ao mapeamento de portas. O

mapeamento estrutural presupõe a decomposição da rede em termos de primitivas simples. As

portas da biblioteca são decompostas de forma similar. A cobertura consiste em cobrir a rede

com os conjuntos de subredes que descrevem as portas. É um problema de cobertura de grafos,

considerado como intratável na medida que sua solução exata é só pode ser obtida com um

procedimento exaustivo, impraticável para problemas reais. A cobertura utilizando

mapeamento Booleano é um problema similar, mudando apenas a forma como são computadas

as subredes. Realiza-se um processo de

clusterização

, que consiste em obter a função Booleana

que descreve a subrede e compará-las às funções Booleanas que descrevem as portas.

A seleção das subredes ou clusters a serem mapeados pode utilizar uma estratégia local

ou global. Uma técnica local é o método guloso, onde se toma uma decisão baseada no melhor

ganho local que se pode obter. É uma técnica que produz resultados rápidos, mas com um grau

menor de otimização. Um método global consiste na decomposição da rede em cones,

mapeamento ótimo dos cones com técnicas de programação dinâmica e posterior minimização

de inversores. Estas técnicas serão vistas com mais detalhe nas seções que seguem.

6.1 Mapeamento de Portas

O mapeamento que analisaremos aqui se restringe a portas com apenas uma saída. Um

1.

Por outro lado, é impossível representar qualquer função Booleana apenas com portas OU-exclusivo, ouainda utilizando apenas portas E e OU. É um exercício interessante para o leitor analisar estes exemplos .


139

caso mais geral seria considerar portas com múltiplas saídas. Um somador de um bit, por

exemplo, é um elemento que tem três entradas - dois bits de dados e o vem-um - e duas saídas,

o vai-um e a soma. Nos casos em que se empregam estruturas especiais, como somador,

decodificador, etc., uma alternativa é fazer um pré-processamento da descrição inicial e

identificar e extrair esses módulos. Em outros estilos de projeto, particularmente no caso de

FPGA (dispositivos programáveis), exitem blocos lógicos genéricos com mais de uma saída.

Estes podem ser tratados a partir da extensão dos métodos apresentados aqui, com a introdução

de etapas adicionais de formação de pares de clusters compatíveis que podem ser mapeados para

uma célula de duas saídas.

6.1.1 Mapeamento Estrutural

Como foi visto na seção anterior, no mapeamento estrutural os dispositivos são

decompostos em termos de primitivas lógicas elementares. Uma alternativa é utilizar apenas um

tipo de operador para descrever a rede e os dispositivos da tecnologia. Neste caso, deve-se

escolher um operador que permita representar qualquer função Booleana. Os operadores

positivos são imediatamente descartados, pois não é possível realizar-se uma função negativa

apenas com operadores positivos. Por exemplo, como fazer uma operação NE contando-se

apenas com operadores E e OU? Não é possivel. Por esse motivo a álgebra Booleana inclui o

operador NÃO. O conjunto de primitivas {E, OU, NÃO} define um conjunto de operadores

universais, pois pode-se implementar qualquer função Booleana a partir de uma combinação

deles. Para se convercer disso, basta lembrar as formas canônicas soma de mintermos e produto

de maxtermos. Uma soma de mintermos (produto de maxtermos) permite definir exatamente

quais os pontos do domínio de uma função valem

1

(

0

). Pode-se assim definir qualquer função

completa especificando-se o seu conjunto-1 através de uma soma de mintermo, ou o seu

conjunto-0 através de um produto de maxtermos. Para completar este raciocínio informal, tanto

os mintermos quanto os maxtermos são obtidos com os operadores básicos da álgebra Booleana.

Existem outros conjuntos de primitivas universais. Bastante conhecido é o conjunto de

primitivas que definem um

anel Booleano:

{XOR, E}. As fórmulas que descrevem funções em

anéis Booleanos são conhecidas mais popularmente como

expressões Reed-Muller

. São

compostas a partir de variáveis, constantes, XOR e E. Uma maneira simples de se verificar se

um conjunto de primitivas é universal é implementar as funções {E, OU, NÃO} com elas. No

caso do anel, temos:

• Operador NÃO:

=

=

=

• Operador OU:

a 1⊕

a 1⋅ a 1⋅∨

a 1⋅ a 0⋅∨

a

140


=

=

=

=

Teorema 6.1

. O conjunto de primitivas {NE} é um conjunto universal.

Prova

. Basta provar que é possível implementar o conjunto {E, OU, NÃO} através da

primitiva NE.

Operador NÃO: = NE(a,a)

Operador E: = NE(NE(a,b))

Operador OU: = NE(NE(a,a),NE(b,b))

♦

De maneira similar pode-se provar que a primitiva NOU permite implementar qualquer

função Booleana. A figura 6.5 exemplifica uma biblioteca simples descrita através de portas

NE.

Figura 6.5. Exemplo de biblioteca simples.

a b∨

a b∨( )

a b⋅

a 1⊕( ) b 1⊕( )⋅

a 1⊕( ) b 1⊕( ) 1⊕⋅

a a a⋅=

a b⋅ a b⋅( )=

a b∨ a b∨( ) a b⋅= =

Inversor:

NE2:

NOU2:

E2:

OU2:

EOUI21:

EOUI22:

Capítulo 6. Mapeamento Tecnológico 141

Considerando que todas as portas são idênticas,

pode-se abstrair a sua representação gráfica e

representar cada porta NE por um vértice. Os vértices

podem ser inversores, que são portas NE com as duas

entradas conectadas juntas, ou portas NE com duas

entradas. As portas EOU22 e NOU2 ficariam

representadas com essa convenção como mostra a

figura 6.6 ao lado.

Dado que as portas da biblioteca e a rede Booleana são representadas por grafos como os

da figura 6.6, o mapeamento de uma função em uma porta pode ser implementado por um

algoritmo que verifica o isomorfismo entre duas árvores. Este problema pode ser resolvido em

tempo linear com o tamanho da árvore. Uma solução recursiva é apresentada na figura 6.7. A

rede a ser mapeada tem variáveis intermediárias nomeadas yi e variáveis primáiras nomeadas xi

A porta tem vértices nomeados vi e pinos nomeados pi. O algoritmo informa se o mapeamento

existe e, em caso afirmativo, qual a correspondência entre nós da rede e pinos pi da porta.

mapeia( r: rede, p: porta)

{ /* r e p são os nós correntemente processados */

if ( p é pino da porta) {/* se chegou a um pino da porta */

assign ( r, p); /* associa nó da rede ao pino */

return (true); /* mapeamento ok, por enquanto */

} else if ( r == xi) /* entrada primária da rede */

return (false);

else if ( r == p == inversor)

return ( mapeia ( sucessor ( r), sucessor ( p));

else if ( r == p == NE) {

if ( mapeia ( sucessor-0 ( r), sucessor-0 ( p) and

mapeia ( sucessor-1 ( r), sucessor-1 ( p))

return (true);

else return ( mapeia ( sucessor-0 ( r), sucessor-1 ( p) and

mapeia ( sucessor-1 ( r), sucessor-0 ( p));

} else return (false);

}

Figura 6.7. Algoritmo de mapeamento estrutural.

O algoritmo processa recursivamente dois grafos que descrevem a rede e uma porta da

biblioteca. Em primeiro lugar o algoritmo testa se p é um pino da porta (folha da árvore). Neste

caso, o mapeamento existe e determina a associação do nó r da rede ao pino p. Note que o

mapeamento ocorre independente do nó da rede ser primário ou intermediário. Caso seja

NOU2

EOU22

Figura 6.6. Portas NOU2 e EOU22

142 Capítulo 6. Mapeamento Tecnológico

intermediário, o algoritmo realiza um mapeamento parcial, vinculando parte da rede a uma

porta. O restante da rede deve ser mapeado posteriormente, através de novas chamadas do

algoritmo. Na verdade, este já é um problema de cobertura da rede. Ambos os processos estão

interligados devido às possíveis combinações de portas que podem ser utilizadas. A separação

do processo entre mapeamento de portas e cobertura da rede aqui adotada é apenas um recurso

didático. Caso o algoritmo atinja uma entrada primária da rede o mapeamento não ocorre. Outro

fator de discriminação é o tipo do nó. Se em uma etapa da recursão encontra-se dois nós de tipos

diferentes (um inversor e outro NE), então o mapeamento falha. Se os nós são do mesmo tipo,

o resultado do mapeamento é dado pela chamada recursiva do algoritmo sobre os sucessores dos

nós na rede. O detalhe aqui é que se o nó tiver duas entradas, é necessário verificar as duas

alternativas possíveis, caso a primeira falhe. No algoritmo mapeia chamados os dois sucessores

de um nó de sucessor-0 e sucessor-1, um pouco impropriamente a imagem e semelhança de

BDDs, visto que aqui não existe diferença entre os sucessores como ocorre nos BDDs.

Considere o exemplo da figura 6.8. Em primeiro lugar invoca-se o algoritmo mapeia( y1, v1)

passando como parâmetro a raiz da rede (a) e a raiz da porta (b). Como y1 e v1 são nós do mesmo

tipo, o mapeamento prossegue com mapeia(y2,v2), que retorna com êxito a assinalação de

{(x1,p1), (x2,p2)}. A seguir, a chamada de mapeia(x3,v3) falha. O algoritmo volta atrás e tenta o

mapeamento dos sucessores 0 e 1 e dos sucessores 1 e 0, falhando igualmente.

Figura 6.8. Mapeamento de uma subfunção de duas portas diferentes.

O mapeamento de (a) em (c) começa da mesma forma com mapeia( y1, v1) . O

mapeamento de y2 e p1 é válido, mas mapeia(x3,v2) falha. O algoritmo retrocede e mapeia x3

em p1, x1 em p2 e x2 em p3 com sucesso. A sequência de passos é como segue:

mapeia(y1, v1)

→ mapeia(y2, p1)

{(y2, p1)} ↵

yi x1 x2 x3∨⋅=

y1

y2

x1 x2 x3

v1

v2 v3

p3 p4p2p1

v1

v2

p3p2p1

(a) (b) (c)

0

0 1

1 0 1

0 1 0 1

0 1

0 1


→ mapeia(x3, v2)

falha ↵→ mapeia(y2, v2)

→ mapeia(x1, p2)

{(x1, p2)} ↵

→ mapeia(x2, p3)

{(x2, p3)} ↵

→ mapeia(x3, p1)

{(x2, p3)} ↵

resultado: {(y2, p1), (x1, p2), (x2, p3)}

Em [Dem94] é apresentada uma alternativa interessante de mapeamento estrutural

empregando a técnica de Aho e Corasick para casamento de strings. O método baseia-se na

modelagem do casamento de strings através de uma máquinas de estado finitas e apresenta a

vantagem de ser mais genérico do que o mapeamento recursivo, com a desvantagem de ser mais

complexo de gerenciar.

6.1.2 Mapeamento Booleano

Uma porta lógica é um elemento físico que estabelece

uma relação entre suas entradas e sua saída em termos de uma

função Booleana. Considere a porta lógica apresentada na

figura 6.9. A função lógica realizada pela porta g em termos

dos seus pinos p1 e p2 é . Quando a

porta g é instanciada em uma rede Booleana, teremos uma associação de variáveis da rede aos

pinos p1 e p2. A função realizada pela porta será personalizada para aquelas variáveis de

entrada.

Exemplo 6.1. Suponhamos uma rede com apenas duas variáveis de entrada X = {x1, x2}.

Quais as funções Booleanas f que poderíamos implementar com a porta g

considerando a possível utilização de inversores na rede? Isso pode ser

determinado assinalando-se as variáveis da rede aos pinos da porta. Algumas

assinalações possíveis são apresentadas a seguir.

:

:

:

:

:

♦Cada porta lógica pode implementar uma família de funções Booleanas diferentes de

acordo com um conjunto de transformações que podem ser aplicadas às suas entradas e à sua

g p1 p2⋅ p1 p2∨= =

p1 x1 p2 x2 f g←,←,← f x1 x2∨=

p1 x2 p2 x1 f g←,←,← f x2 x1∨=

p1 x2 p2 x1 f g←,←,← f x2 x1∨ x1 x2⋅= =

p1 x2 p2 x1 f g←,←,← f x1 x2⋅=

p1 x1 p2 x2 f g←,←,← f x1 x2∨=

p1

p2

g

Figura 6.9. Porta g=p1∨ p2


saída. Podemos enumerar os seguintes conjuntos de transformações [Dav91]:

• Sn, o grupo simétrico de permutações de de n variáveis. Contém n! elementos.

• , o grupo de complementos de variáveis. Contém 2n elementos.

• C, o complemento da função. Contém apenas a função e seu complemento

Seja π uma permutação das variáveis de entrada e ∂ = o complemento delas. Seja µuma composição de ambas as transformações. O problema do mapeamento Booleano pode ser

enunciado como segue.

Definição 6.1. Seja f uma função Booleana e L uma biblioteca de portas lógicas, o

mapeamento Booleano consiste em encontrar um subconjunto de portas {gi}

⊆ L tal que:

f( ) ≡ gi(µ( ))

♦

Exemplo 6.2. Considere a porta lógica da figura 6.9. A função pode ser

implementada pela porta g se fizermos π = (x1,x2), ∂ = (0,1) e f = g. A função

seria implementada com g se π = (x2, x1), ∂ = (1,1) e h = g.

♦O subconjunto {gi} representa todas as portas que podem implementar f segundo um

conjunto de transformações µ. Se este subconjunto é vazio, então não existe nenhuma porta na

biblioteca que implemente f.

O custo do mapeamento Booleano é dado pelo número de comparações necessárias para

verificar se f pode ser implementado por g. Para uma porta de n entradas temos n! permutações,

2n fases de entrada mais 2 fases de saída, perfazendo um total de n!.2n+1 comparações. A figura

6.10 ilustra como estas transformações poderiam ser aplicadas às entradas e à saídade uma

porta. O bloco Sn é responsável pelas permutações das variáveis de entrada. Sobre cada

permutação o bloco realiza uma das 2n atribuições de fase possíveis. Por fim, o bloco C

pode complementar a saída da porta. A combinação destas operações permite obter uma família

de funções a partir da porta.

Figura 6.10. Transformações Booleanas.

Naturalmente, o custo da ordem de O(n!2n) é muito alto para ser prático mesmo para

funções com um pequeno número de entradas. Existem, entretanto, formas de se simplificar o

C2n

xe( )

x x

f x1 x2⋅=

h x1 x2∨=

C2n

PORTASn Cn

2C

x 1

x 2

x n


mapeamento Booleano. A família de funções obtida a partir das transformações ilustradas na

figura 6.10 contém diversas funções equivalentes. Por exemplo, seja g uma porta que

implementa a função E. As transformações são todas

equivalentes, denotando a mesma função, a E b. Basta apenas testar uma destas funções para

saber que a função pode ser implementada pela porta. As transformações que resultam na

mesma função definem um classe de funções equivalentes, ou classe de equivalência. No

exemplo acima, basta verificar que uma das expressões de f pode ser implementada pela porta.

Ao se identificar que uma função pertence a uma classe de equivalência, todas as

transformações equivalentes são automaticamente determinadas. O algoritmo de cobertura da

rede deve então selecionar qual das transformações é a mais interessante para o mapeamento.

Ao se mapear uma função em uma porta é importante detectar quais transformações

resultam em funções equivalentes. Como essas transformações não necessitam ser realizadas, o

número de comparações (e custo do mapeamento) é reduzido. Uma propriedade importante para

deteção de transformações equivalentes é a simetria de variáveis em uma função.

Definição 6.2. Duas variáveis xi, xj ∈ X são simétricas em uma função f se:

♦A simetria de variáveis é uma propriedade transitiva. Se (xi, xj) são simétricas e (xj, xk) são

simétricas, então (xi, xk) também são simétricas. Um conjunto de variáveis simétricas em uma

função f define uma classe de simetria em f. A simplificação resultante em termos de

mapeamento Booleano é que a permutação de variáveis simétricas resulta sempre em funções

equivalentes. Ou seja, não é necessário permutar variáveis simétricas no mapeamento. Um

exemplo extremo dessa propriedade é uma porta E ou OU com n entradas. Como E e OU são

operações comutativas, todas as n entradas são simétricas e formam uma única classe de

simetria. Portanto, o custo de n! permutações é totalmente eliminado.

Exemplo 6.3. Seja . As variáveis {x1, x2, x3}, {x4, x5} e

{x6} formam três classes de simetria, sendo {x6} um caso particular de uma

classe com apenas uma variável. Note que variáveis de classes de simetria

diferentes não são permutadas, assim como as variáveis dentro de uma mesma

classe. Portanto, f não requer nenhuma permutação para ser mapeada em uma

porta.

♦As classes de simetria introduzem significativa redução na complexidade do mapeamento

de portas. A simplificação deriva dos seguintes fatores:

• variáveis de uma mesma classe de simetria não necessitam ser permutadas

• variáveis de classes de simetria diferentes não são permutadas

• classes de simetria de diferente cardinalidade não são permutadas entre si

f a b⋅ b a⋅ a b∨ b a∨= = = =

f x1 … xi … x j … xn, , , , , ,( ) f x1 … x j … xi … xn, , , , , ,( )=

f x1 x2 x3∨ ∨( ) x4 x5∨( ) x6⋅ ⋅=


No exemplo 6.3 temos uma ilustração desta última propriedade. As variáveis x1 e x2, não

são permutadas entre si pois pertencem a mesma classe de simetria. As variáveis x1 ex4 não o

são pois pertencem a classes de simetria diferentes e as classes de simetria {x1, x2, x3} e{x4, x5}

não são permutadas pois tem cardinalidade diferentes. Entretanto, duas classes de simetria com

mesma cardinalidade podem ser trocas de posição. Considere . Temos

as classes de simetria {x1, x2} e {x3, x4}. De acordo com as regras de simplificação, não

permutamos x1 e x2 nem x1 e x3 pelos dois primeiros motivos. Entretanto, {x1, x2} e {x3, x4}

devem ser permutados pois:

Outra propriedade que pode ser utilizada para simplificar o mapeamento de portas é a

monotonia das variáveis.

Definição 6.3. Uma função f é crescente ou positiva em x se . Ela é decrescente ou

negativa em x se . f é degenerada em x se . f é monótona

(unate) em x se ela é crescente ou decrescente em x, caso contrário ela é não-

monótona (binate) em x..

♦Uma variável monótona em uma função deve ser mapeada em uma variável monótona em

uma porta. Da mesma forma devem ser mapeadas as variáveis não-monótonas da função e da

porta lógica. Se uma função tem k variáveis assimétricas e dentre estas existem m monótonas,

o número de permutações a ser realizado é de k!(m-k)!.

Deteção de Simetria em BDDs

É bastante simples verificar se duas variáveis são simétricas em um BDD [Jac94]. A

simetria pode ser determinada a partir da fatoração da função com relação às variáveis a serem

examinadas.

Teorema 6.2. Duas variáveis x e y são simétricas em uma função f se:

Prova. x e y dividem o domínio de f em 4 subdomínios: { }. Trocando x e

y nos vetores de entrada, obtemos uma nova função f’cujos subdomínios com

relação a x e y são { }. Para que f =f’, os 4 subdomínios de ambas

devem ser iguais:

, ou ainda

, ou ainda

, ou ainda

, ou ainda

f x1 x2⋅ x3 x4∨( )∨=

x1 x2⋅ x3 x4∨( ) x3 x4⋅ x1 x2∨( )∨≠∨

f x f x≤f x f x≤ f x f x=

f xy f xy=

f xy f xy f xy f xy, , ,

f yx f yx f yx f yx, , ,

f xy f yx= f 00 f 00=

f xy f yx= f 10 f 01=

f xy f yx= f 01 f 10=

f xy f yx= f 11 f 11=


O primeiro e o quarto subdomínios não mudam, enquanto que o segundo e o

terceiro são trocados. Portanto, se x e y são simétricas em f.

♦A título de ilustração, considere o conjunto de funções elementares de duas entradas

apresentado na figura 6.11. As funções apresentadas são todas simétricas. Os subdomínios

correspondentes a xy e xy são os pontos na diagonal secundária do diagrama. Nas funções E e

XNOR estes valem 0, enquanto que nas funções OU e XOR os pontos eles valem 1.

Figura 6.11. Exemplos de variáveis simétricas.

Em um BDD, a cada nó n está associada uma função Booleana . O arco-1 do nó aponta

para a função cofatorada com relação à variável x de controle do nó: . Da mesma forma, o

arco-0 de n aponta para a função cofatorada com relação ao literal x: . Um caminho no BDD

corresponde, portanto, a sucessivas fatorações de uma função com relação às variáveis dos nós

que aparecem no caminho. Assim, se colocarmos duas variáveis simétricas em posições

adjacentes i, i+1 no ordenamento do BDD, os caminhos que passam pelos nós controlados por

elas devem seguir a restrição imposta pelo teorema 6.2. Como consequência, temos que os nós

com esses índices devem ser combinados de acordo com os padrões apresentados na figura 6.12.

Figura 6.12. Padrões de subdiagramas de variáveis simétricas.

Um algoritmo que verifica se duas variáveis adjacentes são simétricas num BDD deve

checar se todos os padrões de nós controlados por essas variáveis correspondem aos padrões da

figura 6.12. Para determinar classes de simetrias, é necessário comparar as variáveis duas a

duas. Cada par de variáveis deve ser colocado adjacente no BDD para se analisar os padrões de

subgrafos. Uma forma de se fazer isso é trocar as variáveis de lugar utilizando os algoritmos de

manipulação incremental de BDD apresentado no capítulo 4. Começa-se pela variável na raiz

do BDD, digamos x1, que é comparada com a variável adjacente imediatamente inferior, x2.

f 10 f 01=

x

y

E OU XOR XNOR

1 y 1 1

1 1

1 1

1

x

y

x x

y

fn

f xn

f xn

f g f g f g h

(a) (b) (c)

0

0

1

1 10


Troca-se x1 e x2 de posição e a seguir compara-se x1 com x3, a terceira variável no ordenamento.

Repete-se o processo até que x1 tenha sido comparada com todas as variáveis do BDD. A seguir,

repete-se o procedimento começando agora com x2, que está na raiz, deslocando-a até a

penúltima posição no ordenamento (antes de x1). O processo é iterado até que todas as variáveis

tenham sido comparadas. Se n é o número de variáveis, temos n(n-1)/2 comparações no pior

caso. O custo pode ser bastante reduzido se utilizarmos a propriedade transitiva da simetria para

podar a árvore de pesquisa. Se x2 é simétrica a x1, não é necessário comparar x2 às outras

variáveis, pois a comparação com x1 já terá determinado quais são simétricas e quais não o são.

Ao final do processo, todas as classes de simetria da função foram determinadas.

Deteção de Monotonia em BDDs

É também muito simples se verificar se uma variável é crescente ou decrescente em um

BDD. Note que variáveis degeneradas não aparecem em BDDs (que são muito conservadores,

diga-se de passagem). Uma variável x é degerada em f quando . Isso significa, no

BDD, que os sucessores 0 e 1 do nó controlado por x apontam para a mesma subfunção. Neste

caso, o nó é redundante e é eliminado do diagrama.

Para verificar se uma variável x é crescente, decrescente ou não-monótona em um BDD

de uma função f basta colocá-la na última posição do ordenamento. Neste caso, todas as

variáveis de f já foram fatoradas e restam apenas os subdomínios que dependem de x.. Se nestes

subdomínios x é positiva, então f é crescente em x. Se é negativa, f é decrescente em x e se x é

positiva e negativa, então f é não-monótona em x.. No BDD, considerando x a última variável

do ordenamento, temos as seguintes propriedades:

• f é crescente em x se no BDD existe apenas um nó controlado por x e seu sucessor-

1 é 1 e seu sucessor-0 é 0.

• f é decrescente em x se existe apenas um nó controlado por x e seu sucessor-1 é 0

e seu sucessor-0 é 1.

• f é não-monótona em x se existem dois nós controlados por x.

A figura 6.13 ilustra os casos acima. Na figura (a) temos apenas um nó dependendo de x

e o nó representa uma função negativa. Portanto, f é negativa em x. Na figura (b) temos que

existe apenas um nó e ele representa a função . O BDD é portanto positivo ou crescente

em x. Na figura (c), temos tanto x como x no último nível do BDD. Neste caso, f é não-monótona

em x..

Mapeamento com BDDs

Para simplificar o mapeamento, as funções e as portas lógicas podem ser classificadas de

acordo com as propriedades de simetria e monotonicidade. Um aspecto interessante relativo à

utilização de BDDs é que ambas as propriedades acima podem ser detetadas de forma

concomitante. Se começarmos as trocas nas posições das variáveis pela última em vez da

primeira, teremos sucessivamente diferentes variáveis naquela posição. A última variável no

f x f x=

fn

x=


ordenamento é testada com relação à monotonicidade e a seguir é deslocada em direção à raiz

para verificação de simetria.

Figura 6.13. Monotonia de x em um BDD.

Uma forma de classificar as portas é ordenar as variáveis de acordo com as classes de

simetria. Podemos colocar as classes com maior cardinalidade mais próximas à raiz do BDD.

De acordo com esse esquema de classificação, a variável na raiz do BDD pertence a classe de

simetria de maior cardinalidade e a variável no fim do ordenamento pertence a classe de menor

cardinalidade. Na função do exemplo 6.3, a ordem seria {{x1, x2, x3}, {x4, x5},{x6}}. Além da

simetria podemos ordenar as variáveis de acordo com sua monotonicidade. Uma possibilidade

seria crescente, decrescente e não-monótona.

Exemplo 6.4. Seja . As classes de simetria são {{x1, x2,

x3}, {x4}, {x5},{x6}}. O ordenamento seguindo a estratégia acima seria

.

♦Na biblioteca as portas são representadas por um BDDs ordenados de acordo com os

mesmos critérios. A biblioteca é estruturada segundo um arranjo bidimensional, de acordo com

o número de classes de simetria de cada porta numa dimensão e de acordo com um vetor de

cardinalidade de classes na outra. A figura 6.14 ilustra esse tipo de organização. O primeiro eixo

vertical à esquerda contém as portas cujas funções tem apenas uma classe de simetria. Sobre

esse eixo temos subdivisões em termos do número de entradas da porta. Assim, uma porta E

com 4 entradas seria localizada nas coordenadas (1,4) da matriz da biblioteca. A função do

exemplo 6.3 contém 3 classes de simetria, com cardinalidades 3, 2 e 1. Ela ficaria localizada nas

coordenadas (3, 321) da biblioteca. Naturalmente, não tem sentido aqui utilizar um arranjo

sequencial para armazenar a coordenada 321. Uma hash table seria mais adequada para este tipo

de arranjo.

O processo de mapeamento Booleano de uma função em uma porta consiste em classificar

a função e compará-la a todas as portas da biblioteca com mesmas coordenadas. Um exemplo

de classificação é apresentado na figura 6.15. A função a ser classificada é

, inicialmente com um ordenamento aleatório.

Exemplificaremos a deteção de simetria para a variável x4. Em (a), x4 está no topo do BDD e

0 1

x10

0 1

x01 1

0xx

0 1

01

(a) (b) (c)

f x1 x2 x3⋅ ⋅ x4 x5⋅ x5 x6⋅∨ ∨=

x1 x3 x2 x4 x6 x5, , , , ,( )

f x1 x2 x3∨ ∨( ) x4 x5∨( ) x6⋅ ⋅=


pode ser comparada com x3. Basta verificar se os padrões da figura 6.12 ocorrem, ou ainda

verificar se os caminhos e levam ao mesmo nó do BDD. Isso não ocorre para

estas variáveis e, portanto, x3 e x4. não são simétricas. Troca-se x3 e x4.e obtem-se o diagrama

da figura (b). Compara-se agora x4 e x1. Mais uma vez se verifica que não há simetria. A troca

de x1 e x4. produz o diagrama (c), onde se verifica que x4 e x6. não são simétricas. Note,

entretanto, que as duas primeiras variáveis x1 e x3 no topo do BDD apresentam uma

configuração simétrica. A próxima troca leva ao diagrama (d). Vemos que x4 e x5.apresentam

configurações de simetria. Efetivamente, x4 e x5.são variáveis simétricas na função. Os

diagramas (e) e (f) mostram os últimos passos no processamento de x4, onde se verifica sua

assimetria com relação a x2. Ao término do processo, x4 está no fundo do BDD. O processo se

repete para x3, que será deslocada até a posição imediamente anterior a x4. O final, o BDD é

reordenado em função de suas classes de simetria, produzindo o BDD da figura (g).

Figura 6.14. Estrutura de uma biblioteca.

Após a classificação, a função é comparada às portas da biblioteca que tem o mesmo

número de classes de simetria e mesmo vetor de cardinalidade. A comparação indica se a porta

pode implementar a função considerando a possível complementação de fases nas entradas e

saída. O algoritmo que compara os BDDs é muito semelhante ao algoritmo de deteção de

equivalência entre funções, que verifica se os diagramas são isomórficos. A diferença é que no

mapeamento de porta a fase das entradas assim como a fase da saída é determinada durante a

travessia do diagrama. Recordando, dois BDDs r e q são equivalentes se:

• r = q = constante 0 ou 1. Ou seja, se eles são o mesmo terminal do BDD.

• se r e q são controlados pela mesma variável e se seus sucessores-0 são

equivalentes e seus sucessores-1 são equivalentes.

No caso do mapeamento, deve-se acrescentar as seguintes cláusulas:

• r e q são controlados pela mesma variável e e seus sucessores-0 são equivalentes

e seus sucessores-1 são equivalentes ou os sucessores-0 são equivalentes aos

sucessores-1.

• r e q são o mesmo terminal do BDD e a fase da saída é direta ou r = q e a fase da

saída é complementada.

x4 x3⋅ x4 x3⋅

Biblioteca

|Classes de Simetria|

1 2 3 4

22

21

324

2

3

211

221

321

veto

res

de c

lass

es


Figura 6.15. Classificação de um BDD.

A figura 6.16 apresenta um exemplo do mapeamento de uma função (a) em

uma porta NOU de duas entradas, (b). O algoritmo começa pelas duas raízes. Para

simplificar, vamos indicar os nós pelas variáveis que os controlam. x1 não é equivalente a p1

pois sucessor-1(x1) ≠ sucessor-1(p1). Entretanto, a fase de x1 é direta. Resta a alternativa de

verificar a equivalência para as fase invertida de x1. Inverter a fase de uma variável em um BDD

implica em inverter os sucessores 0 e 1. Assim, sucessor-1(x1 ) é o terminal 1 e sucessor-1(p1 )

é 0. Uma vez que a fase da saída é direta, resta testar a possibilidade de inverter a saída. Inverter

uma função equivale a trocar os valores dos terminais. Neste caso, sucessor-1’(p1) = 1 (a

apóstrofe indica que a função foi complementada). O algoritmo prossegue verficando então se

os nós x2 e p2 são equivalentes. Temos sucessor-1(x2 ) = sucessor-1’(p2) e sucessor-0(x2 ) =

0

0

0

0 0 0 0

0

(a)

x4

x3 x3

x1 x1

x6 x6 x6 x6

x5x5

x2

1 0

10

0

0

0

1 1

1 1

111

1

1

1

1

0

0

0

0 0 0 0

0

(b)

x4 x4

x1 x1

x6 x6 x6 x6

x5x5

x2

1 0

10

0

0

0

11

1 1

111

1

1

1

1

0

0

0

0 0 0 0

0

(c)

x3

x4 x4

x6 x6 x6 x6

x5x5

x2

1 0

10

0

0

1

1 1

111

1

1

1

1

x1

0

0

0

0 0

0

(d)

x3

x6 x6

x4 x4

x5x5

x2

1 0

10

0

0

1

1 1

11

1

1

1

x1

1

0

0

0

0 0

0

(e)

x3

x6 x6

x5 x5

x4x4

x2

1 0

10

0

0

1

1

1

1

1

1

x1

0

0

0

0 0

0

(f)

x3

x6 x6

x5 x5

x2x2

x4

1 0

10

0

0

1

1 1

11

1

1

1

x1

1

0 1

x1

x2

x3

x4

x5

x6

0

0

0

0

0

1

1

1

1

1 0(g)

1

x3

f x1 x2∨=

p p1 p2∨=


sucessor-0’(p2). O resultado do mapeamento é que a função f pode ser implementada pela porta

NOU2 se colocarmos um inversor na entrada p1 e um inversor na saída, como ilustra (d).

Figura 6.16. Exemplo de mapeamento de porta.

Um algoritmo para realizar o mapeamento de uma função em uma porta é apresentado na

figura 6.17. É constituido por duas funções principais e algumas funções auxiliares.

mapeia_porta recebe o BDD que descreve a função f e o BDD que descreve a porta lógica g.

Ele inicia o vetor de fase onde são armazenadas as fases de todas as variáveis e a fase da saída.

A fase da saída é iniciada como indefinida. Na primeira comparação de terminais a fase da saída

é colocada em positiva ou negativa. Qualquer tentativa posterior de mudar a fase resulta em

falha no mapeamento (a fase tem que ser a mesma para toda a função). A fase das variáveis é

iniciada como direta. mapeia_porta chama a seguir mapeia_rec, que percorre os BDDs para

verificar se são equivalentes. Se os BDDs são equivalentes, o vetor fase contém todas as fases

das variáveis e da saída. A função monta_porta agrega os inversores necessários à

implementação de f. mapeia_rec processa recursivamente os BDDs verificando as condições de

equivalência. Se os nós bddf e bddg são terminais, a função auxiliar caso_terminal verifica se

os terminais são iguais ou diferentes e faz a consistência com relação a fase da saída. Se apenas

um deles é terminal então o mapeamento falha. Por fim, se os nós são não-terminais e tem a

mesma variável de controle, verifica-se recursivamente o mapeamento dos sucessores. Se o

mapeamento direto tem sucesso, o algoritmo retorna true. Se o mapeamento invertido tem

sucesso o algoritmo retorna o resultado de inverte_fase, que verifica se a fase já foi invertida

(mapeamento falso) ou não (inverte a fase e retorna true). Se nenhum dos casos se verfica, o

mapeamento falha.

6.2 Cobertura da Rede

A cobertura da rede consiste em associar um nó da rede a pelo menos um dispositivo da

tecnologia. Podemos enumerar três métodos alternativos para resolver este problema:

• cobertura gulosa

• cobertura estocástica

• cobertura dinâmica

1

1 0

0

1 0

p1

0

p2

1

1 0≡ ⇒

0 1

1 0

1 0

x1

x2

0

1

x1

x2

(a) (b) (c) (d)

p1

p2


mapeia_porta (bddf, bddg) {

inicia vetor_fase;

if ( mapeia_rec ( bddf, bddg, vetor_fase))

return ( monta_porta ( vetor_fase))

else return (NULL);

}

mapeia_rec ( bddf, bddg, vf) {

switch ( bddf, bddg) {

case (índices diferentes): return (false);

case ( bddf == bddg == terminal)

return ( caso_terminal( bddf, bddg, vf));

case ( bddf ou bddg é terminal): return (false);

case ( mapeia_rec ( suc-0 ( bddf ), suc-0 ( bddg ), vf ) and

mapeia_rec ( suc-1 ( bddf ), suc-1 ( bddg ), vf )) return (true);

case ( mapeia_rec ( suc-0 ( bddf ), suc-0 ( bddg ), vf ) and

mapeia_rec ( suc-1 ( bddf ), suc-1 ( bddg ), vf ))

return ( inverte_fase ( var ( bddf )));

otherwise : return (false);

}

}

Figura 6.17. Mapeamento Booleano de uma função em uma porta.

Outra forma de classificar os métodos é dividindo-os em algoritmicos e sistemas

especialistas. Alguns sistemas especialistas para mapeamento adotam estratégias gulosas ou

estocásticas. Por outro lado, mapeadores algoritmicos podem utilizar qualquer uma das três

estratégias acima. No caso das estratégias gulosa e por programação dinâmica, os métodos

algoritmicos particionam a rede em uma floresta de árvores. Este procedimento é realizado da

seguintes maneira: cada saída da rede é a raiz de uma árvore de nós. Todos os nós conectados

ao fanin da raiz e que tem fanout unitário são incluídos na árvore. O processo se repete para cada

nó acrescentadoà arvore. Se um nó tem fanout maior do que 1, ele torna-se a raiz de uma nova

árvore. As folhas das árvores são, portanto, entradas primárias da rede ou nós da rede com

fanout maior do que 1.

6.2.1 Cobertura Gulosa

Apesar de sugestivamente gastronômico, o título refere-se a uma cobertura de portas

lógicas. Entretanto, o termo guloso relaciona-se à forma como se seleciona uma solução parcial

no processo de mapeamento da rede. O mapeador guloso pega sempre a melhor alternativa

oferecida. Uma característica (e também restrição) desses métodos é que as soluções parciais


ou etapas do mapeamento são determinadas a partir de informações locais. Portanto, são

métodos favorecem o tempo de execução em detrimento da qualidade do resultado. Dois

métodos que utilizam essa abordagem são o mapeamento por sistema especialista e o

mapeamento algoritmico.

Sistemas Especialistas

Sistemas especialistas dedicados ao mapeamento utilizam regras de produção para

otimizar um circuito previamente mapeado [Dar81, Dar84, Geu85]. Os padrões de portas são

interpretados como regras de produção. Temos dois tipos de padrões. O padrão candidato indica

uma subrede candidata a otimização, enquanto que o padrão substituto inidica uma subrede que

substitui a candidata otimizando a qualidade do circuito. Exemplos de regras de produção são

os padrões da figura 6.18. Por exemplo, a quarta regra da figura 6.18 poderia ser descrita da

seguinte maneira:

• se (topologia = ne(x,ne(y,ne(z,w))) e otimização = área) então

substitui(ne(x,ne(y,ne(z,w))) -> ne(x,y,z,w));

O sistema especialista percorre o rede Booleana e, para cada nó, verifica se alguma regra

de produção pode ser aplicada. Em sistemas gulosos, a primeira regra encontrada que melhora

a qualidade do circuito é imediatamente aplicada. O processo é repetido para os nós da rede até

que se atinja um mínimo local, ou seja, que não haja nenhuma regra que produza uma redução

de custo se aplicada ao circuito.

Cobertura Algoritmica

A cobertura algoritmica seguindo uma estratégia gulosa atua normalmente sobre uma

rede Booleana não mapeada. O algoritmo percorre a rede e, para cada nó visitado, realiza o

mapeamento baseado apenas em informações locais. Uma coleção de portas que podem mapear

o nó é selecionada e a porta que provoca a maior redução de custo é eleita para mapear o nó.

Um exemplo de sistema de mapeamento que utiliza esta técnica foi apresentado em

[Cra91]. A rede Booleana é representada como um grafo onde os nós intermediários são

operadores lógicos E (*), OU (+) e NÃO (!) e os nós terminais são as variáveis de entrada. As

portas da tecnologia são descritas como subgrafos utilizando os mesmos operadores. A

biblioteca é restrita a portas de um a dois níveis lógicos. Um exemplo de representaçaão de

portas com dois níveis lógicos é mostrado na figura 6.18 (a). A rede é primeiro particionada em

árvores. As árvores são mapeadas separadamente. Após o mapamento das árvores a rede inteira

é reprocessada para minimização de inversores.

Para mapear uma árvore, o algoritmo percorre a rede executando a cada passo um

mapeamento. Dois tipos de mapeamentos são considerados. Um mapeamento perfeito é aquele

onde uma porção da rede é isomórfica a árvore que descreve uma porta lógica. Um mapeamento

é semiperfeito se não existe um casamento direto entre a porção da rede em análise e uma porta

de dois níveis. Neste caso, a rede é localmente expandida visando gerar uma subrede. A figura


6.18 (b) ilustra o processo de expansão. Uma árvore é mapeada em duas etapas. Na primeira

fase são realizados mapeamentos perfeitos e semiperfeitos e na segunda fase as portas de um

nível lógico são mapeadas. Após o mapeamento de todas as árvores, a rede é processada para

minimização de inversores. O mapeamento das árvores procura utilizar apenas portas positivas.

As portas positivas na raiz das árvores são substituidas por negativas aplicando De Morgan. Os

inversores nas entradas das portas são absorvidos pelas portas no seu fanin. Se biblioteca for

autodual, ou seja, para cada porta positiva existe uma porta que implementa o seu

complemento, garante-se que os inversores só aparecerão nas folhas das árvores.

Figura 6.18. (a) representação das portas e (b) expansão de um nó.

6.2.2 Cobertura Estocástica

A cobertura estocástica parte de uma rede já mapeada. São aplicadas transformações que

geram novas redes equivalentes a primeira a partir de manipulações locais semelhantes àquelas

utilizadas pelos sistemas especialistas (figura 6.19). A principal diferença com relação ao

método guloso é que a cobertura estocástica permite que a solução temporariamente piore,

buscando caminhos alternativos no espaço de soluções que, eventualmente, permitam sair do

mínimo local. O processo é semelhante ao algoritmo estocástico para reordenamento de BDDs

que foi apresentado no capítulo 4 (fig. 4.7). O que muda é o conceito de movimento. No

mapeamento, um movimento é uma transformação de uma subrede de portas em outra subrede

de portas. Portanto, um par de subredes equivalentes caracteriza um movimento no espaço de

soluções. O movimento pode ser realizado no sentido de aumentar ou diminuir a complexidade

da rede.

A figura 6.19 exemplifica alguns tipos de transformações locais (ou movimentos) que

*(+)

+(*)+(*)

(a)

*(+)

*(+)

*(+)*(+)

(b)


podem ser realizadas em uma rede. A substituição de uma subrede à esquerda da figura pela

correspondente subrede à direita caracteriza um movimento no sentido da simplificação do

circuito. O movimento inverso aumenta a complexidade do circuito, substituindo portas

complexas por conjuntos de portas mais simples. Isso, por outro lado, aumenta a possibilidade

de se encontrar novas regras aplicáveis a rede.

Existem diversos tipos de algoritmos estocásticos. A técnica da evolução simulada

aplicada ao mapeamento consistiria na alternância de procedimentos de evolução e mutação. A

evolução consiste em migrar para o mínimo local mais próximo seguindo uma técnica gulosa.

Para sair do mínimo local aplicam-se as transformações no sentido inverso de forma arbitrária,

que aumentam sua complexidade. O procedimento guloso é retomado e iterado com a mutação

até que se atinja um critério de parada. O controle da pesquisa no espaço de soluções é realizado

de forma similar à apresentada na seção 4.1.3. A cada ciclo do algoritmo uma variável de

controle é decrementada. Se a solução é melhorada, o algoritmo recebe como recompensa mais

tempo para sua pesquisa na forma de um incremento da variável de controle. Após uma certa

quantidade de ciclos sem melhora da solução o sistema interrompe a pesquisa.

Figura 6.19. Exemplos de transformações locais.

Em [Geu85] é apresentado um sistema especialista chamado SOCRATES que utiliza uma

estratégia similar. SOCRATES realiza uma pesquisa no espaço de soluções a partir do nó

correntemente processado. Ele examina um número fixo de nós adjacentes (amplitude da busca)

e repete a busca para cada um deles. O procedimento é iterado até se atingir uma determinada

distância do nó atual (profundidade da busca). O melhor movimento encontrado nessa pesquisa

é defindo por uma sequência de transformações. A sequência é aceita se o custo da rede após a

aplicação das transformações é menor do que o inicial. Durante esse movimento composto o

custo da rede pode temporariamente aumentar, o que caracteriza um procedimento estocástico.

O número de transformações da sequência selecionada que são efetivamente realizadas é

limitado por um parâmetro (l de look-ahead). O objetivo principal é controlar o tempo de

processamento, que pode ser muito grande em função do tamanho do espaço de soluções. Em

SOCRATES, um sistema de meta-regras controla a amplitude e profundidade da busca a cada

⇔

⇔

⇔

⇔


passo e escolhe as regras a serem aplicadas. Os resultados apresentados em [Geu85] mostram

um ganho da ordem de 12% sobre os sistemas especialistas gulosos. Valores típicos para os

parâmetros são l = 1, profundidade = 2 e amplitude = 4.

6.2.3 Cobertura Dinâmica

Na verdade, o título mais correto desta seção seria cobertura da rede utilizando-se

técnicas de programação dinâmica , mas é muito longo. Esta é a técnica mais utilizada. Sua

aplicação ao mapeamento tecnológico foi proposta inicialmente em [Keu87]. A rede é

particionada em uma floresta de árvores. Cada árvore pode ser mapeada de forma ótima através

da técnica de programação dinâmica [Aho83].

A programação dinâmica determina a melhor solução para uma árvore calculando e

armazenando os valores ótimos para todas as subárvores. Considere, por exemplo, o problema

de cobrir uma árvore a partir de um conjunto de padrões de subárvores (figura 6.20).

Figura 6.20. Cobertura de uma árvore.

A idéia é montar a árvore a partir dos padrões, como se fosse um quebra-cabeças. Existem

diversas combinações de padrões que atingem esse objetivo. A cobertura com menor custo é

aquela cuja soma dos componentes é mínima. O custo das subárvores é indicado abaixo delas.

A estratégia da programação dinâmica é calcular o custo mínimo realizando todas as

combinações possíveis. O custo de cada combinação é armazenado numa tabela, de forma que

cada vez que se necessitar a avaliação de uma combinação parcial já realizada, basta consultar

a tabela para obter o seu custo. A vantagem da programação dinâmica rezide no fato de que cada

subárvore só é coberta uma vez. O algoritmo evita recalcular a cobertura armazenando os

valores obtidos. O algoritmo procede de maneira ascendente. O nó 1 é coberto pelo padrão a1,

assim como o nó 2. O nó 3 pode ser coberto de diversas maneiras:

• cobre {1, 2, 3} com padrões a1. Custo = 6.

• cobre {1, 3} com a2 e {2} com a1. Custo = 5.

• cobre {2, 3} com a2 e {1} com a1. Custo = 5.

• cobre {1, 2, 3} com a3. Custo = 4.

As alternativas são apresentadas na figura 6.21. A cobertura de menor custo é

implementada com o padrão a3. A cobertura do nó 3 requer primeiro a cobertura do nó 4. Só é

possível calcular o custo da cobertura de um nó n se de todos os descendentes de n já tem sua

cobertura ótima calculada. No caso do nó 4, a solução é trivial pois apenas o padrão a1 pode ser

árvore padrões

2 3 4

a1 a2 a3

1 2

3 4

5


utilizado. A cobertura do nó 3 é então obtida pela aplicação dos padrões e avaliação dos custos.

A figura 6.22 apresenta as alternativas. Ao aplicar o padrão a1 na raiz da árvore, sobram os nós

3 e 4 para serem cobertos. O custo global da cobertura da árvore é dado pela soma do custo de

a1 com o custo das coberturas de 3 e 4, ou seja, 8. A melhor solução é cobrir {4, 5} com um

padrão a2 e {1, 2, 3} com um padrão a3. O custo total é 7.

Figura 6.21. Cobertura de uma subárvore.

Figura 6.22. Cobertura de uma subárvore.

Cobertura Estrutural

A cobertura estrutural é obtida a partir do mapeamento estrutural da rede nas portas da

tecnologia. A rede é particionada em árvores de portas lógicas. A cobertura das árvores é

implementada basicamente da mesma forma apresentada acima. Porções adjacentes da árvore

de portas são agrupadas e associadas com dispositivos da tecnologia. O custo de uma cobertura

é aproximado pela soma dos custos das portas. Lembre que a complexidade das conexões não

é conhecida nesta altura da síntese e, por isso, a avaliação geral do mapeamento é apenas

aproximada. Exemplificamos o processo para o circuito apresentado na figura 6.23, juntamente

com uma biblioteca simplificada de portas lógicas, ambos representados por árvores de portas

NE2. A cobertura começa pelos nós conectados às entradas primárias. Nós {1, 2, 4} são

respectivamente mapeados em {NE2, NE2, INV}, conforme figura 6.24 (a). O custo do

mapeamento está indicado entre parênteses. Para o nó 3 uma alternativa é utilizar uma porta

NE2, como ilustrado em (b). Neste caso, as entradas 1 e 2 são mapeadas em portas NE2 e o custo

total para a cobertura do nó 3 é 9. Outra alternativa é cobrir o nó 3 com uma porta EOU22 (figura

6.24 (c)) com uma área acumulada de 6 unidades. Não havendo mais nenhuma alternativa para

a cobertura da rede até o nó 3, o mapeador retém o valor 6 como sendo a cobertura mínima. O

nó 5 pode ser mapeado em uma porta NE2 (figura 6.24(d)), obtendo-se uma árvore com área

11. Outra solução é mapear o nó 5 em uma porta EOU21 (figura 6.24(e)). O custo é igualmente

11. Portanto, ambas soluções dão o mesmo resultado. Por fim, para mapear o nó 6, pode-se

utilizar um inversor (figura 6.24(f)) ou uma porta EOUI21 (figura 6.24(g)). No primeiro caso,

1 2

3 4

5

1 2

3 4

5

1 2

3 4

5

1 2

3 4

5

a1

a1

a1

custo = 6 custo = 5 custo = 5 custo = 4

a1

a2a1

a2

1 2

3 4

5

1 2

3 4

5

1 2

3 4

5

1 2

3 4

5

a3

a1

a1

custo = 8 custo = 9 custo = 7 custo = 4

a1

a2

a3

a2

a1

a1

a3

a1 a1


a área é dada pela soma das áreas do inversor mais a do nó 5, cujo resultado é 13. No segundo

caso, o custo é dado pelo custo da porta EOUI21 mais o custo do mapeamento dos nós 1 e 2, o

que totaliza 12 unidades. Esta é a cobertura ótima para este circuito, para a biblioteca indicada.

Figura 6.23. Árvore de NE2 e biblioteca simplificada.

Figura 6.24. Cobertura da árvore.

1

23

45 6

Portas

Inv:

NE2:

NOU2:

EOUI21:

EOUI22:

Grafo NE2 Custo

2

3

3

5

6

EOU21:6

EOU22:

7

1 (3)

2 (3)3 (9)

45 6

1 (3)

2 (3)3

4 (2)5 6

1

23 (7)

4 (2)

5 (12) 6

1

23 (7)

45 6

1

23

4

5 (12) 6 (14)

1(3)

2(3)3

4

5 (12) 6

1 (3)

2 (3)3

45 6 (11)

(a)

(b)

(c)

(d)

(e)

(f)

(g)


Cobertura Estrutural com Atribuição de Fase aos Nós

Em uma rede Booleana, os nós podem tanto implementar tanto funções positivas quanto

negativas, como vimos no capítulo 5. A qualidade da cobertura obtida está ligada a combinação

de fases adotada. Vimos na seção 5.2.2.3 métodos genéricos que visam reduzir o número de

inversores necessários em uma rede Booleana. Naquele caso, parte-se do pressuposto de que a

rede é implementada com funções positivas E e OU. No caso do mapeamento, a implementação

da rede depende de fato das primitivas oferecidas pela tecnologia. O custo das portas pode variar

de uma tecnologia para outra apesar de, de modo geral, portas negativas serem via de regra mais

econômicas do que portas positivas. Este é caso da tecnologia CMOS, a mais utilizada

atualmente para projeto de circuitos VLSI. Por esses motivos, o problema da atribuição de fases

aos nós da rede é importante durante o mapeamento tecnológico.

Uma maneira interessante de aumentar o leque de alternativas de mapeamento em função

da fase dos nós foi proposta em [Det87]. Consiste em introduzir em cada conexão entre a saída

de uma porta e a entrada de outra um par de inversores. Esta operação só é realizada se nenhuma

das portas é um inversor. Como dois inversores em série não alteram um sinal lógico, este

truque não muda o comportamento da rede. Por outro lado, oferece novas opções para o

mapeamento. A cobertura da rede pode agora dispor de ambas as fases dos nós para o

mapeamento. Para que os inversores eventualmente não utilizados não interfiram no resultado

final do mapeamento, um elemento fictício é introduzido na biblioteca. É um par de inversores

em série, cuja implementação é um fio, com custo zero. O efeito da utilização deste elemento

de custo nulo durante o mapemento é a remoção de pares de inversores em série que não são

utilizados.

A introdução de par de inversores no circuito da figura 6.23 produz a árvore apresentada

na figura 6.25. Os pares de inversores são indicados com apóstrofe e aspas, herdando o nome

do nó fonte do sinal. O resultado do mapeamento é um circuito com custo 9. Os inversores

adicionais 3’ e 3” possibilitaram a escolha de duas portas negativas, com área global inferior

àquela obtida sem a atribuição de fase.

Figura 6.25. Mapeamento com atribuição de fase.

Cobertura Booleana

Naturalmente, a cobertura Booleana é aquela que utiliza o mapeamento ou casamento

Booleano de portas para implementar a rede lógica. O mapeamento Booleano apresenta

algumas vantagens com relação ao estrutural, conforme foi comentado na introdução deste

capítulo. Em termos de cobertura da rede, a vantagem maior é que o mapeamento Booleano não

1

23

45 6

3’ 3”1’ 1”

2’ 2”

(6)

(3)


se restringe a árvores. Redes também podem ser mapeadas, mas o problema do fanout não-

reconvergente (figuras 6.3 e 6.4) restringe a aplicação do mapeamento a subredes

reconvergentes.

Definição 6.4. Uma subrede é dita reconvergente quando nenhum sinal da rede é utilizado

por nós externos a ela.

♦A cobertura é realizada por um algoritmo que segue a estratégia de programação

dinâmica. A rede não é decomposta em árvores, mas apenas as subredes reconvergentes são

extraídas, para evitar a duplicação de nós. A cobertura de redes genéricas é um problema

intratável, daí a necessidade de simplificações como esta.

Durante a cobertura, a rede é logicamente dividida em subredes reconvergentes,

chamadas de clusters. Os clusters são obtidos a partir de um nó raiz. Ele mesmo é um cluster.

Os outros clusters são obtidos por colapso de nós no fanin transitivo da raiz, desde que estes nós

formem uma subrede reconvergente com a raiz. Dois critérios de parada no processo de

formação de clusters são (1) atingir uma entrada primária da rede e (2) alcançar um nó com

fanout não-reconvergente. Além disso, dois outros fatores são usualmente considerados para

limitar a clusterização da rede: (3) fanin máximo da tecnologia e (4) profundidade do cluster. O

fator (3) é uma restrição tecnológica aparentemente evidente. Se a tecnologia nos oferece

dispositivos de no máximo k entradas, não tem sentido gerar clusters com mais de k entradas.

Entretanto, o problema não é tão simples. O colapso de nós pode reduzir o fanin de um cluster

em uma subrede reconvergente. A limitação no número de entradas pode impedir que soluções

mais interessantes sejam encontradas. A limitação quanto à profundidade da rede é um

parâmetro ortogonal à restrição de fanin. Ela é utilizada para explorar de forma controlada a

rede, desde a cobertura trivial de uma porta por nó até a busca de subredes reconvergentes.

Exemplo 6.5. Considere a rede a seguir:

f = y1·y2

y1 = x1 ∨ x2

y2 = y3·x3

y3 = x4·x5∨ x6

O conjunto de clusters de f obtido pelo colapso das variáveis intermediárias é:

k0 = y1·y2

k1 = (x1 ∨ x2)·y2

k2 = y1·y3·x3

k3 = (x1 ∨ x2)·y3·x3

k4 = y1·(x4·x5 ∨ x6)·x3

k5 = (x1 ∨ x2)·(x4·x5 ∨ x6)·x3

♦O algoritmo de clusterização deve controlar a ordem com que os nós são agrupados para


evitar a geração de clusters repetidos. Além disso, deve prover uma maneira de identificar nós

com fanout reconvergente. Isso pode ser realizado verificando-se se todos os nós ligados ao nó

com multiplo fanout pertencem ao cluster. Um algoritmo para clusterização é apresentado na

figura 6.26.

gera_clusters(cluster, entradas, clusterlist, cond_parada)

{ /* cluster é uma subrede com um nó raiz */

/* entradas é a lista de nós de entrada a serem processados */

/* cond_parada é uma função que verifica critérios de parada */

if ( cond_parada ( cluster , entradas)) return ;

else loop {

if ( entradas == NULL) /* todas as entradas processadas */

return ;

no = pop ( entradas);

if ( no ≠ entrada primária and /* ignore entradas primárias */

fanout ( no) ⊆ cluster ) { /* e nós não-reconvergentes */

novo_cluster = cluster ∪ no;

clusterlist = clusterlist ∪ novo_ cluster;

gera_clusters ( novo_cluster ,

entradas ∪ suporte ( no),

clusterlist ,

cond_parada );

}

}

}

Figura 6.26. Algoritmo para geração de clusters.

O algoritmo é chamado inicialmente com um cluster formado por apenas um nó, a sua

raiz. Em entradas são colocadas as entradas do nó e clusterlist é iniciada com o cluster raiz.

cond_parada é uma função que avalia condições de parada da recursão como aquelas

enumeradas acima. O corpo do algoritmo é um laço onde os nós da lista de entradas são

consumidos a cada ciclo. Quando entradas estiver vazio o algoritmo terminou o processamento

do cluster corrente. Cada nó da lista entradas é testado para verificar se é uma entrada primária

ou se tem um fanout não-reconvergente. Em ambos os casos o nó é (lamentavelmente para ele)

desprezado. A não-reconvergência é facilmente detectada verificando-se se os nós no seu fanout

não estão contidos no cluster em processamento. Se as condições de clusterização são

satisfeitas, forma-se um novo cluster agrupando-se o nó selecionado ao cluster corrente. Este é

incluído na lista de clusters, clusterlist. A clusterização em profundidade é realizada pela

chamada recursiva de gera_clusters sobre o novo cluster obtido, incluindo-se o fanin do nó


selecionado à lista entradas. Note, portanto, que o laço tem por função o agrupamento de nós

em largura enquanto que a recursão é utilizada para o agrupamento de nós em profundidade.

Exemplo 6.6. A figura 6.27(a) ilustra o processo de clusterização para uma subrede

reconvergente. O cluster raiz é o que contém o nó y5. Suas entradas são os nós

{y3, y4}. gera_clusters toma em primeiro lugar o nó y3, formando um novo

cluster {y5, y3}. As entradas do novo cluster são {x3, y2, y4}. x3 é ignorada pois

é variável primária. O colapso de y2 produz o cluster {y5, y3, y2}, com entradas

{x2, y1, y4}. y1 é ignorada pois seu fanout {y2, y4} ⊄ {y5, y3, y2}. y4, por sua

vez, é agrupada formando o cluster {y5, y3, y2, y4}, com entradas {x3, y1}.

Desta vez fanout(y1) = {y2, y4} ⊆ {y5, y3, y2, y4}, e y1 é agrupada ao cluster,

produzindo {y5,y3,y2,y4,y1}. O algoritmo retrocede as etapas anteriores da

recursão produzindo os clusters indicados na árvore de soluções apresentada

na figura 6.26(b).

♦

Figura 6.27. Clusterização de uma subrede reconvergente.

A programação dinâmica por meio de clusters requer que o algoritmo gera_clusters seja

aplicado para todos os nós da rede. Todos os clusters gerados para um nó raiz devem ser

mapeados e avaliados. O custo de um mapeamento é dado pelo custo da porta associada mais o

custo do mapeamentos das suas entradas. O algoritmo começa pelas saídas da rede. Para avaliar

o custo da associação de uma porta a uma porção da rede o algoritmo de cobertura é reaplicado

recursivamente a cada entrada não mapeada do cluster. A recursão prossegue até as entradas

primárias. Durante o retrocesso da recursão os nós vão sendo mapeados das entradas primárias

em direção às saídas, de forma similar à cobertura estrutural.

A questão da atribuição de fases na cobertura Booleana é tratada de forma diferente da

cobertura estrutural. A manipulação de clusters como funções Booleanas simplifica a tarefa no

sentido que pode-se realizar o mapeamento para ambas as fases de cada nó [Mai88, Jac93].

x0

x1

x2

x3

x2

y4

y3

y5

y2

y1

f

y5

y5,y3

y5,y3,y2

y1 não podeser agrupado

y5,y3,y2,y4

y5,y3,y2,y4,y1

y5,y3,y4

y5,y4

{y3, y4}

{x3,y2, y4}

{x2,x3,y1, y4}

{x2,x3, y1}

{x0,x1,x2,x3}

{x2,x3,y1, y2}

{x2,y1, y3}

(b)(a)


Assim, se uma função requer o complemento de uma entrada yj, em vez de se

incluir um inversor na entrada de yi seleciona-se a porta que implementa yj. Ambas as fases do

mapeamento podem igualmente ser utilizadas na etapa final de minimização de inversores da

rede mapeada [Jac93a].

6.3 Comentários

O mapeamento tecnológico para performance e baixa potência segue em linhas gerais um

método similar, porém com algumas diferenças na aplicação das funções custo. O mapeamento

visando obter um circuito com atraso mínimo pode ser bastante complexo em função da

necessidade de deteção e eliminação de caminhos falsos na rede e do correto dimensionamento

da capacidade de acionamento de cada porta [Keu90]. Tanto no caso da performance como no

da baixa potência são necessários modelamentos mais apurados do comportamento elétrico do

circuito, o que introduz dificuldades adicionais.

Cabe salientar que o mapeamento para dispositivos programáveis pode requerer métodos

bastante particulares em função do tipo de dispositivo empregado. Na família dos FPGAs, dois

dispositivos dos mais populares são os da ACTEL [ElG89], baseados em multiplexadores, e os

da Xilinx [Xil94] e Altera, baseados em look-up tables (LUTs). Para as células ACTEL uma

série de métodos baseados em BDDs foram desenvolvidos [Mur92, Ben92, Jac94a]

principalmente devido a equivalência entre nós do BDD em multiplexadores de duas entradas.

Por outro lado, os dispositivos baseados em LUTs implementam quaisquer funções de um

determinado número de entradas. O mapeamento, neste caso, está mais relacionado ao

problema de decompor uma função em um conjunto mínimo de blocos com número restrito de

variáveis.

6.4 Referências

[Aho75] A. Aho, M. Corasick. “Efficient String Matching: An Aid to Bibliographic Search”.In: Communications of the ACM, vol. 18, no. 6, pp. 333-40, June 1975.

[Aho83] A. Aho, J. Hopcroft and J. Ullman. “Data Structures and Algorithms”. Addison-Wes-ley, Reading, Massachusetts. 1983.

[Ben92] T. Benson, H. Bouzouzou, M. Crastes, I. Floricia and G. Saucier. “Synthesis on Mul-tiplexor-based FPGAs using Binary Decision Diagrams”. In: Proceedings of ICCD, 1992.

[Che93] K. Chen. “Boolean Matching Based on Boolean Unification”. In: Proceedings of Eu-ropean Design Automation Conference, pp. 346-51, 1993.

[Cra91] M. Crastes, K. Sakouti and G. Saucier. “A Technology Mapping Method Based on Per-fect and Semi-Perfect Matchings”. In: Proceedings of 28th Design Automation Conference,,1991.

[Dar81] J. A. Darringer, D. Brand, J. Gerbi, W. Joyner and L. Trevillyan. “Logic SynthesisThrough Local Transformations”. In: IBM Journal of Research and Development, Vol. 25,no. 4, pp. 272-280, July 1981.

yi y j yk⋅=


[Dar84] J. A. Darringer et al. “LSS: A System for Production Logic Synthesis”. In: IBM Journalof Research and Development, Vol. 28, no. 5, pp. 537-545, Sep. 1984.

[Dav91] M. Davio. “Technology Mapping”. Unpublished Report.

[Dem94] G. De Micheli. “Synthesis and Optimization of Digital Circuits”. McGraw-Hill, 1994.

[Det87] E. Detjens, G. Ganot, R. Rudell, A. Sangiovanni-Vincentelli, A. Wang. “TechnologyMapping in MIS”. In: Proceedings of IEEE International Conference on Computer-AidedDesign, Nov. 1987.

[ElG89] A. ElGamal, J. Green, J. Reyneri, E. Rogoyski, K. El-Ayat and A. Mohsen. “An Ar-chitecture for Electrically Configurable Gate Arrays”. In: IEEE Journal of Solid State Cir-cuits, 24(2), pp. 394-398, April 1989.

[Geu85] A. J. de Geus, W. Cohen. “A Rule-Based System for Optimizing Combinational Log-ic”. In: IEEE Design & Test of Computers. 1985.

[Jac93] R. Jacobi and A.M. Trullemans. “Boolean Mapping with Binary Decision Diagrams”.IFIP International Workshop on Logic and Architecture Synthesis, anais, Grenoble - França.Dezembro, 1993.

[Jac93a] R. Jacobi. “A Study of the Application of Binary Decision Diagrams on Multi-levelLogic Synthesis”. Doctoral Thesis, Université Catholique de Louvain, Belgium. Dec. 1993.

[Jac94] R. Jacobi. “Symmetry Detection in Logic Functions”. In: Proceedings of VIII Simpósiode Concepção de Circuitos Integrados, Gramado, RS. Novembro 1994.

[Jac94a] R. Jacobi. “Multiplexor Based FPGA Synthesis”. In: Proceedings of IX Congresso daSociedade Brasileira de Microeletrônica - SBMicro, Rio de Janeiro - RJ, Brazil. August1994, pp. 437-446.

[Keu87] K. Keutzer. “DAGON: Technology Binding and Local Optimization by DAG Match-ing”. In: Proceedings of 24th Design Automation Conference, 1987.

[Keu90] K. Keutzer, S. Malik and A. Saldanha. “Is Redundancy Necessary to Reduce Delay?”.In: Proceedings of 27h Design Automation Conference, 1990.

[Mai88] F. Maillot and G. De Micheli. “Technology Mapping using Boolean Matching”. In:Proceedings of IEEE International Conference on Computer-Aided Design, 1988.

[Mor93] F. Moraes, N. Azemard, M. Robert and D. Auvergne. “Flexible Macrocell LayoutGenerator”. In: Proceedings of 4th ACM/SIGDA Physical Design Workshop, Los Angeles(USA), pp. 105-116. 1993.

[Mur92] R. Murgai, R. Brayton and A. Sangiovanni-Vincentelli. “An Improved Synthesis Al-gorithm for Multiplexor-based PGA’s’. In: Proceedings of 29th Design Automation Confer-ence, June, 1992.

[Sav92] H. Savoj, R. Brayton. “The Use of Observability and External Don't Cares for the Sim-plification of Multi-Level Networks”. In: Proceedings of 27h Design Automation Confer-ence, pp. 168-74, 1990.

[Xil94] Xilinx, Inc., “Xilinx Programmable Gate Array Data Book”, 1994.


Documents

Capítulo 6 - sites.poli.usp.brsites.poli.usp.br/d/psi5742/pdf/cap6.pdf · 133 Capítulo 6 Mapeamento Tecnológico A síntese lógica pode ser divida em duas tarefas principais. A