Optimization models for majority logic synthesis

• Ano de defesa: 2022
• Autor(a) principal: Ferraz, Evandro Catelani
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Estadual Paulista (Unesp)
• Palavras-chave em Português: Lógica majoritária; Funções primitivas; Síntese lógica; Solucionadores de otimização; Otimização linear; Majority logic; Primitive functions; Logic synthesis; Optimization solver; Linear optimization
• Link de acesso: http://hdl.handle.net/11449/238331

Neste trabalho apresenta-se o algoritmo 3MS (Majority Math Model Solver), utilizado para síntese de lógica de funções majoritárias com operadores de 3 ou 5 entradas. O novo algoritmo proposto recebe um vetor de números binários como entrada, representando a saída de uma tabela verdade, e retorna uma função majoritária otimizada para sua cobertura. A característica principal desta abordagem é a formulação de restrições que codificam problemas de lógica majoritária em problemas de otimização linear. O conjunto de restrições é então aplicado a um solucionador de otimização e os resultados transcritos em uma função majoritária de saída. No algoritmo 3MS, considera-se tanto o número de níveis quanto de operadores como primeiro ou segundo critérios de custo, possibilitando a escolha de qual destes critérios será priorizado. Como terceiro e quarto critérios de custo, considera-se a minimização de inversores e de literais. O desempenho do algoritmo 3MS foi avaliado a partir de uma comparação com 2 algoritmos de síntese exata para funções majoritárias com operadores de 3 e 5 entradas. Em ambas as sínteses, considera-se apenas o número de níveis e de operadores como critérios de custo. Tendo em vista que no algoritmo 3MS considera-se 2 critérios de custo adicionais, tem-se como objetivo gerar funções que também sejam exatas em relação ao número de níveis e operadores, porém possuam menos inversores e literais. Quando comparado a ambos algoritmos de síntese exata, testes mostraram que o algoritmo 3MS gerou melhores resultados para 64% de todas as 220.376 funções testadas, enquanto atingiu resultados equivalentes para as 36% restantes. O algoritmo 3MS também foi avaliado a partir de uma comparação com o benchmark EPFL (École Polytechnique Fédérale de Lausanne), sendo capaz de gerar resultados competitivos para todos os 10 circuitos que compõem o benchmark.