Optimization models for majority logic synthesis
Arquivos
Data
2022-12-21
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Estadual Paulista (Unesp)
Resumo
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.
This work presents the 3MS (Majority Math Model Solver) algorithm, used for majority of-three and majority-of-five logic synthesis. The new proposed algorithm receives a vector of binary numbers as input, representing the output of a truth table, and returns an optimized majority function for its coverage. Key in this approach is the formulation of constraints that encodes majority logic problems into linear optimization problems. The resulting set of constraints is then applied to an optimization solver and the results translated into the output majority function. The 3MS algorithm considers both depth and size as first and second cost criteria, making it possible to choose which of these criteria will be prioritized. As third and fourth cost criteria, the minimization of inverters and literals is considered. The 3MS algorithm was evaluated based on a comparison with 2 exact synthesis algorithms for both majority-of-three and majority-of-five networks. Both synthesis have only depth and size as cost criteria. Since the 3MS considers 2 additional cost criteria, the goal of the algorithm is to generate functions that are also exact in relation to depth and size, but with less inverters and literals. When compared to both algorithms, simulation studies have shown that the 3MS was able to further improve 64% of all 220,376 compared functions, and achieved equal results for the remaining 36%. The 3MS algorithm was also evaluated based on the EPFL (Ecole Polytechnique F´ed´erale de ´ Lausanne) benchmark suites, where the algorithm was able to generate competitive results for all 10 circuits that composes the benchmark.
This work presents the 3MS (Majority Math Model Solver) algorithm, used for majority of-three and majority-of-five logic synthesis. The new proposed algorithm receives a vector of binary numbers as input, representing the output of a truth table, and returns an optimized majority function for its coverage. Key in this approach is the formulation of constraints that encodes majority logic problems into linear optimization problems. The resulting set of constraints is then applied to an optimization solver and the results translated into the output majority function. The 3MS algorithm considers both depth and size as first and second cost criteria, making it possible to choose which of these criteria will be prioritized. As third and fourth cost criteria, the minimization of inverters and literals is considered. The 3MS algorithm was evaluated based on a comparison with 2 exact synthesis algorithms for both majority-of-three and majority-of-five networks. Both synthesis have only depth and size as cost criteria. Since the 3MS considers 2 additional cost criteria, the goal of the algorithm is to generate functions that are also exact in relation to depth and size, but with less inverters and literals. When compared to both algorithms, simulation studies have shown that the 3MS was able to further improve 64% of all 220,376 compared functions, and achieved equal results for the remaining 36%. The 3MS algorithm was also evaluated based on the EPFL (Ecole Polytechnique F´ed´erale de ´ Lausanne) benchmark suites, where the algorithm was able to generate competitive results for all 10 circuits that composes the benchmark.
Descrição
Palavras-chave
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