Satisfiability-based covering of AIGs using KL-cuts

Abstract

The rapid advancement of Very-large-scale integration (VLSI) silicon integration has revolutionized the electronics industry, enabling the integration of billions of transistors into a single integrated circuit. This complexity necessitates the use of Electronic Design Automation (EDA) tools for VLSI design. These tools automate various tasks, with the design process typically divided into logic synthesis and physical design stages. Logic synthesis involves capturing the initial logic description and generating a netlist of interconnected cell instances, while physical design focuses on placing and routing these instances to create a circuit layout ready for fabrication. Over the past two decades, logic synthesis has heavily relied on the And-Inverter-Graph (AIG) data structure for its scalability and result quality. This thesis introduces a contribution to logic synthesis based on AIGs, specifically focusing on computing AIG covers with KL-cuts, where both the number of inputs (K) and outputs (L) are controlled. While previous work has proposed the use of KL-cuts in synthesis flow, efficient algorithms for covering AIGs with KL-cuts have been lacking. This thesis addresses this issue by presenting an algorithm to optimize this task. Additionally, a detailed review of AIG cut types is provided. Existing synthesis methodologies often lack efficient algorithms for AIG covering with KL-cuts, necessitating the development of optimized solutions. In this thesis are proposed two novel contributions to logic synthesis using AIGs, focusing on KL-cut computation to enhance synthesis efficiency. The first contribution introduces a novel method for expanding single-output cuts into KL-cuts. The second contribution presents a satisfiability-based approach for generating AIG covers using KL-cuts. Experimental results validate the effectiveness of these contributions. The proposed cut expansion method achieved a 1.25x speedup compared to the MFFW method. Furthermore, the proposed approach successfully generated KL-cut covers with a reduction: 49.01% compared to K-cuts from ABC and 7.51% compared to multi-output covers derived from post-processing of ABC results. Keywords: And-inverter graph. electronic design automation. cuts in AIGs. KL-cuts. logic synthesis. very-large-scale integration. satisfiability.

O rápido avanço da integração de silício em Integração em Larga Escala (VLSI) revolucionou a indústria de eletrônicos, permitindo a integração de bilhões de transistores em um único circuito integrado. Essa complexidade exige o uso de ferramentas de Automa- ção de Projeto Eletrônico (EDA) para o design de VLSI. Essas ferramentas automatizam várias tarefas, com o processo de design tipicamente dividido em etapas de síntese lógica e design físico. A síntese lógica envolve capturar a descrição lógica inicial e gerar uma lista de interconexões entre instâncias de células, enquanto o design físico se concentra na colocação e roteamento dessas instâncias para criar um layout de circuito pronto para a fabricação. Nas últimas duas décadas, a síntese lógica tem dependido fortemente da estrutura de dados And-Inverter-Graph (AIG) devido à sua escalabilidade e qualidade dos resultados. Esta tese apresenta uma contribuição para a síntese lógica baseada em AIGs, especificamente focando no cálculo de coberturas de AIG com KL-cuts, onde tanto o nú- mero de entradas (K) quanto de saídas (L) são controlados. Embora trabalhos anteriores tenham proposto o uso de KL-cuts em fluxos de síntese, algoritmos eficientes para cobrir AIGs com KL-cuts têm sido escassos. Esta tese aborda essa questão apresentando um algoritmo para otimizar essa tarefa. Além disso, é forne uma revisão detalhada dos tipos de cortes em AIGs. Metodologias de síntese existentes frequentemente carecem de algoritmos eficientes para cobertura de AIG com KL-cuts, exigindo o desenvolvimento de soluções otimizadas. Nesta tese, são propostas duas contribuições inovadoras para a síntese lógica usando AIGs, com foco no cálculo de KL-cuts para melhorar a eficiência da síntese. A primeira contribuição introduz um método inovador para expandir cortes de saída única em KL-cuts. A segunda contribuição apresenta uma abordagem baseada em satisfatibilidade para gerar coberturas de AIG usando KL-cuts. Resultados experimentais validam a eficácia dessas contribuições. O método de expansão de cortes proposto alcançou uma aceleração de 1,25 vezes em comparação com o método MFFW. Além disso, a abordagem proposta gerou com sucesso coberturas KL-cut com uma redução de 49,01% em comparação com K-cuts do ABC e 7,51% em comparação com coberturas multi-saídas derivadas do pós-processamento dos resultados do ABC.