Dominator-based partitioning for delay optimization

ABSTRACT

Most of the logic synthesis algorithms are not scalable for large networks and, for this reason, partitioning is often applied. However traditional mincut-based partitioning techniques are not always suitable for delay and area logic optimizations. The paper presents an approach that uses a dominator-based partitioning and conventional logic synthesis techniques for delay optimization of large networks. The calculation of dominators is crucial to find topologically ordered clusters suitable for logic restructuring. As a result, a scalable and efficient strategy for delay optimization is proposed and evaluated, showing tangible improvements with respect to existing techniques. A comparison with a standard mincut-based partitioning technique is also presented.

REFERENCES

• 1: C. I. Park and Y. B. Park, "An efficient algorithm for vlsi network partitioning problem using a cost function with balancing factor," IEEE Trans. on CAD of Int. Circuits and Systems, vol. 12, no. 11, pp. 1686--1694, 1993.
• 2: David Ihsin Cheng , Chih-Chang Lin , Malgorzata Marek-Sadowska, Circuit partitioning with logic perturbation, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.650-655, November 05-09, 1995, San Jose, California, United States
• 3: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 4: Jason Cong , Chang Wu, Global clustering-based performance-driven circuit partitioning, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505424]
• 5: Y. Cheon and D. F. Wong, "Design hierarchy-guided multilevel circuit partitioning," IEEE Trans. on CAD of Int. Circuits and Systems, vol. 22, no. 4, pp. 420--427, 2003.
• 6: Cristinel Ababei , Navaratnasothie Selvakkumaran , Kia Bazargan , George Karypis, Multi-objective circuit partitioning for cutsize and path-based delay minimization, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.181-185, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774599]
• 7: D. Brasen and G. Saucier, "FPGA partitioning for critical paths," in EDAC-ETC-EUROASIC, 1994, pp. 99--103.
• 8: C. N. Sze, T. C. Yang, and L. C. Yang, "Multilevel circuit clustering for delay minimization," IEEE Trans. on CAD of Int. Circuits and Systems, vol. 23, no. 7, pp. 1073--1085, 2004.
• 9: K. Singh, A. Wang, R. Brayton, and A. Sangiovanni-Vincentelli, "Timing optimization of combinational logic," in Proc. Int. Conf. Computer-Aided Design (ICCAD), Nov. 1988, pp. 282--285.
• 10: R. Murgai, R. K. Brayton, and A. Sangiovanni-Vincentelli, "On clustering for minimum delay/area," Proc. ACM/IEEE Design Automation Conference, pp. 6--9, 1991.
• 11: Kuang-Chien Chen , Saburo Muroga, Timing optimization for multi-level combinational networks, Proceedings of the 27th ACM/IEEE conference on Design automation, p.339-344, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.105253]
• 12: H. Ajuha and P. R. Menon, "Delay reduction by segment substitution," Proc. European Conference on Design Automation (EDAC), pp. 82--86, 1994.
• 13: J. Cortadella, "Timing-driven logic bi-decomposition," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 6, pp. 675--685, June 2003.
• 14: H. Touati, H. Savoj, and R. Brayton, "Delay optimization of combinational circuits by clustering and partial collapsing," in Proc. Int. Conf. Computer-Aided Design (ICCAD), Nov. 1991, pp. 188--191.
• 15: R. Rajaraman and D. F. Wong, "Optimal clustering for delay minimization," IEEE Trans. on CAD of Int. Circuits and Systems, vol. 14, no. 12, pp. 1490--1405, 1995.
• 16: H. Yang and D. Wong, "Circuit clustering for delay minimization under area and pin constraints," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 16, no. 9, pp. 976--986, 1997.
• 17: Rajat Aggarwal , Rajeev Murgai , Masahiro Fujita, Speeding up technology-independent timing optimization by network partitioning, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.83-90, November 09-13, 1997, San Jose, California, United States
• 18: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 19: E. Dubrova, M. Teslenko, and A. Martinelli, "On relation between non-disjoint decomposition and multiple-vertex dominators," in Proc. International Symposium on Circuits and Systems, 2004, pp. 493--496.
• 20: W. Havanki , S. Banerjia , T. Conte, Treegion Scheduling for Wide Issue Processors, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.266, January 31-February 04, 1998
• 21: M. Enamul Amyeen , W. Kent Fuchs , Irith Pomeranz , Vamsi Boppana, Fault Equivalence Identification Using Redundancy Information and Static and Dynamic Extraction, Proceedings of the 19th IEEE VLSI Test Symposium, p.124, March 29-April 03, 2001
• 22: Maxim Teslenko , Elena Dubrova, An Efficient Algorithm for Finding Double-Vertex Dominators in Circuit Graphs, Proceedings of the conference on Design, Automation and Test in Europe, p.406-411, March 07-11, 2005 [doi>10.1109/DATE.2005.53]
• 23: E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. Sangiovanni-Vincentelli, "SIS: A system for sequential circuit synthesis," U.C. Berkeley, Tech. Rep., May 1992.
• 24: Peter Eades , Xuemin Lin , W. F. Smyth, A fast and effective heuristic for the feedback arc set problem, Information Processing Letters, v.47 n.6, p.319-323, Oct. 18, 1993 [doi>10.1016/0020-0190(93)90079-O]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design

Keywords:
logic design, logic partitioning, timing optimization