A study of false loop and false path in high-level synthesis
Alan P. Su · 1998
The timing has become one of the most important design criteria in the IC design. The false path analysis is a key area of research in the timing optimization and analysis. In this work we discussed problems associated with false loop removal and Register Transfer Level (RTL) false path. In the high-level synthesis, resource sharing may result in a circuit containing false loops that pose great difficulty in timing validation at the design sign-off phase. It is hence desirable to avoid generating any false loops in a synthesized circuit. Previous work considered mainly data path sharing for false loop elimination. However, for a circuit containing both data path and control path, false loops may be created due to control logic sharing, even though the loops caused by data path sharing are all removed. We have presented a novel approach to detect and eliminate the false loops produced by control logic sharing. An effective filter was devised to reduce the computational load for detecting false loops. In the proposed scheme, only the input/output pairs of the control path identified by the filter were investigated in order to detect the false loops. A removal algorithm was proposed to eliminate the detected false loops, following by the logic minimization to further optimize the design. Experimental results showed that, for nine designs we tested, the resulting designs after false loop removal and logic minimization were only slightly larger than those containing false loops. The next problem we studied was the RTL false path problem. To our best knowledge, very little work has been done for false path problems at RTL. In this work, we first found that most false paths that existed at RTL survived through the synthesis process to the gate level, due to the nature of resource allocation in the high-level synthesis and the fact that these false paths were usually difficult to be eliminated by the logic synthesis. The survived false paths were very hard for a timing analyzer to identify. The false path survivorship suggested the need to study false paths at RTL. In this work we first analyzed the false path characteristics to give a new direction for defining false paths. Using the new definition we implement an exact RTL false path identification algorithm. However, the analysis showed the RTL false path identification was an NP complete problem. Then we analyzed three types of RTL false paths and developed identification algorithms. Traditional representations could not represent false path during synthesis. We proposed a modified Assignment Decision Diagram to preserve the false path information during and after the synthesis. Experimental results showed that RTL false paths survived through synthesis to the gate level in 21 out of 22 tested designs. In the test designs, the false path identification gave an average of 26.90% improvement in timing estimation. This promising result showed the critical need for developing algorithms in identifying more RTL false paths.