Eliminating false loops caused by sharing in control path

ABSTRACT

In high-level synthesis, resource sharing may result in a circuit containing false loops that create great difficulty in timing validation during the design sign-off phase. It is hence desirable to avoid generating any false loops in a synthesized circuit. Previous work [Stok 1992; Huang et al. 1995] considered mainly data path sharing for false loop elimination. However, for a complete circuit with both data path and control path, false loops can be created due to control logic sharing. In this article, we present a novel approach to detect and eleminate the false loops caused by control logic sharing. An effective filter is devised to reduce the computational complexity of false loop detection, which is based on checking the level numbers that are propagated from data path operators to imputs and outputs of the control path. Only the input/output pairs of the control path identified by the filter are further investigated by traversing into the data path for false loop detection. A removal algorithm is then applied to eliminate the detected false loops, followed by logic minimization to further optimize the circuit. Experimental results show that for the nine example circuits we tested, the final designs after false loop removal and logic minimization give only slightly larger area than the original ones that contain false loops.

REFERENCES

• 1: Hsu, Y. C., LIu, T. Y., TSAI, F. S., LIN, S. Z., AND YU, C. 1994. Digital design from concept to prototype in hours. In Proceedings of the Asian-Pacific Conference on Circuits and Systems (Dec.).
• 2: Shih-Hsu Huang , Ta-Yung Liu , Yu-Chin Hsu , Yen-Jen Oya, Synthesis of false loop free circuits, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.10-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224840]
• 3: Leon Stok, False loops through resource sharing, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.345-348, November 1992, Santa Clara, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Verification; Hardware description languages; Optimization

General Terms:
Algorithms, Design

Keywords:
control path, false loop