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ônicajody.matos@inf.ufrgs.br

Porto Alegre, 2013

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

Síntese LógicaComposição Funcional

Referências

Roteiro

1 Síntese LógicaContextualização

2 Composição FuncionalBaselineHeurística

3 Referências

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

Síntese LógicaComposição Funcional

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].

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

Síntese LógicaComposição Funcional

ReferênciasContextualização

Roteiro

1 Síntese LógicaContextualização

2 Composição FuncionalBaselineHeurística

3 Referências

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

Síntese LógicaComposição Funcional

ReferênciasContextualização

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

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

Síntese LógicaComposição Funcional

ReferênciasContextualização

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

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

Síntese LógicaComposição Funcional

ReferênciasContextualização

Síntese LógicaSíntese dependente de tecnologia

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

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

Síntese LógicaComposição Funcional

ReferênciasContextualização

Síntese LógicaSíntese dependente de tecnologia

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

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

Roteiro

1 Síntese LógicaContextualização

2 Composição FuncionalBaselineHeurística

3 Referências

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

Composição FuncionalBaseline

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

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

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

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

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 literaisContinuar combinando até que a função objetivo sejaencontrada

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

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 literaisContinuar combinando até que a função objetivo sejaencontrada

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

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 literaisContinuar combinando até que a função objetivo sejaencontrada

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

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 literaisContinuar combinando até que a função objetivo sejaencontrada

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

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 literaisContinuar combinando até que a função objetivo sejaencontrada

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

Composição FuncionalBaseline

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

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

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

Composição FuncionalBaseline

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

Estoura no tempo...

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

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

Composição FuncionalBaseline

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

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

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

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>

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

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

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

Composição FuncionalExemplo

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

Composição FuncionalExemplo

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

Composição FuncionalExemplo

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

Composição FuncionalExemplo

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

Síntese LógicaComposição Funcional

ReferênciasBaselineHeurística

Composição FuncionalExemplo

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

Síntese LógicaComposição Funcional

Referências

Roteiro

1 Síntese LógicaContextualização

2 Composição FuncionalBaselineHeurística

3 Referências

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

Síntese LógicaComposição Funcional

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.

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

Síntese LógicaComposição Funcional

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.

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

Síntese LógicaComposição Funcional

Referências

Contatojody.matos@inf.ufrgs.br

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

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