A Two level approximate logic synthesis method based on insertion and removal of cubes

Abstract

Approximate computing is a design paradigm that allows systems to have imprecise or inexact execution, aiming to optimize performance and power dissipation. When ap proximate computing is applied to systems that perform error-resilient applications, it is possible to optimize without critically degrading the expected application operation. The presented work focuses on exploring approximate computing at the circuit level, more specifically, digital integrated circuits (IC). Electronic design automation tools provide a highly automated IC design flow, which may be roughly divided into three main steps: high-level synthesis, logic synthesis and physical synthesis. The logic synthesis step has as a goal the gate network building and optimization targeting a given technology. The logic synthesis is performed over two-level (2L) or multiple-level topologies of combi national blocks. The employment of approximate computing at the circuit level consists of deriving a gate network implementation that is not logically equivalent to the original circuit behavior specification but can improve area, performance and power dissipation. Several works propose techniques to approximate circuits automatically by systematically modifying a general logic behavior without exceeding a given error threshold. Due to the similarity among those techniques, the adopted data structures and optimization goals through logic synthesis, the automatic construction of approximate circuits at this design phase is called approximate logic synthesis (ALS). Conventional logic synthesis methods to build two-level circuits are employed as part of multilevel synthesis methods and for synthesizing systems over CPLD architectures. Besides the benefits of approximate sum of-products (SOP) and product-of-sums (POS), the approximation of 2L circuits can be exploited in both applications. Moreover, investigations over 2L-ALS methods represent an important contribution to further advancements also on multilevel ALS. This work proposes a two-level approximate logic synthesis method that receives an SOP expres sion and a given error rate threshold as inputs and generates an approximate SOP with an optimized number of literals. In this work, we also intend to derive a scalable method that allows the insertion of more errors than is observed in existing 2L-ALS works. The experimental results show that the proposed approach can derive SOPs with fewer liter als compared to the state-of-the-art method for the same amount of errors. The obtained solutions reach an average literal count reduction of circa 38% with an error rate of 1%, 56% with an error rate of 3%, and up to 93% with an error rate of 5%. Moreover, as it is unknown how approximations made in two-level structures impact the quality of multilevel circuit design, we have carried out some experiments that apply two-level, and multilevel ALS approaches interchangeably to build approximate circuits and so analyze the obtained solutions.

Computação aproximada é um paradigma que permite que um sistema tenha uma execu ção imprecisa ou inexata com o objetivo de otimizar o seu desempenho e sua eficiência energética. Quando este paradigma é aplicado em sistemas que executam funções resi lientes a erros, é possível otimizar o sistema sem degradar de forma crítica a operação desejada. Este trabalho foca no uso de computação aproximada no nível de circuitos, em particular, nos circuitos integrados digitais (CI). Ferramentas de projeto de circuitos integrados fornecem um fluxo altamente automatizado para do projeto de CIs. Este fluxo pode ser dividido em três passos principais: síntese de alto nível, síntese lógica e síntese física. A síntese lógica tem como objetivo otimizar a lógica do circuito e implementá-lo em uma dada tecnologia alvo. A síntese lógica é executada sobre representações dois níveis ou multinível que implementam a lógica combinacional de um dado circuito. A aplicação de computação aproximada no nível de circuitos consiste em obter uma im plementação que não é logicamente equivalente à especificação mas consegue realizar otimizações em área, desempenho e consumo de energia. Diversos trabalhos propõem técnicas para aproximar um circuito de forma automática através de modificação siste mática do funcionamento de um circuito genérico sem exceder uma dada restrição de erro. Devido à similaridade em técnicas, estruturas de dados e objetivos de otimização com a etapa de síntese lógica, a geração automática de circuitos aproximados é frequente mente chamada de síntese lógica aproximada. Métodos de síntese lógica tradicional para construção de circuitos dois-níveis podem ser utilizados para síntese de componentes pro gramáveis CPLDs, bem como parte de métodos para síntese de circuitos multinível. Além da geração de expressões aproximadas do tipo somas-de-produtos (SOP) e produtos-de somas (POS), técnicas de aproximação para circuitos dois-níveis poder ser exploradas nesses dois canários. Além disso, o entendimento dos conceitos e técnicas relacionados à aproximação dois-níveis pode contribuir significativamente para futuros estudos sobre a aproximação de circuitos multinível. Este trabalho propõe um método para aproximar circuitos dois-níveis que tem como entrada uma SOP e um dado limite de frequência de erro, e gera uma expressão aproximada com um número de literais reduzido e que respeita o dado limite de erro. O método proposto foi desenvolvido com a intenção de ser escalável em relação à quantidade de erros permitidos, possibilitando uma inserção de mais erros do que é observado em outros trabalhos que abordam o mesmo problema. Nos resultados experimentais obtidos, o método proposto gerou SOPs aproximadas com menos literais do que o obtido pelo método considerado estado-da-arte nesta tecnologia, para a mesma quantidade de erros. Comparando com a SOP original, o presente método obteve uma redução de literais média de 38% com frequência de erro de 1%, 56% com frequência de erro de 3%, e de até 93% frequência de erro de 5%. Como o impacto das aproxima ções feitas em uma representação dois-níveis na qualidade de um circuito multinível, e vice-versa, é desconhecido, foram feitos experimentos explorando técnicas de aproxima ção dois-níveis e multinível em conjunto para geração de circuitos aproximados, e para análise das soluções obtidas.