The Case for a Balanced Decomposition Process
Jan Schmidt, Petr Fišer · 2009
We present experiments with synthesis tools using examples which are currently believed to be very hard, namely the LEKU examples by Cong and Minkovich and parity examples of our construction. In both cases, we found a way to produce reasonable results with existing tools. We identify the abilities that are crucial for achieving such results, and also generalize them to avoid similar cases of poor performance in future tools. I. INTRODUCTION Logic synthesis is believed to be a matured process, giving results reasonably close to optimum. Yet, there are still circuits which are very hard for any synthesis process. Cong and Minkovich (1) published a method for the construction of combinational circuits with known optimal implementa- tion (LEKO) or with known upper bound (LEKU). Here we study the latter ones, as the gap between the upper bound and obtained results are the largest. Our parity examples (2) are another case of difficult circuits. Synthesis tools give results an order or two bigger than a known upper bound. We investigated the reasons of the observed poor per- formance experimentally. We succeeded in finding tools and procedures that give satisfactory (i.e. not orders of magnitude worse) results, experimented further to obtain clues what makes those tools and procedures successful. First we describe our experimental methods. Secondly, ex- periments with both sets of examples are described together with the results obtained. Finally, we interpret the results and give requirements for future tools.