Fatoração Booleana Utilizando Composição Funcional

Síntese LógicaComposição Funcional

Referências

Fatoração Booleana UtilizandoComposição Funcional

Jody Maick A. de Matos1

Prof. André I. Reis1

1Universidade Federal do Rio Grande do SulInstituto de Informática

Programa de Pós-graduação em Microeletrô[email protected]

Porto Alegre, 2013

J. M. A. Matos Fatoração Booleana com Composição Funcional 1 / 25


Referências

Roteiro

1 Síntese LógicaContextualização

2 Composição FuncionalBaselineHeurística

3 Referências



Referências

Créditos

Todo o material utilizado nessa apresentação, bem como oalgoritmo apresentado, têm como base os artigos científicos (esuas respectivas apresentações em conferências) listados nasreferências: [Reis et al. 2009, Figueiro, Ribas e Reis 2010,Martins et al. 2010, Martins et al. 2012,Martins, Ribas e Reis 2012].



ReferênciasContextualização

Roteiro



3 Referências




Síntese Lógica

Usualmente realizada em dois passosSíntese independente de tecnologiaSíntese dependente de tecnologia

Síntese independente de tecnologiaOtimizações no nível lógico

Síntese dependente de tecnologiaMapear uma abstração lógica para um abstração física




Síntese LógicaSíntese dependente de tecnologia

Fatoração:

Eq# Equação L(1) f = b · (d + c) + (a + d + c) · (a + b · c) 9(2) f = c · (b + a) + c · (a · d + (d + b) · (b + a)) 10(3) f = (c + b + a) · (c + a · d + (d + b) · (b + a)) 10(4) f = b · (d + c + a) + b · (c + a) · (a + d + c) 10





E se quisermos inserir outros custos?

Eq# Equação L S P(1) f = b · (d + c) + (a + d + c) · (a + b · c) 9 3 5(2) f = c · (b + a) + c · (a · d + (d + b) · (b + a)) 10 3 5(3) f = (c + b + a) · (c + a · d + (d + b) · (b + a)) 10 3 4(4) f = b · (d + c + a) + b · (c + a) · (a + d + c) 10 3 6

Menor número de literais: Eq 1Menor associação de transistores em paralelo: Eq 3





E se quisermos inserir outros custos?

Eq# Equação L S P(1) f = b · (d + c) + (a + d + c) · (a + b · c) 9 3 5(2) f = c · (b + a) + c · (a · d + (d + b) · (b + a)) 10 3 5(3) f = (c + b + a) · (c + a · d + (d + b) · (b + a)) 10 3 4(4) f = b · (d + c + a) + b · (c + a) · (a + d + c) 10 3 6

Menor número de literais: Eq 1Menor associação de transistores em paralelo: Eq 3



ReferênciasBaselineHeurística

Roteiro



3 Referências




Composição FuncionalBaseline

Enumerar todas as funções com 1 literal: a, a, b, b, c, c, ...






Combinar as funções de 1 literal para obter as de 2 literais






Combinar as funções de 1 literal para obter as de 2 literaisContinuar combinando até que a função objetivo sejaencontrada





























Qual(is) o(s) problema(s)com esse algoritmo?

Estoura no tempo...Estoura em memória... (no funções = 22n)






Estoura no tempo...

Estoura em memória... (no funções = 22n)






Estoura no tempo...Estoura em memória... (no funções = 22n)




Composição FuncionalHeurística

Realizar as combinações de forma rápidaConcatenação de stringsOperações bitwise

Estrutura bonded-pairs<função/implementação><bit bector/string>




Composição FuncionalFunções Permitidas

Função alvo: f = (a + b) · (c + a · d)

Co-fatores Cubo co-fatoresf|a=1| = c f|a=0,b=1| = c + d

f|a=0| = b(c + d) f|a=0,c=1| = bf|b=1| = c + ad f|a=0,c=0| = bd

f|b=0| = ac f|a=0,d=0| = bcf|c=1| = a + b f|b=1,c=0| = adf|c=0| = abd f|b=0,c=1| = a

f|d=1| = (a + b)(c + a) f|c=0,d=1| = abf|d=0| = c(a + b) f|a=0,b=1,c=0| = d

—— f|b=1,c=1,d=1| = a—— f|b=1,d=1| = c + a




Composição FuncionalExemplo



















Referências

Roteiro



3 Referências



Referências

FIGUEIRO, T.; RIBAS, R.; REIS, A. Functional compositionapplied to aig constructive optimization. In: South BrazilSimposium on Microelectronics. [S.l.: s.n.], 2010.

MARTINS, M. et al. Functional composition paradigm andapplications. In: Proceedings of the International Workshop onLogic and Synthesis 2012. Berkeley, CA, USA: [s.n.], 2012.(IWLS ’12). Acesso em: 04 Jul. de 2012.

MARTINS, M.; RIBAS, R.; REIS, A. Functional composition: Anew paradigm for performing logic synthesis. In: QualityElectronic Design (ISQED), 2012 13th International Symposiumon. [S.l.: s.n.], 2012. p. 236–242. ISSN 1948-3287.

MARTINS, M. et al. Boolean factoring with multi-objectivegoals. In: Computer Design (ICCD), 2010 IEEE InternationalConference on. [S.l.: s.n.], 2010. p. 229–234. ISSN 1063-6404.



Referências

REIS, A. et al. Fast boolean factoring with multi-objectivegoals. In: Proceedings of the International Workshop on Logicand Synthesis 2009. Berkeley, CA, USA: [s.n.], 2009. (IWLS’09). Disponível em:<http://inf.ufrgs.br/logics/docman/conf_2009_iwls_andre.pdf>.Acesso em: 04 Jul. de 2012.



Referências

[email protected]

Obrigado!Mais um pouco sobre o assunto:inf.ufrgs.br/~jmamatos/doku.php/downloads:mic63Baixe essa apresentação: slideshare.net/JodyMatos


Education

Fatoração Booleana Utilizando Composição Funcional